Department of Electrical and Computer Engineering
University of Wisconsin - Madison
Computer Engineering Seminar
(Fall 2009-2010)

        Speaker:    Tai-Hsuan Wu
        Time:       12:00 pm 
        Date:       November 6, 2009    
        Location:   Room 4610, Engineering Hall 
        Subject:     GRIP: Scalable 3-D Global Routing using Integer Programming


As usual soft drinks will be available for those who show up in
time for the seminar. 

*************************************************************************

           GRIP: Scalable 3-D Global Routing using Integer Programming


                                     by

                                Tai-Hsuan Wu    
               Department of Electrical and Computer Engineering
                       University of Wisconsin – Madison
                         Madison, Wisconsin 53706 - 1691

Abstract:

Global routing is one of the most critical steps within the physical 
design flow. This is a stage which plans the approximate routing path 
of each net under a given placement information, and later guides the 
detail router to assign wires to routing tracks while enforcing spacing 
constraints and more sophisticated design rules. The quality of the 
global routing solution directly affects chip area, circuit timing, 
power consumption and the number of iterations required to complete the 
design cycle. In this talk, we present GRIP, a scalable global routing 
technique via Integer Programming (IP). IP was considered not 
applicable to Global Routing due to its high computing demand. 
Nevertheless, we show that the IP for Global Routing can be solved in 
parallel by applying several techniques such as the price and branch 
procedure, the IP decomposition, and the floating terminal concepts. 
Compared to the state-of-the-art academic global routers, GRIP can 
reduce total wire length and via cost by on average 8 % for the ISPD 
2007 benchmarks.


Biography: 

Tai-Hsuan Wu is a Ph.D candidate in Electrical and Computer Engineering 
at the University of Wisconsin-Madison. He received the B.S. degree 
from the Department of Electrical and Control Engineering, National 
Chiao Tung University, Taiwan, in 2002. His research interests are in 
the area of computer-aided design and with emphasis on parallel 
optimization, grid computing environment, and power aware high-
performance design techniques.