Methods |
Corresponding author: Christopher John Topping ( cjt@ecos.au.dk ) Academic editor: Matthias Filter
© 2024 Christopher John Topping, Xiaodong Duan.
This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Citation:
Topping CJ, Duan X (2024) Managing large and complex population operations with agent-based models: The ALMaSS Population_Manager. Food and Ecological Systems Modelling Journal 5: e117593. https://doi.org/10.3897/fmj.5.117593
|
We describe the method used to manage large and complicated populations of autonomous agent-based animal models in the Animal Landscape and Man Simulation System, as implemented in the ALMaSS Population_Manager class. Using three examples, we show how this approach facilitates the representation of populations in a mixed serial and parallel computer model, contributes to the efficiency of code operation and allows detailed behavioural representations to be modelled.
ALMaSS, Agent-based model, multi-threaded software, scheduling, simulation
The Animal Landscape and Man Simulation System (
The role of the population manager in ALMaSS is to hold and manipulate lists of entities (typically agents) that are the focus of a particular model. It is responsible for scheduling actions by agents or other population objects and reporting the population status.
ALMaSS is written in C++ and uses a solid object-oriented approach in its design, which is used to tailor instances of the population manager to specific purposes, such as a skylark population manager or a ladybird population manager. The concept used is that all approaches common to all population managers are defined in the base class Population_Manager and those that are specific to a particular case are defined in descendant classes that inherit the base class code. Inheritance is a pillar of object-oriented programming. The Population_Manager class structure also uses polymorphism, whereby inherited code can be altered in descendent classes. For example, the DoFirst method described below is re-implemented differently for every population manager class, allowing each specific case to exhibit its own behaviour. The use of the Population_Manager class and its descendants is an example of abstraction and encapsulation. As such, the details of the workings of the class are kept within itself, hiding this and the associated data from other parts of the code. This design means that the Population_Manager class is a fully functional entity with an interface to the rest of the ALMaSS simulation.
Interestingly, although potentially highly influential on the outcome, the management of populations of agents in population models seems to have received scant attention in literature.
Some model systems do provide methods for altering scheduling, such as Repast Symphony (
As ALMaSS is a framework for modelling the base Population_Manager classes, it must be constructed to allow maximum expression in the specific models that are derived from it. This expression was attempted using a standard structure that can be adapted using an object-oriented approach in descendent classes. To exemplify this, we provide a minimalist ALMaSS species model to explore the consequences of the population management methods used.
The primary code entity described here is the Population_Manager class and its design. The Population_Manager is the main controlling structure for modelling the populations of agents within ALMaSS. It is presented below, followed by examples demonstrating the utility of the design implemented in ALMaSS.
The Population_Manager class is itself derived from the Population_Manager_Base. The latter contains all the information needed by the agent-based and any other potential type of population manager. The Population_Manager class inherits all aspects of the base class; thus, the functionality is described below as belonging to the descendent class, but where noted below, it is implemented in this base class.
The Population_Manager is never actually used to instantiate an object; instead, it is always used to create a derived class object, for example, Skylark_Population_Manger, which is then implemented for use. The derived class inherits all the Population_Manager functionality. It adds model-specific information, such as the number and type of life stages and all necessary input/output to manage the simulations for the species under consideration. This added functionality includes any species-specific output formats used for this species only. This class structure allows further differentiation for future and more specific models. For example, the class hierarchy for beetles currently comprises three levels (Fig.
Class data structures
The core of this class is a list of all individuals present in the population, which is the most important data structure used. In the original ALMaSS design, the population manager held all individuals in agent-based models in a data structure with a variable number of entries, one for each life stage represented as a separate class in the model. This means that this data structure must be traversed serially in scheduling and other operations and, for simulations with many organisms, this is inefficient. However, a relatively easy option exists for managing these lists in parallel with modern CPUs and code libraries. This option is now implemented in the current version of the population manager code.
Instead of having a single list for each object type, the list of objects is now created as a set of lists, one for each thread. These are denoted as ‘TheSubArrays’ within the program code. ‘TheSubArrays’ is a vector of vectors of forward_list. Vectors are arrays that can change in size during run time and are randomly accessed, thereby allowing the number of lists to be altered at run time to match the number of threads. A forward_list is a C++ container for a singly-linked list (each object points to the next), which is an efficient way to manage a list of objects that can be added to by pushing objects on to the end of the list. These two flexible structures mean that the size of the population can be determined at run-time and can be easily manipulated by descendant classes.
The first dimension of ‘TheSubArrays’ represents the types of population entities managed by the population manager, typically the life stages of the modelled organism. This approach allows descendant classes to change the number of life stages modelled by changing the first dimension. The second dimension of ‘TheSubArrays’ is the thread number, enabling parallel running when more than one thread is used. If only a single thread is used, the simulation is run sequentially. Thread-based parallel computing was implemented using OpenMP (
The key feature of Population_Manager is the method used to schedule and manage simulated individuals’ behaviour. The top-level ALMaSS simulation loop is called from the main scheduling loop, which can be set to loop as many times as necessary to simulate the desired length of the time step (usually one day or 10 minutes in the models created to date). For each time step, the period is separated into ‘pseudo time’, which shares some components of sequential real time, but also allows complex time scheduling of activities, further detailed below. Before each time step can start, some specific fixed actions are needed. The first is to delete the objects of dead individuals from the previous time step and distribute the live individuals evenly to the threads, which results in the release of their allocated memories and optimises the use of the threads. The following action indicates that all individuals are ready to start the time step by a simple flag set for each individual. This flag is critical to the following scheduling process. The flag is called StepDone and is set to false for all objects in ‘TheSubArrays’. Before any output is carried out, the final action is to carry out any required ordering of the lists in TheSubArrays. This reordering is typically to randomise the order of the lists, but can be set to order, based on characteristics such as location. Different orderings have different purposes and randomising the list is the best way to ensure that the order of individuals’ actions does not affect the outcome, thus avoiding concurrency issues (
Following the initial set of actions, the main scheduling process is started. It consists of a higher-level sequence containing an iterative loop. The scheduling process includes three main methods: BeginStep, Step and EndStep, each preceded and followed by a customisable ‘Do’ method (Fig.
‘BeginStep’ and ‘EndStep’ have similar structures. Each iterates through all objects in parallel, depending on the number of threads and calls their ‘BeginStep’ or ‘EndStep’ methods, respectively. This process allows one type of behaviour or sets of behaviour to be selected at the beginning and end of a time step. ‘Step’ differs in that for this process, each object is called once following the order of objects in ‘TheSubArrays’; it is also performed in parallel, depending on the number of threads used. This procedure is repeated for each object that did not set the flag ‘StepDone’ to true. Thus, all objects that did not signal that they finished the ‘Step’ process are called in the order of objects in ‘TheSubArrays’. The Step completes when all objects signal that ‘StepDone’ is equal to true. The current implementation of the step process requires only one iterative sub-process, which is assigned to Step, a pragmatic decision, based on need. To date, there have been no situations where ‘BeginStep’ and ‘EndStep’ needed to be iterative.
The emergent behaviour from the overall time step processes is that behaviour can be scheduled for different life stages differently, such that complex interactions between life stages can be simulated. It also implements a state machine for the ‘Step’ process, allowing highly flexible behaviour sets to be simulated. A final touch to the iterative process is that an individual object can force another to return to the Step code by altering its ‘StepDone’ flag. This “event” facility is particularly useful for closely-connected objects, such as pairs or family groups.
Several agents in the same life stage run simultaneously when the individuals are looped inside the three-step methods; this is the critical procedure to accelerate the simulation running. However, this can cause problems when more than one individual accesses the same resources. The issue here is the simultaneous use of a resource by multiple agents. In this case, both may assume that they obtain it. These situations would result in serious program bugs and be challenging to track. To avoid this, we introduce a “guard map” for the landscape by segmenting the landscape into non-overlapping grids. Each grid has a “guard flag” to ensure that only one individual can perform location-related activities in a single grid. Before an individual tries to perform an activity in a specific location, it must possess the “guard flag” for that location. This “guard flag” stops other agents from carrying out behaviour here and, once the behaviour is completed, the flag is released. If the behaviour is triggered from the ‘BeginStep’ or ‘EndStep’ functions, the agent will simply wait and try the action again later in that time-step section when the flag is released. An enforced wait is needed because only one loop is executed in the ‘BeginStep’ and ‘EndStep’ functions. In the ‘Step’ function, waiting is unnecessary per se since it can be skipped automatically and the next individual will be called. Since the ‘Step’ function is iteratively called until all agents report ‘StepDone’ is true, the agent will automatically wait and try again in the next loop. Loops will continue until all individuals’ ‘StepDone’ flags are “true” in the ‘Step’ function, allowing all agents to complete their actions and release the guards.
Before-step actions
This example illustrates the use of before-step actions. These can do nothing, randomise the list or sort based on the x- or y-coordinate (this last option is for single-threaded execution only). To demonstrate the necessity of this functionality and the need for care in selecting the order of execution, we created a very simple ALMaSS individual-based model, ‘Theoretical1’, which represents animals competing for a limited resource. The model represents competition for food, which is provided to match the needs, based on the number of individuals (each gets 1.0 units). However, they will forage randomly and get 0.5–1.6 food units daily. Food is translated directly to growth. Each day, each individual selects another at random. If it is 20% larger than the other individual, it can eat that individual and grow 0.5% of the eaten individual’s size. Fig.
Here, we demonstrate the utility of the step design using the skylark model (
In the real world, all these types of behaviour are integrated over the day as a series of ongoing activities. Since the time-step of the model is one day, this integration is impossible. Still, it is possible to replicate the overall time-step behaviour using the BeginStep, Step, EndStep algorithm.
To manage the behaviour, the first action is to order the processes logically so that no process depends on another that follows it. In this case, the order can be defined as a – h above. Thus, the male’s first activity is to determine the forage amount available (which is also communicated to the female). He then collects the forage, removes his energetic needs and finally allots portions to each chick. All of this behaviour is carried out in the BeginStep. In the Step, the female uses the information gathered by the male to determine the forage available, subtracts her needs and allots food to the chicks. In the EndStep, the chicks use the information on allotted forage and then determine their daily growth. As noted, these activities are integrated over the day in the real world. Using this method and viewed outside of the time-step, this integration is also the case. However, the separation of the time-step into ‘pseudo-time’ allows this integration to be carried out computationally efficiently. The alternative would be complicated and require multiple iterations through the life stages as each carries out part of the time-step, thus incurring a higher overall computational cost.
For the third example, we aim to illustrate the impact of varying thread counts on the execution time. The ‘Theoretical2’ example involves the creation of 10,000 animal objects. For each time-step, the population experiences 1040 new-born animals with 1000 dead animals, resulting in a gradually expanding population. Each animal is composed of a data structure containing 1,000 real number values. Within the Step function, 10,000 calculations, each squaring a double value, are performed for each animal and no other functionalities are associated with ‘Theoretical2’ animals. All the simulations were run using the same ten by ten km landscape and each run had a duration of 5 years. The ALMaSS simulations require the landscape, but, in this simple example, the landscape does not affect the difference in the run time since Theoetical2 does not interact with it. The run time depends entirely on the number of threads and the population size. The run time for different thread counts is presented in Table
Since its release, ALMaSS and the Population_Manager class have been used to simulate a wide range of species ranging from highly numerous beetles, where simulations are recorded with > 50 million concurrent agents. Species modelled include beetles, spiders, newts, skylarks, hares, roe deer with highly detailed 10-minute time-step behaviour (
‘Theoretical1’ is a minimal implementation of an ALMaSS agent-based model. This publication provides the code to show how this model was implemented and provides the basis for developing new models (Appendix
The results of the simple food scenario raise some interesting points. During testing, it was clear that the precise results depend on the size of the benefit of the rate of growth when eating another individual and, therefore, the chance of a single individual diverging enough from the rest of the individuals to be able to start to eat them. This model is somewhat similar to the seminal work on individual-based models modelling wide-mouth bass in a fish tank (
ALMaSS run times are often very long and CPU development has been geared towards expanding the number of processing cores rather than continuing the increase in CPU speed seen in the 1990s to early 2000s. Hence, to increase efficiency in exploiting modern CPU architecture, ALMaSS needed to address the potential to use multiple cores. ‘Theoretical2’ represents a minimalistic implementation of the ALMaSS agent-based model to demonstrate the potency of multithreading capabilities. The flexibility inherent in its multithreading implementation is noteworthy. By configuring the thread count to 1, the model transforms into a sequential computation equivalent to the original ALMaSS implementation. As the thread count increases, the speed enhancement increase is reduced. This phenomenon might be attributed to the synchronisation overheads associated with managing threads, which aligns with the complexity of the simulation process. This result also suggests that complex models could benefit more from multithreaded code than initially anticipated since these models are usually computationally heavier compared to the cost of managing multi-threads.
Factors that affect this change in efficiency include the guard-map size and step-code complexity. The guard-map resolution will determine the frequency of thread locking in space; hence, the finer this can be, the fewer locks are needed. However, the guard-map grid size cannot be too small since interactions may occur beyond it, especially in the case of broad area interactions (e.g. a density-dependent calculation working on an area larger than 1 m2). Step code complexity will also affect the optimal thread number needed. In an extreme case where the step code is empty, it will result in a simple loop; in this case, the optimal thread number will always be one. Hence, we cannot yet provide precise guidelines regarding the best thread number to choose; it will depend on the simulation being run.
As noted above with the guard-map, when implementing multithreaded code in an ALMaSS model, some care is needed to ensure that key activities where individuals interact with the same resource cannot occur during parallel processing tasks, such as ladybirds eating aphids in the same location. We have created the guard-map to control access to spatially-related resources, which includes other agents. Functions are provided to claim a guard, based on the individual’s location when it is doing location-related activities, for example, moving to a new location or eating resources from a location and release the guard when the individual finishes its’ location-related activities. However, there is one case in which this method cannot protect the multithreaded code. The guard-map fails if an agent can kill another agent of the same type at the same location. For example, two adult ladybirds, one eating the other. The possibility of this kind of interaction needs to be considered in new models and multithreaded code should be disabled if this is the case.
The ALMaSS Population_Manager class has stood the test of time for more than 20 years and has not had a major update until now. The current implementation introduces the new multithreaded code feature for efficiency, which provides significant gains in processing time with minimal increase in memory footprint.
The scheduling of ALMaSS agents provides the flexibility to describe complex behaviour and interactions between agents. However, how the scheduling should be implemented for a specific model should be an active choice to avoid the potential for artificial bias in the outcomes.
The authors have declared that no competing interests exist.
No ethical statement was reported.
This work was partially supported by DeiC National HPC (UCloud, GenomeDK, LUMI) (g.a. DeiC-AU-N1-000025, DeiC-AU-L5-0011 and DeiC-AU-N2-2023015) and by the EcoStack project funded by the European Union's Horizon 2020 Research and Innovation Programme under Grant Agreement no. 773554.
Conceptualization: CJT. Formal analysis: XD. Methodology: CJT. Software: XD, CJT. Writing - original draft: CJT. Writing - review and editing: XD.
Christopher John Topping https://orcid.org/0000-0003-0874-7603
Xiaodong Duan https://orcid.org/0000-0003-2345-4155
All of the data that support the findings of this study are available in the main text or Supplementary Information.
The source code and the running directory are publicly available at:
https://gitlab.com/ALMaSS/almass_methodology.git
See also Suppl. material
The code documentation for the ALMaSS Population_Manager class
Data type: pdf
Explanation note: The doxygen generated documentation from the ALMaSS code for the Population_Manager class.