General Purpose Parallel Discrete Event Simulation Environment And The Study Of Relevant Techniques

Simulation as one of the three scientific research methods that facilitate the development of science and social progress has always been closely linked with the development of computing science and technology. Many of today's challenging research topics and applications, such as complex battlefield simulation, design and verification of large-scale telecommunication networks and VLSIs, air or road traffic control, and decision supporting systems, have demands on model fidelity, computation time, and computational resources far exceeding the capabilities of today's single CPU computers. Many of these problems can only be solved by utilizing parallel computers and Parallel Discrete Event Simulation (PDES) technology. Among the various research fields of PDES, the parallel simulation environment software plays a significant role. This dissertation evolves around key techniques essential to building a general-purpose, high-performance PDES environment. Through the case study of KD-PARSE (KD-PARallel Simulation Environment), a general-purpose high-performance PDES environment we developed, this dissertation illustrates a PDES system model that can capitalize on various hardware architectures, the design of time synchronization algorithms in PDES, event management techniques, event rollback algorithms, and model interoperability in PDES.The dissertation first analyzes various parallel hardware platforms and their respective computing models, and then categorizes PDES system models into four broad classes, namely synchronous, asynchronous, shared-memory and message-passing models. Based on this classification, this dissertation proposes an asynchronous PDES model based on MIMD parallel computers that uniformly uses message-passing paradigm. This PDES model is suitable for distributed, shared, or hybrid memory architectures. In this model events are scheduled by explicitly passing messages, and the lower communication layer takes responsibility for message routing and delivery. As a realization of this PDES model, this dissertation introduces PDES environment KD-PARSE, including its model representation, system architecture, especially how it achieves message passing and global synchronization in a communication environment that consists of distributed, shared, and hybrid memory architectures.Following this, this dissertation discusses time synchronization algorithms in PDES, categorizing the plethora of synchronization algorithms found in relevant literature into four basic types based on the values of key parameters in these algorithms, namely conservative, optimistic, fault-tolerant, and restricted optimistic. Then an algorithm that combines both aggressive and optimistic event processing, Breathing Time Warp, is introduced and discussed, along with PHOLD test results obtained on a cluster computing platform to prove its supremacy over pure conservative, optimistic or aggressive algorithms. Furthermore, this dissertation introduces a new synchronization algorithm called SafeBTW, that improves on BTW's weakness in statically designating the degree of optimism in event processing by distinguishing between "safe causal scheduling relation" and "unsafe causal scheduling relation", thus controlling the propagation of optimistic processing risks. PHOLD tests conducted on the same cluster platform prove that the new algorithm can effectively reduce overhead caused by secondary rollbacks, improve the overall computational efficiency, and achieve desirable scalability as the number of computing nodes increases.Then, based on the actual design in KD-PARSE, this dissertation discusses the event model and event list management in PDES that support optimistic event processing. The relationship between event and simulation object is first introduced, and the design of KD-PARSE's rollback algorithm and framework that utilizes Incremental State Saving algorithm, anti-message, and lazy rollback mechanisms are illustrated. Then the event list design and node-wide event management service of KD-PARSE are discussed, followed by its event state management. Event management overhead is also given through a performance benchmark test.At last, this dissertation introduces a model interoperability framework design in KD-PARSE based on its entity model and event processing mechanism. It consists of a data distribution framework and interaction management framework, allowing entities in a PDES to publish and subscribe to entity state information and interact with each other through means similar to those devised in HLA standard. It also provides a Data Distribution Management (DDM) service based on entity attribute values and subscription interest expressions. To improve performance in commonly found distributed memory environment such as cluster computers, the data distribution framework is optimized in KD-PARSE. The optimized design, compared with non-optimized design, can significantly improve DDM service performance and scalability in distributed memory environment.