मुझे आमतौर पर यह डेटा पुनर्वितरण कहा जाता है, यह समझने के साथ कि यदि आप इसे फिर से वितरित कर रहे हैं तो आप कुछ मीट्रिक के तहत वितरण को इष्टतम होना चाहते हैं, जैसे कार्यों के बीच समानता।
यह कम्प्यूटेशनल लोड संतुलन करने की कोशिश कर रहे समय में वैज्ञानिक/तकनीकी कंप्यूटिंग में आता है। यहां तक कि यदि आप कई आयामों में गणना कर रहे हैं, यदि आप स्पेस भरने वाले वक्र द्वारा प्रोसेसर को असाइन करने वाले स्थानिक डेटा को फिर से वितरित कर रहे हैं, तो यह सटीक समस्या आती है, और वहां आप अक्सर डेटा को समान रूप से विभाजित करना चाहते हैं।
प्रक्रिया बहुत सरल है; आप x i का एक विशेष prefix sum लेना शुरू करते हैं ताकि आप जान सकें कि आपके "बाएं" कितने आइटम हैं। उदाहरण के लिए, ऊपर Noxville के उदाहरण के लिए, यदि आप डेटा था
[9, 6, 1, 6, 2]
उपसर्ग रकम
[0, 9, 15, 16, 22]
हो सकता है और आप (पिछले प्रोसेसर की राशि से अधिक कितने है) पाते हैं देखते हैं कि कुल में 24 आइटम।
फिर आप यह पता लगाते हैं कि आपके आदर्श विभाजन कितने बड़े होंगे - कहें, ceil (totitems/nprocs)। आप ऐसा कर सकते हैं हालांकि आप जब तक प्रत्येक प्रोसेसर इस बात पर सहमत होंगे कि सभी विभाजन आकार क्या होंगे।
अब, आपके पास आगे बढ़ने के कुछ तरीके हैं। यदि डेटा आइटम कुछ अर्थों में बड़े होते हैं और आपके पास स्मृति में दो प्रतियां नहीं हो सकती हैं, तो आप डेटा को अपने निकटतम पड़ोसियों में स्थानांतरित करना शुरू कर सकते हैं। आप अपने बाईं ओर वस्तुओं की संख्या और उस दिशा में "अतिरिक्त" या "घाटा" जानते हैं; और आप यह भी जानते हैं कि आपके पास कितने हैं (और अतिरिक्त या घाटे को ठीक करने के लिए आपने अपना हिस्सा पूरा करने के बाद किया होगा)। तो आप अपने बाएं और दाएं पड़ोसी को डेटा भेजना शुरू करते हैं, और अपने बाएं और दाएं पड़ोसी से डेटा प्राप्त करते हैं, जब तक प्रोसेसर को सामूहिक रूप से सही मात्रा में आइटम नहीं मिलते हैं और आप भी करते हैं।
लेकिन यदि आप डेटा की दो प्रतियां प्राप्त कर सकते हैं, तो आप एक और दृष्टिकोण ले सकते हैं जो भेजे गए संदेशों की संख्या को कम करता है। आप अपने स्थानीय डेटा की शुरुआती इंडेक्स के रूप में "ग्लोबल" सरणी में अपने बाएं सेल्स की संख्या के बारे में सोच सकते हैं। चूंकि आप जानते हैं कि प्रत्येक प्रोसेसर के साथ कितने आइटम समाप्त होंगे, आप सीधे पता लगा सकते हैं कि उन वस्तुओं को किस प्रक्रिया में समाप्त किया जाएगा, और उन्हें सीधे भेज सकते हैं। (उदाहरण के लिए, ऊपर दिए गए उदाहरण में, प्रोसेसर 0 - जिसमें आइटम 0..8 है - जानता है कि यदि प्रत्येक प्रोसेसर लेकिन आखिरी बार 5 डेटा आइटम्स के साथ समाप्त हो रहा है, तो 5-8 मान प्रोसेसर 1 को भेजा जा सकता है।) एक बार भेजे जाने के बाद, आप तब तक प्राप्त करते हैं जब तक आपके पास अपेक्षित डेटा की मात्रा न हो; और आपने कल लिया।
नीचे सी और एमपीआई में ऐसा करने का एक सरल उदाहरण है, लेकिन मूल दृष्टिकोण कहीं भी कहीं भी काम करना चाहिए। एमपीआई के उपसर्ग स्कैन आपरेशन समावेशी रकम उत्पन्न करता है, तो हम मान की अपनी संख्या बंद घटाना करने के लिए विशेष राशि प्राप्त करने के लिए:
#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;
}
चल रहा है यह आपके अपेक्षित व्यवहार मिलता है, ध्यान दें कि जिस तरह से मैंने "वांछित" विभाजन निर्धारित किया है (छत (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
आपका प्रश्न underspecified है: इसके अलावा, मुझे लगता है कि आदेश पुनर्वितरण में संरक्षित है सुनिश्चित करने के लिए (हालांकि वह पर्याप्त है, तो क्रम महत्वपूर्ण है ऐसा करना आसान है) किसी भी प्रयास नहीं किए हैं। उदाहरण के लिए, क्या एक दर्जन दूर नोड्स एक साथ लागत के समय अपने पड़ोसियों से बात कर सकते हैं? यदि 100 नोड्स में एक्स के लिए संदेश हैं, तो क्या वे उन्हें एक ही समय में, लागत 1 पर भेज सकते हैं, या क्या उन्हें लागत 100 पर क्रमबद्ध किया जाना चाहिए? अलग-अलग एल्गोरिदम अलग-अलग [गणना के मॉडल] के लिए लागू होंगे (http://en.wikipedia.org/wiki/Models_of_computation)। विशेष रूप से, एक [नेटवर्क टोपोलॉजी] (http://en.wikipedia.org/wiki/Network_topology) और/या वितरित स्मृति मॉडल बताएं। –
यह वास्तव में अनिर्धारित है, लेकिन नीचे दिए गए कुछ उत्तरों से पहले ही बहुत मदद मिली है। – Gus