by Chris Greenough, Shawn Chin, David Worth, Simon Coakley, Mike Holcombe and Mariam Kiran
The Flexible Large-scale Agent Modelling Environment (FLAME) has been developed in a collaboration between the Computer Science Department at the University of Sheffield and the Software Engineering Group at the STFC Rutherford Appleton Laboratory. FLAME is an applications program generator for agent-based simulations. Using the modeller's definition of the agent-based model and the associated C-code that implements the agent actions and state changes of the agents, FLAME generates the user's application using program templates as either a serial or parallel code.
There are many agent-based modelling (ABM) systems. Many of these systems are based on Java as their implementation language. Although a good language for Web-based and some communications applications, it is not one often used in the area of high-performance computing. Similarly there are relatively few agent systems that address the problem of scalable parallel simulations.
The essence of an agent-based application is that the basic elements of the model can be represented by autonomous entities (agents) that can communicate with other agents in the model and act (perform tasks or computations or even communicate information to the agent population) based on that information. This makes them ideal to model many situations in which discrete elements interact.
Cell biology, transport logistics, behavioural science, and financial and economic markets are a few of the many application areas in which ABMs have been successfully used.
A major problem has been that these models are computationally very intensive and in a population of p agents, p2 interactions can be common. Consequently to date only relatively small populations have been modelled.
FLAME has been developed in a collaboration between the Computer Science Department of the University of Sheffield and the Software Engineering Group at STFC Rutherford Appleton Laboratory. One of its aims was to develop implementation techniques for agent-based simulation that could exploit high-performance computing systems.
FLAME is an applications program generator for agent-based simulations. Using the modeller's definition of the agent-based model and the associated C-code that implements the actions and state changes of the agents, FLAME generates the user's application using program templates as either a serial or parallel code. This is illustrated in Figure 1: the model and agent functions are provided by the model developer and FLAME provides the program templates that the xparser uses to generate the simulation code. The final application executable is built as a serial or parallel application as required by the developer using the FLAME Message Board Library.
Figure 1: The FLAME framework.
It must be noted that the FLAME framework is not the application, but rather the application generator. Any approach to parallelisation must be embedded in FLAME’s program templates and be applicable to a generic agent-based simulation. Although this underlying generic architecture determines much of the potential parallelism in applications, the agent model must contain that parallelism at a task level so that FLAME might be able to utilise it.
It is well understood that a knowledge of task locality and task communication are key elements in achieving efficient and scalable parallel performance. Even if an application has many potentially independent tasks that could be executed in parallel, the balance between the computational and communication loads will greatly affect any parallel performance. These ideas can be expressed in terms of the granularity of application: what are the relative sizes of the computational and communications loads of each of these independent tasks.
Figure 2: A representation of the parallel decomposition used in FLAME.
As with most computational problems there is a computational load, but significantly for agent applications there is a communications load – the information flowing between agents.
FLAME distributes the computational load – the agents themselves – over the processing elements to produce some form of computational load balance in a conventional way. However, the communications load or data load is also distributed over the processors. Each communication type between agents has its own message repository (message board) and these are distributed over the processors. During the simulation a process of message board synchronization is performed to ensure that agents receive the information they require.
FLAME combines the use of multi-threading with Message Passing Interface (MPI) to improve parallel performance. One thread is used for computational work and a second handles all communications. The placement of these message board sychronisations has a fundamental effect on the parallel performance of the application.
Each agent can be decomposed into linked state changes. These states might involve computation or communication. FLAME uses a state graph to schedule agent operations and to exploit parallelism. FLAME schedules nodes (tasks) in this graph to maximise the communication time available to any message board synchronisation task. In this way the information wait time for any agent is minimised.
The FLAME technology has been used with great success in a variety of application areas in both its serial and parallel modes.
Figure 3: Some results from the EURACE model using a population of 22,000 agents.
Within the EURACE project, FLAME has been used to develop a very complex multi-agent simulation of the European economy involving agents such as banks, firms, households etc. With the EURACE model there were nine agent types and over 60 types of communication message. The EURACE model represented the three major markets in an economy: labour, goods and financial.
In parallel processing terms the model can be view as a tightly coupled, fine- grained application and hence not particularly amenable to large-scale parallelism. In some simpler problems from biological applications the FLAME applications have shown reasonable speedups with populations of one million agents. However, the performance of the significantly more complex EURACE model gives encouragement for the FLAME approach achieving some acceptable speedups on small numbers of processors with a population in the order of 22,000 agents.
We are undertaking further research and development to improve the communications latency in the FLAME synchronisation process, along with the development of more sophisticated message filtering techniques to reduce the data flow between processors.
This work was funded by the EURACE project (STREP-35086), which in turn is funded by the European Commission’s 6th Framework Programme. Details of the partners and outputs can be found at the EURACE Web site.
Links:
EURACE: http://www.eurace.org/
FLAME: http://www.flame.ac.uk
Please contact:
Chris Greenough
STCF Rutherford Appleton Lab, UK
E-mail:
