7726067a8a3996a9dc6a29da1e1ea5a661faed7c
[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>]\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
331
332 \subsection{Sample Application 2}
333
334 /* Application: 
335  *   Find the maximum element.
336  *   Each node computes maximum of it's elements and
337  *   the max values it received from other nodes
338  *   and sends the result to next node in the reduction sequence.
339  * Reduction Sequence: Reduce max data to X-Y Plane
340  *   Reduce max data to Y Axis
341  *   Reduce max data to origin.
342  */
343
344 #include "BlueGene.h"
345
346 #define A_SIZE 4
347
348 #define reduceID                    1
349 #define computeMaxID        2
350 #define contributeID             3
351
352 //handler declarations
353 void reduce(ThreadInfo *) ;
354 void computeMax(ThreadInfo *) ;
355 void contribute(ThreadInfo *) ;
356
357 //Application specifice messages inherited from PacketMsg
358 class contributeMsg: public PacketMsg
359 \{
360 public:
361   int max ;
362 \} ;
363
364 class computeMaxMsg: public PacketMsg
365 \{\} ;
366
367 class reduceMsg: public PacketMsg
368 \{\} ;
369
370 //Node variables encapsulated in a struct definition
371 typedef struct userDataStruct
372 \{
373   int data[A_SIZE] ;
374   int count ;
375 \} userData ;
376
377 void BgInit(Main *main)
378 \{
379   int num_comm = 1, num_work = 2;       // default number of communication
380 and worker threads
381   int num_args = main->getNumArgs();
382   if (num_args < 4) \{ 
383     CkAbort("Usage: maxReduceNV <x> <y> <z> [<numCommTh> <numWorkTh>]\n"); 
384   \}
385   if (num_args > 5) \{ num_work = atoi(main->getArgs()[5]); \}
386   if (num_args > 4) \{ num_comm = atoi(main->getArgs()[4]); \}
387
388   CreateBgNodeMsg *bgNodeMsg = new CreateBgNodeMsg;
389   bgNodeMsg->numBgX = atoi(main->getArgs()[1]);
390   bgNodeMsg->numBgY = atoi(main->getArgs()[2]);
391   bgNodeMsg->numBgZ = atoi(main->getArgs()[3]);
392   bgNodeMsg->numCTh = num_comm;
393   bgNodeMsg->numWTh = num_work;
394
395   main->CreateBlueGene(bgNodeMsg);
396   return;
397 \}
398
399 void* BgNodeInit(BgNode *bgNode)
400 \{
401   //register handlers
402   bgNode->registerHandler(reduceID, reduce) ;
403   bgNode->registerHandler(computeMaxID, computeMax) ;
404   bgNode->registerHandler(contributeID, contribute) ;
405
406   //triger computer at each node
407   computeMaxMsg *msg = new computeMaxMsg;
408   bgNode->addMessage(msg, computeMaxID, 0);
409
410   //declare node variable and return a pointer
411   userData *ud = new userData ;
412   ud->count = 0 ;
413   for(int i=0; i<A_SIZE; i++)
414    ud->data[i] = 0 ;
415
416   return (void*)ud ;
417 \}
418
419 void BgFinish()
420 \{\}
421
422 void computeMax(ThreadInfo *info)
423 \{
424   int A[A_SIZE][A_SIZE];
425   int i, j;
426   int max = 0;
427
428   int x,y,z;
429   info->bgNode->getXYZ(x,y,z);
430
431   // Initialize data in each node
432   for (i=0;i<A_SIZE;i++)
433     for (j=0;j<A_SIZE;j++)
434       A[i][j] = info->bgNode->numBgX * info->bgNode->numBgY * 
435                 info->bgNode->numBgZ - x*y*z - i*j ;
436
437   // Find Max
438   for (i=0;i<A_SIZE;i++)
439     for (j=0;j<A_SIZE;j++)
440       if (max < A[i][j])
441       \{
442              max = A[i][j];
443       \}
444
445   // contribute the results for reduction
446   contributeMsg *msg = new contributeMsg;
447   msg->max = max;
448   info->bgNode->addMessage(msg,contributeID,1);
449
450   ckout << "computeMax in " << x << ", " << y << ", " << z << endl;
451   ckout << "contributed max value " << max << endl;
452 \}
453
454 void contribute(ThreadInfo *info)
455 \{
456   int x,y,z;
457   info->bgNode->getXYZ(x,y,z);
458
459   // Accessing node variables : get number of data values received at this node
460   int count = ((userData*)(info->bgNode->nvData))->count++ ;
461   // Store new contribution to node variables
462   ((userData*)(info->bgNode->nvData))->data[count++] =
463 ((contributeMsg*)(info->msg))->max ;
464
465  // Compute the required Count of data values at each node to start reduction 
466  // at that node, depends on reduction sequence
467   int reqCount ;
468
469   if(z==info->bgNode->numBgZ-1)
470   \{
471          reqCount = 1 ;
472   \}
473   else if(z>0 || (z==0 && x==info->bgNode->numBgX-1))
474   \{
475          reqCount = 2 ;
476   \}
477   else if(x>0 || (x==0 && y==info->bgNode->numBgY-1))
478   \{
479          reqCount = 3 ;
480   \}
481   else
482          reqCount = 4 ;
483
484   if(count==reqCount)     //if data for reduction is ready
485   \{
486        reduceMsg *msg = new reduceMsg ;
487        info->bgNode->addMessage(msg, reduceID, 0) ;
488        ckout << "contribute in Node " << x << ", " << y << ", " << z << endl;
489        ckout << "Values collected " << count << ", calling reduction " << endl;
490        return ;
491   \}
492
493   ckout << "contribute in Node " << x << ", " << y << ", " << z << endl ;
494   ckout << "Values collected " << count << ", reqCount " << reqCount << endl;
495 \}
496
497 void reduce(ThreadInfo *info)
498 \{
499   int x,y,z;
500   info->bgNode->getXYZ(x,y,z);
501   ckout << "reduce in " << x << ", " << y << ", " << z << endl;
502
503   //do reduction
504   int max = 0 ;
505   int count = ((userData*)(info->bgNode->nvData))->count ;
506   for(int i=0; i<count; i++)
507   \{
508            if(max<((userData*)(info->bgNode->nvData))->data[i])
509            max = ((userData*)(info->bgNode->nvData))->data[i] ;
510   \}
511
512   if(x==0 && y==0 && z==0)
513   \{
514          ckout << "Exiting: max value is " << max << endl ;
515          info->bgNode->finish() ;
516          return ;
517   \}
518
519   //send max to destination, depends on reduction sequence
520   if(z>0)
521    z-- ;
522   else if(x>0)
523    x-- ;
524   else
525    y-- ;
526
527   contributeMsg *msg = new contributeMsg;
528   msg->max = max;
529   info->bgNode->sendPacket(x,y,z,msg,contributeID,1);
530
531   ckout << "sending max value " << max << " to " << x << ", " << y << ", " << z << endl ;
532 \}
533
534 \section{Compiling and Running}
535
536 Compile Blue Gene emulator programs using {\tt charmc} as one would
537 in the case of normal \charmpp{} programs. In order to link the
538 Blue Gene programs, use \texttt{-language bluegene} as an argument
539 to the {\tt charmc} linker.
540
541 \input{index}
542 \end{document}