In general, the space of transformations that can be applied to a given circuit is potentially infinite because an arbitrarily long sequence of transformations may be applicable. To compound the challenge, the value of the given cost function can change non-monotonically as successive transformations are applied (e.g., some transformations increase area, while others decrease area), thereby making it difficult to apply a typical branch-and-bound approach to prune the search space. Our method employs simple but effective heuristic search strategies (including greedy, lookahead, and breadth-first). A key contribution is to identify commutativity of certain transformations, thereby pruning the design space significantly. The approach was automated and applied to a number of examples. Various throughput targets were assumed: from 50% to 20x throughput improvement. In each example, the approach was successful in meeting the throughput target.

More specifically, this paper makes two contributions. First, we introduce a method that, given a throughput goal, identifies which parts of the pipelined system constrain its throughput. Each such bottleneck is categorized based on the type of structural transformation that could potentially alleviate it: increase degree of pipelining (stage splitting, stage duplication, and loop unrolling); decrease forward latency (stage merging and parallelization); and perform slack matching. The second contribution is a method that guides the user to systematically apply these modifications to alleviate the bottlenecks and reach a target throughput goal.

We have validated the bottleneck analysis method on several examples and were able to attain the desired throughput goal in each case through iterative application of our bottleneck alleviation method. Runtimes were negligible in all cases (less than 50 ms).

The design was fabricated in a 0.13μm CMOS process, using standard cells and with full testability support. Resulting chips were evaluated for performance and robustness, using a large set of test vectors for good fault coverage. Under nominal operating conditions (1.5V and 27°C), the fabricated parts were able to deliver up to 8 giga GCD algorithmic iterations per second (equivalent to 1 GHz clock speed). Moreover, they were functionally correct across a wide range of voltages (0.5V to 4V) and temperatures (-45°C to 150°C). This case study bolsters our confidence in the potential of aynchronous design techniques to help produce reliable ASICS that are fast, testable, and that operate under a wide range of conditions.

This paper presents a fast analytical method for estimating the throughput of pipelined asynchronous systems, and then applies that method to develop a fast solution to the problem of pipeline "slack matching." The approach targets systems with hierarchical topologies, which typically result when high-level (block structured) language specications are compiled into data-driven circuit implementations. A significant contribution is that our approach is the first to efficiently handle architectures with choice (i.e., the presence of conditional computation constructs such if-then-else and conditional loops).

The key behind the fast speed of our analysis method is exploiting information about the hierarchy of a given block-structured system, which yields a runtime that is linear in the number of pipeline stages. In contrast, existing approaches typically represent an entire system as a single Petri net or marked graph, and then apply Markov chain analysis or other state enumeration methods with costly runtimes. Building upon our analysis approach, we introduce a novel solution to the problem of slack matching, i.e., determining optimal insertion of FIFO stages into a pipelined design to improve performance. We present both an optimal solution using an MILP formulation, and a fast heuristic algorithm that yielded optimal results for all of our examples.

We present a technique for increasing the throughput of stream processing architectures by removing the bottlenecks caused by loop structures. We implement loops as self-timed pipelined rings that can operate on multiple data sets concurrently. Our contribution includes a transformation algorithm which takes as input a high-level program and gives as output the structure of an optimized pipeline ring. Our technique handles nested loops and is further enhanced by loop unrolling. Simulations run on benchmark examples show a 1.3 to 4.9x speedup without unrolling and a 2.6 to 9.7x speedup with twofold loop unrolling.

We propose a low-overhead method for delay fault testing in high-speed asynchronous pipelines. The key features of our work are: (i) testing strategies can be administered using low-speed testing equipment; (ii) testing is minimallyintrusive, i.e. very little testing hardware needs to be added; (iii) testing methods are extended to pipelines with forks and joins, which is an important first step to testing pipelines with arbitrary topologies; (iv) test pattern generation takes into account the likely event that one delay fault causes several bits of data to become corrupted; and (v) test generation can leverage existing stuck-at ATPG tools. In describing our testing strategy, we use examples of faults from three very different high-speed pipeline styles: MOUSETRAP, GasP, and high-capacity (HC) pipelines. In addition, we give an in-depth example—including test pattern generation—for both linear and non-linear MOUSETRAP pipelines.