2024-03-29T09:20:24Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000952642023-04-27T10:00:04Z01164:02240:07073:07268
PGAS言語X10による数値制約充足問題ソルバーRealpaverの並列化jpnアプリケーションhttp://id.nii.ac.jp/1001/00095245/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=95264&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Information Processing Society of Japan東京工業大学東京工業大学/IBM東京基礎研究所/JST CREST石井大輔鈴村豊太郎数値制約充足問題 (NCSP) は,制御工学やロボティクス等の問題を実数変数を持つ等式・不等式制約を用いて記述し,充足解を求める問題である.実数変数のドメインを区間ベクトルとして与え,制約伝播と探索を駆使し,指定精度で解を包む区間ベクトル集合を効率よく計算する手法が発展している.有限・離散ドメインの制約充足問題については並列化手法が研究されているものの,実数ドメインにおける多くの提案手法は逐次処理を前提としており,その並列化手法は明らかでなかった.とくに under-constrained NCSP では,領域状の解集合を多数の区間ベクトルで包む計算を行うが,このような求解プロセスには並列性が見込まれる.本研究では,PGAS 言語 X10 を用いて既存の NCSP ソルバー Realpaver を拡張し,計算機クラスタ上でスケール可能な並列ソルバーを構築した.提案手法では,探索木を複数プレースに分散し,各プレースで自律的な求解タスクを走らせることで並列化を行う.また,均等に探索木を分散するための前処理を提案する.東京工業大学 TSUBAME2.0 上で 16 プレースを用いた実験結果では,well-constrained NCSP に対して最大 7.9 倍,under-constrained NCSP に対して最大 9.7 倍の速度向上を得た.AN10463942研究報告ハイパフォーマンスコンピューティング(HPC)2013-HPC-14110172013-09-232013-09-13