IEICE TRANSACTIONS on Fundamentals
An Exact Approach for GPC-Based Compressor Tree Synthesis
Summary :
Multi-operand 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 carry-propagate adders for the two operands in the ASIC implementation. Compressor trees that consist of full adders and half adders cannot be implemented efficiently on LUT-based FPGAs, and carry-chains or dedicated structures have been utilized to produce multi-operand 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 ILP-based 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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.12 pp.2553-2560
- Publication Date
- 2013/12/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E96.A.2553
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
- Logic Synthesis, Test and Verification
Authors
Taeko MATSUNAGA
Faculty of Engineering, Kyushu Sangyo University
Shinji KIMURA
Waseda University
Yusuke MATSUNAGA
Kyushu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Taeko MATSUNAGA, Shinji KIMURA, Yusuke MATSUNAGA, "An Exact Approach for GPC-Based Compressor Tree Synthesis" in IEICE TRANSACTIONS on Fundamentals,
vol. E96-A, no. 12, pp. 2553-2560, December 2013, doi: 10.1587/transfun.E96.A.2553.
Abstract: Multi-operand 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 carry-propagate adders for the two operands in the ASIC implementation. Compressor trees that consist of full adders and half adders cannot be implemented efficiently on LUT-based FPGAs, and carry-chains or dedicated structures have been utilized to produce multi-operand 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 ILP-based 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.2553/_p
Copy
@ARTICLE{e96-a_12_2553,
author={Taeko MATSUNAGA, Shinji KIMURA, Yusuke MATSUNAGA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Exact Approach for GPC-Based Compressor Tree Synthesis},
year={2013},
volume={E96-A},
number={12},
pages={2553-2560},
abstract={Multi-operand 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 carry-propagate adders for the two operands in the ASIC implementation. Compressor trees that consist of full adders and half adders cannot be implemented efficiently on LUT-based FPGAs, and carry-chains or dedicated structures have been utilized to produce multi-operand 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 ILP-based 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.},
keywords={},
doi={10.1587/transfun.E96.A.2553},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - An Exact Approach for GPC-Based Compressor Tree Synthesis
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2553
EP - 2560
AU - Taeko MATSUNAGA
AU - Shinji KIMURA
AU - Yusuke MATSUNAGA
PY - 2013
DO - 10.1587/transfun.E96.A.2553
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2013
AB - Multi-operand 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 carry-propagate adders for the two operands in the ASIC implementation. Compressor trees that consist of full adders and half adders cannot be implemented efficiently on LUT-based FPGAs, and carry-chains or dedicated structures have been utilized to produce multi-operand 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 ILP-based 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.
ER -
English
