New methods for electronic design automation problems

Electronic Design Automation (EDA);Timing Closure;Buffer Insertion;Aerial Image Simulation;Escape Routing;Bus Planner

Wu, Pei-Ci

关键词: Electronic Design Automation (EDA);    Timing Closure;    Buffer Insertion;    Aerial Image Simulation;    Escape Routing;    Bus Planner;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/78447/WU-DISSERTATION-2015.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

As the semiconductor technology marches towards the 14nm node and beyond,EDA (electronic design automation) has rapidly increased in importancewith ever more complicated modern integration circuit (IC) designs.This presents many new issues for EDA including design, manufacturing, andpackaging. Challenging EDA problems in these three domains are studied inthis dissertation.Timing closure, which aims to satisfy the timing constraints, is always akey problem in the physical design flow. The challenges of timing closure forIC designs keep increasing as the technology advances. During the timingoptimization process, buffers can be used to speed up the circuit or serveas delay elements. In this dissertation, we study the hold-violation removalproblem for a circuit-level design. Considering the challenges of industrialdesigns, discrete buffer sizes, accurate timing models/analysis and complextiming constraints make the problem difficult and time-consuming to solve.In this dissertation, a linear programming-based methodology is presented.In the experiment, our approach is tested on industrial designs, and is incorporatedinto to the state-of-the-art industrial optimization flow.While buffers can help fix hold-time violations, they also increase the difficultyof routability and the utilization of a design. And the larger area ofcells contributes larger leakage power, while power is an increasing challengeas the technology advances. Therefore, in Chapter 3, we study the bufferinsertion problem that is to find which buffers to be inserted in order tomeet the timing constraints, meanwhile minimizing the total area of insertedbuffers. Several approaches are presented. We test the proposed approacheson the industrial designs, and the machine learning based approach showsbetter results in terms of quality and runtime.Aerial image simulation is a fundamental problem in the regular lithographyrelatedprocess. Since it requires a huge amount of mathematical computation, an efficient yet accurate implementation becomes a necessity. In theliterature, GPU or FPGA has successfully demonstrated its potential withdetailed tuning for accelerating aerial image simulation. However, the advantagesof GPU or FPGA to CPU are not solid enough, given that the carefultuning for the CPU-based method is missing in the previous works, while therecent CPU architectures have significant modifications towards high performancecomputing capabilities. In this dissertation, we present and discussseveral algorithms for the aerial image simulation on multi-core SIMD CPU.Our experimental results show that the performance on the multi-core SIMDCPU is promising, and careful CPU tuning is necessary in order to exploitits computing capabilities.Since the constantly evolving technology continues to push the complexityof package and printed circuit board (PCB) design to a higher level, nowadaysa modern package can contain thousands of pins. On the other hand, the sizeof a package is still kept to a minimum. This makes the footprint of such apackage on a PCB a very dense pin grid, such that staggered pin arrays havebeen introduced for modern designs with high pin density. Although somestudies have been done on escape routing for hexagonal arrays, the hexagonalarray is only a special kind of staggered pin array. There exist other kindsof staggered pin arrays in current industrial designs, and the existing workscannot be extended to solve them. In this dissertation, we study the escaperouting problem on staggered pin arrays. Network flow models are proposedto correctly model staggered pin arrays, and our proposed algorithm is provedoptimal.The high complexity of PCB design makes the manual design of PCBs anextremely time-consuming and error-prone task. An auto-router for PCBswould improve design productivity tremendously since each board takes about2 months to route manually. This dissertation focuses on a major step in PCBrouting called bus planning. In the bus planning problem, we need to simultaneouslysolve the bus decomposition, escape routing, layer assignment andglobal bus routing. This problem was only partially addressed by Kong etal. (2009). In this dissertation, we present an ILP-based solution to the entirebus planning problem. We apply our bus planner to an industrial PCB(with over 7000 nets and 12 signal layers) which was previously successfullyrouted manually, and compare with a state-of-the-art industrial internal toolwhere the layer assignment and global bus routing are based on the algorithm prosed by Kong et al. (2009). Experimental results show that our busplanner successfully achieves better routability.