高度な問題領域依存チューニングを許す並列組合せ最適化ライブラリPopKern

• 横山, 大作

• 近山, 隆

書誌事項

タイトル別名

• コウド ナ モンダイ リョウイキ イゾン チューニング オ ユルス ヘイレツ クミアワセ サイテキカ ライブラリ PopKern
• PopKern : A Parallel Combinatorial Optimization Library Ready for Highly Domain - specific Tuning

抄録

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

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. Popｴ-Kern 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 Pop-Kern. It also shows some evaluation results with huge combinatorial optimization problems.

収録刊行物

• 情報処理学会論文誌プログラミング（PRO）

  情報処理学会論文誌プログラミング（PRO） 42 (SIG03(PRO10)), 49-64, 2001-03-15

  東京 : 情報処理学会

キーワード

• 通常論文

詳細情報

• CRID: 1050845762821798016
• NII論文ID: 110002725708
• NII論文ID: 10011009229
• NII書誌ID: AA11464814
• ISSN: 18827802
• ISSN: 03875806
• NDL書誌ID: 5712696
• Web Site: http://id.nii.ac.jp/1001/00016882/
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I5712696
• 本文言語コード: ja
• 資料種別: article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles