APSwarm (Automatic Parallel Swarm) is an approach for the efficient and transparent parallelization of a large class of swarm algorithms, specifically those where the multi-agent paradigm is used to implement the functionalities of bio-inspired entities, e.g., ants, birds etc. Parallelization is achieved by partitioning the space on which agents operate onto multiple regions, and assigning each region to a different computing node. Data consistency and conflict issues, which can arise when several agents concurrently access shared data, are handled using a purposely developed notion of logical time. This approach [Cicirelli et al. 2014] enables a transparent porting onto parallel/distributed architectures, as the developer is only in charge of defining the behavior of the agents, without having to cope with issues related to parallel programming and performance optimization.

The approach and a related software architecture aimed to the efficient parallelization of the swarm algorithms for which individuals can be implemented as situated agents immersed in a bidimensional territory. With our approach, the management of the shared territory is transparent for the developer, who remains in charge only of defining the behavior of the agents, without having to cope with issues related to parallel/distributed programming and performance optimization. Our methodology exploits the space partitioning approach, which consists of assigning different regions of the territory to different computing servers. Data consistency issues are not tackled by resorting to lock-based mechanisms and high-level synchronization primitives, which can impair the execution performance and scalability. Conversely, our approach exploits a special-purpose notion of logical time [Lamport 1978] to manage shared information properly. Labels, i.e., natural numbers associated with logical time, are assigned to agents to enforce an order to their operations and prevent any concurrent write-mode access to shared data.

The software architecture is composed of two coarse-grain entities: the Agent Layer and the Middleware Layer. The former contains the agents that implement and execute the code of the agent algorithm. The latter implements the mechanisms required for the parallalization, and contains two main components: the Territory component, that copes with the management of the territory, and the Control Machine that executes the main control loop through which the agent operations are executed step after step. The two layers interact through two software interfaces: the Territory interface and the Agent interface. The Territory interface is used by agents to read/write the territory space regardless from the specific implementation of the Territory component. Analogously, the Agent interface is used by the Control Machine to execute the agent operations regardless from the specific nature of the agents and from the implementation of their functionalities. This decoupled structure facilitates the transparent porting from the sequential to the parallel case. Indeed, the correct use of the Territory interface is the only requirement that an agent must match in order to execute the code independently of the type of execution scenario, sequential or parallel. The following figure shows the software architecture in the parallel execution context.

References  

F. Cicirelli, A. Forestiero, A. Giordano, and C. Mastroianni. 2014. An Approach for Scalable Parallel Exe- cution of Ant Algorithms. In International Conference on High Performance Computing & Simulation, HPCS 2014. Bologna, Italy.

L. Lamport. 1978. Time, clocks and the ordering of events in a distributed system. Commun. ACM 21, 7 (1978), 558–565.