On the timing behavior of concurrent digital systems: Analysis, tools and applications.

摘要

This thesis studies the timing behavior of concurrent digital systems in which components communicate asynchronously---including fully-asynchronous systems, mixed-timing systems such as GALS (globally-asynchronous, locally-synchronous) systems, and fully-synchronous systems with asynchronous-style global communication, such as latency-insensitive systems---with the ultimate goal of developing efficient methods for ensuring their correctness and optimizing their performance.;Unlike clocked systems in which parts advance in lockstep under a central control, asynchronous concurrent systems can exhibit a much wider range of behavior, as parts evolve at their own speeds and communicate amongst themselves, as well as with the environment, in less predictable ways. Different possible interleavings of events result in a proliferation of system states. The overall behavior of these systems is often complex, and has thus far eluded a systematic understanding and the development of efficient analysis tools. This thesis contributes towards an advancement in bridging this gap through the uncovering of some underlying principles in the organization and dynamic behavior of these systems. In particular, it is shown how self-synchronization arises in a large class of these systems. Understanding the mechanism behind this phenomenon enables a systems-level view of concurrency and exposes the global properties which govern their behavior.;Based on this theoretical framework, a set of novel and efficient algorithms are developed for analyzing the timing behavior of a sub-class of concurrent systems, namely, those which synchronize under the AND-causality firing semantics, under two different and complementary delay models: fixed/bounded delays and stochastic delays. It is shown that the timing behavior of a fixed-delay system is driven by its critical cycles, and that it always settles into a steady state with a fixed or periodic pattern. The exact behavior of the system during its entire course of operation can be derived from an understanding of how the critical cycles interact with each other. Two solution approaches are proposed: a graph theoretical approach based on cycle analysis, and an algebraic approach based on normal mode decomposition. Based on this result, an efficient, exact solution to the TSE (time separation of events) problem is proposed for fixed- and bounded-delay systems, which has important applications in their timing verification and performance analysis. For stochastic-delay systems, an efficient solution to analyze their average-case performance based on Markovian analysis is proposed. The solution exploits the decomposability and periodicity of these systems to partially mitigate the state-space explosion problem from which previously-proposed solutions tend to suffer. Two tools, DES-TSE and DES-Perf, have been developed to implement the above techniques, combined and released as a publicly-released tool package, the DES (Discrete Event Systems) Analyzer.