今の私たちが計算機で扱えている問題と計算機の性能の話

研究

上を受けて、計算機科学系研究者の端くれとして、どうして計算機の性能向上が必要なのかを説明してみる。

計算複雑さの話と私たちが計算機で扱えている問題

計算機科学系の学科へ進学すると、最初の方に教えられるのが計算複雑さの話。すっごく大雑把な言い方をすると以下のことが教えられる。

世の中には、四則演算から世界平和の実現法まで多岐にわたるさまざまな問題が存在している。世の中に存在する問題には計算ができる問題と計算ができない問題が存在する。ある問題が何百年、何千年、何億年かかっても良いから有限の処理工程で解決できることを示せたとき、その問題を計算できたという。理論上、計算機で扱うことの出来る問題は計算ができる問題だけである（この話を厳密に学ぶのが計算可能性理論という分野）。

ところが、実際上はこの計算機で扱うことができる問題のすべてを計算機で扱えるわけではない。その理由は計算時間がかかりすぎる、あるいは必要とするメモリの量が多すぎるため。どの問題がどのくらいの計算時間やメモリの量を必要とするのかを検討するのが計算複雑さ理論の分野。

入力されるデータの量に対して計算時間が多項式（xの何乗）で表せる問題を多項式時間問題といい多項式時間問題の集合をPで表す。多項式時間で解けない問題（問題の解答に多項式時間以上かかってしまう問題）の集合の一つにクラスNPがある（たまに目にすることがあるP != NP問題とかのPやNPはこの話）。

計算複雑さ理論において、計算機で扱えるのはクラスPに属する問題だけであるとされているが、実用上は、データの量がnのとき、計算時間がnの2乗（O(n^2)と表す）を超えるともうまともに計算できない。下の図は、問題間の包含関係をベン図で表したもの（ただし、計算可能問題の集合とNPが同じかそうでないかは私の勉強不足で覚えていないので注意）。

あくまでもイメージなので、円の大きさの違いは正確ではないが私たちが現在の計算機を使って実用的に扱えている問題は世の中に存在する問題にくらべれば、本当にわずかなもの。計算複雑さ理論において実用的に計算できると言われているクラスPに比べても、私たちが現在の計算機を使って実用的に扱えている問題はほんのわずか。

日本ではアルゴリズム屋と呼ばれている、ある問題を解く際の有限の処理工程を日々考案し、改良している研究者の人たちは、このPの問題を出来る限り少ない処理工程で解くことができないか、あるいは、NPの問題をPの問題に近似して、それなりの精度の解答を出せないかどうかを研究している。

しかし、我々がシミュレーションなどをすることによって、計算したい問題の多く（ほとんどと言っていいかもしれない）は、NPに属する問題。クラスPに属する問題よりも難しい問題である。たとえば、宅配便が効率良く一筆書きで配達先を回るにはどういう経路をとれば良いのかを考えたり（巡回セールスマン問題。）、飛行機で物を運ぶとき、もっとも利益がでるような積み荷の積み方はどういうものかを考えたり（ナップザック問題）など。小学校から常にお世話になっている時間割を計算機で自動的に作る問題すら、NPに属する問題クラスPに属する問題よりも難しい問題だったりする。

ある問題を解く際の有限の処理工程を日々考案するのも重要だけど、どんな問題にでも良い案が浮かぶわけではない。そこで、計算機の性能をアップさせることで、計算時間の短縮をしちゃえばいいんじゃないという力技のアプローチがでるのは当然の発想。この発想の下に日々繰り広げられているのが高性能計算という分野の話。

スーパーコンピューターと並行処理計算

私たちが計算機に計算させたい問題の多くは、データの量がnのとき、計算時間がnの2乗を超える問題。じゃあ、計算機の性能をアップさせることで計算時間の短縮をしちゃおうという発想の下に開発されているのがスーパーコンピューターやクラスター型並列計算機、あるいはグリッドコンピューティングという話。

計算機の性能UPのための素朴なアプローチは以下の二つ。

  1. CPU（計算機の心臓部。ここで主たる計算を行う）で行われる1処理の速度をどんどん上げる
  2. データの読み出しに費やされる速度をどんどん短くする

集積回路の技術が進みこの部分はここ10年で目を見張るほどの改良が進んだ。その結果として、この二つの部分の改良だけでは十分な性能向上が見込めなくなってきた。それで登場するのが並行処理技術。

並行処理技術とは、計算したい問題を部分問題に分割して、複数のCPUに同時に並行的にその部分問題を解かせる技術。現在のスーパーコンピューター、クラスタ型並列計算機、グリッドコンピューティングなどは、並行処理技術をどう実現するかの違いになっている。

間違っているかもしれないけど大雑把にわけると、以下のようになる（追記２を参照のこと）。

  • スーパーコンピューター：複数CPUと莫大な共有メモリ、CPU間のデータのやりとりはメモリ上で行われる。
  • クラスタ型並列計算機：複数CPUと複数メモリ、CPU間のデータのやりとりは、高速LANを用いて行われる。
  • グリッドコンピューティング：複数CPUと複数メモリ、CPU間のデータのやりとりは、低速LANやインターネットを用いて行われる

「もう、スーパーコンピューターなんかいらないよ。全部グリッドコンピューティングでいいじゃない」という意見があるけど、話はそう簡単じゃない。並行処理を行うためには計算したい問題を部分問題に分割しないといけない。ところが、すべての問題が部分問題に簡単に分割できるわけでないし、分割できたとしても、CPU間でどれぐらい頻繁にデータのやりとりをしなければならないのかが全く異なっている（これを粒度という）。

問題の粒度によって、スーパーコンピューターで処理するのに適した問題、クラスタ型並列計算機で処理するのに適した問題、グリッドコンピューティングで処理するのに適した問題に分かれる。理由はデータのやり取りにかかる通信時間が計算時間に対して影響を与えてしまうため。基本的には、CPU間でデータのやりとりが少なければ少ないほどグリッドコンピューティングに向いた問題であり、CPU間でのデータやり取りが多いほどスーパーコンピューターが必要となる。

このある問題を部分問題に分割し、かつ、それを並行処理技術で解くというのも大きな研究のテーマと成っている。ちなみに、線形代数で表現できる問題は並行処理と相性が良い。たとえば、画像処理（CG）は並行処理ととても相性がよい。ゲーム機のCPUの処理速度が早いといわれる理由はこの線形代数計算に特化したCPUだから。線形代数で表現できない問題に対しては、ゲーム機のCPUは使いづらい（その性能を発揮できない）。

まとめ

  • 現代社会はより広い範囲の問題を計算機で計算することを要請している。
  • 広い範囲の問題を計算機で計算するには、計算機の性能向上が欠かせない（アルゴリズムの改良には限界があるし、これは予測ができない）
  • どんな問題でも並行処理で扱えるわけではない
  • スーパーコンピューティング、クラスタ型並列計算機、グリッドコンピューティングにはそれぞれ得意、不得意な問題がある

追記

急いで書いたので不適当な部分があるので補足。

決定性チューリングマシンを用いて、多項式時間で判定可能な問題のクラスがクラスP。非決定性チューリングマシンを用いて、多項式時間で判定可能な問題のクラスがクラスNP。

クラスNPの任意の問題が問題Aに多項式時間帰着可能であるならば、問題AはNP困難であるという（このとき、問題Aは必ずしもクラスNPに属する問題ではない）。クラスNPの問題AがNP困難であるとき、問題AをNP完全という。

追記２

はてなブックマークコメントより

私の知識が古かったようです。id:dowhileさん、id:staebchenさん、ご教示ありがとうございます。