Grid 計算環境における2 つの制約解消系の試験的実装について

• Item type: Trans(1)
• 公開日: 2005-04-15
• タイトル: Grid 計算環境における2 つの制約解消系の試験的実装について
• タイトル / 言語: en
• タイトル: Some Experimental Results of Two Constraint Solving Systems on the Grid
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 神戸大学自然科学研究科
• 著者所属: 神戸大学自然科学研究科
• 著者所属: 神戸大学自然科学研究科
• 著者所属: 神戸大学自然科学研究科
• 著者所属: 神戸大学自然科学研究科
• 著者所属: 神戸大学学術情報基盤センター
• 著者所属: 神戸大学学術情報基盤センター
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology Kobe University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology Kobe University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology Kobe University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology Kobe University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology Kobe University
• 著者所属(英): en
• 著者所属(英): Information Science and Technology Center Kobe University
• 著者所属(英): en
• 著者所属(英): Information Science and Technology Center Kobe University
• 著者名: 川谷, 宗之; 岡本, 英彰; 松田, 一人; 北川, 哲; 大西秀志; 番原, 睦則; 田村, 直之
• 著者名(英): Muneyuki, Kawatani; Hideaki, Okamoto; Kazuto, Matsuda; Satoshi, Kitagawa; Shuji, Ohnishi; Mutsunori, Banbara; Naoyuki, Tamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 制約プログラミングとは，「ユーザは解決したい問題を制約の形で宣言的に記述するだけで，あとは制約解消系がその制約を満たす解を求めてくれる」という問題解決手法であり，近年注目を集めている．1990 年代には商用の制約解消系が登場し，これまで制約プログラミング手法に基づく生産スケジューリング，資源割当てなどの，実用的なシステムが開発されている．しかしながら，大規模な問題に対しては，制約解消系の処理に大きな計算量が必要とされるという問題がある．一方，近年の急速なネットワークインフラの高速化，普及を受けて新しい分散処理形態であるGrid が注目を集めている．我々の研究チームでは，Grid 計算環境に制約解消系を実装することでそのパフォーマンスを向上させることを目的とし，Grid に適した制約解消系の設計および実装を進めている．本発表では，その一環として実装を行ったGrid 計算環境上の2 つの制約解消系について述べる．まずSunGrid Engine（S.G.E.）上の制約解消系の実装，次にGlobus Toolkit を用いた制約解消系の実装について説明し，最後に，これらの制約解消系と単体計算機上の制約解消系を用いてパフォーマンス比較を行った結果を示す．ベンチマークにはよく知られているJob Shop Scheduling 問題などを用いた．得られた結果のうち，多くの場合において，今回の2 つの制約解消系が単体の計算機上の制約解消系より良い結果を示しており，制約解消系をGrid 計算環境上に実装することによる有効性は十分にあると結論付ける．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In constraint programming, all you have to do is to define problems as sets of constraint declaratively, and then, constraint solvers search solutions. Commercial constraint solvers appeared in 1990s and have been used for production scheduling, resource allocation, and others. Constraint solving systems are useful but there are some issues. One of them is that they need much computational power to solve large scaled problems. Meanwhile, the Grid computing is a hot topic on the recent spread of the network infrastructure. In this presentation, we show some experimental results of two constraint solving systems on the Grid. We have developed these two systems on Sun Grid Engine and Globus Toolkit respectively. In each system, constraint solvers are implemented using Cream developed by our group. Cream is a Java class library for constraint programming and provides various optimization algorithms such as Simulated Annealing, Taboo Search, etc. We use Job Shop Scheduling Problem as benchmarks. In performance, our systems on the Grid gave nice speedup compared with Cream on a single machine.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 46, 号 SIG6(PRO25), p. 61-61, 発行日 2005-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会