Abstract
As the manufacturing technology keeps shrinking, the number of I/O pins in a current VLSI design has easily grown to hundreds, or even thousands. With the pressing need of connecting the huge number of I/O pins to a PCB (Printed Circuit Board), a BGA (Ball Grid Array) package is used mostly nowadays. In this thesis, we propose a two-layer BGA global routing algorithm which routes the net in the order of fingers one at a time while considering the minimization of the total wirelength and overflow. Our algorithm begins with constructing a routing graph and assigning a parameter which represents the maximum overflow tolerance initialized to 0. Our algorithm then extracts a routing subgraph from the routing graph for each net based on the viewpoint of planar routing. Our algorithm next routes nets one at a time on their respective routing subgraphs. If our algorithm cannot find a routing path from a finger to a ball on the given routing subgraph, our algorithm will expand the routing subgraph and try to route again until our algorithm find a routing path or the number of expanding times reaches the user-specified upper bound. A history cost is introduced to make our routing algorithm avoid constructing routing paths through grids which are overflowed during previous iteration. Once it is found that our algorithm cannot finish routing a net, our algorithm will increase the maximum overflow tolerance by one and restart the whole routing process. The experimental results show that our algorithm averagely decreases 96.8% total overflow and 83.33% maximum overflow as compared to a most recent work. Besides, our algorithm produces smaller total wirelength and runs 4.39 times faster.