横山 大作, 近山 隆 "高度な問題領域依存チューニングを許す並列組合せ最適化ライブラリPopKern" 情報処理学会論文誌:プログラミング, Vol. 42, No. SIG3 (PRO 10), pp. 49--64, (Mar. 2001).

概要

組合せ最適化問題は並列計算に向いた性質を持っているため, 莫大な計算量が必要となる大規模問題を並列計算によって高速に解きたい, という要求は強い. 並列プログラミングは特有の知識を必要とする困難な作業であるため, この並列化知識なしで簡単にプログラミングが行えるような, 組合せ最適化問題向け並列化ライブラリがいくつか研究されてきた. しかし, 既存の並列化ライブラリの多くは問題領域依存の知識が十分に活用できず, 実問題の専門家たちにとって不満足なものとなっている. 大規模実問題においては, 問題領域に依存した知識を活用することで, 計算量のオーダーを変えるほどのチューニングが行えることもしばしばだからである. PopKernは, 問題領域依存知識の活用に重点をおいた 汎用並列組合せ最適化ライブラリ・パッケージである. PopKernは,代表的な数種の並列組合せ最適化アルゴリズムを提供している. これらのアルゴリズムの問題領域依存部分を全て利用者定義とし, 問題領域に独立なアルゴリズムの枠組みのみをライブラリとして提供して, 利用者定義部分をプラグインすることによって探索を行う, というのがPopKernの設計である. この設計により,利用者は高度な高速化技法を自由に記述することができ, かつ並列処理特有の専門知識を必要とする記述を行うことなく並列計算ができる. 本論文では,PopKernの設計,実装,大規模問題への適用による評価を述べる.

Solving large-scale combinatorial optimization problems demands for massive processing power. These problems are often amenable to parallel processing. As programming for parallel processing from scratch requires its own know-how, research has been widely conducted on designing easy-to-use libraries in this area. However, these existing libraries have not been used widely, as they do not allow users' fine tuning specific to problem domains. Domain-specific tuning sometimes reduces the amount of computation more drastically than application of parallel processing. PopKern is a general-purpose parallel combinatorial optimization library package that allows domain-specific fine tuning. Pop\-Kern provides typical basic parallel combinatorial optimization algorithms. All problem-domain-specific parts are defined by the user. Problem-domain-independent frameworks of these algorithms are built in the kernel of the library. User-defined parts are plugged in to the kernel. With this design, users have large freedom of applying their expertise in writing user-defined parts, and can enjoy parallel processing without paying any attention to parallel processing details. In this paper, we describes the design and implementation of PopKern. It also shows some evaluation results with huge combinatorial optimization problems.

トップページへ戻る
yokoyama@logos.t.u-tokyo.ac.jp