pret

Precision Timed (PRET) Machines

We argue that at least for embedded software applications, computer architecture, software, and networking have gone too far down the path of emphasizing average case performance over timing predictability. In architecture, techniques such as multi-level caches and deep pipelines with dynamic dispatch and speculative execution make worst-case execution times (WCET) highly dependent on both implementation details of the processor and on the context in which the software is executed. Yet virtually all real-time programming methodologies depend on WCET. When timing properties are important in the software and when concurrent execution is affected by timing, the result is brittle design.

Our goal is to reintroduce timing predictability and repeatability by judiciously adopting architectural optimization techniques to deliver performance enhancements without sacrificing timing predictability and repeatability. Our approach includes extending the instruction-set architectures (ISA) with control over execution time. We believe that timing predictability and repeatability are not at odds with performance.

We have released a cycle-accurate model and simulator of a thread interleaved PRET architecture based on the SPARC ISA. The architecture has multiple software-managed on-chip memories, a memory wheel to arbitrate access to main memory, and extensions to the ISA with timing instructions. Programs are written in C and compiled using GCC’s SPARC compiler. We provide examples, including a video graphic driver example and RSA encryption/decryption algorithms to avoid timing-channel attacks. We plan to implement this as a soft core on FPGA. We will show that PRET architectures executing software components can be seamlessly integrated with what would traditionally have been purely hardware designs, thus greatly improving the expressiveness and usability of FPGA-based design flows. PRET provides a starting point for a revolution that will make timing predictability and repeatability central features of embedded processors.

The CHESS PRET team includes, from left to right:
Hiren Patel, Ben Lickly, Isaac Liu, Shanna-Shaye Forbes, Hugo Andrade (National Instruments), and Edward A. Lee (not in this picture)

Publications

1. Martin Schoeberl, Hiren D. Patel, Edward A. Lee. Fun with a Deadline Instruction, EECS Department, University of California, Berkeley, Technical Report No. UCB/EECS-2009-149, October 30, 2009.
2. Stephen A. Edwards, Sungjun Kim, Edward A. Lee, Isaac Liu, Hiren D. Patel, Martin Schoeberl. A Disruptive Computer Design Idea: Architectures with Repeatable Timing, Proceedings of International Conference on Computer Design (ICCD), IEEE, Lake Tahoe, CA, 4-7 October, 2009.
3. Stephen A. Edwards, Sungjun Kim, Edward A. Lee, Hiren D. Patel, Martin Schoeberl. Reconciling Repeatable Timing with Pipelining and Memory Hierarchy, Workshop on Reconciling Performance and Predictability, Grenoble, France, October 15, 2009.
4. Shanna-Shaye Forbes,Ben Lickly,Man-Kit Leung C Code Generation from the Giotto Model of Computation to the PRET Architecture, Technical Report No. UCB/EECS-2009-86, May, 2009
5. Devesh Dedhia, Example application under PRET environment -- Programming a MultiMediaCard, Computer Science Technical Report CUCS-005-09, Columbia University.
6. Isaac Liu and David McGrogan. Elimination of Side Channel Attacks on a Precision Timed Architecture, Technical Report No. UCB/EECS-2009-15, January 26, 2009
7. Nishant R. Shah, Memory issues in PRET machines, Computer Science Technical Report CUCS-059-08, Columbia University, December, 2008.
8. Hiren D. Patel, Ben Lickly, Bas Burgers and Edward A. Lee, A Timing Requirements-Aware Scratchpad Memory Allocation Scheme for a Precision Timed Architecture, Technical Report No. UCB/EECS-2008-115, September, 2008
9. Shanna-Shaye Forbes, Hugo A. Andrade, Hiren D. Patel and Edward A. Lee. An Automated Mapping of Timed Functional Specification to A Precision Timed Architecture, In proceedings of the 12-th IEEE International Symposium on Distributed Simulation and Real Time Applications (DSRT), October, 2008.
10. Ben Lickly, Isaac Liu, Sungjun Kim, Hiren D. Patel, Stephen A. Edwards and Edward A. Lee, Predictable Programming on a Precision Timed Architecture, in proceedings of International Conference on Compilers, Architecture, and Synthesis from Embedded Systems (CASES), October, 2008.
11. Ben Lickly, Isaac Liu, Sungjun Kim, Hiren D. Patel, Stephen A. Edwards and Edward A. Lee, Predictable Programming on a Precision Timed Architecture, Technical Report No. UCB/EECS-2008-40, April, 2008.
12. Stephen A. Edwards and Edward A. Lee, The case for Precision Timed (PRET) Machines, in proceedings of the 44th annual conference on Design Automation Conference, San Diego, California.
13. Stephen A. Edwards and Edward A. Lee. The Case for the Precision Timed (PRET) Machine, Technical report, University of California, Berkeley, UCB/EECS-2006-149, November, 2006.
14. Edward A. Lee, The Case for Precision Timed (PRET) Machines, National Workshop on High-Confidence Software Platforms for Cyber-Physical Systems (HCSP-CPS) Arlington, VA, November 30, 2006

