Parallel and Distributed Simulation Systems: 7 (Wiley Series on Parallel and Distributed Computing) - Hardcover

Fujimoto, Richard M.

Hardcover

ISBN 10: 0471183830 ISBN 13: 9780471183839

Publisher: Wiley-Interscience, 2000

Synopsis

A state-of-the-art guide for the implementation of distributed simulation technology.

The rapid expansion of the Internet and commodity parallel computers has made parallel and distributed simulation (PADS) a hot technology indeed. Applications abound not only in the analysis of complex systems such as transportation or the next-generation Internet, but also in computer-generated virtual worlds for military and professional training, interactive computer games, and the entertainment industry.

In this book, PADS expert Richard M. Fujimoto provides software developers with cutting-edge techniques for speeding up the execution of simulations across multiple processors and dealing with data distribution over wide area networks ,including the Internet. With an emphasis on parallel and distributed discrete event simulation technologies, Dr. Fujimoto compiles and consolidates research results in the field spanning the last twenty years, discussing the use of parallel and distributed computers in both the modeling and analysis of system behavior and the creation of distributed virtual environments.

While other books on PADS concentrate on applications, Parallel and Distributed Simulation Systems clearly shows how to implement the technology. It explains in detail the synchronization algorithms needed to properly realize the simulations, including an in-depth discussion of time warp and advanced optimistic techniques. Finally, the book is richly supplemented with references, tables and illustrations, and examples of contemporary systems such as the Department of Defense's High Level Architecture (HLA), which has become the standard architecture for defense programs in the United States.

About this title

About the Author

RICHARD M. FUJIMOTO, PhD, is Professor of Computer Science at the Georgia Institute of Technology. Widely recognized for his contributions to the development of PADS, Dr. Fujimoto led the working group responsible for defining time management services for the U.S. Department of Defense High Level Architecture (HLA) effort.

Excerpt. © Reprinted by permission. All rights reserved.

PARALLEL AND DISTRIBUTED SIMULATION SYSTEMS

By Richard M. Fujimoto

JOHN WILEY & SONS, INC.

Copyright © 2000 John Wiley & Sons, Inc.
All right reserved.
ISBN: 978-0-471-18383-9

Contents

Preface.................................................................................xvPART I INTRODUCTION1 Background and Applications...........................................................31.1 Why Parallel/Distributed Simulation?...............................................41.2 Analytic Simulations versus Virtual Environments...................................61.3 Historical Perspective.............................................................81.4 Applications.......................................................................111.5 Underlying Technologies............................................................161.6 Hardware Platforms.................................................................171.7 Summary............................................................................231.8 Additional Readings................................................................242 Discrete Event Simulation Fundamentals................................................272.1 Time...............................................................................272.2 Real-Time, Scaled Real-Time, and As-Fast-As-Possible Execution.....................282.3 State Changes and Time Flow Mechanisms.............................................302.4 Discrete-Event Simulation Programs.................................................342.5 An Example Application.............................................................362.6 Starting and Stopping the Simulation...............................................392.7 Parallel/Distributed Simulation Example............................................392.8 World Views and Object-Oriented Simulation.........................................412.9 Other Approaches to Exploiting Concurrent Execution................................482.10 Additional Readings................................................................48PART II PARALLEL AND DISTRIBUTED DISCRETE-EVENT SIMULATION3 Conservative Synchronization Algorithms...............................................513.1 Synchronization Problem............................................................523.2 Deadlock Avoidance Using Null Messages.............................................543.3 Lookahead and the Simulation Model.................................................583.4 Deadlock Detection and Recovery....................................................603.5 Synchronous Execution..............................................................653.6 Bounded Lag........................................................................793.7 Conditional versus Unconditional Information.......................................813.8 Dynamic Processes and Interconnections.............................................823.9 Repeatability and Simultaneous Events..............................................843.10 Performance of Conservative Mechanisms.............................................873.11 Summary and Critique of Conservative Mechanisms....................................913.12 Additional Readings................................................................944 Time Warp.............................................................................974.1 Preliminaries......................................................................984.2 Local Control Mechanism............................................................984.3 Global Control Mechanism...........................................................1084.4 Computing Global Virtual Time......................................................1124.5 Other Mechanisms...................................................................1224.6 Scheduling Logical Processes.......................................................1334.7 Summary............................................................................1354.8 Additional Readings................................................................1355 Advanced Optimistic Techniques........................................................1375.1 Memory Utilization in Time Warp....................................................1385.2 Performance Hazards in Time Warp...................................................1515.3 Other Optimistic Synchronization Algorithms........................................1545.4 Putting It All Together: Georgia Tech Time Warp (GTW)..............................1615.5 Summary............................................................................1715.6 Comparing Optimistic and Conservative Synchronization..............................1725.7 Additional Readings................................................................1746 Time Parallel Simulation..............................................................1776.1 Time Parallel Cache Simulation Using Fix-up Computations...........................1796.2 Simulation of an ATM Multiplexer Using Regeneration Points.........................1836.3 Simulation of Queues Using Parallel Prefix.........................................1886.4 Summary............................................................................1906.5 Additional Readings................................................................191PART III DISTRIBUTED VIRTUAL ENVIRONMENTS (DVEs)7 DVEs: Introduction....................................................................1957.1 Goals..............................................................................1957.2 Contrasting DVE and PDES Systems...................................................1967.3 Server versus Serverless Architectures.............................................1977.4 Distributed Interactive Simulation.................................................1997.5 Dead Reckoning.....................................................................2047.6 High Level Architecture............................................................2097.7 Summary............................................................................2207.8 Additional Readings................................................................2218 Networking and Data Distribution......................................................2238.1 Message-Passing Services...........................................................2238.2 Networking Requirements............................................................2268.3 Networking Technologies............................................................2278.4 Communication Protocols............................................................2348.5 Group Communication................................................................2438.6 Data Distribution..................................................................2458.7 Summary............................................................................2568.8 Additional Readings................................................................2579 Time Management and Event Ordering....................................................2599.1 The Problem........................................................................2599.2 Message-Ordering Services..........................................................2619.3 Synchronizing Wallclock Time.......................................................2699.4 Summary............................................................................2759.5 Additional Readings................................................................275References..............................................................................277Index...................................................................................293

