Tôi thường chỉ thấy điều này được gọi là phân phối lại dữ liệu, với sự hiểu biết là nếu bạn phân phối lại nó, bạn muốn phân phối tối ưu theo một số chỉ số, như độ đều giữa các tác vụ.
Điều này xảy ra trong tính toán khoa học/kỹ thuật khi bạn đang cố gắng thực hiện cân bằng tải tính toán. Ngay cả khi bạn đang tính toán trong một số thứ nguyên, nếu bạn đang phân phối lại dữ liệu không gian mà bạn gán cho bộ vi xử lý bằng đường cong đầy không gian, vấn đề chính xác này xuất hiện và bạn thường muốn dữ liệu được chia đều.
Quy trình này khá đơn giản; bạn bắt đầu bằng cách lấy một độc quyền prefix sum của x i để bạn biết có bao nhiêu mục là "trái" của bạn. Ví dụ, ví dụ Noxville của trên, nếu bạn có dữ liệu
[9, 6, 1, 6, 2]
số tiền prefix sẽ
[0, 9, 15, 16, 22]
và bạn muốn tìm (từ tổng bộ vi xử lý mới nhất của cộng có bao nhiêu nó có) mà có Tổng cộng 24 mục.
Sau đó, bạn tìm ra phân vùng lý tưởng của bạn lớn đến mức nào - giả sử, ceil (totitems/nprocs). Bạn có thể làm điều này tuy nhiên bạn thích miễn là mọi bộ vi xử lý sẽ đồng ý về những gì tất cả các kích thước phân vùng sẽ được.
Bây giờ, bạn có một số cách để tiếp tục. Nếu các mục dữ liệu lớn theo một nghĩa nào đó và bạn không thể có hai bản sao của chúng trong bộ nhớ, thì bạn có thể bắt đầu chuyển dữ liệu sang các nước láng giềng gần nhất. Bạn biết số lượng các mục bên trái của bạn và "dư thừa" hoặc "thâm hụt" theo hướng đó; và bạn cũng biết có bao nhiêu bạn có (và sẽ có sau khi bạn đã thực hiện một phần của bạn để sửa chữa dư thừa hoặc thâm hụt). Vì vậy, bạn bắt đầu gửi dữ liệu đến hàng xóm bên trái và bên phải của bạn, và nhận dữ liệu từ hàng xóm bên trái và bên phải của bạn, cho đến khi các bộ vi xử lý để lại có số lượng mục phù hợp và bạn cũng làm như vậy.
Nhưng nếu bạn có đủ khả năng để có hai bản sao của dữ liệu, thì bạn có thể thực hiện một cách tiếp cận khác giúp giảm thiểu số lượng thư được gửi. Bạn có thể nghĩ số lượng ô ở bên trái của bạn là chỉ mục bắt đầu của dữ liệu cục bộ của bạn vào mảng "toàn cục". Vì bạn biết có bao nhiêu mục mà mỗi bộ xử lý sẽ kết thúc, bạn có thể tìm ra trực tiếp quy trình nào sẽ kết thúc và có thể gửi chúng trực tiếp. (Ví dụ, trong ví dụ trên, procesor 0 - có các mục 0..8 - biết rằng nếu mỗi bộ xử lý nhưng cuối cùng sẽ kết thúc với 5 mục dữ liệu thì giá trị 5-8 có thể được gửi tới bộ xử lý 1.) Một khi chúng được gửi đi, bạn chỉ đơn giản nhận được cho đến khi bạn có lượng dữ liệu bạn đang mong đợi; và bạn đã hoàn tất.
Dưới đây là một ví dụ đơn giản về việc thực hiện điều này trong C và MPI, nhưng cách tiếp cận cơ bản sẽ hoạt động khá nhiều ở mọi nơi. Hoạt động quét tiền tố của MPI tạo ra các khoản tiền bao gồm, vì vậy chúng tôi phải trừ số giá trị của riêng mình để có được số tiền độc quyền:
#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;
}
Chạy điều này. lưu ý rằng cách tôi đã xác định phân vùng "mong muốn" (sử dụng ceil (totvals/nprocesses)) bộ xử lý cuối cùng nói chung sẽ được tải dưới. Ngoài ra, tôi đã không thực hiện bất kỳ nỗ lực nào để đảm bảo trật tự được giữ lại trong phân phối lại (mặc dù điều đó đủ dễ dàng để thực hiện nếu đơn hàng quan trọng):
$ 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
Câu hỏi của bạn chưa được xác định. Ví dụ, có thể tá tá các nút xa đồng thời nói chuyện với những người hàng xóm gần của họ, với chi phí 1? Nếu 100 nút có thư đến X, họ có thể gửi tất cả cùng một lúc, với chi phí 1 hay chúng phải được đăng theo thứ tự, với chi phí 100? Các thuật toán khác nhau sẽ áp dụng cho [mô hình tính toán] khác nhau (http://en.wikipedia.org/wiki/Models_of_computation). Cụ thể, nêu rõ [cấu trúc liên kết mạng] (http://en.wikipedia.org/wiki/Network_topology) và/hoặc mô hình bộ nhớ phân tán. –
Nó thực sự chưa được xác định, nhưng một vài câu trả lời dưới đây đã cung cấp rất nhiều trợ giúp. – Gus