Methods for Solving Modern, Scale-Borne Problems in VLSI Physical Design

Date
2012-10-01
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The 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.
Description
Keywords
Engineering--Electronics and Electrical
Citation
Rakai, L. (2012). Methods for Solving Modern, Scale-Borne Problems in VLSI Physical Design (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/26895