Synthesis of Timed Circuits Based on Decomposition

This paper presents a decomposition-based method for timed circuit design that is capable of significantly reducing the cost of synthesis. In particular, this method synthesizes each output individually. It begins by contracting the timed signal transition graph (STG) to include only transitions on the output of interest and its possible trigger signals. Next, the reachable state space for this contracted STG is analyzed to determine a minimal number of additional signals, which must be reintroduced into the STG to obtain complete state coding. The circuit for this output is then synthesized from this STG. Results show that the quality of the circuit implementation is nearly as good as the one found from the full reachable state space, but it can be applied to find circuits for which full-state-space methods cannot be successfully applied. The proposed method has been implemented as a part of our tool Nii-Utah Timed Asynchronous circuit Synthesis system (nutas), and its first version is available at http://research.nii.ac.jp/_~yoneda.

I. Introduction

Logic synthesis [1]–[4] from low-level specification languages is one of the major approaches to the automated synthesis of asynchronous circuits. This approach can potentially synthesize more optimized circuits with higher performance than other methods such as syntax-directed-translation methods [5]–[10]. It, however, usually requires enumeration of the state space of the given specification, and it often suffers from the state-explosion problem. Thus, large specifications expressed in hardware-description languages have usually been synthesized by syntax-directed-translation methods or similar techniques that do not require state-space enumeration, sometimes with local-optimization techniques, such as in [11]. This paper tackles the challenge of using logic synthesis also for large specifications derived from hardware-description languages, as it has the potential of providing further global optimization through timed circuit synthesis [12]. In this approach, a specification written in some high-level language is first translated to a timed signal transition graph (STG), and then, logic synthesis is applied to this timed STG. This method uses a compiler that generates timed STGs with the complete-state-coding (CSC) property. Its preliminary tool is described in [13], and an improved version is described in [14] and [15]. Guaranteeing CSC by such a correct-by-construction method, which may not give optimal solutions in the number of inserted state variables, is practical for large STGs, because automatic CSC solvers sometimes do not handle such large STGs well. Furthermore, by using a special protocol shown in [15] and [16], the performance degradation caused by the inserted state variables can be reduced to an almost negligible amount. A key issue to the success of our approach is a new logic-synthesis technique that is efficient enough to handle large STGs. This paper aims at reducing the average cost for logic synthesis from timed STGs by decomposing (or projecting) a specification to many small subspecifications and running the logic-synthesis procedure for each of them.