Calcul de la somme en parallèle

Question

Ceci est une question d'interview. N

N nœuds, chaque nœud se compose de quelques champs et méthodes. Ce sont:

// Every node has an ID. All of these IDs are sequential, and begin with 0. 
// i.e. all ids are uniquely in the range of 0 t N-1 
int id; 
int val; // Every node has a value 
int max; // max = N. Every node knows how many nodes are in the system. 

void send(int idTo, int payload) 
int recv(int idFrom) 

Ecrire un seul morceau de code qui fonctionne sur chaque nœud simultanément, de sorte que quand il est fini en cours d'exécution chaque nœud dans le système connaît la somme des valeurs de tous les nœuds du système.

Answer 1

une solution:

Chaque nœud envoie la somme qu'il a reçu au noeud suivant dans le système. Première fois que chaque nœud reçoit le numéro du nœud précédent, il le note en bas. La prochaine fois qu'il reçoit un nombre -> il soustrait ce nombre du nombre précédent et c'est la somme.

reçoivent recevront un numéro de noeud précédent dans le système et ajouter son propre numéro à lui envoyer enverra au nœud suivant dans le système reçoivent alors attendra une autre entrée du noeud précédent

Answer 2

Vous pouvez diffuser votre valeur à chaque nœud et recevoir les valeurs de tous les autres nœuds. De cette façon, chaque noeud fera l'addition et connaîtra le résultat. Cependant, je pense que cela pourrait être très inefficace.

J'aime mieux l'idée dans les réponses précédentes de recevoir la somme partielle du nœud précédent, ajouter votre propre valeur et passer la nouvelle somme au nœud suivant. Ensuite, vous devez transmettre le résultat final dans l'autre sens afin que chaque nœud connaisse la réponse à la fin. Mais si vous souhaitez exploiter le fait que tous les nœuds peuvent s'exécuter simultanément, vous pouvez démarrer la première propagation à partir des deux extrémités et obtenir le résultat final au milieu, puis effectuer la deuxième traversée également dans les deux directions. Cela vous permettra d'économiser la moitié du temps. Mieux encore, suivant la même idée, vous pouvez faire la somme par paires et envoyer les résultats partiels aux quatrièmes nœuds, puis à la huitième, et ainsi de suite. Cette stratégie prendra seulement O (lg n) pour arriver au milieu.