Information Technology Reference
In-Depth Information
Netlist
Initial net Odering
Find e MaxCong
e MaxCong
Edge_Capacity ?
Run FLUTE
N o
>
Odering the Steiner trees
Ye s
CS-Path laying
N o
Iteration<limit ?
Ye s
Congestion free GR
Apply CR-Algorithm
GR with overlow
Iteration++
Fig. 1. Flow chart depicts the working steps to balance congestion
the net connections, same tracks of a circuitmightgetusedbymanynets.This
in turn can lead to congestion of the tracks. Traditional global routing techniques
does not employ any out of the box congestion minimization techniques and de-
pends upon cumbersome maze routing techniques to achieve this. It is customary
to map a global routing problem to a grid graph and then solve it. The technique
depicted here uses grid formulation of the global routing and then tries to mini-
mize congestion by following a two step approach. The sequence of operations or
the steps are clearly defined by the flowchart shown in Fig. 1. In the first step, the
technique tries to keep the congestion in control while laying out the paths of the
circuit using Congestion Sensing Path Laying technique. Once the paths are laid,
the second step uses heuristics to minimize congestion further while keeping the
nets connected.
Algorithm 1. CongestionSensing
Input: Two steiner points a ( x 1 ,y 1 )& b ( x 2 ,y 2 )where( x 1
= y 2 )
Output: Connected path between two steiner points using grid edges consider-
ing grid edge congestion meanwhile.
A virtual box B is assumed with ( x 1 ,y 1 ) , ( x 1 ,y 2 ) , ( x 2 ,y 1 ) , ( x 2 ,y 2 ) corner points
Repeat the steps 3 to 10 until a == b
Select two incident edges ap i and aq i towards b within B ;
if ( CapCongRatio ( ap i ≤ aq i )) then
Lock ( ap i );
a = p i
else
Lock ( aq i );
a = q i
end if
= x 2 ) and ( y 1
2.1 Congestion Sensing during Path Laying
This section describes the congestion minimization technique used while laying
paths of nets. Initially Steiner minimal trees are generated using FLUTE [28].
FLUTE provides two pin tree segments of one or more edge lengths. The next
step is to select the grid edge for laying the paths. At this juncture while laying
out the edges, we make sure such that the same edge does not get selected
repeatedly. Doing so helps to keep congestion in control and the heuristic applied
Search WWH ::




Custom Search