Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
00c76e126e67512a67e34a740c5028a355e2b207
[simgrid.git] / examples / msg / app-pmm / app-pmm.c
1 /* pmm - double broadcast parallel matrix multiplication                    */
2
3 /* Copyright (c) 2006-2016. The SimGrid Team. All rights reserved.          */
4
5 /* This program is free software; you can redistribute it and/or modify it
6  * under the terms of the license (GNU LGPL) which comes with this package. */
7
8 #include "simgrid/msg.h"
9 #include "xbt/matrix.h"
10 #include "xbt/xbt_os_time.h"
11
12 XBT_LOG_NEW_DEFAULT_CATEGORY(msg_pmm, "Messages specific for this msg example");
13
14 /* This example should always be executed using a deployment of GRID_SIZE * GRID_SIZE nodes. */
15 #define GRID_SIZE 3           /* Modify to adjust the grid's size */
16 #define NODE_MATRIX_SIZE 300  /* Amount of work done by each node*/
17
18 #define GRID_NUM_NODES GRID_SIZE * GRID_SIZE
19 #define MATRIX_SIZE NODE_MATRIX_SIZE * GRID_SIZE
20 #define MAILBOX_NAME_SIZE 10
21 #define NEIGHBOURS_COUNT GRID_SIZE - 1
22
23 /*
24  * The job sent to every node
25  */
26 typedef struct s_node_job{
27   int row;
28   int col;
29   int nodes_in_row[NEIGHBOURS_COUNT];
30   int nodes_in_col[NEIGHBOURS_COUNT];
31   xbt_matrix_t A;
32   xbt_matrix_t B;
33 } s_node_job_t, *node_job_t;
34
35 /*
36  * Structure for recovering results
37  */
38 typedef struct s_result {
39   int row;
40   int col;
41   xbt_matrix_t sC;
42 } s_result_t, *result_t;
43
44 int node(int argc, char **argv);
45 static void create_jobs(xbt_matrix_t A, xbt_matrix_t B, node_job_t *jobs);
46 static void broadcast_jobs(node_job_t *jobs);
47 static node_job_t wait_job(int selfid);
48 static void broadcast_matrix(xbt_matrix_t M, int num_nodes, int *nodes);
49 static void get_sub_matrix(xbt_matrix_t *sM, int selfid);
50 static void receive_results(result_t *results);
51 static void task_cleanup(void *arg);
52
53 int node(int argc, char **argv)
54 {
55   char my_mbox[MAILBOX_NAME_SIZE];
56   node_job_t myjob, jobs[GRID_NUM_NODES];
57   xbt_matrix_t A = NULL;
58   xbt_matrix_t B = NULL;
59   xbt_matrix_t C = NULL;
60   result_t result;
61
62   xbt_assert(argc != 1, "Wrong number of arguments for this node");
63
64   /* Initialize the node's data-structures */
65   int myid = xbt_str_parse_int(argv[1], "Invalid ID received as first node parameter: %s");
66   snprintf(my_mbox, MAILBOX_NAME_SIZE - 1, "%d", myid);
67   xbt_matrix_t sC = xbt_matrix_double_new_zeros(NODE_MATRIX_SIZE, NODE_MATRIX_SIZE);
68
69   if (myid == 0){
70     /* Create the matrices to multiply and one to store the result */
71     A = xbt_matrix_double_new_id(MATRIX_SIZE, MATRIX_SIZE);
72     B = xbt_matrix_double_new_seq(MATRIX_SIZE, MATRIX_SIZE);
73     C = xbt_matrix_double_new_zeros(MATRIX_SIZE, MATRIX_SIZE);
74
75     /* Create the nodes' jobs */
76     create_jobs(A, B, jobs);
77
78     /* Get own job first */
79     myjob = jobs[0];
80
81     /* Broadcast the rest of the jobs to the other nodes */
82     broadcast_jobs(jobs + 1);
83
84   } else {
85     myjob = wait_job(myid);
86   }
87
88   /* Multiplication main-loop */
89   XBT_VERB("Start Multiplication's Main-loop");
90   for (int k=0; k < GRID_SIZE; k++){
91     xbt_matrix_t sA;
92     xbt_matrix_t sB;
93
94     if(k == myjob->col){
95       XBT_VERB("Broadcast sA(%d,%d) to row %d", myjob->row, k, myjob->row);
96       broadcast_matrix(myjob->A, NEIGHBOURS_COUNT, myjob->nodes_in_row);
97     }
98
99     if(k == myjob->row){
100       XBT_VERB("Broadcast sB(%d,%d) to col %d", k, myjob->col, myjob->col);
101       broadcast_matrix(myjob->B, NEIGHBOURS_COUNT, myjob->nodes_in_col);
102     }
103
104     if(myjob->row == k && myjob->col == k){
105       xbt_matrix_double_addmult(myjob->A, myjob->B, sC);
106     }else if(myjob->row == k){
107       get_sub_matrix(&sA, myid);
108       xbt_matrix_double_addmult(sA, myjob->B, sC);
109       xbt_matrix_free(sA);
110     }else if(myjob->col == k){
111       get_sub_matrix(&sB, myid);
112       xbt_matrix_double_addmult(myjob->A, sB, sC);
113       xbt_matrix_free(sB);
114     }else{
115       get_sub_matrix(&sA, myid);
116       get_sub_matrix(&sB, myid);
117       xbt_matrix_double_addmult(sA, sB, sC);
118       xbt_matrix_free(sA);
119       xbt_matrix_free(sB);
120     }
121   }
122
123   /* Node 0: gather the results and reconstruct the final matrix */
124   if(myid == 0){
125     int node;
126     result_t results[GRID_NUM_NODES] = {0};
127
128     XBT_VERB("Multiplication done.");
129
130     /* Get the result from the nodes in the GRID */
131     receive_results(results);
132
133     /* First add our results */
134     xbt_matrix_copy_values(C, sC, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, 0, 0, 0, 0, NULL);
135
136     /* Reconstruct the rest of the result matrix */
137     for (node = 1; node < GRID_NUM_NODES; node++){
138       xbt_matrix_copy_values(C, results[node]->sC, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE,
139                              NODE_MATRIX_SIZE * results[node]->row, NODE_MATRIX_SIZE * results[node]->col,
140                              0, 0, NULL);
141       xbt_matrix_free(results[node]->sC);
142       xbt_free(results[node]);
143     }
144
145     //xbt_matrix_dump(C, "C:res", 0, xbt_matrix_dump_display_double);
146
147     xbt_matrix_free(A);
148     xbt_matrix_free(B);
149     xbt_matrix_free(C);
150
151   /* The rest: return the result to node 0 */
152   }else{
153     msg_task_t task;
154
155     XBT_VERB("Multiplication done. Send the sub-result.");
156
157     result = xbt_new0(s_result_t, 1);
158     result->row = myjob->row;
159     result->col = myjob->col;
160     result->sC = xbt_matrix_new_sub(sC, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, 0, 0, NULL);
161     task = MSG_task_create("result",100,100,result);
162     MSG_task_send(task, "0");
163   }
164
165   /* Clean up and finish*/
166   xbt_matrix_free(sC);
167   xbt_matrix_free(myjob->A);
168   xbt_matrix_free(myjob->B);
169   xbt_free(myjob);
170   return 0;
171 }
172
173 /*
174  * Broadcast the jobs to the nodes of the grid (except to node 0)
175  */
176 static void broadcast_jobs(node_job_t *jobs)
177 {
178   char node_mbox[MAILBOX_NAME_SIZE];
179   msg_comm_t comms[GRID_NUM_NODES - 1] = {0};
180
181   XBT_VERB("Broadcast Jobs");
182   for (int node = 1; node < GRID_NUM_NODES; node++){
183     msg_task_t task  = MSG_task_create("Job", 100, 100, jobs[node-1]);
184     snprintf(node_mbox, MAILBOX_NAME_SIZE - 1, "%d", node);
185     comms[node-1] = MSG_task_isend(task, node_mbox);
186   }
187
188   MSG_comm_waitall(comms, GRID_NUM_NODES-1, -1);
189   for (int node = 1; node < GRID_NUM_NODES; node++)
190     MSG_comm_destroy(comms[node - 1]);
191 }
192
193 static node_job_t wait_job(int selfid)
194 {
195   msg_task_t task = NULL;
196   char self_mbox[MAILBOX_NAME_SIZE];
197   snprintf(self_mbox, MAILBOX_NAME_SIZE - 1, "%d", selfid);
198   msg_error_t err = MSG_task_receive(&task, self_mbox);
199   xbt_assert(err == MSG_OK, "Error while receiving from %s (%d)", self_mbox, (int)err);
200   node_job_t job  = (node_job_t)MSG_task_get_data(task);
201   MSG_task_destroy(task);
202   XBT_VERB("Got Job (%d,%d)", job->row, job->col);
203
204   return job;
205 }
206
207 static void broadcast_matrix(xbt_matrix_t M, int num_nodes, int *nodes)
208 {
209   char node_mbox[MAILBOX_NAME_SIZE];
210
211   for(int node=0; node < num_nodes; node++){
212     snprintf(node_mbox, MAILBOX_NAME_SIZE - 1, "%d", nodes[node]);
213     xbt_matrix_t sM  = xbt_matrix_new_sub(M, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, 0, 0, NULL);
214     msg_task_t task = MSG_task_create("sub-matrix", 100, 100, sM);
215     MSG_task_dsend(task, node_mbox, task_cleanup);
216     XBT_DEBUG("sub-matrix sent to %s", node_mbox);
217   }
218 }
219
220 static void get_sub_matrix(xbt_matrix_t *sM, int selfid)
221 {
222   msg_task_t task = NULL;
223   char node_mbox[MAILBOX_NAME_SIZE];
224
225   XBT_VERB("Get sub-matrix");
226
227   snprintf(node_mbox, MAILBOX_NAME_SIZE - 1, "%d", selfid);
228   msg_error_t err = MSG_task_receive(&task, node_mbox);
229   xbt_assert(err == MSG_OK, "Error while receiving from %s (%d)", node_mbox, (int)err);
230   *sM = (xbt_matrix_t)MSG_task_get_data(task);
231   MSG_task_destroy(task);
232 }
233
234 static void task_cleanup(void *arg){
235   msg_task_t task = (msg_task_t)arg;
236   xbt_matrix_t m = (xbt_matrix_t)MSG_task_get_data(task);
237   xbt_matrix_free(m);
238   MSG_task_destroy(task);
239 }
240
241 int main(int argc, char *argv[])
242 {
243   xbt_os_timer_t timer = xbt_os_timer_new();
244
245   MSG_init(&argc, argv);
246   MSG_create_environment(argv[1]);
247
248   MSG_function_register("node", node);
249   for(int i = 0 ; i< 9; i++) {
250     char *hostname = bprintf("node-%d.acme.org", i);
251     char **argvF = xbt_new(char *, 3);
252     argvF[0] = xbt_strdup("node");
253     argvF[1] = bprintf("%d", i);
254     argvF[2] = NULL;
255     MSG_process_create_with_arguments("node", node, NULL, MSG_host_by_name(hostname), 2, argvF);
256     xbt_free(hostname);
257   }
258
259   xbt_os_cputimer_start(timer);
260   msg_error_t res = MSG_main();
261   xbt_os_cputimer_stop(timer);
262   XBT_CRITICAL("Simulated time: %g", MSG_get_clock());
263
264   return res != MSG_OK;
265 }
266
267 static void create_jobs(xbt_matrix_t A, xbt_matrix_t B, node_job_t *jobs)
268 {
269   int row = 0;
270   int col = 0;
271
272   for (int node = 0; node < GRID_NUM_NODES; node++){
273     XBT_VERB("Create job %d", node);
274     jobs[node] = xbt_new0(s_node_job_t, 1);
275     jobs[node]->row = row;
276     jobs[node]->col = col;
277
278     /* Compute who are the nodes in the same row and column */
279     /* than the node receiving this job */
280     for (int j = 0, k = 0; j < GRID_SIZE; j++) {
281       if (node != (GRID_SIZE * row) + j) {
282         jobs[node]->nodes_in_row[k] = (GRID_SIZE * row) + j;
283         k++;
284       }
285     }
286
287     for (int j = 0, k = 0; j < GRID_SIZE; j++) {
288       if (node != (GRID_SIZE * j) + col) {
289         jobs[node]->nodes_in_col[k] = (GRID_SIZE * j) + col;
290         k++;
291       }
292     }
293
294     /* Assign a sub matrix of A and B to the job */
295     jobs[node]->A =
296       xbt_matrix_new_sub(A, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE * row, NODE_MATRIX_SIZE * col, NULL);
297     jobs[node]->B =
298       xbt_matrix_new_sub(B, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE * row, NODE_MATRIX_SIZE * col, NULL);
299
300     if (++col >= GRID_SIZE){
301       col = 0;
302       row++;
303     }
304   }
305 }
306
307 static void receive_results(result_t *results) {
308   msg_comm_t comms[GRID_NUM_NODES-1] = {0};
309   msg_task_t tasks[GRID_NUM_NODES-1] = {0};
310
311   XBT_VERB("Receive Results.");
312
313   /* Get the result from the nodes in the GRID */
314   for (int node = 1; node < GRID_NUM_NODES; node++)
315    comms[node-1] = MSG_task_irecv(&tasks[node-1], "0");
316
317   MSG_comm_waitall(comms, GRID_NUM_NODES - 1, -1);
318   for (int node = 1; node < GRID_NUM_NODES; node++)
319     MSG_comm_destroy(comms[node - 1]);
320
321   /* Reconstruct the result matrix */
322   for (int node = 1; node < GRID_NUM_NODES; node++){
323     results[node] = (result_t)MSG_task_get_data(tasks[node-1]);
324     MSG_task_destroy(tasks[node-1]);
325   }
326 }