| 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 |
|
収録物識別子 |
AN10463942 |
| 書誌情報 |
研究報告ハイパフォーマンスコンピューティング（HPC）
巻 2018-HPC-167,
号 24,
p. 1-6,
発行日 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-HPC18167024.pdf (812.3 kB)
