TDD A Technology Dependent Decomposition Algorithm for LUT-Based FPGAs
- 格式：pdf
- 大小：457.50 KB
- 文档页数：4
TDD: A Technology Dependent Decomposition Algorithm for LUT-Based FPGAs
Amir H. Farrahi IBM T. J. Watson Research Center P.O. Box 218 Yorktown Heights, NY 10598
Majid S a r r a f i a d e h ECE D e p a r t m e n t
Northwestern University Evanston, IL 60208
Abstห้องสมุดไป่ตู้act
1*2
I
/
POS
A major drawback'of the previous algorithms that perform decomposition and covering f o r L UT-based FPGA technology mapping is the lack of a fast, and reasonably accurate eualuation scheme f o r the decomposition phase. I n this paper, we will show how a fast covering algorithm can be used as a n evaluation engine for the decomposition phase. We show that decomposztion has a significant Impact o n the quality of the final mapping result. More specifically, we show that starting f r o m the same circuit topology, a blind decomposition leads t o mapping results that u s e a n average of 70% t o 150% more L U T s compared t o the results obtained using a technology driv e n decomposition algorithm. A technology driven decomposition algorithm i s developed based o n the proposed idea. Experiments o n a number of MCNC benchmark circuits show a n average of 12% to 72% improvement o n the number of L U T s compared to the previously reported results.
b'
PIS
Figure 1: a) A combinational logic circuit, b) its Boolean network representation, and c) m a p p i n g it o n t o 5-LUTs
1
Introduction
An FPGA is an array of programmable logic blocks that can be interconnected in a fairly general way. In a Lookup-Table (LUT) based FPGA, the basic logic block is a K-input LUT (K-LUT) that can implement any Boolean function of up to K variables. The technology mapping problem for LUTbased FPGAs is t o generate a mapping of a set of Boolean functions onto K-LUTs. Usually, these Boolean functions are described in the form of a Boolean network G = (V,E ) , which is a Directed Acyclic Graph (DAG) with a Boolean function associated with each of its vertices. The process of mapping a Boolean network onto K-input LUT-based FPGAs has been traditionally divided into two phases: Decomposition: Decomposing the nodes in the input network that have more than L inputs into functionally equivalent subnetworks that consist only of nodes with smaller than or equal to L inputs. The resulting network is called an L-feasible or L-bounded network. If K is the minimum number of LUT inputs, then we must have L 5 K. Covering: Covering the resulting K-feasible network with LUTs such that the following feasibility conditions are satisfied: a ) Each primary output (PO) of the circuit is generated by the output of some LUT, b ) Each input of a LUT comes either from a primary input (PI), or from the output of another node that is assigned a LUT, and c ) The number of inputs to each LUT does not exceed K. 'The authors have been supported in part by the National SciFoundation under Grant MIP 9529389. 2This work was done when the first author was a PhD candidate at ECE Department, Northwestern University.
2
Previous Works: Draw backs
Their Merits and
A majority of the research in LUT-based F P G A technology
mapping has focused either only on the decomposition phase [15, 161, or only on the covering phase [3, 41. In some other research [9, 111, the decomposition and covering steps are studied, but in an isolated manner. T h a t is, first the input network goes through a decomposition phase. Then the decomposed network, which is K-feasible, goes through a covering phase. A major drawback of such an isolation between
ence
Generally there are one or more objectives that are to be considered in the mapping process t o achieve mappings with high quality. Examples of such objectives are LUT-minimization, [5, 4, 9, 101, depth minimization [2], and routability-driven technology mapping [13]. In this paper we focus on the LUTminimization problem. Our contribution in this paper is twofold: First, we will show that decomposition has a significant impact on the quality of the final mapping result. More specifically, we will show that starting from the same circuit topology, a blind decomposition leads t o mapping results of significantly inferior quality with 70% to 150% more LUTs, compared to the mapping results obtained from a more intelligent technology driven decomposition. Second, we will show that a fast covering algorithm can be utilized to guide the decomposition algorithm by providing a fast and reasonably accurate estimate on the minimum number of LUTs needed t o cover the result of the decomposition of an infeasible sub-circuit. An integrated technology driven decomposition and covering approach, called TDD is implemented using this approach. Experiments confirm substantial improvement on the number of LUTs compared t o the previous techniques.
Amir H. Farrahi IBM T. J. Watson Research Center P.O. Box 218 Yorktown Heights, NY 10598
Majid S a r r a f i a d e h ECE D e p a r t m e n t
Northwestern University Evanston, IL 60208
Abstห้องสมุดไป่ตู้act
1*2
I
/
POS
A major drawback'of the previous algorithms that perform decomposition and covering f o r L UT-based FPGA technology mapping is the lack of a fast, and reasonably accurate eualuation scheme f o r the decomposition phase. I n this paper, we will show how a fast covering algorithm can be used as a n evaluation engine for the decomposition phase. We show that decomposztion has a significant Impact o n the quality of the final mapping result. More specifically, we show that starting f r o m the same circuit topology, a blind decomposition leads t o mapping results that u s e a n average of 70% t o 150% more L U T s compared t o the results obtained using a technology driv e n decomposition algorithm. A technology driven decomposition algorithm i s developed based o n the proposed idea. Experiments o n a number of MCNC benchmark circuits show a n average of 12% to 72% improvement o n the number of L U T s compared to the previously reported results.
b'
PIS
Figure 1: a) A combinational logic circuit, b) its Boolean network representation, and c) m a p p i n g it o n t o 5-LUTs
1
Introduction
An FPGA is an array of programmable logic blocks that can be interconnected in a fairly general way. In a Lookup-Table (LUT) based FPGA, the basic logic block is a K-input LUT (K-LUT) that can implement any Boolean function of up to K variables. The technology mapping problem for LUTbased FPGAs is t o generate a mapping of a set of Boolean functions onto K-LUTs. Usually, these Boolean functions are described in the form of a Boolean network G = (V,E ) , which is a Directed Acyclic Graph (DAG) with a Boolean function associated with each of its vertices. The process of mapping a Boolean network onto K-input LUT-based FPGAs has been traditionally divided into two phases: Decomposition: Decomposing the nodes in the input network that have more than L inputs into functionally equivalent subnetworks that consist only of nodes with smaller than or equal to L inputs. The resulting network is called an L-feasible or L-bounded network. If K is the minimum number of LUT inputs, then we must have L 5 K. Covering: Covering the resulting K-feasible network with LUTs such that the following feasibility conditions are satisfied: a ) Each primary output (PO) of the circuit is generated by the output of some LUT, b ) Each input of a LUT comes either from a primary input (PI), or from the output of another node that is assigned a LUT, and c ) The number of inputs to each LUT does not exceed K. 'The authors have been supported in part by the National SciFoundation under Grant MIP 9529389. 2This work was done when the first author was a PhD candidate at ECE Department, Northwestern University.
2
Previous Works: Draw backs
Their Merits and
A majority of the research in LUT-based F P G A technology
mapping has focused either only on the decomposition phase [15, 161, or only on the covering phase [3, 41. In some other research [9, 111, the decomposition and covering steps are studied, but in an isolated manner. T h a t is, first the input network goes through a decomposition phase. Then the decomposed network, which is K-feasible, goes through a covering phase. A major drawback of such an isolation between
ence
Generally there are one or more objectives that are to be considered in the mapping process t o achieve mappings with high quality. Examples of such objectives are LUT-minimization, [5, 4, 9, 101, depth minimization [2], and routability-driven technology mapping [13]. In this paper we focus on the LUTminimization problem. Our contribution in this paper is twofold: First, we will show that decomposition has a significant impact on the quality of the final mapping result. More specifically, we will show that starting from the same circuit topology, a blind decomposition leads t o mapping results of significantly inferior quality with 70% to 150% more LUTs, compared to the mapping results obtained from a more intelligent technology driven decomposition. Second, we will show that a fast covering algorithm can be utilized to guide the decomposition algorithm by providing a fast and reasonably accurate estimate on the minimum number of LUTs needed t o cover the result of the decomposition of an infeasible sub-circuit. An integrated technology driven decomposition and covering approach, called TDD is implemented using this approach. Experiments confirm substantial improvement on the number of LUTs compared t o the previous techniques.
