Session 2A: Advanced Topic in Logic Synthesis

2A-1 (Time: 13:30 - 13:55)

Title	Global Optimization of Common Subexpressions for Multiplierless Synthesis of Multiple Constant Multiplications
Author	Yuen-Hong Alvin Ho, Chi-Un Lei, *Hing-Kit Kwan, Ngai Wong (The Univ. of Hong Kong, Hong Kong)
Abstract	In the context of multiple constant multiplication (MCM) design, we propose a novel common subexpression elimination (CSE) algorithm that models the optimal synthesis of coefficients into a 0-1 mixed-integer linear programming (MILP) problem. A time delay constraint is included for synthesis. We also propose coefficient decompositions that combine all minimal signed digit (MSD) representations and the shifted sum (difference) of coefficients. In some cases, the proposed solution space further reduces the number of adders/subtractors in the MCM synthesis.
Slides

2A-2 (Time: 13:55 - 14:20)

Title	Decomposition Based Approach for Synthesis of Multi-Level Threshold Logic Circuits
Author	Tejaswi Gowda, *Sarma Vrudhula (Arizona State Univ., USA)
Abstract	Scaling is currently the most popular technique used to improve performance metrics of CMOS circuits. This cannot go on forever because the properties that are responsible for the functioning of MOSFETs no longer hold in nano dimensions. Recent research into nano devices has shown that nano devices can be an alternative to CMOS when scaling of CMOS becomes infeasible in the near future. This is motivating the need for stable and mature design automation techniques for threshold logic since it is the design abstraction used for most nano-devices. This paper presents a new decomposition theory that is based on the properties of threshold functions. The main contributions of this paper are: (1) A new method of algebraic factorization called the min-max factorization. (2) A decomposition theory that uses this new factorization to identify and characterize threshold functions. (3) A new threshold logic synthesis methodology that uses the decomposition theory. This synthesis methodology produces circuits that are better than the previous state of art (27% better gate count and comparable circuit depth).
No Slides

2A-3 (Time: 14:20 - 14:45)

Title	Timing-Power Optimization for Mixed-Radix Ling Adders by Integer Linear Programming
Author	*Yi Zhu, Jianhua Liu, Haikun Zhu, Chung-Kuan Cheng (Univ. of California, San Diego, USA)
Abstract	This paper optimizes timing and power consumption of mixed-radix Ling adders with the physical area constraints using an integer linear programming formulation. Each cell in the prefix network is flexible to have different radix and size, and Ling carries are incorporated. Optimal solutions are obtained by solving the proposed formulation. The experiments show that the produced optimal structures have a large power saving compared with traditional designs. The ASIC implementation results are superior to those produced by Synopsys Module Compiler.
Slides

2A-4 (Time: 14:45 - 15:10)

Title	Efficient Synthesis of Compressor Trees on FPGAs
Author	Hadi Parandeh-Afshar (Univ. of Tehran, Iran), *Philip Brisk, Paolo Ienne (EPFL, Switzerland)
Abstract	FPGA performance is currently lacking for arithmetic circuits. In many applications, such as digital signal and video processing, large sums of k > 2 integer values is the most computationally intensive part. To improve the quality of addition circuits on FPGAs, both Xilinx and Altera have augmented their basic LUT structure with dedicated circuitry for addition, including a fast carry-chain that does not suffer from routing delays. To sum k > 2 values, the most efficient method is to use a tree of binary or ternary adders. In the world of ASICs, it is well known that compressor trees outperform adder trees when summing k > 2 values; however, due to the peculiarities of FPGAs, all previous literature has reported that adder trees are faster than compressor trees. This paper shows that the conventional wisdom is actually false. A heuristic to synthesize a compressor tree onto an FPGA is presented that reduces the combinational delay through the tree by 27.5%, on average, with an area increase of approximately 5.7%.
Slides

2A-5 (Time: 15:10 - 15:23)

Title	Area Recovery under Depth Constraint by Cut Substitution for Technology Mapping for LUT-Based FPGAs
Author	*Taiga Takata, Yusuke Matsunaga (Kyushu Univ., Japan)
Abstract	This paper presents the post-processing algorithm, Cut Substitution, for technology mapping for LUT-based FPGAs to minimize the area under depth minimum constraint. The problem to minimize area under depth minimum costraint during technology mapping seems to be as difficult as NP-Hard class problem. Cut Substitution generates a local optimum solution by eliminating redundant LUTs while the depth is maintained. The experiments shows that the proposed method derives the solutions whose area are 9% smaller than those of DAOmap on average.
Slides

2A-6 (Time: 15:23 - 15:36)

Title	An Optimal Algorithm for Sizing Sequential Circuits for Industrial Library Based Designs
Author	Sanghamitra Roy, Yu Hen Hu (Univ. of Wisconsin, Madison, USA), *Charlie Chung-Ping Chen, Shih-Pin Hung, Tse-Yu Chiang, Jiuan-Guei Tseng (Nat'l Taiwan Univ., Taiwan)
Abstract	In this paper, we propose an optimal gate sizing and clock skew optimization algorithm for globally sizing synchronous sequential circuits. The number of constraints and variables in our formulation is linear with respect to the number of circuit components and hence our algorithm can efficiently find the optimal solution for industrial scale designs. To the best of our knowledge our method is the first exact gate sizing algorithm that can handle cyclic sequential circuits. Experimental results on industrial cell libraries demonstrate that our algorithm can yield an average of 12.6% improvement in the optimal clock period by combining clock skew optimization with gate sizing. For identical clock period, our algorithm can achieve an average of 11.3% area savings over a popular commercial synthesis tool.
Slides

Last Updated on: January 31, 2008