6 SimGrid was conceived as a tool to study distributed algorithms. Its
7 modern :ref:`S4U interface <S4U_doc>` makes it easy to assess Cloud,
8 P2P, HPC, IoT and similar settings.
10 A typical SimGrid simulation is composed of several |Actors|_, that
11 execute user-provided functions. The actors have to explicitly use the
12 S4U interface to express their computation, communication, disk usage
13 and other |Activities|_, so that they get reflected within the
14 simulator. These activities take place on **Resources** (|Hosts|_,
15 |Links|_, |Disks|_). SimGrid predicts the time taken by each
16 activity and orchestrates accordingly the actors waiting for the
17 completion of these activities.
19 Each actor executes a user-provided function on a simulated |Host|_
20 with which it can interact. Communications are not directly sent to
21 actors, but posted onto a |Mailbox|_ that serve as rendez-vous point
22 between communicating actors.
24 .. |Actors| replace:: **Actors**
25 .. _Actors: app_s4u.html#s4u-actor
27 .. |Activities| replace:: **Activities**
28 .. _Activities: app_s4u.html#s4u-activity
30 .. |Hosts| replace:: **Hosts**
31 .. _Hosts: app_s4u.html#s4u-host
33 .. |Links| replace:: **Links**
34 .. _Links: app_s4u.html#s4u-link
36 .. |Disks| replace:: **Disks**
37 .. _Disks: app_s4u.html#s4u-disk
39 .. |VirtualMachines| replace:: **VirtualMachines**
40 .. _VirtualMachines: app_s4u.html#s4u-virtualmachine
42 .. |Host| replace:: **Host**
43 .. _Host: app_s4u.html#s4u-host
45 .. |Link| replace:: **Link**
46 .. _Link: app_s4u.html#s4u-link
48 .. |Mailbox| replace:: **Mailbox**
49 .. _Mailbox: app_s4u.html#s4u-mailbox
51 .. |Barrier| replace:: **Barrier**
52 .. _Barrier: app_s4u.html#s4u-barrier
54 .. |ConditionVariable| replace:: **ConditionVariable**
55 .. _ConditionVariable: app_s4u.html#s4u-conditionvariable
57 .. |Mutex| replace:: **Mutex**
58 .. _Mutex: app_s4u.html#s4u-mutex
60 **In the remainder of this tutorial**, you will discover a simple yet
61 fully functioning example of SimGrid simulation: the Master/Workers
62 application. We will detail each part of the code and necessary
63 configuration to make it working. After this tour, several exercises
64 are proposed to let you discover some of the SimGrid features, hands
65 on the keyboard. This practical session will be given in C++, that you
66 are supposed to know beforehand.
69 Discover the Master/Workers
70 ---------------------------
72 This section introduces a first example of SimGrid simulation. This
73 simple application is composed of two kind of actors: the **master**
74 is in charge of distributing some computational tasks to a set of
75 **workers** that execute them.
77 .. image:: /tuto_s4u/img/intro.svg
80 We first present a round-robin version of this application, where the
81 master dispatches the tasks to the workers, one after the other, until
82 all tasks are dispatched. Later in this tutorial, you will be given
83 the opportunity to improve this scheme.
88 Let's start with the code of the master. It is represented by the
89 *master* function below. This simple function takes at least 3
90 parameters (the amount of tasks to dispatch, their computational size
91 in flops to compute and their communication size in bytes to
92 exchange). Every parameter after the third one must be the name of an
93 host on which a worker is waiting for something to compute.
95 Then, the tasks are sent one after the other, each on a mailbox named
96 after the worker's hosts. On the other side, a given worker (which
97 code is given below) wait for incoming tasks on its own
102 At the end, once all tasks are dispatched, the master dispatches
103 another task per worker, but this time with a negative amount of flops
104 to compute. Indeed, this application decided by convention, that the
105 workers should stop when encountering such a negative compute_size.
107 At the end of the day, the only SimGrid specific functions used in
108 this example are :cpp:func:`simgrid::s4u::Mailbox::by_name` and
109 :cpp:func:`simgrid::s4u::Mailbox::put`. Also, :c:macro:`XBT_INFO` is used
110 as a replacement to printf() or to cout to ensure that the messages
111 are nicely logged along with the simulated time and actor name.
114 .. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers-fun.cpp
116 :start-after: master-begin
117 :end-before: master-end
119 Here comes the code of the worker actors. This function expects no
120 parameter from its vector of strings. Its code is very simple: it
121 expects messages on the mailbox that is named after its own host. As long as it gets valid
122 computation requests (whose compute_amount is positive), it compute
123 this task and waits for the next one.
125 The worker retrieves its own host with
126 :cpp:func:`simgrid::s4u::this_actor::get_host`. The
127 :ref:`simgrid::s4u::this_actor <API_s4u_this_actor>`
128 namespace contains many such helping functions.
130 .. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers-fun.cpp
132 :start-after: worker-begin
133 :end-before: worker-end
135 Starting the Simulation
136 .......................
138 And this is it. In only a few lines, we defined the algorithm of our
139 master/workers examples.
141 That being said, an algorithm alone is not enough to define a
142 simulation: SimGrid is a library, not a program. So you need to define
143 your own ``main()`` function as follows. This function is in charge of
144 creating a SimGrid simulation engine (on line 3), register the actor
145 functions to the engine (on lines 7 and 8), load the simulated platform
146 from its description file (on line 11), map actors onto that platform
147 (on line 12) and run the simulation until its completion on line 15.
149 .. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers-fun.cpp
151 :start-after: main-begin
152 :end-before: main-end
155 As you can see, this also requires a platform file and a deployment
161 Platform files define the simulated platform on which the provided
162 application will take place. In contains one or several **Network
163 Zone** |api_s4u_NetZone|_ that contain both |Host|_ and |Link|_
164 Resources, as well as routing information.
166 Such files can get rather long and boring, so the example below is
167 only an excerpts of the full ``examples/platforms/small_platform.xml``
168 file. For example, most routing information are missing, and only the
169 route between the hosts Tremblay and Fafard is given. This path
170 traverses 6 links (named 4, 3, 2, 0, 1 and 8). There are several
171 examples of platforms in the archive under ``examples/platforms``.
173 .. |api_s4u_NetZone| image:: /img/extlink.png
176 .. _api_s4u_NetZone: app_s4u.html#s4u-netzone
178 .. |api_s4u_Link| image:: /img/extlink.png
181 .. _api_s4u_Link: app_s4u.html#s4u-link
183 .. literalinclude:: ../../examples/platforms/small_platform.xml
185 :lines: 1-10,12-20,56-62,192-
186 :caption: (excerpts of the small_platform.xml file)
191 Deployment files specify the execution scenario: it lists the actors
192 that should be started, along with their parameter. In the following
193 example, we start 6 actors: one master and 5 workers.
195 .. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers_d.xml
201 This time, we have all parts: once the program is compiled, we can
202 execute it as follows. Note how the XBT_INFO() requests turned into
203 informative messages.
205 .. "WARNING: Over dedent has detected" is expected here as we remove the $ marker this way
207 .. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers.tesh
209 :start-after: s4u-app-masterworkers-fun
210 :prepend: $$$ ./masterworkers platform.xml deploy.xml
214 Each example included in the SimGrid distribution comes with a `tesh`
215 file that presents how to start the example once compiled, along with
216 the expected output. These files are used for the automatic testing of
217 the framework, but can be used to see the examples' output without
218 compiling them. See e.g. the file
219 `examples/s4u/app-masterworkers/s4u-app-masterworkers.tesh <https://framagit.org/simgrid/simgrid/-/blob/master/examples/s4u/app-masterworkers/s4u-app-masterworkers.tesh>`_.
220 Lines starting with `$` are the commands to execute;
221 lines starting with `>` are the expected output of each command while
222 lines starting with `!` are configuration items for the test runner.
228 In this section, you will modify the example presented earlier to
229 explore the quality of the proposed algorithm. For now, it works and
230 the simulation prints things, but the truth is that we have no idea of
231 whether this is a good algorithm to dispatch tasks to the workers.
232 This very simple setting raises many interesting questions:
234 .. image:: /tuto_s4u/img/question.svg
237 - Which algorithm should the master use? Or should the worker decide
240 Round Robin is not an efficient algorithm when all tasks are not
241 processed at the same speed. It would probably be more efficient
242 if the workers were asking for tasks when ready.
244 - Should tasks be grouped in batches or sent separately?
246 The workers will starve if they don't get the tasks fast
247 enough. One possibility to reduce latency would be to send tasks
248 in pools instead of one by one. But if the pools are too big, the
249 load balancing will likely get uneven, in particular when
250 distributing the last tasks.
252 - How does the quality of such algorithm dependent on the platform
253 characteristics and on the task characteristics?
255 Whenever the input communication time is very small compared to
256 processing time and workers are homogeneous, it is likely that the
257 round-robin algorithm performs very well. Would it still hold true
258 when transfer time is not negligible? What if some tasks are
259 performed faster on some specific nodes?
261 - The network topology interconnecting the master and the workers
262 may be quite complicated. How does such a topology impact the
265 When data transfers are the bottleneck, it is likely that a good
266 modeling of the platform becomes essential. The SimGrid platform
267 models are particularly handy to account for complex platform
270 - What is the best applicative topology?
272 Is a flat master worker deployment sufficient? Should we go for a
273 hierarchical algorithm, with some forwarders taking large pools of
274 tasks from the master, each of them distributing their tasks to a
275 sub-pool of workers? Or should we introduce super-peers,
276 duplicating the master's role in a peer-to-peer manner? Do the
277 algorithms require a perfect knowledge of the network?
279 - How is such an algorithm sensitive to external workload variation?
281 What if bandwidth, latency and computing speed can vary with no
282 warning? Shouldn't you study whether your algorithm is sensitive
283 to such load variations?
285 - Although an algorithm may be more efficient than another, how does
286 it interfere with unrelated applications executing on the same
289 **SimGrid was invented to answer such questions.** Do not believe the
290 fools saying that all you need to study such settings is a simple
291 discrete event simulator. Do you really want to reinvent the wheel,
292 debug and optimize your own tool, and validate its models against real
293 settings for ages, or do you prefer to sit on the shoulders of a
294 giant? With SimGrid, you can focus on your algorithm. The whole
295 simulation mechanism is already working.
297 Here is the visualization of a SimGrid simulation of two master worker
298 applications (one in light gray and the other in dark gray) running in
299 concurrence and showing resource usage over a long period of time. It
300 was obtained with the Triva software.
302 .. image:: /tuto_s4u/img/result.png
308 The easiest way to take the tutorial is to use the dedicated Docker
309 image. Once you `installed Docker itself
310 <https://docs.docker.com/install/>`_, simply do the following:
312 .. code-block:: shell
314 docker pull simgrid/tuto-s4u
315 docker run -it --rm --name simgrid --volume ~/simgrid-tutorial:/source/tutorial simgrid/tuto-s4u bash
317 This will start a new container with all you need to take this
318 tutorial, and create a ``simgrid-tutorial`` directory in your home on
319 your host machine that will be visible as ``/source/tutorial`` within the
320 container. You can then edit the files you want with your favorite
321 editor in ``~/simgrid-tutorial``, and compile them within the
322 container to enjoy the provided dependencies.
326 Any change to the container out of ``/source/tutorial`` will be lost
327 when you log out of the container, so don't edit the other files!
329 All needed dependencies are already installed in this container
330 (SimGrid, a C++ compiler, cmake, pajeng and R). Vite being only
331 optional in this tutorial, it is not installed to reduce the image
334 The code template is available under ``/source/simgrid-template-s4u.git``
335 in the image. You should copy it to your working directory and
336 recompile it when you first log in:
338 .. code-block:: shell
340 cp -r /source/simgrid-template-s4u.git/* /source/tutorial
345 Using your Computer Natively
346 ............................
348 To take the tutorial on your machine, you first need to :ref:`install
349 a recent version of SimGrid <install>`, a C++ compiler and also
350 ``pajeng`` to visualize the traces. You may want to install `Vite
351 <http://vite.gforge.inria.fr/>`_ to get a first glance at the traces.
352 The provided code template requires cmake to compile. On Debian and
353 Ubuntu for example, you can get them as follows:
355 .. code-block:: shell
357 sudo apt install simgrid pajeng cmake g++ vite
359 For R analysis of the produced traces, you may want to install R,
360 and the `pajengr <https://github.com/schnorr/pajengr#installation/>`_ package.
362 .. code-block:: shell
364 sudo apt install r-base r-cran-devtools cmake flex bison
365 Rscript -e "library(devtools); install_github('schnorr/pajengr');"
367 An initial version of the source code is provided on framagit. This
368 template compiles with cmake. If SimGrid is correctly installed, you
369 should be able to clone the `repository
370 <https://framagit.org/simgrid/simgrid-template-s4u>`_ and recompile
371 everything as follows:
373 .. code-block:: shell
375 # (exporting SimGrid_PATH is only needed if SimGrid is installed in a non-standard path)
376 export SimGrid_PATH=/where/to/simgrid
378 git clone https://framagit.org/simgrid/simgrid-template-s4u.git
379 cd simgrid-template-s4u/
383 If you struggle with the compilation, then you should double check
384 your :ref:`SimGrid installation <install>`. On need, please refer to
385 the :ref:`Troubleshooting your Project Setup
386 <install_yours_troubleshooting>` section.
388 Discovering the Provided Code
389 .............................
391 Please compile and execute the provided simulator as follows:
393 .. code-block:: shell
396 ./master-workers small_platform.xml master-workers_d.xml
398 For a more "fancy" output, you can use simgrid-colorizer.
400 .. code-block:: shell
402 ./master-workers small_platform.xml master-workers_d.xml 2>&1 | simgrid-colorizer
404 If you installed SimGrid to a non-standard path, you may have to
405 specify the full path to simgrid-colorizer on the above line, such as
406 ``/opt/simgrid/bin/simgrid-colorizer``. If you did not install it at all,
407 you can find it in <simgrid_root_directory>/bin/colorize.
409 For a classical Gantt-Chart vizualisation, you can use `Vite
410 <http://vite.gforge.inria.fr/>`_ if you have it installed, as
411 follows. But do not spend too much time installing Vite, because there
412 is a better way to visualize SimGrid traces (see below).
414 .. code-block:: shell
416 ./master-workers small_platform.xml master-workers_d.xml --cfg=tracing:yes --cfg=tracing/actor:yes
419 .. image:: /tuto_s4u/img/vite-screenshot.png
422 If you want the full power to visualize SimGrid traces, you need
423 to use R. As a start, you can download this `starter script
424 <https://framagit.org/simgrid/simgrid/raw/master/docs/source/tuto_s4u/draw_gantt.R>`_
425 and use it as follows:
427 .. code-block:: shell
429 ./master-workers small_platform.xml master-workers_d.xml --cfg=tracing:yes --cfg=tracing/actor:yes
430 Rscript draw_gantt.R simgrid.trace
432 It produces a ``Rplots.pdf`` with the following content:
434 .. image:: /tuto_s4u/img/Rscript-screenshot.png
438 Lab 1: Simpler Deployments
439 --------------------------
441 In the provided example, adding more workers quickly becomes a pain:
442 You need to start them (at the bottom of the file), and to inform the
443 master of its availability with an extra parameter. This is mandatory
444 if you want to inform the master of where the workers are running. But
445 actually, the master does not need to have this information.
447 We could leverage the mailbox mechanism flexibility, and use a sort of
448 yellow page system: Instead of sending data to the worker running on
449 Fafard, the master could send data to the third worker. Ie, instead of
450 using the worker location (which should be filled in two locations),
451 we could use their ID (which should be filled in one location
454 This could be done with the following deployment file. It's clearly
455 not shorter than the previous one, but it's still simpler because the
456 information is only written once. It thus follows the `DRY
457 <https://en.wikipedia.org/wiki/Don't_repeat_yourself>`_ `SPOT
458 <http://wiki.c2.com/?SinglePointOfTruth>`_ design principle.
460 .. literalinclude:: tuto_s4u/deployment1.xml
464 Copy your ``master-workers.cpp`` into ``master-workers-lab1.cpp`` and
465 add a new executable into ``CMakeLists.txt``. Then modify your worker
466 function so that it gets its mailbox name not from the name of its
467 host, but from the string passed as ``args[1]``. The master will send
468 messages to all workers based on their number, for example as follows:
472 for (int i = 0; i < tasks_count; i++) {
473 std::string worker_rank = std::to_string(i % workers_count);
474 std::string mailbox_name = std::string("worker-") + worker_rank;
475 simgrid::s4u::Mailbox* mailbox = simgrid::s4u::Mailbox::by_name(mailbox_name);
486 The mailboxes are a very powerful mechanism in SimGrid, allowing many
487 interesting application settings. They may feel surprising if you are
488 used to BSD sockets or other classical systems, but you will soon
489 appreciate their power. They are only used to match the
490 communications, but have no impact on the communication
491 timing. ``put()`` and ``get()`` are matched regardless of their
492 initiators' location and then the real communication occurs between
493 the involved parties.
495 Please refer to the full `Mailboxes' documentation
496 <app_s4u.html#s4u-mailbox>`_ for more details.
499 Lab 2: Using the Whole Platform
500 -------------------------------
502 It is now easier to add a new worker, but you still has to do it
503 manually. It would be much easier if the master could start the
504 workers on its own, one per available host in the platform. The new
505 deployment file should be as simple as:
507 .. literalinclude:: tuto_s4u/deployment2.xml
511 Creating the workers from the master
512 ....................................
514 For that, the master needs to retrieve the list of hosts declared in
515 the platform with :cpp:func:`simgrid::s4u::Engine::get_all_hosts`.
516 Then, the master should start the worker actors with
517 :cpp:func:`simgrid::s4u::Actor::create`.
519 ``Actor::create(name, host, func, params...)`` is a very flexible
520 function. Its third parameter is the function that the actor should
521 execute. This function can take any kind of parameter, provided that
522 you pass similar parameters to ``Actor::create()``. For example, you
523 could have something like this:
527 void my_actor(int param1, double param2, std::string param3) {
530 int main(int argc, char argv**) {
532 simgrid::s4u::ActorPtr actor;
533 actor = simgrid::s4u::Actor::create("name", simgrid::s4u::Host::by_name("the_host"),
534 &my_actor, 42, 3.14, "thevalue");
539 Master-Workers Communication
540 ............................
542 Previously, the workers got from their parameter the name of the
543 mailbox they should use. We can still do so: the master should build
544 such a parameter before using it in the ``Actor::create()`` call. The
545 master could even pass directly the mailbox as a parameter to the
548 Since we want later to study concurrent applications, it is advised to
549 use a mailbox name that is unique over the simulation even if there is
550 more than one master.
552 One possibility for that is to use the actor ID (aid) of each worker
553 as a mailbox name. The master can retrieve the aid of the newly
554 created actor with ``actor->get_pid()`` while the actor itself can
555 retrieve its own aid with ``simgrid::s4u::this_actor::get_pid()``.
556 The retrieved value is an ``aid_t``, which is an alias for ``long``.
558 Instead of having one mailbox per worker, you could also reorganize
559 completely your application to have only one mailbox per master. All
560 the workers of a given master would pull their work from the same
561 mailbox, which should be passed as parameter to the workers. This
562 reduces the amount of mailboxes, but prevents the master from taking
563 any scheduling decision. It really depends on how you want to organize
564 your application and what you want to study with your simulator. In
565 this tutorial, that's probably not a good idea.
570 In this exercise, we reduced the amount of configuration that our
571 simulator requests. This is both a good idea, and a dangerous
572 trend. This simplification is another application of the good old DRY/SPOT
573 programming principle (`Don't Repeat Yourself / Single Point Of Truth
574 <https://en.wikipedia.org/wiki/Don%27t_repeat_yourself>`_), and you
575 really want your programming artifacts to follow these software
576 engineering principles.
578 But at the same time, you should be careful in separating your
579 scientific contribution (the master/workers algorithm) and the
580 artifacts used to test it (platform, deployment and workload). This is
581 why SimGrid forces you to express your platform and deployment files
582 in XML instead of using a programming interface: it forces a clear
583 separation of concerns between things of very different nature.
585 Lab 3: Fixed Experiment Duration
586 --------------------------------
588 In the current version, the number of tasks is defined through the
589 worker arguments. Hence, tasks are created at the very beginning of
590 the simulation. Instead, have the master dispatching tasks for a
591 predetermined amount of time. The tasks must now be created on demand
592 instead of beforehand.
594 Of course, usual time functions like ``gettimeofday`` will give you the
595 time on your real machine, which is prety useless in the
596 simulation. Instead, retrieve the time in the simulated world with
597 :cpp:func:`simgrid::s4u::Engine::get_clock`.
599 You can still stop your workers with a specific task as previously,
600 or you may kill them forcefully with
601 :cpp:func:`simgrid::s4u::Actor::kill` (if you already have a reference
602 to the actor you want to kill) or
603 :cpp:func:`void simgrid::s4u::Actor::kill(aid_t)` (if you only have its ID).
606 Anyway, the new deployment `deployment3.xml` file should thus look
609 .. literalinclude:: tuto_s4u/deployment3.xml
612 Controlling the message verbosity
613 .................................
615 Not all messages are equally informative, so you probably want to
616 change some of the ``XBT_INFO`` into ``XBT_DEBUG`` so that they are
617 hidden by default. For example, you may want to use ``XBT_INFO`` once
618 every 100 tasks and ``XBT_DEBUG`` when sending all the other tasks. Or
619 you could show only the total number of tasks processed by
620 default. You can still see the debug messages as follows:
622 .. code-block:: shell
624 ./master-workers-lab3 small_platform.xml deployment3.xml --log=s4u_app_masterworker.thres:debug
627 Lab 4: Competing Applications
628 -----------------------------
630 It is now time to start several applications at once, with the following ``deployment4.xml`` file.
632 .. literalinclude:: tuto_s4u/deployment4.xml
635 Things happen when you do so, but it remains utterly difficult to
636 understand what's happening exactely. Even Gantt visualizations
637 contain too much information to be useful: it is impossible to
638 understand which task belong to which application. To fix this, we
639 will categorize the tasks.
641 Instead of starting the execution in one function call only with
642 ``this_actor::execute(cost)``, you need to
643 create the execution activity, set its tracing category, and then start
644 it and wait for its completion, as follows:
648 simgrid::s4u::ExecPtr exec = simgrid::s4u::this_actor::exec_init(compute_cost);
649 exec->set_tracing_category(category);
650 // exec->start() is optional here as wait() starts the activity on need
653 You can make the same code shorter as follows:
657 simgrid::s4u::this_actor::exec_init(compute_cost)->set_tracing_category(category)->wait();
659 Visualizing the result
660 .......................
662 vite is not enough to understand the situation, because it does not
663 deal with categorization. This time, you absolutely must switch to R,
664 as explained on `this page
665 <https://simgrid.org/contrib/R_visualization.html>`_.
669 Include here the minimal setting to view something in R.
672 Lab 5: Better Scheduling
673 ------------------------
675 You don't need a very advanced visualization solution to notice that
676 round-robin is completely suboptimal: most of the workers keep waiting
677 for more work. We will move to a First-Come First-Served mechanism
680 For that, your workers should explicitly request for work with a
681 message sent to a channel that is specific to their master. The name
682 of that private channel can be the one used to categorize the
683 executions, as it is already specific to each master.
685 The master should serve in a round-robin manner the requests it
686 receives, until the time is up. Changing the communication schema can
687 be a bit hairy, but once it works, you will see that such as simple
688 FCFS schema allows one to double the amount of tasks handled over time
689 here. Things may be different with another platform file.
694 From this, many things can easily be added. For example, you could:
696 - Allow workers to have several pending requests so as to overlap
697 communication and computations as much as possible. Non-blocking
698 communication will probably become handy here.
699 - Add a performance measurement mechanism, enabling the master to make smart scheduling choices.
700 - Test your code on other platforms, from the ``examples/platforms``
701 directory in your archive.
703 What is the largest number of tasks requiring 50e6 flops and 1e5
704 bytes that you manage to distribute and process in one hour on
706 - Optimize not only for the amount of tasks handled, but also for the
707 total energy dissipated.
708 - And so on. If you come up with a really nice extension, please share
709 it with us so that we can extend this tutorial.
714 This tutorial is now terminated. You could keep reading the [online documentation][fn:4] or
715 [tutorials][fn:7], or you could head up to the example section to read some code.
719 Things to improve in the future:
721 - Propose equivalent exercises and skeleton in java (and Python once we have a python binding).
723 .. LocalWords: SimGrid