examples/msg/pmm/msg_pmm.c

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