Order/Radix Problemにおける対称性とホストの偏りを利用した最適化アルゴリズムの提案

• Item type: SIG Technical Reports(1)
• 公開日: 2021-11-29
• タイトル: Order/Radix Problemにおける対称性とホストの偏りを利用した最適化アルゴリズムの提案
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 高性能計算
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 理化学研究所計算科学研究センター
• 著者所属: 関西大学
• 著者所属: 関西大学
• 著者所属: 理化学研究所計算科学研究センター
• 著者名: 中尾, 昌広; 塚本, 雅生; 花田, 良子; 山本, 啓二
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 並列計算機システムにおいて，平均ホスト間距離（h-ASPL：host-Average Shortest Path Length）が小さい間接網を導入することで，システム全体の性能を向上させることが期待できる．そのような間接網をグラフ理論上で議論するため，Order/Radix Problem（ORP）が提案されている．ORP とは，与えられたホスト数と Radix を満たす最小の h-ASPL を持つグラフを発見する問題である．ORP のグラフは間接網を表しており，頂点はホストとスイッチの 2 種類が存在し，スイッチはホストもしくは他のスイッチと隣接でき，ホストはスイッチとのみ隣接できる．本稿では，ORP のための最適化アルゴリズムの提案を行う．提案アルゴリズムの特徴として，グラフに対称性を持たせる点，各スイッチによって隣接するホストを偏らせる点が挙げられる．これらの特徴により，h-ASPL を求めるための計算時間を削減させ，かつ提案アルゴリズムの解探索性能を向上させることができる．ORP のための国際コンペティション Graph Golf が出題している問題を用いて提案アルゴリズムの性能評価を行った．その結果，提案アルゴリズムは既存アルゴリズムと比較して h-ASPL が小さいグラフを生成できることを示した．さらに，提案アルゴリズムが生成するグラフの性能を評価するため，並列シミュレーションフレームワーク SimGrid と並列ベンチマーク集 NAS Parallel Benchmarks による評価を行った．その結果，提案アルゴリズムが生成するグラフは，既存アルゴリズムが生成するグラフよりも高い性能を発揮できることを示した．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2021-HPC-182, 号 13, p. 1-14, 発行日 2021-11-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8841
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会