Parallelisation and Java
In this practical you'll see how we parallelise a simple model, and then we'll run the model on across a set of cores.
This program will be standard Java, but will use MPJ Express to add parallel behaviour. The model we'll run will be a stripped-down version of the model used in this paper. It presents the fundamental model dynamics without any of the detail of what is being modelled. Essentially it provides a landscape full of randomly scattered agents. The agents move to another location if their density is too high. Eventually this should evenly spread the agents. If you read the paper, you'll see that this was used to replicate the behaviour of aphids, which have a density-dependent set of behaviours including movement.
The first thing to consider is how we are going to divide our modelling task up. Most geographical models have agents acting over a landscape and time, and the agents engage in actions/processes on the basis of communication with other agents and interrogation of the attributes of the landscape.
We want to divide up the processing done to different nodes (PCs/cores), but we need to do it in a way that minimises the transfer of data between the nodes as these take time. This means limiting the movement of agents between nodes, and/or the communication between agents on different nodes, and/or the interrogation by an agents on one node of landscape attributes on another.
Most geographical systems can be divided up so that either the landscape or the agents are evenly spread across the nodes and the data transfer minimised. The following table show the things to take into consideration:
| Agent Movement | Landscape Interrogation | Agent Communication | Solution |
|---|---|---|---|
| Low | Local | Low | Divide up space and the local agents |
| Low | Local | High but local | Divide up space and the local agents, using boundaries between high-communication groups |
| High | Local/Global | Low | Divide up agents, each having their own landscape |
| High | Local/Global | High | Difficult |
NB: I've never seen a division by time, though it must be possible in some systems. | |||
The worst case scenario is when the agents move around interrogating the landscape, but also need to communicate with each other. Under these circumstances you need some creative thinking to make parallelization worthwhile.
Take our model: you have 1000 agents moving around a square space of 10 by 10 cells with no specific attributes in each cell. When the density of agents in a cell gets too great, they move on. Say you have 10 nodes.
We can't divide up the landscape into 10 blocks of 10 cells and deal with each block on a separate node, as we expect the agents to frequently move around and this would cause agents to move between nodes (maybe 100 agents from each node would need to move to 10 other nodes each iteration - even if we put the agents in an array to move them, we might need 10 communications per node per iteration). Equally, we can't divide up the agents and treat groups of agents independently, each having its own copy of the landscape, as each agent needs to find out how many other agents are in the same cell in the landscape (so we might, at a minimum, have 100 calls, one from each node to each other of the ten nodes; at worst each agent could ask each other agent its location -- then we could have towards a million calls).
So, what's the solution? The solution is to divide up the agents, but rather than each agent querying every node to find out which agents on other machines are at its coordinates, we pass a simple density map for each node back to a central node, which adds them up and sends a map of the summed densities back to each node once per iteration (so two communications - one out, one in, per node per iteration).
Of course, if all your agents need to move and communicate in detail with each other, you are probably sunk on speed - though a parallel architecture still gives you advantages in terms of memory.
Next: Building the model.