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

基于多处理器的 VLSI（超大规模集成）布局算法

• 批准号: 8701369
• 负责人: Rob Rutenbar
• 金额: $ 9.7万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-07-01 至 1989-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8701369&HistoricalAwards=false
• 关键词: Multiprocessor; Based; VLSI; Very; Large

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.

Rutenbar 博士将研究 VLSI 设计布局任务，这些任务可以构建为组合优化问题，并通过并行模拟退火算法来解决。 两种类型的多处理器正在变得可用：共享内存和分布式内存机器。 该研究将考虑在分布式内存机器上运行并行算法。 这是因为共享内存机器中的并行模拟退火在概念上往往更容易，并且比分布式内存机器中受到更多关注。 该研究将建立在首席研究员最近构建的可操作平面图的基础上。它将成为测试算法分解和不同风格的并行模拟退火新想法的工具。 这项工作将经过仔细的检测和测量，以识别和量化对加速和解决方案质量的重要影响。 在实验和测量阶段之后，主要研究人员将开发不同类型的并行性如何影响加速和解决方案质量的模型。 目标是获得有关并行模拟退火的足够知识，以便合理控制应用于一系列 VLSI 设计问题的过程。 超大规模集成（VLSI/ULSI）电路设计已成为研究界强烈关注的话题以及工程师和科学家的实际兴趣。 这项研究解决了 ULSI 电路设计运行复杂设计算法的需求。 随着此类设备变得越来越复杂并且行业竞争越来越激烈，这一需求变得至关重要。 为了在合理的时间内完成此任务，有必要考虑在并行计算机上运行设计软件的加速。 这需要开发在并行机器上高效运行的新算法。 在并行机上运行算法的通用方法称为“模拟退火”。 该方法虽然概念上很简单，但对于 VLSI/ULSI 设计算法没有明显的实现。首席研究员在这一领域取得了重要的概念进展，并将在他的研究中进一步将其发展到实践中。