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