Multi-instantiated Block Top-layer Routing Technique Based on Steiner Tree Algorithm

As the scale of chips becomes larger and larger, the time and labor cost of the overall design of a large single chip becomes higher and higher. Therefore, it has become a widely adopted solution to divide one large-scale design into several smaller blocks and realize the functions of each block respectively. In this paper, a multi-instantiated block routing technique is proposed based on the improved Steiner tree algorithm. The algorithm divides wire networks into grids and uses FLUTE to construct and decompose the minimum rectangular Steiner tree of all multipin wire networks, which will decompose any multi-pin connection into several two-pin connections. It abstracts the functions of multi-instantiated blocks involved, and adds fixed pins on the edge of them. The routing process will be conducted inside every block respectively. In order to verify the accuracy and validity of the proposed method, a series of verification experiments are carried out, which shows that the proposed multi-instantiated block routing algorithm can effectively reduce the path redundancy caused by multiple pass-throughs in blocks and improve the routing process efficiency.