Routing the Power and Ground Wires on a VLSI Chip

摘要

This thesis presents four new algorithms to route noncrossing power and ground trees in one metal layer of a VLSI chip. The implementation of the best algorithm forms MIT's Placement-Interconnect (PI) Projects power-ground routing phase. The input of this power-ground algorithm is a set of rectangular modules on a rectangular chip. Because of bonding limitations, the pads are placed along the chip's perimeter, while the logic modules are placed in the interior. In constructing the power-ground layout, the algorithm first lays a ground ring between the pads and the chip's perimeter, then a power ring between the logic modules and the pads. Next, a tree of wires connects the ground pad with the logic modules' ground connection points. Then, starting at various points on the power ring, several branches of wires connect the power ring to the logic modules' power connection points. A tree-traversal algorithm then uses the modules' current requirements to determine how much current will flow through each power-ground wire during the chip's operation. An algorithm then widens each wire to the width appropriate for carrying that current. (Author)