Paper Info
Title
GVT algorithms and discrete event dynamics on 129K+ processor cores
Abstract
Parallel discrete event simulation (PDES) represents a class of codes that are challenging to scale to large number of processors due to tight global timestamp-ordering and fine-grained event execution. One of the critical factors in scaling PDES is the efficiency of the underlying global virtual time (GVT) algorithm needed for correctness of parallel execution and speed of progress. Although many GVT algorithms have been proposed previously, few have been proposed for scalable asynchronous execution and none customized to exploit one-sided communication. Moreover, the detailed performance effects of actual GVT algorithm implementations on large platforms are unknown. Here, three major GVT algorithms intended for scalable execution on high-performance systems are studied: (1) a synchronous GVT algorithm that affords ease of implementation, (2) an asynchronous GVT algorithm that is more complex to implement but can relieve blocking latencies, and (3) a variant of the asynchronous GVT algorithm, proposed and studied for the first time here, to exploit one-sided communication in extant supercomputing platforms. Performance results are presented of implementations of these algorithms on up to 129,024 cores of a Cray XT5 system, exercised on a range of parameters: optimistic and conservative synchronization, fine-to medium-grained event computation, synthetic and non-synthetic applications, and different lookahead values. Performance to the tune of tens of billions of events executed per second are registered, exceeding the speeds of any known PDES engine, and showing asynchronous GVT algorithms to outperform state-of-the-art synchronous GVT algorithms. Detailed PDES-specific runtime metrics are presented to further the understanding of tightly-coupled discrete event dynamics on massively parallel platforms.
Year
DOI
Venue
2011
10.1109/HiPC.2011.6152725
High Performance Computing
Keywords
Field
DocType
parallel discrete event simulation,state-of-the-art synchronous gvt algorithm,gvt algorithm,discrete event dynamic,processor core,fine-grained event execution,synchronous gvt algorithm,asynchronous gvt algorithm,actual gvt algorithm implementation,one-sided communication,fine-to medium-grained event computation,major gvt,computational modeling,heuristic algorithm,asynchrony,benchmark testing,computer model,engines,parallel programming,discrete event simulation,coprocessors
Asynchronous communication,Synchronization,Supercomputer,Massively parallel,Computer science,Parallel computing,Correctness,Algorithm,Cray XT5,Multi-core processor,Discrete event simulation,Distributed computing
Conference
ISBN
Citations 
PageRank 
978-1-4577-1949-3
6
0.50
References 
Authors
8
3
Name
Order
Citations
PageRank
Kalyan S. Perumalla172564.15
Alfred J. Park2354.53
Vinod Tipparaju363846.25