Foster design method

1. Foster brief introduction

Foster Is a method of designing parallel computing programs , There are four steps （Partitioning、Communication、Agglomeration、Mapping） To design parallel computing programs . There is also a design method Culler Follow Foster Be the same in essentials while differing in minor points .

As an example, the question is $1000\times 1000$ Multiply a matrix by a vector . Used 4 Threads .

Give me a vaccination first . The question of matrix times vector is too simple , Be sure to use Foster The design method feels Foster It's a bit of a burden . For example, information transmission 、 Consolidation can actually be done without operations , It can be solved directly at the time of division . however , To be resolved later n-body When waiting for questions Foster Design method can better show its function .

2. design process

2.1 Partitioning

First, divide the problem into smaller subtasks .

Under the large problem of vector multiplication matrix, the problem can be decomposed into $10^6$ Times of multiplication and times of addition . Multiplication is much more expensive than addition , Therefore, only multiplication is regarded as the smallest subtask .

2.2.2 Communication

In the design phase of information transmission , Consider the data to be transferred between threads or the data to be transferred with shared variables .

The calculation results of each multiplication subtask obtained in the previous division process should be handed over to a thread for summation .

Obviously, the process of information transmission is rather tedious , The cost is also relatively high , This problem will be solved in the next integration step .

2.2.3 Agglomeration

The integration step is to merge the sub problems obtained from the previous division , The purpose is to reduce the cost of information transmission or reduce the amount of programming .

In the integration, the multiplication of a row of matrices and vectors can be combined into a sub problem , This completely eliminates the cost of information transmission . And as long as the matrix dimension can be divided by the number of threads, the number of problems solved by each thread is the same .

actually , The normal idea is to divide the calculation of a line of multiplication into a subtask . This is just to highlight Foster The design idea divides each multiplication .

2.2.4 Mapping

The process of mapping is to thread （ Sub problem ） Process mapped to the processor . This process is directly controlled by the operating system or hardware , Programmers generally do not control through code .

3. General design scheme

The following table shows Foster Design method at every step of the design

Step name	Design
Partitioning	Every multiplication of matrix elements and vector elements is divided into a sub problem
Communication	The result of each multiplication should be summarized
Agglomeration	Combine the multiplication of one row into one task
Mapping	Assign threads to different processing units

appendix ： Code implementation

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define DIMENSION 12

int **matrix;
int *vec;
int *result;
int thread = 4;

void *mul(void *r);

int main()
{
    
    //  Initializing matrices and vectors 
    long i, j;
    matrix = (int **)calloc(DIMENSION, sizeof(int *));
    for(i = 0; i < DIMENSION; ++i)
        matrix[i] = (int *)calloc(DIMENSION, sizeof(int));
    vec = (int *)calloc(DIMENSION, sizeof(int));
    result = (int *)calloc(DIMENSION, sizeof(int));
    for(i = 0; i < DIMENSION; ++i)
    {
    
        matrix[i][i] = 1;
        vec[i] = i;
    } 

    printf("Before mul vec:\n");
    for (i = 0; i < DIMENSION; ++i)
        printf("%d ", vec[i]);
    printf("\n");

    pthread_t *handles = (pthread_t *)malloc(thread * sizeof(pthread_t));
    for(i = 0; i < thread; ++i)
        pthread_create(&handles[i], NULL, mul,\
            (void *)i);

    for(i = 0; i < thread; ++i)
        pthread_join(handles[i], NULL);

    printf("After mul vec:\n");
    for(i = 0; i < DIMENSION; ++i)
        printf("%d ", result[i]);
    printf("\n");

    free(handles);
    free(vec);
    free(result);
    for(i = 0; i < DIMENSION; ++i)
        free(matrix[i]);
    free(matrix);

    return 0;
}

void *mul(void *r)
{
    
    long rank = (long)r;
    int len = DIMENSION / thread;
    int fir_dim = rank * len;
    int las_dim = (rank + 1) * len;

    int i, j;
    for(i = fir_dim; i < las_dim; ++i)
        for(j = 0; j < DIMENSION; ++j)
            result[i] += vec[j] * matrix[i][j];
    
    return NULL;
}