fixed a lot of minor errors
[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 the Blue Gene machine from the
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 programs on the emulator.
111
112 Considering that the emulator machine will emulate several Bluegene nodes on
113 each physical node, the emulator program defines 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         register 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 the emulator,
144 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 has its
148 own node specific data associated with it. To do this, the user needs to define its 
149 own node-specific variables encapsulated in a struct definition and register
150  the pointer to the data with 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 retrieve
167 the Blue Gene 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 This sends a trunk of data to Node[x, y, z] and also specifies the
183 handler function to be used for this message i.e. the handlerID;
184 threadID specifes the desired thread to handle the message, ANYTHREAD means
185 no preference.
186
187 To specify the thread category:
188 \begin{description}
189 \item[1:] a small piece of work that can be done by
190 communication thread itself, so NO scheduling overhead.
191 \item[0:] a large piece of work, so communication thread
192 schedules it for a worker thread
193 \end{description}
194 }
195
196
197 \subsection{Writing a Blue Gene Application}
198
199 \subsubsection{Application Skeleton}
200
201 \begin{alltt}
202 Handler function prototypes;
203 Node specific data type declarations;
204
205 void  BgEmulatorInit(int argc, char **argv)  function
206   Configure bluegene machine parameters including size, number of threads, etc.
207   You also neet to register handlers here.
208
209 void *BgNodeStart(int argc, char **argv) function
210   The usual practice in this function is to send an intial message to trigger 
211   the execution.
212   You can also register node specific data in this function.
213
214 Handler Function 1, void handlerName(char *info)
215 Hanlder Function 2, void handlerName(char *info)
216 ..
217 Handler Function N, void handlerName(char *info)
218
219 \end{alltt}
220
221 \subsubsection{Sample Application 1}
222
223 \begin{verbatim}
224 /* Application: 
225  *   Each node starting at [0,0,0] sends a packet to next node in
226  *   the ring order.
227  *   After node [0,0,0] gets message from last node
228  *   in the ring, the application ends.
229  */
230
231
232 #include "blue.h"
233
234 #define MAXITER 2
235
236 int iter = 0;
237 int passRingHandler;
238
239 void passRing(char *msg);
240
241 void nextxyz(int x, int y, int z, int *nx, int *ny, int *nz)
242 {
243   int numX, numY, numZ;
244
245   BgGetSize(&numX, &numY, &numZ);
246   *nz = z+1; *ny = y; *nx = x;
247   if (*nz == numZ) {
248     *nz = 0; (*ny) ++;
249     if (*ny == numY) {
250       *ny = 0; (*nx) ++;
251       if (*nx == numX) *nx = 0;
252     }
253   }
254 }
255
256 void BgEmulatorInit(int argc, char **argv)
257 {
258   passRingHandler = BgRegisterHandler(passRing);
259 }
260
261 /* user defined functions for bgnode start entry */
262 void BgNodeStart(int argc, char **argv)
263 {
264   int x,y,z;
265   int nx, ny, nz;
266   int data, id;
267
268   BgGetXYZ(&x, &y, &z);
269   nextxyz(x, y, z, &nx, &ny, &nz);
270   id = BgGetThreadID();
271   data = 888;
272   if (x == 0 && y==0 && z==0) {
273     BgSendPacket(nx, ny, nz, -1,passRingHandler, LARGE_WORK, 
274                                 sizeof(int), (char *)&data);
275   }
276 }
277
278 /* user write code */
279 void passRing(char *msg)
280 {
281   int x, y, z;
282   int nx, ny, nz;
283   int id;
284   int data = *(int *)msg;
285
286   BgGetXYZ(&x, &y, &z);
287   nextxyz(x, y, z, &nx, &ny, &nz);
288   if (x==0 && y==0 && z==0) {
289     if (++iter == MAXITER) BgShutdown();
290   }
291   id = BgGetThreadID();
292   BgSendPacket(nx, ny, nz, -1, passRingHandler, LARGE_WORK, 
293                                 sizeof(int), (char *)&data);
294 }
295
296 \end{verbatim}
297
298
299 \subsubsection{Sample Application 2}
300
301 \begin{verbatim}
302
303 /* Application: 
304  *   Find the maximum element.
305  *   Each node computes maximum of it's elements and
306  *   the max values it received from other nodes
307  *   and sends the result to next node in the reduction sequence.
308  * Reduction Sequence: Reduce max data to X-Y Plane
309  *   Reduce max data to Y Axis
310  *   Reduce max data to origin.
311  */
312
313
314 #include <stdlib.h>
315 #include "blue.h"
316
317 #define A_SIZE 4
318
319 #define X_DIM 3
320 #define Y_DIM 3
321 #define Z_DIM 3
322
323 int REDUCE_HANDLER_ID;
324 int COMPUTATION_ID;
325
326 extern "C" void reduceHandler(char *);
327 extern "C" void computeMax(char *);
328
329 class ReductionMsg {
330 public:
331   int max;
332 };
333
334 class ComputeMsg {
335 public:
336   int dummy;
337 };
338
339 void BgEmulatorInit(int argc, char **argv)
340 {
341   if (argc < 2) { 
342     CmiAbort("Usage: <program> <numCommTh> <numWorkTh>\n"); 
343   }
344
345   /* set machine configuration */
346   BgSetSize(X_DIM, Y_DIM, Z_DIM);
347   BgSetNumCommThread(atoi(argv[1]));
348   BgSetNumWorkThread(atoi(argv[2]));
349
350   REDUCE_HANDLER_ID = BgRegisterHandler(reduceHandler);
351   COMPUTATION_ID = BgRegisterHandler(computeMax);
352
353 }
354
355 void BgNodeStart(int argc, char **argv) {
356   int x, y, z;
357   BgGetXYZ(&x, &y, &z);
358
359   ComputeMsg *msg = new ComputeMsg;
360   BgSendLocalPacket(ANYTHREAD, COMPUTATION_ID, LARGE_WORK, 
361                         sizeof(ComputeMsg), (char *)msg);
362 }
363
364 void reduceHandler(char *info) {
365   // assumption: THey are initialized to zero?
366   static int max[X_DIM][Y_DIM][Z_DIM];
367   static int num_msg[X_DIM][Y_DIM][Z_DIM];
368
369   int i,j,k;
370   int external_max;
371
372   BgGetXYZ(&i,&j,&k);
373   external_max = ((ReductionMsg *)info)->max;
374   num_msg[i][j][k]++;
375
376   if ((i == 0) && (j == 0) && (k == 0)) {
377     // master node expects 4 messages:
378     // 1 from itself;
379     // 1 from the i dimension;
380     // 1 from the j dimension; and
381     // 1 from the k dimension
382     if (num_msg[i][j][k] < 4) {
383       // not ready yet, so just find the max
384       if (max[i][j][k] < external_max) {
385         max[i][j][k] = external_max;
386       }
387     } else {
388       // done. Can report max data after making last comparison
389       if (max[i][j][k] < external_max) {
390         max[i][j][k] = external_max;
391       }
392       CmiPrintf("The maximal value is %d \n", max[i][j][k]);
393       BgShutdown();
394       return;
395     }
396   } else if ((i == 0) && (j == 0) && (k != Z_DIM - 1)) {
397     // nodes along the k-axis other than the last one expects 4 messages:
398     // 1 from itself;
399     // 1 from the i dimension;
400     // 1 from the j dimension; and
401     // 1 from the k dimension
402     if (num_msg[i][j][k] < 4) {
403       // not ready yet, so just find the max
404       if (max[i][j][k] < external_max) {
405         max[i][j][k] = external_max;
406       }
407     } else {
408       // done. Forwards max data to node i,j,k-1 after making last comparison
409       if (max[i][j][k] < external_max) {
410         max[i][j][k] = external_max;
411       }
412       ReductionMsg *msg = new ReductionMsg;
413       msg->max = max[i][j][k];
414       BgSendPacket(i,j,k-1,ANYTHREAD,REDUCE_HANDLER_ID,LARGE_WORK, 
415                                 sizeof(ReductionMsg), (char *)msg);
416     }
417   } else if ((i == 0) && (j == 0) && (k == Z_DIM - 1)) {
418     // the last node along the k-axis expects 3 messages:
419     // 1 from itself;
420     // 1 from the i dimension; and
421     // 1 from the j dimension
422     if (num_msg[i][j][k] < 3) {
423       // not ready yet, so just find the max
424       if (max[i][j][k] < external_max) {
425         max[i][j][k] = external_max;
426       }
427     } else {
428       // done. Forwards max data to node i,j,k-1 after making last comparison
429       if (max[i][j][k] < external_max) {
430         max[i][j][k] = external_max;
431       }
432       ReductionMsg *msg = new ReductionMsg;
433       msg->max = max[i][j][k];
434       BgSendPacket(i,j,k-1,ANYTHREAD,REDUCE_HANDLER_ID,LARGE_WORK, 
435                                 sizeof(ReductionMsg), (char *)msg);
436     }
437   } else if ((i == 0) && (j != Y_DIM - 1)) {
438     // for nodes along the j-k plane except for the last and first row of j,
439     // we expect 3 messages:
440     // 1 from itself;
441     // 1 from the i dimension; and
442     // 1 from the j dimension
443     if (num_msg[i][j][k] < 3) {
444       // not ready yet, so just find the max
445       if (max[i][j][k] < external_max) {
446         max[i][j][k] = external_max;
447       }
448     } else {
449       // done. Forwards max data to node i,j-1,k after making last comparison
450       if (max[i][j][k] < external_max) {
451         max[i][j][k] = external_max;
452       }
453       ReductionMsg *msg = new ReductionMsg;
454       msg->max = max[i][j][k];
455       BgSendPacket(i,j-1,k,ANYTHREAD,REDUCE_HANDLER_ID,LARGE_WORK, 
456                                 sizeof(ReductionMsg), (char *)msg);
457     }
458   } else if ((i == 0) && (j == Y_DIM - 1)) {
459     // for nodes along the last row of j on the j-k plane,
460     // we expect 2 messages:
461     // 1 from itself;
462     // 1 from the i dimension;
463     if (num_msg[i][j][k] < 2) {
464       // not ready yet, so just find the max
465       if (max[i][j][k] < external_max) {
466         max[i][j][k] = external_max;
467       }
468     } else {
469       // done. Forwards max data to node i,j-1,k after making last comparison
470       if (max[i][j][k] < external_max) {
471         max[i][j][k] = external_max;
472       }
473       ReductionMsg *msg = new ReductionMsg;
474       msg->max = max[i][j][k];
475       BgSendPacket(i,j-1,k,ANYTHREAD,REDUCE_HANDLER_ID,LARGE_WORK, 
476                                 sizeof(ReductionMsg), (char *)msg);
477     }
478   } else if (i != X_DIM - 1) {
479     // for nodes anywhere the last row of i,
480     // we expect 2 messages:
481     // 1 from itself;
482     // 1 from the i dimension;
483     if (num_msg[i][j][k] < 2) {
484       // not ready yet, so just find the max
485       if (max[i][j][k] < external_max) {
486         max[i][j][k] = external_max;
487       }
488     } else {
489       // done. Forwards max data to node i-1,j,k after making last comparison
490       if (max[i][j][k] < external_max) {
491         max[i][j][k] = external_max;
492       }
493       ReductionMsg *msg = new ReductionMsg;
494       msg->max = max[i][j][k];
495       BgSendPacket(i-1,j,k,ANYTHREAD,REDUCE_HANDLER_ID,LARGE_WORK, 
496                                 sizeof(ReductionMsg), (char *)msg);
497     }
498   } else if (i == X_DIM - 1) {
499     // last row of i, we expect 1 message:
500     // 1 from itself;
501     if (num_msg[i][j][k] < 1) {
502       // not ready yet, so just find the max
503       if (max[i][j][k] < external_max) {
504         max[i][j][k] = external_max;
505       }
506     } else {
507       // done. Forwards max data to node i-1,j,k after making last comparison
508       if (max[i][j][k] < external_max) {
509         max[i][j][k] = external_max;
510       }
511       ReductionMsg *msg = new ReductionMsg;
512       msg->max = max[i][j][k];
513       BgSendPacket(i-1,j,k,-1,REDUCE_HANDLER_ID,LARGE_WORK, 
514                                 sizeof(ReductionMsg), (char *)msg);
515     }
516   }
517 }
518
519 void computeMax(char *info) {
520   int A[A_SIZE][A_SIZE];
521   int i, j;
522   int max = 0;
523
524   int x,y,z; // test variables
525   BgGetXYZ(&x,&y,&z);
526
527   // Initialize
528   for (i=0;i<A_SIZE;i++) {
529     for (j=0;j<A_SIZE;j++) {
530       A[i][j] = i*j;
531     }
532   }
533
534 //  CmiPrintf("Finished Initializing %d %d %d!\n",  x , y , z);
535
536   // Find Max
537   for (i=0;i<A_SIZE;i++) {
538     for (j=0;j<A_SIZE;j++) {
539       if (max < A[i][j]) {
540         max = A[i][j];
541       }
542     }
543   }
544
545   // prepare to reduce
546   ReductionMsg *msg = new ReductionMsg;
547   msg->max = max;
548   BgSendLocalPacket(ANYTHREAD, REDUCE_HANDLER_ID, LARGE_WORK, 
549                                 sizeof(ReductionMsg), (char *)msg);
550
551 //  CmiPrintf("Sent reduce message to myself with max value %d\n", max);
552 }
553
554
555 \end{verbatim}
556