TCG-Based placement design handling complex topological constraints for integrated circuit layouts

In modern VLSI design, extensive research has shown that automated analog layout generation is a nontrivial process in the analog and mixed-signal circuitry synthesis. The main contribution of this thesis is successful development of a method, which is able to handle complex multi-group symmetry, substrate sharing, and other topological constraints in the analog and mixed-signal layout placement design using transitive closure graph (TCG) representation. -- This thesis proposes a set of symmetric-feasible conditions, which can guarantee symmetric placement of sensitive cells with respect to one or multiple symmetry axes for reduction of parasitic mismatch and thermal gradients. A new contour-based packing scheme has been developed with the time complexity of O(p･n･lgn), where p is the number of the symmetry groups and n is the number of the placed cells. Furthermore, a set of perturbation operations is devised with the time complexity of O(n), where n is the number of the placed cells, in order to generate a random symmetric-feasible TCG state from an existing one. The experimental results show the effectiveness and superiority of this proposed scheme compared to the other state-of-the-art placement algorithms for analog layout designs. -- In addition, the proposed method is able to handle the substrate sharing constraints which require the devices to be placed adjacent to share a common substrate in order to decrease the effect of substrate coupling. To the best of the author's knowledge, this is the first proposed approach to handle the substrate sharing constraints based on topological representations. Other topological constraints such as relationship, abutment and alignment can also be handled by our method. -- The thesis first presents a brief introduction to the analog design, including electronic design automation, analog synthesis, and analog placement. The previous important works, which intended to solve the analog placement problem, are thoroughly surveyed and analyzed. Secondly the TCG-based method to handle complex analog layout constraints such as symmetry, substrate sharing and other requirements is detailed and the corresponding algorithm complexity is analyzed. Finally the performance of the proposed method is compared with the other alternatives and the conclusions are drawn