Routability Estimation And Routing Algorithm For Analog Circuits

With the rapid development of integrated circuits, analog and mixed signalcircuits is gaining more portions in system on chips. However, due to the complexityof design constraints, analog circuits’s design automation technology has notdeveloped as quickly as for digital circuits. Thus, analog circuits design automationhas become the bottleneck for the whole design flow of SoCs. Placement and routingare the two most important steps in the design automation process.In digital circuits,placement solution has great impact on the following routing quality. In analogcircuits,routing is not allowed on top of the placed active devices.The placementsolution has even more impact on the following routing process.In digital circuits,congestion estimation methods are performed to guide the placement optimizationprocess. For analog placement process, due to the smaller circuit size, more accurateestimation, i.e., routability estimation, is possible.A gridless router system be designed and implemented in this thesis.The systemis based on the implicit-connection graph and solve the problem of analog automaticrouting. This thesis presents routability estimation model to guide the analogplacement optimization process. The main contributions are as follows:A gridless router system is designed and implemented. The router is based on theimplicit connection graph. A*heuristic algorithm be used for searching routingpath. Firstly，multipin nets are decomposed into several two-pin subnets by usingthe minimum spanning tree algorithm.Secondly, The implicit connection graph isconstructed by extending the borderlines of each obstacle to routingboundaries.Again,A*heuristic algorithm is adopted to search the path of subnetsin the routing map.Finally,the result of routing become visualization by usingGTK language.Experiment shows that the completion rate of routing reach99%and above.Aroutability estimation model for analog circuits is proposed. The innovations ofthe model are as follows:1)The routing demand and obstacles demand areestimated.A weights quantitatively estimate the congestion of routing area.2) Adynamic pattern routing (DPR) algorithm is adopted to predict the possiblerouting path of subnets. Compared with L-shape or Z-shape Pattern routing algorithm, this approach can explore patterns with more than two bends underminimal congestion aware.The algorithm is more efficient and accurate.Theapproach predict subnets’s the possible routing path,which in line with therouting path of the actual router.3) The horizontal/vertical expansion algorithmand angle expansion algorithm are proposed. The DPR algorithm search thepossible routing path of subnets in the expanded Bounding-Box. According to thecongestion weights determine whether the subnet can be routed.Then, theroutability of the placement solution be obtained.Experiment shows that thismodel accurately estimate the routability.