MedicineLakex

 

Timing driven floorplanning on programmable hierarchical targets

Timing Driven Floorplanning on Programmable Hierarchical S.A Senouci, A. Amoura, H. Krupnova, G. Saucier.
Institut National Polytechnique de Grenoble/CSI 46, Avenue Felix Viallet 38031 Grenoble cedex, FRANCE Abstract{ The goal of this paper is to perform In [KatsKoWaYo95] partitioning method under perfor- a timing optimization of a circuit described by a mance, area and IO pins constraints was proposed for MCM network of cells on a target structure whose con- systems. The method rstly uses clustering of all nodes that nection delays have discrete values following its hi- cause the timing violations. After that the iterative im- erarchy. The circuits is modelled by a set of timed provement with mathematical programming is applied to cones whose delay histograms allow their classica- minimize the number of cuts.
tion into critical, potential critical and neutral cones according to predicted delays. The oorplanning is In [RajWong93] the problem of circuit clustering for de- then guided by this cone structuring and has two lay minimization was considered under any monotone con- innovative features: rst, it is shown that the place- straint. Proposed algorithm is timing-optimal, but the ment of the elements of the neutral cones has no penalty is a high degree of replication. In [YaWo95] pin impact on timing results, thus a signicant reduc- constraint is also taken into consideration.
tion is obtained; second, despite a greedy approach, In [SwaSe95] path-based timing driven placement algo- a near optimal oorplan is achieved in a large num- rithm is presented. The dierence with the preceding path- ber of examples.
based approaches is that it may handle very large circuits.
The hierarchical methodology is applied through condens- ing netlist and applying simulated annealing with dierent temperatures to netlist with dierent degrees of condens- ing. Timing penalty is incorporated into the annealing cost The problem of incorporating performance objectives in the In [YousSait95] timing driven oorplanning approach is physical design of integrated circuits has been widely ad- presented for general cell layouts. The approach incorpo- dressed in the past relating to placement, oorplanning, and rates timing criteria into the objective function of the greedy chip partitioning.
force-directed block placement algorithm.
In [BurYou85] an approach to the automatic layout de- In [RoySe94] present a multi-FPGA partitioning algo- sign for VLSI chips was proposed. It incorporates timing in- rithm handling timing constraints. Method considers the formation to inuence the placement and wiring processes. geometric aspects - relative positions of partitions with re- Placement is based on a successive partitioning algorithm. spect to each other, subdividing each partition into bins.
Weighting nets according to their timing criticality biases Timing penalty function is incorporated into the simulated the gain computation of the FM partitioning algorithm.
annealing cost function.
In [ShiKuTsay92] system partitioning algorithm for In [SawTho95] a constructive set cover based approach MCM is proposed under timing and capacity constraints. is proposed to minimize the number of chip crossings in They use a divide-and-conquer strategy: srtly, clustering multi-way partitioning for FPGAs. In [SauBra93] cone- is applied to insure timing correctness; then K-Way pack- based clustering and clusters merge are applied to contain ing is applied to obtain an initial solution satisfying capacity critical paths inside cones.
constraints, and after that K&L algorithm tries to minimize No one of the previous approaches addressed the multi- net crossings.
level target. In this paper, we present a timing-driven oorplanning approach for hierachically structured pro- grammable targets. We propose an algorithm which denes partial assignement of the design cells to the target struc- ture nodes. This assignement is performed only for timing critical cells and guarantes the timing predictability of the nal placement.
The paper is organized as follows. In section 2, we give I=O be the number of I=O of a quadrant.
basic denitions, terminology and notations used thereafter.
Our desing modelling is presented in section 3 nd 4. Timing Let NQc be the number of cells of a quadrant.
modelling and the oorplanning problem are described in section 5. Algorithm for timing invariant partial oorplan Let NSq be the number of quadrants in a segment.
is discussed in section 6. In section 6, we show how to translate constraints oorplan to the place and route tool. 2.2 Timing characteristics Experimental results and conclusion are given in sections 8 As was said above, each level of hierarchy in the target ar- chitecture is characterized by an interconnect delay added when traversing this level. For example i1;i2 and i3 cor- 2 Hierarchical target respond to the interconnect delay of the Levels 1,2 and 3 correspondingly in Figure 1.
2.1 Physical characteristics In the following, we suppose that the target hierarchy has A target architecture is characterized by a set of basic mod- 3 levels as shown in Figure 1. We call the rst level nodes ules/cells and interconnection resources. A hierarchical tar- as quadrants and the second level nodes as segments.
get is dened in addition by a hierarchy tree diagram with a depth corresponding to the number of levels of hierarchy. At Traversal time of a cell ci is denoted ci and may vary each level the chip is organized into a subset regions, called from a cell to another.
quadrants, containing a xed number of modules. Like for The interconnect delay between two cells in a quadrant any hierarchy, the subsets at a given level are included in a is constant which implies a fanout independant delay.
subset associated with a higher level. In this paper we make a basic assumption that connections have a discrete delay The interconnect delay between two cells in two dier- at dierent hierarchy levels. Usually the interconnect delay ents quadrants is constant and denoted dq.
grows at higher levels. Figure 1 gives an example of a hi- erarchical device structure represented by a hierarchy tree The interconnect delay between two cells in two dier- and a chip layout. Each hierarchy tree node corresponds ents segments is constant and denoted ds.
to a chip region, or quadrant, and may be weighted by a number of parameters (size in terms of the number of basic 3 Design modelling cells, IO pins number, etc.). In Figure 1a the "hierarchy tree" diagram represents the target with three levels of hi- erarchy. In Figure 1b the corresponding chip structure is 3.1 Boolean network shown. At each level of hierarchy the interconnect channels The digital circuit is modelized as boolean network. This are available. We suppose that there is no limitation on the network is represented as a directed bipartite graph G = (V ;V ;E) where the node set V represents the circuit ele- ments and node set V represents the nets.
A node N V is said predecessor of a node N V if there exists a directed edge e E from N V to Level 2 Interconnect Level 2 Interconnect N V . In other words,if a net N is connected to the output pin of module represented by N . The node N is called successor of the node N .1 Level 3 Interconnect V is said successor of a node N if there exists a directed edge e E from N V to Level 2 Interconnect Level 2 Interconnect N V . In other words,if a net N is connected to an input pin of module represented by N . The node N is called predecessor of the node N .1 Nodes from the set V correspond to combinatorial and sequential elements of the circuit.
Figure 1: Hierarchical Target: a) Hierarchy tree; b) chip The inputs/outputs of the sequential elements are called secondary inputs/outputs.
traversed hierarchy levels.
Denition 3 : Physical delay of a path The physical delay of a path P is dened as follow : T = TL(P) + TI(P). Where TL(P) is the logic delay of the path P and TI(P) is the Interconnect delay of the path P.
3.4 Prime cones of a design A prime cone in the network is a predecessor cone of any primary /secondary output.
One node may belong to one or more cones, which forms the cone intersections. An example of circuit containing two intersecting cones is given in Figure 4.
Figure 2: Circuit representation.
3.2 Predecessor cone We dene the predecessor cone of a node of the set V by the set of paths connecting that node to primary or sec- ondary inputs without traversing any node corresponding to a sequntial element.
Intersection of the prime cones C1 and C2 Figure 4: Intersecting prime cones.
3.5 Design prole In Figure 5 are given statistics of the number of prime cones in dierent industrial circuits.
Figure 6 shows the saturation in term of cells of the prime Predecessor cone of the node E8 cones. In fact, the size of the cones in term of cells will be a criteria to choose an appropriate algorithm to perform Figure 3: Predecessor cones.
the oorplanning, thus we will consider in the following two kinds of cones, the wide ones and the narrow ones.
3.3 Paths in a boolean networkDenition 1 : Logic delay of a path 4 Timing modelling for prime cones It is considered here to use the prime cones as basic con- path P traversing n cells has a logic delay TL(P) = stituants. The prime cones are classied according to tim- Denition 2 : Interconnect delay of a path The interconnect delay of a path P is determined after the ing criticality. This will allow timing driven assignement of oorplanning process. It takes in account the number of prime cones to quadrants later on.
dened as follow : C880 MCNC Design. : Upper bound predicted arrival time.
AT(Ci) = MaxP C (TL(P)) + NQ(Ci) dq + NS(Ci) dS.
: Lower bound predicted arrival time.
Epsilon-critical prime cones The physical delay of a cone is equal to the physical delay Potential critical prime cones of its longest path.
TP(Ci) = TP(P), where P is the longest path in the cone P(Ci) be the physical delay of the prime cone Ci, then Neutral prime cones Tp(Ci) AT(Ci).
Let Ci be a prime cone, its physical delay after placement is at worst equal to AT(Ci), because in the worst case, each cell of the longest path delay in the cone C Figure 7: Cone classication results.
a dierent segment.
5.3 Floorplanning problem 5 Design timing prole and classi- The Floorplanning process consits on assigning cells to the fying prime cones of a circuit quadrants of the hierarchical target.
Theorem 5.1 Classication of prime cones The physical delay of a set of prime cones is independent of the assignement of the cells of neutral cones.
At the begining, the Floorplanning process consists in as- signment of basic cells to quadrants. Prime cones are eval- Proof uated by computing thier lower and upper predicted arrival Let C times. These predicted times allow us to classify the cones i be a neutral cone and TP (Ci) the physical delay of into three dierent sets.
According to the denition of neutral cones, we know that  Critical prime cone. Prime cone whose root In another hand, even in the case of the worst assignement has a lower bound predicted time AT(Ci) such that of the cells of the cone Ci, we have TP(Ci) AT(Ci). (II) i) Max(AT) .
(I) and (II) implie that TP(Ci) Max(AT): Or Max(AT) is the lower bound predicted arrival time of Set2: Neutral cones. Prime cone whose root has an the set of prime cones, this implies that the assignement upper bound predicted time AT(Ci) such that : of the cells of the neutral cone Ci has no inuence on the AT(Ci) Max(AT) .
physical delay of the set of prime cones.
Set3: Potential critical cones. Prime cone whose root has an upper bound predicted time AT(Ci) such that 5.4 Experimental results on complexity i) Max(AT) .
5.2 Design timing prole The complexity reduction of the oorplanning problem is about (Number of neutral prime cone / Number of prime In Table 1, we present the results of timing analysis per- cones).
formed on the MCNC benchmark C880. It may be seen In Figure 7 is presented an experimental evaluation of that the number of  critical cones is small (equal to 4), the complexity reduction due to the elimination of neutral and the number of potential critical cones is smaller (equal cones. We observe that in average, the complexity was re- to 3) than the number of neutral cones (equal to 19).
duced by more than 47%.
The value of  is xed here to almost 10% of the maximum lower bound predicted time of the whole prime cones.
Pot-critical :Potential Critical Pot-critical Neutral % Neutral 1. Creating prime cones and intersections structures 2. Performing timing analysis 3. Classifying cone set into -Set1: critical cones -Set2: neutral cones -Set3 :potential critical cones 4. Clustering usign logical depth based approach 5. Update current arrival time Table 1: Complexity reduction Set1 and Set3 empty? Choose the best solution 6 Algorithm for timing invariant Figure 8: Timing-driven placement algorithm.
In the rst step, the prime cones and their intersections 6.1 Logic depth based approach are created, then we perform the timing analysis by com- puting the dierent delays (AT, AT,.). This timing anal- Input : Classied cones.
ysis allows us to classify the prime cones into three sets Local variables : : critical prime cones, potential critical prime cones and neutral prime cones.
c : Number of cells in a quadrant.
During the oorplanning process, the current arrival time q : Number of quadrants in a segment.
indice segment : integer = 0.
is updated as follows : Output : Set of constraints.
Consider the oorplanning performed on the elements of a cone Ci whose root is a node Ni. At each step, a cell cj of while(set of  critical cones is not empty) the cone is assigned to a quadrant Q. If at a given time, the number of quadrants used is greater than the minimum number of quadrants required to implement the cone Ci while(all the nodes of C whish is estimated to N i are not assigned) Q(Ci), the current arrival time is Select The longest path tree of C then updated.To update the current arrival time, intercon- nect delay between quadrants is then taken in account. If i be the top of the path tree selected; /*Grouping the elements of N two quadrants belong to the same segment and connected i predecessor cone PCi.*/ /*The grouping is performed from the leaves to the top*/ to each other, then an interconnect delay dq is added. Oth- erwise, if two quadrants belong to two dierent segments while (Number of quadrant used N and connected to each other, then an interconnet delay d indice segment++; is then added. All the paths which cross the cone Ci are also updated, but we have to distinguish two cases : indice segment = New Set of quadrants; The rst case is when C i belongs to an intersection between Elements are assigned to a quadrant Q; two dierent prime cones, then all the paths which cross the Add the quadrant Q to the set S i and may belong to the two prime cones have to be updated. Otherwise, only the paths which cross the cone Ci and the selected prime cone are currently updated.
Update the current arrival time; 7 Connection to place and route The resulting informations of the oorplanning algorithm Delay Delay Delay Delay Delay Delay are stored as constraints in a le for the place and route tool. These facilities to propagate oorplan constraints ex- ist in mostly for all FPGA design (Xilinx, ORCA, Altera.).
In this paper, we take as illustration a hierarchical target namely called AMD MACH5. In the corresponding soft- ware environnement, these constraints will be propagated to a special le called PI (physical information) and passed to the AMD lter MACHXL .
The same work can be done for Xilinx using RLOC con- Table 2: Experimental results on MCNC benchs.
straints and PPR tool.
Example : The positions of the macrocells S2 and S1 are passed to the Circuits place and route tool as follows : Delay Delay Delay Delay Use PIle for constraints : Section Target 'S0Ba'; This constraint means that the place and route tool has to assign the cells S1 and S2 to the quadrant a of the segment S0 ( see Figure 1).
8 Experimental results Table 3: Experimental results on mutiplier.
The oorplanning algorithm described in this paper has been implemented in the C language on Sun SPARC work- stations, and tested on a set of industrial examples. We compared the results with those obtained by the placement tool without oorplanning constraints. The experimental Delay Delay Delay Delay Delay Delay results (Table 2 and Table 3 and table 4) show a reduction of 57%,79.44%,61% on the delay due to the interconnections in the circuits and 15%,19.22%,15% on the critical path de- lay of the circuits.
C.P : Critical Path Int : Interconnect Timing predictable layout is one of the most dicult prob- lems in the electronic circuit design world. The target ad- dressed here makes the timing prediction easier. In addition to the complecity reduction of the oorplanning problem, we focused on designs where a logic structuring contributes also to the problem simplication for the sucient condition track. Within this framework, it was shown that the timing Table 4: Experimental results on adder predictable layout becomes a tractable problem. Pratical results demonstrated the eciency of these approaches on a typical hierarchical target namely the last MACH5 CPLD family. The approaches proposed here can be extended to all FPGA/CPLD families.
10 References[SawTho95] P. Sawkar, D. Thomas "Multi-Way Partition- ing For Minimum Delay For Look-Up Table Based FPGAs", Proc. 32nd Design Automation Conference, 1995: 201-205.
[SauBra93] G. Saucier, D. Brasen, J-P. Hiol "Partition- ning with cone structures", Proc. ICCAD , 1993 [KatsKoWaY o95] Y. Katsura, T. Koide, S. Wak- abayashi, N.Yoshida "A New System Partitioning Method under Performance and Physical Constraints dor Multi- Chip Modules", Proc. ICCAD, 1995 [Y ousSait95] H. Youssef, S. M. Sait, K. J. Al-Farra, "Timing Inuenced Force Directed Floorplanning", Proc.
of IEEE Int. Conf. on Comput.-Aided Design, 1995: 156- 161.[SwaSe95]W. Swartz,C. Sechen, "Timing drivenplace- ment for large standard cell circuits", Proc. 32nd Design Automation Conference, 1995: 211-215.
[Y anWon95] H. Yang, D. F. Wong "Circuit clustering for delay minimization under area and pin constraints", Proc.
of IEEE Int. Conf. on Comput.-Aided Design, 1995: 65-70.
[RoySe94] K. Roy-Neogi, C. Sechen, "Mul- tiple FPGA partitioning with performance optimization", Proc. ACM/SIGDA Int. Symp. on Field Programmable Gate Arrays, 1994: 146-152.
[SauBra93] G. Saucier, D. Brasen, J-P. Hiol "Partition- ing with cone structures", Proc. ICCAD, 1993.
[RajWong93] R. Rajaraman, D. F. Wong, "Optimal clus- tering for delay minimization", Proc. 30th Design Automa- tion Conference, 1993: 309-314.
[ShiKuTsay92] M. Shih, E. S. Kuh, R.-S. Tsay, "Performance-driven system partitioning on multi-chip modules", Proc. 29th Design Automation Conference, 1992: [HauNaiY of87] P.S. Hauge, R. Nair, E.J. Yoa, "Circuit placement for predictable performance", Proc. of IEEE Int.
Conf. on Comput.-Aided Design, 1987: 88-91.
[BurY ou85] M. Burstein, M. N. Youssef, "Timing inu- enced layout design", Proc. 22nd Design Automation Con- ference, 1985: 124-130.

Main Page

Front Matter

Table of Contents

Session Index

Source: http://www.cecs.uci.edu/~papers/compendium94-03/papers/1998/fpga98/pdffiles/04_2.pdf