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   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     xbt_matrix_t sC;
  94
  95     if(k == myjob->col){
  96       XBT_VERB("Broadcast sA(%d,%d) to row %d", myjob->row, k, myjob->row);
  97       broadcast_matrix(myjob->A, NEIGHBOURS_COUNT, myjob->nodes_in_row);
  98     }
  99
 100     if(k == myjob->row){
 101       XBT_VERB("Broadcast sB(%d,%d) to col %d", k, myjob->col, myjob->col);
 102       broadcast_matrix(myjob->B, NEIGHBOURS_COUNT, myjob->nodes_in_col);
 103     }
 104
 105     if(myjob->row == k && myjob->col == k){
 106       xbt_matrix_double_addmult(myjob->A, myjob->B, sC);
 107     }else if(myjob->row == k){
 108       get_sub_matrix(&sA, myid);
 109       xbt_matrix_double_addmult(sA, myjob->B, sC);
 110       xbt_matrix_free(sA);
 111     }else if(myjob->col == k){
 112       get_sub_matrix(&sB, myid);
 113       xbt_matrix_double_addmult(myjob->A, sB, sC);
 114       xbt_matrix_free(sB);
 115     }else{
 116       get_sub_matrix(&sA, myid);
 117       get_sub_matrix(&sB, myid);
 118       xbt_matrix_double_addmult(sA, sB, sC);
 119       xbt_matrix_free(sA);
 120       xbt_matrix_free(sB);
 121     }
 122   }
 123
 124   /* Node 0: gather the results and reconstruct the final matrix */
 125   if(myid == 0){
 126     int node;
 127     result_t results[GRID_NUM_NODES] = {0};
 128
 129     XBT_VERB("Multiplication done.");
 130
 131     /* Get the result from the nodes in the GRID */
 132     receive_results(results);
 133
 134     /* First add our results */
 135     xbt_matrix_copy_values(C, sC, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, 0, 0, 0, 0, NULL);
 136
 137     /* Reconstruct the rest of the result matrix */
 138     for (node = 1; node < GRID_NUM_NODES; node++){
 139       xbt_matrix_copy_values(C, results[node]->sC, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE,
 140                              NODE_MATRIX_SIZE * results[node]->row, NODE_MATRIX_SIZE * results[node]->col,
 141                              0, 0, NULL);
 142       xbt_matrix_free(results[node]->sC);
 143       xbt_free(results[node]);
 144     }
 145
 146     //xbt_matrix_dump(C, "C:res", 0, xbt_matrix_dump_display_double);
 147
 148     xbt_matrix_free(A);
 149     xbt_matrix_free(B);
 150     xbt_matrix_free(C);
 151
 152   /* The rest: return the result to node 0 */
 153   }else{
 154     msg_task_t task;
 155
 156     XBT_VERB("Multiplication done. Send the sub-result.");
 157
 158     result = xbt_new0(s_result_t, 1);
 159     result->row = myjob->row;
 160     result->col = myjob->col;
 161     result->sC = xbt_matrix_new_sub(sC, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, 0, 0, NULL);
 162     task = MSG_task_create("result",100,100,result);
 163     MSG_task_send(task, "0");
 164   }
 165
 166   /* Clean up and finish*/
 167   xbt_matrix_free(sC);
 168   xbt_matrix_free(myjob->A);
 169   xbt_matrix_free(myjob->B);
 170   xbt_free(myjob);
 171   return 0;
 172 }
 173
 174 /*
 175  * Broadcast the jobs to the nodes of the grid (except to node 0)
 176  */
 177 static void broadcast_jobs(node_job_t *jobs)
 178 {
 179   char node_mbox[MAILBOX_NAME_SIZE];
 180   msg_comm_t comms[GRID_NUM_NODES - 1] = {0};
 181
 182   XBT_VERB("Broadcast Jobs");
 183   for (int node = 1; node < GRID_NUM_NODES; node++){
 184     msg_task_t task  = MSG_task_create("Job", 100, 100, jobs[node-1]);
 185     snprintf(node_mbox, MAILBOX_NAME_SIZE - 1, "%d", node);
 186     comms[node-1] = MSG_task_isend(task, node_mbox);
 187   }
 188
 189   MSG_comm_waitall(comms, GRID_NUM_NODES-1, -1);
 190   for (int node = 1; node < GRID_NUM_NODES; node++)
 191     MSG_comm_destroy(comms[node - 1]);
 192 }
 193
 194 static node_job_t wait_job(int selfid)
 195 {
 196   msg_task_t task = NULL;
 197   char self_mbox[MAILBOX_NAME_SIZE];
 198   snprintf(self_mbox, MAILBOX_NAME_SIZE - 1, "%d", selfid);
 199   msg_error_t err = MSG_task_receive(&task, self_mbox);
 200   xbt_assert(err == MSG_OK, "Error while receiving from %s (%d)", self_mbox, (int)err);
 201   node_job_t job  = (node_job_t)MSG_task_get_data(task);
 202   MSG_task_destroy(task);
 203   XBT_VERB("Got Job (%d,%d)", job->row, job->col);
 204
 205   return job;
 206 }
 207
 208 static void broadcast_matrix(xbt_matrix_t M, int num_nodes, int *nodes)
 209 {
 210   char node_mbox[MAILBOX_NAME_SIZE];
 211
 212   for(int node=0; node < num_nodes; node++){
 213     snprintf(node_mbox, MAILBOX_NAME_SIZE - 1, "%d", nodes[node]);
 214     xbt_matrix_t sM  = xbt_matrix_new_sub(M, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, 0, 0, NULL);
 215     msg_task_t task = MSG_task_create("sub-matrix", 100, 100, sM);
 216     MSG_task_dsend(task, node_mbox, task_cleanup);
 217     XBT_DEBUG("sub-matrix sent to %s", node_mbox);
 218   }
 219 }
 220
 221 static void get_sub_matrix(xbt_matrix_t *sM, int selfid)
 222 {
 223   msg_task_t task = NULL;
 224   char node_mbox[MAILBOX_NAME_SIZE];
 225
 226   XBT_VERB("Get sub-matrix");
 227
 228   snprintf(node_mbox, MAILBOX_NAME_SIZE - 1, "%d", selfid);
 229   msg_error_t err = MSG_task_receive(&task, node_mbox);
 230   xbt_assert(err == MSG_OK, "Error while receiving from %s (%d)", node_mbox, (int)err);
 231   *sM = (xbt_matrix_t)MSG_task_get_data(task);
 232   MSG_task_destroy(task);
 233 }
 234
 235 static void task_cleanup(void *arg){
 236   msg_task_t task = (msg_task_t)arg;
 237   xbt_matrix_t m = (xbt_matrix_t)MSG_task_get_data(task);
 238   xbt_matrix_free(m);
 239   MSG_task_destroy(task);
 240 }
 241
 242 int main(int argc, char *argv[])
 243 {
 244   xbt_os_timer_t timer = xbt_os_timer_new();
 245
 246   MSG_init(&argc, argv);
 247   MSG_create_environment(argv[1]);
 248
 249   MSG_function_register("node", node);
 250   for(int i = 0 ; i< 9; i++) {
 251     char *hostname = bprintf("node-%d.acme.org", i);
 252     char **argvF = xbt_new(char *, 3);
 253     argvF[0] = xbt_strdup("node");
 254     argvF[1] = bprintf("%d", i);
 255     argvF[2] = NULL;
 256     MSG_process_create_with_arguments("node", node, NULL, MSG_host_by_name(hostname), 2, argvF);
 257     xbt_free(hostname);
 258   }
 259
 260   xbt_os_cputimer_start(timer);
 261   msg_error_t res = MSG_main();
 262   xbt_os_cputimer_stop(timer);
 263   XBT_CRITICAL("Simulated time: %g", MSG_get_clock());
 264
 265   return res != MSG_OK;
 266 }
 267
 268 static void create_jobs(xbt_matrix_t A, xbt_matrix_t B, node_job_t *jobs)
 269 {
 270   int row = 0;
 271   int col = 0;
 272
 273   for (int node = 0; node < GRID_NUM_NODES; node++){
 274     XBT_VERB("Create job %d", node);
 275     jobs[node] = xbt_new0(s_node_job_t, 1);
 276     jobs[node]->row = row;
 277     jobs[node]->col = col;
 278
 279     /* Compute who are the nodes in the same row and column */
 280     /* than the node receiving this job */
 281     for (int j = 0, k = 0; j < GRID_SIZE; j++) {
 282       if (node != (GRID_SIZE * row) + j) {
 283         jobs[node]->nodes_in_row[k] = (GRID_SIZE * row) + j;
 284         k++;
 285       }
 286     }
 287
 288     for (int j = 0, k = 0; j < GRID_SIZE; j++) {
 289       if (node != (GRID_SIZE * j) + col) {
 290         jobs[node]->nodes_in_col[k] = (GRID_SIZE * j) + col;
 291         k++;
 292       }
 293     }
 294
 295     /* Assign a sub matrix of A and B to the job */
 296     jobs[node]->A =
 297       xbt_matrix_new_sub(A, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE * row, NODE_MATRIX_SIZE * col, NULL);
 298     jobs[node]->B =
 299       xbt_matrix_new_sub(B, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE, NODE_MATRIX_SIZE * row, NODE_MATRIX_SIZE * col, NULL);
 300
 301     if (++col >= GRID_SIZE){
 302       col = 0;
 303       row++;
 304     }
 305   }
 306 }
 307
 308 static void receive_results(result_t *results) {
 309   msg_comm_t comms[GRID_NUM_NODES-1] = {0};
 310   msg_task_t tasks[GRID_NUM_NODES-1] = {0};
 311
 312   XBT_VERB("Receive Results.");
 313
 314   /* Get the result from the nodes in the GRID */
 315   for (int node = 1; node < GRID_NUM_NODES; node++)
 316    comms[node-1] = MSG_task_irecv(&tasks[node-1], "0");
 317
 318   MSG_comm_waitall(comms, GRID_NUM_NODES - 1, -1);
 319   for (int node = 1; node < GRID_NUM_NODES; node++)
 320     MSG_comm_destroy(comms[node - 1]);
 321
 322   /* Reconstruct the result matrix */
 323   for (int node = 1; node < GRID_NUM_NODES; node++){
 324     results[node] = (result_t)MSG_task_get_data(tasks[node-1]);
 325     MSG_task_destroy(tasks[node-1]);
 326   }
 327 }