WEKO3
アイテム
Order/Degree問題のための重みなしグラフにおける全点対間最短経路アルゴリズムの並列化
https://ipsj.ixsq.nii.ac.jp/records/199131
https://ipsj.ixsq.nii.ac.jp/records/19913177314ac4-8386-4c77-a69e-7a3eb29af2a2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-HPC19171010.pdf (2.3 MB)
|
Copyright (c) 2019 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2019-09-13 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 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 | ||||||||||||
| 著者名 |
中尾, 昌広
× 中尾, 昌広
× 村井, 均
× 佐藤, 三久
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | 大規模並列計算機システムのネットワークトポロジを設計することは，グラフ理論上の Order/Degree 問題として定義することができる．Order/Degree 問題を解く際には，グラフの特徴量の 1 つである全点対間最短経路 （APSP：All Pairs Shortest Path） を高速に求める必要がある．そこで本稿では，幅優先探索による APSPアルゴリズム （BFS-APSP） と隣接行列による APSP アルゴリズム （ADJ-APSP） の並列化および比較を行う．なお，本稿では重みなしグラフを対象とする．それぞれの逐次アルゴリズムおよび OpenMP を用いたスレッド並列アルゴリズムにおいては，ADJ-APSP の方が性能が高いことを示した．しかしながら，MPI を用いた並列アルゴリズムにおいては，MPI の最大並列数は BFS-APSP の方が ADJ-APSP よりも多いため，BFS-APSP の方が性能が高くなる場合があることを示した．さらに，ADJ-APSP について GPU を用いた並列化を行うことにより，CPU よりも最大 16.53 倍の性能向上を達成した．また，対称性を持つグラフに対して各 APSP アルゴリズムを適用させることで，計算時間を大幅に短縮できることを示した． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN10463942 | |||||||||||
| 書誌情報 |
研究報告ハイパフォーマンスコンピューティング（HPC） 巻 2019-HPC-171, 号 10, p. 1-10, 発行日 2019-09-13 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-8841 | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
