Fixed latex bugs.
[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{BlueGene Emulator was developed by Arun Singla, Neelam Saboo
8 and Joshua Unger under the guidance of Prof. L. V. Kale.}
9
10 \begin{document}
11 \maketitle
12
13 \section{Introduction}
14
15 Blue Gene is a proposed one million processor machine from IBM.
16
17 The Blue Gene emulator environment is designed with the following
18 objectives:
19
20 \begin{enumerate}
21 \item To support a realistic Blue Gene API on existing parallel machines
22
23 \item To obtain first-order performance estimates of algorithms
24
25 \item To facilitate implementations of alternate programming models for
26       Blue Gene
27 \end{enumerate}
28
29 The ``Blue Gene'' machine supported by the emulator consists of
30 three-dimensional grid of 1-chip nodes.  The user may specify the size
31 of the machine along each dimension (e.g. 34x34x36).  The chip supports
32 $k$ threads (e.g. 200), each with its own integer unit.  The proximity of
33 the integer unit with individual memory modules within a chip is not
34 currently modeled.
35
36 The API supported by the emulator can be broken down into several
37 components:
38
39 \begin{enumerate}
40 \item Low-level API for chip-to-chip communication
41 \item Mid-level API that supports local micro-tasking with a chip level
42 scheduler with features such as: read-only variables, reductions, broadcasts,
43 distributed tables, get/put operations
44 \item Migratable objects with automatic load balancing support
45 \end{enumerate}
46
47 Of these, the first two have been implemented.  The simple time stamping
48 algorithm, without error correction, has been implemented.  More
49 sophisticated timing algorithms, specifically aimed at error correction,
50 and more sophisticated features (2, 3, and others), as well as libraries
51 of commonly needed parallel operations are part of the proposed work for
52 future.
53
54 The following sections define the appropriate parts of the API, with
55 example programs and instructions for executing them.
56
57 \section{Blue Gene Programming Environment}
58
59 The basic philosophy of the Blue Gene Emulator is to hide intricate details
60 of Blue Gene machine from
61 application developer.Thus, the application developer needs to provide
62 intialization details and handler
63 functions only and gets the result as though running on a real machine.
64 Communication, Thread creation,
65 Time Stamping, etc are done by the emulator.
66
67 \subsection{Blue Gene API: Level 0}
68
69 \function{void putMessage(PacketMsg *)}
70 \desc{
71         chip-to-chip communication function, invoked by Blue Gene
72         environment when a node calls sendPacket
73         to put the message in the inBuffer of target node.
74 }
75
76 \function{boolean checkReady()}
77 \desc{
78         invoked by communication thread to see if there is any unattended
79         message in inBuffer.
80 }
81
82 \function{PacketMsg *getMessage()}
83 \desc{
84         invoked by communication thread to retrieve the unattended message
85         in inBuffer.
86 }
87
88 \subsection{Initialization API: Level 1a}
89
90 Execution starts at BgInit(Main *), where Blue Gene machine parameters are
91 initialized.
92
93 \function{void CreateBlueGene(CreateBgNodeMsg *msg)}
94 \desc{
95 Specifies the machines configuration in CreateBgNodeMsg.
96 }
97
98 Data required for initialization of Node is specified in a system
99 defined type CreateBgNodeMsg.
100
101 \begin{alltt}
102         class CreateBgNodeMsg
103         \{
104                 public:
105                   int numCTh ;
106                   int numWTh ;
107                   int numBgX ;
108                   int numBgY ;
109                   int numBgZ ;
110         \} ;
111 \end{alltt}
112
113 \function{int  getNumArgs()}
114 \desc{
115 Return the number of command line arguments
116 }
117
118 \function{const char** getArgs()}
119 \desc{
120 Return command line arguments
121 }
122
123 \function{typedef void (*BgHandler)(void*)}
124 \desc{
125 This is type defined in BlueGene.h. It represents a handler function
126 that returns nothing and takes a (void *)
127 }
128
129 The Runtime system calls BgNodeInit(BgNode *) for each node, where
130 application handlers are registered and
131 computation is triggered by creating a task at required nodes. The Node
132 Variables are encapsulated in a struct
133 definition and a pointer to this (node private variable) is returned.
134
135 \function{void  registerHandler(int handlerID, BgHandler h)}
136 \desc{
137 Register a Handler with each node
138 }
139
140 \function{void addMessage(PacketMsg *msgPtr, int handlerID, int threadCategory)}
141 \desc{
142 Create a micro-task, specifiy the handler function to be
143 used for this message i.e. handlerID, and
144 specify the thread category:
145 \begin{description}
146 \item[1:] a small piece of work that can be done by
147 communication thread itself, so NO scheduling overhead.
148 \item[0:] a large piece of work, so communication thread
149 schedules it for a worker thread
150 \end{description}
151 }
152
153 InterNode communication messages are to be inherited from PacketMsg
154
155 \begin{alltt}
156         class PacketMsg
157         \{
158             public:
159                   int srcX ;
160                   int srcY ;
161                   int srcZ ;
162                   int destX ;
163                   int destY ;
164                   int destZ ;
165                   int numBytes ;
166                   double sendTime ;
167                   double recvTime ;
168         \} ;
169 \end{alltt}
170
171 After completion of execution, Blue Gene environment invokes a user defined
172 function BgFinish().
173
174 \subsection{Handler Function API: Level 1a}
175
176 \function{void sendPacket(int x, int y, int z, PacketMsg *msgPtr, int handlerID, int threadCategory)}
177 \desc{
178 Sends a PacketMsg pointer to Node[x,y,z] and also specifies the
179 handler function to be used for this message ie. handlerID,
180 specify the thread category:
181 \begin{description}
182 \item[1:] a small piece of work that can be done by
183 communication thread itself, so NO scheduling overhead.
184 \item[0:] a large piece of work, so communication thread
185 schedules it for a worker thread
186 \end{description}
187 }
188
189 \function{void getXYZ(int\& x, int\& y, int\& z)}
190 \desc{
191 Gets which Blue Gene node do the invoking thread belongs to
192 }
193
194 \function{double getTime()}
195 \desc{
196 Returns current time of thread in microseconds (execution time since
197 the application started)
198 }
199
200
201 \section{Writing a Blue Gene Application}
202
203 \subsection{Application Skeleton}
204
205 \begin{alltt}
206 Handler declarations
207 Application specific messages, inherited from PacketMsg
208 Struct definitions encapsulating Node (specific) variables
209
210 void  BgInit(Main *)  function
211   Make a Blue Gene node creation message, CreateBgNodeMsg
212   Initialize number of Communication Threads and 
213     number of Worker Threads per node
214   Initialize number of Blue Gene nodes in X, Y, and Z dimension.
215   Initialize the emulator by calling CreateBlueGene(CreateBgNodeMsg)
216
217 void *BgNodeInit(BgNode *) function
218   Register handlers, registerHandler(handlerID, handler)
219   Send initialization message packets to node, 
220     addMessage(messagePointer, handlerID)
221   Declare Node Variables (struct) and return a pointer to it.
222
223 void  BgFinish()  function
224   detects Quiescence
225
226 Handler Function 1, void handlerName(ThreadInfo *info)
227 Hanlder Function 2, void handlerName(ThreadInfo *info)
228 ..
229 Handler Function N, void handlerName(ThreadInfo *info)
230
231 \end{alltt}
232
233 \subsection{Sample Application 1}
234
235 \begin{alltt}
236 /* Application: 
237  *   Each node starting at [0,0,0] sends a packet to next node in
238  *   the ring order.
239  *   After node [0,0,0] gets message from last node
240  *   in the ring, the application ends.
241  */
242
243 #include "BlueGene.h"
244 #define  computeID 1
245
246 extern "C" void compute(ThreadInfo *) ;
247
248 class MyMsg : public PacketMsg
249 \{
250 public:
251   int dummy ;
252 \} ;
253
254
255 void BgInit(Main *main)
256 \{
257   int num_comm = 1, num_work = 2;       // default number of communication
258                                         // and worker threads per node
259   int num_args = main->getNumArgs();
260   if (num_args < 4) \{ 
261     // Abort application: insufficient number of arguments
262     CkAbort("Usage: ring <x> <y> <z> [<numCommTh> <numWorkTh>]\verb+\n+"); 
263   \}
264
265   if (num_args > 5) \{ num_work = atoi(main->getArgs()[5]); \}
266   if (num_args > 4) \{ num_comm = atoi(main->getArgs()[4]); \}
267
268   CreateBgNodeMsg *bgNodeMsg = new CreateBgNodeMsg;
269   bgNodeMsg->numBgX = atoi(main->getArgs()[1]);
270   bgNodeMsg->numBgY = atoi(main->getArgs()[2]);
271   bgNodeMsg->numBgZ = atoi(main->getArgs()[3]);
272   bgNodeMsg->numCTh = num_comm;
273   bgNodeMsg->numWTh = num_work;
274
275   main->CreateBlueGene(bgNodeMsg);
276   return;
277 \}
278
279 void* BgNodeInit(BgNode *bgNode)
280 \{
281   bgNode->registerHandler(computeID, compute) ;
282
283   // trigger computation at Node[0,0,0]
284   if(bgNode->thisIndex.x==0 \&\& bgNode->thisIndex.y==0 \&\& bgNode->thisIndex.z==0)
285   \{
286    MyMsg *msg = new MyMsg ;
287    msg->dummy = 0 ;
288    bgNode->addMessage(msg, computeID, 0) ;
289   \}
290   return NULL;    // No node variables for this example
291 \}
292
293 void BgFinish() \{\}
294
295 void compute(ThreadInfo *info)
296 \{
297   int i, j, k ;
298   int ni, nj, nk ;
299
300   info->bgNode->getXYZ(i,j,k) ;
301
302   if(i==info->bgNode->numBgX-1 \&\& j==info->bgNode->numBgY-1 \&\& 
303      k==info->bgNode->numBgZ-1)
304   \{
305            ckout << "Exiting" << endl ;
306            info->bgNode->finish() ;
307            return ;
308   \}
309
310   nk = k + 1 ;
311   nj = j ;
312   ni = i ;
313   if( nk==info->bgNode->numBgZ )
314   \{
315           nk = 0 ;
316          nj = j+1 ;
317          if ( nj==info->bgNode->numBgY )
318          \{
319                 nj = 0 ;
320                 ni = i+1 ;
321                 if ( ni==info->bgNode->numBgX ) \{
322                     ni = 0 ;
323                 \}
324          \}
325   \}
326   MyMsg *msg = new MyMsg ;
327   msg->dummy = i+j+k ;
328   info->bgNode->sendPacket(ni, nj, nk, msg, computeID, 0) ;
329 \}
330 \end{alltt}
331
332
333 \subsection{Sample Application 2}
334
335 \begin{alltt}
336
337 /* Application: 
338  *   Find the maximum element.
339  *   Each node computes maximum of it's elements and
340  *   the max values it received from other nodes
341  *   and sends the result to next node in the reduction sequence.
342  * Reduction Sequence: Reduce max data to X-Y Plane
343  *   Reduce max data to Y Axis
344  *   Reduce max data to origin.
345  */
346
347 #include "BlueGene.h"
348
349 #define A_SIZE 4
350
351 #define reduceID                    1
352 #define computeMaxID        2
353 #define contributeID             3
354
355 //handler declarations
356 void reduce(ThreadInfo *) ;
357 void computeMax(ThreadInfo *) ;
358 void contribute(ThreadInfo *) ;
359
360 //Application specifice messages inherited from PacketMsg
361 class contributeMsg: public PacketMsg
362 \{
363 public:
364   int max ;
365 \} ;
366
367 class computeMaxMsg: public PacketMsg
368 \{\} ;
369
370 class reduceMsg: public PacketMsg
371 \{\} ;
372
373 //Node variables encapsulated in a struct definition
374 typedef struct userDataStruct
375 \{
376   int data[A_SIZE] ;
377   int count ;
378 \} userData ;
379
380 void BgInit(Main *main)
381 \{
382   int num_comm = 1, num_work = 2;       // default number of communication
383 and worker threads
384   int num_args = main->getNumArgs();
385   if (num_args < 4) \{ 
386     CkAbort("Usage: maxReduceNV <x> <y> <z> [<numCommTh> <numWorkTh>]\verb+\n+"); 
387   \}
388   if (num_args > 5) \{ num_work = atoi(main->getArgs()[5]); \}
389   if (num_args > 4) \{ num_comm = atoi(main->getArgs()[4]); \}
390
391   CreateBgNodeMsg *bgNodeMsg = new CreateBgNodeMsg;
392   bgNodeMsg->numBgX = atoi(main->getArgs()[1]);
393   bgNodeMsg->numBgY = atoi(main->getArgs()[2]);
394   bgNodeMsg->numBgZ = atoi(main->getArgs()[3]);
395   bgNodeMsg->numCTh = num_comm;
396   bgNodeMsg->numWTh = num_work;
397
398   main->CreateBlueGene(bgNodeMsg);
399   return;
400 \}
401
402 void* BgNodeInit(BgNode *bgNode)
403 \{
404   //register handlers
405   bgNode->registerHandler(reduceID, reduce) ;
406   bgNode->registerHandler(computeMaxID, computeMax) ;
407   bgNode->registerHandler(contributeID, contribute) ;
408
409   //triger computer at each node
410   computeMaxMsg *msg = new computeMaxMsg;
411   bgNode->addMessage(msg, computeMaxID, 0);
412
413   //declare node variable and return a pointer
414   userData *ud = new userData ;
415   ud->count = 0 ;
416   for(int i=0; i<A_SIZE; i++)
417    ud->data[i] = 0 ;
418
419   return (void*)ud ;
420 \}
421
422 void BgFinish()
423 \{\}
424
425 void computeMax(ThreadInfo *info)
426 \{
427   int A[A_SIZE][A_SIZE];
428   int i, j;
429   int max = 0;
430
431   int x,y,z;
432   info->bgNode->getXYZ(x,y,z);
433
434   // Initialize data in each node
435   for (i=0;i<A_SIZE;i++)
436     for (j=0;j<A_SIZE;j++)
437       A[i][j] = info->bgNode->numBgX * info->bgNode->numBgY * 
438                 info->bgNode->numBgZ - x*y*z - i*j ;
439
440   // Find Max
441   for (i=0;i<A_SIZE;i++)
442     for (j=0;j<A_SIZE;j++)
443       if (max < A[i][j])
444       \{
445              max = A[i][j];
446       \}
447
448   // contribute the results for reduction
449   contributeMsg *msg = new contributeMsg;
450   msg->max = max;
451   info->bgNode->addMessage(msg,contributeID,1);
452
453   ckout << "computeMax in " << x << ", " << y << ", " << z << endl;
454   ckout << "contributed max value " << max << endl;
455 \}
456
457 void contribute(ThreadInfo *info)
458 \{
459   int x,y,z;
460   info->bgNode->getXYZ(x,y,z);
461
462   // Accessing node variables : get number of data values received at this node
463   int count = ((userData*)(info->bgNode->nvData))->count++ ;
464   // Store new contribution to node variables
465   ((userData*)(info->bgNode->nvData))->data[count++] =
466 ((contributeMsg*)(info->msg))->max ;
467
468  // Compute the required Count of data values at each node to start reduction 
469  // at that node, depends on reduction sequence
470   int reqCount ;
471
472   if(z==info->bgNode->numBgZ-1)
473   \{
474          reqCount = 1 ;
475   \}
476   else if(z>0 || (z==0 \&\& x==info->bgNode->numBgX-1))
477   \{
478          reqCount = 2 ;
479   \}
480   else if(x>0 || (x==0 \&\& y==info->bgNode->numBgY-1))
481   \{
482          reqCount = 3 ;
483   \}
484   else
485          reqCount = 4 ;
486
487   if(count==reqCount)     //if data for reduction is ready
488   \{
489        reduceMsg *msg = new reduceMsg ;
490        info->bgNode->addMessage(msg, reduceID, 0) ;
491        ckout << "contribute in Node " << x << ", " << y << ", " << z << endl;
492        ckout << "Values collected " << count << ", calling reduction " << endl;
493        return ;
494   \}
495
496   ckout << "contribute in Node " << x << ", " << y << ", " << z << endl ;
497   ckout << "Values collected " << count << ", reqCount " << reqCount << endl;
498 \}
499
500 void reduce(ThreadInfo *info)
501 \{
502   int x,y,z;
503   info->bgNode->getXYZ(x,y,z);
504   ckout << "reduce in " << x << ", " << y << ", " << z << endl;
505
506   //do reduction
507   int max = 0 ;
508   int count = ((userData*)(info->bgNode->nvData))->count ;
509   for(int i=0; i<count; i++)
510   \{
511            if(max<((userData*)(info->bgNode->nvData))->data[i])
512            max = ((userData*)(info->bgNode->nvData))->data[i] ;
513   \}
514
515   if(x==0 \&\& y==0 \&\& z==0)
516   \{
517          ckout << "Exiting: max value is " << max << endl ;
518          info->bgNode->finish() ;
519          return ;
520   \}
521
522   //send max to destination, depends on reduction sequence
523   if(z>0)
524    z-- ;
525   else if(x>0)
526    x-- ;
527   else
528    y-- ;
529
530   contributeMsg *msg = new contributeMsg;
531   msg->max = max;
532   info->bgNode->sendPacket(x,y,z,msg,contributeID,1);
533
534   ckout << "sending max value " << max << " to " << x << ", " << y << ", " << z << endl ;
535 \}
536 \end{alltt}
537
538 \section{Compiling and Running}
539
540 Compile Blue Gene emulator programs using {\tt charmc} as one would
541 in the case of normal \charmpp{} programs. In order to link the
542 Blue Gene programs, use \texttt{-language bluegene} as an argument
543 to the {\tt charmc} linker.
544
545 \input{index}
546 \end{document}