New approaches for placement and benchmarking of CMOS and gene chips

The importance of component placement, for both Complementary Metal Oxide Semiconductor (CMOS) chip and Gene chip (or DNA array) technologies, cannot be underestimated. Placement determines (a) the physical performance of Very Large Scale Integration (VLSI) CMOS circuits, and (b) the level of integration and fidelity of Gene chips. Benchmarking is concerned with calculating the gap between the result of a suboptimal algorithm and the result of the (generally unachievable) optimal algorithm. Any calculated difference fuels continued attention to the given problem. In the framework of placement and benchmarking, this thesis is concerned with two central questions. (1) Are current placement algorithms optimal (or "near" optimal) with respect to realistic CMOS and Gene chip instances? And (2) If question (1) is answered negatively, how can the performance of placement algorithms be improved?; In the context of CMOS chips, this thesis proposes a new approach, zero-change netlist transformations (ZCNT), for placement benchmarking. ZCNT answers question (1) negatively, and proves, for the first time, that placers display significant suboptimal behavior (by up to 22%) for circuit instances that are realistic. This is in contrast to previous approaches which gave results on highly artificial circuit topologies or reported loose lower bounds. Then in answer to question (2), this thesis proposes a new placement technique, placement feedback, which improves top-down placement frameworks. Implementing the proposed technique in the open-source placer Capo yields placements with up to 15% improvement in wirelength.; In the context of Gene chips, this thesis proposes a number of benchmarking methods, including calculation of placement lower bounds and construction of chips with known optimal (and suboptimal) placements. The proposed bench marking methods answer question (1) negatively by proving that current Gene chip placement algorithms are suboptimal by about 42%. Having answered question (1) negatively, the thesis answers question (2) by proposing a number of new placement approaches---constructive and iterative in nature---that improve upon current algorithmic approaches. The effectiveness of the proposed approaches is demonstrated by providing placements for academic chips and for an industrial Human Genome chip that are better than previous approaches by 18% and 6% respectively.