グラフをk分割する並列アルゴリズム

磯本 和典  若林 真一  宮尾 淳一  吉田 典可  

誌名
電子情報通信学会論文誌 A   Vol.J75-A   No.6   pp.1064-1071
発行日: 1992/06/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: アルゴリズムとデータ構造,計算複雑度
キーワード: 
グラフk分割,  並列アルゴリズム,  ヒューリスティックアルゴリズム,  VLSIレイアウト設計,  

本文: PDF(554.1KB)>>
論文を購入




あらまし: 
近年の半導体集積化技術の発達により,VLSIレイアウト設計で取り扱うデータの量が格段に増加しつつある.従って,今後の計算機の処理速度の向上を見込んでも,従来手法よりも高速なレイアウトアルゴリズムの開発が要求されている.本論文では,レイアウト設計に関する最も基本的な問題の一つであるグラフのk(>2)分割問題について考察し,並列アルゴリズムを提案する.この問題の解き方としては,グラフ2分割アルゴリズムを階層的に繰り返し適用する手法が一般的である.この手法では各階層において複数のプロセッサを稼動させることにより容易に並列化できるが,プロセッサの稼動率や計算時間の面で問題がある.本論文ではグラフのk分割に対し,並列処理による計算時間の削減を目的として非階層的k分割手法と呼ぶ手法を新たに提案する.一般に,得られる解の精度を逐次アルゴリズムによるものと同程度に保ったままで,並列化による十分な速度向上率を達成することは難しいと考えられる.本論文では逐次型計算機上におけるシミュレーション実験によって提案したアルゴリズムの有効性を示す.