スケーラブルな並列探索による最適化問題の求解

• Item type: SIG Technical Reports(1)
• 公開日: 2018-12-10
• タイトル: スケーラブルな並列探索による最適化問題の求解
• タイトル / 言語: en
• タイトル: Solving Optimization Problems with Scalable Parallel Search
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 最適化問題
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 福井大学
• 著者所属: 福井大学
• 著者所属: 理化学研究所
• 著者所属(英): en
• 著者所属(英): University of Fukui
• 著者所属(英): en
• 著者所属(英): University of Fukui
• 著者所属(英): en
• 著者所属(英): RIKEN
• 著者名: 泉, 翔太; 石井, 大輔; 美添, 一樹
• 著者名(英): Shota, Izumi; Daisuke, Ishii; Kazuki, Yoshizoe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Branch-and-bound 等の探索に基づく最適化手法の並列化は HPC の古典的テーマである．Saraswat らが提案した大域的負荷分散 （GLB） ライブラリは，同型の並列ワーカーからなる機構を提供し，不均一なタスク （例 : 並列探索） を 16K コア程度までスケールさせることができる．しかし，GLB ライブラリを最適化問題へ適用すると，暫定解を効率よく並列ワーカー間で共有することが課題となる．そこで，本研究では GLB ライブラリを拡張し，暫定解の共有速度と通信コストのトレードオフを解決することを目指す．また，拡張 GLB ライブラリのベンチマークとして，木構造に基づく最適化問題を用いる．ワーカー間で暫定解を共有する機能として，通信ワーカーを動的に選択する方式と，ワーカー間の超立方体ネットワークを用いる方式を実装した．拡張 GLB ライブラリを用いてベンチマーク問題の並列ソルバーを実装し，複数インスタンスを求解する評価を実験したところ，784 コア使用時に 429-824 倍の速度向上 （並列化効率 0.55-1.05） を達成した．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2018-HPC-167, 号 24, p. 1-6, 発行日 2018-12-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8841
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会