Information Technology Reference
In-Depth Information
updating a partitioning costs time and has to be evaluated against
the benefits gained by an improved partitioning.
In summary, static and dynamic partition computation strategies
represent different update rates ranging from once during a simulation
(static) to multiple updates during a simulation (dynamic). Addition-
ally, dynamic partition computation strategies may exploit statistical
knowledge gained during a simulation.
The quality of a specific partitioning depends on many factors.
Obviously, a partitioning is considered better if the runtime for a
simulation is reduced as far as possible. Unfortunately, it is not easy
to tell in advance which strategy is best. Strategies may be devised to
distribute agents or actions uniformly across partitions (assuming this
results in maximized parallelism and therefore maximum speedup) or
to partition a model in a way that communication between nodes is
minimized (assuming network connections between nodes are limiting
elements). Although all these assumptions and considerations may
be correct, it is impossible to estimate in advance which strategy
produces the best results. As dynamics of a model change during
execution of a simulation, it is very likely that at different points in
time different partitions are most suited. Similar questions are also
addressed by research in the areas of load balancing [29, 118, 32]and
online algorithms [7].
In the following, different partitioning strategies covering a wide
range of issues discussed in this section are specified. The available
computing nodes are denoted by
N
1
...N
m
. Each node
i
may execute
n
i
threads concurrently, and subsequently the available threads for
each node
N
i
are denoted by
T
1
...T
n
i
. If only one node is considered
the superscript
i
indicating the node is dropped, hence the available
threads are denoted by
T
=
{
T
1
...T
n
}
.
8.1.2 Conflict detection as bottleneck
The GRAMS reference model defines simulation as a sequence of
state transitions. The computation of a state transition takes only
into account the current model state and an event which has to be
