This paper demonstrates the design of efficient asynchronous bundled-data pipelines for the matrix-vector multiplication core of discrete cosine transforms (DCTs). The architecture is optimized for both zero and small-valued data, typical in DCT applications, yielding both high average performance and low average power. The proposed bundled-data pipelines include novel data-dependent delay lines with integrated control circuitry to efficiently implement speculative completion sensing. The control circuits are based on a novel control-circuit template that simplifies the design of such nonlinear pipelines. Extensive post-layout back-end timing analysis was performed to gain confidence in the timing margins as well as to quantify performance and energy. Comparison with a synchronous counterpart suggests that our best asynchronous design yields 30% higher average throughput with negligible energy overhead.

This paper proposes an efficient asynchronous hardwired matrix-vector multiplier for the rwo-dimensional discrete cosine transform and inverse discrete cosine transform (DCT/IDCT). The design achieves low power and high performance by taking advantage of the typically large fraction of zero and small-valued data in DCT and IDCT applications. In particular, it skips multiplication by zero and dynamically activates/deactivates required bit-slices of fine-grain bit-partitioned adders using simplified, static-logic-based speculative completion sensing. The results extracted by both bit-level analysis and HSPICE simulations indicate significant improvements compared to traditional designs.

In many computer-aided design tools, binary decision diagrams (BDDs) are used to represent Boolean functions. To increase the efficiency and capability of these tools, many algorithms have been developed to reduce the size of the BDDs. This paper presents heuristic algorithms to minimize the size of the BDDs representing incompletely specified functions by intelligently assigning don't cares to binary values. Experimental results show that new algorithms yield significantly smaller BDDs compared with existing algorithms yet still require manageable run-times. These algorithms are particularly useful for synthesis application where the structure of the hardware/software is derived from the BDD representation of the function to implement because the minimization quality is more critical than the minimization speed in these applications.

Reachability analysis of finite state machines is essential to many computer-aided design applications. We present new techniques to improve both approximate and exact reachability analysis using don't cares. First, we propose an iterative approximate reachability analysis technique in which don't care sets derived from previous iterations are used in subsequent iterations for better approximation. Second, we propose new techniques to use the final approximation to enhance the capability and efficiency of exact reachability analysis. Experimental results show that the new techniques can improve reachability analysis significantly.

This paper explores the use of don’t cares in software synthesis for embedded systems. Embedded systems have extremely tight realtime and code/data size constraints, that make expensive optimizations desirable. We propose applying BDD minimization techniques in the presence of a don’t care set to synthesize code for extended Finite State Machines from a BDD-based representation of the FSM transition function. The don’t care set can be derived from local analysis (such as unused state codes or don’t care inputs) as well as from external information (such as impossible input patterns). We show experimental results, discuss their implications, the interaction between BDD-based minimization and dynamic variable reordering, and propose directions for future work. 1

In many computer-aided design tools, binary decision diagrams(BDDs) are used to represent Boolean functions. To increase theefficiency and capability of these tools, many algorithms have beendeveloped to reduce the size of BDDs. This paper presents heuristicalgorithms that minimize the size of BDDs representing incompletelyspecified functions by intelligently assigning don't cares tobinary values. The traditional algorithm, restrict [Verification of Synchronous Sequential Machines Based on Symbolic Execution], is often effectivein BDD minimization, but can increase the BDD size. We proposenew algorithms based on restrict which are guaranteed neverto increase the size of the BDD, thereby significantly reducing peakmemory requirements. Experimental results show that our techniquestypically yield significantly smaller BDDs than restrict.