Information Technology Reference
In-Depth Information
algorithms for concurrent global routing, integer programming (IP) methods
have been suggested. Integer programmingcanbeformulatedinanumberof
ways.
The [21], solves the GR problem, using IP where GR constraints are combined
to find the best wiring layput of a circuit. New modeling techniques are used
to solve the routing problem formulated as an integer programming problem.
The LP problem is solved by an interior point algorithm that finds a near op-
timal wiring in polynomial time without perfoming randomized rounding. Few,
IP based GR are SideWinder [22], BoxRouter [23], and GRIP [24]. The common
approach of IP based routers is the decomposition of multi pin nets into two
pin nets using FLUTE. After decomposition, different router uses different ILP
formulations to solve the global routing problem. Given the routing graph and
a set of Steiner trees for each net, the goal of this technique is to select one
Steiner tree for each net, such that, the total wire length is minimized and the
channel capacity constraints are not violated. [25] presents an ecient approach
to global routing that takes spacing-dependent costs into account and provably
finds a near-optimum solution including these costs. [26] presents a parallel
global routing algorithm that concurrently processes routing subproblems cor-
responding to rectangular subregions covering the chip area. The algorithm uses
at it core an existing integer programming (IP) formulation both for routing
each subproblem and for connecting them. GRIP [24] is another global rout-
ing technique via integer programming. GRIP optimizes wirelength and via cost
directly. By using integer programming in an effective manner, GRIP obtains
high-quality solutions. The paper [27] presents a collaborative procedure for
multiobjective global routing that takes independently generated multiple GR
solutions as input and performs multi objective optimization based on Pareto
algebra to generate quick multiple GR solution.
This paper introduces a novel approach of reducing total overflow with focus
on keeping wire length and signal delay in check. This paper makes the following
contributions:
1. This algorithm does not follow traditional steiner tree construction approach,
rather a congestion sensing algorithm has been developed for this.
2. For load adjustment a congestion balancing algorithm has been designed
that takes signal delay and wire length into consideration.
3. Tree augmentation has been applied to the remaining of the the nets with
atleast one congested edge few iterations of congestion balancing algorithm.
The rest of the paper is organized as follows. While the next section describes
the congestion estimation and minimization technique, section 3 presents the
experimental results and comparisons with some existing global routers. The
conclusion of the paper is provided in section 4.
2 Congestion Estimation and Minimization
During global routing, pins with the same electric potential are connected using
wire segments. The final design should reflect fully connected nets. While making
