6230b0ac6905b2995672e038fff99c14783e4fb7
[charm.git] / doc / charm++ / manual.rst
1 ==============================================
2 The Charm++ Parallel Programming System Manual
3 ==============================================
4
5 .. contents::
6    :depth: 3
7
8
9 Basic Concepts
10 ==============
11
12 Charm++ is a C++-based parallel programming system, founded on the
13 migratable-objects programming model, and supported by a novel and
14 powerful adaptive runtime system. It supports both irregular as well as
15 regular applications, and can be used to specify task-parallelism as
16 well as data parallelism in a single application. It automates dynamic
17 load balancing for task-parallel as well as data-parallel applications,
18 via separate suites of load-balancing strategies. Via its message-driven
19 execution model, it supports automatic latency tolerance, modularity and
20 parallel composition. Charm++ also supports automatic
21 checkpoint/restart, as well as fault tolerance based on distributed
22 checkpoints.
23
24 Charm++ is a production-quality parallel programming system used by
25 multiple applications in science and engineering on supercomputers as
26 well as smaller clusters around the world. Currently the parallel
27 platforms supported by Charm++ are the IBM BlueGene/Q and OpenPOWER
28 systems, Cray XE, XK, and XC systems, Omni-Path and Infiniband clusters,
29 single workstations and networks of workstations (including x86 (running
30 Linux, Windows, MacOS)), etc. The communication protocols and
31 infrastructures supported by Charm++ are UDP, MPI, OFI, Infiniband,
32 uGNI, and PAMI. Charm++ programs can run without changing the source on
33 all these platforms. Charm++ programs can also interoperate with MPI
34 programs (§ :numref:`sec:interop`). Please see the Installation and Usage
35 section for details about installing, compiling and running Charm++
36 programs (§ :numref:`sec:install`).
37
38 Programming Model
39 -----------------
40
41 The key feature of the migratable-objects programming model is
42 *over-decomposition*: The programmer decomposes the program into a large
43 number of work units and data units, and specifies the computation in
44 terms of creation of and interactions between these units, without any
45 direct reference to the processor on which any unit resides. This
46 empowers the runtime system to assign units to processors, and to change
47 the assignment at runtime as necessary. Charm++ is the main (and early)
48 exemplar of this programming model. AMPI is another example within the
49 Charm++ family of the same model.
50
51 .. _mainchare:
52
53 Execution Model
54 ---------------
55
56 A basic unit of parallel computation in Charm++ programs is a *chare* .
57 A chare is similar to a process, an actor, an ADA task, etc. At its most
58 basic level, it is just a C++ object. A Charm++ computation consists of
59 a large number of chares distributed on available processors of the
60 system, and interacting with each other via asynchronous method
61 invocations. Asynchronously invoking a method on a remote object can
62 also be thought of as sending a “message” to it. So, these method
63 invocations are sometimes referred to as messages. (besides, in the
64 implementation, the method invocations are packaged as messages anyway).
65 Chares can be created dynamically.
66
67 Conceptually, the system maintains a “work-pool” consisting of seeds for
68 new chares, and messages for existing chares. The Charm++ runtime system
69 ( *Charm RTS*) may pick multiple items, non-deterministically, from this
70 pool and execute them, with the proviso that two different methods
71 cannot be simultaneously executing on the same chare object (say, on
72 different processors). Although one can define a reasonable theoretical
73 operational semantics of Charm++ in this fashion, a more practical
74 description of execution is useful to understand Charm++. A Charm++
75 application’s execution is distributed among Processing Elements (PEs),
76 which are OS threads or processes depending on the selected Charm++
77 build options. (See section :numref:`sec:machine` for a
78 precise description.) On each PE, there is a scheduler operating with
79 its own private pool of messages. Each instantiated chare has one PE
80 which is where it currently resides. The pool on each PE includes
81 messages meant for Chares residing on that PE, and seeds for new Chares
82 that are tentatively meant to be instantiated on that PE. The scheduler
83 picks a message, creates a new chare if the message is a seed (i.e. a
84 constructor invocation) for a new Chare, and invokes the method
85 specified by the message. When the method returns control back to the
86 scheduler, it repeats the cycle. I.e. there is no pre-emptive scheduling
87 of other invocations.
88
89 When a chare method executes, it may create method invocations for other
90 chares. The Charm Runtime System (RTS, sometimes referred to as the
91 Chare Kernel in the manual) locates the PE where the targeted chare
92 resides, and delivers the invocation to the scheduler on that PE.
93
94 Methods of a chare that can be remotely invoked are called *entry*
95 methods. Entry methods may take serializable parameters, or a pointer to
96 a message object. Since chares can be created on remote processors,
97 obviously some constructor of a chare needs to be an entry method.
98 Ordinary entry methods [1]_ are completely non-preemptive- Charm++ will
99 not interrupt an executing method to start any other work, and all calls
100 made are asynchronous.
101
102 Charm++ provides dynamic seed-based load balancing. Thus location
103 (processor number) need not be specified while creating a remote chare.
104 The Charm RTS will then place the remote chare on a suitable processor.
105 Thus one can imagine chare creation as generating only a seed for the
106 new chare, which may *take root* on some specific processor at a later
107 time.
108
109 Chares can be grouped into collections. The types of collections of
110 chares supported in Charm++ are: *chare-arrays*, *chare-groups*, and
111 *chare-nodegroups*, referred to as *arrays*, *groups*, and *nodegroups*
112 throughout this manual for brevity. A Chare-array is a collection of an
113 arbitrary number of migratable chares, indexed by some index type, and
114 mapped to processors according to a user-defined map group. A group
115 (nodegroup) is a collection of chares, with exactly one member element
116 on each PE (“node”).
117
118 Charm++ does not allow global variables, except readonly variables (see
119 :numref:`readonly`). A chare can normally only access its own data
120 directly. However, each chare is accessible by a globally valid name.
121 So, one can think of Charm++ as supporting a *global object space*.
122
123 Every Charm++ program must have at least one mainchare. Each mainchare
124 is created by the system on processor 0 when the Charm++ program starts
125 up. Execution of a Charm++ program begins with the Charm Kernel
126 constructing all the designated mainchares. For a mainchare named X,
127 execution starts at constructor X() or X(CkArgMsg \*) which are
128 equivalent. Typically, the mainchare constructor starts the computation
129 by creating arrays, other chares, and groups. It can also be used to
130 initialize shared readonly objects.
131
132 Charm++ program execution is terminated by the CkExit call. Like the
133 exit system call, CkExit never returns, and it optionally accepts an
134 integer value to specify the exit code that is returned to the calling
135 shell. If no exit code is specified, a value of zero (indicating
136 successful execution) is returned. The Charm RTS ensures that no more
137 messages are processed and no entry methods are called after a CkExit.
138 CkExit need not be called on all processors; it is enough to call it
139 from just one processor at the end of the computation.
140
141 As described so far, the execution of individual Chares is “reactive”:
142 When method A is invoked the chare executes this code, and so on. But
143 very often, chares have specific life-cycles, and the sequence of entry
144 methods they execute can be specified in a structured manner, while
145 allowing for some localized non-determinism (e.g. a pair of methods may
146 execute in any order, but when they both finish, the execution continues
147 in a pre-determined manner, say executing a 3rd entry method). To
148 simplify expression of such control structures, Charm++ provides two
149 methods: the structured dagger notation (Sec :numref:`sec:sdag`), which
150 is the main notation we recommend you use. Alternatively, you may use
151 threaded entry methods, in combination with *futures* and *sync* methods
152 (See :numref:`threaded`). The threaded methods run in light-weight
153 user-level threads, and can block waiting for data in a variety of ways.
154 Again, only the particular thread of a particular chare is blocked,
155 while the PE continues executing other chares.
156
157 The normal entry methods, being asynchronous, are not allowed to return
158 any value, and are declared with a void return type. However, the *sync*
159 methods are an exception to this. They must be called from a threaded
160 method, and so are allowed to return (certain types of) values.
161
162 .. _proxies:
163
164 Proxies and the charm interface file
165 ------------------------------------
166
167 To support asynchronous method invocation and global object space, the
168 RTS needs to be able to serialize (“marshall”) the parameters, and be
169 able to generate global “names” for chares. For this purpose,
170 programmers have to declare the chare classes and the signature of their
171 entry methods in a special “``.ci``” file, called an interface file.
172 Other than the interface file, the rest of a Charm++ program consists of
173 just normal C++ code. The system generates several classes based on the
174 declarations in the interface file, including “Proxy” classes for each
175 chare class. Those familiar with various component models (such as
176 CORBA) in the distributed computing world will recognize “proxy” to be a
177 dummy, standin entity that refers to an actual entity. For each chare
178 type, a “proxy” class exists. The methods of this “proxy” class
179 correspond to the remote methods of the actual class, and act as
180 “forwarders”. That is, when one invokes a method on a proxy to a remote
181 object, the proxy marshalls the parameters into a message, puts adequate
182 information about the target chare on the envelope of the message, and
183 forwards it to the remote object. Individual chares, chare array,
184 groups, node-groups, as well as the individual elements of these
185 collections have a such a proxy. Multiple methods for obtaining such
186 proxies are described in the manual. Proxies for each type of entity in
187 Charm++ have some differences among the features they support, but the
188 basic syntax and semantics remain the same - that of invoking methods on
189 the remote object by invoking methods on proxies.
190
191 The following sections provide detailed information about various
192 features of the Charm++ programming system. Part I, “Basic Usage”, is
193 sufficient for writing full-fledged applications. Note that only the
194 last two chapters of this part involve the notion of physical processors
195 (cores, nodes, ..), with the exception of simple query-type utilities
196 (Sec :numref:`basic utility fns`). We strongly suggest that all
197 application developers, beginners and experts alike, try to stick to the
198 basic language to the extent possible, and use features from the
199 advanced sections only when you are convinced they are essential. (They
200 are useful in specific situations; but a common mistake we see when we
201 examine programs written by beginners is the inclusion of complex
202 features that are not necessary for their purpose. Hence the caution).
203 The advanced concepts in the Part II of the manual support
204 optimizations, convenience features, and more complex or sophisticated
205 features.  [2]_
206
207 .. _machineModel:
208 .. _sec:machine:
209
210 Machine Model
211 -------------
212
213 At its basic level, Charm++ machine model is very simple:
214 Think of each chare as a separate processor by itself. The methods of
215 each chare can access its own instance variables (which are all private,
216 at this level), and any global variables declared as *readonly*. It also
217 has access to the names of all other chares (the “global object space”),
218 but all that it can do with that is to send asynchronous remote method
219 invocations towards other chare objects. (Of course, the instance
220 variables can include as many other regular C++ objects that it “has”;
221 but no chare objects. It can only have references to other chare
222 objects).
223
224 In accordance with this vision, the first part of the manual (up to and
225 including the chapter on load balancing) has almost no mention of
226 entities with physical meanings (cores, nodes, etc.). The runtime system
227 is responsible for the magic of keeping closely communicating objects on
228 nearby physical locations, and optimizing communications within chares
229 on the same node or core by exploiting the physically available shared
230 memory. The programmer does not have to deal with this at all. The only
231 exception to this pure model in the basic part are the functions used
232 for finding out which “processor” an object is running on, and for
233 finding how many total processors are there.
234
235 However, for implementing lower level libraries, and certain
236 optimizations, programmers need to be aware of processors. In any case,
237 it is useful to understand how the Charm++ implementation works under
238 the hood. So, we describe the machine model, and some associated
239 terminology here.
240
241 In terms of physical resources, we assume the parallel machine consists
242 of one or more *nodes*, where a node is a largest unit over which cache
243 coherent shared memory is feasible (and therefore, the maximal set of
244 cores per which a single process *can* run. Each node may include one or
245 more processor chips, with shared or private caches between them. Each
246 chip may contain multiple cores, and each core may support multiple
247 hardware threads (SMT for example).
248
249 Charm++ recognizes two logical entities: a PE (processing element) and a
250 logical node, or simply “node”. In a Charm++ program, a PE is a unit of
251 mapping and scheduling: each PE has a scheduler with an associated pool
252 of messages. Each chare is assumed to reside on one PE at a time. A
253 logical node is implemented as an OS process. In non-SMP mode there is
254 no distinction between a PE and a logical node. Otherwise, a PE takes
255 the form of an OS thread, and a logical node may contain one or more
256 PEs. Physical nodes may be partitioned into one or more logical nodes.
257 Since PEs within a logical node share the same memory address space, the
258 Charm++ runtime system optimizes communication between them by using
259 shared memory. Depending on the runtime command-line parameters, a PE
260 may optionally be associated with a subset of cores or hardware threads.
261
262 A Charm++ program can be launched with one or more (logical) nodes per
263 physical node. For example, on a machine with a four-core processor,
264 where each core has two hardware threads, common configurations in
265 non-SMP mode would be one node per core (four nodes/PEs total) or one
266 node per hardware thread (eight nodes/PEs total). In SMP mode, the most
267 common choice to fully subscribe the physical node would be one logical
268 node containing *seven* PEs-one OS thread is set aside per process for
269 network communications. (When built in the “multicore” mode that lacks
270 network support, a comm thread is unnecessary, and eight PEs can be used
271 in this case. A comm thread is also omitted when using some
272 high-performance network layers such as PAMI.) Alternatively, one can
273 choose to partition the physical node into multiple logical nodes, each
274 containing multiple PEs. One example would be *three* PEs per logical
275 node and two logical nodes per physical node, again reserving a comm
276 thread per logical node.
277
278 It is not a general practice in Charm++ to oversubscribe the underlying
279 physical cores or hardware threads on each node. In other words, a
280 Charm++ program is usually not launched with more PEs than there are
281 physical cores or hardware threads allocated to it. More information
282 about these launch time options are provided in
283 Appendix :numref:`sec:run`. And utility functions to retrieve the
284 information about those Charm++ logical machine entities in user
285 programs can be referred in section :numref:`basic utility fns`.
286
287 Basic Charm++ Programming
288 =========================
289
290 Program Structure, Compilation and Utilities
291 --------------------------------------------
292
293 A Charm++ program is essentially a C++ program where some components
294 describe its parallel structure. Sequential code can be written using
295 any programming technologies that cooperate with the C++ toolchain. This
296 includes C and Fortran. Parallel entities in the user’s code are written
297 in C++. These entities interact with the Charm++ framework via inherited
298 classes and function calls.
299
300 Charm++ Interface (.ci) Files
301 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
302
303 All user program components that comprise its parallel interface (such
304 as messages, chares, entry methods, etc.) are granted this elevated
305 status by declaring them in separate *charm++ interface* description
306 files. These files have a *.ci* suffix and adopt a C++-like declaration
307 syntax with several additional keywords. In some declaration contexts,
308 they may also contain some sequential C++ source code. Charm++ parses
309 these interface descriptions and generates C++ code (base classes, utility
310 classes, wrapper functions etc.) that facilitates the interaction of the
311 user program’s entities with the framework. A program may have several
312 interface description files.
313
314 Syntax Highlighting of .ci Files
315 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
316
317 Vim
318 '''
319
320 To enable syntax highlighting of .ci files in Vim, do the following:
321
322 .. code-block:: bash
323
324    $ cp charm/contrib/ci.vim ~/.vim/syntax/.
325    $ vim ~/.vim/filetype.vim
326
327 And paste the following line in that file:
328
329 .. code-block:: vim
330
331    au! BufRead,BufNewFile *.ci set filetype=ci
332
333 Sublime Text
334 ''''''''''''
335
336 Syntax highlighting in Sublime Text (version 3 or newer) can be enabled
337 by installing the *Charmci* package through Package Control.
338
339 Emacs
340 '''''
341
342 Syntax highlighting in Emacs can be enabled by triggering C++ handling on the .ci file extension by adding the following line to your .emacs file.
343
344 .. code-block:: emacs
345
346    (add-to-list 'auto-mode-alist '("\\.ci\\'" . c++-mode))
347
348 Modules
349 ~~~~~~~
350
351 The top-level construct in a *ci* file is a named container for
352 interface declarations called a *module*. Modules allow related
353 declarations to be grouped together, and cause generated code for these
354 declarations to be grouped into files named after the module. Modules
355 cannot be nested, but each *ci* file can have several modules. Modules
356 are specified using the keyword *module*. A module name must be a valid
357 C++ identifier.
358
359 ::
360
361    module myFirstModule {
362        // Parallel interface declarations go here
363        ...
364    };
365
366 Generated Files
367 ~~~~~~~~~~~~~~~
368
369 Each module present in a *ci* file is parsed to generate two files. The
370 basename of these files is the same as the name of the module and their
371 suffixes are *.decl.h* and *.def.h*. For e.g., the module defined
372 earlier will produce the files “myFirstModule.decl.h” and
373 “myFirstModule.def.h”. As the suffixes indicate, they contain the
374 declarations and definitions respectively, of all the classes and
375 functions that are generated based on the parallel interface
376 description.
377
378 We recommend that the header file containing the declarations (decl.h)
379 be included at the top of the files that contain the declarations or
380 definitions of the user program entities mentioned in the corresponding
381 module. The def.h is not actually a header file because it contains
382 definitions for the generated entities. To avoid multiple definition
383 errors, it should be compiled into just one object file. A convention we
384 find useful is to place the def.h file at the bottom of the source file
385 (.C, .cpp, .cc etc.) which includes the definitions of the corresponding
386 user program entities.
387
388 It should be noted that the generated files have no dependence on the
389 name of the *ci* file, but only on the names of the modules. This can
390 make automated dependency-based build systems slightly more complicated.
391
392 Module Dependencies
393 ~~~~~~~~~~~~~~~~~~~
394
395 A module may depend on the parallel entities declared in another module.
396 It can express this dependency using the *extern* keyword. *extern* ed
397 modules do not have to be present in the same *ci* file.
398
399 ::
400
401    module mySecondModule {
402
403        // Entities in this module depend on those declared in another module
404        extern module myFirstModule;
405
406        // More parallel interface declarations
407        ...
408    };
409
410 The *extern* keyword places an include statement for the decl.h file of
411 the *extern* ed module in the generated code of the current module. Hence,
412 decl.h files generated from *extern* ed modules are required during the
413 compilation of the source code for the current module. This is usually
414 required anyway because of the dependencies between user program
415 entities across the two modules.
416
417 The Main Module and Reachable Modules
418 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
419
420 Charm++ software can contain several module definitions from several
421 independently developed libraries / components. However, the user
422 program must specify exactly one module as containing the starting point
423 of the program’s execution. This module is called the *mainmodule*. Every
424 Charm++ program has to contain precisely one *mainmodule*.
425
426 All modules that are “reachable” from the *mainmodule* via a chain of
427 *extern* ed module dependencies are included in a Charm++ program. More
428 precisely, during program execution, the Charm++ runtime system will
429 recognize only the user program entities that are declared in reachable
430 modules. The decl.h and def.h files may be generated for other modules,
431 but the runtime system is not aware of entities declared in such
432 unreachable modules.
433
434 ::
435
436    module A {
437        ...
438    };
439
440    module B {
441        extern module A;
442        ...
443    };
444
445    module C {
446        extern module A;
447        ...
448    };
449
450    module D {
451        extern module B;
452        ...
453    };
454
455    module E {
456        ...
457    };
458
459    mainmodule M {
460        extern module C;
461        extern module D;
462        // Only modules A, B, C and D are reachable and known to the runtime system
463        // Module E is unreachable via any chain of externed modules
464        ...
465    };
466
467 Including other headers
468 ~~~~~~~~~~~~~~~~~~~~~~~
469
470 There can be occasions where code generated from the module definitions
471 requires other declarations / definitions in the user program’s
472 sequential code. Usually, this can be achieved by placing such user code
473 before the point of inclusion of the decl.h file. However, this can
474 become laborious if the decl.h file has to included in several places.
475 Charm++ supports the keyword *include* in *ci* files to permit the
476 inclusion of any header directly into the generated decl.h files.
477
478 ::
479
480    module A {
481        include "myUtilityClass.h"; //< Note the semicolon
482        // Interface declarations that depend on myUtilityClass
483        ...
484    };
485
486    module B {
487        include "someUserTypedefs.h";
488        // Interface declarations that require user typedefs
489        ...
490    };
491
492    module C {
493        extern module A;
494        extern module B;
495        // The user includes will be indirectly visible here too
496        ...
497    };
498
499 The main() function
500 ~~~~~~~~~~~~~~~~~~~
501
502 The Charm++ framework implements its own main function and
503 retains control until the parallel execution environment is initialized
504 and ready for executing user code. Hence, the user program must not
505 define a *main()* function. Control enters the user code via the
506 *mainchare* of the *mainmodule*. This will be discussed in further detail
507 in :numref:`mainchare`.
508
509 Using the facilities described thus far, the parallel interface
510 declarations for a Charm++ program can be spread across multiple ci
511 files and multiple modules, permitting good control over the grouping
512 and export of parallel API. This aids the encapsulation of parallel
513 software.
514
515 Compiling Charm++ Programs
516 ~~~~~~~~~~~~~~~~~~~~~~~~~~
517
518 Charm++ provides a compiler-wrapper called *charmc* that handles all *ci*,
519 C, C++ and Fortran source files that are part of a user program. Users can
520 invoke charmc to parse their interface descriptions, compile source code
521 and link objects into binaries. It also links against the appropriate
522 set of charm framework objects and libraries while producing a binary.
523 *charmc* and its functionality is described in :numref:`sec:compile`.
524
525 .. _basic utility fns:
526
527 Utility Functions
528 ~~~~~~~~~~~~~~~~~
529
530 The following calls provide basic rank information and utilities useful
531 when running a Charm++ program.
532
533 ``void CkAssert(int expression)``
534 Aborts the program if expression is 0.
535
536 ``void CkAbort(const char \*message)``
537 Causes the program to abort, printing
538 the given error message. This function never returns.
539
540 ``void CkExit()``
541 This call informs the Charm RTS that computation on all
542 processors should terminate. This routine never returns, so any code
543 after the call to CkExit() inside the function that calls it will not
544 execute. Other processors will continue executing until they receive
545 notification to stop, so it is a good idea to ensure through
546 synchronization that all useful work has finished before calling
547 CkExit().
548
549 ``double CkWallTimer()``
550 Returns the elapsed wall time since the start of execution.
551
552 Information about Logical Machine Entities
553 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
554
555 As described in section :numref:`machineModel`, Charm++ recognizes
556 two logical machine entities: “node” and PE (processing element). The
557 following functions provide basic information about such logical machine
558 that a Charm++ program runs on. PE and “node” are numbered starting from
559 zero.
560
561 ``int CkNumPes()``
562 Returns the total number of PEs across all nodes.
563
564 ``int CkMyPe()``
565 Returns the index of the PE on which the call was made.
566
567 ``int CkNumNodes()``
568 Returns the total number of logical Charm++ nodes.
569
570 ``int CkMyNode()``
571 Returns the index of the “node” on which the call was
572 made.
573
574 ``int CkMyRank()``
575 Returns the rank number of the PE on a “node” on which
576 the call was made. PEs within a “node” are also ranked starting from
577 zero.
578
579 ``int CkNodeFirst(int nd)``
580 Returns the index of the first PE on the logical
581 node :math:`nd`.
582
583 ``int CkNodeSize(int nd)``
584 Returns the number of PEs on the logical node
585 :math:`nd` on which the call was made.
586
587 ``int CkNodeOf(int pe)``
588 Returns the “node” number that PE :math:`pe`
589 belongs to.
590
591 ``int CkRankOf(int pe)``
592 Returns the rank of the given PE within its node.
593
594 Terminal I/O
595 ^^^^^^^^^^^^
596
597 Charm++ provides both C and C++ style methods of doing terminal I/O.
598
599 In place of C-style printf and scanf, Charm++ provides CkPrintf and
600 CkScanf. These functions have interfaces that are identical to their C
601 counterparts, but there are some differences in their behavior that
602 should be mentioned.
603
604 Charm++ also supports all forms of printf, cout, etc. in addition to the
605 special forms shown below. The special forms below are still useful,
606 however, since they obey well-defined (but still lax) ordering
607 requirements.
608
609 ``int CkPrintf(format [, arg]*)``
610 This call is used for atomic terminal
611 output. Its usage is similar to ``printf`` in C. However, CkPrintf has
612 some special properties that make it more suited for parallel
613 programming. CkPrintf routes all terminal output to a single end point
614 which prints the output. This guarantees that the output for a single
615 call to CkPrintf will be printed completely without being interleaved
616 with other calls to CkPrintf. Note that CkPrintf is implemented using an
617 asynchronous send, meaning that the call to CkPrintf returns immediately
618 after the message has been sent, and most likely before the message has
619 actually been received, processed, and displayed. As such, there is no
620 guarantee of order in which the output for concurrent calls to CkPrintf
621 is printed. Imposing such an order requires proper synchronization
622 between the calls to CkPrintf in the parallel application.
623
624 ``void CkError(format [, arg]*))``
625 Like CkPrintf, but used to print error messages on stderr.
626
627 ``int CkScanf(format [, arg]*)``
628 This call is used for atomic terminal input. Its usage is similar to scanf in C. A call to CkScanf, unlike CkPrintf, blocks all execution on the processor it is called from, and returns only after all input has been retrieved.
629
630 For C++ style stream-based I/O, Charm++ offers ``ckout`` and ``ckerr`` in place of
631 ``cout`` and ``cerr``. The C++ streams and their Charm++ equivalents are related
632 in the same manner as printf and scanf are to ``CkPrintf`` and ``CkScanf``. The
633 Charm++ streams are all used through the same interface as the
634 C++ streams, and all behave in a slightly different way, just like C-style
635 I/O.
636
637 Basic Syntax
638 ------------
639
640 .. _entry:
641
642 Entry Methods
643 ~~~~~~~~~~~~~
644
645 Member functions in the user program which function as entry methods
646 have to be defined in public scope within the class definition. Entry
647 methods typically do not return data and have a “void” return type. An
648 entry method with the same name as its enclosing class is a constructor
649 entry method and is used to create or spawn chare objects during
650 execution. Class member functions are annotated as entry methods by
651 declaring them in the interface file as:
652
653 ::
654
655    entry void Entry1(parameters);
656
657 Parameters is either a list of serializable parameters, (e.g., “int i,
658 double x”), or a message type (e.g., “MyMessage \*msg”). Since
659 parameters get marshalled into a message before being sent across the
660 network, in this manual we use “message” to mean either a message type
661 or a set of marshalled parameters.
662
663 Messages are lower level, more efficient, more flexible to use than
664 parameter marshalling.
665
666 For example, a chare could have this entry method declaration in the
667 interface (``.ci``) file:
668
669 ::
670
671      entry void foo(int i,int k);
672
673 Then invoking foo(2,3) on the chare proxy will eventually invoke
674 foo(2,3) on the chare object.
675
676 Since Charm++ runs on distributed memory machines, we cannot pass an
677 array via a pointer in the usual C++ way. Instead, we must specify the
678 length of the array in the interface file, as:
679
680 ::
681
682      entry void bar(int n,double arr[n]);
683
684 Since C++ does not recognize this syntax, the array data must be passed to
685 the chare proxy as a simple pointer. The array data will be copied and
686 sent to the destination processor, where the chare will receive the copy
687 via a simple pointer again. The remote copy of the data will be kept
688 until the remote method returns, when it will be freed. This means any
689 modifications made locally after the call will not be seen by the remote
690 chare; and the remote chare’s modifications will be lost after the
691 remote method returns- Charm++ always uses call-by-value, even for
692 arrays and structures.
693
694 This also means the data must be copied on the sending side, and to be
695 kept must be copied again at the receive side. Especially for large
696 arrays, this is less efficient than messages, as described in the next
697 section.
698
699 Array parameters and other parameters can be combined in arbitrary ways,
700 as:
701
702 ::
703
704      entry void doLine(float data[n],int n);
705      entry void doPlane(float data[n*n],int n);
706      entry void doSpace(int n,int m,int o,float data[n*m*o]);
707      entry void doGeneral(int nd,int dims[nd],float data[product(dims,nd)]);
708
709 The array length expression between the square brackets can be any valid
710 C++ expression, including a fixed constant, and may depend in any manner
711 on any of the passed parameters or even on global functions or global
712 data. The array length expression is evaluated exactly once per
713 invocation, on the sending side only. Thus executing the doGeneral
714 method above will invoke the (user-defined) product function exactly
715 once on the sending processor.
716
717 Marshalling User-Defined Structures and Classes
718 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
719
720 The marshalling system uses the pup framework to copy data, meaning
721 every user class that is marshalled needs either a pup routine, a
722 “PUPbytes” declaration, or a working operator|. See the PUP description
723 in Section :numref:`sec:pup` for more details on these
724 routines.
725
726 Any user-defined types in the argument list must be declared before
727 including the “.decl.h” file. Any user-defined types must be fully
728 defined before the entry method declaration that consumes it. This is
729 typically done by including the header defining the type in the ``.ci``
730 file. Alternatively, one may define it before including the ``.decl.h``
731 file. As usual in C, it is often dramatically more efficient to pass a
732 large structure by reference than by value.
733
734 As an example, refer to the following code from
735 ``examples/charm++/PUP/HeapPUP``:
736
737 ::
738
739    // In HeapObject.h:
740
741    class HeapObject {
742     public:
743      int publicInt;
744
745      // ... other methods ...
746
747      void pup(PUP::er &p) {
748        // remember to pup your superclass if there is one
749        p|publicInt;
750        p|privateBool;
751        if (p.isUnpacking())
752          data = new float[publicInt];
753        PUParray(p, data, publicInt);
754      }
755
756     private:
757      bool privateBool;
758      float *data;
759    };
760
761    // In SimplePup.ci:
762
763    mainmodule SimplePUP {
764      include "HeapObject.h";
765
766      // ... other Chare declarations ...
767
768      array [1D] SimpleArray{
769        entry SimpleArray();
770        entry void acceptData(HeapObject &inData);
771      };
772    };
773
774    // In SimplePup.h:
775
776    #include "SimplePUP.decl.h"
777
778    // ... other definitions ...
779
780    class SimpleArray : public CBase_SimpleArray {
781     public:
782      void acceptData(HeapObject &inData) {
783        // ... code using marshalled parameter ...
784      }
785    };
786
787    // In SimplePup.C:
788
789    #include "SimplePUP.h"
790
791    main::main(CkArgMsg *m)
792    {
793      // normal object construction
794      HeapObject exampleObject(... parameters ...);
795
796      // normal chare array construction
797      CProxy_SimpleArray simpleProxy = CProxy_SimpleArray::ckNew(30);
798
799      // pass object to remote method invocation on the chare array
800      simpleProxy[29].acceptData(exampleObject);
801    }
802
803    #include "SimplePUP.def.h"
804
805 Chare Objects
806 ~~~~~~~~~~~~~
807
808 Chares are concurrent objects with methods that can be invoked remotely.
809 These methods are known as entry methods. All chares must have a
810 constructor that is an entry method, and may have any number of other
811 entry methods. All chare classes and their entry methods are declared in
812 the interface (``.ci``) file:
813
814 ::
815
816        chare ChareType
817        {
818            entry ChareType(parameters1);
819            entry void EntryMethodName(parameters2);
820        };
821
822 Although it is *declared* in an interface file, a chare is a C++ object
823 and must have a normal C++ *implementation* (definition) in addition. A
824 chare class ``ChareType`` must inherit from the class
825 ``CBase_ChareType``, which is a special class that is generated by the
826 Charm++ translator from the interface file. Note that C++ namespace
827 constructs can be used in the interface file, as demonstrated in
828 ``examples/charm++/namespace``.
829
830 To be concrete, the C++ definition of the chare above might have the
831 following definition in a ``.h`` file:
832
833 ::
834
835       class ChareType : public CBase_ChareType {
836           // Data and member functions as in C++
837           public:
838               ChareType(parameters1);
839               void EntryMethodName2(parameters2);
840       };
841
842 Each chare encapsulates data associated with medium-grained units of
843 work in a parallel application. Chares can be dynamically created on any
844 processor; there may be thousands of chares on a processor. The location
845 of a chare is usually determined by the dynamic load balancing strategy.
846 However, once a chare commences execution on a processor, it does not
847 migrate to other processors [3]_. Chares do not have a default “thread
848 of control”: the entry methods in a chare execute in a message driven
849 fashion upon the arrival of a message [4]_.
850
851 The entry method definition specifies a function that is executed
852 *without interruption* when a message is received and scheduled for
853 processing. Only one message per chare is processed at a time. Entry
854 methods are defined exactly as normal C++ function members, except that
855 they must have the return value void (except for the constructor entry
856 method which may not have a return value, and for a *synchronous* entry
857 method, which is invoked by a *threaded* method in a remote chare). Each
858 entry method can either take no arguments, take a list of arguments that
859 the runtime system can automatically pack into a message and send (see
860 section :numref:`entry`), or take a single argument that is a pointer
861 to a Charm++ message (see section :numref:`messages`).
862
863 A chare’s entry methods can be invoked via *proxies* (see
864 section :numref:`proxies`). Proxies to a chare of type ``chareType``
865 have type ``CProxy_chareType``. By inheriting from the CBase parent
866 class, each chare gets a ``thisProxy`` member variable, which holds a
867 proxy to itself. This proxy can be sent to other chares, allowing them
868 to invoke entry methods on this chare.
869
870 .. _chare creation:
871
872 Chare Creation
873 ^^^^^^^^^^^^^^
874
875 Once you have declared and defined a chare class, you will want to
876 create some chare objects to use. Chares are created by the ``ckNew``
877 method, which is a static method of the chare’s proxy class:
878
879 ::
880
881       CProxy_chareType::ckNew(parameters, int destPE);
882
883 The ``parameters`` correspond to the parameters of the chare’s
884 constructor. Even if the constructor takes several arguments, all of the
885 arguments should be passed in order to ``ckNew``. If the constructor
886 takes no arguments, the parameters are omitted. By default, the new
887 chare’s location is determined by the runtime system. However, this can
888 be overridden by passing a value for ``destPE``, which specifies the PE
889 where the chare will be created.
890
891 The chare creation method deposits the *seed* for a chare in a pool of
892 seeds and returns immediately. The chare will be created later on some
893 processor, as determined by the dynamic load balancing strategy (or by
894 ``destPE``). When a chare is created, it is initialized by calling its
895 constructor entry method with the parameters specified by ``ckNew``.
896
897 Suppose we have declared a chare class ``C`` with a constructor that
898 takes two arguments, an ``int`` and a ``double``.
899
900 #. This will create a new chare of type C on any processor and return a
901    proxy to that chare:
902
903    ::
904
905          CProxy_C chareProxy = CProxy_C::ckNew(1, 10.0);
906
907 #. This will create a new chare of type C on processor destPE and return
908    a proxy to that chare:
909
910    ::
911
912          CProxy_C chareProxy = CProxy_C::ckNew(1, 10.0, destPE);
913
914 For an example of chare creation in a full application, see
915 ``examples/charm++/fib`` in the Charm++ software distribution, which
916 calculates Fibonacci numbers in parallel.
917
918 Method Invocation on Chares
919 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
920
921 A message may be sent to a chare through a proxy object using the
922 notation:
923
924 ::
925
926        chareProxy.EntryMethod(parameters)
927
928 This invokes the entry method EntryMethod on the chare referred to by
929 the proxy chareProxy. This call is asynchronous and non-blocking; it
930 returns immediately after sending the message.
931
932 Local Access
933 ^^^^^^^^^^^^
934
935 You can get direct access to a local chare using the proxy’s ckLocal
936 method, which returns an ordinary C++ pointer to the chare if it exists on
937 the local processor, and NULL otherwise.
938
939 ::
940
941        C *c=chareProxy.ckLocal();
942        if (c==NULL) {
943            // object is remote; send message
944        } else {
945            // object is local; directly use members and methods of c
946        }
947
948 .. _readonly:
949
950 Read-only Data
951 ~~~~~~~~~~~~~~
952
953 Since Charm++ does not allow global variables, it provides a special
954 mechanism for sharing data amongst all objects. *Read-only* variables of
955 simple data types or compound data types including messages and arrays
956 are used to share information that is obtained only after the program
957 begins execution and does not change after they are initialized in the
958 dynamic scope of the ``main`` function of the mainchare. They are
959 broadcast to every Charm++ Node (process) by the Charm++ runtime, and
960 can be accessed in the same way as C++ “global” variables on any process.
961 Compound data structures containing pointers can be made available as
962 read-only variables using read-only messages(see
963 section :numref:`messages`) or read-only arrays(see
964 section :numref:`basic arrays`). Note that memory has to be
965 allocated for read-only messages by using new to create the message in
966 the ``main`` function of the mainchare.
967
968 Read-only variables are declared by using the type modifier readonly,
969 which is similar to const in C++. Read-only data is specified in the
970 ``.ci`` file (the interface file) as:
971
972 ::
973
974     readonly Type ReadonlyVarName;
975
976 The variable ReadonlyVarName is declared to be a read-only variable of
977 type Type. Type must be a single token and not a type expression.
978
979 ::
980
981     readonly message MessageType *ReadonlyMsgName;
982
983 The variable ReadonlyMsgName is declared to be a read-only message of
984 type MessageType. Pointers are not allowed to be readonly variables
985 unless they are pointers to message types. In this case, the message
986 will be initialized on every PE.
987
988 ::
989
990     readonly Type ReadonlyArrayName [arraysize];
991
992 The variable ReadonlyArrayName is declared to be a read-only array of
993 type Type with arraysize elements. Type must be a single token and not a
994 type expression. The value of arraysize must be known at compile time.
995
996 Read-only variables must be declared either as global or as public class
997 static data in the C/C++ implementation files, and these declarations have
998 the usual form:
999
1000 ::
1001
1002     Type ReadonlyVarName;
1003     MessageType *ReadonlyMsgName;
1004     Type ReadonlyArrayName [arraysize];
1005
1006 Similar declarations preceded by extern would appear in the ``.h`` file.
1007
1008 *Note:* The current Charm++ translator cannot prevent assignments to
1009 read-only variables. The user must make sure that no assignments occur
1010 in the program outside of the mainchare constructor.
1011
1012 For concrete examples for using read-only variables, please refer to
1013 examples such as ``examples/charm++/array`` and
1014 ``examples/charm++/gaussSeidel3D``.
1015
1016 Users can get the same functionality of readonly variables by making
1017 such variables members of Charm++ Node Group objects and constructing
1018 the Node Group in the mainchare’s main routine.
1019
1020 .. _basic arrays:
1021
1022 Chare Arrays
1023 ------------
1024
1025 Chare arrays are arbitrarily-sized, possibly-sparse collections of
1026 chares that are distributed across the processors. The entire array has
1027 a globally unique identifier of type CkArrayID, and each element has a
1028 unique index of type CkArrayIndex. A CkArrayIndex can be a single
1029 integer (i.e. a one-dimensional array), several integers (i.e. a
1030 multi-dimensional array), or an arbitrary string of bytes (e.g. a binary
1031 tree index).
1032
1033 Array elements can be dynamically created and destroyed on any PE,
1034 migrated between PEs, and messages for the elements will still arrive
1035 properly. Array elements can be migrated at any time, allowing arrays to
1036 be efficiently load balanced. A chare array (or a subset of array
1037 elements) can receive a broadcast/multicast or contribute to a
1038 reduction.
1039
1040 An example program can be found here: ``examples/charm++/array``.
1041
1042 Declaring a One-dimensional Array
1043 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1044
1045 You can declare a one-dimensional (1D) chare array as:
1046
1047 ::
1048
1049    //In the .ci file:
1050    array [1D] A {
1051      entry A(parameters1);
1052      entry void someEntry(parameters2);
1053    };
1054
1055 Array elements extend the system class CBase_ClassName, inheriting
1056 several fields:
1057
1058 -  thisProxy: the proxy to the entire chare array that can be indexed to
1059    obtain a proxy to a specific array element (e.g. for a 1D chare array
1060    thisProxy[10]; for a 2D chare array thisProxy(10, 20))
1061
1062 -  thisArrayID: the array’s globally unique identifier
1063
1064 -  thisIndex: the element’s array index (an array element can obtain a
1065    proxy to itself like this thisProxy[thisIndex])
1066
1067 ::
1068
1069    class A : public CBase_A {
1070      public:
1071        A(parameters1);
1072
1073        void someEntry(parameters2);
1074    };
1075
1076 Note that A must have a *migration constructor*, which is typically
1077 empty:
1078
1079 ::
1080
1081    //In the .C file:
1082    A::A(void)
1083    {
1084      //... constructor code ...
1085    }
1086
1087    A::someEntry(parameters2)
1088    {
1089      // ... code for someEntry ...
1090    }
1091
1092 See the section :numref:`arraymigratable` on migratable array
1093 elements for more information on the migration constructor that takes
1094 CkMigrateMessage \* as the argument.
1095
1096 Declaring Multi-dimensional Arrays
1097 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1098
1099 Charm++ supports multi-dimensional or user-defined indices. These array
1100 types can be declared as:
1101
1102 ::
1103
1104    //In the .ci file:
1105    array [1D]  ArrayA { entry ArrayA(); entry void e(parameters);}
1106    array [2D]  ArrayB { entry ArrayB(); entry void e(parameters);}
1107    array [3D]  ArrayC { entry ArrayC(); entry void e(parameters);}
1108    array [4D]  ArrayD { entry ArrayD(); entry void e(parameters);}
1109    array [5D]  ArrayE { entry ArrayE(); entry void e(parameters);}
1110    array [6D]  ArrayF { entry ArrayF(); entry void e(parameters);}
1111    array [Foo] ArrayG { entry ArrayG(); entry void e(parameters);}
1112    array [Bar<3>] ArrayH { entry ArrayH(); entry void e(parameters);}
1113
1114 The declaration of ArrayG expects an array index of type
1115 CkArrayIndexFoo, which must be defined before including the ``.decl.h``
1116 file (see section :numref:`user-defined array index type` on
1117 user-defined array indices for more information).
1118
1119 ::
1120
1121    //In the .h file:
1122    class ArrayA : public CBase_ArrayA { public: ArrayA(){} ...};
1123    class ArrayB : public CBase_ArrayB { public: ArrayB(){} ...};
1124    class ArrayC : public CBase_ArrayC { public: ArrayC(){} ...};
1125    class ArrayD : public CBase_ArrayD { public: ArrayD(){} ...};
1126    class ArrayE : public CBase_ArrayE { public: ArrayE(){} ...};
1127    class ArrayF : public CBase_ArrayF { public: ArrayF(){} ...};
1128    class ArrayG : public CBase_ArrayG { public: ArrayG(){} ...};
1129    class ArrayH : public CBase_ArrayH { public: ArrayH(){} ...};
1130
1131 The fields in thisIndex are different depending on the dimensionality of
1132 the chare array:
1133
1134 -  1D array: thisIndex
1135
1136 -  2D array (:math:`x`,\ :math:`y`): thisIndex.x, thisIndex.y
1137
1138 -  3D array (:math:`x`,\ :math:`y`,\ :math:`z`): thisIndex.x,
1139    thisIndex.y, thisIndex.z
1140
1141 -  4D array (:math:`w`,\ :math:`x`,\ :math:`y`,\ :math:`z`):
1142    thisIndex.w, thisIndex.x, thisIndex.y, thisIndex.z
1143
1144 -  5D array (:math:`v`,\ :math:`w`,\ :math:`x`,\ :math:`y`,\ :math:`z`):
1145    thisIndex.v, thisIndex.w, thisIndex.x, thisIndex.y, thisIndex.z
1146
1147 -  6D array
1148    (:math:`x_1`,\ :math:`y_1`,\ :math:`z_1`,\ :math:`x_2`,\ :math:`y_2`,\ :math:`z_2`):
1149    thisIndex.x1, thisIndex.y1, thisIndex.z1, thisIndex.x2, thisIndex.y2,
1150    thisIndex.z2
1151
1152 -  Foo array: thisIndex
1153
1154 -  Bar<3> array: thisIndex
1155
1156 .. _basic array creation:
1157
1158 Creating an Array
1159 ~~~~~~~~~~~~~~~~~
1160
1161 An array is created using the CProxy_Array::ckNew routine, which must be
1162 called from PE 0. To create an array from any PE, asynchronous array
1163 creation using a callback can be used. See
1164 section :numref:`asynchronous_array_creation` for asynchronous
1165 array creation. CProxy_Array::ckNew returns a proxy object, which can be
1166 kept, copied, or sent in messages. The following creates a 1D array
1167 containing elements indexed (0, 1, …, dimX-1):
1168
1169 ::
1170
1171    CProxy_ArrayA a1 = CProxy_ArrayA::ckNew(params, dimX);
1172
1173 Likewise, a dense multidimensional array can be created by passing the
1174 extents at creation time to ckNew.
1175
1176 ::
1177
1178    CProxy_ArrayB a2 = CProxy_ArrayB::ckNew(params, dimX, dimY);
1179    CProxy_ArrayC a3 = CProxy_ArrayC::ckNew(params, dimX, dimY, dimZ);
1180    CProxy_ArrayD a4 = CProxy_ArrayC::ckNew(params, dimW, dimX, dimY, dimZ);
1181    CProxy_ArrayE a5 = CProxy_ArrayC::ckNew(params, dimV, dimW, dimX, dimY, dimZ);
1182    CProxy_ArrayF a6 = CProxy_ArrayC::ckNew(params, dimX1, dimY1, dimZ1, dimX2, dimY2, dimZ2);
1183
1184 For user-defined arrays, this functionality cannot be used. The array
1185 elements must be inserted individually as described in
1186 section :numref:`dynamic_insertion`.
1187
1188 During creation, the constructor is invoked on each array element. For
1189 more options when creating the array, see
1190 section :numref:`advanced array create`.
1191
1192 Entry Method Invocation
1193 ~~~~~~~~~~~~~~~~~~~~~~~
1194
1195 To obtain a proxy to a specific element in chare array, the chare array
1196 proxy (e.g. thisProxy) must be indexed by the appropriate index call
1197 depending on the dimensionality of the array:
1198
1199 -  1D array, to obtain a proxy to element :math:`i`:
1200    thisProxy[:math:`i`] or thisProxy(\ :math:`i`)
1201
1202 -  2D array, to obtain a proxy to element :math:`(i,j)`:
1203    thisProxy(\ :math:`i`,\ :math:`j`)
1204
1205 -  3D array, to obtain a proxy to element :math:`(i,j,k)`:
1206    thisProxy(\ :math:`i`,\ :math:`j`,\ :math:`k`)
1207
1208 -  4D array, to obtain a proxy to element :math:`(i,j,k,l)`:
1209    thisProxy(\ :math:`i`,\ :math:`j`,\ :math:`k`,\ :math:`l`)
1210
1211 -  5D array, to obtain a proxy to element :math:`(i,j,k,l,m)`:
1212    thisProxy(\ :math:`i`,\ :math:`j`,\ :math:`k`,\ :math:`l`,\ :math:`m`)
1213
1214 -  6D array, to obtain a proxy to element :math:`(i,j,k,l,m,n)`:
1215    thisProxy(\ :math:`i`,\ :math:`j`,\ :math:`k`,\ :math:`l`,\ :math:`m`,\ :math:`n`)
1216
1217 -  User-defined array, to obtain a proxy to element :math:`i`:
1218    thisProxy[:math:`i`] or thisProxy(\ :math:`i`)
1219
1220 To send a message to an array element, index the proxy and call the
1221 method name:
1222
1223 ::
1224
1225    a1[i].doSomething(parameters);
1226    a3(x,y,z).doAnother(parameters);
1227    aF[CkArrayIndexFoo(...)].doAgain(parameters);
1228
1229 You may invoke methods on array elements that have not yet been created.
1230 The Charm++ runtime system will buffer the message until the element is
1231 created.  [5]_
1232
1233 Messages are not guaranteed to be delivered in order. For instance, if a
1234 method is invoked on method A and then method B; it is possible that B
1235 is executed before A.
1236
1237 ::
1238
1239    a1[i].A();
1240    a1[i].B();
1241
1242 Messages sent to migrating elements will be delivered after the
1243 migrating element arrives on the destination PE. It is an error to send
1244 a message to a deleted array element.
1245
1246 Broadcasts on Chare Arrays
1247 ~~~~~~~~~~~~~~~~~~~~~~~~~~
1248
1249 To broadcast a message to all the current elements of an array, simply
1250 omit the index (invoke an entry method on the chare array proxy):
1251
1252 ::
1253
1254    a1.doIt(parameters); //<- invokes doIt on each array element
1255
1256 The broadcast message will be delivered to every existing array element
1257 exactly once. Broadcasts work properly even with ongoing migrations,
1258 insertions, and deletions.
1259
1260 .. _reductions:
1261
1262 Reductions on Chare Arrays
1263 ~~~~~~~~~~~~~~~~~~~~~~~~~~
1264
1265 A reduction applies a single operation (e.g. add, max, min, ...) to data
1266 items scattered across many processors and collects the result in one
1267 place. Charm++ supports reductions over the members of an array or
1268 group.
1269
1270 The data to be reduced comes from a call to the member contribute
1271 method:
1272
1273 ::
1274
1275    void contribute(int nBytes, const void *data, CkReduction::reducerType type);
1276
1277 This call contributes nBytes bytes starting at data to the reduction
1278 type (see Section :numref:`builtin_reduction`). Unlike sending a
1279 message, you may use data after the call to contribute. All members of
1280 the chare array or group must call contribute, and all of them must use
1281 the same reduction type.
1282
1283 For example, if we want to sum each array/group member’s single integer
1284 myInt, we would use:
1285
1286 ::
1287
1288        // Inside any member method
1289        int myInt=get_myInt();
1290        contribute(sizeof(int),&myInt,CkReduction::sum_int);
1291
1292 The built-in reduction types (see below) can also handle arrays of
1293 numbers. For example, if each element of a chare array has a pair of
1294 doubles forces[2], the corresponding elements of which are to be added
1295 across all elements, from each element call:
1296
1297 ::
1298
1299        double forces[2]=get_my_forces();
1300        contribute(2*sizeof(double),forces,CkReduction::sum_double);
1301
1302 Note that since C++ arrays (like forces[2]) are already pointers, we
1303 don’t use &forces.
1304
1305 A slightly simpler interface is available for ``std::vector<T>``, since
1306 the class determines the size and count of the underlying type:
1307
1308 ::
1309
1310        CkCallback cb(...);
1311        vector<double> forces(2);
1312        get_my_forces(forces);
1313        contribute(forces, CkReduction::sum_double, cb);
1314
1315 Either of these will result in a ``double`` array of 2 elements, the
1316 first of which contains the sum of all forces[0] values, with the second
1317 element holding the sum of all forces[1] values of the chare array
1318 elements.
1319
1320 Typically the client entry method of a reduction takes a single argument
1321 of type CkReductionMsg (see Section :numref:`reductionClients`).
1322 However, by giving an entry method the reductiontarget attribute in the
1323 ``.ci`` file, you can instead use entry methods that take arguments of
1324 the same type as specified by the *contribute* call. When creating a
1325 callback to the reduction target, the entry method index is generated by
1326 ``CkReductionTarget(ChareClass, method_name)`` instead of
1327 ``CkIndex_ChareClass::method_name(...)``. For example, the code for a
1328 typed reduction that yields an ``int``, would look like this:
1329
1330 ::
1331
1332      // In the .ci file...
1333      entry [reductiontarget] void done(int result);
1334
1335      // In some .C file:
1336      // Create a callback that invokes the typed reduction client
1337      // driverProxy is a proxy to the chare object on which
1338      // the reduction target method "done" is called upon completion
1339      // of the reduction
1340      CkCallback cb(CkReductionTarget(Driver, done), driverProxy);
1341
1342      // Contribution to the reduction...
1343      contribute(sizeof(int), &intData, CkReduction::sum_int, cb);
1344
1345      // Definition of the reduction client...
1346      void Driver::done(int result)
1347      {
1348        CkPrintf("Reduction value: %d", result);
1349      }
1350
1351 This will also work for arrays of data
1352 elements(\ ``entry [reductiontarget] void done(int n, int result[n])``),
1353 and for any user-defined type with a PUP method (see
1354 :numref:`sec:pup`). If you know that the reduction will yield a
1355 particular number of elements, say 3 ``int``\ s, you can also specify a
1356 reduction target which takes 3 ``int``\ s and it will be invoked
1357 correctly.
1358
1359 Reductions do not have to specify commutative-associative operations on
1360 data; they can also be used to signal the fact that all array/group
1361 members have reached a certain synchronization point. In this case, a
1362 simpler version of contribute may be used:
1363
1364 ::
1365
1366        contribute();
1367
1368 In all cases, the result of the reduction operation is passed to the
1369 *reduction client*. Many different kinds of reduction clients can be
1370 used, as explained in Section :numref:`reductionClients`.
1371
1372 Please refer to ``examples/charm++/reductions/typed_reduction`` for a
1373 working example of reductions in Charm++.
1374
1375 Note that the reduction will complete properly even if chare array
1376 elements are *migrated* or *deleted* during the reduction. Additionally,
1377 when you create a new chare array element, it is expected to contribute
1378 to the next reduction not already in progress on that processor.
1379
1380 .. _builtin_reduction:
1381
1382 Built-in Reduction Types
1383 ^^^^^^^^^^^^^^^^^^^^^^^^
1384
1385 Charm++ includes several built-in reduction types, used to combine
1386 individual contributions. Any of them may be passed as an argument of
1387 type CkReduction::reducerType to contribute.
1388
1389 The first four operations (``sum``, ``product``, ``max``, and ``min``)
1390 work on ``char``, ``short``, ``int``, ``long``, ``long long``,
1391 ``float``, or ``double`` data as indicated by the suffix. The logical
1392 reductions (``and``, ``or``) only work on bool and integer data. All the
1393 built-in reductions work on either single numbers (pass a pointer) or
1394 arrays- just pass the correct number of bytes to contribute.
1395
1396 #. CkReduction::nop : no operation performed.
1397
1398 #. CkReduction::sum_char, sum_short, sum_int, sum_long, sum_long_long,
1399    sum_uchar, sum_ushort, sum_uint, sum_ulong, sum_ulong_long,
1400    sum_float, sum_double : the result will be the sum of the given
1401    numbers.
1402
1403 #. CkReduction::product_char, product_short, product_int, product_long,
1404    product_long_long, product_uchar, product_ushort, product_uint,
1405    product_ulong, product_ulong_long, product_float, product_double :
1406    the result will be the product of the given numbers.
1407
1408 #. CkReduction::max_char, max_short, max_int, max_long, max_long_long,
1409    max_uchar, max_ushort, max_uint, max_ulong, max_ulong_long,
1410    max_float, max_double : the result will be the largest of the given
1411    numbers.
1412
1413 #. CkReduction::min_char, min_short, min_int, min_long, min_long_long,
1414    min_uchar, min_ushort, min_uint, min_ulong, min_ulong_long,
1415    min_float, min_double : the result will be the smallest of the given
1416    numbers.
1417
1418 #. CkReduction::logical_and_bool, logical_and_int : the result will be
1419    the logical AND of the given values.
1420
1421 #. CkReduction::logical_or_bool, logical_or_int : the result will be the
1422    logical OR of the given values.
1423
1424 #. CkReduction::logical_xor_bool, logical_xor_int : the result will be
1425    the logical XOR of the given values.
1426
1427 #. CkReduction::bitvec_and_bool, bitvec_and_int : the result will be the
1428    bitvector AND of the given values.
1429
1430 #. CkReduction::bitvec_or_bool, bitvec_or_int : the result will be the
1431    bitvector OR of the given values.
1432
1433 #. CkReduction::bitvec_xor_bool, bitvec_xor_int : the result will be the
1434    bitvector XOR of the given values.
1435
1436 #. CkReduction::set : the result will be a verbatim concatenation of all
1437    the contributed data, separated into CkReduction::setElement records.
1438    The data contributed can be of any length, and can vary across array
1439    elements or reductions. To extract the data from each element, see
1440    the description below.
1441
1442 #. CkReduction::concat : the result will be a byte-by-byte concatenation
1443    of all the contributed data. The contributed elements are not
1444    delimiter-separated.
1445
1446 #. CkReduction::random : the result will be a single randomly selected
1447    value of all of the contributed values.
1448
1449 #. CkReduction::statistics : returns a CkReduction::statisticsElement
1450    struct, containing summary statistics of the contributed data.
1451    Specifically, the struct contains the following fields: int count,
1452    double mean, and double m2, and the following functions: double
1453    variance() and double stddev().
1454
1455 CkReduction::set returns a collection of CkReduction::setElement
1456 objects, one per contribution. This class has the definition:
1457
1458 ::
1459
1460    class CkReduction::setElement
1461    {
1462    public:
1463      int dataSize; //The length of the `data' array in bytes.
1464      char data[1]; //A place holder that marks the start of the data array.
1465      CkReduction::setElement *next(void);
1466    };
1467
1468 Example: Suppose you would like to contribute 3 integers from each array
1469 element. In the reduction method you would do the following:
1470
1471 ::
1472
1473    void ArrayClass::methodName (CkCallback &cb)
1474    {
1475      int result[3];
1476      result[0] = 1;            // Copy the desired values into the result.
1477      result[1] = 2;
1478      result[2] = 3;
1479      // Contribute the result to the reductiontarget cb.
1480      contribute(3*sizeof(int), result, CkReduction::set, cb);
1481    }
1482
1483 Inside the reduction’s target method, the contributions can be accessed
1484 by using the ``CkReduction::setElement->next()`` iterator.
1485
1486 ::
1487
1488    void SomeClass::reductionTargetMethod (CkReductionMsg *msg)
1489    {
1490      // Get the initial element in the set.
1491      CkReduction::setElement *current = (CkReduction::setElement*) msg->getData();
1492      while(current != NULL) // Loop over elements in set.
1493      {
1494        // Get the pointer to the packed int's.
1495        int *result = (int*) &current->data;
1496        // Do something with result.
1497        current = current->next(); // Iterate.
1498      }
1499    }
1500
1501 The reduction set order is undefined. You should add a source field to
1502 the contributed elements if you need to know which array element gave a
1503 particular contribution. Additionally, if the contributed elements are
1504 of a complex data type, you will likely have to supply code for
1505 serializing/deserializing them. Consider using the PUP interface
1506 (§ :numref:`sec:pup`) to simplify your object serialization
1507 needs.
1508
1509 If the outcome of your reduction is dependent on the order in which data
1510 elements are processed, or if your data is just too heterogeneous to be
1511 handled elegantly by the predefined types and you don’t want to
1512 undertake multiple reductions, you can use a tuple reduction or define
1513 your own custom reduction type.
1514
1515 Tuple reductions allow performing multiple different reductions in the
1516 same message. The reductions can be on the same or different data, and
1517 the reducer type for each reduction can be set independently as well.
1518 The contributions that make up a single tuple reduction message are all
1519 reduced in the same order as each other. As an example, a chare array
1520 element can contribute to a gatherv-like operation using a tuple
1521 reduction that consists of two set reductions.
1522
1523 ::
1524
1525    int tupleSize = 2;
1526    CkReduction::tupleElement tupleRedn[] = {
1527      CkReduction::tupleElement(sizeof(int), &thisIndex, CkReduction::set),
1528      CkReduction::tupleElement(sizeData, data, CkReduction::set)
1529    };
1530    CkReductionMsg* msg = CkReductionMsg::buildFromTuple(tupleRedn, tupleSize);
1531    CkCallback allgathervCB(CkIndex_Foo::allgathervResult(0), thisProxy);
1532    msg->setCallback(allgathervCB);
1533    contribute(msg);
1534
1535 Note that ``CkReduction::tupleElement`` only holds pointers to the data that
1536 will make up the reduction message, therefore any local variables used must
1537 remain in scope until ``CkReductionMsg::buildFromTuple`` completes.
1538
1539 The result of this reduction is a single CkReductionMsg that can be
1540 processed as multiple reductions:
1541
1542 ::
1543
1544    void Foo::allgathervResult (CkReductionMsg* msg)
1545    {
1546      int numReductions;
1547      CkReduction::tupleElement* results;
1548
1549      msg->toTuple(&results, &numReductions);
1550      CkReduction::setElement* currSrc  = (CkReduction::setElement*)results[0].data;
1551      CkReduction::setElement* currData = (CkReduction::setElement*)results[1].data;
1552
1553      // ... process currSrc and currData
1554
1555      delete [] results;
1556    }
1557
1558 See the next section (Section :numref:`new_type_reduction`) for details
1559 on custom reduction types.
1560
1561 Destroying Array Elements
1562 ~~~~~~~~~~~~~~~~~~~~~~~~~
1563
1564 To destroy an array element - detach it from the array, call its
1565 destructor, and release its memory-invoke its Array destroy method, as:
1566
1567 ::
1568
1569    a1[i].ckDestroy();
1570
1571 Note that this method can also be invoked remotely i.e. from a process
1572 different from the one on which the array element resides. You must
1573 ensure that no messages are sent to a deleted element. After destroying
1574 an element, you may insert a new element at its index.
1575
1576 .. _sec:sdag:
1577
1578 Structured Control Flow: Structured Dagger
1579 ------------------------------------------
1580
1581 Charm++ is based on the message-driven parallel programming paradigm. In
1582 contrast to many other approaches, Charm++ programmers encode entry
1583 points to their parallel objects, but do not explicitly wait (i.e.
1584 block) on the runtime to indicate completion of posted ‘receive’
1585 requests. Thus, a Charm++ object’s overall flow of control can end up
1586 fragmented across a number of separate methods, obscuring the sequence
1587 in which code is expected to execute. Furthermore, there are often
1588 constraints on when different pieces of code should execute relative to
1589 one another, related to data and synchronization dependencies.
1590
1591 Consider one way of expressing these constraints using flags, buffers,
1592 and counters, as in the following example:
1593
1594 ::
1595
1596    // in .ci file
1597    chare ComputeObject {
1598      entry void ComputeObject();
1599      entry void startStep();
1600      entry void firstInput(Input i);
1601      entry void secondInput(Input j);
1602    };
1603
1604    // in C++ file
1605    class ComputeObject : public CBase_ComputeObject {
1606      int   expectedMessageCount;
1607      Input first, second;
1608
1609    public:
1610      ComputeObject() {
1611        startStep();
1612      }
1613      void startStep() {
1614        expectedMessageCount = 2;
1615      }
1616
1617      void firstInput(Input i) {
1618        first = i;
1619        if (--expectedMessageCount == 0)
1620          computeInteractions(first, second);
1621        }
1622      void recv_second(Input j) {
1623        second = j;
1624        if (--expectedMessageCount == 0)
1625          computeInteractions(first, second);
1626      }
1627
1628      void computeInteractions(Input a, Input b) {
1629        // do computations using a and b
1630        ...
1631        // send off results
1632        ...
1633        // reset for next step
1634        startStep();
1635      }
1636    };
1637
1638 In each step, this object expects pairs of messages, and waits to
1639 process the incoming data until it has both of them. This sequencing is
1640 encoded across 4 different functions, which in real code could be much
1641 larger and more numerous, resulting in a spaghetti-code mess.
1642
1643 Instead, it would be preferable to express this flow of control using
1644 structured constructs, such as loops. Charm++ provides such constructs
1645 for structured control flow across an object’s entry methods in a
1646 notation called Structured Dagger. The basic constructs of Structured
1647 Dagger (SDAG) provide for *program-order execution* of the entry methods
1648 and code blocks that they define. These definitions appear in the
1649 ``.ci`` file definition of the enclosing chare class as a ‘body’ of an
1650 entry method following its signature.
1651
1652 The most basic construct in SDAG is the ``serial`` (aka the ``atomic``)
1653 block. Serial blocks contain sequential C++ code. They’re also called
1654 atomic because the code within them executes without returning control
1655 to the Charm++ runtime scheduler, and thus avoiding interruption from
1656 incoming messages. The keywords atomic and serial are synonymous, and
1657 you can find example programs that use atomic. However, we recommend the
1658 use of serial and are considering the deprecation of the atomic keyword.
1659 Typically serial blocks hold the code that actually deals with incoming
1660 messages in a ``when`` statement, or to do local operations before a
1661 message is sent or after it’s received. The earlier example can be
1662 adapted to use serial blocks as follows:
1663
1664 ::
1665
1666    // in .ci file
1667    chare ComputeObject {
1668      entry void ComputeObject();
1669      entry void startStep();
1670      entry void firstInput(Input i) {
1671        serial {
1672          first = i;
1673          if (--expectedMessageCount == 0)
1674            computeInteractions(first, second);
1675        }
1676      };
1677      entry void secondInput(Input j) {
1678        serial {
1679          second = j;
1680          if (--expectedMessageCount == 0)
1681            computeInteractions(first, second);
1682        }
1683      };
1684    };
1685
1686    // in C++ file
1687    class ComputeObject : public CBase_ComputeObject {
1688      ComputeObject_SDAG_CODE
1689      int   expectedMessageCount;
1690      Input first, second;
1691
1692    public:
1693      ComputeObject() {
1694        startStep();
1695      }
1696      void startStep() {
1697        expectedMessageCount = 2;
1698      }
1699
1700      void computeInteractions(Input a, Input b) {
1701        // do computations using a and b
1702        . . .
1703        // send off results
1704        . . .
1705        // reset for next step
1706        startStep();
1707      }
1708    };
1709
1710 Note that chare classes containing SDAG code must include a few
1711 additional declarations in addition to inheriting from their
1712 ``CBase_Foo`` class, by incorporating the ``Foo_SDAG_CODE``
1713 generated-code macro in the class.
1714
1715 Serial blocks can also specify a textual ‘label’ that will appear in
1716 traces, as follows:
1717
1718 ::
1719
1720      entry void firstInput(Input i) {
1721        serial "process first" {
1722          first = i;
1723          if (--expectedMessageCount == 0)
1724            computeInteractions(first, second);
1725        }
1726      };
1727
1728 In order to control the sequence in which entry methods are processed,
1729 SDAG provides the ``when`` construct. These statements, also called
1730 triggers, indicate that we expect an incoming message of a particular
1731 type, and provide code to handle that message when it arrives. From the
1732 perspective of a chare object reaching a ``when`` statement, it is
1733 effectively a ‘blocking receive.’
1734
1735 Entry methods defined by a ``when`` are not executed immediately when a
1736 message targeting them is delivered, but instead are held until control
1737 flow in the chare reaches a corresponding ``when`` clause. Conversely,
1738 when control flow reaches a ``when`` clause, the generated code checks
1739 whether a corresponding message has arrived: if one has arrived, it is
1740 processed; otherwise, control is returned to the Charm++ scheduler.
1741
1742 The use of ``when`` substantially simplifies the example from above:
1743
1744 ::
1745
1746    // in .ci file
1747    chare ComputeObject {
1748      entry void ComputeObject();
1749      entry void startStep() {
1750        when firstInput(Input first)
1751          when secondInput(Input second)
1752            serial {
1753              computeInteractions(first, second);
1754            }
1755      };
1756      entry void firstInput(Input i);
1757      entry void secondInput(Input j);
1758    };
1759
1760    // in C++ file
1761    class ComputeObject : public CBase_ComputeObject {
1762      ComputeObject_SDAG_CODE
1763
1764    public:
1765      ComputeObject() {
1766        startStep();
1767      }
1768
1769      void computeInteractions(Input a, Input b) {
1770        // do computations using a and b
1771        . . .
1772        // send off results
1773        . . .
1774        // reset for next step
1775        startStep();
1776      }
1777    };
1778
1779 Like an ``if`` or ``while`` in C code, each ``when`` clause has a body
1780 made up of the statement or block following it. The variables declared
1781 as arguments to the entry method triggering the when are available in
1782 the scope of the body. By using the sequenced execution of SDAG code and
1783 the availability of parameters to when-defined entry methods in their
1784 bodies, the counter ``expectedMessageCount`` and the intermediate copies
1785 of the received input are eliminated. Note that the entry methods
1786 ``firstInput`` and ``secondInput`` are still declared in the ``.ci``
1787 file, but their definition is in the SDAG code. The interface translator
1788 generates code to handle buffering and triggering them appropriately.
1789
1790 For simplicity, ``when`` constructs can also specify multiple expected
1791 entry methods that all feed into a single body, by separating their
1792 prototypes with commas:
1793
1794 ::
1795
1796    entry void startStep() {
1797      when firstInput(Input first),
1798           secondInput(Input second)
1799        serial {
1800          computeInteractions(first, second);
1801        }
1802    };
1803
1804 A single entry method is allowed to appear in more than one ``when``
1805 statement. If only one of those ``when`` statements has been triggered
1806 when the runtime delivers a message to that entry method, that ``when``
1807 statement is guaranteed to process it. If there is no trigger waiting
1808 for that entry method, then the next corresponding ``when`` to be
1809 reached will receive that message. If there is more than one ``when``
1810 waiting on that method, which one will receive it is not specified, and
1811 should not be relied upon. For an example of multiple ``when``
1812 statements handling the same entry method without reaching the
1813 unspecified case, see the CharmLU benchmark.
1814
1815 To more finely control the correspondence between incoming messages and
1816 ``when`` clauses associated with the target entry method, SDAG supports
1817 *matching* on reference numbers. Matching is typically used to denote an
1818 iteration of a program that executes asynchronously (without any sort of
1819 barrier or other synchronization between steps) or a particular piece of
1820 the problem being solved. Matching is requested by placing an expression
1821 denoting the desired reference number in square brackets between the
1822 entry method name and its parameter list. For parameter marshalled entry
1823 methods, the reference number expression will be compared for equality
1824 with the entry method’s first argument. For entry methods that accept an
1825 explicit message (§ :numref:`messages`), the reference number on the
1826 message can be set by calling the function
1827 ``CkSetRefNum(void *msg, CMK_REFNUM_TYPE ref)``. Matching is used in the
1828 loop example below, and in
1829 ``examples/charm++/jacobi2d-sdag/jacobi2d.ci``. Multiple ``when``
1830 triggers for an entry method with different matching reference numbers
1831 will not conflict - each will receive only corresponding messages.
1832
1833 SDAG supports the ``for`` and ``while`` loop constructs mostly as if
1834 they appeared in plain C or C++ code. In the running example,
1835 ``computeInteractions()`` calls ``startStep()`` when it is finished to
1836 start the next step. Instead of this arrangement, the loop structure can
1837 be made explicit:
1838
1839 ::
1840
1841    // in .ci file
1842    chare ComputeObject {
1843      entry void ComputeObject();
1844      entry void runForever() {
1845        while(true) {
1846          when firstInput(Input first),
1847               secondInput(Input second) serial {
1848              computeInteractions(first, second);
1849          }
1850        }
1851      };
1852      entry void firstInput(Input i);
1853      entry void secondInput(Input j);
1854    };
1855
1856    // in C++ file
1857    class ComputeObject : public CBase_ComputeObject {
1858      ComputeObject_SDAG_CODE
1859
1860    public:
1861      ComputeObject() {
1862        runForever();
1863      }
1864
1865      void computeInteractions(Input a, Input b) {
1866        // do computations using a and b
1867        . . .
1868        // send off results
1869        . . .
1870      }
1871    };
1872
1873 If this code should instead run for a fixed number of iterations, we can
1874 instead use a for loop:
1875
1876 ::
1877
1878    // in .ci file
1879    chare ComputeObject {
1880      entry void ComputeObject();
1881      entry void runForever() {
1882        for(iter = 0; iter < n; ++iter) {
1883          // Match to only accept inputs for the current iteration
1884          when firstInput[iter](int a, Input first),
1885               secondInput[iter](int b, Input second) serial {
1886            computeInteractions(first, second);
1887          }
1888        }
1889      };
1890      entry void firstInput(int a, Input i);
1891      entry void secondInput(int b, Input j);
1892    };
1893
1894    // in C++ file
1895    class ComputeObject : public CBase_ComputeObject {
1896      ComputeObject_SDAG_CODE
1897      int n, iter;
1898
1899    public:
1900      ComputeObject() {
1901        n = 10;
1902        runForever();
1903      }
1904
1905      void computeInteractions(Input a, Input b) {
1906        // do computations using a and b
1907        . . .
1908        // send off results
1909        . . .
1910      }
1911    };
1912
1913 Note that ``int iter;`` is declared in the chare’s class definition and
1914 not in the ``.ci`` file. This is necessary because the Charm++ interface
1915 translator does not fully parse the declarations in the ``for`` loop
1916 header, because of the inherent complexities of C++.
1917
1918 SDAG also supports conditional execution of statements and blocks with
1919 ``if`` statements. The syntax of SDAG ``if`` statements matches that of
1920 C and C++. However, if one encounters a syntax error on correct-looking
1921 code in a loop or conditional statement, try assigning the condition
1922 expression to a boolean variable in a serial block preceding the
1923 statement and then testing that boolean’s value. This can be necessary
1924 because of the complexity of parsing C++ code.
1925
1926 In cases where multiple tasks must be processed before execution
1927 continues, but with no dependencies or interactions among them, SDAG
1928 provides the ``overlap`` construct. Overlap blocks contain a series of
1929 SDAG statements within them which can occur in any order. Commonly these
1930 blocks are used to hold a series of ``when`` triggers which can be
1931 received and processed in any order. Flow of control doesn’t leave the
1932 overlap block until all the statements within it have been processed.
1933
1934 In the running example, suppose each input needs to be preprocessed
1935 independently before the call to ``computeInteractions``. Since we don’t
1936 care which order they get processed in, and want it to happen as soon as
1937 possible, we can apply ``overlap``:
1938
1939 ::
1940
1941    // in .ci file
1942    chare ComputeObject {
1943      entry void ComputeObject();
1944      entry void startStep() {
1945        overlap {
1946          when firstInput(Input i)
1947            serial { first = preprocess(i); }
1948          when secondInput(Input j)
1949            serial { second = preprocess(j); }
1950         }
1951         serial {
1952           computeInteractions(first, second);
1953         }
1954      };
1955      entry void firstInput(Input i);
1956      entry void secondInput(Input j);
1957    };
1958
1959    // in C++ file
1960    class ComputeObject : public CBase_ComputeObject {
1961      ComputeObject_SDAG_CODE
1962
1963    public:
1964      ComputeObject() {
1965        startStep();
1966      }
1967
1968      void computeInteractions(Input a, Input b) {
1969        // do computations using a and b
1970        . . .
1971        // send off results
1972        . . .
1973        // reset for next step
1974        startStep();
1975      }
1976    };
1977
1978 Another construct offered by SDAG is the ``forall`` loop. These loops
1979 are used when the iterations of a loop can be performed independently
1980 and in any order. This is in contrast to a regular ``for`` loop, in
1981 which each iteration is executed sequentially. The loop iterations are
1982 executed entirely on the calling PE, so they do not run in parallel.
1983 However, they are executed concurrently, in that execution of different
1984 iterations can interleave at ``when`` statements, like any other SDAG
1985 code. SDAG statements following the ``forall`` loop will not execute
1986 until all iterations have completed. The ``forall`` loop can be seen as
1987 an ``overlap`` with an indexed set of otherwise identical statements in
1988 the body.
1989
1990 The syntax of ``forall`` is
1991
1992 ::
1993
1994    forall [IDENT] (MIN:MAX,STRIDE) BODY
1995
1996 The range from MIN to MAX is inclusive. In each iteration instance of
1997 ``BODY``, the ``IDENT`` variable will take on one of the values in the
1998 specified range. The ``IDENT`` variable must be declared in the
1999 application C++ code as a member of the enclosing chare class.
2000
2001 Use of ``forall`` is demonstrated through distributed parallel
2002 matrix-matrix multiply shown in ``examples/charm++/matmul/matmul.ci``
2003
2004 The ``case`` Statement
2005 ~~~~~~~~~~~~~~~~~~~~~~
2006
2007 The ``case`` statement in SDAG expresses a disjunction over a set of
2008 ``when`` clauses. In other words, if it is known that one dependency out
2009 of a set will be satisfied, but which one is not known, this statement
2010 allows the set to be specified and will execute the corresponding block
2011 based on which dependency ends up being fulfilled.
2012
2013 The following is a basic example of the ``case`` statement. Note that
2014 the trigger ``b(), d()`` will only be fulfilled if both ``b()`` and
2015 ``d()`` arrive. If only one arrives, then it will partially match, and
2016 the runtime will not “commit” to this branch until the second arrives.
2017 If another dependency fully matches, the partial match will be ignored
2018 and can be used to trigger another ``when`` later in the execution.
2019
2020 ::
2021
2022    case {
2023      when a() { }
2024      when b(), d() { }
2025      when c() { }
2026    }
2027
2028 A full example of the ``case`` statement can be found
2029 ``tests/charm++/sdag/case/caseTest.ci``.
2030
2031 Usage Notes
2032 ~~~~~~~~~~~
2033
2034 SDAG Code Declaration
2035 ^^^^^^^^^^^^^^^^^^^^^
2036
2037 If you’ve added *Structured Dagger* code to your class, you must link in
2038 the code by adding “*className*\ \_SDAG_CODE” inside the class
2039 declaration in the .h file. This macro defines the entry points and
2040 support code used by *Structured Dagger*. Forgetting this results in a
2041 compile error (undefined SDAG entry methods referenced from the .def.h
2042 file).
2043
2044 For example, an array named “Foo” that uses sdag code might contain:
2045
2046 ::
2047
2048    class Foo : public CBase_Foo {
2049    public:
2050        Foo_SDAG_CODE
2051        Foo(...) {
2052           ...
2053        }
2054        Foo(CkMigrateMessage *m) { }
2055
2056        void pup(PUP::er &p) {
2057           ...
2058        }
2059        . . .
2060    };
2061
2062 Direct Calls to SDAG Entry Methods
2063 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2064
2065 An SDAG entry method that contains one or more when clause(s) cannot be
2066 directly called and will result in a runtime error with an error
2067 message. It has to be only called through a proxy. This is a runtime
2068 requirement that is enforced in order to prevent accidental calls to
2069 SDAG entry methods that are asynchronous in nature. Additionally, since
2070 they are called using a proxy, it enhances understandability and clarity
2071 as to not be confused for a regular function call that returns
2072 immediately.
2073
2074 For example, in the first example discussed, it is invalid to call the
2075 SDAG entry method ``startStep`` directly as ``startStep();`` because it
2076 contains when clauses. It has to be only called using the proxy i.e.
2077 ``computeObj.startStep();`` , where ``computeObj`` is the proxy to
2078 ``ComputeObject``.
2079
2080 .. _sec:pup:
2081
2082 Serialization Using the PUP Framework
2083 -------------------------------------
2084
2085 The PUP (Pack/Unpack) framework is a generic way to describe the data in
2086 an object and to use that description for serialization. The
2087 Charm++ system can use this description to pack the object into a
2088 message and unpack the message into a new object on another processor,
2089 to pack and unpack migratable objects for load balancing or
2090 checkpoint/restart-based fault tolerance. The PUP framework also
2091 includes support special for STL containers to ease development in C++.
2092
2093 Like many C++ concepts, the PUP framework is easier to use than describe:
2094
2095 ::
2096
2097    class foo : public mySuperclass {
2098     private:
2099        double a;
2100        int x;
2101        char y;
2102        unsigned long z;
2103        float arr[3];
2104     public:
2105        ...other methods...
2106
2107        //pack/unpack method: describe my fields to charm++
2108        void pup(PUP::er &p) {
2109          mySuperclass::pup(p);
2110          p|a;
2111          p|x; p|y; p|z;
2112          PUParray(p,arr,3);
2113        }
2114    };
2115
2116 This class’s pup method describes the fields of the class to Charm++.
2117 This allows Charm++ to marshall parameters of type foo across
2118 processors, translate foo objects across processor architectures, read
2119 and write foo objects to files on disk, inspect and modify foo objects
2120 in the debugger, and checkpoint and restart programs involving foo
2121 objects.
2122
2123 .. _sec:pupcontract:
2124
2125 PUP contract
2126 ~~~~~~~~~~~~
2127
2128 Your object’s pup method must save and restore all your object’s data.
2129 As shown, you save and restore a class’s contents by writing a method
2130 called “pup” which passes all the parts of the class to an object of
2131 type PUP::er, which does the saving or restoring. This manual will often
2132 use “pup” as a verb, meaning “to save/restore the value of” or
2133 equivalently, “to call the pup method of”.
2134
2135 Pup methods for complicated objects normally call the pup methods for
2136 their simpler parts. Since all objects depend on their immediate
2137 superclass, the first line of every pup method is a call to the
2138 superclass’s pup method—the only time you shouldn’t call your
2139 superclass’s pup method is when you don’t have a superclass. If your
2140 superclass has no pup method, you must pup the values in the superclass
2141 yourself.
2142
2143 .. _sec:pupoperator:
2144
2145 PUP operator
2146 ^^^^^^^^^^^^
2147
2148 The recommended way to pup any object ``a`` is to use ``p|a;``. This
2149 syntax is an operator ``|`` applied to the PUP::er ``p`` and the user
2150 variable ``a``.
2151
2152 The ``p|a;`` syntax works wherever ``a`` is:
2153
2154 -  A simple type, including char, short, int, long, float, or double. In
2155    this case, ``p|a;`` copies the data in-place. This is equivalent to
2156    passing the type directly to the PUP::er using ``p(a)``.
2157
2158 -  Any object with a pup method. In this case, ``p|a;`` calls the
2159    object’s pup method. This is equivalent to the statement a.pup(p);.
2160
2161 -  A pointer to a PUP::able object, as described in
2162    Section :numref:`sec:pup::able`. In this case, ``p|a;`` allocates
2163    and copies the appropriate subclass.
2164
2165 -  An object with a PUPbytes(myClass) declaration in the header. In this
2166    case, ``p|a;`` copies the object as plain bytes, like memcpy.
2167
2168 -  An object with a custom ``operator |`` defined. In this case,
2169    ``p|a;`` calls the custom ``operator |``.
2170
2171 See ``examples/charm++/PUP``
2172
2173 For container types, you must simply pup each element of the container.
2174 For arrays, you can use the utility method PUParray, which takes the
2175 PUP::er, the array base pointer, and the array length. This utility
2176 method is defined for user-defined types T as:
2177
2178 ::
2179
2180        template<class T>
2181        inline void PUParray(PUP::er &p,T *array,int length) {
2182           for (int i=0;i<length;i++) p|array[i];
2183        }
2184
2185 .. _sec:pupstl:
2186
2187 PUP STL Container Objects
2188 ^^^^^^^^^^^^^^^^^^^^^^^^^
2189
2190 If the variable is from the C++ Standard Template Library, you can
2191 include operator\ ``|``\ ’s for STL containers such as vector, map, set,
2192 list, pair, and string, templated on anything, by including the header
2193 “pup_stl.h”.
2194
2195 See ``examples/charm++/PUP/STLPUP``
2196
2197 PUP Dynamic Data
2198 ^^^^^^^^^^^^^^^^
2199
2200 As usual in C++, pointers and allocatable objects usually require special
2201 handling. Typically this only requires a p.isUnpacking() conditional
2202 block, where you perform the appropriate allocation. See
2203 Section :numref:`sec:pupdynalloc` for more information and examples.
2204
2205 If the object does not have a pup method, and you cannot add one or use
2206 PUPbytes, you can define an operator\ ``|`` to pup the object. For
2207 example, if myClass contains two fields a and b, the operator\ ``|``
2208 might look like:
2209
2210 ::
2211
2212      inline void operator|(PUP::er &p,myClass &c) {
2213        p|c.a;
2214        p|c.b;
2215      }
2216
2217 See ``examples/charm++/PUP/HeapPUP``
2218
2219 .. _sec:pupbytes:
2220
2221 PUP as bytes
2222 ^^^^^^^^^^^^
2223
2224 For classes and structs with many fields, it can be tedious and
2225 error-prone to list all the fields in the pup method. You can avoid this
2226 listing in two ways, as long as the object can be safely copied as raw
2227 bytes—this is normally the case for simple structs and classes without
2228 pointers.
2229
2230 -  Use the ``PUPbytes(myClass)`` macro in your header file. This lets
2231    you use the ``p|*myPtr;`` syntax to pup the entire class as
2232    sizeof(myClass) raw bytes.
2233
2234 -  Use ``p((void *)myPtr,sizeof(myClass));`` in the pup method. This is
2235    a direct call to pup a set of bytes.
2236
2237 -  Use ``p((char *)myCharArray,arraySize);`` in the pup method. This is
2238    a direct call to pup a set of bytes. Other primitive types may also
2239    be used.
2240
2241 Note that pupping as bytes is just like using ‘memcpy’: it does nothing
2242 to the data other than copy it whole. For example, if the class contains
2243 any pointers, you must make sure to do any allocation needed, and pup
2244 the referenced data yourself.
2245
2246 Pupping as bytes may prevent your pup method from ever being able to
2247 work across different machine architectures. This is currently an
2248 uncommon scenario, but heterogeneous architectures may become more
2249 common, so pupping as bytes is discouraged.
2250
2251 .. _sec:pupoverhead:
2252
2253 PUP overhead
2254 ^^^^^^^^^^^^
2255
2256 The PUP::er overhead is very small—one virtual function call for each
2257 item or array to be packed/unpacked. The actual packing/unpacking is
2258 normally a simple memory-to-memory binary copy.
2259
2260 For arrays and vectors of builtin arithmetic types like “int" and
2261 “double", or of types declared as “PUPbytes”, PUParray uses an even
2262 faster block transfer, with one virtual function call per array or
2263 vector.
2264
2265 Thus, if an object does not contain pointers, you should prefer
2266 declaring it as PUPbytes.
2267
2268 For types of objects whose default constructors do more than necessary
2269 when an object will be unpacked from PUP, it is possible to tell the
2270 runtime system to call a more minimalistic alternative. This can apply
2271 to types used as both member variables of chares and as marshalled
2272 arguments to entry methods. A non-chare class can define a constructor
2273 that takes an argument of type ``PUP::reconstruct`` for this purpose.
2274 The runtime system code will call a ``PUP::reconstruct`` constructor in
2275 preference to a default constructor when it’s available. Where
2276 necessary, constructors taking ``PUP::reconstruct`` should call the
2277 constructors of members variables with ``PUP::reconstruct`` if
2278 applicable to that member.
2279
2280 .. _sec:pupmodes:
2281
2282 PUP modes
2283 ^^^^^^^^^
2284
2285 Charm++ uses your pup method to both pack and unpack, by passing
2286 different types of PUP::ers to it. The method p.isUnpacking() returns
2287 true if your object is being unpacked—that is, your object’s values are
2288 being restored. Your pup method must work properly in sizing, packing,
2289 and unpacking modes; and to save and restore properly, the same fields
2290 must be passed to the PUP::er, in the exact same order, in all modes.
2291 This means most pup methods can ignore the pup mode.
2292
2293 Three modes are used, with three separate types of PUP::er: sizing,
2294 which only computes the size of your data without modifying it; packing,
2295 which reads/saves values out of your data; and unpacking, which
2296 writes/restores values into your data. You can determine exactly which
2297 type of PUP::er was passed to you using the p.isSizing(), p.isPacking(),
2298 and p.isUnpacking() methods. However, sizing and packing should almost
2299 always be handled identically, so most programs should use
2300 p.isUnpacking() and !p.isUnpacking(). Any program that calls
2301 p.isPacking() and does not also call p.isSizing() is probably buggy,
2302 because sizing and packing must see exactly the same data.
2303
2304 The p.isDeleting() flag indicates the object will be deleted after
2305 calling the pup method. This is normally only needed for pup methods
2306 called via the C or f90 interface, as provided by AMPI or the other
2307 frameworks. Other Charm++ array elements, marshalled parameters, and
2308 other C++ interface objects have their destructor called when they are
2309 deleted, so the p.isDeleting() call is not normally required—instead,
2310 memory should be deallocated in the destructor as usual.
2311
2312 More specialized modes and PUP::ers are described in
2313 section :numref:`sec:PUP:CommonPUPers`.
2314
2315 .. _sec:lifecycle:
2316
2317 PUP Usage Sequence
2318 ~~~~~~~~~~~~~~~~~~
2319
2320 .. figure:: fig/pup.png
2321    :name: fig:pup
2322    :width: 6in
2323
2324    Method sequence of an object with a pup method.
2325
2326 Typical method invocation sequence of an object with a pup method is
2327 shown in Figure :numref:`fig:pup`. As usual in C++, objects are
2328 constructed, do some processing, and are then destroyed.
2329
2330 Objects can be created in one of two ways: they can be created using a
2331 normal constructor as usual; or they can be created using their pup
2332 constructor. The pup constructor for Charm++ array elements and
2333 PUP::able objects is a “migration constructor” that takes a single
2334 “CkMigrateMessage \*"; for other objects, such as parameter marshalled
2335 objects, the pup constructor has no parameters. The pup constructor is
2336 always followed by a call to the object’s pup method in ``isUnpacking``
2337 mode.
2338
2339 Once objects are created, they respond to regular user methods and
2340 remote entry methods as usual. At any time, the object pup method can be
2341 called in ``isSizing`` or ``isPacking`` mode. User methods and sizing or
2342 packing pup methods can be called repeatedly over the object lifetime.
2343
2344 Finally, objects are destroyed by calling their destructor as usual.
2345
2346 .. _arraymigratable:
2347
2348 Migratable Array Elements using PUP
2349 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2350
2351 Array objects can migrate from one PE to another. For example, the load
2352 balancer (see section :numref:`lbFramework`) might migrate array
2353 elements to better balance the load between processors. For an array
2354 element to be migratable, it must implement a pup method. The standard
2355 PUP contract (see section :numref:`sec:pupcontract`) and constraints
2356 wrt to serializing data apply. The one exception for chare , group and
2357 node group types is that since the runtime system will be the one to
2358 invoke their PUP routines, the runtime will automatically call PUP on
2359 the generated CBase\_ superclasses so users do not need to call PUP on
2360 generated superclasses.
2361
2362 A simple example for an array follows:
2363
2364 ::
2365
2366    //In the .h file:
2367    class A2 : public CBase_A2 {
2368    private: //My data members:
2369        int nt;
2370        unsigned char chr;
2371        float flt[7];
2372        int numDbl;
2373        double *dbl;
2374    public:
2375        //...other declarations
2376
2377        virtual void pup(PUP::er &p);
2378    };
2379
2380    //In the .C file:
2381    void A2::pup(PUP::er &p)
2382    {
2383        // The runtime will automatically call CBase_A2::pup()
2384        p|nt;
2385        p|chr;
2386        p(flt,7);
2387        p|numDbl;
2388        if (p.isUnpacking()) dbl=new double[numDbl];
2389        p(dbl,numDbl);
2390    }
2391
2392 The default assumption, as used in the example above, for the object
2393 state at PUP time is that a chare, and its member objects, could be
2394 migrated at any time while it is inactive, i.e. not executing an entry
2395 method. Actual migration time can be controlled (see
2396 section :numref:`lbFramework`) to be less frequent. If migration
2397 timing is fully user controlled, e.g., at the end of a synchronized load
2398 balancing step, then PUP implementation can be simplified to only
2399 transport “live” ephemeral data matching the object state which
2400 coincides with migration. More intricate state based PUPing, for objects
2401 whose memory footprint varies substantially with computation phase, can
2402 be handled by explicitly maintaining the object’s phase in a member
2403 variable and implementing phase conditional logic in the PUP method (see
2404 section :numref:`sec:pupdynalloc`).
2405
2406 Marshalling User Defined Data Types via PUP
2407 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2408
2409 Parameter marshalling requires serialization and is therefore
2410 implemented using the PUP framework. User defined data types passed as
2411 parameters must abide by the standard PUP contract (see section
2412 :numref:`sec:pupcontract`).
2413
2414 A simple example of using PUP to marshall user defined data types
2415 follows:
2416
2417 ::
2418
2419    class Buffer {
2420    public:
2421    //...other declarations
2422      void pup(PUP::er &p) {
2423        // remember to pup your superclass if there is one
2424        p|size;
2425        if (p.isUnpacking())
2426          data = new int[size];
2427        PUParray(p, data, size);
2428      }
2429
2430    private:
2431      int size;
2432      int *data;
2433    };
2434
2435
2436    // In some .ci file
2437    entry void process(Buffer &buf);
2438
2439 For efficiency, arrays are always copied as blocks of bytes and passed
2440 via pointers. This means classes that need their pup routines to be
2441 called, such as those with dynamically allocated data or virtual methods
2442 cannot be passed as arrays-use STL vectors to pass lists of complicated
2443 user-defined classes. For historical reasons, pointer-accessible
2444 structures cannot appear alone in the parameter list (because they are
2445 confused with messages).
2446
2447 The order of marshalling operations on the send side is:
2448
2449 -  Call “p\ ``|``\ a” on each marshalled parameter with a sizing
2450    PUP::er.
2451
2452 -  Compute the lengths of each array.
2453
2454 -  Call “p\ ``|``\ a” on each marshalled parameter with a packing
2455    PUP::er.
2456
2457 -  memcpy each arrays’ data.
2458
2459 The order of marshalling operations on the receive side is:
2460
2461 -  Create an instance of each marshalled parameter using its default
2462    constructor.
2463
2464 -  Call “p\ ``|``\ a” on each marshalled parameter using an unpacking
2465    PUP::er.
2466
2467 -  Compute pointers into the message for each array.
2468
2469 Finally, very large structures are most efficiently passed via messages,
2470 because messages are an efficient, low-level construct that minimizes
2471 copying and overhead; but very complicated structures are often most
2472 easily passed via marshalling, because marshalling uses the high-level
2473 pup framework.
2474
2475 See ``examples/charm++/PUP/HeapPUP``
2476
2477 .. _loadbalancing:
2478
2479 Load Balancing
2480 --------------
2481
2482 Load balancing in Charm++ is enabled by its ability to place, or
2483 migrate, chares or chare array elements. Typical application usage to
2484 exploit this feature will construct many more chares than processors,
2485 and enable their runtime migration.
2486
2487 Iterative applications, which are commonplace in physical simulations,
2488 are the most suitable target for Charm++’s measurement based load
2489 balancing techniques. Such applications may contain a series of
2490 time-steps, and/or iterative solvers that run to convergence. For such
2491 computations, typically, the heuristic principle that we call “principle
2492 of persistence” holds: the computational loads and communication
2493 patterns between objects (chares) tend to persist over multiple
2494 iterations, even in dynamic applications. In such cases, the recent past
2495 is a good predictor of the near future. Measurement-based chare
2496 migration strategies are useful in this context. Currently these apply
2497 to chare-array elements, but they may be extended to chares in the
2498 future.
2499
2500 For applications without such iterative structure, or with iterative
2501 structure, but without predictability (i.e. where the principle of
2502 persistence does not apply), Charm++ supports “seed balancers” that move
2503 “seeds” for new chares among processors (possibly repeatedly) to achieve
2504 load balance. These strategies are currently available for both chares
2505 and chare-arrays. Seed balancers were the original load balancers
2506 provided in Charm since the late 80’s. They are extremely useful for
2507 state-space search applications, and are also useful in other
2508 computations, as well as in conjunction with migration strategies.
2509
2510 For iterative computations when there is a correlation between
2511 iterations/steps, but either it is not strong, or the machine
2512 environment is not predictable (due to noise from OS interrupts on small
2513 time steps, or time-shared desktop machines), one can use a combination
2514 of the two kinds of strategies. The baseline load balancing is provided
2515 by migration strategies, but in each iteration one also spawns off work
2516 in the form of chares that can run on any processor. The seed balancer
2517 will handle such work as it arises.
2518
2519 Examples are in ``examples/charm++/load_balancing`` and
2520 ``tests/charm++/load_balancing``
2521
2522 .. _lbFramework:
2523
2524 Measurement-based Object Migration Strategies
2525 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2526
2527 In Charm++, objects (except groups, nodegroups) can migrate from
2528 processor to processor at runtime. Object migration can potentially
2529 improve the performance of the parallel program by migrating objects
2530 from overloaded processors to underloaded ones.
2531
2532 Charm++ implements a generic, measurement-based load balancing framework
2533 which automatically instruments all Charm++ objects, collects
2534 computation load and communication structure during execution and stores
2535 them into a load balancing database. Charm++ then provides a collection
2536 of load balancing strategies whose job it is to decide on a new mapping
2537 of objects to processors based on the information from the database.
2538 Such measurement based strategies are efficient when we can reasonably
2539 assume that objects in a Charm++ application tend to exhibit temporal
2540 correlation in their computation and communication patterns, i.e. future
2541 can be to some extent predicted using the historical measurement data,
2542 allowing effective measurement-based load balancing without
2543 application-specific knowledge.
2544
2545 Two key terms in the Charm++ load balancing framework are:
2546
2547 -  Load balancing database provides the interface of almost all load
2548    balancing calls. On each processor, it stores the load balancing
2549    instrumented data and coordinates the load balancing manager and
2550    balancer. It is implemented as a Chare Group called LBDatabase.
2551
2552 -  Load balancer or strategy takes the load balancing database and
2553    produces the new mapping of the objects. In Charm++, it is
2554    implemented as Chare Group inherited from BaseLB. Three kinds of
2555    schemes are implemented: (a) centralized load balancers, (b) fully
2556    distributed load balancers and (c) hierarchical load balancers.
2557
2558 .. _lbStrategy:
2559
2560 Available Load Balancing Strategies
2561 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2562
2563 Load balancing can be performed in either a centralized, a fully
2564 distributed, or an hierarchical fashion.
2565
2566 In centralized approaches, the entire machine’s load and communication
2567 structure are accumulated to a single point, typically processor 0,
2568 followed by a decision making process to determine the new distribution
2569 of Charm++ objects. Centralized load balancing requires synchronization
2570 which may incur an overhead and delay. However, due to the fact that the
2571 decision process has a high degree of the knowledge about the entire
2572 platform, it tends to be more accurate.
2573
2574 In distributed approaches, load data is only exchanged among neighboring
2575 processors. There is no global synchronization. However, they will not,
2576 in general, provide an immediate restoration for load balance - the
2577 process is iterated until the load balance can be achieved.
2578
2579 In hierarchical approaches, processors are divided into independent
2580 autonomous sets of processor groups and these groups are organized in
2581 hierarchies, thereby decentralizing the load balancing task. Different
2582 strategies can be used to balance the load on processors inside each
2583 processor group, and processors across groups in a hierarchical fashion.
2584
2585 Listed below are some of the available non-trivial centralized load
2586 balancers and their brief descriptions:
2587
2588 -  **GreedyLB**: Uses a greedy algorithm that always assigns the
2589    heaviest object to the least loaded processor.
2590
2591 -  **GreedyRefineLB**: Uses a greedy algorithm that assigns the heaviest
2592    object to the least loaded processor when the benefit outweighs the
2593    migration cost, otherwise leaves the object on its current processor.
2594    It takes an optional command-line argument *+LBPercentMoves*,which
2595    specifies the percentage of migrations that can be tolerated.
2596
2597 -  **TopoCentLB**: Extends the greedy algorithm to take processor
2598    topology into account.
2599
2600 -  **RefineLB**: Moves objects away from the most overloaded processors
2601    to reach average, limits the number of objects migrated.
2602
2603 -  **RefineSwapLB**: Moves objects away from the most overloaded
2604    processors to reach average. In case it cannot migrate an object from
2605    an overloaded processor to an underloaded processor, it swaps objects
2606    to reduce the load on the overloaded processor. This strategy limits
2607    the number of objects migrated.
2608
2609 -  **RefineTopoLB**: Same idea as in RefineLB, but takes processor
2610    topology into account.
2611
2612 -  **BlockLB**: This strategy does a blocked distribution of objects to
2613    processors.
2614
2615 -  **ComboCentLB**: A special load balancer that can be used to combine
2616    any number of centralized load balancers mentioned above.
2617
2618 Listed below are some of the communication-aware load balancers:
2619
2620 -  **MetisLB**: Uses `METIS <http://glaros.dtc.umn.edu/gkhome/metis/metis/overview>`__
2621    to partition the object communication graph.
2622
2623 -  **ScotchLB**: Uses the `SCOTCH <http://www.labri.fr/perso/pelegrin/scotch/>`__
2624    library for partitioning the object
2625    communication graph, while also taking object load imbalance into
2626    account.
2627
2628 -  **GreedyCommLB**: Extends the greedy algorithm to take the
2629    communication graph into account.
2630
2631 -  **RefineCommLB**: Same idea as in RefineLB, but takes communication
2632    into account.
2633
2634 Listed below are the distributed load balancers:
2635
2636 -  **NeighborLB**: A neighborhood load balancer in which each processor
2637    tries to average out its load only among its neighbors.
2638
2639 -  **WSLB**: A load balancer for workstation clusters, which can detect
2640    load changes on desktops (and other timeshared processors) and adjust
2641    load without interfering with other’s use of the desktop.
2642
2643 -  **DistributedLB**: A load balancer which uses partial information
2644    about underloaded and overloaded processors in the system to do
2645    probabilistic transfer of load. This is a refinement based strategy.
2646
2647 An example of a hierarchical strategy can be found in:
2648
2649 -  **HybridLB**: This calls GreedyLB at the lower level and RefineLB at
2650    the root.
2651
2652 Listed below are load balancers for debugging purposes:
2653
2654 -  **RandCentLB**: Randomly assigns objects to processors;
2655
2656 -  **RotateLB**: This strategy moves objects to the next available PE
2657    every time it is called. It is useful for debugging PUP routines and
2658    other migration related bugs.
2659
2660 Users can choose any load balancing strategy they think is appropriate
2661 for their application. We recommend using GreedyRefineLB with
2662 applications in general. For applications where the cost of migrating
2663 objects is very high, say, due to frequent load balancing to handle
2664 frequent load changes or due to size of data in the object being large,
2665 a strategy which favors migration minimization at the cost of balance
2666 (eg: RefineLB) is more suitable. DistributedLB and HybridLB are suitable
2667 for large number of nodes. Communication-aware load balancers like
2668 MetisLB and ScotchLB are suitable for communication intensive
2669 applications. RotateLB and RandCentLB are more useful for debugging
2670 object migrations. The compiler and runtime options are described in
2671 section :numref:`lbOption`.
2672
2673 **Metabalancer to automatically schedule load balancing**
2674
2675 Metabalancer can be invoked to automatically decide when to invoke the
2676 load balancer, given the load-balancing strategy. Metabalancer uses a
2677 linear prediction model to set the load balancing period based on
2678 observed load imbalance.
2679
2680 The runtime option *+MetaLB* can be used to invoke this feature to
2681 automatically invoke the load balancing strategy based on the imbalance
2682 observed. This option needs to be specified alongside the *+balancer*
2683 option to specify the load balancing strategy to use. Metabalancer
2684 relies on the AtSync() calls specified in Section :numref:`lbarray`
2685 to collect load statistics.
2686
2687 *+MetaLBModelDir* ``<path-to-model>`` can be used to invoke the
2688 Metabalancer feature to automatically decide which load balancing
2689 strategy to invoke. A model trained on a generic representative load
2690 imbalance benchmark can be found in ``charm/src/ck-ldb/rf_model``.
2691 Metabalancer makes a decision on which load balancing strategy to invoke
2692 out of a subset of strategies, namely GreedyLB, RefineLB, HybridLB,
2693 DistributedLB, MetisLB and ScotchLB. For using the model based
2694 prediction in Metabalancer, Charm++ needs to be built with all the above
2695 load balancing strategies, including ScotchLB that relies on the
2696 external partitioning library SCOTCH specified in the
2697 Section :numref:`lbOption`.
2698
2699 .. _lbarray:
2700
2701 Load Balancing Chare Arrays
2702 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
2703
2704 The load balancing framework is well integrated with chare array
2705 implementation - when a chare array is created, it automatically
2706 registers its elements with the load balancing framework. The
2707 instrumentation of compute time (WALL/CPU time) and communication
2708 pattern is done automatically and APIs are provided for users to trigger
2709 the load balancing. To use the load balancer, you must make your array
2710 elements migratable (see migration section above) and choose a load
2711 balancing strategy (see the section :numref:`lbStrategy` for a
2712 description of available load balancing strategies).
2713
2714 There are three different ways to use load balancing for chare arrays to
2715 meet different needs of the applications. These methods are different in
2716 how and when a load balancing phase starts. The three methods are:
2717 **periodic load balancing mode**, **at sync mode** and **manual mode**.
2718
2719 In *periodic load balancing mode*, a user specifies only how often load
2720 balancing is to occur, using +LBPeriod runtime option to specify the
2721 time interval.
2722
2723 In *at sync mode*, the application invokes the load balancer explicitly
2724 at appropriate (generally at a pre-existing synchronization boundary) to
2725 trigger load balancing by inserting a function call (AtSync) in the
2726 application source code.
2727
2728 In the prior two load balancing modes, users do not need to worry about
2729 how to start load balancing. However, in one scenario, those automatic
2730 load balancers will fail to work - when array elements are created by
2731 dynamic insertion. This is because the above two load balancing modes
2732 require an application to have fixed the number of objects at the time
2733 of load balancing. The array manager needs to maintain a head count of
2734 local array elements for the local barrier. In this case, the
2735 application must use the *manual mode* to trigger load balancer.
2736
2737 The detailed APIs of these three methods are described as follows:
2738
2739 #. **Periodical load balancing mode**: In the default setting, load
2740    balancing happens whenever the array elements are ready, with an
2741    interval of 1 second. It is desirable for the application to set a
2742    larger interval using +LBPeriod runtime option. For example
2743    “+LBPeriod 5.0” can be used to start load balancing roughly every 5
2744    seconds. By default, array elements may be asked to migrate at any
2745    time, provided that they are not in the middle of executing an entry
2746    method. The array element’s variable usesAtSync being false
2747    attributes to this default behavior.
2748
2749 #. **At sync mode**: Using this method, elements can be migrated only at
2750    certain points in the execution when the application invokes
2751    AtSync(). In order to use the at sync mode, one should set usesAtSync
2752    to true in the array element constructor. When an element is ready to
2753    migrate, call AtSync()  [6]_. When all local elements call AtSync,
2754    the load balancer is triggered. Once all migrations are completed,
2755    the load balancer calls the virtual function
2756    ArrayElement::ResumeFromSync() on each of the array elements. This
2757    function can be redefined in the application.
2758
2759    Note that the minimum time for AtSync() load balancing to occur is
2760    controlled by the LBPeriod. Unusually high frequency load balancing
2761    (more frequent than 500ms) will perform better if this value is set
2762    via +LBPeriod or SetLBPeriod() to a number shorter than your load
2763    balancing interval.
2764
2765    Note that *AtSync()* is not a blocking call, it just gives a hint to
2766    load balancing that it is time for load balancing. During the time
2767    between *AtSync* and *ResumeFromSync*, the object may be migrated.
2768    One can choose to let objects continue working with incoming
2769    messages, however keep in mind the object may suddenly show up in
2770    another processor and make sure no operations that could possibly
2771    prevent migration be performed. This is the automatic way of doing
2772    load balancing where the application does not need to define
2773    ResumeFromSync().
2774
2775    The more commonly used approach is to force the object to be idle
2776    until load balancing finishes. The user places an AtSync call at the
2777    end of some iteration and when all elements reach that call load
2778    balancing is triggered. The objects can start executing again when
2779    ResumeFromSync() is called. In this case, the user redefines
2780    ResumeFromSync() to trigger the next iteration of the application.
2781    This manual way of using the at sync mode results in a barrier at
2782    load balancing (see example here :numref:`lbexample`).
2783
2784 #. **Manual mode**: The load balancer can be programmed to be started
2785    manually. To switch to the manual mode, the application calls
2786    *TurnManualLBOn()* on every processor to prevent the load balancer
2787    from starting automatically. *TurnManualLBOn()* should be called as
2788    early as possible in the program. It could be called at the
2789    initialization part of the program, for example from a global
2790    variable constructor, or in an initproc call
2791    (Section :numref:`initproc`). It can also be called in the
2792    constructor of a static array or before the *doneInserting* call for
2793    a dynamic array. It can be called multiple times on one processor,
2794    but only the last one takes effect.
2795
2796    The function call *CkStartLB()* starts load balancing immediately.
2797    This call should be made at only one place on only one processor.
2798    This function is not blocking, the object will continue to process
2799    messages and the load balancing, when triggered, happens in the
2800    background.
2801
2802    *TurnManualLBOff()* turns off manual load balancing and switches back
2803    to the automatic load balancing mode.
2804
2805 .. _lbmigobj:
2806
2807 Migrating objects
2808 ~~~~~~~~~~~~~~~~~
2809
2810 Load balancers migrate objects automatically. For an array element to
2811 migrate, user can refer to Section :numref:`arraymigratable` for how
2812 to write a “pup” for an array element.
2813
2814 In general one needs to pack the whole snapshot of the member data in an
2815 array element in the pup subroutine. This is because the migration of
2816 the object may happen at any time. In certain load balancing schemes
2817 where the user explicitly controls when load balancing occurs, the user
2818 may choose to pack only a part of the data and may skip temporary data.
2819
2820 An array element can migrate by calling the migrateMe(destination
2821 processor) member function- this call must be the last action in an
2822 element entry method. The system can also migrate array elements for
2823 load balancing (see the section :numref:`lbarray`).
2824
2825 To migrate your array element to another processor, the Charm++ runtime
2826 will:
2827
2828 -  Call your ckAboutToMigrate method
2829
2830 -  Call your pup method with a sizing PUP::er to determine how big a
2831    message it needs to hold your element.
2832
2833 -  Call your pup method again with a packing PUP::er to pack your
2834    element into a message.
2835
2836 -  Call your element’s destructor (deleting the old copy).
2837
2838 -  Send the message (containing your element) across the network.
2839
2840 -  Call your element’s migration constructor on the new processor.
2841
2842 -  Call your pup method on with an unpacking PUP::er to unpack the
2843    element.
2844
2845 -  Call your ckJustMigrated method
2846
2847 Migration constructors, then, are normally empty- all the unpacking and
2848 allocation of the data items is done in the element’s pup routine.
2849 Deallocation is done in the element destructor as usual.
2850
2851 Other utility functions
2852 ~~~~~~~~~~~~~~~~~~~~~~~
2853
2854 There are several utility functions that can be called in applications
2855 to configure the load balancer, etc. These functions are:
2856
2857 -  **LBTurnInstrumentOn()** and **LBTurnInstrumentOff()**: are plain C
2858    functions to control the load balancing statistics instrumentation on
2859    or off on the calling processor. No implicit broadcast or
2860    synchronization exists in these functions. Fortran interface:
2861    **FLBTURNINSTRUMENTON()** and **FLBTURNINSTRUMENTOFF()**.
2862
2863 -  **setMigratable(bool migratable)**: is a member function of array
2864    element. This function can be called in an array element constructor
2865    to tell the load balancer whether this object is migratable or
2866    not [7]_.
2867
2868 -  **LBSetPeriod(double s)**: this function can be called anywhere (even
2869    in Charm++ initnodes or initprocs) to specify the load balancing
2870    period time in seconds. It tells load balancer not to start next load
2871    balancing in less than :math:`s` seconds. This can be used to prevent
2872    load balancing from occurring too often in *automatic without sync
2873    mode*. Here is how to use it:
2874
2875    ::
2876
2877       // if used in an array element
2878       LBDatabase *lbdb = getLBDB();
2879       lbdb->SetLBPeriod(5.0);
2880
2881       // if used outside of an array element
2882       LBSetPeriod(5.0);
2883
2884    Alternatively, one can specify +LBPeriod {seconds} at command line.
2885
2886 .. _lbOption:
2887
2888 Compiler and runtime options to use load balancing module
2889 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2890
2891 Load balancing strategies are implemented as libraries in Charm++. This
2892 allows programmers to easily experiment with different existing
2893 strategies by simply linking a pool of strategy modules and choosing one
2894 to use at runtime via a command line option.
2895
2896 **Note:** linking a load balancing module is different from activating
2897 it:
2898
2899 -  link an LB module: is to link a Load Balancer module(library) at
2900    compile time. You can link against multiple LB libraries as
2901    candidates.
2902
2903 -  activate an LB: is to actually ask the runtime to create an LB
2904    strategy and start it. You can only activate load balancers that have
2905    been linked at compile time.
2906
2907 Below are the descriptions about the compiler and runtime options:
2908
2909 #. **compile time options:**
2910
2911    -  | *-module NeighborLB -module GreedyCommLB ...*
2912       | links the modules NeighborLB, GreedyCommLB etc into an
2913         application, but these load balancers will remain inactive at
2914         execution time unless overridden by other runtime options.
2915
2916    -  | *-module CommonLBs*
2917       | links a special module CommonLBs which includes some commonly
2918         used Charm++ built-in load balancers. The commonly used load
2919         balancers include: *DummyLB, GreedyLB, GreedyRefineLB, CommLB, RandCentLB, RefineLB, RefineCommLB, RotateLB, DistributedLB, HybridLB, ComboCentLB, RefineSwapLB, NeighborLB, OrbLB, BlockLB, GreedyCommLB*
2920
2921    -  | *-balancer GreedyCommLB*
2922       | links the load balancer GreedyCommLB and invokes it at runtime.
2923
2924    -  | *-balancer GreedyCommLB -balancer RefineLB*
2925       | invokes GreedyCommLB at the first load balancing step and
2926         RefineLB in all subsequent load balancing steps.
2927
2928    -  | *-balancer ComboCentLB:GreedyLB,RefineLB*
2929       | You can create a new combination load balancer made of multiple
2930         load balancers. In the above example, GreedyLB and RefineLB
2931         strategies are applied one after the other in each load
2932         balancing step.
2933
2934    The list of existing load balancers is given in Section
2935    :numref:`lbStrategy`. Note: you can have multiple -module \*LB
2936    options. LB modules are linked into a program, but they are not
2937    activated automatically at runtime. Using -balancer A at compile time
2938    will activate load balancer A automatically at runtime. Having
2939    -balancer A implies -module A, so you don’t have to write -module A
2940    again, although that is not invalid. Using CommonLBs is a convenient
2941    way to link against the commonly used existing load balancers.
2942
2943    The SCOTCH-based load balancer(s) use an external partitioning
2944    library requiring 3rd party software:
2945
2946    SCOTCH can be downloaded from:
2947    http://www.labri.fr/perso/pelegrin/scotch/
2948
2949    Use the *-incdir and -libdir* build time option to add your
2950    installation of any third party libraries you wish to use to the
2951    Charm++ search paths.
2952
2953 #. **Building individual load balancers**
2954
2955    Load balancers can be built individually by changing the current
2956    working directory to the *tmp* subdirectory of your build and making
2957    them by name.
2958
2959    ::
2960
2961        cd netlrts-linux-x86_64/tmp
2962        make PhasebyArrayLB
2963
2964 #. **Write and use your own load balancer**
2965
2966    Refer Section :numref:`lbWriteNewLB` for writing a new load
2967    balancer. Compile it in the form of library and name it
2968    *libmoduleFooLB.a* where *FooLB* is the new load balancer. Add the
2969    path to the library and link the load balancer into an application
2970    using *-module FooLB*.
2971
2972    You can create a library by modifying the Makefile in the following
2973    way. This will create *libmoduleFooLB.a*.
2974
2975    .. code-block:: makefile
2976
2977       libmoduleFooLB.a: FooLB.o
2978         $(CHARMC) -o libmoduleFooLB.a FooLB.o
2979
2980    To include this balancer in your application, the Makefile can be
2981    changed in the following way
2982
2983    .. code-block:: makefile
2984
2985       $(TARGET): $(OBJECTS)
2986         $(CHARMC) -o $(TARGET) -L/path-to-the-lib $(OBJS) -module FooLB
2987
2988 #. **runtime options:**
2989
2990    Runtime balancer selection options are similar to the compile time
2991    options as described above, but they can be used to override those
2992    compile time options.
2993
2994    -  | *+balancer help*
2995       | displays all available balancers that have been linked in.
2996
2997    -  | *+balancer GreedyCommLB*
2998       | invokes GreedyCommLB
2999
3000    -  | *+balancer GreedyCommLB +balancer RefineLB*
3001       | invokes GreedyCommLB at the first load balancing step and
3002         RefineLB in all subsequent load balancing steps.
3003
3004    -  | *+balancer ComboCentLB:GreedyLB,RefineLB*
3005       | same as the example in the -balancer compile time option.
3006
3007    Note: +balancer option works only if you have already linked the
3008    corresponding load balancers module at compile time. Giving +balancer
3009    with a wrong LB name will result in a runtime error. When you have
3010    used -balancer A as compile time option, you do not need to use
3011    +balancer A again to activate it at runtime. However, you can use
3012    +balancer B to override the compile time option and choose to
3013    activate B instead of A.
3014
3015 #. **Handling the case that no load balancer is activated by users**
3016
3017    When no balancer is linked by users, but the program counts on a load
3018    balancer because it used *AtSync()* and expect *ResumeFromSync()* to
3019    be called to continue, a special load balancer called *NullLB* will
3020    be automatically created to run the program. This default load
3021    balancer calls *ResumeFromSync()* after *AtSync()*. It keeps a
3022    program from hanging after calling *AtSync()*. *NullLB* will be
3023    suppressed if another load balancer is created.
3024
3025 #. **Other useful runtime options**
3026
3027    There are a few other runtime options for load balancing that may be
3028    useful:
3029
3030    -  | *+LBDebug {verbose level}*
3031       | {verbose level} can be any positive integer number. 0 is to turn
3032         off the verbose. This option asks load balancer to output load
3033         balancing information to stdout. The bigger the verbose level
3034         is, the more verbose the output is.
3035
3036    -  | *+LBPeriod {seconds}*
3037       | {Seconds} can be any float number. This option sets the minimum
3038         period time in seconds between two consecutive load balancing
3039         steps. The default value is 1 second. That is to say that a load
3040         balancing step will not happen until 1 second after the last
3041         load balancing step.
3042
3043    -  | *+LBSameCpus*
3044       | This option simply tells load balancer that all processors are
3045         of same speed. The load balancer will then skip the measurement
3046         of CPU speed at runtime. This is the default.
3047
3048    -  | *+LBTestPESpeed*
3049       | This option tells the load balancer to test the speed of all
3050         processors at runtime. The load balancer may use this
3051         measurement to perform speed-aware load balancing.
3052
3053    -  | *+LBObjOnly*
3054       | This tells load balancer to ignore processor background load
3055         when making migration decisions.
3056
3057    -  | *+LBSyncResume*
3058       | After load balancing step, normally a processor can resume
3059         computation once all objects are received on that processor,
3060         even when other processors are still working on migrations. If
3061         this turns out to be a problem, that is when some processors
3062         start working on computation while the other processors are
3063         still busy migrating objects, then this option can be used to
3064         force a global barrier on all processors to make sure that
3065         processors can only resume computation after migrations are
3066         completed on all processors.
3067
3068    -  | *+LBOff*
3069       | This option turns off load balancing instrumentation of both CPU
3070         and communication usage at startup time.
3071
3072    -  | *+LBCommOff*
3073       | This option turns off load balancing instrumentation of
3074         communication at startup time. The instrument of CPU usage is
3075         left on.
3076
3077 .. _seedlb:
3078
3079 Seed load balancers - load balancing Chares at creation time
3080 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3081
3082 Seed load balancing involves the movement of object creation messages,
3083 or "seeds", to create a balance of work across a set of processors. This
3084 seed load balancing scheme is used to balance chares at creation time.
3085 After the chare constructor is executed on a processor, the seed
3086 balancer does not migrate it. Depending on the movement strategy,
3087 several seed load balancers are available now. Examples can be found
3088 ``examples/charm++/NQueen``.
3089
3090 #. | *random*
3091    | A strategy that places seeds randomly when they are created and
3092      does no movement of seeds thereafter. This is used as the default
3093      seed load balancer.
3094
3095 #. | *neighbor*
3096    | A strategy which imposes a virtual topology on the processors, load
3097      exchange happens among neighbors only. The overloaded processors
3098      initiate the load balancing and send work to its neighbors when it
3099      becomes overloaded. The default topology is mesh2D, one can use
3100      command line option to choose other topology such as ring, mesh3D
3101      and dense graph.
3102
3103 #. | *spray*
3104    | A strategy which imposes a spanning tree organization on the
3105      processors, results in communication via global reduction among all
3106      processors to compute global average load via periodic reduction.
3107      It uses averaging of loads to determine how seeds should be
3108      distributed.
3109
3110 #. | *workstealing*
3111    | A strategy that the idle processor requests a random processor and
3112      steal chares.
3113
3114 Other strategies can also be explored by following the simple API of the
3115 seed load balancer.
3116
3117 **Compile and run time options for seed load balancers**
3118
3119 To choose a seed load balancer other than the default *rand* strategy,
3120 use link time command line option **-balance foo**.
3121
3122 When using neighbor seed load balancer, one can also specify the virtual
3123 topology at runtime. Use **+LBTopo topo**, where *topo* can be one of:
3124 (a) ring, (b) mesh2d, (c) mesh3d and (d) graph.
3125
3126 To write a seed load balancer, name your file as *cldb.foo.c*, where
3127 *foo* is the strategy name. Compile it in the form of library under
3128 charm/lib, named as *libcldb-foo.a*, where *foo* is the strategy name
3129 used above. Now one can use **-balance foo** as compile time option to
3130 **charmc** to link with the *foo* seed load balancer.
3131
3132 .. _lbexample:
3133
3134 Simple Load Balancer Usage Example - Automatic with Sync LB
3135 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3136
3137 A simple example of how to use a load balancer in sync mode in one’s
3138 application is presented below.
3139
3140 ::
3141
3142    /*** lbexample.ci ***/
3143    mainmodule lbexample {
3144      readonly CProxy_Main mainProxy;
3145      readonly int nElements;
3146
3147      mainchare Main {
3148        entry Main(CkArgMsg *m);
3149        entry void done(void);
3150      };
3151
3152      array [1D] LBExample {
3153        entry LBExample(void);
3154        entry void doWork();
3155      };
3156    };
3157
3158 ——————————————————————————-
3159
3160 ::
3161
3162    /*** lbexample.C ***/
3163    #include <stdio.h>
3164    #include "lbexample.decl.h"
3165
3166    /*readonly*/ CProxy_Main mainProxy;
3167    /*readonly*/ int nElements;
3168
3169    #define MAX_WORK_CNT 50
3170    #define LB_INTERVAL 5
3171
3172    /*mainchare*/
3173    class Main : public CBase_Main
3174    {
3175    private:
3176      int count;
3177    public:
3178      Main(CkArgMsg* m)
3179      {
3180        /*....Initialization....*/
3181        mainProxy = thisProxy;
3182        CProxy_LBExample arr = CProxy_LBExample::ckNew(nElements);
3183        arr.doWork();
3184      };
3185
3186      void done(void)
3187      {
3188        count++;
3189        if(count==nElements){
3190          CkPrintf("All done");
3191          CkExit();
3192        }
3193      };
3194    };
3195
3196    /*array [1D]*/
3197    class LBExample : public CBase_LBExample
3198    {
3199    private:
3200      int workcnt;
3201    public:
3202      LBExample()
3203      {
3204        workcnt=0;
3205        /* May initialize some variables to be used in doWork */
3206        //Must be set to true to make AtSync work
3207        usesAtSync = true;
3208      }
3209
3210      LBExample(CkMigrateMessage *m) { /* Migration constructor -- invoked when chare migrates */ }
3211
3212      /* Must be written for migration to succeed */
3213      void pup(PUP::er &p){
3214        p|workcnt;
3215        /* There may be some more variables used in doWork */
3216      }
3217
3218      void doWork()
3219      {
3220        /* Do work proportional to the chare index to see the effects of LB */
3221
3222        workcnt++;
3223        if(workcnt==MAX_WORK_CNT)
3224          mainProxy.done();
3225
3226        if(workcnt%LB_INTERVAL==0)
3227          AtSync();
3228        else
3229          doWork();
3230      }
3231
3232      void ResumeFromSync(){
3233        doWork();
3234      }
3235    };
3236
3237    #include "lbexample.def.h"
3238
3239 Processor-Aware Chare Collections
3240 ---------------------------------
3241
3242 So far, we have discussed chares separately from the underlying hardware
3243 resources to which they are mapped. However, for writing lower-level
3244 libraries or optimizing application performance it is sometimes useful
3245 to create chare collections where a single chare is mapped per specified
3246 resource used in the run. The group  [8]_ and node group constructs
3247 provide this facility by creating a collection of chares with a single
3248 chare (or branch) on each PE (in the case of groups) or process (for
3249 node groups).
3250
3251 .. _sec:group:
3252
3253 Group Objects
3254 ~~~~~~~~~~~~~
3255
3256 Groups have a definition syntax similar to normal chares, and they have
3257 to inherit from the system-defined class CBase_ClassName, where
3258 ClassName is the name of the group’s C++ class  [9]_.
3259
3260 Group Definition
3261 ^^^^^^^^^^^^^^^^
3262
3263 In the interface (``.ci``) file, we declare
3264
3265 ::
3266
3267    group Foo {
3268      // Interface specifications as for normal chares
3269
3270      // For instance, the constructor ...
3271      entry Foo(parameters1);
3272
3273      // ... and an entry method
3274      entry void someEntryMethod(parameters2);
3275    };
3276
3277 The definition of the ``Foo`` class is given in the ``.h`` file, as
3278 follows:
3279
3280 ::
3281
3282    class Foo : public CBase_Foo {
3283      // Data and member functions as in C++
3284      // Entry functions as for normal chares
3285
3286      public:
3287        Foo(parameters1);
3288        void someEntryMethod(parameters2);
3289    };
3290
3291 .. _sec:groups/creation:
3292
3293 Group Creation
3294 ^^^^^^^^^^^^^^
3295
3296 Groups are created using ckNew like chares and chare arrays. Given the
3297 declarations and definitions of group ``Foo`` from above, we can create
3298 a group in the following manner:
3299
3300 ::
3301
3302    CProxy_Foo fooProxy = CProxy_Foo::ckNew(parameters1);
3303
3304 One can also use ckNew to get a CkGroupID as shown below:
3305
3306 ::
3307
3308    CkGroupID fooGroupID = CProxy_Foo::ckNew(parameters1);
3309
3310 A CkGroupID is useful to specify dependence in group creations using
3311 CkEntryOptions. For example, in the following code, the creation of
3312 group ``GroupB`` on each PE depends on the creation of ``GroupA`` on
3313 that PE.
3314
3315 ::
3316
3317    // Create GroupA
3318    CkGroupID groupAID = CProxy_GroupA::ckNew(parameters1);
3319
3320    // Create GroupB. However, for each PE, do this only
3321    // after GroupA has been created on it
3322
3323    // Specify the dependency through a `CkEntryOptions' object
3324    CkEntryOptions opts;
3325    opts.setGroupDepID(groupAId);
3326
3327    // The last argument to `ckNew' is the `CkEntryOptions' object from above
3328    CkGroupID groupBID = CProxy_GroupB::ckNew(parameters2, opts);
3329
3330 Note that there can be several instances of each group type. In such a
3331 case, each instance has a unique group identifier, and its own set of
3332 branches.
3333
3334 Method Invocation on Groups
3335 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
3336
3337 An asynchronous entry method can be invoked on a particular branch of a
3338 group through a proxy of that group. If we have a group with a proxy
3339 ``fooProxy`` and we wish to invoke entry method ``someEntryMethod`` on
3340 that branch of the group which resides on PE ``somePE``, we would
3341 accomplish this with the following syntax:
3342
3343 ::
3344
3345    fooProxy[somePE].someEntryMethod(parameters);
3346
3347 This call is asynchronous and non-blocking; it returns immediately after
3348 sending the message. A message may be broadcast to all branches of a
3349 group (i.e., to all PEs) using the notation :
3350
3351 ::
3352
3353    fooProxy.anotherEntryMethod(parameters);
3354
3355 This invokes entry method anotherEntryMethod with the given parameters
3356 on all branches of the group. This call is also asynchronous and
3357 non-blocking, and it, too, returns immediately after sending the
3358 message.
3359
3360 Recall that each PE hosts a branch of every instantiated group.
3361 Sequential objects, chares and other groups can gain access to this
3362 *PE-local* branch using ckLocalBranch():
3363
3364 ::
3365
3366    GroupType *g=groupProxy.ckLocalBranch();
3367
3368 This call returns a regular C++ pointer to the actual object (not a proxy)
3369 referred to by the proxy groupProxy. Once a proxy to the local branch of
3370 a group is obtained, that branch can be accessed as a regular C++ object.
3371 Its public methods can return values, and its public data is readily
3372 accessible.
3373
3374 Let us end with an example use-case for groups. Suppose that we have a
3375 task-parallel program in which we dynamically spawn new chares.
3376 Furthermore, assume that each one of these chares has some data to send
3377 to the mainchare. Instead of creating a separate message for each
3378 chare’s data, we create a group. When a particular chare finishes its
3379 work, it reports its findings to the local branch of the group. When all
3380 the chares on a PE have finished their work, the local branch can send a
3381 single message to the main chare. This reduces the number of messages
3382 sent to the mainchare from the number of chares created to the number of
3383 processors.
3384
3385 For a more concrete example on how to use groups, please refer to
3386 ``examples/charm++/histogram_group``. It presents a parallel
3387 histogramming operation in which chare array elements funnel their bin
3388 counts through a group, instead of contributing directly to a reduction
3389 across all chares.
3390
3391 NodeGroup Objects
3392 ~~~~~~~~~~~~~~~~~
3393
3394 The *node group* construct is similar to the group construct discussed
3395 above. Rather than having one chare per PE, a node group is a collection
3396 of chares with one chare per *process*, or *logical node*. Therefore,
3397 each logical node hosts a single branch of the node group. As with
3398 groups, node groups can be addressed via globally unique identifiers.
3399 Nonetheless, there are significant differences in the semantics of node
3400 groups as compared to groups and chare arrays. When an entry method of a
3401 node group is executed on one of its branches, it executes on *some* PE
3402 within the logical node. Also, multiple entry method calls can execute
3403 concurrently on a single node group branch. This makes node groups
3404 significantly different from groups and requires some care when using
3405 them.
3406
3407 NodeGroup Declaration
3408 ^^^^^^^^^^^^^^^^^^^^^
3409
3410 Node groups are defined in a similar way to groups.  [10]_ For example,
3411 in the interface file, we declare:
3412
3413 ::
3414
3415     nodegroup NodeGroupType {
3416      // Interface specifications as for normal chares
3417     };
3418
3419 In the ``.h`` file, we define NodeGroupType as follows:
3420
3421 ::
3422
3423     class NodeGroupType : public CBase_NodeGroupType {
3424      // Data and member functions as in C++
3425      // Entry functions as for normal chares
3426     };
3427
3428 Like groups, NodeGroups are identified by a globally unique identifier
3429 of type CkGroupID. Just as with groups, this identifier is common to all
3430 branches of the NodeGroup, and can be obtained from the inherited data
3431 member thisgroup. There can be many instances corresponding to a single
3432 NodeGroup type, and each instance has a different identifier, and its
3433 own set of branches.
3434
3435 Method Invocation on NodeGroups
3436 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
3437
3438 As with chares, chare arrays and groups, entry methods are invoked on
3439 NodeGroup branches via proxy objects. An entry method may be invoked on
3440 a *particular* branch of a nodegroup by specifying a *logical node
3441 number* argument to the square bracket operator of the proxy object. A
3442 broadcast is expressed by omitting the square bracket notation. For
3443 completeness, example syntax for these two cases is shown below:
3444
3445 ::
3446
3447     // Invoke `someEntryMethod' on the i-th logical node of
3448     // a NodeGroup whose proxy is `myNodeGroupProxy':
3449     myNodeGroupProxy[i].someEntryMethod(parameters);
3450
3451     // Invoke `someEntryMethod' on all logical nodes of
3452     // a NodeGroup whose proxy is `myNodeGroupProxy':
3453     myNodeGroupProxy.someEntryMethod(parameters);
3454
3455 It is worth restating that when an entry method is invoked on a
3456 particular branch of a nodegroup, it may be executed by *any* PE in that
3457 logical node. Thus two invocations of a single entry method on a
3458 particular branch of a NodeGroup may be executed *concurrently* by two
3459 different PEs in the logical node. If this could cause data races in
3460 your program, please consult § :numref:`sec:nodegroups/exclusive`
3461 (below).
3462
3463 .. _sec:nodegroups/exclusive:
3464
3465 NodeGroups and exclusive Entry Methods
3466 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
3467
3468 Node groups may have exclusive entry methods. The execution of an
3469 exclusive entry method invocation is *mutually exclusive* with those of
3470 all other exclusive entry methods invocations. That is, an exclusive
3471 entry method invocation is not executed on a logical node as long as
3472 another exclusive entry method is executing on it. More explicitly, if a
3473 method M of a nodegroup NG is marked exclusive, it means that while an
3474 instance of M is being executed by a PE within a logical node, no other
3475 PE within that logical node will execute any other *exclusive* methods.
3476 However, PEs in the logical node may still execute *non-exclusive* entry
3477 method invocations. An entry method can be marked exclusive by tagging
3478 it with the exclusive attribute, as explained in
3479 § :numref:`attributes`.
3480
3481 Accessing the Local Branch of a NodeGroup
3482 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
3483
3484 The local branch of a NodeGroup NG, and hence its member fields and
3485 methods, can be accessed through the method NG\*
3486 CProxy_NG::ckLocalBranch() of its proxy. Note that accessing data
3487 members of a NodeGroup branch in this manner is *not* thread-safe by
3488 default, although you may implement your own mutual exclusion schemes to
3489 ensure safety. One way to ensure safety is to use node-level locks,
3490 which are described in the Converse manual.
3491
3492 NodeGroups can be used in a similar way to groups so as to implement
3493 lower-level optimizations such as data sharing and message reduction.
3494
3495 Initializations at Program Startup
3496 ----------------------------------
3497
3498 .. _initnode:
3499 .. _initproc:
3500
3501 initnode and initproc Routines
3502 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3503
3504 Some registration routines need be executed
3505 exactly once before the computation begins. You may choose to declare a
3506 regular C++ subroutine initnode in the .ci file to ask Charm++ to execute
3507 the routine exactly once on *every logical node* before the computation
3508 begins, or to declare a regular C++ subroutine initproc to be executed
3509 exactly once on *every PE*.
3510
3511 ::
3512
3513    module foo {
3514        initnode void fooNodeInit(void);
3515        initproc void fooProcInit(void);
3516        chare bar {
3517            ...
3518            initnode void barNodeInit(void);
3519            initproc void barProcInit(void);
3520        };
3521    };
3522
3523 This code will execute the routines fooNodeInit and static
3524 bar::barNodeInit once on every logical node and fooProcInit and
3525 bar::barProcInit on every PE before the main computation starts.
3526 Initnode calls are always executed before initproc calls. Both init
3527 calls (declared as static member functions) can be used in chares, chare
3528 arrays and groups.
3529
3530 Note that these routines should only implement registration and startup
3531 functionality, and not parallel computation, since the Charm++ run time
3532 system will not have started up fully when they are invoked. In order to
3533 begin the parallel computation, you should use a mainchare instead,
3534 which gets executed on only PE 0.
3535
3536 Event Sequence During Charm++ Startup
3537 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3538
3539 At startup, every Charm++ program performs the following actions, in
3540 sequence:
3541
3542 #. Module Registration: all modules given in the .ci files are
3543    registered in the order of their specification in the linking stage
3544    of program compilation. For example, if you specified
3545    “``-module A -module B``” while linking your Charm++ program, then
3546    module ``A`` is registered before module ``B`` at runtime.
3547
3548 #. initnode, initproc Calls: all initnode and initproc functions are
3549    invoked before the creation of Charm++ data structures, and before
3550    the invocation of any mainchares’ main() methods.
3551
3552 #. readonly Variables: readonly variables are initialized on PE 0 in the
3553    mainchare, following program order as given in the ``main()`` method.
3554    After initialization, they are broadcast to all other PEs making them
3555    available in the constructors groups, chares, chare arrays, etc. (see
3556    below.)
3557
3558 #. Group and NodeGroup Creation: on PE 0, constructors of these objects
3559    are invoked in program order. However, on all other PEs, their
3560    creation is triggered by messages. Since message order is not
3561    guaranteed in Charm++ program, constructors of groups and nodegroups
3562    should **not** depend on other Group or NodeGroup objects on a PE.
3563    However, if your program structure requires it, you can explicitly
3564    specify that the creation of certain Groups/NodeGroups depends on the
3565    creation of others, as described in
3566    § :numref:`sec:groups/creation`. In addition, since those
3567    objects are initialized after the initialization of readonly
3568    variables, readonly variables can be used in the constructors of
3569    Groups and NodeGroups.
3570
3571 #. Charm++ Array Creation: the order in which array constructors are
3572    called on PEs is similar to that described for groups and nodegroups,
3573    above. Therefore, the creation of one array should **not** depend on
3574    other arrays. As Array objects are initialized last, their
3575    constructors can use readonly variables and local branches of Group
3576    or NodeGroup objects.
3577
3578 Advanced Programming Techniques
3579 ===============================
3580
3581 Optimizing Entry Method Invocation
3582 ----------------------------------
3583
3584 .. _messages:
3585
3586 Messages
3587 ~~~~~~~~
3588
3589 Although Charm++ supports automated parameter marshalling for entry
3590 methods, you can also manually handle the process of packing and
3591 unpacking parameters by using messages. A message encapsulates all the
3592 parameters sent to an entry method. Since the parameters are already
3593 encapsulated, sending messages is often more efficient than parameter
3594 marshalling, and can help to avoid unnecessary copying. Moreover, assume
3595 that the receiver is unable to process the contents of the message at
3596 the time that it receives it. For example, consider a tiled matrix
3597 multiplication program, wherein each chare receives an :math:`A`-tile
3598 and a :math:`B`-tile before computing a partial result for
3599 :math:`C = A \times B`. If we were using parameter marshalled entry
3600 methods, a chare would have to copy the first tile it received, in order
3601 to save it for when it has both the tiles it needs. Then, upon receiving
3602 the second tile, the chare would use the second tile and the first
3603 (saved) tile to compute a partial result. However, using messages, we
3604 would just save a *pointer* to the message encapsulating the tile
3605 received first, instead of the tile data itself.
3606
3607 **Managing the memory buffer associated with a message.** As suggested
3608 in the example above, the biggest difference between marshalled
3609 parameters and messages is that an entry method invocation is assumed to
3610 *keep* the message that it is passed. That is, the Charm++ runtime
3611 system assumes that code in the body of the invoked entry method will
3612 explicitly manage the memory associated with the message that it is
3613 passed. Therefore, in order to avoid leaking memory, the body of an
3614 entry method must either delete the message that it is receives, or save
3615 a pointer to it, and delete it a later point in the execution of the
3616 code.
3617
3618 Moreover, in the Charm++ execution model, once you pass a message buffer
3619 to the runtime system (via an asynchronous entry method invocation), you
3620 should *not* reuse the buffer. That is, after you have passed a message
3621 buffer into an asynchronous entry method invocation, you shouldn’t
3622 access its fields, or pass that same buffer into a second entry method
3623 invocation. Note that this rule doesn’t preclude the *single reuse* of
3624 an input message - consider an entry method invocation :math:`i_1`,
3625 which receives as input the message buffer :math:`m_1`. Then,
3626 :math:`m_1` may be passed to an asynchronous entry method invocation
3627 :math:`i_2`. However, once :math:`i_2` has been issued with :math:`m_1`
3628 as its input parameter, :math:`m_1` cannot be used in any further entry
3629 method invocations.
3630
3631 Several kinds of message are available. Regular Charm++ messages are
3632 objects of *fixed size*. One can have messages that contain pointers or
3633 variable length arrays (arrays with sizes specified at runtime) and
3634 still have these pointers as valid when messages are sent across
3635 processors, with some additional coding. Also available is a mechanism
3636 for assigning *priorities* to a message regardless of its type. A
3637 detailed discussion of priorities appears later in this section.
3638
3639 Message Types
3640 ^^^^^^^^^^^^^
3641
3642 **Fixed-Size Messages.** The simplest type of message is a *fixed-size*
3643 message. The size of each data member of such a message should be known
3644 at compile time. Therefore, such a message may encapsulate primitive
3645 data types, user-defined data types that *don’t* maintain pointers to
3646 memory locations, and *static* arrays of the aforementioned types.
3647
3648 **Variable-Size Messages.** Very often, the size of the data contained
3649 in a message is not known until runtime. For such scenarios, you can use
3650 variable-size (*varsize*) messages. A *varsize* message can encapsulate
3651 several arrays, each of whose size is determined at run time. The space
3652 required for these encapsulated, variable length arrays is allocated
3653 with the entire message comprises a contiguous buffer of memory.
3654
3655 **Packed Messages.** A *packed* message is used to communicate
3656 non-linear data structures via messages. However, we defer a more
3657 detailed description of their use to
3658 § :numref:`sec:messages/packed_msgs`.
3659
3660 Using Messages In Your Program
3661 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
3662
3663 There are five steps to incorporating a (fixed or varsize) message type
3664 in your Charm++ program: (1) Declare message type in .ci file; (2)
3665 Define message type in .h file; (3) Allocate message; (4) Pass message
3666 to asynchronous entry method invocation and (5) Deallocate message to
3667 free associated memory resources.
3668
3669 **Declaring Your Message Type.** Like all other entities involved in
3670 asynchronous entry method invocation, messages must be declared in the
3671 ``.ci`` file. This allows the Charm++ translator to generate support
3672 code for messages. Message declaration is straightforward for fixed-size
3673 messages. Given a message of type ``MyFixedSizeMsg``, simply include the
3674 following in the .ci file:
3675
3676 ::
3677
3678     message MyFixedSizeMsg;
3679
3680 For varsize messages, the .ci declaration must also include the names
3681 and types of the variable-length arrays that the message will
3682 encapsulate. The following example illustrates this requirement. In it,
3683 a message of type ``MyVarsizeMsg``, which encapsulates three
3684 variable-length arrays of different types, is declared:
3685
3686 ::
3687
3688     message MyVarsizeMsg {
3689       int arr1[];
3690       double arr2[];
3691       MyPointerlessStruct arr3[];
3692     };
3693
3694 **Defining Your Message Type.** Once a message type has been declared to
3695 the Charm++ translator, its type definition must be provided. Your
3696 message type must inherit from a specific generated base class. If the
3697 type of your message is ``T``, then ``class T`` must inherit from
3698 ``CMessage_T``. This is true for both fixed and varsize messages. As an
3699 example, for our fixed size message type ``MyFixedSizeMsg`` above, we
3700 might write the following in the .h file:
3701
3702 ::
3703
3704    class MyFixedSizeMsg : public CMessage_MyFixedSizeMsg {
3705      int var1;
3706      MyPointerlessStruct var2;
3707      double arr3[10];
3708
3709      // Normal C++ methods, constructors, etc. go here
3710    };
3711
3712 In particular, note the inclusion of the static array of ``double``\ s,
3713 ``arr3``, whose size is known at compile time to be that of ten
3714 ``double``\ s. Similarly, for our example varsize message of type
3715 ``MyVarsizeMsg``, we would write something like:
3716
3717 ::
3718
3719    class MyVarsizeMsg : public CMessage_MyVarsizeMsg {
3720      // variable-length arrays
3721      int *arr1;
3722      double *arr2;
3723      MyPointerlessStruct *arr3;
3724
3725      // members that are not variable-length arrays
3726      int x,y;
3727      double z;
3728
3729      // Normal C++ methods, constructors, etc. go here
3730    };
3731
3732 Note that the .h definition of the class type must contain data members
3733 whose names and types match those specified in the .ci declaration. In
3734 addition, if any of data members are private or protected, it should
3735 declare class CMessage_MyVarsizeMsg to be a friend class. Finally, there
3736 are no limitations on the member methods of message classes, except that
3737 the message class may not redefine operators ``new`` or ``delete``.
3738
3739 Thus the mtype class declaration should be similar to:
3740
3741 **Creating a Message.** With the .ci declaration and .h definition in
3742 place, messages can be allocated and used in the program. Messages are
3743 allocated using the C++ new operator:
3744
3745 ::
3746
3747     MessageType *msgptr =
3748      new [(int sz1, int sz2, ... , int priobits=0)] MessageType[(constructor arguments)];
3749
3750 The arguments enclosed within the square brackets are optional, and are
3751 used only when allocating messages with variable length arrays or
3752 prioritized messages. These arguments are not specified for fixed size
3753 messages. For instance, to allocate a message of our example message
3754 ``MyFixedSizeMsg``, we write:
3755
3756 ::
3757
3758    MyFixedSizeMsg *msg = new MyFixedSizeMsg(<constructor args>);
3759
3760 In order to allocate a varsize message, we must pass appropriate values
3761 to the arguments of the overloaded new operator presented previously.
3762 Arguments sz1, sz2, ... denote the size (in number of elements) of the
3763 memory blocks that need to be allocated and assigned to the pointers
3764 (variable-length arrays) that the message contains. The priobits
3765 argument denotes the size of a bitvector (number of bits) that will be
3766 used to store the message priority. So, if we wanted to create
3767 ``MyVarsizeMsg`` whose ``arr1``, ``arr2`` and ``arr3`` arrays contain
3768 10, 20 and 7 elements of their respective types, we would write:
3769
3770 ::
3771
3772    MyVarsizeMsg *msg = new (10, 20, 7) MyVarsizeMsg(<constructor args>);
3773
3774 Further, to add a 32-bit priority bitvector to this message, we would
3775 write:
3776
3777 ::
3778
3779    MyVarsizeMsg *msg = new (10, 20, 7, sizeof(uint32_t)*8) VarsizeMessage;
3780
3781 Notice the last argument to the overloaded new operator, which specifies
3782 the number of bits used to store message priority. The section on
3783 prioritized execution (§ :numref:`prioritized message passing`)
3784 describes how priorities can be employed in your program.
3785
3786 Another version of the overloaded new operator allows you to pass in an
3787 array containing the size of each variable-length array, rather than
3788 specifying individual sizes as separate arguments. For example, we could
3789 create a message of type ``MyVarsizeMsg`` in the following manner:
3790
3791 ::
3792
3793    int sizes[3];
3794    sizes[0] = 10;               // arr1 will have 10 elements
3795    sizes[1] = 20;               // arr2 will have 20 elements
3796    sizes[2] = 7;                // arr3 will have 7 elements
3797
3798    MyVarsizeMsg *msg = new(sizes, 0) MyVarsizeMsg(<constructor args>); // 0 priority bits
3799
3800 **Sending a Message.** Once we have a properly allocated message, we can
3801 set the various elements of the encapsulated arrays in the following
3802 manner:
3803
3804 ::
3805
3806      msg->arr1[13] = 1;
3807      msg->arr2[5] = 32.82;
3808      msg->arr3[2] = MyPointerlessStruct();
3809      // etc.
3810
3811 And pass it to an asynchronous entry method invocation, thereby sending
3812 it to the corresponding chare:
3813
3814 ::
3815
3816    myChareArray[someIndex].foo(msg);
3817
3818 When a message is *sent*, i.e. passed to an asynchronous entry method
3819 invocation, the programmer relinquishes control of it; the space
3820 allocated for the message is freed by the runtime system. However, when
3821 a message is *received* at an entry point, it is *not* freed by the
3822 runtime system. As mentioned at the start of this section, received
3823 messages may be reused or deleted by the programmer. Finally, messages
3824 are deleted using the standard C++ delete operator.
3825
3826 .. _message packing:
3827
3828 Message Packing
3829 ^^^^^^^^^^^^^^^
3830
3831 The Charm++ interface translator generates implementation for three
3832 static methods for the message class CMessage_mtype. These methods have
3833 the prototypes:
3834
3835 ::
3836
3837        static void* alloc(int msgnum, size_t size, int* array, int priobits);
3838        static void* pack(mtype*);
3839        static mtype* unpack(void*);
3840
3841 One may choose not to use the translator-generated methods and may
3842 override these implementations with their own alloc, pack and unpack
3843 static methods of the mtype class. The alloc method will be called when
3844 the message is allocated using the C++ new operator. The programmer never
3845 needs to explicitly call it. Note that all elements of the message are
3846 allocated when the message is created with new. There is no need to call
3847 new to allocate any of the fields of the message. This differs from a
3848 packed message where each field requires individual allocation. The
3849 alloc method should actually allocate the message using CkAllocMsg,
3850 whose signature is given below:
3851
3852 ::
3853
3854    void *CkAllocMsg(int msgnum, int size, int priobits);
3855
3856 For varsize messages, these static methods ``alloc``, ``pack``, and
3857 ``unpack`` are generated by the interface translator. For example, these
3858 methods for the VarsizeMessage class above would be similar to:
3859
3860 ::
3861
3862    // allocate memory for varmessage so charm can keep track of memory
3863    static void* alloc(int msgnum, size_t size, int* array, int priobits)
3864    {
3865      int totalsize, first_start, second_start;
3866      // array is passed in when the message is allocated using new (see below).
3867      // size is the amount of space needed for the part of the message known
3868      // about at compile time.  Depending on their values, sometimes a segfault
3869      // will occur if memory addressing is not on 8-byte boundary, so altered
3870      // with ALIGN8
3871      first_start = ALIGN8(size);  // 8-byte align with this macro
3872      second_start = ALIGN8(first_start + array[0]*sizeof(int));
3873      totalsize = second_start + array[1]*sizeof(double);
3874      VarsizeMessage* newMsg =
3875        (VarsizeMessage*) CkAllocMsg(msgnum, totalsize, priobits);
3876      // make firstArray point to end of newMsg in memory
3877      newMsg->firstArray = (int*) ((char*)newMsg + first_start);
3878      // make secondArray point to after end of firstArray in memory
3879      newMsg->secondArray = (double*) ((char*)newMsg + second_start);
3880
3881      return (void*) newMsg;
3882    }
3883
3884    // returns pointer to memory containing packed message
3885    static void* pack(VarsizeMessage* in)
3886    {
3887      // set firstArray an offset from the start of in
3888      in->firstArray = (int*) ((char*)in->firstArray - (char*)in);
3889      // set secondArray to the appropriate offset
3890      in->secondArray = (double*) ((char*)in->secondArray - (char*)in);
3891      return in;
3892    }
3893
3894    // returns new message from raw memory
3895    static VarsizeMessage* VarsizeMessage::unpack(void* inbuf)
3896    {
3897      VarsizeMessage* me = (VarsizeMessage*)inbuf;
3898      // return first array to absolute address in memory
3899      me->firstArray = (int*) ((size_t)me->firstArray + (char*)me);
3900      // likewise for secondArray
3901      me->secondArray = (double*) ((size_t)me->secondArray + (char*)me);
3902      return me;
3903    }
3904
3905 The pointers in a varsize message can exist in two states. At creation,
3906 they are valid C++ pointers to the start of the arrays. After packing,
3907 they become offsets from the address of the pointer variable to the
3908 start of the pointed-to data. Unpacking restores them to pointers.
3909
3910 .. _sec:messages/packed_msgs:
3911
3912 Custom Packed Messages
3913 ''''''''''''''''''''''
3914
3915 In many cases, a message must store a *non-linear* data structure using
3916 pointers. Examples of these are binary trees, hash tables etc. Thus, the
3917 message itself contains only a pointer to the actual data. When the
3918 message is sent to the same processor, these pointers point to the
3919 original locations, which are within the address space of the same
3920 processor. However, when such a message is sent to other processors,
3921 these pointers will point to invalid locations.
3922
3923 Thus, the programmer needs a way to “serialize” these messages *only if*
3924 the message crosses the address-space boundary. Charm++ provides a way
3925 to do this serialization by allowing the developer to override the
3926 default serialization methods generated by the Charm++ interface
3927 translator. Note that this low-level serialization has nothing to do
3928 with parameter marshalling or the PUP framework described later.
3929
3930 Packed messages are declared in the ``.ci`` file the same way as
3931 ordinary messages:
3932
3933 ::
3934
3935    message PMessage;
3936
3937 Like all messages, the class PMessage needs to inherit from
3938 CMessage_PMessage and should provide two *static* methods: pack and
3939 unpack. These methods are called by the Charm++ runtime system, when the
3940 message is determined to be crossing address-space boundary. The
3941 prototypes for these methods are as follows:
3942
3943 ::
3944
3945    static void *PMessage::pack(PMessage *in);
3946    static PMessage *PMessage::unpack(void *in);
3947
3948 Typically, the following tasks are done in pack method:
3949
3950 -  Determine size of the buffer needed to serialize message data.
3951
3952 -  Allocate buffer using the CkAllocBuffer function. This function takes
3953    in two parameters: input message, and size of the buffer needed, and
3954    returns the buffer.
3955
3956 -  Serialize message data into buffer (along with any control
3957    information needed to de-serialize it on the receiving side.
3958
3959 -  Free resources occupied by message (including message itself.)
3960
3961 On the receiving processor, the unpack method is called. Typically, the
3962 following tasks are done in the unpack method:
3963
3964 -  Allocate message using CkAllocBuffer function. *Do not use new to
3965    allocate message here. If the message constructor has to be called,
3966    it can be done using the in-place new operator.*
3967
3968 -  De-serialize message data from input buffer into the allocated
3969    message.
3970
3971 -  Free the input buffer using CkFreeMsg.
3972
3973 Here is an example of a packed-message implementation:
3974
3975 ::
3976
3977    // File: pgm.ci
3978    mainmodule PackExample {
3979      ...
3980      message PackedMessage;
3981      ...
3982    };
3983
3984    // File: pgm.h
3985    ...
3986    class PackedMessage : public CMessage_PackedMessage
3987    {
3988      public:
3989        BinaryTree<char> btree; // A non-linear data structure
3990        static void* pack(PackedMessage*);
3991        static PackedMessage* unpack(void*);
3992        ...
3993    };
3994    ...
3995
3996    // File: pgm.C
3997    ...
3998    void*
3999    PackedMessage::pack(PackedMessage* inmsg)
4000    {
4001      int treesize = inmsg->btree.getFlattenedSize();
4002      int totalsize = treesize + sizeof(int);
4003      char *buf = (char*)CkAllocBuffer(inmsg, totalsize);
4004      // buf is now just raw memory to store the data structure
4005      int num_nodes = inmsg->btree.getNumNodes();
4006      memcpy(buf, &num_nodes, sizeof(int));  // copy numnodes into buffer
4007      buf = buf + sizeof(int);               // don't overwrite numnodes
4008      // copies into buffer, give size of buffer minus header
4009      inmsg->btree.Flatten((void*)buf, treesize);
4010      buf = buf - sizeof(int);              // don't lose numnodes
4011      delete inmsg;
4012      return (void*) buf;
4013    }
4014
4015    PackedMessage*
4016    PackedMessage::unpack(void* inbuf)
4017    {
4018      // inbuf is the raw memory allocated and assigned in pack
4019      char* buf = (char*) inbuf;
4020      int num_nodes;
4021      memcpy(&num_nodes, buf, sizeof(int));
4022      buf = buf + sizeof(int);
4023      // allocate the message through Charm RTS
4024      PackedMessage* pmsg =
4025        (PackedMessage*)CkAllocBuffer(inbuf, sizeof(PackedMessage));
4026      // call "inplace" constructor of PackedMessage that calls constructor
4027      // of PackedMessage using the memory allocated by CkAllocBuffer,
4028      // takes a raw buffer inbuf, the number of nodes, and constructs the btree
4029      pmsg = new ((void*)pmsg) PackedMessage(buf, num_nodes);
4030      CkFreeMsg(inbuf);
4031      return pmsg;
4032    }
4033    ...
4034    PackedMessage* pm = new PackedMessage();  // just like always
4035    pm->btree.Insert('A');
4036    ...
4037
4038 While serializing an arbitrary data structure into a flat buffer, one
4039 must be very wary of any possible alignment problems. Thus, if possible,
4040 the buffer itself should be declared to be a flat struct. This will
4041 allow the C++ compiler to ensure proper alignment of all its member
4042 fields.
4043
4044 .. _attributes:
4045
4046 Entry Method Attributes
4047 ~~~~~~~~~~~~~~~~~~~~~~~
4048
4049 Charm++ provides a handful of special attributes that entry methods may
4050 have. In order to give a particular entry method an attribute, you must
4051 specify the keyword for the desired attribute in the attribute list of
4052 that entry method’s ``.ci`` file declaration. The syntax for this is as
4053 follows:
4054
4055 ::
4056
4057    entry [attribute1, ..., attributeN] void EntryMethod(parameters);
4058
4059 Charm++ currently offers the following attributes that one may assign to
4060 an entry method: threaded, sync, exclusive, nokeep, notrace, appwork,
4061 immediate, expedited, inline, local, python, reductiontarget, aggregate.
4062
4063 threaded
4064    entry methods run in their own non-preemptible threads. These entry
4065    methods may perform blocking operations, such as calls to a sync
4066    entry method, or explicitly suspending themselves. For more details,
4067    refer to section :numref:`threaded`.
4068
4069 sync
4070    entry methods are special in that calls to them are blocking-they do
4071    not return control to the caller until the method finishes execution
4072    completely. Sync methods may have return values; however, they may
4073    only return messages or data types that have the PUP method
4074    implemented. Callers must run in a thread separate from the runtime
4075    scheduler, e.g. a threaded entry methods. Calls expecting a return
4076    value will receive it as the return from the proxy invocation:
4077
4078    ::
4079
4080        ReturnMsg* m;
4081        m = A[i].foo(a, b, c);
4082
4083    For more details, refer to section :numref:`sync`.
4084
4085 exclusive
4086    entry methods should only exist on NodeGroup objects. One such entry
4087    method will not execute while some other exclusive entry methods
4088    belonging to the same NodeGroup object are executing on the same
4089    node. In other words, if one exclusive method of a NodeGroup object
4090    is executing on node N, and another one is scheduled to run on the
4091    same node, the second exclusive method will wait to execute until the
4092    first one finishes. An example can be found in
4093    ``tests/charm++/pingpong``.
4094
4095 nokeep
4096    entry methods take only a message as their lone argument, and the
4097    memory buffer for this message is managed by the Charm++ runtime
4098    system rather than by the user. This means that the user has to
4099    guarantee that the message will not be buffered for later usage or be
4100    freed in the user code. Additionally, users are not allowed to modify
4101    the contents of a nokeep message, since for a broadcast the same
4102    message can be reused for all entry method invocations on each PE. If
4103    a user frees the message or modifies its contents, a runtime error
4104    may result. An example can be found in
4105    ``examples/charm++/histogram_group``.
4106
4107 notrace
4108    entry methods will not be traced during execution. As a result, they
4109    will not be considered and displayed in Projections for performance
4110    analysis. Additionally, ``immediate`` entry methods are by default
4111    ``notrace`` and will not be traced during execution.
4112
4113 appwork
4114    this entry method will be marked as executing application work. It
4115    will be used for performance analysis.
4116
4117 immediate
4118    entry methods are executed in an “immediate” fashion as they skip the
4119    message scheduling while other normal entry methods do not. Immediate
4120    entry methods can only be associated with NodeGroup objects,
4121    otherwise a compilation error will result. If the destination of such
4122    entry method is on the local node, then the method will be executed
4123    in the context of the regular PE regardless the execution mode of
4124    Charm++ runtime. However, in the SMP mode, if the destination of the
4125    method is on the remote node, then the method will be executed in the
4126    context of the communication thread. For that reason, immediate entry
4127    methods should be used for code that is performance critical and does
4128    not take too long in terms of execution time because long running
4129    entry methods can delay communication by occupying the communication
4130    thread for entry method execution rather than remote communication.
4131
4132    Such entry methods can be useful for implementing
4133    multicasts/reductions as well as data lookup when such operations are
4134    on the performance critical path. On a certain Charm++ PE, skipping
4135    the normal message scheduling prevents the execution of immediate
4136    entry methods from being delayed by entry functions that could take a
4137    long time to finish. Immediate entry methods are implicitly
4138    “exclusive” on each node, meaning that one execution of immediate
4139    message will not be interrupted by another. Function
4140    CmiProbeImmediateMsg() can be called in user codes to probe and
4141    process immediate messages periodically. Also note that ``immediate``
4142    entry methods are by default ``notrace`` and are not traced during
4143    execution. An example of ``immediate`` entry method can be found in
4144    ``examples/charm++/immediateEntryMethod``.
4145
4146 expedited
4147    entry methods skip the priority-based message queue in Charm++
4148    runtime. It is useful for messages that require prompt processing
4149    when adding the immediate attribute to the message does not apply.
4150    Compared with the immediate attribute, the expedited attribute
4151    provides a more general solution that works for all types of Charm++
4152    objects, i.e. Chare, Group, NodeGroup and Chare Array. However,
4153    expedited entry methods will still be scheduled in the lower-level
4154    Converse message queue, and be processed in the order of message
4155    arrival. Therefore, they may still suffer from delays caused by long
4156    running entry methods. An example can be found in
4157    ``examples/charm++/satisfiability``.
4158
4159 inline
4160    entry methods will be called as a normal C++ member function if the
4161    message recipient happens to be on the same PE. The call to the
4162    function will happen inline, and control will return to the calling
4163    function after the inline method completes. Because of this, these
4164    entry methods need to be re-entrant as they could be called multiple
4165    times recursively. Parameters to the inline method will be passed by
4166    reference to avoid any copying, packing, or unpacking of the
4167    parameters. This makes inline calls effective when large amounts of
4168    data are being passed, and copying or packing the data would be an
4169    expensive operation. Perfect forwarding has been implemented to allow
4170    for seamless passing of both lvalue and rvalue references. Note that
4171    calls with rvalue references must take place in the same translation
4172    unit as the .decl.h file to allow for the appropriate template