Riedel, Marc D. and Bruck, Jehoshua (2003) Algorithmic Aspects of Cyclic Combinational Circuit Synthesis. California Institute of Technology . (Unpublished) https://resolver.caltech.edu/CaltechPARADISE:ETR053
![]()
|
PDF
See Usage Policy. 172kB | |
![]()
|
Postscript
See Usage Policy. 1MB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechPARADISE:ETR053
Abstract
Digital circuits are called combinational if they are memoryless: if they have outputs that depend only on the current values of the inputs. Combinational circuits are generally thought of as acyclic (i.e., feed-forward) structures. And yet, cyclic circuits can be combinational. Cycles sometimes occur in designs synthesized from high-level descriptions, as well as in bus-based designs [16]. Feedback in such cases is carefully contrived, typically occurring when functional units are connected in a cyclic topology. Although the premise of cycles in combinational circuits has been accepted, and analysis techniques have been proposed [7], no one has attempted the synthesis of circuits with feedback at the logic level. We have argued the case for a paradigm shift in combinational circuit design [10]. We should no longer think of combinational logic as acyclic in theory or in practice, since most combinational circuits are best designed with cycles. We have proposed a general methodology for the synthesis of multilevel networks with cyclic topologies and incorporated it in a general logic synthesis environment. In trials, benchmark circuits were optimized significantly, with improvements of up to 30%I n the area. In this paper, we discuss algorithmic aspects of cyclic circuit design. We formulate a symbolic framework for analysis based on a divide-and-conquer strategy. Unlike previous approaches, our method does not require ternary-valued simulation. Our analysis for combinationality is tightly coupled with the synthesis phase, in which we assemble a combinational network from smaller combinational components. We discuss the underpinnings of the heuristic search methods and present examples as well as synthesis results for benchmark circuits. In this paper, we discuss algorithmic aspects of cyclic circuit design. We formulate a symbolic framework for analysis based on a divide-and-conquer strategy. Unlike previous approaches, our method does not require ternary-valued simulation. Our analysis for combinationality is tightly coupled with the synthesis phase, in which we assemble a combinational network from smaller combinational components. We discuss the underpinnings of the heuristic search methods and present examples as well as synthesis results for benchmark circuits.
Item Type: | Report or Paper (Technical Report) | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
ORCID: |
| ||||||
Group: | Parallel and Distributed Systems Group | ||||||
Record Number: | CaltechPARADISE:ETR053 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechPARADISE:ETR053 | ||||||
Usage Policy: | You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format. | ||||||
ID Code: | 26083 | ||||||
Collection: | CaltechPARADISE | ||||||
Deposited By: | Imported from CaltechPARADISE | ||||||
Deposited On: | 09 Apr 2003 | ||||||
Last Modified: | 22 Nov 2019 09:58 |
Repository Staff Only: item control page