Preface

These are exciting times in the parallel and distributed simulation field. After many years of research and development in university and industrial laboratories, the field has exploded in the last decade and is now seeing use in many real-world systems and applications. My goal in writing Parallel and Distributed Simulation Systems is to give an in-depth treatment of technical issues concerning the execution of discrete event simulation programs on computing platforms composed of many processors interconnected through a network. The platform may range from tightly coupled multiprocessor computer systems confined to a single cabinet or room to geographically distributed personal computers or specialized simulators (for example, video game systems) spread across the world. This technology can be used to speed up the execution of large-scale simulations, for example simulations of the next generation of the Internet, or to create distributed synthetic environments for training or entertainment.

My goal in writing this book was to bring together into one volume the fundamental principles concerning parallel and distributed simulation systems that today are scattered across numerous journals and conference proceedings. The intended audience includes managers and practitioners involved in research and/or development of distributed simulation systems. The book can serve as a textbook for an advanced undergraduate or a graduate level computer science course. The book might be of interest in other disciplines (for example, industrial engineering or operations research) although the principal emphasis is on issues concerning parallel and distributed computation. Prior knowledge of discrete event simulation parallel, or distributed computation would be helpful, but is not essential as the book will include brief introductions to these fields.

Contents

The book is divided into three parts. The first provides an introduction to the field. Chapter 1 describes typical applications where this technology can be applied, and gives an historical perspective to characterize the communities that developed and refined this technology. Background information concerning parallel and distributed computing systems is reviewed. Chapter 2 reviews fundamental concepts in discrete event simulation to provide a common basis and terminology that is used in the remainder of the book.

The second part is primarily concerned with parallel and distributed execution of simulations, primarily for analysis applications such as to design large, complex systems. Here the goal is to use multiple processors to speed up the execution. Much of the material in these four chapters is concerned with synchronization algorithms that are used to ensure a parallel execution of the simulation yields the same results as a sequential execution, but (hopefully!) much more quickly. Two principal approaches to addressing this issue are called conservative and optimistic synchronization. Chapter 3 is concerned with the former, and Chapters 4 and 5 with the latter. Chapter 6 is concerned with an altogether different approach to parallel execution called time parallel simulation that is only suitable for certain classes of simulation problems, but can yield dramatic performance improvements when it can be applied.

The third part is concerned with distributed virtual environments (DVEs). Here the emphasis is on real-time simulations, that is, to create virtual environments into which humans may be embedded, for example, for training or entertainment. Chapter 7 gives an introduction to this area, focusing primarily on two efforts within the defense community, namely Distributed Interactive Simulation (DIS) and the High Level Architecture (HLA) where much of this technology was developed and has been applied. Chapters 8 and 9 are concerned with two specific issues in DVEs. Chapter 8 covers the problem of efficiently distributing data among the participants of the DVE. The first half of the chapter is an introduction to computer networks which provide the underlying communication support for DVEs. The second half is concerned with techniques to effectively utilize the networking infrastructure, particularly for large-scale simulations with many interacting components. Finally, Chapter 9 revisits the problem of time synchronization in DVEs as well as the problem of ensuring that the different computers participating in the simulation have properly synchronized clocks.

Part I lays the groundwork for the remainder of the book, so should be read first. Parts II and III can be read in either order. I have used this book as the text in a 10-week course in parallel and distributed simulation taught at Georgia Tech, and plan to use it when we transition to 15-week semesters. Alternatively, this book could be used for part of a course in discrete event simulation. When used in this manner, instructors may wish to skip Chapters 5 and 6, and the first half of Chapter 8 to obtain a more abbreviated treatment of the subject material.

Software

Interested readers may wish to try out some of the algorithms discussed in this book. Although software is not included with the text, it is available. In particular, the Georgia Tech Time Warp (GTW) software discussed in Chapter 5 and an implementation of a subset of the High level Architecture Run Time Infrastructure are freely available for education and research purposes. Information concerning this software is available at http:aawww.cc.gatech.edu/computing/pads. To obtain a copy of either or both of these software packages, you may contact me via electronic mail at fujimoto@cc.gatech.edu.

(Continues...)

Excerpted from PARALLEL AND DISTRIBUTED SIMULATION SYSTEMSby Richard M. Fujimoto Copyright © 2000 by John Wiley & Sons, Inc.. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Edition details

• Publisher: Wiley-Interscience
• Publication date: 2000
• Language: English
• ISBN 10: 0471183830
• ISBN 13: 9780471183839
• Binding: Hardcover
• Edition number: 1
• Number of pages: 320