
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

An Exact Approach for GPCBased Compressor Tree Synthesis
Taeko MATSUNAGA Shinji KIMURA Yusuke MATSUNAGA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E96A
No.12
pp.25532560 Publication Date: 2013/12/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E96.A.2553
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms) Category: Logic Synthesis, Test and Verification Keyword: compressor tree, generalized parallel counter, integer linear programming, arithmetic synthesis,
Full Text: PDF>>
Summary:
Multioperand adders that calculate the summation of more than two operands usually consist of compressor trees, which reduce the number of operands to two without any carry propagation, and carrypropagate adders for the two operands in the ASIC implementation. Compressor trees that consist of full adders and half adders cannot be implemented efficiently on LUTbased FPGAs, and carrychains or dedicated structures have been utilized to produce multioperand adders on FPGAs. Recent studies indicate that compressor trees can be implemented efficiently on LUTs using Generalized Parallel Counters (GPCs) as the building blocks of compressor trees. This paper addresses the problem of synthesizing compressor trees based on GPCs. Based on the observation that characteristics such as the area, power, and delay correlate roughly to the total number and the maximum level of GPCs, the target problem can be regarded as a minimization problem for the total number of GPCs and the maximum levels of the GPCs, for which an ILPbased approach is proposed. The key point of our formulation is not to model the problem based on the structures of compressor trees like the existing approach, but instead the compression process itself is used to reduce the number of variables and constraints in the ILP formulation. The experimental results demonstrate the advantage of our formulation in terms of the quality and runtime.

