打順最適化問題の高速化手法

• Item type: Journal(1)
• 公開日: 2007-03-15
• タイトル: 打順最適化問題の高速化手法
• タイトル / 言語: en
• タイトル: Speed-up Techniques to Find an Optimal Batting Order
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 計算科学と数値シミュレーションの理論と実践
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者名: 大澤, 清; 合田, 憲人
• 著者名(英): Kiyoshi, Osawa; Kento, Aida
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿ではグリッド環境のような計算資源の性能が不均一な環境に対して適応的ジョブ割当て手法を用いた打順最適化問題の高速化手法について述べる．打順の最適化問題はその打順により得られる期待得点を目的関数として定義され，その期待得点はD'Esopo and Lefkowitz 進塁モデルに基づく確率計算により算出される．この計算をすべての打順について行うため，Ninf-G を用いてグリッド環境上で並列に実行することで計算の高速化を図った．また高速化手法として計算パラメータの複数打順間での共通利用，各打者の守備能力を考慮した計算対象打順の選別を行った．さらに負荷分散方式として計算対象打順を適応的に計算ノードに割り当てる方法と計算開始時の試行計算結果に基づき静的に割り当てる方法を実装し比較を行ったところ，グリッド環境においては適応的に割り当てる方法が有効であることが確認された．また適応的に割り当てる場合の最適な計算粒度すなわち打順の分割数をモデル化により決定し，計算資源の有効利用を図った．以上の高速化手法を適用し4 拠点のPCクラスタを利用して134 991 360 通りの打順の組合せについて期待得点を計算し最適な打順を探索した結果，1 台の計算ノードで理論的に265 日程度を要する処理が2 522 秒で実行可能となった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose speed-up techniques to find an optimal batting order in a baseball team by adaptive job assignment, which is suitable for heterogeneous computing resources like the Grid. The objective function of the optimization problem to find an optimal batting order is to calculate expected runs, and the expected runs are computed using the D'Esopo and Lefkowitz runner advancement model. The proposed technique parallelizes computation for performances of all batting orders using Ninf-G, so that the computation time is reduced on the Grid. Furthermore, the proposed techniques improve performance by sharing parameters among multiple batting orders and by choosing feasible batting orders, which fill all fielding positions. We implemented two load balancing algorithms. The first algorithm adaptively assigns computation of batting orders to computing nodes, and the second algorithm statically assigns according to measured computational power at run time. From the comparison with these algorithms, we found the effectiveness of the adaptive algorithm on the Grid. In order to improve the performance of the load balancing, we estimated the optimal computational granularity, or the number of batting orders, by using the model of the computational complexity. The experimental results show that the proposed techniques compute the optimal batting order among 134,991,360 batting orders in 2,522 seconds on the Grid testbed over 4 sites, while it theoretically takes 265 days on a single computer.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 48, 号 3, p. 1443-1454, 発行日 2007-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764