Я обычно вижу это как перераспределение данных, с пониманием, что если вы перераспределяете его, вы хотите, чтобы распределение было оптимальным по некоторой метрике, такой как равномерность между задачами.
Это действительно происходит вНаучно-технические вычисления, когда вы пытаетесь сбалансировать вычислительную нагрузку.Даже если вы выполняете вычисления в нескольких измерениях, если вы перераспределяете пространственные данные, которые вы назначаете процессорам, по кривой заполнения пространства, возникает именно эта проблема, и там вы часто хотите, чтобы данные были равномерно разделены.
Процедура довольно проста;вы начинаете с того, что берете эксклюзивную префиксную сумму из x i , чтобы вы знали, сколько предметов находится «слева» от вас.Например, для приведенного выше примера Ноксвилла, если бы у вас были данные
[9, 6, 1, 6, 2]
, префиксные суммы были бы
[0, 9, 15, 16, 22]
, и вы бы нашли (из суммы последнего процессора плюс сколько у него есть данных).) что всего 24 элемента.
Затем вы выясните, насколько большими будут ваши идеальные разделы - скажем, ceil (totitems / nprocs).Вы можете делать это так, как вам нравится, при условии, что каждый процессор согласует, какими будут размеры всех разделов.
Теперь у вас есть несколько способов продолжить работу.Если элементы данных в некотором смысле велики и у вас не может быть двух копий в памяти, вы можете начать сдвигать данные только для ближайших соседей.Вы знаете количество предметов слева и «избыток» или «дефицит» в этом направлении;и вы также знаете, сколько у вас есть (и будет после того, как вы сделали свою часть, чтобы исправить избыток или дефицит).Таким образом, вы начинаете отправлять данные своему левому и правому соседу и получать данные от своего левого и правого соседа, пока у процессоров слева не соберется нужное количество элементов, как и у вас.
Но если вы можете позволить себе иметь две копии данных, тогда вы можете использовать другой подход, который минимизирует количество отправляемых сообщений.Вы можете думать о количестве ячеек слева от вас как начальный индекс ваших локальных данных в «глобальном» массиве.Поскольку вы знаете, сколько элементов будет у каждого процессора, вы сможете напрямую определить, к какому процессу будут обрабатываться эти элементы, и можете отправлять их напрямую.(Например, в приведенном выше примере процессор 0 - который имеет элементы 0..8 - знает, что если каждый процессор, кроме последнего, получит 5 элементов данных, то значения 5-8 могут быть отправлены процессору 1.После того, как они отправлены, вы просто получаете, пока не получите ожидаемый объем данных;и все готово.
Ниже приведен простой пример выполнения этого в C и MPI, но базовый подход должен работать практически везде.Операция сканирования префиксов MPI генерирует инклюзивные суммы, поэтому мы должны вычесть наше собственное количество значений, чтобы получить эксклюзивную сумму:
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <time.h>
void initdata(const int rank, const int maxvals, char **data, int *nvals) {
time_t t;
unsigned seed;
t = time(NULL);
seed = (unsigned)(t * (rank + 1));
srand(seed);
*nvals = (rand() % (maxvals-1)) + 1;
*data = malloc((*nvals+1) * sizeof(char));
for (int i=0; i<*nvals; i++) {
(*data)[i] = 'A' + (rank % 26);
}
(*data)[*nvals] = '\0';
}
int assignrank(const int globalid, const int totvals, const int size) {
int nvalsperrank = (totvals + size - 1)/size;
return (globalid/nvalsperrank);
}
void redistribute(char **data, const int totvals, const int curvals, const int globalstart,
const int rank, const int size, int *newnvals) {
const int stag = 1;
int nvalsperrank = (totvals + size - 1)/size;
*newnvals = nvalsperrank;
if (rank == size-1) *newnvals = totvals - (size-1)*nvalsperrank;
char *newdata = malloc((*newnvals+1) * sizeof(char));
newdata[(*newnvals)] = '\0';
MPI_Request requests[curvals];
int nmsgs=0;
/* figure out whose data we have, redistribute it */
int start=0;
int newrank = assignrank(globalstart, totvals, size);
for (int val=1; val<curvals; val++) {
int nextrank = assignrank(globalstart+val, totvals, size);
if (nextrank != newrank) {
MPI_Isend(&((*data)[start]), (val-1)-start+1, MPI_CHAR, newrank, stag, MPI_COMM_WORLD, &(requests[nmsgs]));
nmsgs++;
start = val;
newrank = nextrank;
}
}
MPI_Isend(&((*data)[start]), curvals-start, MPI_CHAR, newrank, stag, MPI_COMM_WORLD, &(requests[nmsgs]));
nmsgs++;
/* now receive all of our data */
int newvalssofar= 0;
int count;
MPI_Status status;
while (newvalssofar != *newnvals) {
MPI_Recv(&(newdata[newvalssofar]), *newnvals - newvalssofar, MPI_CHAR, MPI_ANY_SOURCE, stag, MPI_COMM_WORLD, &status);
MPI_Get_count(&status, MPI_CHAR, &count);
newvalssofar += count;
}
/* wait until all of our sends have been received */
MPI_Status statuses[curvals];
MPI_Waitall(nmsgs, requests, statuses);
/* now we can get rid of data and relace it with newdata */
free(*data);
*data = newdata;
}
int main(int argc, char **argv) {
const int maxvals=30;
int size, rank;
char *data;
int mycurnvals, mylvals, myfinalnvals;
int totvals;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
initdata(rank, maxvals, &data, &mycurnvals);
MPI_Scan( &mycurnvals, &mylvals, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD );
if (rank == size-1) totvals = mylvals;
mylvals -= mycurnvals;
MPI_Bcast( &totvals, 1, MPI_INT, size-1, MPI_COMM_WORLD );
printf("%3d : %s %d\n", rank, data, mylvals);
redistribute(&data, totvals, mycurnvals, mylvals, rank, size, &myfinalnvals);
printf("%3d after: %s\n", rank, data);
free(data);
MPI_Finalize();
return 0;
}
Запустив это, вы получите ожидаемое поведение;обратите внимание, что, как я определил «желаемое» разбиение (используя ceil (totvals / nprocesses)), конечный процессор, как правило, будет недостаточно загружен.Кроме того, я не делал никаких попыток обеспечить сохранение порядка при перераспределении (хотя это достаточно легко сделать, если порядок важен):
$ mpirun -np 13 ./distribute
0 : AAAAAAAAAAA 0
1 : BBBBBBBBBBBB 11
2 : CCCCCCCCCCCCCCCCCCCCCCCCCC 23
3 : DDDDDDD 49
4 : EEEEEEEEE 56
5 : FFFFFFFFFFFFFFFFFF 65
6 : G 83
7 : HHHHHHH 84
8 : IIIIIIIIIIIIIIIIIIIII 91
9 : JJJJJJJJJJJJJJJJJJ 112
10 : KKKKKKKKKKKKKKKKKKKK 130
11 : LLLLLLLLLLLLLLLLLLLLLLLLLLLL 150
12 : MMMMMMMMMMMMMMMMMM 178
0 after: AAAAAAAAAAABBBBB
1 after: BBBBBBBCCCCCCCCC
2 after: CCCCCCCCCCCCCCCC
3 after: DDDDDDDCEEEEEEEE
4 after: EFFFFFFFFFFFFFFF
5 after: FFFHHHHHHHIIIIIG
6 after: IIIIIIIIIIIIIIII
7 after: JJJJJJJJJJJJJJJJ
8 after: JJKKKKKKKKKKKKKK
9 after: LLLLLLLLLLKKKKKK
10 after: LLLLLLLLLLLLLLLL
11 after: LLMMMMMMMMMMMMMM
12 after: MMMM