AMPI manual intro
[charm.git] / doc / ampi / manual.tex
1 \documentclass[10pt]{article}
2 \usepackage{../pplmanual}
3 \input{../pplmanual}
4
5 \title{Adaptive MPI Manual}
6 \version{1.0}
7 \credits{
8 AMPI has been developed by Milind Bhandarkar with inputs from Gengbin Zheng and
9 Orion Lawlor. The derived data types (DDT) library, which AMPI uses for the
10 derived data types support, has been developed by Neelam Saboo. The current 
11 version of AMPI is maintained by Chao Huang.
12 }
13
14 \begin{document}
15 \maketitle
16
17 \section{Introduction}
18
19 This manual describes Adaptive MPI~(\ampi{}), which is an implementation of a
20 significant subset\footnote{Currently, 110 MPI-1.1 Standard functions have 
21 been implemented.} of MPI-1.1 Standard over \charmpp{}. \charmpp{} is a
22 \CC{}-based parallel programming library being developed by Prof. L. V. Kal\'{e} 
23 and his students back from 1992 until now at University of Illinois.
24
25 We first describe our philosophy behind this work (why we do what we do).
26 Later we give a brief introduction to \charmpp{} and rationale for \ampi{}
27 (tools of the trade). We then describe \ampi{} in detail. Finally we summarize the
28 changes required for original MPI codes to get them working with \ampi{}
29 (current state of our work). Appendices contain the gory details of installing
30 \ampi{}, building and running \ampi{} programs.
31
32 \subsection{Our Philosophy}
33
34 Developing parallel Computational Science and Engineering (CSE) applications is
35 a complex task. One has to implement the right physics, develop or choose and
36 code appropriate numerical methods, decide and implement the proper input and
37 output data formats, perform visualizations, and be concerned with correctness
38 and efficiency of the programs. It becomes even more complex for multi-physics
39 coupled simulations such as the solid propellant rocket simulation application.  
40 Our philosophy is to lessen the burden of the application developers by
41 providing advanced programming paradigms and versatile runtime systems that can
42 handle many common programming and performance concerns automatically and let the application
43 programmers focus on the actual application content.
44
45 Many of these concerns can be addressed using processor virtualization and over-decomposition philosophy of \charmpp{}. Thus, the developer only sees virtual processors and lets the runtime system deal with underlying physical processors. As an immediate and simple benefit, the programmer can use as many virtual processors ("MPI ranks") as the problem can be easily decomposed to them. For example, suppose the problem domain has $n*2^n$ parts that can be easily distributed but programming for general number of MPI processes is burdensome, then the developer can have $n*2^n$ virtual processors on any number of physical ones using \ampi{}.
46
47 Another benefit of virtualization is communication and computation overlap without programming effort. Techniques such as software pipelining require programming effort to achieve this goal and improve performance. However, one can use \ampi{} to have more virtual processors than physical processors to overlap communication and computation. In this manner, while some of the virtual processors of a physical one are waiting for a message to arrive, others can continue their execution. Thus, performance will be improved without any change to the source code.
48
49 One important concern is that of load imbalance. In a dynamic simulation application
50 such as rocket simulation, burning  solid fuel, sub-scaling for a certain part
51 of the mesh, crack propagation, particle flows all contribute to load
52 imbalance. Centralized load balancing strategy built into an application is
53 impractical since each individual modules are developed almost independently by
54 various developers. In addition, embedding a load balancing strategy in the code complicates it and programming effort increases significantly. Thus, the runtime system support for load balancing becomes
55 even more critical.
56
57 There are different load balancing strategies built into \charmpp{} that can be selected. Among those, some may fit better for an application depending on its characteristics. Moreover, one can write a new load balancer, best suited for an application, by the simple API provided inside \charmpp{} infrastructure. Our approach is
58 based on actual measurement of load information at runtime, and on migrating
59 computations from heavily loaded to lightly loaded processors.
60
61 For this approach to be effective, we need the computation to be split into
62 pieces many more in number than available processors. This allows us to
63 flexibly map and re-map these computational pieces to available processors.
64 This approach is usually called ``multi-domain decomposition''.
65
66 \charmpp{}, which we use as a runtime system layer for the work described here,
67 simplifies our approach. It embeds an elaborate performance tracing mechanism,
68 a suite of plug-in load balancing strategies, infrastructure for defining and
69 migrating computational load, and is interoperable with other programming
70 paradigms.
71
72 \subsection{Terminology}
73
74 \begin{description}
75
76 \item[Module] A module refers to either a complete program or a library with an
77 orchestrator subroutine\footnote{Like many software engineering terms, this
78 term is overused, and unfortunately clashes with Fortran 90 module that denotes
79 a program unit. We specifically refer to the later as ``Fortran 90 module'' to
80 avoid confusion.} . An orchestrator subroutine specifies the main control flow
81 of the module by calling various subroutines from the associated library and
82 does not usually have much state associated with it.
83
84 \item[Thread] A thread is a lightweight process that owns a stack and machine
85 registers including program counter, but shares code and data with other
86 threads within the same address space. If the underlying operating system
87 recognizes a thread, it is known as kernel thread, otherwise it is known as
88 user-thread. A context-switch between threads refers to suspending one thread's
89 execution and transferring control to another thread. Kernel threads typically
90 have higher context switching costs than user-threads because of operating
91 system overheads. The policy implemented by the underlying system for
92 transferring control between threads is known as thread scheduling policy.
93 Scheduling policy for kernel threads is determined by the operating system, and
94 is often more inflexible than user-threads. Scheduling policy is said to be
95 non-preemptive if a context-switch occurs only when the currently running
96 thread willingly asks to be suspended, otherwise it is said to be preemptive.
97 \ampi{} threads are non-preemptive user-level threads.
98
99 \item[Chunk] A chunk is a combination of a user-level thread and the data it
100 manipulates. When a program is converted from MPI to \ampi{}, we convert an MPI
101 process into a chunk. This conversion is referred to as chunkification.
102
103 \item[Object] An object is just a blob of memory on which certain computations
104 can be performed. The memory is referred to as an object's state, and the set
105 of computations that can be performed on the object is called the interface of
106 the object.
107
108 \end{description}
109
110 \section{\charmpp{}}
111
112 \charmpp{} is an object-oriented parallel programming library for \CC{}.  It
113 differs from traditional message passing programming libraries (such as MPI) in
114 that \charmpp{} is ``message-driven''. Message-driven parallel programs do not
115 block the processor waiting for a message to be received.  Instead, each
116 message carries with itself a computation that the processor performs on
117 arrival of that message. The underlying runtime system of \charmpp{} is called
118 \converse{}, which implements a ``scheduler'' that chooses which message to
119 schedule next (message-scheduling in \charmpp{} involves locating the object
120 for which the message is intended, and executing the computation specified in
121 the incoming message on that object). A parallel object in \charmpp{} is a
122 \CC{} object on which a certain computations can be asked to performe from
123 remote processors.
124
125 \charmpp{} programs exhibit latency tolerance since the scheduler always picks
126 up the next available message rather than waiting for a particular messageto
127 arrive.  They also tend to be modular, because of their object-based nature.
128 Most importantly, \charmpp{} programs can be \emph{dynamically load balanced},
129 because the messages are directed at objects and not at processors; thus
130 allowing the runtime system to migrate the objects from heavily loaded
131 processors to lightly loaded processors. It is this feature of \charmpp{} that
132 we utilize for \ampi{}.
133
134 Since many CSE applications are originally written using MPI, one would have to
135 do a complete rewrite if they were to be converted to \charmpp{} to take
136 advantage of dynamic load balancing. This is indeed impractical. However,
137 \converse{} -- the runtime system of \charmpp{} -- came to our rescue here,
138 since it supports interoperability between different parallel programming
139 paradigms such as parallel objects and threads. Using this feature, we
140 developed \ampi{}, an implementation of a significant subset of MPI-1.1
141 standard over \charmpp{}.  \ampi{} is described in the next section.
142
143 \section{AMPI}
144
145 \ampi{} utilizes the dynamic load balancing capabilities of \charmpp{} by
146 associating a ``user-level'' thread with each \charmpp{} migratable object.
147 User's code runs inside this thread, so that it can issue blocking receive
148 calls similar to MPI, and still present the underlying scheduler an opportunity
149 to schedule other computations on the same processor. The runtime system keeps
150 track of computation loads of each thread as well as communication graph
151 between \ampi{} threads, and can migrate these threads in order to balance the
152 overall load while simultaneously minimizing communication overhead. 
153
154 \subsection{AMPI Status}
155
156 Currently all the MPI-1.1 Standard functions are supported in \ampi{}, with a
157 collection of our extentions explained in detail in this manual. One-sided
158 communication calls in MPI-2 are implemented, but they are not taking advantage
159 of RMA features yet. Also ROMIO\footnote{http://www-unix.mcs.anl.gov/romio/} 
160 has been integrated to support parallel I/O features. Link with {\tt -lampiromio}
161 to take advantage of this library.
162
163 Following MPI-1.1 basic datatypes are supported in \ampi{}. (Some are not 
164 available in Fortran binding. Refer to MPI-1.1 Standard for details.)
165 \begin{alltt}
166 MPI_DATATYPE_NULL  MPI_BYTE            MPI_UNSIGNED_LONG MPI_LONG_DOUBLE_INT
167 MPI_DOUBLE         MPI_PACKED          MPI_LONG_DOUBLE   MPI_2FLOAT
168 MPI_INT            MPI_SHORT           MPI_FLOAT_INT     MPI_2DOUBLE
169 MPI_FLOAT          MPI_LONG            MPI_DOUBLE_INT    MPI_LB
170 MPI_COMPLEX        MPI_UNSIGNED_CHAR   MPI_LONG_INT      MPI_UB
171 MPI_LOGICAL        MPI_UNSIGNED_SHORT  MPI_2INT
172 MPI_CHAR           MPI_UNSIGNED        MPI_SHORT_INT
173 \end{alltt}
174
175 Following MPI-1.1 reduction operations are supported in \ampi{}.
176
177 \begin{alltt}
178 MPI_MAX   MPI_MIN   MPI_SUM   MPI_PROD  MPI_MAXLOC  MPI_MINLOC
179 MPI_LAND  MPI_LOR   MPI_LXOR  MPI_BAND  MPI_BOR     MPI_BXOR
180 \end{alltt}
181
182 Following are AMPI extension calls, which will be explained in detail in this
183 manual.
184 \begin{alltt}
185 MPI_Migrate     MPI_Checkpoint  MPI_Restart     MPI_Register    MPI_Get_userdata
186 MPI_Ialltoall   MPI_Iallgather  MPI_Iallreduce  MPI_Ireduce     MPI_IGet
187 \end{alltt}
188
189
190 \subsection{Name for Main Program}
191
192 To convert an existing program to use AMPI, the main function or program may need to be renamed. The changes should be made as follows:
193
194 \subsubsection{Fortran}
195
196 You must declare the main program as a subroutine called ``MPI\_MAIN''. Do not declare the main subroutine as a \textit{program} because it will never be called by the AMPI runtime.
197
198 \subsubsection{C or C++}
199
200 The main function can be left as is, if \texttt{mpi.h} is included before the main function. This header file has a preprocessor macro that renames main, and the renamed version is called by the AMPI runtime by each thread.
201
202
203 \subsection{Global Variable Privatization}
204
205 For dynamic load balancing to be effective, one needs to map multiple
206 user-level threads onto a processor. Traditional MPI programs assume that the
207 entire processor is allocated to themselves, and that only one thread of
208 control exists within the process's address space.  Thats where the need arises
209 to make some transformations to the original MPI program in order to run
210 correctly with \ampi{}.
211
212 The basic transformation needed to port the MPI program to \ampi{} is
213 privatization of global variables.\footnote{Typical Fortran MPI programs
214 contain three types of global variables.
215
216 \begin{enumerate}
217
218 \item Global variables that are ``read-only''. These are either
219 \emph{parameters} that are set at compile-time. Or other variables that are
220 read as input or set at the beginning of the program and do not change during
221 execution. It is not necessary to privatize such variables.
222
223 \item Global variables that are used as temporary buffers. These are variables
224 that are used temporarily to store values to be accessible across subroutines.
225 These variables have a characteristic that there is no blocking call such as
226 \texttt{MPI\_recv} between the time the variable is set and the time it is ever
227 used. It is not necessary to privatize such variables either. 
228
229 \item True global variables. These are used across subroutines that contain
230 blocking receives and therefore possibility of a context switche between the
231 definition and use of the variable. These variables need to be privatized.
232
233 \end{enumerate}
234 }
235 With the MPI process model, each MPI node can keep a copy of its own
236 ``permanent variables'' -- variables that are accessible from more than one
237 subroutines without passing them as arguments.  Module variables, ``saved''
238 subroutine local variables, and common blocks in Fortran 90 belong to this
239 category. If such a program is executed without privatization on \ampi{}, all
240 the \ampi{} threads that reside on one processor will access the same copy of
241 such variables, which is clearly not the desired semantics.  To ensure correct
242 execution of the original source program, it is necessary to make such
243 variables ``private'' to individual threads. We are two choices: automatic 
244 global swapping and manual code modification.
245
246 \subsubsection{Automatic Globals Swapping}
247 Thanks to the ELF Object Format, we have successfully automated the procedure 
248 of switching the set of user global variables when switching thread contexts. 
249 The only thing that the user needs to do is to set flag {\tt -swapglobals} 
250 at compile and link time. Currently this feature only works on x86 and x86\_64
251  (i.e. amd64) platforms that fully support ELF. Thus it will not work on PPC or
252   Itanium, or on some microkernels such as Catamount.When this feature does
253    not work for you,
254 you are advised to make the modification manually, which is detailed in the
255 following section.
256
257 \subsubsection{Manual Change}
258 We have employed a strategy of argument passing to do this privatization
259 transformation. That is, the global variables are bunched together in a
260 single user-defined type, which is allocated by each thread dynamically. Then a
261 pointer to this type is passed from subroutine to subroutine as an argument.
262 Since the subroutine arguments are passed on a stack, which is not shared
263 across all threads, each subroutine, when executing within a thread operates on
264 a private copy of the global variables. 
265
266 This scheme is demonstrated in the following examples. The original Fortran 90 
267 code contains a module \texttt{shareddata}. This module is used in the main 
268 program and a subroutine \texttt{subA}.
269
270 \begin{alltt}
271 !FORTRAN EXAMPLE
272 MODULE shareddata
273   INTEGER :: myrank
274   DOUBLE PRECISION :: xyz(100)
275 END MODULE
276
277 SUBROUTINE MPI_MAIN
278   USE shareddata
279   include 'mpif.h'
280   INTEGER :: i, ierr
281   CALL MPI_Init(ierr)
282   CALL MPI_Comm_rank(MPI_COMM_WORLD, myrank, ierr)
283   DO i = 1, 100
284     xyz(i) =  i + myrank
285   END DO
286   CALL subA
287   CALL MPI_Finalize(ierr)
288 END PROGRAM
289
290 SUBROUTINE subA
291   USE shareddata
292   INTEGER :: i
293   DO i = 1, 100
294     xyz(i) = xyz(i) + 1.0
295   END DO
296 END SUBROUTINE
297
298 //C Example
299 #include <mpi.h>
300
301 int myrank;
302 double xyz[100];
303
304 void subA();
305 int main(int argc, char** argv)\{
306   int i;
307   MPI_Init(&argc, &argv);
308   MPI_Comm_rank(MPI_COMM_WORLD, myrank);
309   for(i=0;i<100;i++)
310     xyz[i] = i + myrank;
311   subA();
312   MPI_Finalize();
313 \}
314
315 void subA()\{
316   int i;
317   for(i=0;i<100;i++)
318     xyz[i] = xyz[i] + 1.0;
319 \}
320 \end{alltt}
321
322 \ampi{} executes the main subroutine inside a user-level thread as a subroutine. 
323  
324 Now we transform this program using the argument passing strategy. We first group the
325 shared data into a user-defined type.
326
327 \begin{alltt}
328 !FORTRAN EXAMPLE
329 MODULE shareddata
330   \emph{TYPE chunk}
331     INTEGER :: myrank
332     DOUBLE PRECISION :: xyz(100)
333   \emph{END TYPE}
334 END MODULE
335
336 //C Example
337 struct shareddata\{
338   int myrank;
339   double xyz[100];
340 \};
341 \end{alltt}
342
343 Now we modify the main subroutine to dynamically allocate this data and change the
344 references to them. Subroutine \texttt{subA} is then modified to take this data
345 as argument. 
346
347 \begin{alltt}
348 !FORTRAN EXAMPLE
349 SUBROUTINE MPI_Main
350   USE shareddata
351   USE AMPI
352   INTEGER :: i, ierr
353   \emph{TYPE(chunk), pointer :: c}
354   CALL MPI_Init(ierr)
355   \emph{ALLOCATE(c)}
356   CALL MPI_Comm_rank(MPI_COMM_WORLD, c\%myrank, ierr)
357   DO i = 1, 100
358     \emph{c\%xyz(i) =  i + c\%myrank}
359   END DO
360   CALL subA(c)
361   CALL MPI_Finalize(ierr)
362 END SUBROUTINE
363
364 SUBROUTINE subA(c)
365   USE shareddata
366   \emph{TYPE(chunk) :: c}
367   INTEGER :: i
368   DO i = 1, 100
369     \emph{c\%xyz(i) = c\%xyz(i) + 1.0}
370   END DO
371 END SUBROUTINE
372
373 //C Example
374 void MPI_Main\{
375   int i,ierr;
376   struct shareddata *c;
377   ierr = MPI_Init();
378   c = (struct shareddata*)malloc(sizeof(struct shareddata));
379   ierr = MPI_Comm_rank(MPI_COMM_WORLD, c.myrank);
380   for(i=0;i<100;i++)
381     c.xyz[i] = i + c.myrank;
382   subA(c);
383   ierr = MPI_Finalize();
384 \}
385
386 void subA(struct shareddata *c)\{
387   int i;
388   for(i=0;i<100;i++)
389     c.xyz[i] = c.xyz[i] + 1.0;
390 \}
391 \end{alltt}
392
393 With these changes, the above program can be made thread-safe. Note that it is
394 not really necessary to dynamically allocate \texttt{chunk}. One could have
395 declared it as a local variable in subroutine \texttt{MPI\_Main}.  (Or for a
396 small example such as this, one could have just removed the \texttt{shareddata}
397 module, and instead declared both variables \texttt{xyz} and \texttt{myrank} as
398 local variables). This is indeed a good idea if shared data are small in size.
399 For large shared data, it would be better to do heap allocation because in
400 \ampi{}, the stack sizes are fixed at the beginning (can be specified from the
401 command line) and stacks do not grow dynamically.
402
403
404
405 \subsection{Extensions for Migrations}
406
407 For MPI chunks to migrate, we have added a few calls to \ampi{}. These include
408 ability to register thread-specific data with the run-time system, to pack all
409 the thread's data, and to express willingness to migrate.
410
411 \subsubsection{Registering Chunk data}
412
413 When the \ampi{} runtime system decides that load imbalance exists within the
414 application, it will invoke one of its internal load balancing strategies,
415 which determines the new mapping of \ampi{} chunks so as to balance the load.
416 Then \ampi{} runtime has to pack up the chunk's state and move it to its new
417 home processor. \ampi{} packs up any internal data in use by the chunk,
418 including the thread's stack in use. This means that the local variables
419 declared in subroutines in a chunk, which are created on stack, are
420 automatically packed up by the \ampi{} runtime system. However, it has no way
421 of knowing what other data are in use by the chunk. Thus upon starting
422 execution, a chunk needs to notify the system about the data that it is going
423 to use (apart from local variables.) Even with the data registration, \ampi{}
424 cannot determine what size the data is, or whether the registered data contains
425 pointers to other places in memory. For this purpose, a packing subroutine also
426 needs to be provided to the \ampi{} runtime system along with registered data.
427 (See next section for writing packing subroutines.) The call provided by
428 \ampi{} for doing this is \texttt{MPI\_Register}. This function takes two
429 arguments: A data item to be transported alongwith the chunk, and the pack
430 subroutine, and returns an integer denoting the registration identifier. In
431 C/\CC{} programs, it may be necessary to use this return value after migration
432 completes and control returns to the chunk, using function
433 \texttt{MPI\_Get\_userdata}. Therefore, the return value should be stored in a
434 local variable.
435
436 \subsubsection{Migration}
437
438 The \ampi{} runtime system could detect load imbalance by itself and invoke the
439 load balancing strategy. However, since the application code is going to
440 pack/unpack the chunk's data, writing the pack subroutine will be complicated
441 if migrations occur at a stage unknown to the application. For example, if the
442 system decides to migrate a chunk while it is in initialization stage (say,
443 reading input files), application code will have to keep track of how much data
444 it has read, what files are open etc. Typically, since initialization occurs
445 only once in the beginning, load imbalance at that stage would not matter much.
446 Therefore, we want the demand to perform load balance check to be initiated by
447 the application.
448
449 \ampi{} provides a subroutine \texttt{MPI\_Migrate} for this purpose. Each
450 chunk periodically calls \texttt{MPI\_Migrate}. Typical CSE applications are
451 iterative and perform multiple time-steps. One should call
452 \texttt{MPI\_Migrate} in each chunk at the end of some fixed number of
453 timesteps. The frequency of \texttt{MPI\_Migrate} should be determined by a
454 tradeoff between conflicting factors such as the load balancing overhead, and
455 performance degradation caused by load imbalance. In some other applications,
456 where application suspects that load imbalance may have occurred, as in the
457 case of adaptive mesh refinement; it would be more effective if it performs a
458 couple of timesteps before telling the system to re-map chunks. This will give
459 the \ampi{} runtime system some time to collect the new load and communication
460 statistics upon which it bases its migration decisions. Note that
461 \texttt{MPI\_Migrate} does NOT tell the system to migrate the chunk, but
462 merely tells the system to check the load balance after all the chunks call
463 \texttt{MPI\_Migrate}. To migrate the chunk or not is decided only by the
464 system's load balancing strategy.
465
466 \subsubsection{Packing/Unpacking Thread Data}
467
468 Once the \ampi{} runtime system decides which chunks to send to which
469 processors, it calls the specified pack subroutine for that chunk, with the
470 chunk-specific data that was registered with the system using
471 \texttt{MPI\_Register}. This section explains how a subroutine should be
472 written for performing pack/unpack.
473
474 There are three steps to transporting the chunk's data to other processor.
475 First, the system calls a subroutine to get the size of the buffer required to
476 pack the chunk's data. This is called the ``sizing'' step. In the next step,
477 which is called immediately afterward on the source processor, the system
478 allocates the required buffer and calls the subroutine to pack the chunk's data
479 into that buffer. This is called the ``packing'' step. This packed data is then
480 sent as a message to the destination processor, where first a chunk is created
481 (alongwith the thread) and a subroutine is called to unpack the chunk's data
482 from the buffer. This is called the ``unpacking'' step.
483
484 Though the above description mentions three subroutines called by the \ampi{}
485 runtime system, it is possible to actually write a single subroutine that will
486 perform all the three tasks. This is achieved using something we call a
487 ``pupper''. A pupper is an external subroutine that is passed to the chunk's
488 pack-unpack-sizing subroutine, and this subroutine, when called in different
489 phases performs different tasks. An example will make this clear:
490
491 Suppose the chunk data is defined as a user-defined type in Fortran 90:
492
493 \begin{alltt}
494 !FORTRAN EXAMPLE
495 MODULE chunkmod
496   TYPE, PUBLIC :: chunk
497       INTEGER , parameter :: nx=4, ny=4, tchunks=16
498       REAL(KIND=8) t(22,22)
499       INTEGER xidx, yidx
500       REAL(KIND=8), dimension(400):: bxm, bxp, bym, byp
501   END TYPE chunk
502 END MODULE
503
504 //C Example
505 struct chunk\{
506   double t;
507   int xidx, yidx;
508   double bxm,bxp,bym,byp;
509 \};
510 \end{alltt}
511
512 Then the pack-unpack subroutine \texttt{chunkpup} for this chunk module is
513 written as:
514
515 \begin{alltt}
516 !FORTRAN EXAMPLE
517 SUBROUTINE chunkpup(p, c)
518   USE pupmod
519   USE chunkmod
520   IMPLICIT NONE
521   INTEGER :: p
522   TYPE(chunk) :: c
523
524   call pup(p, c\%t)
525   call pup(p, c\%xidx)
526   call pup(p, c\%yidx)
527   call pup(p, c\%bxm)
528   call pup(p, c\%bxp)
529   call pup(p, c\%bym)
530   call pup(p, c\%byp)
531 end subroutine
532
533 //C Example
534 void chunkpup(pup_er p, struct chunk c)\{
535   pup_double(p,c.t);
536   pup_int(p,c.xidx);
537   pup_int(p,c.yidx);
538   pup_double(p,c.bxm);
539   pup_double(p,c.bxp);
540   pup_double(p,c.bym);
541   pup_double(p,c.byp);
542 \}
543 \end{alltt}
544
545 There are several things to note in this example. First, the same subroutine
546 \texttt{pup} (declared in module \texttt{pupmod}) is called to size/pack/unpack
547 any type of data. This is possible because of procedure overloading possible in
548 Fortran 90. Second is the integer argument \texttt{p}. It is this argument that
549 specifies whether this invocation of subroutine \texttt{chunkpup} is sizing,
550 packing or unpacking. Third, the integer parameters declared in the type
551 \texttt{chunk} need not be packed or unpacked since they are guaranteed to be
552 constants and thus available on any processor.
553
554 A few other functions are provided in module \texttt{pupmod}. These functions
555 provide more control over the packing/unpacking process. Suppose one modifies
556 the \texttt{chunk} type to include allocatable data or pointers that are
557 allocated dynamically at runtime. In this case, when the chunk is packed, these
558 allocated data structures should be deallocated after copying them to buffers,
559 and when the chunk is unpacked, these data structures should be allocated
560 before copying them from the buffers.  For this purpose, one needs to know
561 whether the invocation of \texttt{chunkpup} is a packing one or unpacking one.
562 For this purpose, the \texttt{pupmod} module provides functions
563 \verb+fpup_isdeleting+(\verb+fpup_isunpacking+). These functions return logical value
564 \verb+.TRUE.+ if the invocation is for packing (unpacking), and \verb+.FALSE.+
565 otherwise. Following example demonstrates this:
566
567 Suppose the type \texttt{dchunk} is declared as:
568
569 \begin{alltt}
570 !FORTRAN EXAMPLE
571 MODULE dchunkmod
572   TYPE, PUBLIC :: dchunk
573       INTEGER :: asize
574       REAL(KIND=8), pointer :: xarr(:), yarr(:)
575   END TYPE dchunk
576 END MODULE
577
578 //C Example
579 struct dchunk\{
580   int asize;
581   double* xarr, *yarr;
582 \};
583 \end{alltt}
584
585 Then the pack-unpack subroutine is written as:
586
587 \begin{alltt}
588 !FORTRAN EXAMPLE
589 SUBROUTINE dchunkpup(p, c)
590   USE pupmod
591   USE dchunkmod
592   IMPLICIT NONE
593   INTEGER :: p
594   TYPE(dchunk) :: c
595
596   pup(p, c\%asize)
597   \emph{
598   IF (fpup_isunpacking(p)) THEN       !! if invocation is for unpacking
599     allocate(c\%xarr(asize))
600     ALLOCATE(c\%yarr(asize))
601   ENDIF
602   }
603   pup(p, c\%xarr)
604   pup(p, c\%yarr)
605   \emph{
606   IF (fpup_isdeleting(p)) THEN        !! if invocation is for packing
607     DEALLOCATE(c\%xarr(asize))
608     DEALLOCATE(c\%yarr(asize))
609   ENDIF
610   }
611
612 END SUBROUTINE
613
614 //C Example
615 void dchunkpup(pup_er p, struct dchunk c)\{
616   pup_int(p,c.asize);
617   if(pup_isUnpacking(p))\{
618     c.xarr = (double *)malloc(sizeof(double)*c.asize);
619     c.yarr = (double *)malloc(sizeof(double)*c.asize);
620   \}
621   pup_doubles(p,c.xarr,c.asize);
622   pup_doubles(p,c.yarr,c.asize);
623   if(pup_isPacking(p))\{
624     free(c.xarr);
625     free(c.yarr);
626   \}
627 \}
628 \end{alltt}
629
630 One more function \verb+fpup_issizing+ is also available in module \texttt{pupmod}
631 that returns \verb+.TRUE.+ when the invocation is a sizing one. In practice one
632 almost never needs to use it.
633
634 \subsection{Extensions for Checkpointing}
635
636 The pack-unpack subroutines written for migrations make sure that the current
637 state of the program is correctly packed (serialized) so that it can be
638 restarted on a different processor. Using the \emph{same} subroutines, it
639 is also possible to save the state of the program to disk, so that if the 
640 program were to crash abruptly, or if the allocated time for the program
641 expires before completing execution, the program can be restarted from the
642 previously checkpointed state. Thus, the pack-unpack subroutines act as the 
643 key facility for checkpointing in addition to their usual role for migration.
644
645 A subroutine for checkpoint purpose has been added to AMPI:
646 \texttt{void MPI\_Checkpoint(char *dirname);}
647 This subroutine takes a directory name as its argument. It is a collective 
648 function, meaning every virtual processor in the program needs to call this 
649 subroutine and specify the same directory name. (Typically, in an
650 iterative AMPI program, the iteration number, converted to a character string,
651 can serve as a checkpoint directory name.) This directory is created, and the
652 entire state of the program is checkpointed to this directory.  One can restart
653 the program from the checkpointed state by specifying \texttt{"+restart
654 dirname"} on the command-line. This capability is powered by the \charmpp{} 
655 runtime system. For more information about \charmpp{} checkpoint/restart
656 mechanism please refer to \charmpp{} manual. 
657
658 \subsection{Extensions for Memory Efficiency}
659
660 MPI functions usually require the user to preallocate the data buffers needed before the
661 functions being called. For unblocking communication primitives, sometimes the user would
662 like to do lazy memory allocation until the data actually arrives, which gives the
663 oppotunities to write more memory efficient programs.     
664 We provide a set of AMPI functions as an extension to the standard MPI-2 one-sided calls,
665 where we provide a split phase MPI\_Get called MPI\_IGet. MPI\_IGet preserves the similar
666 semantics as MPI\_Get except that no user buffer is provided to hold incoming data.
667 MPI\_IGet\_Wait will block until the requested data arrives and runtime system takes
668 care to allocate space, do appropriate unpacking based on data type, and return.
669 MPI\_IGet\_Free lets the runtime system free the resources being used for this get request
670 including the data buffer. And MPI\_IGet\_Data is the utility program that returns the
671 actual data.     
672  
673
674 \begin{alltt}
675
676 int MPI_IGet(MPI_Aint orgdisp, int orgcnt, MPI_Datatype orgtype, int rank,
677              MPI_Aint targdisp, int targcnt, MPI_Datatype targtype, MPI_Win win,
678              MPI_Request *request);
679
680 int MPI_IGet_Wait(MPI_Request *request, MPI_Status *status, MPI_Win win);
681
682 int MPI_IGet_Free(MPI_Request *request, MPI_Status *status, MPI_Win win);
683
684 char* MPI_IGet_Data(MPI_Status status);
685
686 \end{alltt}
687
688
689
690 \subsection{Extensions for Interoperability}
691
692 Interoperability between different modules is essential for coding coupled
693 simulations.  In this extension to \ampi{}, each MPI application module runs
694 within its own group of user-level threads distributed over the physical
695 parallel machine.  In order to let \ampi{} know which chunks are to be created,
696 and in what order, a top level registration routine needs to be written. A
697 real-world example will make this clear. We have an MPI code for fluids and
698 another MPI code for solids, both with their main programs, then we first
699 transform each individual code to run correctly under \ampi{} as standalone
700 codes. This involves the usual ``chunkification'' transformation so that
701 multiple chunks from the application can run on the same processor without
702 overwriting each other's data. This also involves making the main program into
703 a subroutine and naming it \texttt{MPI\_Main}.
704
705 Thus now, we have two \texttt{MPI\_Main}s, one for the fluids code and one for
706 the solids code. We now make these codes co-exist within the same executable,
707 by first renaming these \texttt{MPI\_Main}s as \texttt{Fluids\_Main} and
708 \texttt{Solids\_Main}\footnote{Currently, we assume that the interface code,
709 which does mapping and interpolation among the boundary values of Fluids and
710 Solids domain, is integrated with one of Fluids and Solids.} writing a
711 subroutine called \texttt{MPI\_Setup}.
712
713 \begin{alltt}
714 !FORTRAN EXAMPLE
715 SUBROUTINE MPI_Setup
716   USE ampi
717   CALL MPI_Register_main(Solids_Main)
718   CALL MPI_Register_main(Fluids_Main)
719 END SUBROUTINE
720
721 //C Example
722 void MPI_Setup()\{
723   MPI_Register_main(Solids_Main);
724   MPI_Register_main(Fluids_Main);
725 \}
726 \end{alltt}
727
728 This subroutine is called from the internal initialization routines of \ampi{}
729 and tells \ampi{} how many number of distinct chunk types (modules) exist, and
730 which orchestrator subroutines they execute.
731
732 The number of chunks to create for each chunk type is specified on the command
733 line when an \ampi{} program is run. Appendix B explains how \ampi{} programs
734 are run, and how to specify the number of chunks (\verb|+vp| option). In the
735 above case, suppose one wants to create 128 chunks of Solids and 64 chunks of
736 Fluids on 32 physical processors, one would specify those with multiple
737 \verb|+vp| options on the command line as:
738
739 \begin{alltt}
740 > charmrun gen1.x +p 32 +vp 128 +vp 64
741 \end{alltt}
742
743 This will ensure that multiple chunk types representing different complete
744 applications can co-exist within the same executable. They can also continue to
745 communicate among their own chunk-types using the same \ampi{} function calls
746 to send and receive with communicator argument as \texttt{MPI\_COMM\_WORLD}.
747 But this would be completely useless if these individual applications cannot
748 communicate with each other, which is essential for building efficient coupled
749 codes.  For this purpose, we have extended the \ampi{} functionality to allow
750 multiple ``\texttt{COMM\_WORLD}s''; one for each application. These \emph{world
751 communicators} form a ``communicator universe'': an array of communicators
752 aptly called \emph{MPI\_COMM\_UNIVERSE}. This array of communicators is 
753 indexed [1 . . . \texttt{MPI\_MAX\_COMM}]. In the current implementation,
754 \texttt{MPI\_MAX\_COMM} is 8, that is, maximum of 8 applications can co-exist
755 within the same executable.
756
757 The order of these \texttt{COMM\_WORLD}s within \texttt{MPI\_COMM\_UNIVERSE}
758 is determined by the order in which individual applications are registered in
759 \texttt{MPI\_Setup}.
760
761 Thus, in the above example, the communicator for the Solids module would be
762 \texttt{MPI\_COMM\_UNIVERSE(1)} and communicator for Fluids module would be
763 \texttt{MPI\_COMM\_UNIVERSE(2)}.
764
765 Now any chunk within one application can communicate with any chunk in the
766 other application using the familiar send or receive \ampi{} calls by
767 specifying the appropriate communicator and the chunk number within that
768 communicator in the call. For example if a Solids chunk number 36 wants to send
769 data to chunk number 47 within the Fluids module, it calls:
770
771 \begin{alltt}
772 !FORTRAN EXAMPLE
773 INTEGER , PARAMETER :: Fluids_Comm = 2
774 CALL MPI_Send(InitialTime, 1, MPI_Double_Precision, tag, 
775               \emph{47, MPI_Comm_Universe(Fluids_Comm)}, ierr)
776
777 //C Example
778 int Fluids_Comm = 2;
779 ierr = MPI_Send(InitialTime, 1, MPI_DOUBLE, tag,
780                 \emph{47, MPI_Comm_Universe(Fluids_Comm)});
781 \end{alltt}
782
783 The Fluids chunk has to issue a corresponding receive call to receive this
784 data:
785
786 \begin{alltt}
787 !FORTRAN EXAMPLE
788 INTEGER , PARAMETER :: Solids_Comm = 1
789 CALL MPI_Recv(InitialTime, 1, MPI_Double_Precision, tag, 
790               \emph{36, MPI_Comm_Universe(Solids_Comm)}, stat, ierr)
791
792 //C Example
793 int Solids_Comm = 1;
794 ierr = MPI_Recv(InitialTime, 1, MPI_DOUBLE, tag,
795                 \emph{36, MPI_Comm_Universe(Solids_Comm)}, &stat);
796 \end{alltt}
797
798 \subsection{Extensions for Sequential Re-run of a Parallel Node}
799 In some scenarios, a sequential re-run of a parallel node is desired. One
800 example is instruction-level accurate architecture simulations, in which case
801 the user may wish to repeat the execution of a node in a parallel run in the
802 sequential simulator. AMPI provides support for such needs by logging the change
803 in the MPI environment on a certain processors. To activate the feature, build 
804 AMPI module with variable ``AMPIMSGLOG'' defined, like the following command in
805 charm directory. (Linking with zlib ``-lz'' might be required with this, for
806 generating compressed log file.)
807
808 \begin{alltt}
809 > ./build AMPI net-linux -DAMPIMSGLOG
810 \end{alltt}
811
812 The feature is used in two phases: writing (logging) the environment and
813 repeating the run. The first logging phase is invoked by a parallel run of the
814 AMPI program with some additional command line options. 
815
816 \begin{alltt}
817 > ./charmrun ./pgm +p4 +vp4 +msgLogWrite +msgLogRank 2 +msgLogFilename "msg2.log"
818 \end{alltt}
819
820 In the above example, a parallel run with 4 processors and 4 VPs will be
821 executed, and the changes in the MPI environment of processor 2 (also VP 2,
822 starting from 0) will get logged into diskfile "msg2.log". 
823
824 Unlike the first run, the re-run is a sequential program, so it is not invoked
825 by charmrun (and omitting charmrun options like +p4 and +vp4), and additional
826 comamnd line options are required as well. 
827
828 \begin{alltt}
829 > ./pgm +msgLogRead +msgLogRank 2 +msgLogFilename "msg2.log"
830 \end{alltt}
831
832 \subsection{Communication Optimizations for AMPI}
833 AMPI is powered by the \charmpp{} communication optimization support now!
834 Currently the user needs to specify the communication pattern by command
835 line option. In the future this can be done automatically by the system.
836
837 Currently there are four strategies available: USE\_DIRECT, USE\_MESH,
838 USE\_HYPERCUBE and USE\_GRID. USE\_DIRECT sends the message directly. 
839 USE\_MESH imposes a 2d Mesh virtual topology on the processors so each 
840 processor sends messages to its neighbors in its row and column of the 
841 mesh which forward the messages to their correct destinations. USE\_HYPERCUBE 
842 and USE\_GRID impose a hypercube and a 3d Grid topologies on the processors. 
843 USE\_HYPERCUBE will do best for very small messages and small number of 
844 processors, 3d has better performance for slightly higher message sizes 
845 and then Mesh starts performing best. The programmer is encouraged to try 
846 out all the strategies. (Stolen from the CommLib manual by Sameer :)
847
848 For more details please refer to the CommLib paper \footnote{L. V. Kale and 
849 Sameer Kumar and Krishnan Vardarajan, 2002. 
850 http://finesse.cs.uiuc.edu/papers/CommLib.pdf}. 
851
852 Specifying the strategy is as simple as a command line option +strategy. For
853 example:
854 \begin{alltt}
855 > ./charmrun +p64 alltoall +vp64 1000 100 +strategy USE\_MESH
856 \end{alltt}
857 tells the system to use MESH strategy for CommLib. By default USE\_DIRECT is
858 used.
859
860 \subsection{User Defined Initial Mapping}
861                                                                                 
862 You can define the initial mapping of virtual processors (vp) to physical 
863 processors (p) as a runtime option. You can choose from predefined initial 
864 mappings or define your own mappings. Following predefined mappings are 
865 available:
866                                                                                 
867 \begin{description}
868
869 \item[Round Robin]
870                                                                                 
871 This mapping scheme, maps virtual processor to physical processor in round-robin
872 fashion, i.e. if there are 8 virtual processors and 2 physical processors then
873 virtual processors indexed 0,2,4,6 will be mapped to physical processor 0 and 
874 virtual processors indexed 1,3,5,7 will be mapped to physical processor 1. 
875
876 \begin{alltt}
877 > ./charmrun ./hello +p2 +vp8 +mapping RR\_MAP
878 \end{alltt}
879                                                                                 
880 \item[Block Mapping]
881                                                                                 
882 This mapping scheme, maps virtual processors to physical processor in chunks, 
883 i.e. if there are 8 virtual processors and 2 physical processors then virtual 
884 processors indexed 0,1,2,3 will be mapped to physical processor 0 and virtual 
885 processors indexed 4,5,6,7 will be mapped to physical processor 1.
886                                                                                 
887 \begin{alltt}
888 > ./charmrun ./hello +p2 +vp8 +mapping BLOCK\_MAP
889 \end{alltt}
890                                                                                 
891 \item[Proportional Mapping]
892                                                                                 
893 This scheme takes the processing capability of physical processors into account
894 for mapping virtual processors to physical processors, i.e. if there are 2 
895 processors with different processing power, then number of virtual processors 
896 mapped to processors will be in proportion to their processing power.
897                                                                                 
898 \begin{alltt}
899 > ./charmrun ./hello +p2 +vp8 +mapping PROP\_MAP
900 > ./charmrun ./hello +p2 +vp8
901 \end{alltt}
902
903 \end{description}
904
905 If you want to define your own mapping scheme, please contact us for help.
906
907 \subsection{Compiling AMPI Programs}
908
909 \charmpp{} provides a cross-platform compile-and-link script called \charmc{}
910 to compile C, \CC{}, Fortran, \charmpp{} and \ampi{} programs.  This script
911 resides in the \texttt{bin} subdirectory in the \charmpp{} installation
912 directory. The main purpose of this script is to deal with the differences of
913 various compiler names and command-line options across various machines on
914 which \charmpp{} runs. While, \charmc{} handles C and \CC{} compiler
915 differences most of the time, the support for Fortran 90 is new, and may have
916 bugs. But \charmpp{} developers are aware of this problem and are working to
917 fix them. Even in its alpha stage of Fortran 90 support, \charmc{} still
918 handles many of the compiler differences across many machines, and it is
919 recommended that \charmc{} be used to compile and linking \ampi{} programs. One
920 major advantage of using \charmc{} is that one does not have to specify which
921 libraries are to be linked for ensuring that \CC{} and Fortran 90 codes are
922 linked correctly together. Appropriate libraries required for linking such
923 modules together are known to \charmc{} for various machines.
924
925 In spite of the platform-neutral syntax of \charmc{}, one may have to specify
926 some platform-specific options for compiling and building \ampi{} codes.
927 Fortunately, if \charmc{} does not recognize any particular options on its
928 command line, it promptly passes it to all the individual compilers and linkers
929 it invokes to compile the program.
930
931 \appendix
932
933 \section{Installing AMPI}
934
935 \ampi{} is included in the source distribution of \charmpp{}. 
936 To get the latest sources from PPL, visit:
937         http://charm.cs.uiuc.edu/
938
939 and follow the download link.
940 Now one has to build \charmpp{} and \ampi{} from source.
941
942 The build script for \charmpp{} is called \texttt{build}. The syntax for this
943 script is:
944
945 \begin{alltt}
946 > build <target> <version> <opts>
947 \end{alltt}
948
949 For building \ampi{} (which also includes building \charmpp{} and other
950 libraries needed by \ampi{}), specify \verb+<target>+ to be \verb+AMPI+. And
951 \verb+<opts>+ are command line options passed to the \verb+charmc+ compile
952 script.  Common compile time options such as \texttt{-g, -O, -Ipath, -Lpath,
953 -llib} are accepted. 
954
955 To build a debugging version of \ampi{}, use the option: ``\texttt{-g}''. 
956 To build a production version of \ampi{}, use the options: ``\texttt{-O 
957 -DCMK\_OPTIMIZE=1}''.
958
959 \verb+<version>+ depends on the machine, operating system, and the underlying
960 communication library one wants to use for running \ampi{} programs.
961 See the charm/README file for details on picking the proper version.
962 Following is an example of how to build AMPI under linux and ethernet
963 environment, with debugging info produced:
964
965 \begin{alltt}
966 > build AMPI net-linux -g
967 \end{alltt}
968
969 \section{Building and Running AMPI Programs}
970 \subsection{Building}
971 \charmpp{} provides a compiler called charmc in your charm/bin/ directory. 
972 You can use this compiler to build your AMPI program the same way as other
973 compilers like cc. Especially, to build an AMPI program, a command line 
974 option \emph{-language ampi} should be applied. All the command line 
975 flags that you would use for other compilers can be used with charmc the 
976 same way. For example:
977
978 \begin{alltt}
979 > charmc -language ampi -c pgm.c -O3
980 > charmc -language ampi -o pgm pgm.o -lm -O3 
981 \end{alltt}
982
983 Shortcuts to the AMPI compiler are provided. If you have added charm/bin 
984 into your \$PATH environment variable, simply type \emph{mpicc, mpiCC, 
985 mpif77,} and \emph{mpif90} as provided by other MPI implementations.
986
987 \begin{alltt}
988 > mpicc -c pgm.c -g
989 \end{alltt}
990
991 \subsection{Running}
992 \charmpp{} distribution contains a script called \texttt{charmrun} that makes
993 the job of running \ampi{} programs portable and easier across all parallel
994 machines supported by \charmpp{}. \texttt{charmrun} is copied to a directory
995 where an \ampi{} prgram is built using \charmc{}. It takes a command line
996 parameter specifying number of processors, and the name of the program followed
997 by \ampi{} options (such as number of chunks to create, and the stack size of
998 every chunk) and the program arguments. A typical invocation of \ampi{} program
999 \texttt{pgm} with \texttt{charmrun} is:
1000
1001 \begin{alltt}
1002 > charmrun pgm +p16 +vp32 +tcharm_stacksize 3276800
1003 \end{alltt}
1004
1005 Here, the \ampi{} program \texttt{pgm} is run on 16 physical processors with
1006 32 chunks (which will be mapped 2 per processor initially), where each
1007 user-level thread associated with a chunk has the stack size of 3,276,800 bytes.
1008
1009 \end{document}