Concurrent and Comparative Discrete Event Simulation

Concurrent simulation is over twenty years old. During that pe­ riod it has been widely adopted for the simulation of faults in digital circuits, for which it provides a combination of extreme efficiency and generality . Yet, it is remarkable that no book published so far presents a correct and sufficiently detailed treatment of concurrent simulation. A first reason to welcome into print the effort of the authors is, therefore, that it provides a much needed account of an important topic in design automation. This book is, however, unique for sev­ eral other reasons. It is safe to state that no individual has contrib­ uted more than Ernst Ulrich to the development of digital logic simulation. For concurrent simulation, one may say that Ernst has contributed more than the rest of the world. We would find such a claim difficult to dispute. The unique experience of the authors con­ fers a special character to this book: It is authoritative, inspired, and focused on what is conceptually important. Another unique aspect of this book, perhaps the one that will be the most surprising for many readers, is that it is strongly projected towards the future. Concurrent simulation is presented as a general experimentation methodology and new intriguing applications are analyzed. The discussion of multi-domain concurrent simulation--­ recent work of Karen Panetta Lentz and Ernst Ulrich---is fascinat­ ing.

Table of Contents:
1 Introduction and Overview.- 1.1 Comparative Experimentation.- 1.2 The Evolution of Concurrent Simulation.- 1.3 Historical Facts, Major Features, and Major Advantages of CCS/MDCCS.- 1.4 Conceptual Overviews of CCS and MDCCS.- 1.5 Multi-List-Traversal.- 1.6 Orthogonal and Non-Orthogonal Domains.- 1.7 Statistical Simulation Control.- 1.8 Observation and the Use of Signatures.- 1.9 Selective-Trace/Event-Driven Simulation.- 1.10 Behavioral Modeling for CCS and MDCCS.- 1.11 Conclusion.- 1.12 References.- 2 New Applications.- 2.1 Introduction.- 2.2 The New Applications.- 2.3 References.- 3 History and Background: Digital Logic and Fault Simulation.- 3.1 Introduction.- 3.2 Logic Simulation in the 1950s and 1960s.- 3.3 Accuracy based on the X-State.- 3.4 Compiled Logic Simulation.- 3.5 Selective-Trace and Event-Driven Logic Simulation (Discrete Event Simulation).- 3.6 Event Scheduling and Execution.- 3.7 Simulation beyond the Gate-Level.- 3.8 Switch-Level Simulation.- 3.9 Min-Max Logic Simulation and Timing Verification.- 3.10 Hardware Simulation Engines.- 3.11 Terminology for Digital Logic Simulation.- 3.12 Modeling and Primitive Models.- 3.13 Table-Lookup.- 3.14 The Simulation of Memories.- 3.15 A Neglected Viewpoint — Instruction-Level Modeling and Simulation.- 3.16 High-Level Logic Simulation; Execution of Computer Programs.- 3.17 A Rehearsal Strategy.- 3.18 Faults for Fault and Design Simulation.- 3.19 Simultaneous Fault Simulation Methods.- 3.20 Miscellaneous Comments and Conclusions.- 3.21 References.- 4 Concurrent Fault Simulation.- 4.1 Introduction.- 4.2 Basic Concurrent Fault Simulation.- 4.3 Co-detection, Signatures, and Rehearsal Simulation.- 4.4 Types of Faults.- 4.5 Conclusion.- 4.6 References.- Chapters 5 Multi-List-Traversal.- 5.1 Introduction.- 5.2 MLTVariations.- 5.3 Axioms, Features, and Implementation Strategies.- 5.4 Specifics of Multi-List-Traversal.- 5.5 An MLT-Variation Based on Selective Traversal.- 5.6 Conclusion.- 5.7 References.- 6 Observation.- 6.1 Introduction.- 6.2 Advantages over Conventional, Serial Observation.- 6.3 Signatures, Distances, Sizes, Profiles, and Event Counts.- 6.4 A Per-Experiment Access Count.- 6.5 Conclusion.- 7 Multi-Domain Concurrent and Comparative Simulation.- 7.1 Introduction.- 7.2 MDCCS Basics.- 7.3 Efficiency Through Similarity.- 7.4 Storage Replication.- 7.5 Observation Precision with MDCCS.- 7.6 Further Efficiency Considerations.- 7.7 Multi-List Traversal.- 7.8 The MDCCS Multi-List Traversal.- 7.9 Conclusion.- 7.10 References.- 8 Fault Simulation of Diagnostic Programs.- 8.1 Introduction.- 8.2 An Overview of the Concurrent Simulation of Diagnostic Programs; Detection and Isolation.- 8.3 Memory Simulation; Accurate X-state Simulation for Memories.- 8.4 Observation and Statistics for Diagnostic Investigation.- 8.5 Conclusion: New Diagnostic Strategies.- 8.6 Reference.- 9 Concurrent Software Simulation (CSS).- 9.1 Introduction.- 9.2 An Example of CSS.- 9.3 CSS as a General Purpose Behavioral Modeling Method.- 9.4 Reference.- 10 Min-Max Simulation.- 10.1 Introduction.- 10.2 Terminology.- 10.3 Philosophies, Strategies, and Miscellaneous Facts.- 10.4 Ambiguity Propagation.- 10.5 The S-algorithm; Detecting False Glitches with the Help of S-Experiments.- 10.6 References.- 11 Concurrent Test Generation.- 11.1 Introduction.- 11.2 Fault Simulator Used as Test Evaluator.- 11.3 Fault Simulator Used as Test Generator.- 11.4 Contest Algorithm.- 11.5 Contest Test Generator.- 11.6 Complexity of Concurrent Test Generation.- 11.7 Conclusion.- 11.8 References.- 12 Simulation on Multiprocessors.- 12.1 Introduction.- 12.2 Parallel Processing.- 12.3 Data Parallel Simulation.- 12.4 CFS on MARS Multiprocessor.- 12.5 Conclusion.- 12.6 References.- 13 Conclusion and Future Work.- 13.1 References.