1 /* pmm - parallel matrix multiplication "double diffusion" */
3 /* Copyright (c) 2006, 2007, 2008, 2009, 2010, 2011. The SimGrid Team.
4 * All rights reserved. */
6 /* This program is free software; you can redistribute it and/or modify it
7 * under the terms of the license (GNU LGPL) which comes with this package. */
9 #include "xbt/matrix.h"
12 // #define BENCH_THIS_CODE /* Will only work from within the source tree as we require xbt/xbt_os_time.h, that is not public yet) */
13 #ifdef BENCH_THIS_CODE
14 #include "xbt/xbt_os_time.h"
17 /** @addtogroup MSG_examples
19 * - <b>pmm/msg_pmm.c</b>: Parallel Matrix Multiplication is a little
20 * application. This is something that most MPI developper have
21 * written during their class, here implemented using MSG instead
25 XBT_LOG_NEW_DEFAULT_CATEGORY(msg_pmm,
26 "Messages specific for this msg example");
28 /* This example should always be executed using a deployment of
29 * GRID_SIZE * GRID_SIZE nodes. */
30 #define GRID_SIZE 3 /* Modify to adjust the grid's size */
31 #define NODE_MATRIX_SIZE 300 /* Ammount of work done by each node*/
33 #define GRID_NUM_NODES GRID_SIZE * GRID_SIZE
34 #define MATRIX_SIZE NODE_MATRIX_SIZE * GRID_SIZE
35 #define MAILBOX_NAME_SIZE 10
36 #define NEIGHBOURS_COUNT GRID_SIZE - 1
39 * The job sent to every node
41 typedef struct s_node_job{
44 int nodes_in_row[NEIGHBOURS_COUNT];
45 int nodes_in_col[NEIGHBOURS_COUNT];
48 } s_node_job_t, *node_job_t;
51 * Structure for recovering results
53 typedef struct s_result {
57 } s_result_t, *result_t;
59 int node(int argc, char **argv);
60 static void create_jobs(xbt_matrix_t A, xbt_matrix_t B, node_job_t *jobs);
61 static void broadcast_jobs(node_job_t *jobs);
62 static node_job_t wait_job(int selfid);
63 static void broadcast_matrix(xbt_matrix_t M, int num_nodes, int *nodes);
64 static void get_sub_matrix(xbt_matrix_t *sM, int selfid);
65 static void receive_results(result_t *results);
66 static void task_cleanup(void *arg);
68 int node(int argc, char **argv)
71 char my_mbox[MAILBOX_NAME_SIZE];
72 node_job_t myjob, jobs[GRID_NUM_NODES];
73 xbt_matrix_t A, B, C, sA, sB, sC;
76 xbt_assert(argc != 1, "Wrong number of arguments for this node");
78 /* Initialize the node's data-structures */
80 snprintf(my_mbox, MAILBOX_NAME_SIZE - 1, "%d", myid);
81 sC = xbt_matrix_double_new_zeros(NODE_MATRIX_SIZE, NODE_MATRIX_SIZE);
84 /* Create the matrices to multiply and one to store the result */
85 A = xbt_matrix_double_new_id(MATRIX_SIZE, MATRIX_SIZE);
86 B = xbt_matrix_double_new_seq(MATRIX_SIZE, MATRIX_SIZE);
87 C = xbt_matrix_double_new_zeros(MATRIX_SIZE, MATRIX_SIZE);
89 /* Create the nodes' jobs */
90 create_jobs(A, B, jobs);
92 /* Get own job first */
95 /* Broadcast the rest of the jobs to the other nodes */
96 broadcast_jobs(jobs + 1);
99 A = B = C = NULL; /* Avoid warning at compilation */
100 myjob = wait_job(myid);
103 /* Multiplication main-loop */
104 XBT_VERB("Start Multiplication's Main-loop");
105 for(k=0; k < GRID_SIZE; k++){
107 XBT_VERB("Broadcast sA(%d,%d) to row %d", myjob->row, k, myjob->row);
108 broadcast_matrix(myjob->A, NEIGHBOURS_COUNT, myjob->nodes_in_row);
112 XBT_VERB("Broadcast sB(%d,%d) to col %d", k, myjob->col, myjob->col);
113 broadcast_matrix(myjob->B, NEIGHBOURS_COUNT, myjob->nodes_in_col);
116 if(myjob->row == k && myjob->col == k){
117 xbt_matrix_double_addmult(myjob->A, myjob->B, sC);
118 }else if(myjob->row == k){
119 get_sub_matrix(&sA, myid);
120 xbt_matrix_double_addmult(sA, myjob->B, sC);
122 }else if(myjob->col == k){
123 get_sub_matrix(&sB, myid);
124 xbt_matrix_double_addmult(myjob->A, sB, sC);
127 get_sub_matrix(&sA, myid);
128 get_sub_matrix(&sB, myid);
129 xbt_matrix_double_addmult(sA, sB, sC);
135 /* Node 0: gather the results and reconstruct the final matrix */
138 result_t results[GRID_NUM_NODES] = {0};
140 XBT_VERB("Multiplication done.");
142 /* Get the result from the nodes in the GRID */
143 receive_results(results);
145 /* First add our results */
146 xbt_matrix_copy_values(C, sC, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE,
149 /* Reconstruct the rest of the result matrix */
150 for (node = 1; node < GRID_NUM_NODES; node++){
151 xbt_matrix_copy_values(C, results[node]->sC,
152 NODE_MATRIX_SIZE, NODE_MATRIX_SIZE,
153 NODE_MATRIX_SIZE * results[node]->row,
154 NODE_MATRIX_SIZE * results[node]->col,
156 xbt_matrix_free(results[node]->sC);
157 xbt_free(results[node]);
160 //xbt_matrix_dump(C, "C:res", 0, xbt_matrix_dump_display_double);
166 /* The rest: return the result to node 0 */
170 XBT_VERB("Multiplication done. Send the sub-result.");
172 result = xbt_new0(s_result_t, 1);
173 result->row = myjob->row;
174 result->col = myjob->col;
176 xbt_matrix_new_sub(sC, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, 0, 0, NULL);
177 task = MSG_task_create("result",100,100,result);
178 MSG_task_send(task, "0");
181 /* Clean up and finish*/
183 xbt_matrix_free(myjob->A);
184 xbt_matrix_free(myjob->B);
190 * Broadcast the jobs to the nodes of the grid (except to node 0)
192 static void broadcast_jobs(node_job_t *jobs)
195 char node_mbox[MAILBOX_NAME_SIZE];
197 msg_comm_t comms[GRID_NUM_NODES - 1] = {0};
199 XBT_VERB("Broadcast Jobs");
200 for (node = 1; node < GRID_NUM_NODES; node++){
201 task = MSG_task_create("Job", 100, 100, jobs[node-1]);
202 snprintf(node_mbox, MAILBOX_NAME_SIZE - 1, "%d", node);
203 comms[node-1] = MSG_task_isend(task, node_mbox);
206 MSG_comm_waitall(comms, GRID_NUM_NODES-1, -1);
207 for (node = 1; node < GRID_NUM_NODES; node++)
208 MSG_comm_destroy(comms[node - 1]);
211 static node_job_t wait_job(int selfid)
213 msg_task_t task = NULL;
214 char self_mbox[MAILBOX_NAME_SIZE];
217 snprintf(self_mbox, MAILBOX_NAME_SIZE - 1, "%d", selfid);
218 err = MSG_task_receive(&task, self_mbox);
220 xbt_die("Error while receiving from %s (%d)", self_mbox, (int)err);
221 job = (node_job_t)MSG_task_get_data(task);
222 MSG_task_destroy(task);
223 XBT_VERB("Got Job (%d,%d)", job->row, job->col);
228 static void broadcast_matrix(xbt_matrix_t M, int num_nodes, int *nodes)
231 char node_mbox[MAILBOX_NAME_SIZE];
235 for(node=0; node < num_nodes; node++){
236 snprintf(node_mbox, MAILBOX_NAME_SIZE - 1, "%d", nodes[node]);
237 sM = xbt_matrix_new_sub(M, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, 0, 0, NULL);
238 task = MSG_task_create("sub-matrix", 100, 100, sM);
239 MSG_task_dsend(task, node_mbox, task_cleanup);
240 XBT_DEBUG("sub-matrix sent to %s", node_mbox);
245 static void get_sub_matrix(xbt_matrix_t *sM, int selfid)
247 msg_task_t task = NULL;
248 char node_mbox[MAILBOX_NAME_SIZE];
251 XBT_VERB("Get sub-matrix");
253 snprintf(node_mbox, MAILBOX_NAME_SIZE - 1, "%d", selfid);
254 err = MSG_task_receive(&task, node_mbox);
256 xbt_die("Error while receiving from %s (%d)", node_mbox, (int)err);
257 *sM = (xbt_matrix_t)MSG_task_get_data(task);
258 MSG_task_destroy(task);
261 static void task_cleanup(void *arg){
262 msg_task_t task = (msg_task_t)arg;
263 xbt_matrix_t m = (xbt_matrix_t)MSG_task_get_data(task);
265 MSG_task_destroy(task);
269 * \brief Main function.
271 int main(int argc, char *argv[])
273 #ifdef BENCH_THIS_CODE
274 xbt_os_timer_t timer = xbt_os_timer_new();
277 MSG_init(&argc, argv);
279 char **options = &argv[1];
280 const char* platform_file = options[0];
281 const char* application_file = options[1];
283 MSG_create_environment(platform_file);
285 MSG_function_register("node", node);
286 MSG_launch_application(application_file);
288 #ifdef BENCH_THIS_CODE
289 xbt_os_timer_start(timer);
291 msg_error_t res = MSG_main();
292 #ifdef BENCH_THIS_CODE
293 xbt_os_timer_stop(timer);
295 XBT_CRITICAL("Simulated time: %g", MSG_get_clock());
303 static void create_jobs(xbt_matrix_t A, xbt_matrix_t B, node_job_t *jobs)
305 int node, j, k, row = 0, col = 0;
307 for (node = 0; node < GRID_NUM_NODES; node++){
308 XBT_VERB("Create job %d", node);
309 jobs[node] = xbt_new0(s_node_job_t, 1);
310 jobs[node]->row = row;
311 jobs[node]->col = col;
313 /* Compute who are the nodes in the same row and column */
314 /* than the node receiving this job */
315 for (j = 0, k = 0; j < GRID_SIZE; j++) {
316 if (node != (GRID_SIZE * row) + j) {
317 jobs[node]->nodes_in_row[k] = (GRID_SIZE * row) + j;
322 for (j = 0, k = 0; j < GRID_SIZE; j++) {
323 if (node != (GRID_SIZE * j) + col) {
324 jobs[node]->nodes_in_col[k] = (GRID_SIZE * j) + col;
329 /* Assign a sub matrix of A and B to the job */
331 xbt_matrix_new_sub(A, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE,
332 NODE_MATRIX_SIZE * row, NODE_MATRIX_SIZE * col,
335 xbt_matrix_new_sub(B, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE,
336 NODE_MATRIX_SIZE * row, NODE_MATRIX_SIZE * col,
339 if (++col >= GRID_SIZE){
346 static void receive_results(result_t *results){
348 msg_comm_t comms[GRID_NUM_NODES-1] = {0};
349 msg_task_t tasks[GRID_NUM_NODES-1] = {0};
351 XBT_VERB("Receive Results.");
353 /* Get the result from the nodes in the GRID */
354 for (node = 1; node < GRID_NUM_NODES; node++){
355 comms[node-1] = MSG_task_irecv(&tasks[node-1], "0");
358 MSG_comm_waitall(comms, GRID_NUM_NODES - 1, -1);
359 for (node = 1; node < GRID_NUM_NODES; node++)
360 MSG_comm_destroy(comms[node - 1]);
362 /* Reconstruct the result matrix */
363 for (node = 1; node < GRID_NUM_NODES; node++){
364 results[node] = (result_t)MSG_task_get_data(tasks[node-1]);
365 MSG_task_destroy(tasks[node-1]);