Simultaneous Routing and Buffer Insertion with Restrictions on Buffer Locations

Abstract During the routing of global interconnects, macro blocks form useful routing regions which allow wires to go through but forbid buffers to be inserted. They give restrictions on buffer locations. In this paper, we take these buffer location restrictions into consideration and solve the simultaneous maze routing and buffer insertion problem. Given a block placement defining buffer location restrictions and a pair of pins (a source and a sink), we give a polynomial time exact algorithm to find a buffered route from the source to the sink with minimum Elmore delay. 1 Introduction With the evolution of VLSI fabrication technology, interconnect delay, especially global interconnect delay, has become the dominant factor in deep sub-micron design. Many techniques are employed to reduce interconnect delay; among them, buffer insertion has been shown to be an effective approach [2]. During routing process, especially that for global nets, there are macro blocks placed within the area. These blocks form useful routing regions because wires are allowed to run over them. But since buffers are implemented by transistors, a buffer "over " a macro block must be actually put into that block. However, it is impossible to insert a buffer into a macro block if it is an IP (Intellectual Property) where internal structure can not be changed, or it is a block such as memory which requires regular layout. Even in the case when that is theoretically possible, since a re-design of the influenced block is needed, it is usually not allowed due to the design flow. Therefore, macro blocks present themselves as routing resources for wires but obstacles for buffers