Multi-Instantiation Top-Level Routing Technique Based on Decision Negotiation Algorithm

With the development of integrated circuit, multi-instantiated block technology is considered as a reliable optimization direction of chip design, which can effectively save the storage and labor cost in the development process, but brings new challenges to the top layer routing at the same time. On this basis, a multi-instantiation top-level routing algorithm based on decision negotiation is designed in this paper, which effectively solves the problems of multi-instantiated block routing, including long routing time and too long path length. In this paper, a non-uniform grid form is proposed to formulate alternative path sets and determine alternative routing channels between endpoints. The decision extraction and decision evaluation algorithms are used to deal with the path redundancy and short circuit problems generated by multiple instantiations. The feasible solution is determined by improved BFS (Breadth First Search) algorithm on the candidate decision set. The optimal solution with the shortest path in Manhattan is determined by iterative decision evaluation in the feasible solution. In order to verify the accuracy and effectiveness of the proposed method, a verification experiment is conducted in this paper for a number of multi-instantiation modules within 100. The experimental results show that the routing time of the proposed multi-instantiation top-level routing algorithm based on decision negotiation is between 0.1s and 3s, and the ratio of the path length to the standard value is over 95%, on the basis of a 100% success ratio.