1 /*! @page tutorial_msg SimGrid Tutorial with MSG
5 \section tuto-msg-intro Introduction
7 \subsection tuto-msg-intro-settings Settings
9 \warning Before you take this tutorial, you should remember that the
10 MSG interface is currently deprecated. It means that it will remain as
11 is, inchanged, for a few years, but that new developments should use
12 the new S4U interface instead. Unfortunately, the S4U tutorial is not
13 written yet. Sorry about that.
15 This tutorial will guide your create and run your first SimGrid
16 simulator. Let's consider the following scenario:
18 > Assume we have a (possibly large) bunch of (possibly large) data to
19 > process and which originally reside on a server (a.k.a. master). For
20 > sake of simplicity, we assume all input file require the same amount
21 > of computation. We assume the server can be helped by a (possibly
22 > large) set of worker machines. What is the best way to organize the
28 \htmlinclude tuto-msg/overview.svg
33 \subsection tuto-msg-intro-questions Raised Questions
35 Although this looks like a very simple setting it raises several
36 interesting questions:
38 - Which algorithm should the master use to send workload?
40 The provided code sends the tasks to the workers with a trivial
41 round-robin algorithm. It would probably be more efficient if the
42 workers were asking for tasks, to let the master distribute the
43 tasks in a more cleaver way.
45 - Should the worker specify how many tasks they want? Or should the
46 master decide everything?
48 The workers will starve if they don't get the tasks fast
49 enough. One possibility to reduce latency would be to send tasks
50 in pools instead of one by one. But if the pools are too big, the
51 load balancing will likely get uneven, in particular when
52 distributing the last tasks.
54 - How does the quality of such algorithm dependent on the platform
55 characteristics and on the task characteristics?
57 Whenever the input communication time is very small compared to
58 processing time and workers are homogeneous, it is likely that the
59 round-robin algorithm performs very well. Would it still hold true
60 when transfer time is not negligible and the platform is, say, a
61 volunteer computing system ? What if some tasks are performed
62 faster on some specific nodes?
64 - The network topology interconnecting the master and the workers
65 may be quite complicated. How does such a topology impact the
68 When data transfers are the bottleneck, it is likely that a good
69 modeling of the platform becomes essential. The SimGrid platform
70 models are particularly handy to account for complex platform
73 - What topology to use for the application?
75 Is a flat master worker deployment sufficient? Should we go for a
76 hierarchical algorithm, with some forwarders taking large pools of
77 tasks from the master, each of them distributing their tasks to a
78 sub-pool of workers? Or should we introduce super-peers,
79 dupplicating the master's role in a peer-to-peer manner? Do the
80 algorithms require a perfect knowledge of the network?
82 - How is such an algorithm sensitive to external workload variation?
84 What if bandwidth, latency and computing speed can vary with no
85 warning? Shouldn't you study whether your algorithm is sensitive
86 to such load variations?
88 - Although an algorithm may be more efficient than another, how
89 does it interfere with other applications?
94 As you can see, this very simple setting may need to evolve way beyond
95 what you initially imagined. And this is a good news.
97 But don't believe the fools saying that all you need to study such
98 settings is a simple discrete event simulator. Do you really want to
99 reinvent the wheel, write your own tool, debug it, optimize it and
100 validate its models against real settings for ages, or do you prefer
101 to sit on the shoulders of a giant?<br>
102 With SimGrid, you can forget about most technical details (but not
103 all), and focus on your algorithm. The whole simulation mechanism is
106 \subsection tuto-msg-intro-goal Envisionned Study
109 The following figure is a screenshot of [triva][fn:1] visualizing a [SimGrid
110 simulation][fn:2] of two master worker applications (one in light gray and
111 the other in dark gray) running in concurrence and showing resource
112 usage over a long period of time.
114 ![Test](./sc3-description.png)
116 \section tuto-msg-starting Getting Started
118 \subsection tuto-msg-prerequesite Prerequisite
120 In this example, we use Pajeng and Vite to visualize the result of
121 SimGrid simulations. These external tools are usually very easy to
122 install. On Debian and Ubuntu for example, you can get them as follows:
125 sudo apt-get install pajeng vite
128 \subsection tuto-msg-setup Setting up and Compiling
130 The corresponding source files can be obtained
131 [online on GitLab](https://gitlab.inria.fr/simgrid/simgrid/tree/master/doc/tuto-msg/src).
132 There is a button on the top right to download the whole
133 directory in one archive file. If you wish, other platform files are available from
134 [this GitLab directory](https://gitlab.inria.fr/simgrid/simgrid/tree/master/examples/platforms).
136 As you can see, there is already a little Makefile that compiles
137 everything for you. If you struggle with the compilation, then you should double check
138 your @ref install "SimGrid installation".
139 On need, please refer to the @ref install_yours_trouble section.
141 \section tuto-msg-ex0 Discovering the provided simulator
143 Please compile and execute the provided simulator as follows:
147 ./masterworker examples/platforms/small_platform.xml deployment0.xml
150 For a more "fancy" output, you can use simgrid-colorizer.
153 ./masterworker examples/platforms/small_platform.xml deployment0.xml 2>&1 | simgrid-colorizer
156 If you installed SimGrid to a non-standard path, you may have to
157 specify the full path to simgrid-colorizer on the above line, such as
158 \c /opt/simgrid/bin/simgrid-colorizer. If you did not install it at all,
159 you can find it in \<simgrid_root_directory\>/bin/colorize.
161 For a classical Gantt-Chart visualization, you can produce a [Paje][fn:5] trace:
164 ./masterworker platforms/platform.xml deployment0.xml --cfg=tracing:yes \
165 --cfg=tracing/msg/process:yes
169 Alternatively, you can use [vite][fn:6].
172 ./masterworker platforms/platform.xml deployment0.xml --cfg=tracing:yes \
173 --cfg=tracing/msg/process:yes --cfg=tracing/basic:yes
177 \subsection tuto-msg-exo0-source Understanding this source code
179 Explore the \ref doc/tuto-msg/masterworker.c source file. It contains 3 functions:
180 - \c master: that's the code executed by the master process.<br>
181 It creates a large array containing all tasks,
182 dispatches all tasks to the workers and then dispatch
183 specific tasks which name is "finalize".
184 - \c worker: each workers will execute this function.<br>
185 That's an infinite loop waiting for incomming tasks.
186 We exit the loop if the name of the received task is "finalize", or process the task otherwise.
187 - \c main: this setups the simulation.
189 How does SimGrid know that we need one master and several workers?
190 Because it's written in the deployment file (called \c
191 deployment0.xml), that we pass to MSG_create_environment() during the setup.
193 \include doc/tuto-msg/deployment0.xml
195 \section tuto-msg-exo1 Exercise 1: Simplifying the deployment file
197 In the provided example, the deployment file `deployment0.xml` is
198 tightly connected to the platform file `small_platform.xml` and adding
199 more workers quickly becomes a pain: You need to start them (at the
200 bottom of the file), add to inform the master that they are available
201 (in the master parameters list).
203 Instead, modify the simulator `masterworker.c` into `masterworker-exo1.c`
204 so that the master launches a worker process on all the other machines
205 at startup. The new deployment file `deployment1.xml` should be as
208 \include doc/tuto-msg/deployment1.xml
210 For that, the master needs to retrieve the list of hosts declared in
211 the platform, with the following functions (follow the links for their
215 int MSG_get_host_number(void);
216 xbt_dynar_t MSG_hosts_as_dynar(void);
217 void * xbt_dynar_to_array (xbt_dynar_t dynar);
220 Then, the master should start the worker processes with the following function:
223 msg_process_t MSG_process_create(const char *name, xbt_main_func_t code, void *data, msg_host_t host);
226 \subsection tuto-msg-exo1-config Increasing configurability
228 The worker processes wait for incomming messages on a channel which
229 name they need to know beforehand. In the provided code, each worker
230 uses the name of its host as a channel name. You can see this in the
231 receiver source code:
234 int res = MSG_task_receive(&(task), MSG_host_get_name(MSG_host_self()));
235 xbt_assert(res == MSG_OK, "MSG_task_receive failed");
238 This way, you can have at most one worker per host. To later study the
239 behavior of concurrent applications on the platform, we need to
240 alleviate this. Several solutions exist:
242 Now that the the master creates the workers, it knows their PID
243 (process ID -- given by @ref MSG_process_get_PID()), so you could use
244 it in the channel name.
246 Another possibility for the master is to determine a channel name
247 before the process creation, and give that name as a parameter to the
248 starting process. This is what the `data` parameter of @ref
249 MSG_process_create is meant for. You can pass any arbitrary pointer,
250 and the created process can retrieve this value later with the @ref
251 MSG_process_get_data and @ref MSG_process_self functions. Since we
252 want later to study concurrent applications, it is advised to use a
253 channel name such as `master_name:worker_name`.
255 A third possibility would be to inverse the communication architecture
256 and have the workers pulling work from the master. This require to
257 pass the master's channel to the workers.
259 \subsection tuto-msg-exo1-wrapup Wrap up
261 In this exercise, we reduced the amount of configuration that our
262 simulator requests. This is both a good idea, and a dangerous
263 trend. This simplification is an application of the good old DRY/SPOT
264 programming principle (Don't Repeat Yourself / Single Point Of Truth
265 -- <a href="https://en.wikipedia.org/wiki/Don%27t_repeat_yourself">more on wikipedia</a>),
266 and you really want your programming artefacts to follow these software engineering principles.
268 But at the same time, you should be careful in separating your
269 scientific contribution (the master/wokers algorithm) and the
270 artefacts used to test it (platform, deployment and workload). This is
271 why SimGrid forces you to expres your platform and deployment files in
272 XML instead of using a programming interface: it forces a clear
273 separation of concerns between things that are of very different
276 If you struggle with this exercise, have a look at
277 our solution in \ref doc/tuto-msg/masterworker-sol1.c
278 This is not perfect at all, and many other solutions would have been possible, of course.
280 \section tuto-msg-exo2 Exercise 2: Infinite amount of work, fixed experiment duration
282 In the current version, the number of tasks is defined through the
283 worker arguments. Hence, tasks are created at the very beginning of
284 the simulation. Instead, have the master dispatching tasks for a
285 predetermined amount of time. The tasks must now be created on demand
286 instead of beforehand.
288 Of course, usual time functions like `gettimeofday` will give you the
289 time on your real machine, which is prety useless in the
290 simulation. Instead, retrieve the time in the simulated world with
293 You can still stop your workers with a specific task as previously,
294 but other methods exist. You can forcefully stop processes with the
295 following functions, but be warned that SimGrid traditionnally had
296 issues with forcefully stopping procsses involved in computations or
297 communications. We hope that it's better now, but YMMV.
300 void MSG_process_kill(msg_process_t process);
301 int MSG_process_killall(int reset_PIDs);
304 Anyway, the new deployment `deployment2.xml` file should thus look
307 \include doc/tuto-msg/deployment2.xml
309 \subsection tuto-msg-exo2-verbosity Controlling the message verbosity
311 Not all messages are equally informative, so you probably want to
312 change most of the `XBT_INFO` into `XBT_DEBUG` so that they are hidden
313 by default. You could for example show only the total number of tasks
314 processed by default. You can still see the debug messages as follows:
317 ./masterworker examples/platforms/small_platform.xml deployment2.xml --log=msg_test.thres:debug
320 \subsection tuto-msg-exo2-wrapup Wrap up
322 Our imperfect solution to this exercise is available as @ref doc/tuto-msg/masterworker-sol2.c
323 But there is still much to improve in that code.
325 \section tuto-msg-exo3 Exercise 3: Understanding how competing applications behave
327 It is now time to start several applications at once, with the following `deployment3.xml` file.
329 \include doc/tuto-msg/deployment3.xml
331 Things happen when you do so, but it remains utterly difficult to
332 understand what's happening exactely. Even visualizations with pajeng
333 and Vite contain too much information to be useful: it is impossible
334 to understand which task belong to which application. To fix this, we
335 will categorize the tasks.
337 For that, first let each master create its own category of tasks with
338 @ref TRACE_category(), and then assign this category to each task using
339 @ref MSG_task_set_category().
341 The outcome can then be visualized as a Gantt-chart as follows:
344 ./masterworker examples/platforms/small_platform.xml deployment3.xml --cfg=tracing:yes --cfg=tracing/msg/process:yes
348 \subsection tuto-msg-exo3-further Going further
350 vite is not enough to understand the situation, because it does not
351 deal with categorization. That is why you should switch to R to
352 visualize your outcomes, as explained on <a
353 href="http://simgrid.gforge.inria.fr/contrib/R_visualization.php">this
356 As usual, you can explore our imperfect solution, in @ref doc/tuto-msg/masterworker-sol3.c.
358 \section tuto-msg-exo4 Exercise 4: Better scheduling: FCFS
360 You don't need a very advanced visualization solution to notice that
361 round-robin is completely suboptimal: most of the workers keep waiting
362 for more work. We will move to a First-Come First-Served mechanism
365 For that, your workers should explicitely request for work with a
366 message sent to a channel that is specific to their master. The name
367 of their private channel name should be attached (using the last
368 parameter of @ref MSG_task_create()) to the message sent, so that
369 their master can answer.
371 The master should serve requests in a round-robin manner, until the
372 time is up. Things get a bit more complex to stop the workers
373 afterward: the master cannot simply send a terminating task, as the
374 workers are blocked until their request for work is accepted. So
375 instead, the master should wait for incomming requests even once the
376 time is up, and answer with a terminating task.
378 Once it works, you will see that such as simple FCFS schema allows to
379 double the amount of tasks handled over time in this case.
381 \subsection tuto-msg-exo4-further Going further
383 From this, many things can easily be added. For example, you could:
384 - Allow workers to have several pending requests so as to overlap
385 communication and computations as much as possible. Non-blocking communication will probably become handy here.
386 - Add a performance measurement mechanism, enabling the master to make smart scheduling choices.
387 - Test your code on other platforms, from the `examples/platforms` directory in your archive.<br>
388 What is the largest number of tasks requiring 50e6 flops and 1e5
389 bytes that you manage to distribute and process in one hour on
390 `g5k.xml` (you should use `deployment_general.xml`)?
391 - Optimize not only for the amount of tasks handled, but also for the total energy dissipated.
392 - And so on. If you come up with a really nice extension, please share it with us so that we can extend this tutorial.
394 \section tuto-msg-further Where to go from here?
396 This tutorial is now terminated. You could keep reading the [online documentation][fn:4] or
397 [tutorials][fn:7], or you could head up to the example section to read some code.
399 \subsection tuto-msg-further-todo TODO: Points to improve for the next time
401 - Propose equivalent exercises and skeleton in java.
402 - Propose a virtualbox image with everything (simgrid, pajeng, ...) already set
404 - Ease the installation on mac OS X (binary installer) and
406 - Explain that programming in C or java and having a working
407 development environment is a prerequisite.
410 [fn:1]: http://triva.gforge.inria.fr/index.html
411 [fn:2]: http://hal.inria.fr/inria-00529569
412 [fn:3]: http://hal.inria.fr/hal-00738321
413 [fn:4]: http://simgrid.gforge.inria.fr/simgrid/latest/doc/
414 [fn:5]: https://github.com/schnorr/pajeng/
415 [fn:6]: http://vite.gforge.inria.fr/
416 [fn:7]: http://simgrid.org/tutorials/
423 * @example doc/tuto-msg/masterworker.c
424 * @example doc/tuto-msg/masterworker-sol1.c
425 * @example doc/tuto-msg/masterworker-sol2.c
426 * @example doc/tuto-msg/masterworker-sol3.c
427 * @example doc/tuto-msg/masterworker-sol4.c