This book’s goal is to provide a frame of reference for the burgeoning field of highperformance embedded computing. Embedded computers have moved well beyond the early days of 8-bit microcontrollers. Today, embedded computers are organized into multiprocessors that run millions of lines of code. They do so in real time and at very low power levels. In order to properly design such systems, a large and growing body of research has developed to answer questions about the characteristics of embedded hardware and software. These are real systems-aircraft, cell phones, and digital television all rely on high-performance embedded systems. We understand quite a bit about how to design such systems, but we also have a great deal more to understand.

Real-time control was actually one of the first uses of computers – Chapter 1 mentions the MIT Whirlwind computer, developed in the 1950s for weapons control. But the microprocessor moved embedded computing to the front burner as an application area for computers. Although sophisticated embedded systems were in use by 1980, embedded computing as an academic field didn’t emerge until the 1990s. Even today, many traditional computer science and engineering disciplines study embedded computing topics without being fully aware of related work being done in other disciplines.

Embedded computers are very widely used, with billions sold each year. A huge number of practitioners design embedded systems – a half-million programmers design embedded software. Although embedded systems vary widely in their details, there are common principles that apply to the field of embedded computing. Some of those principles were discovered decades ago while others are just being developed today. The development of embedded computing as a research field has helped to move embedded system design from a craft to a discipline, a move that is entirely appropriate given the important (sometimes safety-critical) tasks entrusted to embedded computers.

One reasonable question to ask about this field is how it differs from traditional computer systems topics, such as client-server systems or scientific computing. Are we just applying the same principles to smaller systems or do we need to do something new? I believe that embedded computing, though it makes use of many techniques from computer science and engineering, poses some unique challenges. First, most if not all embedded systems must perform tasks in real time. This requires a major shift in thinking for both software and hardware designers. Second, embedded computing also puts a great deal of emphasis on power and energy consumption. While power is important in all aspects of computer systems, embedded applications tend to be closer to the edge of the energy-operation envelope than many generalpurpose systems. All this leads to embedded systems being more heavily engineered to meet a particular set of requirements than are general-purpose computers, which, after all, are designed for general use.

This book assumes that you, the reader, are familiar with the basics of embedded hardware and software, such as might be found in Computers as Components. This book builds on those foundations to study a range of advanced topics. In selecting topics to cover, I tried to identify topics and results that are unique to embedded computing. I did include some background material from other disciplines to help set the stage for a discussion of embedded systems problems.

Here is a brief tour through the book:

Chapter 1 provides some important background for the rest of the book. It tries to define the set of topics that are at the center of embedded computing. It looks at methodologies and design goals.We survey models of computation, which serve as a frame of reference for the characteristics of applications. It also surveys several important applications that rely on embedded computing in order to provide some terminology that can be used throughout the book.

Chapter 2 looks at processors. We consider several different styles of processors that are used in embedded systems. We consider techniques for tuning the performance of a processor, such as voltage scaling. We consider the role of the processor memory hierarchy in embedded CPUs. We look at techniques used to optimize embedded CPUs, such as code compression and bus encoding. We consider techniques for simulating processors.

Chapter 3 studies programs. The back end of the compilation process, which helps determine the quality of the code, is the first topic. We spend a great deal of time on memory system optimizations since memory behavior is a prime determinant of both performance and energy consumption. We consider performance analysis including both simulation and worst-case execution time analysis.We also consider how models of computing are reflected in programming models and languages.

Chapter 4 moves up to multiple-process systems. We study and compare scheduling algorithms, including the interaction between language design and scheduling mechanisms. We evaluate operating system architectures and the overhead incurred by the operating system. We also consider methods for verifying the behavior of multiple process systems.

Chapter 5 concentrates on multiprocessor architectures. We consider both tightly coupled multiprocessors and the physically distributed systems used in vehicles. We consider architectures and their components: processors, memory, and networks. We also look at methodologies for multiprocessor design.

