Scheduling critical channels in conservative parallel discrete event simulation
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper introduces the Critical Channel Traversing (CCT) algorithm, a new scheduling algorithm for both sequential and parallel discrete event simulation. CCT is a general conservative algorithm that is aimed at the simulation of low-granularity network models on shared-memory multiprocessor computers. An implementation of the CCT algorithm within a kernel called TasKit has demonstrated excellent performance for large ATM network simulations when compared to previous sequential, optimistic and conservative kernels. TasKit has achieved two to three times speedup on a single processor with respect to a splay tree central-event-list based sequential kernel. On a 16 processor (R8000) Silicon Graphics PowerChallenge, TasKit has achieved an event-rate of 1.2 million events per second and a speedup of 26 relative to the sequential kernel for a large ATM network model. Performance is achieved through a multi-level scheduling scheme that supports the scheduling of large grains of computation even with low-granularity events. Performance is also enhanced by supporting good cache behavior and automatic load balancing. The paper describes the algorithm and its motivation, proves its correctness and briefly presents performance results for TasKit.Keywords
This publication has 9 references indexed in Scilit:
- GTW: a time warp system for shared memory multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Conservative Parallel Simulation of ATM NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- SimKit: a high performance logical process simulation class library in C++Published by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- A high fidelity ATM traffic and network simulatorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Buffer management in shared-memory time warp systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Parallel simulation todayAnnals of Operations Research, 1994
- Parallel discrete event simulationCommunications of the ACM, 1990
- Virtual timeACM Transactions on Programming Languages and Systems, 1985
- Distributed Simulation: A Case Study in Design and Verification of Distributed ProgramsIEEE Transactions on Software Engineering, 1979