Presentations

1. Hiren D. Patel, Predictable Programming on a Precision Timed Architecture, International Conference on Compilers, Architecture, and Synthesis from Embedded Systems (CASES), Atlanta, Georgia, October 21, 2008.
2. Hiren D. Patel, Predictable Programming on a Precision Timed Architecture, Virginia Tech., Blacksburg, Virginia, October 17, 2008.
3. Stephen Edwards, What We Do With 10^12 Transistors?, Google, Mountain View, California, February 20, 2008. [video]
4. Stephen Edwards, Precision Timed (PRET) Machines, Altera, San Jose, California, January 9, 2008.
5. Stephen Edwards, Precision Timed (PRET) Machines, National Taiwan University, Taipei, Taiwan, July 6, 2007.
6. Stephen Edwards, Precision-Timed (PRET) Machines at DAC is mentioned in the EETimes article, "Designers pitch 'wild and crazy' ideas at DAC.", June 6, 2007.
7. Stephen A. Edwards and Edward A. Lee. Precision-Timed (PRET) Machines, June, 2007; Presented at the 44th Design Automation Conference, San Diego, California.

Posters

1. Isaac Liu, Ben Lickly, Hiren D. Patel, Edward A. Lee, Poster Abstract: Timing Instructions - ISA Extensions for Timing Guarantees, a poster at Real-Time and Embedded Technology and Applications Symposium, San Francisco, California, 2009.
2. Ben Lickly and Hiren D. Patel, Timing-aware Exceptions for a Precision Timed (PRET) Target, Berkeley EECS Annual Research Symposium, February 12, 2009.
3. Hiren D. Patel, Isaac Liu, Ben Lickly, and Edward A. Lee, A Precision Timed Architecture for Predictable and Repeatable Timing, Berkeley EECS Annual Research Symposium, February 12, 2009.
4. Shanna-Shaye Forbes, Hiren D. Patel, Hugo A. Andrade, Ben Lickly, Isaac Liu. Mapping a Timed Functional Specification to a Precision Timed (PRET) Machine, Talk or presentation, 21, 2008.

Class Projects

1. Shanna-Shaye Forbes, Toward an Automated Mapping from A Timed Functional Specification to A Timed Architecture, EE 249: Design of Embedded Systems: Models, Validation and Synthesis, Fall 2007.
2. Isaac Liu and Joern Rheder, A Multithreaded Peripheral Processor for Real-Time Embedded Systems, EE 252: Graduate Computer Architecture, Fall 2007.
3. Isaac Liu and Ben Lickly, Micro-Architectural modeling of a SPARC Processor, EE 249: Design of Embedded Systems: Models, Validation and Synthesis, Fall 2007.

Miscellaneous

• C++ Coding guidelines
• Assigned Readings and Reviews

Wiki

• Internal Wiki accessible only by Chess participants and PRET members.

Resources

• Membership in pret is open to Chess participants (see Who can get an account?).
  Request an account in the pret workgroup
• pret private forum (Open only to pret workgroup members)

Mailing lists and discussion forums may be found under the pret link above.

To modify this page, use CVS

Acknowledgments