examples/msg/pmm/msg_pmm.c

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