Sponsored By:
ASP-DAC 2006 Archives
3A-1
| Title | An Anytime Symmetry Detection Algorithm for ROBDDs |
| Author | *Neil Kettle, Andy King (University of Kent, Great Britain) |
| Abstract | Detecting symmetries is crucial to logic synthesis, technology mapping, detecting function equivalence under unknown input correspondence, and \ROBDD\/ minimization. State-of-the-art is represented by Mishchenko's algorithm. In this paper we present an efficient anytime algorithm for detecting symmetries in Boolean functions represented as \ROBDDs, that output pairs of symmetric variables until a prescribed time bound is exceeded. The algorithm is complete in that given sufficient time it is guaranteed to find all symmetric pairs. The complexity of this algorithm is in $O(n^4+n\card{G}+\card{G}^3)$ where $n$ is the number of variables and $\card{G}$ the number of nodes in the \ROBDD, and it is thus competitive with Mishchenko's $O(\card{G}^3)$ algorithm in the worst-case since $n\ll\card{G}$. However, our algorithm performs significantly better because the anytime approach only requires lightweight data structure support and it offers unique opportunities for optimization. |
| Slides (pdf file) | 3A-1 |
3A-2
| Title | High Level Equivalence Symmetric Input Identification |
| Author | *Ming-Hong Su, Chun-Yao Wang (Department of Computer Science, National Tsing Hua University, Taiwan) |
| Abstract | Abstract — Symmetric input identification is an important technique in logic synthesis. Previous approaches deal with this problem by building BDDs and developing algorithms to determine symmetric inputs. For the design whose corresponding BDDs cannot be built, BDD-based approaches cannot be applied on this problem. To avoid the limitations of BDD-based approaches, simulation-based methods have been proposed. It is applicable to designs described in arbitrary level, especially to high-level and black box designs. Previous simulation-based approaches focus on determining the inputs of nonequivalence symmetry. In this paper, we propose a simulation-based approach to identify equivalence symmetric inputs. The experimental results on a set of ISCAS-85 and MCNC benchmarks are also presented. |
| Slides (pdf file) | 3A-2 |
3A-3
| Title | Fast Multi-Domain Clock Skew Scheduling for Peak Current Reduction |
| Author | *Shih-Hsu Huang, Chia-Ming Chang, Yow-Tyng Nieh (Chung Yuan Christian University, Taiwan) |
| Abstract | Given several specific clocking domains, the peak current minimization problem can be formulated as a 0-1 integer linear program. However, if the number of binary variables is large, the run time is unacceptable. In this paper, we study the reduction of this high computational expense. Our approach includes the following two aspects. First, we derive the ASAP schedule and the ALAP schedule to prune the redundancies without sacrificing the exactness (optimality) of the solution. Second, we propose a zone-based scheduling algorithm to solve a large circuit heuristically. |
| Slides (pdf file) | 3A-3 |
3A-4
| Title | Low Area Pipelined Circuits by Multi-clock Cycle Paths and Clock Scheduling |
| Author | *Bakhtiar Affendi Rosdi, Atsushi Takahashi (Tokyo Institute of Technology, Japan) |
| Abstract | A new algorithm is proposed to reduce the number of intermediate registers of a pipelined circuit using a combination of multi-clock cycle paths and clock scheduling. The algorithm analyzes the pipelined circuit and determines the intermediate registers that can be removed. An efficient subsidiary algorithm is presented that computes the minimum feasible clock period of a circuit containing multi-clock cycle paths. Experiments with a pipelined adder and multiplier verify that the proposed algorithm can reduce the number of intermediate registers without degrading performance, even when delay variations exist. |
| Slides (pdf file) | 3A-4 |
3A-5
| Title | A Transduction-based Framework to Synthesize RSFQ Circuits |
| Author | *Shigeru Yamashita (Nara Institute of Science and Technology, Japan), Katsunori Tanaka (NEC Corporation, Media and Information Research Laboratories, Japan), Hideyuki Takada (Kyoto University, Japan), Koji Obata, Kazuyoshi Takagi (Nagoya University, Japan) |
| Abstract | In this paper, we propose a new framework to synthesize rapid single flux quantum (RSFQ) logic circuits. In our framework, we construct a virtual cell, which we call ``2-AND/XOR,'' from the RSFQ logic primitives. By using 2-AND/XOR cells, we can successfully adopt the conventional logic design techniques into our framework, and thus we can successfully generate RSFQ circuits in reasonable time even for large benchmark circuits that have not reported in the existing researches. |
| Slides (pdf file) | 3A-5 |