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设计实现 算法首席研究员已经提出了重要的概念 在这方面取得的进展，并将进一步发展他们的实践， 他的研究。