Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Precision Timed Machines

Isaac Liu

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2012-113
May 14, 2012

http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-113.pdf

Cyber-Physical Systems (CPS) are integrations of computation with physical processes. These systems must be equipped to handle the inherent concurrency and inexorable passage of time of physical processes. Traditional computing abstractions only concern themselves with the functional aspects of a program, and not its timing properties. Thus, nearly every abstraction layer has failed to incorporate time into its semantics; the passage of time is merely a consequence of the implementation. When the temporal properties of the system must be guaranteed, designers must reach beneath the abstraction layers. This not only increases the design complexity and effort, but the systems are overdesigned, brittle and extremely sensitive to change. In this work, we address the difficulties of handling time in computing systems by re- examining the lower levels of abstraction. In particular, we focus on the instruction set architecture (ISA) layer and its affects on microarchitecture design. Modern ISAs do not constrain timing properties of instructions as part of the contract. Thus, architecture designs have largely implemented techniques that improve average performance at the expense of execution time variability. This leads to imprecise WCET bounds that limit the timing predictability and timing composability of architectures. In order to address the lack of temporal semantics in the ISA, we propose instruction extensions to the ISA that give temporal meaning to the program. The instruction extensions allow programs to specify execution time properties in software that must be observed for any correct execution of the program. This brings control over timing to the software and allows programs to contain timing properties that are independent of the underlying architecture. In addition, we present the Precision Timed ARM (PTARM) architecture, an architecture that provides timing predictability and composability without sacrificing performance. PTARM employs a predictable thread-interleaved pipeline with an exposed memory hierarchy that uses scratchpads and a predictable DRAM controller. This removes timing interference among the hardware threads, enabling timing composability in the architecture, and provides deterministic execution times for instructions within the architecture, enabling timing predictability in the architecture. We show that the predictable thread-interleaved pipeline and DRAM controller design also achieve better throughput compared to conventional architectures when fully utilized, accomplishing our goal to provide both predictability and performance. To show the applicability of the architecture, we present two applications implementedwith the PRET architecture that utilize the predictable execution time and the extended ISA to achieve their design requirements. The first application is a real-time fuel rail simulator that implements a one dimensional computational fluid dynamics (1D-CFD) solver on a multicore PRET architecture. This provides a scalable solution to close the loop of fuel delivery, allowing for more precise fuel injections that lead to a cleaner and more efficient engine. The second application presents a case study that uses PRET to remove the vulnerability of timing side-channel attacks on encryption algorithms. We implement the RSA and DSA encryption algorithms on PRET and show that by using the timing extended ISA and a predictable architecture, we can completely remove the vulnerabilities that are exploited for the attacks. By providing a predictable architecture, we provide simpler and more accurate timing analysis of the software. With the ISA extensions, we provide timing control and allow architecture independent timing properties to be specified in the software. Through these contributions, we aim to introduce a timing deterministic foundation to the lower levels of computing abstractions, which enables more precise and efficient control over timing for the design of CPS.

Advisor: Edward A. Lee


BibTeX citation:

@phdthesis{Liu:EECS-2012-113,
    Author = {Liu, Isaac},
    Title = {Precision Timed Machines},
    School = {EECS Department, University of California, Berkeley},
    Year = {2012},
    Month = {May},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-113.html},
    Number = {UCB/EECS-2012-113},
    Abstract = {Cyber-Physical Systems (CPS) are integrations of computation with physical processes. These systems must be equipped to handle the inherent concurrency and inexorable passage of time of physical processes. Traditional computing abstractions only concern themselves with the functional aspects of a program, and not its timing properties. Thus, nearly every abstraction layer has failed to incorporate time into its semantics; the passage of time is merely a consequence of the implementation. When the temporal properties of the system must be guaranteed, designers must reach beneath the abstraction layers. This not only increases the design complexity and effort, but the systems are overdesigned, brittle and extremely sensitive to change. In this work, we address the difficulties of handling time in computing systems by re- examining the lower levels of abstraction. In particular, we focus on the instruction set architecture (ISA) layer and its affects on microarchitecture design. Modern ISAs do not constrain timing properties of instructions as part of the contract. Thus, architecture designs have largely implemented techniques that improve average performance at the expense of execution time variability. This leads to imprecise WCET bounds that limit the timing predictability and timing composability of architectures. In order to address the lack of temporal semantics in the ISA, we propose instruction extensions to the ISA that give temporal meaning to the program. The instruction extensions allow programs to specify execution time properties in software that must be observed for any correct execution of the program. This brings control over timing to the software and allows programs to contain timing properties that are independent of the underlying architecture. In addition, we present the Precision Timed ARM (PTARM) architecture, an architecture that provides timing predictability and composability without sacrificing performance. PTARM employs a predictable thread-interleaved pipeline with an exposed memory hierarchy that uses scratchpads and a predictable DRAM controller. This removes timing interference among the hardware threads, enabling timing composability in the architecture, and provides deterministic execution times for instructions within the architecture, enabling timing predictability in the architecture. We show that the predictable thread-interleaved pipeline and DRAM controller design also achieve better throughput compared to conventional architectures when fully utilized, accomplishing our goal to provide both predictability and performance. To show the applicability of the architecture, we present two applications implementedwith the PRET architecture that utilize the predictable execution time and the extended ISA to achieve their design requirements. The first application is a real-time fuel rail simulator that implements a one dimensional computational fluid dynamics (1D-CFD) solver on a multicore PRET architecture. This provides a scalable solution to close the loop of fuel delivery, allowing for more precise fuel injections that lead to a cleaner and more efficient engine. The second application presents a case study that uses PRET to remove the vulnerability of timing side-channel attacks on encryption algorithms. We implement the RSA and DSA encryption algorithms on PRET and show that by using the timing extended ISA and a predictable architecture, we can completely remove the vulnerabilities that are exploited for the attacks. By providing a predictable architecture, we provide simpler and more accurate timing analysis of the software. With the ISA extensions, we provide timing control and allow architecture independent timing properties to be specified in the software. Through these contributions, we aim to introduce a timing deterministic foundation to the lower levels of computing abstractions, which enables more precise and efficient control over timing for the design of CPS.}
}

EndNote citation:

%0 Thesis
%A Liu, Isaac
%T Precision Timed Machines
%I EECS Department, University of California, Berkeley
%D 2012
%8 May 14
%@ UCB/EECS-2012-113
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-113.html
%F Liu:EECS-2012-113