A study on VLSI layout methods based on meta-heuristics

基于元启发式的VLSI布局方法研究

• 批准号: 05680274
• 负责人: WAKABAYASHI Shinichi
• 金额: $ 1.15万
• 依托单位: HIROSHIMA UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1993
• 资助国家: 日本
• 起止时间: 1993 至 1994
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-05680274/
• 关键词: Meta-heuristics; VLSI; Layout design; Floorplan Design; Cell placement; Global routing; Channel routing; Genetic algorithm; 配置設計; 配線設計; ヒューリスティックアルゴリズム; 組合せ問題; VLSIレイアウト設計; シミュレーティドアニーリング; スタンダードセル

In this research, we have studied the VLSI layout design methods based on meta-heuristics. For all algorithms developed in this research, we have performed simulations experiments to show their effectiveness. Summaries of the research results are as follows.1.Hypergraph partitioning algorithms : We have developed algorithms for the hypergraph partitioning problem, which is one of the fundamental problems in VLSI layout design. In the proposed algorithms, clustering of nodes is performed to get a good solution.2.A floorplanning method based on topological constraint manipulation : For the floorplan design of VLSI chips, we have developed a floorplanning algorithm, in which topological constraints of block placement arre dynamically changed.3.Cell placement algorithms : We have developed two cell placement algorithms, one of which is based on genetic algorithms, and the other is a timing-driven cell placement algorithm.4.Global routing methods : We have developed two global routing methods for standard cell layouts, whose objective is to minimize both the channel density and the total wire length.5.Over-the-cell channel routing methods : We have proposed new cell models for standard cell layout design with over-the-cell three-layr channel routing, and developed channel routing algorithms.

本研究主要研究基于元逻辑的超大规模集成电路版图设计方法。对于本研究中开发的所有算法，我们都进行了模拟实验，以显示其有效性。主要研究成果如下：1.超图划分算法：针对超大规模集成电路版图设计中的基本问题之一超图划分问题，提出了超图划分算法。2.一种基于拓扑约束操作的布图规划方法：针对超大规模集成电路芯片的布图规划设计，提出了一种动态改变块布局拓扑约束的布图规划算法。3.单元布局算法：我们开发了两种单元布局算法，一种是基于遗传算法的，另一种是时序驱动的单元布局算法。4.全局布线方法：我们开发了两种用于标准单元布局的全局布线方法，其目标是最小化通道密度和总布线长度。5.单元上通道布线方法：我们提出了新的单元模型的标准单元布局设计与over-the-cell三层通道布线，并开发了通道布线算法。

项目成果

S.Wakabayashi: "Gate Array Placement Based on Mincut Partitioning with Path Delay Constraints" Proc.International Symposium on Circuits and Systems. 3. 2059-2062 (1993)

S.Wakabayashi：“基于具有路径延迟约束的最小切割分区的门阵列布局”Proc.International Symposium on Circuits and Systems。

Yoko Kamidoi: "On three-way graph partitioning" Proc.1994 IEEE ISCAS. Vol.5. 173-176 (1994)

Yoko Kamidoi：“关于三向图分区”Proc.1994 IEEE ISCAS。

Tetsushi Koide: "Three-layer channel routing for standard cells with column-dependent variable over-the-cell routing capacities" Proc.1994 IEEE CICC. 643-646 (1994)

Tetsushi Koide：“具有列相关变量跨单元路由能力的标准单元的三层通道路由”Proc.1994 IEEE CICC。

Shin'ichi Wakabayashi: "Gate array placement based on mincut partitioning with path delay constraints" Proc.1993 IEEE ISCAS. Vol.3. 2059-2062 (1993)

Shinichi Wakabayashi：“基于具有路径延迟约束的最小切割分区的门阵列放置”Proc.1993 IEEE ISCAS。

Kazunori Isomoto: "A graph bisection algorithm based on subgraph migration" IEICE Trans.Fundamentals of Electnonics,Communications,and Computer Scierces. E77-A. 2039-2044 (1994)

Kazunori Isomoto：“基于子图迁移的图平分算法”IEICE Trans.Fundamentals of Elecnonics、Communications 和 Computer Science。