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设计算法没有明显的实现。首席研究人员在这一领域取得了重要的概念进步，并将进一步发展其研究中的实践。