A new delay-insensitive data encoding scheme for global communication, level-encoded transition signaling (LETS), is introduced. LETS is a generalization of level-encoded dual rail (LEDR), an earlier non-return-to-zero encoding scheme where one of two wires changes value per data bit per transaction. In LETS, only one of $N=2^n$ (1-of-$N$) wire changes value per n data bits per transaction. Compared to most common return-to-zero encoding schemes, LETS has potential power and throughput advantages, since fewer rails switch and no return-to-zero phase is required. Compared to existing non-return-to-zero schemes (i.e., LEDR), higher-dimension LETS codes have a potential power advantage, with significantly reduced switching activity per data bit. Two alternative 1-of-4 LETS codes are proposed, and efficient hardware for completion detection and conversion to return-to-zero protocols is introduced. Finally, a general theoretical framework is presented which characterizes the properties of arbitrary 1-of-$N$ LETS codes, as well as a simple procedure to generate such codes.

« hide abstract

The time separation of events (TSE) problem is that of finding the maximum and minimum separation between the times of occurrence of two events in a concurrent system. It has applications in the performance analysis, optimization and verification of concurrent digital systems. This paper introduces an efficient polynomial-time algorithm to give exact bounds on TSE's for choice-free concurrent systems, whose operational semantics obey the max-causality rule. A choice-free concurrent system is modeled as a strongly-connected marked graph, where delays on operations are modeled as bounded intervals with unspecified distributions. While previous approaches handle acyclic systems only, or else require graph unfolding until a steady-state behavior is reached, the proposed approach directly identifies and evaluates the asymptotic steady-state behavior of a cyclic system via a graph-theoretical approach. As a result, the method has significantly lower computational complexity than previously-proposed solutions. A prototype CAD tool has been developed to demonstrate the feasibility and efficacy of our method. A set of experiments have been performed on the tool as well as two existing tools, with noticeable improvement on runtime and accuracy for several examples.

« hide abstract

This paper presents an efficient method for the performance analysis and optimization of asynchronous systems. An asynchronous system is modeled as a marked graph with probabilistic delay distributions. We show that these systems exhibit inherent periodic behaviors. Based on this property, we derive an algorithm to construct the state space of the system through composition and capture the time evolution of the states into a periodic Markov chain. The system is solved for important performance metrics such as the distribution of input arrival time at a component, which is useful for subsequent system optimization, as well as relative component utilization, system latency and throughput. We also present a tool to demonstrate the feasibility of this method. Initial experimental results are promising, showing over three orders of magnitude improvement in runtime and nearly two orders of magnitude decrease in the size of the state space over previously published results. While the focus of this paper is on asynchronous digital systems, our technique can be applied to other concurrent systems that exhibit global asynchronous behavior, such as GALS and embedded systems.

« hide abstract

This paper presents a unifying framework for the modeling of asynchronous pipeline circuits. A pipeline protocol is captured in a graph-based model which defines the partial ordering of both its control and data events. The relationship between an entire space of different protocols is then captured in a semi-lattice, which has well-defined top and bottom elements, corresponding to the most concurrent and least concurrent protocol variants, respectively. This framework also provides a set of correct-by-construction transformation rules which allows for the systematic exploration of the entire design space by their successive application. To the best of our knowledge, this is the first formal framework for asynchronous pipelines which can capture protocols from a variety of logic style families, including both dynamic and static. It is also the first to provide a formal foundation for the design-space exploration of asynchronous pipelines.

« hide abstract

This paper shows that self-timed meshes can achieve linear speed-up. The per-processor performance of a mesh is the average number of operations per processor per unit time. For synchronous processors, it has been shown that the per-processor performance of a mesh goes to zero as the size of the mesh goes to infinity. This paper shows that for self-timed meshes, the per-processor performance can be bounded below by a positive constant. Thus, self-timed meshes are asymptotically faster than synchronous ones. Furthermore, simulation and analytic results are used to show that analysis based solely on average case times can be optimistic and lead to poor design decisions.

« hide abstract