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