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