Abstractions currently used in computing hide timing properties of software. As a consequence, computer scientists have developed techniques that deliver improved average-case performance and/or design convenience at the expense of timing predictability. For embedded software, which interacts closely with physical processes, timing is usually an essential property. Lack of timing in the core abstractions results in brittle and non-portable designs. Moreover, as embedded software becomes more networked, the prevailing empirical test-based approach to achieving real-time computing becomes inadequate.
This project reintroduces timing predictability as a first-class property of embedded processor architectures. It tackles the problem from the hardware design perspective, developing precision timed (PRET) machines as soft cores on FPGAs. It shows that software on PRET machines can be integrated with what would traditionally have been purely hardware designs. This project seeks to reinvigorate research in an area of computer science and computer architecure that have stagnated in research due to maturing industrial practice. This is expected to provide a starting point for a decades-long revolution that will once again make timing predictability an essential feature of processors. This project addresses the core abstractions of computing. Rather than attempting to correct the lack of timing in these abstractions with more layers of abstraction, this project has the goal of showing that embedded processors can deliver both predictable timing and high performance. It opens up the field to new computing abstractions that include timing as a first-class property.
All widely used software abstractions lack temporal semantics. The notion of correct execution of a program written in every widely-used programming language today does not depend on the temporal behavior of the program. But temporal behavior matters in almost all systems. Even in systems with no particular real-time requirements, timing of programs is relevant to the value delivered by programs, and in the case of concurrent programs, also affects the functionality. In systems with real-time requirements, including most cyber-physical systems, temporal behavior affects not just the value delivered by a system but also its correctness. For concurrent software, which includes almost all interesting applications, the inability to directly control timing of software makes systems much more fragile. In particular, the behavior of a deployed system may differ considerably from the behavior of the system when being tested. Programmers are forced to use indirect methods such as setting priorities or deadlines, using synchronization primitives such as monitors and semaphores, and (often) delving into operating-system and hardware details to control interrupts and multitasking behavior. Such techniques are notoriously difficult to get right. Formal verification can help, but for many applications, verifying the software is not enough. We have to verify the system, which includes physical components that are not realized in software. Those physical components have temporal semantics, and the temporal behavior of the software directly impacts the overall system behavior. We cannot formally verify temporal behavior of software, however, if time is not part of the semantics of programs. To solve these problems, time can and must become part of the semantics of programs for a large class of applications. This NSF project has demonstrated that this is both practical and useful. The project has developed and evaluated three generations of PRET machines, where the PRET acronym stands for PREcision Timed; Predictable, REpeatable Timing; Performance with REpeatable Timing; and the French word for ``ready.'' All interpretations are valid and informative. PRET machines revise the concept of an instruction set architecture (ISA) to introduce temporal semantics. Programs written for a particular PRET ISA must meet certain timing requirements to be correctly executed. Timing becomes a correctness criterion, rather than a performance metric. Outcomes: This project started Feb. 1, 2008, ran for three years, and then received a two-year extension, for a total of five years. Over that time, the participants included, besides the three co-PIs, three visiting faculty, 10 grad students, and two postdocs. In addition, the project collaborated with Columbia University, University of Aukland (New Zealand), INRIA (Grenoble), National Instruments, Brigham Young University, Arizona State University, and Thales. The publications resulting from the project are listed at http://chess.eecs.berkeley.edu/pret/ and include 16 conference papers, one PhD thesis, 6 technical reports, and many presentations, including some invited keynote presentations. This project has established that it is possible to gain precise control over the timing of the actions of software without sacrificing performance. We believe that this work will lead to a generation of processors capable of precise and repeatable real-time behavior. These will be used in conjunction with general-purpose processors to provide time-sensitive services (such as high-performance networking and real-time media processing), and as processors for safety-critical and certification-intensive applications, such as automotive systems and aircraft control systems. Intellectual Merit: This project has addressed the core abstractions of computing, which throughout the 20-th century, have deliberately abstracted away time. For embedded systems, this is inappropriate. Unlike most research in real-time systems, which attempts to correct this problem with ever more layers of abstraction, band-aid patches, and ad-hoc methods, this project has confronted the problem directly. It has demonstrated embedded processor architectures that deliver both predictable timing and high performance, and thus open up the field for a whole new set of computing abstractions that include timing as a first-class property. Broader Impacts: The economic potential of embedded systems today is limited by our inability to develop reliable, comprehensible, portable, networked, and cost-effective real-time software. Enormous cost overruns on defense programs that rely on such software are one indication. Slow product development, limited functionality, and poor networking of consumer products are another. The economic potential of improved methods, particularly ones where safety-critical, real-time embedded software can be networked, is enormous. The broader impacts of this project are simple: it has reinvigorated the field of embedded systems by showing that computation with predictable timing has vastly greater potential than naive applications of general-purpose processors. The potential economic impact is incalculable.
