Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
b51f5dfe04fd813e1c5c5ff27fe1fec7d0385c84
[simgrid.git] / doc / doxygen / module-smpi.doc
1 /** @addtogroup SMPI_API
2
3 This programming environment enables the study of MPI application by
4 emulating them on top of the SimGrid simulator. This is particularly
5 interesting to study existing MPI applications within the comfort of
6 the simulator. The motivation for this work is detailed in the
7 reference article (available at http://hal.inria.fr/inria-00527150).
8
9 Our goal is to enable the study of *unmodified* MPI applications,
10 although we are not quite there yet (see @ref SMPI_what). In
11 addition, you can modify your code to speed up your studies or
12 otherwise increase their scalability (see @ref SMPI_adapting).
13
14 \section SMPI_who Who should use SMPI (and who shouldn't)
15
16 SMPI is now considered as stable and you can use it in production. You
17 may probably want to read the scientific publications that detail the
18 models used and their limits, but this should not be absolutely
19 necessary. If you already fluently write and use MPI applications,
20 SMPI should sound very familiar to you. Use smpicc instead of mpicc,
21 and smpirun instead of mpirun (see below for more details).
22
23 Of course, if you don't know what MPI is, the documentation of SMPI
24 will seem a bit terse to you. You should pick up a good MPI tutorial
25 on the Internet (or a course in your favorite university) and come
26 back to SMPI once you know a bit more about MPI. Alternatively, you
27 may want to turn to the other SimGrid interfaces such as the 
28 \ref MSG_API environment, or the \ref SD_API one.
29
30 \section SMPI_what What can run within SMPI?
31
32 You can run unmodified MPI applications (both C and Fortran) within
33 SMPI, provided that (1) you only use MPI calls that we implemented in
34 MPI and (2) you don't use any globals in your application.
35
36 \subsection SMPI_what_coverage MPI coverage of SMPI
37
38 Our coverage of the interface is very decent, but still incomplete;
39 Given the size of the MPI standard, it may well be that we never
40 implement absolutely all existing primitives. One sided communications
41 and I/O primitives are not targeted for now. Our current state is
42 still very decent: we pass most of the MPICH coverage tests.
43
44 The full list of not yet implemented functions is documented in the
45 file <tt>include/smpi/smpi.h</tt> of the archive, between two lines
46 containing the <tt>FIXME</tt> marker. If you really need a missing
47 feature, please get in touch with us: we can guide you though the
48 SimGrid code to help you implementing it, and we'd glad to integrate
49 it in the main project afterward if you contribute them back.
50
51 \subsection SMPI_what_globals Issues with the globals
52
53 Concerning the globals, the problem comes from the fact that usually,
54 MPI processes run as real UNIX processes while they are all folded
55 into threads of a unique system process in SMPI. Global variables are
56 usually private to each MPI process while they become shared between
57 the processes in SMPI. This point is rather problematic, and currently
58 forces to modify your application to privatize the global variables.
59
60 We tried several techniques to work this around. We used to have a
61 script that privatized automatically the globals through static
62 analysis of the source code, but it was not robust enough to be used
63 in production. This issue, as well as several potential solutions, is
64 discussed in this article: "Automatic Handling of Global Variables for
65 Multi-threaded MPI Programs",
66 available at http://charm.cs.illinois.edu/newPapers/11-23/paper.pdf
67 (note that this article does not deal with SMPI but with a concurrent
68 solution called AMPI that suffers of the same issue). 
69
70 Currently, we have no solution to offer you, because all proposed solutions will
71 modify the performance of your application (in the computational
72 sections). Sacrificing realism for usability is not very satisfying, so we did
73 not implement them yet. You will thus have to modify your application if it uses
74 global variables. We are working on another solution, leveraging distributed
75 simulation to keep each MPI process within a separate system process, but this
76 is far from being ready at the moment.
77
78 \section SMPI_compiling Compiling your code
79
80 This is very simply done with the <tt>smpicc</tt> script. If you
81 already compiled any MPI code before, you already know how to use it.
82 If not, you should try to get your MPI code running on top of MPI
83 before giving SMPI a spin. Actually, that's very simple even if it's
84 the first time you use MPI code: just use smpicc as a compiler (in
85 replacement of gcc or your usual compiler), and you're set.
86
87 \section SMPI_executing Executing your code on top of the simulator
88
89 This is done though the <tt>smpirun</tt> script as follows.
90 <tt>my_hostfile.txt</tt> is a classical MPI hostfile (that is, this
91 file lists the machines on which the processes must be dispatched, one
92 per line)  <tt>my_platform.xml</tt> is a classical SimGrid platform
93 file. Of course, the hosts of the hostfile must exist in the provided
94 platform. <tt>./program</tt> is the MPI program that you want to
95 simulate (must be compiled by <tt>smpicc</tt>) while <tt>-arg</tt> is
96 a command-line parameter passed to this program.
97
98 \verbatim
99 smpirun -hostfile my_hostfile.txt -platform my_platform.xml ./program -arg
100 \endverbatim
101
102 smpirun accepts other parameters, such as <tt>-np</tt> if you don't
103 want to use all the hosts defined in the hostfile, <tt>-map</tt> to
104 display on which host each rank gets mapped of <tt>-trace</tt> to
105 activate the tracing during the simulation. You can get the full list
106 by running
107 \verbatim
108 smpirun -help
109 \endverbatim
110
111 \section SMPI_adapting Adapting your MPI code to the use of SMPI
112
113 As detailed in the reference article (available at
114 http://hal.inria.fr/inria-00527150), you may want to adapt your code
115 to improve the simulation performance. But these tricks may seriously
116 hinder the result quality (or even prevent the app to run) if used
117 wrongly. We assume that if you want to simulate an HPC application,
118 you know what you are doing. Don't prove us wrong!
119
120 \section SMPI_adapting_size Reducing your memory footprint
121
122 If you get short on memory (the whole app is executed on a single node when
123 simulated), you should have a look at the SMPI_SHARED_MALLOC and
124 SMPI_SHARED_FREE macros. It allows to share memory areas between processes: The
125 purpose of these macro is that the same line malloc on each process will point
126 to the exact same memory area. So if you have a malloc of 2M and you have 16
127 processes, this macro will change your memory consumption from 2M*16 to 2M
128 only. Only one block for all processes.
129
130 If your program is ok with a block containing garbage value because all
131 processes write and read to the same place without any kind of coordination,
132 then this macro can dramatically shrink your memory consumption. For example,
133 that will be very beneficial to a matrix multiplication code, as all blocks will
134 be stored on the same area. Of course, the resulting computations will useless,
135 but you can still study the application behavior this way. 
136
137 Naturally, this won't work if your code is data-dependent. For example, a Jacobi
138 iterative computation depends on the result computed by the code to detect
139 convergence conditions, so turning them into garbage by sharing the same memory
140 area between processes does not seem very wise. You cannot use the
141 SMPI_SHARED_MALLOC macro in this case, sorry.
142
143 This feature is demoed by the example file
144 <tt>examples/smpi/NAS/DT-folding/dt.c</tt>
145
146 \section SMPI_adapting_speed Toward faster simulations
147
148 If your application is too slow, try using SMPI_SAMPLE_LOCAL,
149 SMPI_SAMPLE_GLOBAL and friends to indicate which computation loops can
150 be sampled. Some of the loop iterations will be executed to measure
151 their duration, and this duration will be used for the subsequent
152 iterations. These samples are done per processor with
153 SMPI_SAMPLE_LOCAL, and shared between all processors with
154 SMPI_SAMPLE_GLOBAL. Of course, none of this will work if the execution
155 time of your loop iteration are not stable.
156
157 This feature is demoed by the example file 
158 <tt>examples/smpi/NAS/EP-sampling/ep.c</tt>
159
160
161 \section SMPI_collective_algorithms Simulating collective operations
162
163 MPI collective operations can be implemented very differently from one library 
164 to another. Actually, all existing libraries implement several algorithms 
165 for each collective operation, and by default select at runtime which one 
166 should be used for the current operation, depending on the sizes sent, the number
167  of nodes, the communicator, or the communication library being used. These 
168 decisions are based on empirical results and theoretical complexity estimation, 
169 but they can sometimes be suboptimal. Manual selection is possible in these cases, 
170 to allow the user to tune the library and use the better collective if the 
171 default one is not good enough.
172
173 SMPI tries to apply the same logic, regrouping algorithms from OpenMPI, MPICH 
174 libraries, and from StarMPI (<a href="http://star-mpi.sourceforge.net/">STAR-MPI</a>).
175 This collection of more than a hundred algorithms allows a simple and effective
176  comparison of their behavior and performance, making SMPI a tool of choice for the
177 development of such algorithms.
178
179 \subsection Tracing_internals Tracing of internal communications
180
181 For each collective, default tracing only outputs only global data. 
182 Internal communication operations are not traced to avoid outputting too much data
183 to the trace. To debug and compare algorithm, this can be changed with the item 
184 \b tracing/smpi/internals , which has 0 for default value.
185 Here are examples of two alltoall collective algorithms runs on 16 nodes, 
186 the first one with a ring algorithm, the second with a pairwise one :
187
188 \htmlonly
189 <a href="smpi_simgrid_alltoall_ring_16.png" border=0><img src="smpi_simgrid_alltoall_ring_16.png" width="30%" border=0 align="center"></a>
190 <a href="smpi_simgrid_alltoall_pair_16.png" border=0><img src="smpi_simgrid_alltoall_pair_16.png" width="30%" border=0 align="center"></a>
191 <br/>
192 \endhtmlonly
193
194 \subsection Selectors
195
196 The default selection logic implemented by default in OpenMPI (version 1.7) 
197 and MPICH (version 3.0.4) has been replicated and can be used by setting the
198 \b smpi/coll_selector item to either ompi or mpich. The code and details for each 
199 selector can be found in the <tt>src/smpi/colls/smpi_(openmpi/mpich)_selector.c</tt> file.
200 As this is still in development, we do not insure that all algorithms are correctly
201  replicated and that they will behave exactly as the real ones. If you notice a difference,
202 please contact <a href="http://lists.gforge.inria.fr/mailman/listinfo/simgrid-devel">SimGrid developers mailing list</a>
203
204 The default selector uses the legacy algorithms used in versions of SimGrid
205  previous to the 3.10. they should not be used to perform performance study and 
206 may be removed in the future, a different selector being used by default.
207
208 \subsection algos Available algorithms
209
210 For each one of the listed algorithms, several versions are available,
211  either coming from STAR-MPI, MPICH or OpenMPI implementations. Details can be
212  found in the code or in <a href="http://www.cs.arizona.edu/~dkl/research/papers/ics06.pdf">STAR-MPI</a> for STAR-MPI algorithms.
213
214 Each collective can be selected using the corresponding configuration item. For example, to use the pairwise alltoall algorithm, one should add \b --cfg=smpi/alltoall:pair to the line. This will override the selector (for this algorithm only) if provided, allowing better flexibility.
215
216 Warning: Some collective may require specific conditions to be executed correctly (for instance having a communicator with a power of two number of nodes only), which are currently not enforced by Simgrid. Some crashes can be expected while trying these algorithms with unusual sizes/parameters
217
218 \subsubsection MPI_Alltoall
219
220 Most of these are best described in <a href="http://www.cs.arizona.edu/~dkl/research/papers/ics06.pdf">STAR-MPI</a>
221
222  - default : naive one, by default
223  - ompi : use openmpi selector for the alltoall operations
224  - mpich : use mpich selector for the alltoall operations
225  - automatic (experimental) : use an automatic self-benchmarking algorithm 
226  - 2dmesh : organizes the nodes as a two dimensional mesh, and perform allgather 
227 along the dimensions
228  - 3dmesh : adds a third dimension to the previous algorithm
229  - rdb : recursive doubling : extends the mesh to a nth dimension, each one 
230 containing two nodes
231  - pair : pairwise exchange, only works for power of 2 procs, size-1 steps,
232 each process sends and receives from the same process at each step
233  - pair_light_barrier : same, with small barriers between steps to avoid contention
234  - pair_mpi_barrier : same, with MPI_Barrier used
235  - pair_one_barrier : only one barrier at the beginning
236  - ring : size-1 steps, at each step a process send to process (n+i)%size, and receives from (n-i)%size
237  - ring_light_barrier : same, with small barriers between some phases to avoid contention
238  - ring_mpi_barrier : same, with MPI_Barrier used
239  - ring_one_barrier : only one barrier at the beginning
240  - basic_linear :posts all receives and all sends,
241 starts the communications, and waits for all communication to finish
242
243 \subsubsection MPI_Alltoallv
244
245  - default : naive one, by default
246  - ompi : use openmpi selector for the alltoallv operations
247  - mpich : use mpich selector for the alltoallv operations
248  - automatic (experimental) : use an automatic self-benchmarking algorithm 
249  - bruck : same as alltoall
250  - pair : same as alltoall
251  - pair_light_barrier : same as alltoall
252  - pair_mpi_barrier : same as alltoall
253  - pair_one_barrier : same as alltoall
254  - ring : same as alltoall
255  - ring_light_barrier : same as alltoall
256  - ring_mpi_barrier : same as alltoall
257  - ring_one_barrier : same as alltoall
258  - ompi_basic_linear : same as alltoall
259
260
261 \subsubsection MPI_Gather
262
263  - default : naive one, by default
264  - ompi : use openmpi selector for the gather operations
265  - mpich : use mpich selector for the gather operations
266  - automatic (experimental) : use an automatic self-benchmarking algorithm 
267 which will iterate over all implemented versions and output the best
268  - ompi_basic_linear : basic linear algorithm from openmpi, each process sends to the root
269  - ompi_binomial : binomial tree algorithm
270  - ompi_linear_sync : same as basic linear, but with a synchronization at the
271  beginning and message
272 cut into two segments.
273
274 \subsubsection MPI_Barrier
275  - default : naive one, by default
276  - ompi : use openmpi selector for the barrier operations
277  - mpich : use mpich selector for the barrier operations
278  - automatic (experimental) : use an automatic self-benchmarking algorithm 
279  - ompi_basic_linear : all processes send to root
280  - ompi_two_procs : special case for two processes
281  - ompi_bruck : nsteps = sqrt(size), at each step, exchange data with rank-2^k and rank+2^k
282  - ompi_recursivedoubling : recursive doubling algorithm
283  - ompi_tree : recursive doubling type algorithm, with tree structure
284  - ompi_doublering : double ring algorithm
285
286
287 \subsubsection MPI_Scatter
288  - default : naive one, by default
289  - ompi : use openmpi selector for the scatter operations
290  - mpich : use mpich selector for the scatter operations
291  - automatic (experimental) : use an automatic self-benchmarking algorithm 
292  - ompi_basic_linear : basic linear scatter 
293  - ompi_binomial : binomial tree scatter
294
295
296 \subsubsection MPI_Reduce
297  - default : naive one, by default
298  - ompi : use openmpi selector for the reduce operations
299  - mpich : use mpich selector for the reduce operations
300  - automatic (experimental) : use an automatic self-benchmarking algorithm 
301  - arrival_pattern_aware : root exchanges with the first process to arrive
302  - binomial : uses a binomial tree
303  - flat_tree : uses a flat tree
304  - NTSL : Non-topology-specific pipelined linear-bcast function 
305    0->1, 1->2 ,2->3, ....., ->last node : in a pipeline fashion, with segments
306  of 8192 bytes
307  - scatter_gather : scatter then gather
308  - ompi_chain : openmpi reduce algorithms are built on the same basis, but the
309  topology is generated differently for each flavor
310 chain = chain with spacing of size/2, and segment size of 64KB 
311  - ompi_pipeline : same with pipeline (chain with spacing of 1), segment size 
312 depends on the communicator size and the message size
313  - ompi_binary : same with binary tree, segment size of 32KB
314  - ompi_in_order_binary : same with binary tree, enforcing order on the 
315 operations
316  - ompi_binomial : same with binomial algo (redundant with default binomial 
317 one in most cases)
318  - ompi_basic_linear : basic algorithm, each process sends to root
319
320 \subsubsection MPI_Allreduce
321  - default : naive one, by default
322  - ompi : use openmpi selector for the allreduce operations
323  - mpich : use mpich selector for the allreduce operations
324  - automatic (experimental) : use an automatic self-benchmarking algorithm 
325  - lr : logical ring reduce-scatter then logical ring allgather
326  - rab1 : variations of the  <a href="https://fs.hlrs.de/projects/par/mpi//myreduce.html">Rabenseifner</a> algorithm : reduce_scatter then allgather
327  - rab2 : variations of the  <a href="https://fs.hlrs.de/projects/par/mpi//myreduce.html">Rabenseifner</a> algorithm : alltoall then allgather
328  - rab_rsag : variation of the  <a href="https://fs.hlrs.de/projects/par/mpi//myreduce.html">Rabenseifner</a> algorithm : recursive doubling 
329 reduce_scatter then recursive doubling allgather 
330  - rdb : recursive doubling
331  - smp_binomial : binomial tree with smp : 8 cores/SMP, binomial intra 
332 SMP reduce, inter reduce, inter broadcast then intra broadcast
333  - smp_binomial_pipeline : same with segment size = 4096 bytes
334  - smp_rdb : 8 cores/SMP, intra : binomial allreduce, inter : Recursive 
335 doubling allreduce, intra : binomial broadcast
336  - smp_rsag : 8 cores/SMP, intra : binomial allreduce, inter : reduce-scatter, 
337 inter:allgather, intra : binomial broadcast
338  - smp_rsag_lr : 8 cores/SMP, intra : binomial allreduce, inter : logical ring 
339 reduce-scatter, logical ring inter:allgather, intra : binomial broadcast
340  - smp_rsag_rab : 8 cores/SMP, intra : binomial allreduce, inter : rab
341 reduce-scatter, rab inter:allgather, intra : binomial broadcast
342  - redbcast : reduce then broadcast, using default or tuned algorithms if specified
343  - ompi_ring_segmented : ring algorithm used by OpenMPI
344
345 \subsubsection MPI_Reduce_scatter
346  - default : naive one, by default
347  - ompi : use openmpi selector for the reduce_scatter operations
348  - mpich : use mpich selector for the reduce_scatter operations
349  - automatic (experimental) : use an automatic self-benchmarking algorithm 
350  - ompi_basic_recursivehalving : recursive halving version from OpenMPI
351  - ompi_ring : ring version from OpenMPI
352  - mpich_pair : pairwise exchange version from MPICH
353  - mpich_rdb : recursive doubling version from MPICH
354  - mpich_noncomm : only works for power of 2 procs, recursive doubling for noncommutative ops
355
356
357 \subsubsection MPI_Allgather
358
359  - default : naive one, by default
360  - ompi : use openmpi selector for the allgather operations
361  - mpich : use mpich selector for the allgather operations
362  - automatic (experimental) : use an automatic self-benchmarking algorithm 
363  - 2dmesh : see alltoall
364  - 3dmesh : see alltoall
365  - bruck : Described by Bruck et.al. in <a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=642949">
366 Efficient algorithms for all-to-all communications in multiport message-passing systems</a> 
367  - GB : Gather - Broadcast (uses tuned version if specified)
368  - loosely_lr : Logical Ring with grouping by core (hardcoded, default 
369 processes/node: 4)
370  - NTSLR : Non Topology Specific Logical Ring
371  - NTSLR_NB : Non Topology Specific Logical Ring, Non Blocking operations
372  - pair : see alltoall
373  - rdb : see alltoall
374  - rhv : only power of 2 number of processes
375  - ring : see alltoall
376  - SMP_NTS : gather to root of each SMP, then every root of each SMP node 
377 post INTER-SMP Sendrecv, then do INTRA-SMP Bcast for each receiving message, 
378 using logical ring algorithm (hardcoded, default processes/SMP: 8)
379  - smp_simple : gather to root of each SMP, then every root of each SMP node 
380 post INTER-SMP Sendrecv, then do INTRA-SMP Bcast for each receiving message, 
381 using simple algorithm (hardcoded, default processes/SMP: 8)
382  - spreading_simple : from node i, order of communications is i -> i + 1, i ->
383  i + 2, ..., i -> (i + p -1) % P
384  - ompi_neighborexchange : Neighbor Exchange algorithm for allgather. 
385 Described by Chen et.al. in  <a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=1592302">Performance Evaluation of Allgather Algorithms on Terascale Linux Cluster with Fast Ethernet</a>
386
387
388 \subsubsection MPI_Allgatherv
389  - default : naive one, by default
390  - ompi : use openmpi selector for the allgatherv operations
391  - mpich : use mpich selector for the allgatherv operations
392  - automatic (experimental) : use an automatic self-benchmarking algorithm 
393  - GB : Gatherv - Broadcast (uses tuned version if specified, but only for 
394 Bcast, gatherv is not tuned)
395  - pair : see alltoall
396  - ring : see alltoall
397  - ompi_neighborexchange : see allgather
398  - ompi_bruck : see allgather
399  - mpich_rdb : recursive doubling algorithm from MPICH
400  - mpich_ring : ring algorithm from MPICh - performs differently from the 
401 one from STAR-MPI
402
403 \subsubsection MPI_Bcast
404  - default : naive one, by default
405  - ompi : use openmpi selector for the bcast operations
406  - mpich : use mpich selector for the bcast operations
407  - automatic (experimental) : use an automatic self-benchmarking algorithm 
408  - arrival_pattern_aware : root exchanges with the first process to arrive
409  - arrival_pattern_aware_wait : same with slight variation
410  - binomial_tree : binomial tree exchange
411  - flattree : flat tree exchange
412  - flattree_pipeline : flat tree exchange, message split into 8192 bytes pieces
413  - NTSB : Non-topology-specific pipelined binary tree with 8192 bytes pieces
414  - NTSL : Non-topology-specific pipelined linear with 8192 bytes pieces
415  - NTSL_Isend : Non-topology-specific pipelined linear with 8192 bytes pieces, asynchronous communications
416  - scatter_LR_allgather : scatter followed by logical ring allgather
417  - scatter_rdb_allgather : scatter followed by recursive doubling allgather
418  - arrival_scatter : arrival pattern aware scatter-allgather
419  - SMP_binary : binary tree algorithm with 8 cores/SMP
420  - SMP_binomial : binomial tree algorithm with 8 cores/SMP
421  - SMP_linear : linear algorithm with 8 cores/SMP
422  - ompi_split_bintree : binary tree algorithm from OpenMPI, with message split in 8192 bytes pieces
423  - ompi_pipeline : pipeline algorithm from OpenMPI, with message split in 128KB pieces
424
425
426 \subsection auto Automatic evaluation 
427
428 (Warning : This is experimental and may be removed or crash easily)
429
430 An automatic version is available for each collective (or even as a selector). This specific 
431 version will loop over all other implemented algorithm for this particular collective, and apply 
432 them while benchmarking the time taken for each process. It will then output the quickest for 
433 each process, and the global quickest. This is still unstable, and a few algorithms which need 
434 specific number of nodes may crash.
435
436
437 \subsection add Add an algorithm
438
439 To add a new algorithm, one should check in the src/smpi/colls folder how other algorithms 
440 are coded. Using plain MPI code inside Simgrid can't be done, so algorithms have to be 
441 changed to use smpi version of the calls instead (MPI_Send will become smpi_mpi_send). Some functions may have different signatures than their MPI counterpart, please check the other algorithms or contact us using <a href="http://lists.gforge.inria.fr/mailman/listinfo/simgrid-devel">SimGrid developers mailing list</a>.
442
443 Example: adding a "pair" version of the Alltoall collective.
444
445  - Implement it in a file called alltoall-pair.c in the src/smpi/colls folder. This file should include colls_private.h.
446
447  - The name of the new algorithm function should be smpi_coll_tuned_alltoall_pair, with the same signature as MPI_Alltoall.
448
449  - Once the adaptation to SMPI code is done, add a reference to the file ("src/smpi/colls/alltoall-pair.c") in the SMPI_SRC part of the DefinePackages.cmake file inside buildtools/cmake, to allow the file to be built and distributed.
450
451  - To register the new version of the algorithm, simply add a line to the corresponding macro in src/smpi/colls/cools.h ( add a "COLL_APPLY(action, COLL_ALLTOALL_SIG, pair)" to the COLL_ALLTOALLS macro ). The algorithm should now be compiled and be selected when using --cfg=smpi/alltoall:pair at runtime.
452
453  - To add a test for the algorithm inside Simgrid's test suite, juste add the new algorithm name in the ALLTOALL_COLL list found inside buildtools/cmake/AddTests.cmake . When running ctest, a test for the new algorithm should be generated and executed. If it does not pass, please check your code or contact us.
454
455  - Feel free to push this new algorithm to the SMPI repository using Git.
456
457
458
459
460 */