cleaning up of the manual
[charm.git] / doc / bigsim / emulator.tex
1
2 \section{BigSim Emulator}
3 \label{bgemulator}
4
5 The BigSim emulator environment is designed with the following
6 objectives:
7
8 \begin{enumerate}
9 \item To support a realistic BigSim API on existing parallel machines
10
11 \item To obtain first-order performance estimates of algorithms
12
13 \item To facilitate implementations of alternate programming models for
14       Blue Gene
15 \end{enumerate}
16
17 The machine supported by the emulator consists of three-dimensional grid of
18 1-chip nodes.  The user may specify the size of the machine along each
19 dimension (e.g. 34x34x36).  The chip supports $k$ threads (e.g. 200), each with
20 its own integer unit.  The proximity of the integer unit with individual memory
21 modules within a chip is not currently modeled.
22
23 The API supported by the emulator can be broken down into several
24 components:
25
26 \begin{enumerate}
27 \item Low-level API for chip-to-chip communication
28 \item Mid-level API that supports local micro-tasking with a chip level
29 scheduler with features such as: read-only variables, reductions, broadcasts,
30 distributed tables, get/put operations
31 \item Migratable objects with automatic load balancing support
32 \end{enumerate}
33
34 Of these, the first two have been implemented.  The simple time stamping
35 algorithm, without error correction, has been implemented.  More
36 sophisticated timing algorithms, specifically aimed at error correction,
37 and more sophisticated features (2, 3, and others), as well as libraries
38 of commonly needed parallel operations are part of the proposed work for
39 future.
40
41 The following sections define the appropriate parts of the API, with
42 example programs and instructions for executing them.
43
44 \subsection{BigSim Programming Environment}
45
46 The basic philosophy of the BigSim Emulator is to hide intricate details of the
47 simulated machine from the application developer. Thus, the application
48 developer needs to provide initialization details and handler functions only and
49 gets the result as though running on a real machine.  Communication, Thread
50 creation, Time Stamping, etc are done by the emulator.
51
52 \subsubsection{BigSim API: Level 0}
53
54 \function{void addBgNodeInbuffer(bgMsg *msgPtr, int nodeID)}
55 \desc{
56         low-level primitive invoked by Blue Gene emulator to put the 
57         message to the inbuffer queue of a node.
58
59         msgPtr - pointer to the message to be sent to target node; 
60
61         nodeID - node ID of the target node, it is the serial number of a 
62                  bluegene node in the emulator's physical node.
63 }
64
65 \function{void addBgThreadMessage(bgMsg *msgPtr, int threadID)}
66 \desc{
67         add a message to a thread's affinity queue, these messages can be 
68         only executed by a specific thread indicated by threadID.
69 }
70
71 \function{void addBgNodeMessage(bgMsg *msgPtr)}
72 \desc{
73         add a message to a node's non-affinity queue, these messages can be 
74         executed by any thread in the node.
75 }
76
77 \function{boolean checkReady()}
78 \desc{
79         invoked by communication thread to see if there is any unattended
80         message in inBuffer.
81 }
82
83 \function{bgMsg * getFullBuffer()}
84 \desc{
85         invoked by communication thread to retrieve the unattended message 
86         in inBuffer.
87 }
88
89 \function{CmiHandler msgHandlerFunc(char *msg)}
90 \desc{
91         Handler function type that user can register to handle the message.
92 }
93
94 \function{void sendPacket(int x, int y, int z, int msgSize,bgMsg *msg)}
95 \desc{
96         chip-to-chip communication function. It send a message to Node[x][y][z].
97         
98         bgMsg is the message type with message envelop used internally.
99 }
100
101 \subsubsection{Initialization API: Level 1a}
102
103 All the functions defined in API Level 0 are used internally for the 
104 implementation of bluegene node communication and worker threads.
105
106 From this level, the functions defined are exposed to users to write bluegene
107 programs on the emulator.
108
109 Considering that the emulator machine will emulate several Bluegene nodes on
110 each physical node, the emulator program defines this function 
111 \function{BgEmulatorInit(int argc, char **argv)} to initialize each emulator
112 node. In this function, user program can define the Bluegene machine size,
113 number of communication/worker threads, and check the command line arguments.
114
115 The size of the simulated machine being emulated and the number of thread per
116 node is determined either by the command line arguments or calling following
117 functions:
118
119 \function{void BgSetSize(int sx, int sy, int sz)}
120 \desc{
121         set Blue Gene Machine size;
122 }
123
124 \function{void BgSetNumWorkThread(int num)}
125 \desc{
126         set number of worker threads per node;
127 }
128
129 \function{void BgSetNumCommThread(int num)}
130 \desc{
131         set number of communication threads per node;
132 }
133
134 \function{int BgRegisterHandler(BgHandler h)}
135 \desc{
136         register user message handler functions; 
137 }
138
139 For each simulated node, the execution starts at 
140 \function{BgNodeStart(int argc, char **argv)} called by the emulator,
141 where application handlers can be registered and computation 
142 is triggered by creating a task at required nodes.
143
144 Similar to pthread's thread specific data, each bluegene node has its
145 own node specific data associated with it. To do this, the user needs to define its 
146 own node-specific variables encapsulated in a struct definition and register
147  the pointer to the data with the emulator by following function:
148
149 \function{void BgSetNodeData(char *data)}
150
151 To retrieve the node specific data, call:
152
153 \function{char *BgGetNodeData();}
154
155 After completion of execution, user program invokes a function:
156
157 \function{void BgShutdown()}
158
159 to terminate the emulator.
160
161 \subsubsection{Handler Function API: Level 1a}
162
163 The following functions can be called in user's application program to retrieve
164 the simulated machine information, get thread execution time, and perform the
165 communication.
166
167 \function{void BgGetSize(int *sx, int *sy, int *sz);}
168
169 \function{int BgGetNumWorkThread();}
170
171 \function{int BgGetNumCommThread();}
172
173 \function{int BgGetThreadID();}
174
175 \function{double BgGetTime();}
176
177 \function{void BgSendPacket(int x, int y, int z, int threadID, int handlerID, WorkType type, int numbytes, char* data);}
178 \desc{
179 This sends a trunk of data to Node[x, y, z] and also specifies the
180 handler function to be used for this message i.e. the handlerID;
181 threadID specifies the desired thread to handle the message, ANYTHREAD means
182 no preference.
183
184 To specify the thread category:
185 \begin{description}
186 \item[1:] a small piece of work that can be done by
187 communication thread itself, so NO scheduling overhead.
188 \item[0:] a large piece of work, so communication thread
189 schedules it for a worker thread
190 \end{description}
191 }
192
193
194 \subsection{Writing a BigSim Application}
195
196 \subsubsection{Application Skeleton}
197
198 \begin{alltt}
199 Handler function prototypes;
200 Node specific data type declarations;
201
202 void  BgEmulatorInit(int argc, char **argv)  function
203   Configure bluegene machine parameters including size, number of threads, etc.
204   You also need to register handlers here.
205
206 void *BgNodeStart(int argc, char **argv) function
207   The usual practice in this function is to send an initial message to trigger 
208   the execution.
209   You can also register node specific data in this function.
210
211 Handler Function 1, void handlerName(char *info)
212 Handler Function 2, void handlerName(char *info)
213 ..
214 Handler Function N, void handlerName(char *info)
215
216 \end{alltt}
217
218 \subsubsection{Sample Application 1}
219
220 \begin{verbatim}
221 /* Application: 
222  *   Each node starting at [0,0,0] sends a packet to next node in
223  *   the ring order.
224  *   After node [0,0,0] gets message from last node
225  *   in the ring, the application ends.
226  */
227
228
229 #include "blue.h"
230
231 #define MAXITER 2
232
233 int iter = 0;
234 int passRingHandler;
235
236 void passRing(char *msg);
237
238 void nextxyz(int x, int y, int z, int *nx, int *ny, int *nz)
239 {
240   int numX, numY, numZ;
241
242   BgGetSize(&numX, &numY, &numZ);
243   *nz = z+1; *ny = y; *nx = x;
244   if (*nz == numZ) {
245     *nz = 0; (*ny) ++;
246     if (*ny == numY) {
247       *ny = 0; (*nx) ++;
248       if (*nx == numX) *nx = 0;
249     }
250   }
251 }
252
253 void BgEmulatorInit(int argc, char **argv)
254 {
255   passRingHandler = BgRegisterHandler(passRing);
256 }
257
258 /* user defined functions for bgnode start entry */
259 void BgNodeStart(int argc, char **argv)
260 {
261   int x,y,z;
262   int nx, ny, nz;
263   int data, id;
264
265   BgGetXYZ(&x, &y, &z);
266   nextxyz(x, y, z, &nx, &ny, &nz);
267   id = BgGetThreadID();
268   data = 888;
269   if (x == 0 && y==0 && z==0) {
270     BgSendPacket(nx, ny, nz, -1,passRingHandler, LARGE_WORK, 
271                                 sizeof(int), (char *)&data);
272   }
273 }
274
275 /* user write code */
276 void passRing(char *msg)
277 {
278   int x, y, z;
279   int nx, ny, nz;
280   int id;
281   int data = *(int *)msg;
282
283   BgGetXYZ(&x, &y, &z);
284   nextxyz(x, y, z, &nx, &ny, &nz);
285   if (x==0 && y==0 && z==0) {
286     if (++iter == MAXITER) BgShutdown();
287   }
288   id = BgGetThreadID();
289   BgSendPacket(nx, ny, nz, -1, passRingHandler, LARGE_WORK, 
290                                 sizeof(int), (char *)&data);
291 }
292
293 \end{verbatim}
294
295
296 \subsubsection{Sample Application 2}
297
298 \begin{verbatim}
299
300 /* Application: 
301  *   Find the maximum element.
302  *   Each node computes maximum of it's elements and
303  *   the max values it received from other nodes
304  *   and sends the result to next node in the reduction sequence.
305  * Reduction Sequence: Reduce max data to X-Y Plane
306  *   Reduce max data to Y Axis
307  *   Reduce max data to origin.
308  */
309
310
311 #include <stdlib.h>
312 #include "blue.h"
313
314 #define A_SIZE 4
315
316 #define X_DIM 3
317 #define Y_DIM 3
318 #define Z_DIM 3
319
320 int REDUCE_HANDLER_ID;
321 int COMPUTATION_ID;
322
323 extern "C" void reduceHandler(char *);
324 extern "C" void computeMax(char *);
325
326 class ReductionMsg {
327 public:
328   int max;
329 };
330
331 class ComputeMsg {
332 public:
333   int dummy;
334 };
335
336 void BgEmulatorInit(int argc, char **argv)
337 {
338   if (argc < 2) { 
339     CmiAbort("Usage: <program> <numCommTh> <numWorkTh>\n"); 
340   }
341
342   /* set machine configuration */
343   BgSetSize(X_DIM, Y_DIM, Z_DIM);
344   BgSetNumCommThread(atoi(argv[1]));
345   BgSetNumWorkThread(atoi(argv[2]));
346
347   REDUCE_HANDLER_ID = BgRegisterHandler(reduceHandler);
348   COMPUTATION_ID = BgRegisterHandler(computeMax);
349
350 }
351
352 void BgNodeStart(int argc, char **argv) {
353   int x, y, z;
354   BgGetXYZ(&x, &y, &z);
355
356   ComputeMsg *msg = new ComputeMsg;
357   BgSendLocalPacket(ANYTHREAD, COMPUTATION_ID, LARGE_WORK, 
358                         sizeof(ComputeMsg), (char *)msg);
359 }
360
361 void reduceHandler(char *info) {
362   // assumption: THey are initialized to zero?
363   static int max[X_DIM][Y_DIM][Z_DIM];
364   static int num_msg[X_DIM][Y_DIM][Z_DIM];
365
366   int i,j,k;
367   int external_max;
368
369   BgGetXYZ(&i,&j,&k);
370   external_max = ((ReductionMsg *)info)->max;
371   num_msg[i][j][k]++;
372
373   if ((i == 0) && (j == 0) && (k == 0)) {
374     // master node expects 4 messages:
375     // 1 from itself;
376     // 1 from the i dimension;
377     // 1 from the j dimension; and
378     // 1 from the k dimension
379     if (num_msg[i][j][k] < 4) {
380       // not ready yet, so just find the max
381       if (max[i][j][k] < external_max) {
382         max[i][j][k] = external_max;
383       }
384     } else {
385       // done. Can report max data after making last comparison
386       if (max[i][j][k] < external_max) {
387         max[i][j][k] = external_max;
388       }
389       CmiPrintf("The maximal value is %d \n", max[i][j][k]);
390       BgShutdown();
391       return;
392     }
393   } else if ((i == 0) && (j == 0) && (k != Z_DIM - 1)) {
394     // nodes along the k-axis other than the last one expects 4 messages:
395     // 1 from itself;
396     // 1 from the i dimension;
397     // 1 from the j dimension; and
398     // 1 from the k dimension
399     if (num_msg[i][j][k] < 4) {
400       // not ready yet, so just find the max
401       if (max[i][j][k] < external_max) {
402         max[i][j][k] = external_max;
403       }
404     } else {
405       // done. Forwards max data to node i,j,k-1 after making last comparison
406       if (max[i][j][k] < external_max) {
407         max[i][j][k] = external_max;
408       }
409       ReductionMsg *msg = new ReductionMsg;
410       msg->max = max[i][j][k];
411       BgSendPacket(i,j,k-1,ANYTHREAD,REDUCE_HANDLER_ID,LARGE_WORK, 
412                                 sizeof(ReductionMsg), (char *)msg);
413     }
414   } else if ((i == 0) && (j == 0) && (k == Z_DIM - 1)) {
415     // the last node along the k-axis expects 3 messages:
416     // 1 from itself;
417     // 1 from the i dimension; and
418     // 1 from the j dimension
419     if (num_msg[i][j][k] < 3) {
420       // not ready yet, so just find the max
421       if (max[i][j][k] < external_max) {
422         max[i][j][k] = external_max;
423       }
424     } else {
425       // done. Forwards max data to node i,j,k-1 after making last comparison
426       if (max[i][j][k] < external_max) {
427         max[i][j][k] = external_max;
428       }
429       ReductionMsg *msg = new ReductionMsg;
430       msg->max = max[i][j][k];
431       BgSendPacket(i,j,k-1,ANYTHREAD,REDUCE_HANDLER_ID,LARGE_WORK, 
432                                 sizeof(ReductionMsg), (char *)msg);
433     }
434   } else if ((i == 0) && (j != Y_DIM - 1)) {
435     // for nodes along the j-k plane except for the last and first row of j,
436     // we expect 3 messages:
437     // 1 from itself;
438     // 1 from the i dimension; and
439     // 1 from the j dimension
440     if (num_msg[i][j][k] < 3) {
441       // not ready yet, so just find the max
442       if (max[i][j][k] < external_max) {
443         max[i][j][k] = external_max;
444       }
445     } else {
446       // done. Forwards max data to node i,j-1,k after making last comparison
447       if (max[i][j][k] < external_max) {
448         max[i][j][k] = external_max;
449       }
450       ReductionMsg *msg = new ReductionMsg;
451       msg->max = max[i][j][k];
452       BgSendPacket(i,j-1,k,ANYTHREAD,REDUCE_HANDLER_ID,LARGE_WORK, 
453                                 sizeof(ReductionMsg), (char *)msg);
454     }
455   } else if ((i == 0) && (j == Y_DIM - 1)) {
456     // for nodes along the last row of j on the j-k plane,
457     // we expect 2 messages:
458     // 1 from itself;
459     // 1 from the i dimension;
460     if (num_msg[i][j][k] < 2) {
461       // not ready yet, so just find the max
462       if (max[i][j][k] < external_max) {
463         max[i][j][k] = external_max;
464       }
465     } else {
466       // done. Forwards max data to node i,j-1,k after making last comparison
467       if (max[i][j][k] < external_max) {
468         max[i][j][k] = external_max;
469       }
470       ReductionMsg *msg = new ReductionMsg;
471       msg->max = max[i][j][k];
472       BgSendPacket(i,j-1,k,ANYTHREAD,REDUCE_HANDLER_ID,LARGE_WORK, 
473                                 sizeof(ReductionMsg), (char *)msg);
474     }
475   } else if (i != X_DIM - 1) {
476     // for nodes anywhere the last row of i,
477     // we expect 2 messages:
478     // 1 from itself;
479     // 1 from the i dimension;
480     if (num_msg[i][j][k] < 2) {
481       // not ready yet, so just find the max
482       if (max[i][j][k] < external_max) {
483         max[i][j][k] = external_max;
484       }
485     } else {
486       // done. Forwards max data to node i-1,j,k after making last comparison
487       if (max[i][j][k] < external_max) {
488         max[i][j][k] = external_max;
489       }
490       ReductionMsg *msg = new ReductionMsg;
491       msg->max = max[i][j][k];
492       BgSendPacket(i-1,j,k,ANYTHREAD,REDUCE_HANDLER_ID,LARGE_WORK, 
493                                 sizeof(ReductionMsg), (char *)msg);
494     }
495   } else if (i == X_DIM - 1) {
496     // last row of i, we expect 1 message:
497     // 1 from itself;
498     if (num_msg[i][j][k] < 1) {
499       // not ready yet, so just find the max
500       if (max[i][j][k] < external_max) {
501         max[i][j][k] = external_max;
502       }
503     } else {
504       // done. Forwards max data to node i-1,j,k after making last comparison
505       if (max[i][j][k] < external_max) {
506         max[i][j][k] = external_max;
507       }
508       ReductionMsg *msg = new ReductionMsg;
509       msg->max = max[i][j][k];
510       BgSendPacket(i-1,j,k,-1,REDUCE_HANDLER_ID,LARGE_WORK, 
511                                 sizeof(ReductionMsg), (char *)msg);
512     }
513   }
514 }
515
516 void computeMax(char *info) {
517   int A[A_SIZE][A_SIZE];
518   int i, j;
519   int max = 0;
520
521   int x,y,z; // test variables
522   BgGetXYZ(&x,&y,&z);
523
524   // Initialize
525   for (i=0;i<A_SIZE;i++) {
526     for (j=0;j<A_SIZE;j++) {
527       A[i][j] = i*j;
528     }
529   }
530
531 //  CmiPrintf("Finished Initializing %d %d %d!\n",  x , y , z);
532
533   // Find Max
534   for (i=0;i<A_SIZE;i++) {
535     for (j=0;j<A_SIZE;j++) {
536       if (max < A[i][j]) {
537         max = A[i][j];
538       }
539     }
540   }
541
542   // prepare to reduce
543   ReductionMsg *msg = new ReductionMsg;
544   msg->max = max;
545   BgSendLocalPacket(ANYTHREAD, REDUCE_HANDLER_ID, LARGE_WORK, 
546                                 sizeof(ReductionMsg), (char *)msg);
547
548 //  CmiPrintf("Sent reduce message to myself with max value %d\n", max);
549 }
550
551
552 \end{verbatim}
553