Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
acc03e0f35a63bf2439a5366585419c4103a8c0c
[simgrid.git] / doc / index.doc
1 /*! \page index
2
3 <center>
4 \htmlonly
5 <img align=center src="simgrid_logo.png" alt="SimGrid"><br>
6 \endhtmlonly
7 </center>
8
9 \section quick Quick start
10
11 SimGrid is a toolkit that provides core functionalities for the simulation
12 of distributed applications in heterogeneous distributed environments.
13 The specific goal of the project is to facilitate research in the area of
14 distributed and parallel application scheduling on distributed computing
15 platforms ranging from simple network of workstations to Computational
16 Grids.
17
18 \subsection quick_dl Getting and installing the software
19
20   - The official webpage is <a href="http://simgrid.gforge.inria.fr/">simgrid.gforge.inria.fr</a>. 
21   - The development webpage is <a href="https://gforge.inria.fr/projects/simgrid//">gforge.inria.fr/projects/simgrid</a>. 
22   - The user mailing list is <simgrid-user@lists.gforge.inria.fr>
23   - The SimGrid software package can be downloaded from <a href="https://gforge.inria.fr/frs/?group_id=12">here</a>. 
24
25 To compile and install it, simply type the following. If you are not
26 familiar with compiling C files under UNIX and using libraries, please check
27 the \ref faq. SimGrid also works under Windows, but we do not distribute any
28 pre-compiled binaries [yet].
29
30 \verbatim $ ./configure
31  $ make all
32  [become root]
33  # make install\endverbatim
34  
35 \subsection quick_more More information
36
37 The API is described <a href="API/html/modules.html">here</a> while 
38 <a href="examples/html/modules.html">this page</a> presents some example of
39 use.
40
41 For more information about the SimGrid toolkit, please simply keep reading
42 this page. It is organized as follow:
43
44   - \ref overview: Presentation of the toolkit, of each of its components
45     and of their interactions.
46   - \ref people: Who is behind this project.
47   - \ref publications: Some articles providing more details about the
48     SimGrid toolkit or using and validating it.
49
50 <hr>
51
52 \section overview Overview of the toolkit components
53
54 As depicted by the following schema, the SimGrid toolkit is basically
55 three-layered (click on the picture to jump to a specific component).
56
57
58 \htmlonly
59 <center>
60 \endhtmlonly
61 \htmlinclude simgrid_modules.map
62 \htmlonly
63 <br><b>Relationships between the SimGrid components</b>
64 </center>
65 \endhtmlonly
66
67 \subsection overview_fondation Basement layer
68
69 The basement of the whole toolkit is constituted by the <b>\ref XBT_API
70 (eXtended Bundle of Tools)</b>.
71
72 It is a portable library providing some grounding features such as \ref
73 XBT_log, \ref XBT_error and \ref XBT_config. XBT also encompass the
74 following convenient datastructures: \ref XBT_dynar, \ref XBT_fifo, \ref
75 XBT_dict, \ref XBT_heap, \ref XBT_set and \ref XBT_swag.
76
77 See the \ref XBT_API section for more details.
78
79 \subsection overview_kernel Simulation kernel layer
80
81 The core functionnalities to simulate a virtual platform are provided by a
82 module called <b>\ref SURF_API</b> ("that's historical, my friend").  It is
83 very low-level and is not intended to be used as such by end-users. Instead,
84 it serve as a basis for the higher level layer.
85
86 SURF main features are a fast max-min linear solver and the ability to
87 change transparently the model used to describe the platform. This greatly
88 eases the comparison of the several models existing in the litterature.
89
90 See the \ref SURF_API section for more details.
91
92 \subsection overview_envs Programmation environments layer
93
94 This simulation kernel is used to build several programmation environments.
95 Each of them target a specific audiance and constitute a different paradigm.
96 To choose which of them you want to use, you have to think about what you
97 want to do and what would be the result of your work. 
98
99  - If you want to study a theoritical problem and compare several
100    heuristics, you probably want to try <b>\ref MSG_API</b> (yet another
101    historical name). It was designed exactly to that extend and should allow
102    you to build easily rather realistic multi-agents simulation. Yet,
103    realism is not the main goal of this environment and the most annoying
104    technical issues of real platforms are masked here. Check the \ref
105    MSG_API section for more information.
106
107  - If you want to study the behaviour of a MPI application using emulation
108    technics, you should have a look at the <b>\ref SMPI_API</b> (Simulated
109    MPI) programming environment. Unfortunately, this work is still underway.
110    Check the \ref SMPI_API section for more information. 
111    
112  - If you want to develop a real distributed application, then you may find
113    <b>\ref GRAS_API</b> (Grid Reality And Simulation) useful. This is an API
114    for the realization of distributed applications. 
115    \n\n
116    Moreover, there is two implementations of this API: one on top of the
117    SURF (allowing to develop and test your application within the comfort of
118    the simulator) and another suited for deployment on real platforms
119    (allowing the resulting application to be highly portable and extremely
120    efficient).
121    \n\n
122    Even if you do not plan to run your code for real, you may want to switch
123    to GRAS if you intend to use MSG in a very intensive way (e.g. for
124    simulating a peer-to-peer environment).
125    \n\n
126    See the \ref GRAS_API section for more details.
127
128 If your favorite programming environment/model is not there (BSP,
129 components, etc.) is not represented in the SimGrid toolkit yet, you may
130 consider adding it. You should contact us first, though.
131
132 Any question, remark or suggestion are welcome on the 
133 <a href=https://listes.ens-lyon.fr/wws/info/simgrid2-users>SimGrid users
134 mailing list</a>.
135
136 <hr>
137
138 \section people People
139
140 The authors of SimGrid are:
141
142  - Henri Casanova <casanova#cs.ucsd.edu>
143  - Arnaud Legrand <arnaud.legrand#imag.fr>
144  - Martin Quinson <martin.quinson#loria.fr>
145
146 \subsection contributers Contributers and alumni project members
147
148  - Loris Marchal: wrote the new algorithm for simulation TCP
149    bandwidth-sharing.
150  - Julien Lerouge : wrote a XML parser for ENV descriptions and helped for
151    the general design during a 4 month period (march-june 2002) 
152    in the LIP.
153  - ClĂ©ment Menier and Marc Perache : wrote a first prototype of the MSG
154    interface during a project at ENS-Lyon (jan 2002). 
155  - Dmitrii Zagorodnov : wrote some parts of the first version of SimGrid
156    (1999). 
157
158 <hr>
159
160 \section publications Selected publications
161
162 When citing SimGrid, the prefered reference paper is <i>Scheduling
163 Distributed Applications: the SimGrid Simulation Framework</i>, even if it's
164 a bit old now. We are actively working on improving this.
165
166 \subsection simulation About simulation
167
168 \li <b>Scheduling Distributed Applications: the
169        SimGrid Simulation Framework</b>\n
170     by <em>Henri Casanova and Arnaud Legrand and Loris Marchal</em>\n
171     Proceedings of the third IEEE International Symposium
172     on Cluster Computing and the Grid (CCGrid'03)\n
173     Since the advent of distributed computer systems an active field
174     of research has been the investigation of scheduling strategies
175     for parallel applications.  The common approach is to employ
176     scheduling heuristics that approximate an optimal
177     schedule. Unfortunately, it is often impossible to obtain
178     analytical results to compare the efficacy of these heuristics.
179     One possibility is to conducts large numbers of back-to-back
180     experiments on real platforms.  While this is possible on
181     tightly-coupled platforms, it is infeasible on modern distributed
182     platforms (i.e. Grids) as it is labor-intensive and does not
183     enable repeatable results. The solution is to resort to
184     simulations. Simulations not only enables repeatable results but
185     also make it possible to explore wide ranges of platform and
186     application scenarios.\n
187     In this paper we present the SimGrid framework which enables the
188     simulation of distributed applications in distributed computing
189     environments for the specific purpose of developing and evaluating
190     scheduling algorithms.  This paper focuses on SimGrid v2, which
191     greatly improves on the first version of the software with more
192     realistic network models and topologies.  SimGrid v2 also enables
193     the simulation of distributed scheduling agents, which has become
194     critical for current scheduling research in large-scale platforms.
195     After describing and validating these features, we present a case
196     study by which we demonstrate the usefulness of SimGrid for
197     conducting scheduling research.
198
199
200 \li <b>A Network Model for Simulation of Grid Application</b>\n
201     by <em>Henri Casanova and Loris Marchal</em>\n
202     \anchor paper_tcp
203     In this work we investigate network models that can be
204     potentially employed in the simulation of scheduling algorithms for
205     distributed computing applications. We seek to develop a model of TCP
206     communication which is both high-level and realistic. Previous research
207     works show that accurate and global modeling of wide-area networks, such
208     as the Internet, faces a number of challenging issues. However, some
209     global models of fairness and bandwidth-sharing exist, and can be link
210     withthe behavior of TCP. Using both previous results and simulation (with
211     NS), we attempt to understand the macroscopic behavior of
212     TCP communications. We then propose a global model of the network for the
213     Grid platform. We perform partial validation of this model in
214     simulation. The model leads to an algorithm for computing
215     bandwidth-sharing. This algorithm can then be implemented as part of Grid
216     application simulations. We provide such an implementation for the
217     SimGrid simulation toolkit.\n
218     ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/RR2002/RR2002-40.ps.gz
219
220
221 \li <b>MetaSimGrid : Towards realistic scheduling simulation of
222         distributed applications</b>\n
223     by <em>Arnaud Legrand and Julien Lerouge</em>\n
224     Most scheduling problems are already hard on homogeneous
225     platforms, they become quite intractable in an heterogeneous
226     framework such as a metacomputing grid. In the best cases, a
227     guaranteed heuristic can be found, but most of the time, it is
228     not possible. Real experiments or simulations are often
229     involved to test or to compare heuristics. However, on a
230     distributed heterogeneous platform, such experiments are
231     technically difficult to drive, because of the genuine
232     instability of the platform. It is almost impossible to
233     guarantee that a platform which is not dedicated to the
234     experiment, will remain exactly the same between two tests,
235     thereby forbidding any meaningful comparison. Simulations are
236     then used to replace real experiments, so as to ensure the
237     reproducibility of measured data. A key issue is the
238     possibility to run the simulations against a realistic
239     environment. The main idea of trace-based simulation is to
240     record the platform parameters today, and to simulate the
241     algorithms tomorrow, against the recorded data: even though it
242     is not the current load of the platform, it is realistic,
243     because it represents a fair summary of what happened
244     previously. A good example of a trace-based simulation tool is
245     SimGrid, a toolkit providing a set of core abstractions and
246     functionalities that can be used to easily build simulators for
247     specific application domains and/or computing environment
248     topologies. Nevertheless, SimGrid lacks a number of convenient
249     features to craft simulations of a distributed application
250     where scheduling decisions are not taken by a single
251     process. Furthermore, modeling a complex platform by hand is
252     fastidious for a few hosts and is almost impossible for a real
253     grid. This report is a survey on simulation for scheduling
254     evaluation purposes and present MetaSimGrid, a simulator built
255     on top of SimGrid.\n
256     ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/RR2002/RR2002-28.ps.gz
257
258 \li <b>SimGrid: A Toolkit for the Simulation of Application
259         Scheduling</b>\n
260     by <em>Henri Casanova</em>\n
261     Advances in hardware and software technologies have made it
262     possible to deploy parallel applications over increasingly large
263     sets of distributed resources. Consequently, the study of
264     scheduling algorithms for such applications has been an active area
265     of research. Given the nature of most scheduling problems one must
266     resort to simulation to effectively evaluate and compare their
267     efficacy over a wide range of scenarios. It has thus become
268     necessary to simulate those algorithms for increasingly complex
269     distributed, dynamic, heterogeneous environments. In this paper we
270     present SimGrid, a simulation toolkit for the study of scheduling
271     algorithms for distributed application. This paper gives the main
272     concepts and models behind SimGrid, describes its API and
273     highlights current implementation issues. We also give some
274     experimental results and describe work that builds on SimGrid's
275     functionalities.\n
276     http://grail.sdsc.edu/papers/simgrid_ccgrid01.ps.gz
277
278 \subsection research Papers using SimGrid results
279
280 \li <b>Optimal algorithms for scheduling divisible workloads on
281        heterogeneous systems</b>\n
282     by <em>Olivier Beaumont and Arnaud Legrand and Yves Robert</em>\n
283    In this paper, we discuss several algorithms for scheduling
284    divisible loads on heterogeneous systems. Our main contributions
285    are (i) new optimality results for single-round algorithms and (ii)
286    the design of an asymptotically optimal multi-round algorithm. This
287    multi-round algorithm automatically performs resource selection, a
288    difficult task that was previously left to the user. Because it is
289    periodic, it is simpler to implement, and more robust to changes in
290    the speeds of processors or communication links. On the theoretical
291    side, to the best of our knowledge, this is the first published
292    result assessing the absolute performance of a multi-round
293    algorithm.  On the practical side, extensive simulations reveal
294    that our multi-round algorithm outperforms existing solutions on a
295    large variety of platforms, especially when the
296    communication-to-computation ratio is not very high (the difficult
297    case).\n
298    ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/RR2002/RR2002-36.ps.gz
299 \li <b>On-line Parallel Tomography</b>\n
300     by <em>Shava Smallen</em>\n
301     Masters Thesis, UCSD, May 2001
302 \li <b>Applying Scheduling and Tuning to On-line Parallel Tomography </b>\n
303      by <em>Shava Smallen, Henri Casanova, Francine Berman</em>\n
304      in Proceedings of Supercomputing 2001
305 \li <b>Heuristics for Scheduling Parameter Sweep applications in
306          Grid environments</b>\n
307     by <em>Henri Casanova, Arnaud Legrand, Dmitrii Zagorodnov and 
308             Francine Berman</em>\n
309     in Proceedings of the 9th Heterogeneous Computing workshop 
310     (HCW'2000), pp349-363.
311 */