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

This project implement a algonthm 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 algonthm 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 algonthm is used to search for optimal chairung 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 denved This bound enables us to prune the search tree efficiently The algonthm will be implemented and tested in this project using C language The result will be compared with euler's path algonthm using heuristic search and a pseudo input to find the minimum mterlace