Information Technology Reference
In-Depth Information
executed (see Chapter 6.7). Independently of how much simulation
time has already elapsed a simulation engine is always faced with
an identical task of computing follow-up states. The computation of
a state transition always takes the same amount of wallclock time
and therefore runtime grows almost linearly with elapsed simulation
time. Although the computation of state changes associated with
any successfully executed action accounts for a great deal of the
overall runtime, the potentially more crucial aspect is the evaluation
of constraints defined within an agent-based model (see Chapter 6.6.4).
As constraint evaluation takes up to
O
(
n
2
) runtime (with
n
A
referring to the number of agents) it has a very dominant influence
on overall runtime (cp. [48]). Assuming that all
n
A
agents have
at least one effector and that all effectors take one time step to
execute,
n
A
effector actions are executed simultaneously. Assuming
further that only one constraint is defined which determines whether
an effector action may be executed or not (depending on the other
effector actions), each action
a
needs to be checked against
n
A
−
A
1
other actions which results in
n
A
×
(
n
A
−
1) constraint evaluations.
Even assuming symmetry reduces this number only to
2
(
n
2
n
A
)and
therefore runtime of constraint evaluation is expected to be quadratic
in the number of agents
n
A
.
In order to achieve reasonable speedups quadratic growth in runtime
needs to be avoided [125]. Given the nature of the constraints and the
inherent possibility of actions to interfere with each other, evaluating
constraints of
n
agents, respectively actions, results in quadratic
runtime. In this case, the best possible solution is to largely reduce
the number
n
of agents or actions which may interfere with each
other. This way quadratic runtime is still required, but only for small
numbers
n
of actions. Reducing the numbers of evaluations whether
two or more actions are interfering can mainly be achieved by the
following two means:
A
−
