ネットワークフローアルゴリズムを用いた遅延改善手法

スポンサーリンク

概要

論文の詳細を見る
大規模回路の遅延を改善する新しい手法を提案する。これは、回路に"paddingノード"をクリティカルでないエッジに挿入する。そして、ネットワークフローアルゴリズムで分離集合を求め、回路に適用すべき局所変換の最良の集合を見つける。この手法は、メモリ使用量と計算時間が、それぞれ、回路サイズに対して線形、多項式オーダになるため、大規模回路の遅延最適化に適している。本手法と"選択関数"を用いるK. J. Singh法との比較実験を行った。本手法は適用した全ての回路について最適化できたのに対し、Singh法は3つの回路についてメモリ不足で最適化できなかった。また、遅延改善能力は両手法で同じ程度であった。
社団法人電子情報通信学会の論文
1999-06-11

著者

田宮豊
(株)富士通研究所

関連論文

もっと見る

スポンサーリンク