This book is the result of a desire to systematically understand and present various models of computation developed during the 1980s and 1990s. These models have been elaborated, analyzed, and applied in the context of digital hardware and embedded software design. All of them have in common a strong emphasis on issues of time.
During the 1980s several new languages appeared that were based on the perfect synchrony assumption—that neither computation nor communication takes any noticeable time and that the timing of the system is solely determined by the arrival of input events. These so-called synchronous languages (Esterel, Signal, Argos, Lustre, StateCharts, etc.) were developed for either embedded software or digital hardware design. Since then a few of them, in particular Esterel, have enjoyed the continuous support of a growing user community.
The synchronous design style for hardware design, developed in the 1960s, has been extraordinarily successful and has dominated the development of digital hardware so completely that several generations of hardware designers have been educated under the implicit assumption that this is the only feasible way to design hardware.
Several dataflow models and languages were developed in the 1970s. With the definition of restricted models, such as synchronous dataflow, cyclo-static dataflow, and boolean dataflow, between 1985 and 1995 and their application to the design of signal processing systems, sophisticated tools with a large and growing user community evolved. Today dataflow models are firmly established in the designer communities of a number of application domains.
Discrete event models also have a long history. They have been used for modeling and simulation in a large variety of application areas. Discrete event models are a very general modeling technique: any kind of system can be modeled and simulated with any degree of accuracy. They are used to model objects as diverse as tiny semiconductor transistors and the communication patterns of the global Internet. Any entity of interest to scientists and engineers has been subject to simulation as a discrete event system. In hardware design a variant, the delta-delay-based discrete event model, has become popular with the advent of languages such as VHDL and Verilog.
The representation of time, at different abstraction and accuracy levels, plays a prominent role in all these models. The treatment of time might be considered to be among the most characteristic distinguishing features of these models. In fact a main conjecture of this book is that the same concepts and formalism can be used to model discrete event, synchronous, and dataflow models by simply varying the abstraction level for the representation of time. Thus, time, synchronization, and communication are central themes in this book. Further, the relationship between the communication part and the communication part of a process is important; the clean separation of the two parts is a guiding principle in developing the formalism used throughout this book.
As a result, this book presents one basic formalism to represent the seemingly very different computational models for discrete event, synchronous, and dataflow models. An advantage of this approach is that these models can be studied and compared within the same framework, thus making the essential differences and similarities apparent without allowing syntactical and superficial differences to obscure the deeper relationships.
In addition to the desire of a better understanding of the subject matter, the book is also the response to the demands of teaching a course. Draft versions of this book have been used since January 2001 in the course “System Modeling” for students of the System-on-Chip master’s program at the Royal Institute of Technology in Stockholm. It has been found pedagogically useful to introduce the students to the basics of system modeling, finite state machines, and Petri nets before the unifying formalism of the book is explained and applied to the main models of computation and concurrency. Moreover, some chapters not only reflect the inherent logic of the subject but also are partially there in their current form and presentation due to requirements of that particular curriculum, of which “System Modeling” is a part. Consequently, depending on the background and interest of the reader, the book can be read in different ways. Figure P-1 outlines four alternative paths through the book.
Reader A follows the book in both the selection of topics and the course of presentation.
Reader B is mostly interested in the new material not covered in other books. She is either already familiar with or else not very interested in the basic concepts of modeling, finite state machines, and Petri nets. As a matter of fact, a good understanding of the topics of Chapters 1 and 2 is not a prerequisite for the rest of the book. Petri nets are used again at the end of Chapter 3, in Sections 3.14 and 3.15, but you can safely skip these sections without jeopardizing your understanding of the rest of the book. Also, the Rugby model, introduced in chapter 1 is used as a notational roadmap during the rest of the books. Most chapters have a section at the end, named “Rugby Coordinates”, which locates the discussed model of computation within the Rugby model. Although these sections are intended to be an orientation aid for the reader, they are not required to understand the other sections. Thus, these sections can be skipped together with the discussion of the Rugby model in Section 1.5.
Reader C is, like Reader B, only interested in the new material but prefers to focus fully on the discussion of the models of computation (MoC) in the unifying framework. Perhaps he is short of time or is just not interested in more advanced topics like MoC integration or nondeterminism. Chapters 3, 4, and 5 are in a sense the core of the book, and focusing first on them to obtain an understanding of the main ideas and lines of thought is an easily justifiable approach.
Reader D is, like Reader C, only interested in the unifying presentation of the main models of computation but is not very fluent in finite state machines and Petri nets and thus reads Chapter 2 as a preparation.
Other alternative reading paths and path combinations are feasible. Chapters 6, 7, 8, and 9 are almost independent of one another and can be read in any order corresponding to the reader’s preferences, after Chapters 3 through 5 have been perused.
It is also possible to benefit from the book without penetrating all the formal details and peculiarities of the presented formalism.
Reader E is interested in an intuitive understanding of the book’s main concepts but not so much in their mathematical presentation. He may follow any of the reading paths outlined above but may even in the core Chapters 3 through 5 skip, or browse superficially, the following sections without losing the thread or jeopardizing the chance to intuitively grasp the main ideas of succeeding chapters: Sections 3.5 (theoretical properties of processes), 3.6 (process composition and feedback loops), 3.10.2–3.10.5 (up-rating of processes other than the simplest possible), 3.11 (process down-rating), 3.12.2 (process merging for complex cases), 3.15.2 (multiprocessor schedules), 4.3 (feedback loops in synchronous process networks), and 4.7 (extended characteristic functions in the clocked synchronous model). These sections are interesting and required for the formal development of the framework and its properties, but are not required for an intuitive understanding. Again, Chapters 6 through 9, which partially also involve a more formal treatment, may be selected or skipped individually.
As mentioned earlier, this book has been used as a textbook for “System Modeling” in the System-on-Chip master’s program at the Royal Institute of Technology in Stockholm. Thus, a full graduate course can be based solely on this book. It can also be used as complementary material for a course that attempts to give a comprehensive view of different important models of computation. For instance a graduate course in embedded system design could use Chapters 3 through 5 to introduce the untimed, synchronous, and timed models of computation.
Since the book gives a systematic and consistent account of a number of important computational models, it is suitable for graduate students, researchers, and teachers in the areas of design of electronic and embedded systems who are interested in the tasks of modeling, specification, and validation. With the development of a unifying framework, in which different computational models can be studied and compared, and with the presentation of new viewpoints on issues like oversynchronization, nondeterminism, and stochastic processes, we hope to provide a contribution that advances the understanding in this field.
To the practicing engineer the formal treatment may be an obstacle to the quick extraction of the main message. However, with the earlier suggestion of reading path E, we hope to ease the penetration of the subject even for those who are not enthusiastic about mathematical formalisms. Moreover, many small examples and interesting application cases are interwoven in the text, some of which may even be interesting for their own sake. For instance, at the end of the discussion of the untimed computational model we present scheduling techniques for synchronous dataflow models, and after the presentation of the synchronous models we acquaint the reader with validation techniques based on monitors. In Chapter 7 we give practical suggestions on how to realize determinate behavior in the presence of a nondeterministic underlying model, and in Chapter 8 we give an alternative to nondeterministic models based on stochastic processes.
Hence, we hope that students, teachers, researchers, and engineers will consider the theoretical foundation worthy of a careful study to gain new insights and a better understanding, and that they will find the illustrating examples and applications of immediate practical use.
Writing this book took four years. During this time many people have helped and contributed in different ways. It is in fact difficult to correctly trace back all ideas, contributions and influences and I am afraid I am not able to do justice to everybody because memories tend to change over time and distort the real cause of events. Anyway, I will try hard to properly and gratefully list all inputs since they together significantly shaped the final result and made it a much better book than I could have written otherwise.
At the Royal Institute of Technology in Stockholm I find the former Electronic Systems Design Lab (ESDlab) and now the Laboratory of Electronics and Computer Science (LECS) to be a very pleasant and inspiring research environment. I had the privilege to discuss with and benefit from many people there. Historically, my first attempt to find common, deep principles beneath a vast and confusing variety of languages, methods, tools and methodologies resulted in the formulation of the Rugby model. Numerous discussions with Shashi Kumar, now at Jönköping University, Sweden, and Ahmed Hemani, now at Acreo AB, Stockholm, Sweden, have been very exciting and considerably deepened my understanding in this subject. The work of the graduate students Andreas Johansson (now at Spirea AB, Stockholm), Ingo Sander and Per Bjuréus (now at Saab Aerospace, Stockholm) has been a rich source of inspiration and ideas and forced me more than once to reconsider basic assumptions and opinions. In particular, Ingo Sander’s work on ForSyDe has countless connections to many of the topics and concepts presented in this book. Thanks to Zhonghai Lu for his implementation case studies, to Wenbiao Wu, to Ashish Singh who helped me better understand some of the formal properties of the framework and to Tarvo Raudvere, who in countless hours developed examples and exercises for the associated course. Some of his exercises also made it into this book. The discussions with Luc Onana, Seif Haridi and Dilian Gurov helped me better understand some of the mysteries of fixed point theory. With many others at LECS I had many fruitful and exciting discussions with no direct connection to the subject of this book but which nonetheless have influenced it. Among those are Johnny Öberg, Peeter Ellervee, now at Tallinn Technical University, Mattias O’Nils, now at Mid Sweden University, Sundsvall, Sweden, Abhijit K. Deb, and Björn Lisper, now at Mälardalen University, Västerås, Sweden. Finally, I am very grateful to Hannu Tenhunen for creating a very inspiring environment and for his never-ending stream of ideas and suggestions on a variety of technical and non-technical issues.
Many thanks to the technical reviewers Edward A. Lee, University of California at Berkeley, California, Grant Martin, Cadence Laboratories, Berkeley, California, and Perry Alexander, University of Kansas, who read a draft of the manuscript and provided many valuable suggestions for improvement. Unfortunately I could not implement all their ideas and proposals. I particular I would like to thank also Grant Martin for reading so carefully the final manuscript and for spotting many small and some big technical mistakes, which would not have been detected otherwise.
A warm thank you goes to Alyson Day and Denise Penrose at Morgan Kaufmann Publishers for their strong support and encouragement throughout the publishing process, and to Richard Cook at Keyword Publishing Services, Essex, UK, for ironing out all the grammar, style and format errors that I managed to introduce. Needless to say, any technical and language errors that remain in the text despite their heroic effort are of my origin.
Although it has been observed many times, it is still true and urgent to state that the endeavor of writing such a book is only possible through the strong support and many sacrifices of one’s family. I apologize for spending so many hours with this book rather than with them and I am most grateful to Ewa, Simon and Philip for support and encouragement during the last four years.