| Item type |
SIG Technical Reports(1) |
| 公開日 |
2018-12-10 |
| タイトル |
|
|
タイトル |
MPI/OpenMP並列によるグラフ対称性とSimulated Annealingを用いたOrder/Degree問題の一解法 |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
最適化問題 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
理化学研究所計算科学研究センター |
| 著者所属 |
|
|
|
理化学研究所計算科学研究センター |
| 著者所属 |
|
|
|
理化学研究所計算科学研究センター |
| 著者所属(英) |
|
|
|
en |
|
|
RIKEN Center for Computational Science |
| 著者所属(英) |
|
|
|
en |
|
|
RIKEN Center for Computational Science |
| 著者所属(英) |
|
|
|
en |
|
|
RIKEN Center for Computational Science |
| 著者名 |
中尾, 昌広
村井, 均
佐藤, 三久
|
| 著者名(英) |
Masahiro, Nakao
Hitoshi, Murai
Mitsuhisa, Sato
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
大規模システム内における各要素間を接続するネットワークのトポロジは，システム全体の通信遅延に強く関係していることが知られている．通信遅延が小さいネットワークトポロジを設計することは，そのネットワークトポロジを無向グラフとしてモデル化することで，グラフ理論上の Order / Degree 問題として定義できる．本稿では，Simulated Annealing （SA） をベースにした Order / Degree 問題を効率良く解くことができる手法を提案する．本手法は，ネットワークのトポロジに対称性を持たせることにより SA の解探索性能を高め，また計算時間を大幅に削減している．Order / Degree 問題のための国際コンペティションである Graph Golf で出題されているいくつかの問題に対して本手法を適用した結果，通信遅延の十分小さいネットワークトポロジを発見した．また，その対称性を利用した計算時間の削減手法を用いることで，Graph Golf が出題している (n，d) = (72，4)，(256，5)，(256，10) の問題において，それぞれ 8.11 倍，31.76 倍，15.67 倍の高速化を達成した．さらに，MPI と OpenMP を用いたハイブリッド並列化を行うことにより，さらなる計算時間の削減を行った．その結果，Graph Golf が出題している (n，d) = (400000，32) の問題において，最大 209.80 倍の性能向上を達成した．また，トポロジの対称性とハイブリッド並列化を組合せることにより，その問題においては最大 2,098,000 倍の高速化を達成できたと考えられる． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN10463942 |
| 書誌情報 |
研究報告ハイパフォーマンスコンピューティング（HPC）
巻 2018-HPC-167,
号 23,
p. 1-11,
発行日 2018-12-10
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8841 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-HPC18167023.pdf (1.8 MB)
