New methods for electronic design automation problems

Wu, Pei-Ci

Permalink

https://hdl.handle.net/2142/78447 Copy

Description

Title

New methods for electronic design automation problems

Author(s)

Wu, Pei-Ci

Issue Date

2015-04-22

Director of Research (if dissertation) or Advisor (if thesis)

Wong, Martin D.F.

Doctoral Committee Chair(s)

Wong, Martin D.F.

Committee Member(s)

• Chen, Deming
• Hwu, Wen-Mei W.
• Rutenbar, Robin A.

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

As the semiconductor technology marches towards the 14nm node and beyond, EDA (electronic design automation) has rapidly increased in importance with ever more complicated modern integration circuit (IC) designs. This presents many new issues for EDA including design, manufacturing, and packaging. Challenging EDA problems in these three domains are studied in this dissertation. Timing closure, which aims to satisfy the timing constraints, is always a key problem in the physical design flow. The challenges of timing closure for IC designs keep increasing as the technology advances. During the timing optimization process, buffers can be used to speed up the circuit or serve as delay elements. In this dissertation, we study the hold-violation removal problem for a circuit-level design. Considering the challenges of industrial designs, discrete buffer sizes, accurate timing models/analysis and complex timing 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 incorporated into to the state-of-the-art industrial optimization flow. While buffers can help fix hold-time violations, they also increase the difficulty of routability and the utilization of a design. And the larger area of cells contributes larger leakage power, while power is an increasing challenge as the technology advances. Therefore, in Chapter 3, we study the buffer insertion problem that is to find which buffers to be inserted in order to meet the timing constraints, meanwhile minimizing the total area of inserted buffers. Several approaches are presented. We test the proposed approaches on the industrial designs, and the machine learning based approach shows better results in terms of quality and runtime. Aerial image simulation is a fundamental problem in the regular lithographyrelated process. Since it requires a huge amount of mathematical computation, an efficient yet accurate implementation becomes a necessity. In the literature, GPU or FPGA has successfully demonstrated its potential with detailed tuning for accelerating aerial image simulation. However, the advantages of GPU or FPGA to CPU are not solid enough, given that the careful tuning for the CPU-based method is missing in the previous works, while the recent CPU architectures have significant modifications towards high performance computing capabilities. In this dissertation, we present and discuss several algorithms for the aerial image simulation on multi-core SIMD CPU. Our experimental results show that the performance on the multi-core SIMD CPU is promising, and careful CPU tuning is necessary in order to exploit its computing capabilities. Since the constantly evolving technology continues to push the complexity of package and printed circuit board (PCB) design to a higher level, nowadays a modern package can contain thousands of pins. On the other hand, the size of a package is still kept to a minimum. This makes the footprint of such a package on a PCB a very dense pin grid, such that staggered pin arrays have been introduced for modern designs with high pin density. Although some studies have been done on escape routing for hexagonal arrays, the hexagonal array is only a special kind of staggered pin array. There exist other kinds of staggered pin arrays in current industrial designs, and the existing works cannot be extended to solve them. In this dissertation, we study the escape routing problem on staggered pin arrays. Network flow models are proposed to correctly model staggered pin arrays, and our proposed algorithm is proved optimal. The high complexity of PCB design makes the manual design of PCBs an extremely time-consuming and error-prone task. An auto-router for PCBs would improve design productivity tremendously since each board takes about 2 months to route manually. This dissertation focuses on a major step in PCB routing called bus planning. In the bus planning problem, we need to simultaneously solve the bus decomposition, escape routing, layer assignment and global bus routing. This problem was only partially addressed by Kong et al. (2009). In this dissertation, we present an ILP-based solution to the entire bus planning problem. We apply our bus planner to an industrial PCB (with over 7000 nets and 12 signal layers) which was previously successfully routed manually, and compare with a state-of-the-art industrial internal tool where the layer assignment and global bus routing are based on the algorithm prosed by Kong et al. (2009). Experimental results show that our bus planner successfully achieves better routability.

Graduation Semester

2015-5

Type of Resource

text

Permalink

http://hdl.handle.net/2142/78447

Copyright and License Information

Copyright 2015 Pei-Ci Wu

Owning Collections