The 11th Asia and South Pacific Design Automation Conference Technical Program

The 11th Asia and South Pacific Design Automation Conference

Wednesday January 25, 2006

Session 3A Logic Synthesis (16:00 - 18:05)
Location: Room 411+412
Chair(s): Shinji Kimura (Waseda University, Japan), Shih-Chieh Chang (National Tsing Hua University, Taiwan)

3A-1 (Time: 16:00 - 16:25)

Title	An Anytime Symmetry Detection Algorithm for ROBDDs
Author	*Neil Kettle, Andy King (University of Kent, Great Britain)
Page	pp. 243 - 248
Keyword	ROBDD, Symmetry
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.
PDF file

3A-2 (Time: 16:25 - 16:50)

Title	High Level Equivalence Symmetric Input Identification
Author	*Ming-Hong Su, Chun-Yao Wang (Department of Computer Science, National Tsing Hua University, Taiwan)
Page	pp. 249 - 253
Keyword	Symmetry, Simulation, BDD, Logic Synthesis
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.
PDF file

3A-3 (Time: 16:50 - 17:15)

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)
Page	pp. 254 - 259
Keyword	Clock Skew Optimization, Clock Skew Scheduling, Integer Linear Programming, High Performance, Low Power
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.
PDF file

3A-4 (Time: 17:15 - 17:40)

Title	Low Area Pipelined Circuits by Multi-clock Cycle Paths and Clock Scheduling
Author	*Bakhtiar Affendi Rosdi, Atsushi Takahashi (Tokyo Institute of Technology, Japan)
Page	pp. 260 - 265
Keyword	multi-clock cycle, clock scheduling, pipelined circuits
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.
PDF file

3A-5 (Time: 17:40 - 18:05)

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)
Page	pp. 266 - 272
Keyword	RSFQ, logic design, Transduction Method
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.
PDF file