エキスコン（６） MISDの話題

さてここまでくるとMISDの話題が残される。Multiple Instruction Single Data、すなわち単一のデータに対して複数処理を扱うスパコンなんて意味があるのだろうか。

　先般、茨木京都大学名誉教授の講演を聴く機会があった。茨木氏はオペレーションズ・リサーチ学会（以下OR学会という）の分野で多くの貢献をしておられる。題目は「汎用ソルバによる問題解決」である。現実の課題は多種多様であり、マンパワーでも処理できないし、コンピュータで処理するにしてもNP困難な壁にぶつかる。
NPとは Nondeterministic Polynomial timeのことで、日本語に訳すと非決定性計算時間である。
計算手順により処理しようとする対象の個数をnとするとき、このnの２乗とか３乗などの多項式で表すことができるものを多項式程度といい、多項式程度では処理できないようなnの階乗、すなわちn!とか、nのn乗の処理回数を要することをNP困難というのである。nが10程度であれば、nのn乗は、100億回程度であるのでパソコンでも何とか処理できそうであるが、nの数が千とか万の数になると、スパコンでも処理困難である。
　いかなるスパコン、あるいは将来出現するであろうエキスコンでも処理できない問題が現実にある。
この課題を汎用ソルバで解決しようとする趣旨である。茨木氏は、NP困難であっても、最適解ではないが現実的に許容できる解が得られる。「近似解を求めるのはNP困難ではない」と説明された。「ただしこれは必ずしも証明されていないが」と茨木氏はつけ加えていた。
そのためにメタ・ヒューリスティックな手法として
•遺伝アルゴリズム(genetic algorithm)
•アニーリング法(simulated annealing)
•タブー探索(tabu search)
•反復局所探索(iterated local search)
•可変近傍探索(variable neighborhood search)
などを用いる。メタ・ヒューリスティックの適切な訳語は難しい。「仁王様のような強大な力をつかって、なんとか問題解決すること」とでも解説しておくことにする。
汎用ソルバとは、これらのアルゴリズムを統合的に包含するシステム・ソフトである。OR関係の学会としてInternational Timetabling Competition 2007で出題された３つの課題にこの汎用ソルバで応募したところ、それぞれ３位、２位、３位を獲得している。揃って３位以上を獲得したのは、茨木氏が主導した汎用ソルバだけであった。

この汎用ソルバは、見方によれば単一の課題を複数のアルゴリズムで解析して、NP困難の近似解を求めると解釈できる。別の視点からすればMISDである。将来を展望すれば、それぞれのアルゴリズムごとにスパコンを構成し、そのスパコンの集合体のエキスコンが汎用ソルバとして威力を発揮する事になろう。茨木氏の言葉を借りれば、NP困難な課題を許容できる時間内で、最適解ではないが許容できる解が与えられる。
様々なアルゴリズムを搭載した多数のスパコンで同一の課題を処理するエキスコン、あくまで想像の範囲ではあるが、米国の政府機関には設置されていて、様々な問題に対処しているかも知れない。
（納）