SYSTEMS, NO. I, JANUARY 1994 1 FlowMap: An Optimal .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,VOL. 13, NO. I , JANUARY 19941FlowMap: An Optimal TechnologyMapping Algorithm for Delay Optimizationin Lookup-Table Based FPGA DesignsJason Cong, Member, IEEE, and Yuzheng Dingseveral synthesis techniques [20], [22], Chortle and Chortlecrf by Francis et al. based on tree decomposition and binpacking techniques [l 13, [14], Xmap by Karplus based onthe if-then-else DAG representation [17], the algorithm byWoo based on the notion of edge visibility [27], and thework by Sawkar and Thomas based on the clique partitioningapproach [24]. The algorithms in the second class emphasizeon minimizing the delay of the mapping solutions. This classincludes MIS-pga-delay by Murgai et al. which combinesthe technology mapping with layout synthesis [21], Chortled by Francis et al. which minimizes the depth increase ateach bin packing step [12], and DAG-Map by Cong et al.[3], [7] based on Lawler’s labeling algorithm. The mappingalgorithms in the third class, including that proposed by Bhatand Hill [l], and that by Schlag, Kong, and Chan [26], havethe objective of maximizing the routability of the mappingsolutions. Although many existing mapping methods showedencouraging results, these methods are heuristic in nature, andit is difficult to determine how far the mapping solutionsof these algorithms are away from the optimal solution.’ ItI. INTRODUCTIONhas been of both theoretical and practical interest to CADHE SHORT DESIGN cycle and low manufacturing cost researchers to develop optimal FPGA mapping algorithms forhave made FPGA an important technology for VLSI general Boolean networks.This paper presents a theoretical breakthrough which showsASIC designs. The LUT-based FPGA architecture is a populararchitecture used by several FPGA manufacturers, including that the LUT-based FPGA technology mapping problem forXilinx and AT&T [15], [28]. In an LUT-based FFGA chip, depth minimization can be solved optimally in polynomialthe basic programmable logic block is a K-input lookup table time for general K-bounded Boolean networks. A key step(K-LUT) which can implement any Boolean function of up in our algorithm is to compute a minimum height K-feasibleto K variables. The technology mapping problem in LUT- cut in a network, which is solved optimally in polynomial timebased FPGA designs is to cover a general Boolean network based on efficient network flow computation. Our algorithm(obtained by technology independent synthesis) using K - also effectively minimizes the number of LUT’s by maximizLUT’s to obtain a functionally equivalent K-LUT network. ing the volume of each cut and by several post-processingThis paper studies the LUT-based FFGA technology mapping operations. Based on these results, we have implemented anJT-based FPGA mapping package named FlowMap. Weproblem for delay optimization.The previous LUT-based FPGA mapping algorithms can have tested FlowMap on a set of benchmark examples andbe roughly divided into three classes. The algorithms in the compared it with other LUT-based FPGA mapping algorithmsfirst class emphasize on minimizing the number of LUT’s for delay optimization, including Chortle-d, MIS-pga-delay,in the mapping solutions. This class includes MIS-pga and and DAG-Map. FlowMap reduces the LUT network depth byits enhancement, MIS-pga-new, by Murgai et al. based on up to 7% and reduces the number of LUT’s by up to 50%compared to the three previous methods.A6struct- The field programmable gate-array (FPGA) hasbecome an important technology in VLSI ASIC designs. In thepast a few years, a number of heuristic algorithms have beenproposed for technology mapping in lookup-table (LUT) basedFPGA designs, but none of them guarantees optimal solutions forgeneral Boolean networks and Little is known about how far theirsolutions are away h m the optimal ones. This paper presents atheoretical breakthrough which shows that the LUT-based FPGAtechnology mapping problem for depth minimization can besolved optimally in polynomial time. A key step in our algorithmis to compute a minimum height K-feasible cut in a network,which is solved optimally in polynomial time based on networkflow computation. Our algorithm also effectively minimizes thenumber of LUT’s by maximizing the volume of each cut andby several post-processingoperations. Based on these results, wehave implemented an LUT-based FPGA mapping package calledFlowMap. We have tested FlowMap on a large set of benchmarkexamples and compared it with other LUT-basedFPGA mappingalgorithms for delay optimization, including Chortle-d, MIS-pgadelay, and DAG-Map. FlowMap reduces the LUT network depthby up to 7% and reduces the number of LUT’s by up to 50%compared to the three previous methods.TManuscript received September 28, 1992; revised April 30, 1993. Thisresearch was supported in part by the NSF under Grant MIP-9110511. XilinxInc. and the State of California MICRO F’rogram under Grant 92-030. Thispaper was recommended by Associate Editor L. Trevillyan.The authors are with the Department of Computer Science, University ofCalifornia, Los Angeles, CA 90024.IEEE Log Number 9212334.’Some previous algorithms achieve optimal mapping for restricted problemdomains: Chortle is optimal when the input network is a tree, Chortle-crf andChortle-d are optimal when the input network is a tree and h’ 5 6, and DAGMap is optimal when the mapping constraint is monotone, which is true fortrees.0278-0070/94 04.00 0 1994 IEEE
2IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 13, NO. 1, JANUARY 1994Fig. 1. Mapping a Boolean network to a K-LUT network ( K 3).K-LUT can implement any K-feasible cone of a Booleannetwork. The technology mapping problem for K-LUT basedFPGA’s is to cover a given K-bounded Boolean networkwith K-feasible cones, or equivalently, K-LUT’s4. shows anexample of mapping a Boolean network into a 3-LUT network.Note that we allow these cones to overlap, which means thatthe nodes in the overlapped region can be duplicated whengenerating K-LUT’s. In fact, our algorithm is capable ofduplicating nodes automatically when necessary, in order toachieve depth optimization. A technology mapping solutionS is a DAG in which each node is a K-feasible cone(equivalently, a K-LUT) and the edge (C,,C,)exists if Uis in input(C,). Our main objective is to compute a mappingsolution that results in the minimum delay.The delay of an FPGA circuit is determined by two factors:the delay in K-LUT’s and the delay in the interconnectionpaths. Each K-LUT contributes a constant delay (the accesstime of a K-LUT) independent of the function it implements.Since layout information is not available at this stage, weVI.assume that each edge in the mapping solution contributesa constant delay. In this case, the delay is determined by the11. PROBLEM FORMULATIONAND PRELIMINARIESdepth of the mapping solution, which is known as the unitA Boolean network can be represented as a directed acyclic delay model. We say that a mapping solution is optimal if itsgraph (DAG) where each node represents a logic gate? and a depth is minimum. The primary objective of our algorithmdirected edge (z,j) exists if the qutput of gate i is an input is to find an optimal mapping solution in terms of depthof gate j . A primary input (PI) node has no incoming edge minimization, and the secondary objective is to reduce theand a primary output (PO) node has no outgoing edge. We use number of K-LUT’s used in the technology mapping solution.input(v) to denote the set of nodes which are fanins of gateSeveral concepts about cuts in a network will be used inU. Given a subgraph H of the Boolean network, input(H)our algorithm. Given a network N ( V ( N ) E, ( N ) ) with adenotes the set of distinct nodes outside H which supply source 3 and a sink t, a cut ( X , x )is a partition of the nodesinputs to the gates in H. For a node v in the network, a KThe node cut-size ofin V ( N ) such that s E X and t Efeasible cone at v , denoted C,,is a subgraph consisting of U( X , x ) ,denoted n ( X , X ) ,is the number of nodes in X thatand its predecessors3 such that linput(C,) I 5 K and any pathi.e.,are adjacent to some node inconnecting a node in C, and v lies entirely in C,. The levelof a node v is the length of the longest path from any PI noden ( X , X ) I{. : (z,y)E E ( N ) , x E X and y Eto U. The level of a PI node is zero. The depth of a networkis the largest node level in the network. A Boolean networkA cut ( X , X ) is K-feasible if n ( X , X ) 5 K. Assume thatis K-bounded if linput(v)I 5 K for each node U.We assume that each programmable logic block in an each edge (u,u) has a non-negative capacity c ( u , v ) . TheFPGA is a K-input one-input lookup-table (K-LUT) that edge cut-size of ( X , Y ) ,denoted e ( X , X ) , is the sum of theOur result makes a sharp contrast with the fact that theconventional technology mapping problem in library-baseddesigns is “-hard for general Boolean networks [9], [18].Due to the inherent difficulty, most conventional technologymapping algorithms decompose the input network into aforest of trees and then map each tree optimally [9], [18].Such a methodology was also used in some existing FPGAmapping algorithms [ l l ] , [12], [14]. However, the result inthis paper shows that K-LUT mapping can be carried outdirectly on general K-bounded Boolean networks to achievedepth-optimal solutions.The remainder of this paper is organized as follows. SectionI1 gives a precise problem formulation and some preliminaries.Section I11 presents our depth-optimal technology mappingalgorithm for LUT-based FPGA designs. Section IV describesseveral enhancements of our algorithm for area minimization.Experimental results and comparative study are presented inSection V. Extensions and conclusions are presented in Sectionx.x,x}lcan implement any K-input Boolean function. Thus, each’In the rest of the paper gates and nodes are used interchangeably forBoolean networks.3 is a predecessor of 2) if there is a directed path from U to v.41f the input network is not K-bounded, it may not be covered with K LUT’s directly. In this case, nodes in the network with more than K faninsmay have to be decomposed before covering. However, we consider such adecomposition step as part of the synthesis procedure.
CONG AND DING: FLOWMAP AN OPTIMAL TECHNOLOGY MAPPING ALGORITHMFig. 3. Constraint on the number of inputs to LUT is not monotone (I 3).Fig. 2. A 3-feasible cut of edge cut-size 10, volume 9, and height 2.capacities of the forward edges that cross the cut, i.e.,Throughout this paper, we assume that the capacity of eachedge is one unless specified otherwise. The volume of a cut( X ,y),denoted woZ(X,X),is the number of nodes ini.e.,woZ(X, Moreover, assume that there is a given labelE(w) associated with each node 'U. The height of a cut ( X ,denoted h ( X , X ) ,is defined to be the maximum label in X,i.e.,x) 1x1.x,x),h ( X , X ) max{l(x) : 5 E X }Fig. 2 shows a cut ( X , x ) in a network with given nodelabels, where n ( X , X ) 3, e ( X l x ) 10, h ( X , X ) 2,and woZ(X,x) 9.111. AN OPTIMALLUT-BASEDFPGA MAPPINGALGORITHMFOR DEPTHMINIMIZATIONOur algorithm is applicable to any K-bounded Booleannetwork. Given a general Boolean network as input, if it isnot K-bounded, there are a number of ways to transformit into a K-bounded network. For example, the Roth-Karpdecomposition [23] was used in [20] to obtain a K-boundednetwork. We use the algorithm DMIG presented in [3], whichis based on the Huffman coding tree construction [16], todecompose each multiple input simple gate5 into a tree oftwo-input simple gates. According to the result in [3], sucha decomposition procedure increases the network depth byat most a small constant factor. The reason for carrying outsuch a transformation is that if we think of FPGA technologymapping as a process of packing gates into K-LUT's, then,smaller gates will be more easily packed, and the mappingalgorithm will be able to pack more gates along critical paths toone K-LUT, resulting smaller depth in the mapping solution.This argument is justified by our experimental results in Table111 shown in Section V.In the rest of this paper, we shall assume that the inputnetworks are K-bounded networks. Although we transform'We can always obtain a simple gate network by representing each complexgate in the sum-of-products form and then replacing it with two levels ofsimple gates.an input network into a network of two-input simple gates,the optimality of our algorithm does not depend on the factthat each node in the given Boolean network is a two-inputsimple gate. The optimality of our mapping result holds aslong as the input network is a K-bounded network, in whichthe gates need not to be simple.The fundamental difficulty in the LUT-based FPGA mapping is that the constraint on the number of inputs of aprogrammable logic block is not a monotone clustering constraint. A clustering constraint r is monotone, if knowingthat a network H satisfies r implies that any subnetwork ofH also satisfies r [19]. For example, if we assume that theconstraint for each programmable logic block is the numberof gates it may cover in the original network, it is a monotoneclustering constraint. Unfortunately, limiting the number ofdistinct inputs of each programmable logic block is not amonotone clustering constraint. For example, Fig. 3 showsa network of three distinct inputs, which is 3-feasible. But thesubnetwork consisting of nodes t , v and 20 has four distinctinputs, which is not 3-feasible. Clustering (or, similarly, mapping) for a monotone clustering constraint r is much easierbecause if a subnetwork H does not satisfy the constraintr, we can conclude that H is not a part of any cluster. Itwas shown that Lawler's labeling algorithm [19] can producea minimum depth clustering solution in polynomial timewhenever the clustering constraint is monotone. The DAGMap algorithm developed by Cong et al. [3], [7] modifiedLawler's algorithm and applied it to the LUT-based FPGAmapping problem. Although it achieved encouraging resultsfor depth minimization, it was shown that the DAG-Mapalgorithm is not optimal [3].The mapping algorithm presented in this paper successfullyovercomes the difficulty due to the nonmonotone clusteringconstraint in LUT-based FPGA technology mapping. Thealgorithm runs in two phases. In the first phase, it computesa label for each node which reflects the level of the K-LUTimplementing that node in an optimal mapping solution. In thesecond phase, it generates the K-LUT mapping solution basedon the node labels computed in the first phase.3.1. The Labeling PhaseGiven a K-bounded Boolean network N , let Nt denote thesubnetwork consisting of node t and all the predecessors oft. We define the label of t , denoted Z(t), to be the depth ofthe optimal K-LUT mapping solution of Nt. Clearly, the level
IEEE TRANSAmONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 13, NO. 1, JANUARY 19944(b)(a)(C)Fig. 4. Computing the label l ( t ) of node t ( K 3). (a) The partial network. (b) Construction of Nt and the highest 3-feasible cut. (c) Determining l(t).of the K-LUT rooted at t (if exists) in the optimal mappingsolution of N is at least Z(t),and the maximum label of all thePO’s of N is the depth of the optimal mapping solution of N .The first phase of our algorithm computes the labels of allthe nodes in N, according to the topological order startingfrom the PI’S. The topological ordering guarantees that everynode is processed after all of its predecessors have beenprocessed. For each PI node U , we assign l(u) 0. Supposet is the current node being processed. Then, for each nodeU # t in Nt, the label Z ( U ) must have been computed. Byincluding in Nt an auxiliary node s and connecting s to allthe PI nodes in N t , we obtain a network with s as the sourceand t as the sink. For simplicity we still denote it as N t . Fig.4(a) shows part of a Boolean network in which gate t is to belabeled, and Fig. 4(b) shows the construction of the networkN t . Let LUT(t) be the K-LUT that implements node t in anoptimal K-LUT mapping solution of Nt. Let 13 denote the setof nodes in LUT(t) and X denote the remaining nodes in Nt.Then, ( X , x ) forms a K-feasible cut between s and t in Ntbecause the number of inputs of LUT(t) is no more than K.Moreover, let U be the node with the maximum label in X ,1 in the optimal mappingthen, the level of LUT(t) is Z(U)solution of Nt. Recall the definition of the height of a cut inSection II, we have h ( X , X ) 1(u). Therefore, in order tominimize the level of LUT(t) in the mapping solution of Nt,we want to find a minimum height K-feasible cut (X,inNt.6 In other words, x)Z(t) min(X,s?) is K-feasibleh(X,X) 1.(1).Based on the above discussion, we haveLemma I: The label Z(t) computed by Eq. ( I ) gives the minimum depth of any mapping solution of N t .0Fig. 4(b) and (c) illustrate our labeling method. Since in 4(b)there is a minimum height 3-feasible cut in Nt of height 1,6We exclude the cuts ( X , x ) where 7 contains a PI node. Our algorithmto be shown later on guarantees that such kind of cuts are not generated.we have Z(t) 2, and the optimal K-LUT mapping solutionof Nt is shown in Fig. 4(c).There is no existing algorithm for computing a minimumheight K-feasible cut efficiently. One important contributionof our work is that we have developed an O(Krn) timealgorithm for computing a minimum height K-feasible cutin N t , where rn is the number of edges in Nt. First, we showthat the node labels defined by our labeling scheme satisfy thefollowing property.Lemma 2: Let E(t) be the label of node t , then l(t) p orl(t) p 1, where p is the maximum label of the nodes ininput(t).Proofi Let t’ be any node in input (t). Then for any cut(X,x)in Nt, either t’ E X , or ( X , x ) also determines aK-feasible cut (X’,X’) in Nt, with h(X‘,X’) 5 h ( X , X ) ,whereX’ XnV(Nt,) andX’ XnV(Nt,).If ( X , x ) i sa minimum height K-feasible cut in N t , then, in the formercase, we have Z(t) h ( X , X ) l 2 Z(t’) l, i.e., Z(t) Z(t’);and in the latter case, we have Z(t’) - 1 5 h(X’,X’) 5h ( X , X ) Z(t) - 1, which implies Z(t) 2 Z(t’). (Note thisproves that the label of any node cannot be smaller than thoseof its predecessors.) Therefore, l ( t ) 2 p.On the other hand, since the network N is K-bounded,linput(t)I 5 K. Therefore, (V(Nt) - { t } , { t } )is a Kfeasible cut. Because each node in V(Nt) - {t} is either ininput(t) or is a predecessor of some node in input(t), themaximum label of the nodes in V ( N t )- {t} is p. Therefore,0h(V(Nt) - {t}, {t}) p, i.e., Z(t) 5 p 1.According to Lemma 2, our algorithm first checks if thereis a K-feasible cut ( X t , x t ) of height p - 1 in N t . If thereis such a cut, we assign Z(t) p and node t can be packedinto one K-LUT in the second phase ofwith the nodes inour algorithm for generating the mapping solution. Otherwise,the minimum height of the K-feasible cuts in Nt is p and(V(Nt) - { t } , { t } )is such a cut. In this case, we assignl ( t ) p 1 and we shall use a new K-LUT for node tin the second phase. wt
CONG AND DING FLOWMAP: AN OPTIMAL TECHNOLOGY MAPPING ALGORITHM(a)5(b)(C)Fig. 5. Network transformations in computing a minimum height A--feasible cut in Nt ( K 3).Whether Nt has a K-feasible cut of height p - 1 or notcan be tested efficiently using the following method. Let p bethe maximum label of the nodes in input(t),which is alsothe maximum label of the nodes Nt - {t}. We first apply anetwork transformation on Nt that collapses all the nodes inNt with label 2 p, together with t, into the new sink t‘. Denotethe resulting network as N;, we have the following result.Lemma 3: Nt has a K-feasible cut of height p - 1if and onlyif Ni has a K-feasible cut.Proof: Let Ht denote the set of nodes in Nt that arecollapsed into t’.let X XI, and-If Ni has a K-feasible cut
compared to the three previous methods. ’ Some previous algorithms achieve optimal mapping for restricted problem domains: Chortle is optimal when the input network is a tree, Chortle-crf and Chortle-d are optimal when the input network is a tree and h’ 5 6, and DAG- Map is optimal when the mapping constraint is monotone, which is true for .
Texts of Wow Rosh Hashana II 5780 - Congregation Shearith Israel, Atlanta Georgia Wow ׳ג ׳א:׳א תישארב (א) ׃ץרֶָֽאָּהָּ תאֵֵ֥וְּ םִימִַׁ֖שַָּה תאֵֵ֥ םיקִִ֑לֹאֱ ארָָּ֣ Îָּ תישִִׁ֖ארֵ Îְּ(ב) חַורְָּ֣ו ם
1.2 48kw/65hp 1990 1994 dh 10x825-du 1.3 58-65kw/79 -88hp 1990 1994 dh 10x825du 1.3, 1. 51983 1994 a c a rbu do simple 1 0x8 -du a 4x 10x850-du a alt 5 h 10x865-du a o 10x875-du 1.5 70-77kw/ 105-95hp 1990 1994 dh 10x825-du 1.7 1986 1994 a 10x850-du aa 13x950-du 1.7 16v 101kw/137hp 1990 1994 dh 10x825-du alfa 33 16v 1.7 16v 1990 1994 a 1 0x85 -du aa 13x950-du alfa 6 2.0 a 10x915-du
2.1 (a) One simple answer: choose the mean temperature in June 1994 as the forecast for June 1995. That is, 17.2 C. (b) The time plot below shows clear seasonality with average temperature higher in summer. Month Celsius 1994 Jan 1994 Feb 1994 May 1994 Jul 1994 Sep
2145 14 H.P. Onan Elite Single Hydro 1994 2160 16 H.P. Vanguard Twin Auto Gear 1994 2165 16 H.P. Vanguard Twin Hydro 1994 2185 18 H.P. Command Twin Hydro 1994. NOTES: 1 MODEL: 2130 YEAR: 1994-1995 Factory Model Number: 134-212F100, 135-212F100 12.5 H.P. Auto Gear Drive
Sergio Antonio Priego Resendiz 1920799 18/feb/1994 . 0291 . Isabel Alicia Rodríguez Rivera 499427 22/feb/1994 . 0292 . J. Jesús García Arredondo 1734849 25/feb/1994 . 0293 . Alicia Belaunzaran Flores 1618602 25/feb/1994 . 0294 . Ángel Roldán Arana 1774409 28/feb/1994 . 0295 . César Alejandro Ortiz Plata 1921680 01/mar/1994 . 0296
B2 Flute Duet 3 Gaubert * Divertissement Grec Leduc 1994 B2 Flute Duet 3 Gearhart/Wilkins, ed. Flute Sessions Shawnee 1994 B2 Flute Duet 3 Haydn Echo Zimmerman 1994 B2 Flute Duet 3 Hotteterre * Suite in C Heugel 1994 B2 Flute Duet 3 Jeney, ed. Flotenduos, 2Vols. Eulenburg 1994 B2 Flute Duet 3 Koehler 40 Progressive Duets, Op. 55 Vol.1 (Nos. 16-25) Cundy 1994 B2 Flute Duet 3 Koehler
50 a2305412099 girish 02/05/1994 51 a2305412104 ayush jain 11/7/1994 52 a2305412107 khushal juneja 10/13/1994 53 a2305412109 archit garg 09/11/94 54 a2305412119 ashish yadav 8/1/1994 55 a2305412126 rahul vij 29/6/1995 56 a2305412127 vishwas pancholi 2/18/1994 57 a2305412129 prakhar wadhawan 8/22/1994
A Puppet Patchwork Moon Zooms - W.P. Puppeteers Nevermore - E.A.P of Grey Seal Puppets VHS 1994 SE REGI FEST 1 1994 Southeast Regional Festival, Tape 2 Footage from the 1994 Southeast Regional Festival held in Asheville, North Carolina from June 23-25, 1994. Workshops Pot Pourri VHS 1994 SE REGI FEST 2 1994 Southeast Regional Festival, Tape 3
