## 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 classica- 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 signicant 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 denes
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 denitions, 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 dened 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.

Denition 3 : Physical delay of a path
The physical delay of a path P is dened 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 dene 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 prole
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 networkDenition 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 classied according to tim-
Denition 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.

dened 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 classication results.

a dierent segment.

5.3 Floorplanning problem
5 Design timing prole 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 Classication 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 denition 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 prole
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 : Classied 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 PIle 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 simplication 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

Media Components The selection or development of the culture medium is vital to success in tissue culture. No single medium will support the growth of all cells, and changes in the medium are often necessary for different types of growth response from a single explant. A literature search is useful for selecting the appropriate medium.provide a useful guide on examining the effect of plant growth regu-lators, salt composition of the basal medium and a statistical analysis of the results. Likewise,can provide a guide for studying the effects of the MS inorganic salts on explant growth. If literature on the plant is not available, the development of a suitable medium is based on trial and error. The approach to developing the medium will depend on the purpose of the cell culture. Many of the media outlined in this manual can serve as useful starting points in developing a medium for a specific purpose, whether it is callus induction, somatic embryo-genesis, anther culture, or shoot proliferation.

FACULTE MIXTE DE MEDECINE ET DE PHARMACIE ANNEE UNIVERSITAIRE 2001/2002 LE DIPLOME D'ETAT DE DOCTEUR EN PHARMACIE Présentée et soutenue publiquement le 21 mars 2002 né le 02 avril 1976, à ROUEN LES ACOUPHENES OU L'IMPOSSIBLE SILENCE : ETIOLOGIE, PHYSIOPATHOLOGIE ET TENTATIVES DE TRAITEMENT Président du jury :