This research addresses some critical challenges in various problems of VLSI design
automation, including sophisticated solution search on DAG topology, simultaneous
multi-stage design optimization, optimization on multi-scenario and multi-core
designs, and GPU-based parallel computing for runtime acceleration.
Discrete optimization for VLSI design automation problems is often quite complex,
due to the inconsistency and interference between solutions on reconvergent
paths in directed acyclic graph (DAG). This research proposes a systematic solution
search guided by a global view of the solution space. The key idea of the proposal
is joint relaxation and restriction (JRR), which is similar in spirit to mathematical
relaxation techniques, such as Lagrangian relaxation. Here, the relaxation and
restriction together provides a global view, and iteratively improves the solution.
Traditionally, circuit optimization is carried out in a sequence of separate optimization
stages. The problem with sequential optimization is that the best solution
in one stage may be worse for another. To overcome this difficulty, we take the approach
of performing multiple optimization techniques simultaneously. By searching
in the combined solution space of multiple optimization techniques, a broader view
of the problem leads to the overall better optimization result. This research takes
this approach on two problems, namely, simultaneous technology mapping and cell placement, and simultaneous gate sizing and threshold voltage assignment.
Modern processors have multiple working modes, which trade off between power
consumption and performance, or to maintain certain performance level in a powerefficient
way. As a result, the design of a circuit needs to accommodate different
scenarios, such as different supply voltage settings. This research deals with this
multi-scenario optimization problem with Lagrangian relaxation technique. Multiple
scenarios are taken care of simultaneously through the balance by Lagrangian multipliers.
Similarly, multiple objective and constraints are simultaneously dealt with by
Lagrangian relaxation. This research proposed a new method to calculate the subgradients
of the Lagrangian function, and solve the Lagrangian dual problem more
effectively.
Multi-core architecture also poses new problems and challenges to design automation.
For example, multiple cores on the same chip may have identical design
in some part, while differ from each other in the rest. In the case of buffer insertion,
the identical part have to be carefully optimized for all the cores with different
environmental parameters. This problem has much higher complexity compared to
buffer insertion on single cores. This research proposes an algorithm that optimizes
the buffering solution for multiple cores simultaneously, based on critical component
analysis.
Under the intensifying time-to-market pressure, circuit optimization not only
needs to find high quality solutions, but also has to come up with the result fast.
Recent advance in general purpose graphics processing unit (GPGPU) technology
provides massive parallel computing power. This research turns the complex computation
task of circuit optimization into many subtasks processed by parallel threads.
The proposed task partitioning and scheduling methods take advantage of the GPU
computing power, achieve significant speedup without sacrifice on the solution quality.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2010-05-7770 |
| Date | 2010 May 1900 |
| Creators | Liu, Yifang |
| Contributors | Hu, Jiang |
| Source Sets | Texas A and M University |
| Language | English |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | application/pdf |
Page generated in 0.0022 seconds