Information Technology Reference
In-Depth Information
A tacit assumption often made when using spatial decomposition is
that it is possible to split a model (environment and agents) into the
required number of partitions. The maximum number of partitions is
usually determined by the number of threads that may be executed
in parallel. To exploit maximal parallelism, a model has to be split
up into the same number of disjoint partitions. In this context,
disjoint
refers to partitions of a model which do not influence each
other (i.e., agents of the respective partitions do not interfere with
each other). Although spatial decomposition is often used with good
results [125, 97, 78, 114], it may be impossible or inecient to compute
the necessary number of disjoint partitions for a wide variety of agent-
based models.
At least two different types of spatial decomposition are conceivable:
1.
Informed
spatial decomposition
As mentioned above, the set of agents is split into disjoint sets
which can not influence each other as they are too far apart and
thus belong to different spatial regions.
2.
Uninformed
spatial decomposition
A second approach is to specify spatial regions in advance without
taking into account context information. Each region is assigned
to a separate computing thread which takes care of all agents
within this region. Obviously, this approach will most probably not
produce an optimal decomposition of the set of agents. However,
this approach is easy to implement and introduces only minimal
overhead for computing an initial partitioning and updating the
mapping of agents to specific spatial regions.
Action-dependent decomposition
An alternative to partitioning a model along spatial boundaries is to
partition the currently executed actions according to their type. This
partitioning strategy aims at executing those actions simultaneously
by different threads which are not able to interfere with each other due
to their nature. In general, many types of actions are very different
