Multiprocessor-Based VLSI (Very Large Scale Integrated) Layout Algorithms

点击翻译按钮获取中文摘要

Dr. Rutenbar will investigate VLSI design layout tasks that can be structured as combinatorial optimization problems and solved with parallel simulated annealing algorithms. Two sorts of multi-processors are becoming available: shared memory and distributed memory machines. The research will consider running parallel algorithms on distributed memory machines. This is because parallel simulated annealing in shared memory machines tends to be conceptually easier and has received more attention than in distributed memory machines. The research will build on an operational floor-planner, which the principal investigator has recently built. It will be the vehicle for testing new ideas for algorithm decompositions and different styles of parallel simulated annealing. This work will be carefully instrumented and measured to identify and quantify important effects on speedup and solution quality. After the experimentation and measurement phase, the principal investigator will develop models of how speedup and solution quality are effected by different styles of parallelism. The goal is to gain sufficient knowledge of parallel simulated annealing in general to permit reasonable control of the process applied to a range of VLSI design problems. Very and ultra large scale integrated (VLSI/ULSI) circuit design has become a topic of intense interest in the research community and practical interest to engineers and scientists. This research addresses the need to run sophisticated design algorithms for ULSI circuit design. It is a need that has become of paramount importance as such devices become increasingly complex and the industry more competitive. To do this in a reasonable amount of time, it is necessary to consider the speedup that running the design software on parallel computers. This entails development of new algorithms which run efficiently on parallel machines. A general method for running algorithms on parallel machines is called "simulated annealing". This method, while conceptually simple, does not have obvious implementations for VLSI/ULSI design algorithms. The principal investigator has made important conceptual advances in this area and will further develop them toward practice in his research.