Gridless Routing Algortithms For Analog Integrated Circuits

With the rapid development of the integrated circuit, the proportion of analogcircuit in the integrated circuitis growing increasingly. This is because most signal wecontact is analog signal in our daily life. However, due to the diversity of the analogcircuit’s function, the complexity of self-restraint, and analog circuit easily affectedby noise, analog circuit automation develops extremely. The slowdevelopment ofanalog circuit automation has become the bottleneck of the development of integratedcircuit. It has an important research value that dedicates to the study the analog circuitdesign automation. It focuses on the study about the analog circuitgridless routingalgorithms in this thesis. The contributions are as follows:Firstly, itpresents a new expanding tile structure in this thesis, which setsan arraycontains30vertices’ valuesthat represents the six expand direction information. Thesix expand directions are east, west, south, north, up and down. East, west, south andnorth has three directions information respectively. Up and down has nine directionsinformation respectively.Each expanding tile’s information includes the cost of therouting path, as well as the direction of the routing path search.It makes pointinformation more specific and makessearch target directioninformationclearer. Theprogress of the search to the target point can be optimized obviously.Secondly, depending on the new expanding tile structure, a new fastgridlessrouter is presented in this thesis. The new fast gridless router uses A*searchalgorithm that based on split graph data structure. This model aims atthe multiple endline networks, making sure the routing result’s corners, via and path are optimal.Thirdly, the routing method is presented in this thesis has advantage in searchadjacent tile and cost update than SIAR method. The new method can avoid that tilesare searched again and again. Some directions cannot be updated. These are noinformation about directions in tile, leading to the waste of routingresources.Wepresent the method of gridless routing aimed at improving theshortcomings of SIAR method in this thesis.The improved method avoids therepeated search about the unavailable direction.Also, the resource waste and routingof the running time is reduced, without reducing the quality of the routing results. Finally, the new method is suitable for the single and multilevel analog circuit.Inthe single analog circuit test cases,the new method is faster than SIAR method,andthe speed up ratio is between1.13x and2.07x. In the multilevel analog circuit testcases, it makes the speed-up ratio between1.06x and2.23x.Plenty of data showthatthe quantity of routing results’ corners, via, path length and path cost does not beincreased. So, the quality of routing result cannot be reduced by this new method.