Topological placement with symmetry constraints for analog layout design

In recent years, complete systems that used to occupy one or more boards have been integrated on a few chips or even on a, single chip. Although most functions in such integrated systems are implemented with digital or digital signal processing circuitry, the analog circuits needed at the interface between the electronic system and the real world are now being integrated on the same die for reasons of cost and performance.; In the digital domain, computer-aided design (CAD) tools are fairly well developed, especially for the lower level of the design flow. Unfortunately, the situation is worse on the analog side. Apart from circuit simulators, layout editing environments, or layout verification tools, real commercial solutions are only beginning to appear. This thesis addresses the problem of device-level placement with symmetry constraints in analog blocks. Different from the traditional way of approaching the analog placement problems, that is, the exploration of an extremely large set of absolute representations of both feasible and unfeasible placement configurations, this thesis advocates the use of subsets of non-slicing topological representations, such that the typical presence of an arbitrary number of symmetry groups of devices be directly taken into account during the search of the solution space.; The thesis introduces the concepts of symmetric-feasible sequence-pairs and symmetric-feasible binary tree representations of the layout, discusses the advantages offered by the exploration of these subsets of topological representations---like the significant reduction in size of the solution space of analog placement problems with symmetry constraints. Three evaluation algorithms of complexity O (n log n) using less used data structures---the segment trees and deterministic skip lists---are presented and thoroughly analyzed.; A prototype placement tool for analog layout using alternative exploration algorithms is presented in the thesis. The tool can operate both with different topological representations (sequence-pairs and trees) and different, code evaluation algorithms.; The computation times exhibited by this novel approach are significantly better than those of the algorithms using the traditional exploration strategy, while generating high-quality placement solutions.