Congestion Balancing Global Router - VLSI Design and Test - page 223

Congestion Balancing Global Router
Shyamapada Mukherjee 1 ,JibeshPatra 2 , and Suchismita Roy 2
1 Dr. B.C. Roy Engg. College, Durgapur, India
2 National Institute of Technology, Durgapur, India
{shyamamukherji,jibesh.patra}@gmail.com ,
[e-mail]
Abstract. A novel algorithmic approach for a global routing solution
for VLSI circuits is proposed in this paper. Instead of following the tra-
ditional Steiner tree approach towards global routing, we have used a
congestion sensing path laying approach. We introduce the concept of
detouring of net segments running through heavily congested edges. The
technique brings down the congestion of edges, to meet the constraints of
edge capacity, by detouring the net segments through sparsely populated
edges. Our approach has been implemented and tested on the ISPD 98
benchmark circuits and has achieved results comparable to other global
routers when congestion minimization and wire length minimization are
taken into consideration.
Keywords: Global Routing, Detouring, Steiner Tree.
1 Introduction
Routing is one of the traditional VLSI physical design automation area along
with placement and synthesis. With exponentially growing demand of nano-
circuits, shrinking size of integrated circuits which in turn increases chip density,
and on chip communication, the challenges for current global routers are more
than ever before. During the global routing phase, the planning of a provisional
path between the interconnects, in various routing regions on the chip takes
place. Global routing techniques in recent years have improved significantly with
the introduction of ISPD1998 [1], ISPD2007 [2], and ISPD2008 [3] global routing
benchmark circuits.
The approaches of solving global routing problem can be grouped into two
broad categories: sequential and concurrent techniques. In sequential routing ap-
proaches, nets are first ordered according to their routing importance followed
by each net being routed separately. However, once a net has been routed it may
block other nets which are not yet routed. As a result, this approach is very sen-
sitive to the order in which the nets are considered for routing. In this approach,
routes for nets routed early can be easily found while the nets routed at a later
stage might be dicult to route or become unroutable. Sequential algorithm was
first introduced by Lee [4] and it became the basis for the maze runner algo-
rithms. Several approaches have been proposed to extend these algorithms to