Chapter 6 looks at software for multiprocessors. We consider scheduling algorithms for multiprocessors. We also study middleware architectures for dynamic resource allocation in multiprocessors.

Chapter 7 concentrates on hardware/software co-design. We study different models that have been used to characterize embedded applications and target architectures. We study a wide range of algorithms for co-synthesis and we compare the models and assumptions used by these algorithms.

Hopefully this book covers at least most of the topics of interest to a practitioner and student of advanced embedded computing systems. There were some topics for which I could find surprisingly little work in the literature, software testing for embedded systems being a prime example. I tried to find representative articles of the major approaches to each problem. I am sure that I have failed in many cases to adequately represent a particular problem, for which I apologize.

This book is about embedded computing; it touches upon but does not exhaustively cover several related fields:

Applications – Embedded systems are designed to support applications like multimedia, communications, etc. Chapter 1 introduces some basic concepts about a few applications and understanding something about the application domain is important. But an in-depth look at these fields is best left to others.

VLSI – Although systems-on-chips are an important medium for embedded systems, they are not the only medium. Automobiles, airplanes, and many other
important systems are controlled by distributed embedded networks.

Hybrid systems – The field of hybrid systems studies the interactions between continuous and discrete systems. This is an important and interesting area, and many embedded systems can make use of hybrid system techniques, but hybrid systems deserve their own book.

Software engineering – Software design is a rich field that provides critical foundations but leave many questions specific to embedded computing unanswered.

I would like to thank all the people who have helped me with this book: Robert P. Adler (Intel), Brian Butler (Qualcomm), Alain Darte (CNRS), Babak Falsafi (CMU), Ran Ginosar (Gen-Gurion University), John Glossner (Sandbridge), Graham Hellestrand (VaSTSystems), Paolo Ienne (EPFL), Masaharu Imai (Osaka University), Irwin Jacobs (Qualcomm), Axel Jantsch (KTH), Ahmed Jerraya (TIMA), Lizy Kurian John (UT Austin), Christoph Kirsch (University of Salzburg), Haris Lekatsas (NEC), Frank Mueller (NCSU), Pierre Paulin (ST Microelectronics), Laura Pozzi (University of Lugano), Chris Rowen (Tensukuca), Rob Rutenbar (CMU), Deepu Talla (TI), David Whalley (FSU), Jiang Xu (Sandbridge), and Shengqi Yang (Intel).

I greatly appreciate the support, guidance, and encouragement given by my editor Nat McFadden, as well as the reviewers he worked with. The review process has helped identify the proper role of this book and Nat provided a steady stream of insightful thoughts and comments. I’d also like to thank my long-standing editor at Morgan Kaufman, Denise Penrose, who shepherded this book from the beginning.

I’d also like to express my appreciation to digital libraries, particularly those of the IEEE and ACM. I am not sure that this book would have been possible without them. If I had to find all the papers that I studied in a bricks-and-mortar library, I would have rubbery legs from walking through the stacks, tired eyes, and thousands of paper cuts. With the help of digital libraries, I only have the tired eyes.

Preface to the Second Edition

In this second edition, I tried to take a fresh look at the field of embedded computing and the range of techniques we now can apply to the design of high-performance embedded systems. A stunning range of applications now use embedded multiprocessors and complex software stacks: smartphones, airplanes, cars, electric power equipment, and the list goes on. These complex applications require sophisticated hardware, software, and design methodologies.

I updated every chapter; some required more revision than others. I also added a new chapter on cyber-physical systems. CPS has emerged since the publication of the first edition as a synthesis of control theory and embedded computing. While CPS leverages many of the techniques described in the other chapters, a number of new results apply to the design of cyber-physical systems. I tried to both outline those results and to highlight their relationship to results described in the other chapters.

My editors, Todd Green and Nate McFadden, gave me invaluable support and advice. I would like to thank the anonymous reviewers for their thoughtful and helpful comments. Any faults in this book, conceptual, technical, or stylistic, are all mine.

Reprinted with permission from Morgan Kaufmann, an imprint of Elsevier.