我通常只看到这称为数据重新分配,其理解是,如果您正在重新分配它,您希望分配在某些指标下是最佳的,例如任务之间的均匀性。
当您尝试进行计算负载平衡时,这确实出现在科学/技术计算中。即使您在多个维度上进行计算,如果您通过空间填充曲线重新分配分配给处理器的空间数据,就会出现这个确切的问题,并且您通常确实希望数据被均匀划分。
该过程非常简单;你首先取x i的唯一前缀总和,这样你就知道有多少项目在你的“左边”。例如,对于上面 Noxville 的示例,如果您有数据
[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