Synthesis of transistor-chaining algorithm for CMOS cell layout using bipartite graph / Azizi Misnan

This project implement a algorithm for the optimal transistor chaining problem in CMOS functional cell layout based on Uehara and vanCleemput's layout style [1] which assumed that the height of each logic module layout is constant and performed the optimisation by decomposing the graph module into a minimum number of sub graph having a dual Euler (d-Euler) trail.. The algorithm takes a transistor level circuit schematic and the outputs a minimum set of chains. Searching for possible abutment between the transistor pairs are modelled as a bipartite graph. A depth - first search algorithm is used to search for optimal chaining. Theorems on number of branches needed to be explored at each node of search tree are derived. A theoretical lower bound on the size of the chain set is derived. This bound enables us to prune the search tree efficiently. The algorithm will be implemented and tested in this project using C language. The result will be compared with euler's path algorithm using heuristic search and a pseudo input to find the minimum interlace.