Japan Advanced Institute of Science and Technology
JAIST Repository
https://dspace.jaist.ac.jp/
Title 埋め込みパターンとその関連操作に基づくグラフ埋め
込み最適化
Author(s) 佐藤, 円
Citation
Issue Date 2010‑03
Type Thesis or Dissertation Text version author
URL http://hdl.handle.net/10119/8948 Rights
Description Supervisor:金子 峰雄, 情報科学研究科, 修士
埋め込みパターンとその関連操作に基づく グラフ埋め込み最適化
佐藤 円(0810029)
北陸先端科学技術大学院大学 情報科学研究科 2010年2月9日
キーワード: 並列計算機相互結合網, グラフ埋め込み問題, パターン，メッシュグラフ.
本論文は，並列計算機の相互結合網と並列計算プログラムのタスク割り当てに対するグ ラフ埋め込み問題について述べている．並列プログラムの設計において，並列計算時に利 用したい並列計算機の持つ相互結合網の構造に合わせ，設計者が明示的に設計を行うこと がある．このように設計された並列プログラムは，ある相互結合網用に計算アルゴリズム を割り当てて設計されているため，指定の並列計算機上では高速に実行されるが，それ以 外の相互結合網上では一般には使用できないか非常に性能の悪いものになる．
そこで，実際に計算で使用する並列計算機をその各PEをグラフの頂点，通信路を辺と したホストグラフHにて表現し，一方，プログラムモデルのタスクを頂点，タスク間の関 係を辺としたゲストグラフGとしてグラフモデル化し，Gの頂点や辺をHの頂点や辺に割 り当てるグラフ埋め込みが重要な役割を果たすことになる．特に，実際の性能と対応する グラフ上での指標であるedge-congestionやdilation（通信遅延の下界），vertex-congestion
（各PEにタスクがどれだけ割り当てられているか），expansion（相互結合網中でタスク がどれだけの割合を占めるか）などの最適化が求められている．
このようなグラフ埋め込み問題の議論として従来研究では，(1)特定のグラフトポロジー に特化した埋め込みの議論が多く，また，(2)その解は専ら専門家の経験等に基づいた発 見に委ねられている．現実への応用問題として，グラフ埋め込み問題にはグラフトポロ ジーの多様性やサイズや境界形状にも多様性があり，より現実的なグラフ埋め込み問題に 解を与えるために，その実行可能解や最適解を専門家による発見ではなく，ある定まった 計算アルゴリズムによって生成する手法の確立は非常に重要なものと考えられるが，固有 のグラフトポロジーに特化した従来のグラフ埋め込みの議論では，そうした議論はほとん ど見られない．実行可能解や最適解の探索として，原理的には関数ΦV :V(G)−→V(H) やΦE : E(G) −→ P(H) を列挙しつつ探索することが考えられるが，このとき，頂点の 重複を許せば|V(H)||V(G)|，重複を許さないとしても|V(H)|!/(|V(H)| − |V(G)|)!の解空 間サイズとなり，大きな|V(G)|に対してそのまま適用することは難しい．
Copyright c⃝2010 by Madoka Satou
1
本研究では，相互結合網や並列プログラムのグラフトポロジーが規則的であることに着 目し，グラフ埋め込みをゲストグラフの各頂点の写像として取り扱うよりも，よりマクロ 的な扱いを導入することによって探索を大幅に効率化することを考え，その初期段階とし て本論文では，メッシュ形の規則的構造を持つグラフを対象として，パターン埋め込みを 提案し，また，こうしたマクロ的な取り扱いでも多様性に富む解を生成可能にするため に，パターン埋め込みに関連するいくつかの操作について検討・提案を行っている．
ゲストグラフG，ホストグラフH共に想定するメッシュグラフは，(1)有限個の種類の 辺にてグラフが特徴づけられ，1つの頂点とそれに接続する各種類の辺1つずつおよびそ れらの辺の他端点から成る単位部分グラフが，グラフ境界部の頂点を除いてその他全て の頂点について共通であり，(2)どの頂点から見ても，グラフの境界外を除いてグラフ構 造が等しい（移動不変性）性質を持っている．初めに，ゲストグラフGにおける(1)の性 質とホストグラフHにおける(2)の性質より，単位部分グラフの埋め込みをGの構造に 従って繰り返すことが可能であり，これをパターン埋め込みと定義する．1つのパターン 埋め込みは，頂点数に関わりなく辺の種類数だけの辺埋め込みによって規定されることに なる．次に，こうしたパターン埋め込みを複数組み合わせることによって，より複雑でか つ柔軟性のある解を生成するためのパターン切り替えを導入し，その切り替えがゲストグ ラフGの構造を保つための条件を明確にした．また複数のパターン埋め込みが頂点を共 有しないための条件についても明らかにし，特にパターン埋め込みがホストグラフ上を折 り返る際の実行可能なパターン切り替えの条件を明確化している．これにより，現段階で はメッシュグラフに対してのみに限定されるが，グラフ埋め込みに対し，現実問題に即し た多様性に富んだ埋め込み解を得るための枠組みを作ることができた．
今回提案したパターン埋め込みは，パターン自体や切り替え・重ね合わせ操作の組み合 わせと切り替える場所によって，さまざまな解が得られるという特徴がある．その一方，
最適な埋め込みを求めるためのパターンの選択，パターン切り替え場所の選択等の具体的 な探索手法については今後の課題となっている．また，本論文で示したパターン埋め込み はメッシュ形グラフを対象とした議論に止まっており，メッシュ構造からより広いグラフ クラスへの議論を行うために，パターンという枠組みを更に拡張することが大きな課題と なっている．
2
