Logo AND Algorithmique Numérique Distribuée

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