ボロノイ線図を用いたLSI設計における一割当アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1989-01-25
• タイトル: ボロノイ線図を用いたLSI設計における一割当アルゴリズム
• タイトル / 言語: en
• タイトル: An Assignment Algorithm in VLSI Layout Design Using Voronoi Diagram
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 日本電気（株）C&Cシステム研究所
• 著者所属(英): en
• 著者所属(英): C&C Systems Research Labs, NEC Corp.
• 著者名: 枝廣, 正人
• 著者名(英): Masato, Edahiro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では、LSI設計におけるドライバーフリップフロップ割当て問題（DFA問題）に対する発見的アルゴリズムを提案する。DFA問題は、LSI特性向上、チップ面積削減のために重要である。DFA問題に対しては最小重み最大マッチング法を用いて解く方法が一般的であるが、最大マッチングの最適解が問題の最適解にならない場合がある、時間がかかる、などの欠点がある。本論文において提案するアルゴリズムにおいてはボロノイ線図を用いて最小森を求めた後、最短経路探索を繰返して解の改善を行なうことにより実行可能解を求めている。計算機実験の結果、1000点程度の問題を1分以内で解くことができることが確認された(NEC EWS4800/10)。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper presents a new algorithm for the driver-flip-flop reassignment problem after the placement of the semi-custom layout design. This algorithm, by using the Voronoi diagram, is quite efficient and gives a better solution than the existing techniques. The efficiency and quality of the solution are shown in experimental results.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1989, 号 8(1988-AL-005), p. 147-154, 発行日 1989-01-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会