Tom Dickman
ABSTRACT
Multi-core and many-core processing chips are becoming widespread and are now being widely integrated into Beowulf clusters. This poses a challenging problem for distributed simulation as it now becomes necessary to extend the algorithms to operate on a platform that includes both shared memory and distributed memory hardware. Furthermore, as the number of on-chip cores grows, the challenges for developing solutions without significant contention for shared data structures grows. This is especially true for the pending event list data structures where multiple execution threads attempt to schedule the next event for execution. This problem is especially aggravated in parallel simulation, where event executions are generally fine-grained leading quickly to non-trivial contention for the pending event list.
This manuscript explores the design of the software architecture and several data structures to manage the pending event sets for execution in a Time Warp synchronized parallel simulation engine. The experiments are especially targeting multi-core and many-core Beowulf clusters containing 8-core to 48-core processors. These studies include a two-level structure for holding the pending event sets using three different data structures, namely: splay trees, the STL multiset, and ladder queues. Performance comparisons of the three data structures using two architectures for the pending event sets are presented.
- H. Avril and C. Tropper. Clustered time warp and logic simulation. In Proceedings of the Ninth Workshop on Parallel and Distributed Simulation (PADS'95), pages 112--119, June 1995. Google Scholar
Digital Library
- P. D. R. Bayer. Symmetric binary b-trees: Data structure and maintenance algorithms. Acta Informatica, 1(4):290--306, Dec. 1972.Google ScholarDigital Library
- R. Brown. Calendar queues: A fast O(1) priority queue implementation for the simulation event set problem. Communications of the ACM, 31(10):1220--1227, Oct. 1988. Google ScholarDigital Library
- R. Child and P. A. Wilsey. Using DVFS to optimize time warp simulations. In Proceedings of the 2012 Winter Simulation Conference, July 2012. Google ScholarDigital Library
- R. Fujimoto. Parallel discrete event simulation. Communications of the ACM, 33(10):30--53, Oct. 1990. Google ScholarDigital Library
- A. Ghuloum. Face the inevitable, embrace parallelism. Communications of the ACM, 52(9):36--38, Sept. 2009. Google ScholarDigital Library
- M. Hansen, H. Yalcin, and J. P. Hayes. Unveiling the iscas-85 benchmarks: A case study in reverse engineering. IEEE Design and Test, 16(3):72--80, July-Sept 1999. (benchmarks available online at: http://web.eecs.umich.edu/~jhayes/iscas.restore/). Google ScholarDigital Library
- Intel Press Release, Intel Corporation. Futuristic intel chip could reshape how computers are built, consumers interact with their pcs and personal devices. Technical report, Intel Press Release, Intel Corporation, Dec. 2009.Google Scholar
- R. Kalla. Power7: Ibm's next generation power microprocessor. In Hot Chips 21, Aug. 2009.Google ScholarCross Ref
- D. E. Martin, T. J. McBrayer, and P. A. Wilsey. warped: A Time Warp simulation kernel for analysis and application development. In H. El-Rewini and B. D. Shriver, editors, 29th Hawaii International Conference on System Sciences (HICSS-29), volume Volume I, pages 383--386, Jan. 1996. Google ScholarDigital Library
- R. Miller. Optimistic parallel discrete event simulation on a beowulf cluster of multi-core machines. Master's thesis, University of Cincinnati, 2010.Google Scholar
- K. Muthalagu. Threaded warped: An optimistic parallel discrete event simulator for clusters fo multi-core machines. Master's thesis, School of Electronic and Computing Systems, University of Cincinnati, Cincinnati, OH, Nov. 2012.Google Scholar
- A. Palaniswamy and P. A. Wilsey. Parameterized Time Warp: An integrated adaptive solution to optimistic pdes. Journal of Parallel and Distributed Computing, 37(2):134--145, Sept. 1996. Google ScholarDigital Library
- S. K. Prasad, S. I. Sawant, and B. Naqib. Using parallel data structures in optimistic discrete event simulation of varying granularity on shared-memory computers. In IEEE First International Conference on Algorithms and Architectures for Parallel Processing, pages 365--374, Apr. 1995.Google ScholarCross Ref
- R. Radhakrishnan, L. Moore, and P. A. Wilsey. External adjustment of runtime parameters in Time Warp synchronized parallel simulators. In 11th International Parallel Processing Symposium, (IPPS'97). IEEE Computer Society Press, Apr. 1997. Google ScholarDigital Library
- R. Rajan and P. A. Wilsey. Dynamically switching between lazy and aggressive cancellation in a Time Warp parallel simulator. In Proc. of the 28th Annual Simulation Symposium, pages 22--30. IEEE Computer Society Press, Apr. 1995. Google ScholarDigital Library
- P. L. Reiher and D. Jefferson. Dynamic load management in the time warp operating system. Transactions of the Society for Computer Simulation, 7(2):91--120, 1990. Google ScholarDigital Library
- R. Ronngren, R. Ayani, R. M. Fujimoto, and S. R. Das. Efficient implementation of event sets in time warp. In Proceedings of the 1993 workshop on Parallel and distributed simulation, pages 101--108, May 1993. Google ScholarDigital Library
- R. Ronngren, J. Riboe, and R. Ayani. Lazy queue: An efficient implementation of the pending-event set. In Proc. of the 24th Annual Simulation Symposium, pages 194--204, Apr. 1991. Google ScholarDigital Library
- T. Santoro and F. Quaglia. A low-overhead constant-time ltf scheduler for optimistic simulation systems. In Proceedings of the The IEEE symposium on Computers and Communications, pages 948--953, June 2010. Google ScholarDigital Library
- D. Sleator and R. Tarjan. Self adjusting binary search trees. Journal of the ACM, 32(3):652--686, July 1985. Google ScholarDigital Library
- W. T. Tang, R. S. M. Goh, and I. L.-J. Thng. Ladder queue: An o(1) priority queue structure for large-scale discrete event simulation. ACM Transactions on Modeling and Computer Simulation, 15(3):175--204, July 2005. Google ScholarDigital Library
- R. E. Tarjan. Amortized computational complexity. SIAM J. Alg. Disc. Meth., 6(2):306--318, Apr. 1985.Google ScholarDigital Library
- R. Vitali, A. Pellegrini, and F. Quaglia. Towards symmetric multi-threaded optimistic simulation kernels. In Proceedings of the 2012 ACM/IEEE/SCS 26th Workshop on Principles of Advanced and Distributed Simulation, pages 211--220, July 2012. Google ScholarDigital Library
Index Terms
- Event pool structures for PDES on many-core Beowulf clusters
Recommendations
Lock-free pending event set management in time warp
SIGSIM PADS '14: Proceedings of the 2nd ACM SIGSIM Conference on Principles of Advanced Discrete SimulationThe rapid growth in the parallelism of multi-core processors has opened up new opportunities and challenges for parallel simulation discrete event simulation (PDES). PDES simulators attempt to find parallelism within the pending event set to achieve ...
Efficient simulation of agent-based models on multi-GPU and multi-core clusters
SIMUTools '10: Proceedings of the 3rd International ICST Conference on Simulation Tools and TechniquesAn effective latency-hiding mechanism is presented in the parallelization of agent-based model simulations (ABMS) with millions of agents. The mechanism is designed to accommodate the hierarchical organization as well as heterogeneity of current state-...
Multi- and many-core data mining with adaptive sparse grids
CF '11: Proceedings of the 8th ACM International Conference on Computing FrontiersGaining knowledge out of vast datasets is a main challenge in data-driven applications nowadays. Sparse grids provide a numerical method for both classification and regression in data mining which scales only linearly in the number of data points and is ...
Comments