Timing Analysis and Design Optimization for GALS Systems on Time-predictable Multi-core Architectures

Abstract

Ubiquitous real-time embedded systems are defined as computer systems that constantly monitor, respond to, or control external environment. Both functional and temporal correctness should be guaranteed for such systems, especially safety-critical systems whose correct operations are vital to ensure the safety of the public and the environment. The synchronous approach supporting deterministic concurrency is widely adopted in the design and verification of real-time embedded applications. Due to the surge in the demand for tools that can be used to model, validate and synthesize asynchronous systems, a Model of Computation (MoC) named Globally Asynchronous Locally Synchronous (GALS) has been proposed, providing both asynchronous and synchronous concurrency while preserving the advantages of the synchronous approach. A system modelled using GALS MoC consists of a set of subsystems at the top level, called Clock-Domains (CDs), running asynchronously to each other. A CD comprises a set of reactions that are running concurrently and synchronously. Recently, the insatiable demand for performance due to the growing complexity and more stringent timing requirements of embedded applications make it inevitable to integrate more Processing Elements (PEs) in a single chip, forming multi-core architectures. Moreover, in order to meet the resource usage constraints, shared resources (such as shared memory and input/output) are typically found in multi-core architecture, which are accessed through a shared bus to which all the PEs are connected. Due to the lack of methodologies and tools for timing analysis and design optimization of GALS systems running on multi-core architectures, statically and accurately determining the timing characteristics of the systems still remains a challenge. In addition, the overhead of resolving contentions induced by accessing shared resources simultaneously cannot be underestimated because it may even offset the benefit brought by integrating multiple PEs. This thesis focuses on timing analysis and design optimization of GALS systems running on time-predictable multi-core architectures. Starting with a scalable Timing Analysis and Code Optimization (TACO) framework targeting a CD running on a tandem processor platform, a series of timing analysis and design optimization techniques are presented in this thesis. A methodology based on design space exploration is proposed for finding the schedule with Guaranteed Reaction Time (GRT) for a CD running on a customizable multi-core architecture. This methodology is further extended by incorporating a novel bus arbitration policy, named Application-Specific Time Division Multiple Access (ASTDMA), to improve the efficiency of bus bandwidth utilization and hence reduce the GRT for each CD in a GALS system. Finally, a methodology is presented for minimizing resource usage for a GALS system with asynchronous execution of CDs on a multi-core architecture with shared resources. Another novel bus arbitration policy, named weighted TDMA, is employed by this methodology in order to improve the efficiency of bus bandwidth utilization. Experimental results show that the proposed optimization techniques effectively improve the worst-case performance of the system while maintaining time-predictability. Due to the fact that the timing analysis is only achievable on a time-predictable execution platform, the details of the target hardware architectures are given for each technique presented in this thesis.