Information Technology Reference
In-Depth Information
Defining partitioning strategies is the easy task; the hard part is
to actually compute a partitioning. An optimal partitioning strategy
ensures that a maximum number of agents may be executed in parallel.
Computing the desired number of partitions of independent agents is
equivalent to the graph partitioning problem which is known to be
NP-complete. Therefore, computing partitions of independent agents
has to rely on heuristic methods. Typical heuristic methods include
spatial decomposition as well as action-dependent decomposition.
Given a specific partitioning, it is easy to evaluate its quality
a
posteriori
by measuring runtime and calculating the speedup achieved
by using this partitioning strategy. Yet, it is hardly possible to
evaluate the quality of a partitioning strategy
a priori
. Typical
indicators used to evaluate the quality of a specific partitioning include
the equality of distribution of agents to partitions, minimization of
agent interaction across partition boundaries, minimization of network
trac, etc. Unfortunately, these indicators are often hard to compute
and of little predictive value regarding achievable speedup.
Model partitioning has to go hand in hand with parallel execution
of the simulation engine that actually executes the model. This thesis
defines parallelization of a simulation engine on three levels: At first,
parallel execution may be applied on processor-level (i. e., usage of
multi-core processors); secondly, parallel execution may be applied
on node-level by usage of multiple processors within one computing
node and thirdly, parallel execution may be applied on cluster-level
by the usage of multiple computing nodes. Multi-level parallelization
refers to simultaneous application of parallelization on multiple levels,
e. g., by combining cluster-level and node-level parallelization.
An example implementation of the GRAMS reference model has
been developed to demonstrate its practical applicability. The example
implementation resembles the GRAMS reference model very closely.
Two different single-threaded simulation engines were implemented
(one using a time-stepped execution control, and the other one using
an event-driven execution control) as well as a multi-threaded event-
driven simulation engine. As expected all simulation engines produce
identical results when executing the same model. The conformance of
