System Design, Modeling, and Simulation using Ptolemy II

Book Description:

This book is a definitive introduction to models of computation for the design of complex, heterogeneous systems. It has a particular focus on cyber-physical systems, which integrate computing, networking, and physical dynamics. The book captures more than twenty years of experience in the Ptolemy Project at Uc Berkeley, which pioneered many design, modeling, and simulation techniques that are now in widespread use. All of the methods covered in the book are realized in the open source Ptolemy Ii modeling framework and are available for experimentation through links provided in the book. The book is suitable for engineers, scientists, researchers, and managers who wish to understand the rich possibilities offered by modern modeling techniques. The goal of the book is to equip the reader with a breadth of experience that will help in understanding the role that such techniques can play in design.

Content

Preface ix

How to Use This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii

Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv

I Getting Starting 1

1 Heterogeneous Modeling 2

1.1 Syntax, Semantics, and Pragmatics . . . . . . . . . . . . . . . . . . . . . 5

1.2 Domains and Models of Computation . . . . . . . . . . . . . . . . . . . 7

1.3 The Role of Models in Design . . . . . . . . . . . . . . . . . . . . . . . 8

1.4 Actor Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5 Model Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.6 Approaches to Heterogeneous Modeling . . . . . . . . . . . . . . . . . . 13

1.7 Models of Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.8 Overview of Domains and Directors . . . . . . . . . . . . . . . . . . . . 24

1.9 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

iii2 Building Graphical Models 38

2.1 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.2 Tokens and Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

2.3 Hierarchy and Composite Actors . . . . . . . . . . . . . . . . . . . . . . 59

2.4 Annotations and Parameterization . . . . . . . . . . . . . . . . . . . . . 65

2.5 Navigating Larger Models . . . . . . . . . . . . . . . . . . . . . . . . . 68

2.6 Classes and Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

2.7 Higher-Order Components . . . . . . . . . . . . . . . . . . . . . . . . . 79

2.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

II Models of Computation 91

3 Dataflow 92

3.1 Synchronous Dataflow . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

3.2 Dynamic Dataflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

4 Process Networks and Rendezvous 131

4.1 Kahn Process Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

4.2 Rendezvous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

5 Synchronous-Reactive Models 158

5.1 Fixed-Point Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

5.2 SR Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

5.3 Finding the Fixed-Point . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

5.4 The Logic of Fixed Points . . . . . . . . . . . . . . . . . . . . . . . . . 178

5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

iv Ptolemaeus, System DesignExercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

6 Finite State Machines 186

6.1 Creating FSMs in Ptolemy . . . . . . . . . . . . . . . . . . . . . . . . . 187

6.2 Structure and Execution of an FSM . . . . . . . . . . . . . . . . . . . . . 192

6.3 Hierarchical FSMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

6.4 Concurrent Composition of State Machines . . . . . . . . . . . . . . . . 223

6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

7 Discrete-Event Models 232

7.1 Model of Time in DE Domain . . . . . . . . . . . . . . . . . . . . . . . 235

7.2 Queueing Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

7.3 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

7.4 Zeno Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264

7.5 Using DE with other Models of Computation . . . . . . . . . . . . . . . 265

7.6 Wireless and Sensor Network Systems . . . . . . . . . . . . . . . . . . . 268

7.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

8 Modal Models 274

8.1 The Structure of Modal Models . . . . . . . . . . . . . . . . . . . . . . . 279

8.2 Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

8.3 Execution of Modal Models . . . . . . . . . . . . . . . . . . . . . . . . 292

8.4 Modal Models and Domains . . . . . . . . . . . . . . . . . . . . . . . . 294

8.5 Time in Modal Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

9 Continuous-Time Models 315

9.1 Ordinary Differential Equations . . . . . . . . . . . . . . . . . . . . . . 316

9.2 Mixed Discrete and Continuous Systems . . . . . . . . . . . . . . . . . . 330

Ptolemaeus, System Design v9.3 Hybrid Systems and Modal Models . . . . . . . . . . . . . . . . . . . . 346

9.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354

10 Modeling Timed Systems 355

10.1 Clocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

10.2 Clock Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . 361

10.3 Modeling Communication Delays . . . . . . . . . . . . . . . . . . . . . 365

10.4 Modeling Execution Time . . . . . . . . . . . . . . . . . . . . . . . . . 378

10.5 Ptides for Distributed Real-Time Systems . . . . . . . . . . . . . . . . . 380

10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

10.7 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

11 Ptera: An Event-Oriented Model of Computation 394

11.1 Syntax and Semantics of Flat Models . . . . . . . . . . . . . . . . . . . 395

11.2 Hierarchical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411

11.3 Heterogeneous Composition . . . . . . . . . . . . . . . . . . . . . . . . 413

11.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417

III Modeling Infrastructure 419

12 Software Architecture 420

12.1 Package Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421

12.2 The Structure of Models . . . . . . . . . . . . . . . . . . . . . . . . . . 423

12.3 Actor Semantics and the MoC . . . . . . . . . . . . . . . . . . . . . . . 427

12.4 Designing Actors in Java . . . . . . . . . . . . . . . . . . . . . . . . . . 437

12.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446

13 Expressions 448

13.1 Simple Arithmetic Expressions . . . . . . . . . . . . . . . . . . . . . . . 449

vi Ptolemaeus, System Design13.2 Uses of Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456

13.3 Composite Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 461

13.4 Operations on Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472

13.5 Nil Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487

13.6 Fixed Point Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487

13.7 Units . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489

13.8 Tables of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493

14 The Type System 506

14.1 Type Inference, Conversion, and Conflict . . . . . . . . . . . . . . . . . 508

14.2 Structured Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520

14.3 Type Constraints in Actor Definitions . . . . . . . . . . . . . . . . . . . 524

14.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531

15 Ontologies 533

15.1 Creating and Using Ontologies . . . . . . . . . . . . . . . . . . . . . . . 535

15.2 Finding and Minimizing Errors . . . . . . . . . . . . . . . . . . . . . . . 549

15.3 Creating a Unit System . . . . . . . . . . . . . . . . . . . . . . . . . . . 555

15.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560

16 Web Interfaces 563

16.1 Export to Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564

16.2 Web Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580

16.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598

17 Signal Display 600

17.1 Overview of Available Plotters . . . . . . . . . . . . . . . . . . . . . . . 600

17.2 Customizing a Plot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602

Bibliography 610

Ptolemaeus, System Design viiActor Index 632

Index 643