Behjat, LalehRakai, Logan2012-10-012012-11-132012-10-012012http://hdl.handle.net/11023/253The design automation community is confronted with new challenges every technology node. Many of the challenges are borne out of issues relating to scale, be it the very small or the very large. For example, the extremely large scale of the number of instances in modern designs creates challenges in effectively exploring vast solution spaces in reasonable amounts of time. At the other end of the scale spectrum, the extremely small scale of features created by modern lithography processes are highly susceptible to process variations which affect performance and yield. This thesis deals with the development of methods for solving scale-borne problems in the physical design of integrated circuits. This thesis addresses challenges faced in two important phases of physical design: placement and clock network synthesis. The importance of these two phases is reflected in the fact that they have been the subject of five out of the last seven ACM/IEEE International Symposium on Physical Design (ISPD) contests. The number of instances and the size of the solution space in performing placement are truly immense. A proven linear-time clustering algorithm is proposed to deal with the explosion of problem sizes being encountered. Several extensions to the algorithm are proposed to further improve the quality of results. The number of instances in clock network design is also growing at a rapid pace. In order to cope with this challenge, a generic framework to parallelize algorithms that perform the main stages of clock network synthesis is proposed. Theorems are provided to prove asymptotically optimal speedup when the framework is applied to several classes of algorithms. Another challenge addressed regarding clock network synthesis is that of variation. A method is proposed for handling variations in lengths and widths of buffers and interconnects, that arise from the manufacturing process.engUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.Engineering--Electronics and ElectricalComputer-aided designParallel algorithmsRobust OptimizationClusteringdoctoral thesis10.11575/PRISM/26895