PARALLEL AGENT-BASED SIMULATION ON A CLUSTER OF WORKSTATIONS
Abstract
We discuss a parallel implementation of an agent-based simulation. Our approach allows to adapt a sequential simulator for large-scale simulation on a cluster of workstations. We target discrete-time simulation models that capture the behavior of Web users and Web sites. Web users are connected with each other in a graph resembling the social network. Web sites are also connected in a similar graph. Users are stateful entities. At each time step, they exhibit certain behaviour such as visiting bookmarked sites, exchanging information about Web sites in the "word-of-mouth" style, and updating bookmarks. The real-world phenomena of emerged aggregated behavior of the Internet population is studied. The system distributes data among workstations, which allows large-scale simulations infeasible on a stand-alone computer. The model properties cause traffic between workstations proportional to partition sizes. Network latency is hidden by concurrent simulation of multiple users. The system is implemented in Mozart that provides multithreading, dataflow variables, component-based software development, and network-transparency. Currently we can simulate up to 106 Web users on 104 Web sites using a cluster of 16 computers, which takes few seconds per simulation step, and for a problem of the same size, parallel simulation offers speedups between 11 and 14.
References
S. Lelis , Second Kyoto Workshop on Digital Cities,LNCS 2362 (Springer, 2001) pp. 41–55. Google Scholar-
D. L. Watts , Small Worlds: the Dynamics of Networks Between Order and Randomness ( Princeton University Press , 1999 ) . Crossref, Google Scholar -
Y. Matsuo , Clustering using Small World Structure , Proc. of the Int. Conf. on Knowledge-Based Intelligent Information and Engineering Systems ( Crema, Italy , 2002 ) . Google Scholar - Mozart Consortium, The Mozart Programming System, http://www.mozart-oz.org/ . Google Scholar
-
P. Van Roy and S. Haridi , Concepts, Techniques, and Models of Computer Programming ( MIT Press , 2004 ) . Google Scholar - A. Graps, N-Body/particle simulation methods, www.amara.com/papers/nbody.html (2000) . Google Scholar
-
B. P. Zeiglar , H. Praehofer and T. G. Kim , Theory of Modeling and Simulation: Integrating Discrete Event and Continuous Complex Dynamic Systems ( Academic Press , 2000 ) . Google Scholar -
R. M. Fujimoto , Parallel and Distributed Simulation Systems ( Wiley , 2000 ) . Google Scholar A. Fersche , Parallel and Distributed Computing Handbook (McGraw-Hill, 1996) pp. 1003–1041. Google ScholarD. M. Dicol , Principles of Conversative Parallel Simulation, Proc. of the 28th Winter Simulation Conf. (1996) pp. 128–135. Google ScholarE. H. Page , Beyond Speedup: PADS, the HLA and Web-Based Simulation, Proc. of PADS'99 (IEEE Society Press Press, 1999) pp. 2–9. Google ScholarF. Wieland , E. Blair and T. Zukas , Parallel Discrete-Event Simulation (PDES): A Case Study in Design, Development, and Performance Using SPEEDES, Proc. of PADS'95 (IEEE CS Press, 1995) pp. 103–110. Google ScholarA. C. H. Chow and B. P. Zeigler , Parallel DEVS: A Parallel, Hierarchical, Modular, Modeling Formalism, Proc. of the 26th Winter Simulation Conf. (1994) pp. 716–722. Google Scholar-
J. Cowie , Towards Realistic Million-Node Internet Simulations , Proc. of PDPTA'99 ( CSREA Press , 1999 ) . Google Scholar - IEEE Transactions on Parallel and Distributed Systems 13, 433 (2002). Crossref, Web of Science, Google Scholar
S. L. Ferenci , K. S. Perumalla and R. M. Fujimoto , An Approach for Federating Parallel Simulators, Proc. of PADS'00 (IEEE CS Press, 2000) pp. 63–70. Google Scholar- Parallel Computing 27, 1611 (2001). Crossref, Web of Science, Google Scholar
- ACM Transactions on Modeling and Computer Simulation (TOMACS) 6, 210 (1996). Crossref, Google Scholar
R. M. Fujimoto , Parallel and distributed simulation, Proc. of the 27th Winter Simulation Conf. (1995) pp. 118–125. Google Scholar-
U. Legedza and William E. Weihl , Proceedings of the 10th workshop on Parallel and Distributed Simulation ( IEEE CS Press , 1996 ) . Google Scholar - Proceedings of the SCS Multiconference on Distributed Simulation,
Simulation Series no. 3 19, eds.B. Unger and D. Jefferson (SCS, 1988) pp. 34–44. Google Scholar , - Proceedings of the 6th Workshop on Parallel and Distributed Simulation, eds.
M. Abrams and P. F. Reynolds Jr. (SCS, 1992) pp. 117–126. Google Scholar , T. K. Som and R. G. Sargent , Model structure and load balancing in optimistic parallel discrete event simulation, Proceedings of the 14th workshop on Parallel and Distributed Simulation (IEEE CS Press, 2000) pp. 147–154. Google ScholarR. Schlagenhaft , Dynamic load balancing of a multi-cluster simulator on a network of workstations, Proceedings of the 9th workshop on Parallel and Distributed Simulation (IEEE CS Press, 1995) pp. 175–180. Google ScholarL. F. Wilson and D. M. Nicol , Experiments in automated load balancing, Proc. of the 10th workshop on Parallel and Distr. Simulation (IEEE CS Press, 1996) pp. 4–11. Google Scholar-
B. P. Zeigler and D. Kim , Design of high level modelling/high performance simulation environments , Proc. of the 10th workshop on Parallel and Distributed Simulation ( IEEE CS Press , 1996 ) . Google Scholar D. M. Nicol and P. F. Reynolds , An optimal repartitioning decision policy, Proceedings of the 17th Winter Simulation Conf. (ACM Press, 1985) pp. 493–497. Google Scholar- Proceedings of the IEEE 89, 174 (2001). Crossref, Web of Science, Google Scholar
A. M. Uhrmacher and K. Gugler , Proc. of PADS'00 (IEEE CS Press, 2000) pp. 101–108. Google ScholarJ. Anderson , A Generic Distributed Simulation System for Intelligent Agent Design and Evaluation, Proc. of the 10th Int. Conf. on AI, Simulation, and Planning in High Autonomy Systems (2000) pp. 36–44. Google Scholar-
N. Cetin , Large-Scale Multi-Agent Transportation Simulations , Proc. of the Workshop on Cellular Automata, Neural Networks and Multi-Agent Systems in Urban Planning ( Milan, Italy , 2001 ) . Google Scholar - J. of Systems Architecture 46, 1205 (2000). Crossref, Web of Science, Google Scholar
V. Strumpen , Software-Based Communication Latency Hiding for Commodity Workstation Networks, Proc. of ICPP'96 (CRC Press, 1996) pp. 146–153. Google Scholar- Parallel Computing 26, 1297 (2000). Crossref, Web of Science, Google Scholar
- J. of Paral. and Dist. Computing 37, 70 (1996). Crossref, Web of Science, Google Scholar