scheduling critical channels in conservative parallel discrete event simulation
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 multi-processor 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.
scheduling critic parallel discrete event simulation event simulation paper algorithm scheduling algorithm general network network model processor computation implementation kernel performance speedup tree graphics atm network modeling scheme cache behavior load balancing motivation correctness parallel simulation shared memory optimistic pdes chandy-misra-bryant algorithm conservative pdes relation time parallelism critical channel traversing algorithm