The Research On Key Technologies Used In Chip-level Multi-layer Routing

The routing system is divided into two steps: global routing and detailed routing. In order to reduce the complexity of problem, the traditional routing generally is a kind of grid routing, which bases on uniform-grid-graph. Essentially speaking, routing resource is a successive area, so the routing should be a kind of gridless routing, which can be satisfied with the requirement of variable wire width and variable wire space. So, with rapid development of the computer hardware, the researches on gridless routing are more and more popular among domestic and foreign researchers.In this dissertation, based on the in-depth investigation and thorough summary of the latest gridless routing technology and the key technologies used in the large scale routing problem, the key routing technologies are thoroughly studied, which are used in global routing and gridless detailed routing under performance-driven chip-level multilayer routing flow, and a series of effective algorithms is proposed, which are used to optimize the performance of the timing and manufacture. The method of crosspoint assignment which connects global routing and detailed routing, is also primarily studied.The present gridless routing algorithms mainly take the routing ratio as the essential goal, but very little takes account of performance optimization such as timing optimization. In view of these situations, a timing-driven multilayer global routing algorithm is proposed. This algorithm employs a multilayer work flow like "V" and finishes routing by coarsen followed by uncoarsen. In coarsen step, the problem scale is gradually reduced in a Top-Down way until the scale is enough small to be deal with;in uncoarsen step, the routing results are gradually refined in a Down-Top way. When the most top level arrives, the global routing results are determined. In coarsest level, a special multi nets routing algorithm considering timing constraint is proposed for global nets. To avoid the blindness introduced by prematurely fixed routing and supply overall consideration and flexibility for routing, this algorithm postpones fixing exact routing by the soft edge and mobile Steiner node.In view of the feature of multilevel gridless routing, a new crosspoint assignment (CPA) method is required to meet noise constraint and via minimum. In this dissertation, the algorithm of crosspoint assignment is primarily studied: this algorithm firstly decomposes the boundary of a tile to a set of internals by blockinformation, and then solve CPA problem by two steps: coarsened crosspoint assignment (CCPA) and refined crosspoint assignment (RCPA). In the CCPA, safe space for each crosspoint is calculated by noise constraint and each crosspoint is allocated to an internal. CCPA employs effective graphic routing algorithm to minimize via amount and ensure none of internals overflow. In the RCPA, the exact position of each crosspoint is determined to meet with noise constraint and find the maximum number of alignments between the crosspoint on the boundary and their neighboring pins (or crosspoint) of the same nets.In detailed routing, a multilayer gridless area routing algorithm based on non-uniform-grid graph is proposed. This algorithm firstly disassembles nets with multiple terminals by MCSTMR, which minimizes the radius and cost of spanning tree considering timing performance, and generates a set of nets with two terminals. Then a multi-layer routing problem is converted into a sequence of two-layer routing problem by self-adaptive iterative strategy. When a net with two terminals is processed, a non-uniform-grid graph is generated by information of block inside the current routing layer pair, which is the basic graph model for maze routing algorithm. On the non-uniform-grid graph, all nets with two terminals are routed one by one by improved maze routing algorithm , then detailed routing results are generated. In view of the feature of gridless routing, this dissertation improves the searching strategy of maze routing and manages the blocks by a 2-d internal tree to accelerate maze routing. At the same time, a conception of design for manufacture is introduced in a maze routing and an OPC-friendly maze routing algorithm is proposed to improve the probability of manufacture.The main algorithms above have been implemented in C/C++ and successfully debugged. It is shown experimental that the algorithms presented are valid and efficient.