|
|
|
さて、プロセッサが無数に用意されており、いくら使っても良いと仮定しよう。 配列aにある500個のデータの合計をとるという処理を考える。 通常、配列aにある500個のデータの合計は、C言語(or C++、C#)だと int sum=0; for(int i=0;i<500;i++) { sum+=a[i]; } というプログラムになる。片っ端からsumに足し込んでいくわけだ。 ところで、「CPUが無数に用意されている」と前置きしたのに、このようなデータの合計を求める定石通りのプログラムを相変わらず書いてて良いのだろうか？ 仮に、自動でスレッドを生成するコンパイラがあったと仮定しても、このプログラムを並列実行してくれるだろうか？ というのも、このループ処理は、sumという変数の内容を確定するために、その1回前のループで決定した内容に足さなければならないという構造になっている。499番目の計算をするには、498番目の内容が確定していないと実行できず、498番目の計算をするには497番目の…という構造のため、自動的にマルチスレッド展開するコンパイラがあったとしても、この書き方のループは並列展開されない。 いや、そもそも「ループ」というプログラム構造自体、並列演算に向いていないんじゃないかと推測できる。 ループの中身は、プログラム全体の処理時間の大半を占めるし、本来なら同じ処理を多量に行う部分である。せっかく並列処理にしやすい部分なのに、アルゴリズムの組み方によっては並列処理に展開できないのだ。 だから、従来、ループ処理として記述されていた部分を、他の書き方に「抜本的に」変えなければならない。 「プログラミング言語自体、大幅なパラダイムシフトが要求される」と予言する理由はここにある。 2006/12/31
|
|
並列演算の世界というのは、従来とは全く違う思考が要求される。 ということで、例題として 『任意の数を書いた500枚のカードの山が(物理的に積んで)あったとして、その数の合計を知りたい』という、作業を考えててみることにする。 コンピュータ処理でなくて、手計算なり電卓を使っての計算作業である。 もし、計算できる人が1人しかいない場合は、当たり前だが片っ端から合計していくしかない。 何桁の足し算かは知らないが、仮に1回の計算に10秒かかるとしよう。499回の計算なので最終的な合計を求めるまでにかかる時間は4990秒(およそ1時間23分)になる。 1時間半も無休で計算し続けるのは辛い作業である。 ということで、もう1人、手伝える人を増員する。 『他人に迷惑をかけちゃいけないので、一人で頑張る』、というのもま、一つの解ではあるが、せっかく手伝ってくれるというのだから、仕事を割り振らないと申し訳ない。 ２人で作業するにはどうすれば良いだろうか。 【案１】 250枚ずつにカードを山分けし、それぞれ互いに合計を求めた後、最後に２人で求めた結果を足す。 1回の計算に10秒かかるとすれば、1人あたり250回の計算になる(両者で249回、最後の合計に1回)で2500秒(41分40秒)に短縮できる計算になる。 計算時間にムラがある場合は、全体の処理にかかる時間が遅い方に引きずられる欠点はある。 【案２】 500枚の1つの山から、カードを1枚ずつめくりながら、足していき、山がなくなったら最後に２人の結果を足す。 このアルゴリズムをプログラムで表現する場合は、２人が同時に同じカードをめくったり、飛ばしたりしないように、きちんと制御しなければならない点で、面倒な方法ではあるが、計算のムラに強い利点もある。 ただ、おわかりのように、並列演算の世界には、もはや「最初から最後まで繰り返す(順番にやっていく)」というループ処理の概念はない。 2006/12/31
|
|
2人で作業すると、計算時間は約半分の41分にまで短縮できる。 では、計算を手伝う人を、もっと増やしてみよう。 500枚のカードの集計の手伝いに50人集まったとする。 単純計算ではこれで50倍速の処理になるはずだ。 だが、これだけ人数が増えると、逆に困った問題が出る。データの集配問題だ。 仮に、【案１】の延長のような事をする場合、500枚のカードを10枚ずつに山分けする事になる。その他にも、計算した結果の収集作業、その結果の集計作業といった、別の処理の負担が増大する。 ここが無視できなくなるのだ。 具体的な処理時間で言えば、カードそのものの計算は、1人あたり9回の計算(10枚分。90秒:1分30秒)で済むが、50人それぞれが出した結果を集計するのに49回の計算(490秒:8分10秒)が必要になってしまう。これにカードを分配する時間が加わる。 単純に手伝う人(CPU)の数が多いほど前処理・後処理の負担が大きくなり、並列化の効果が発揮できにくくなってくる。 また、50人を集めるつもりが、都合が悪くて40人しか集まらなかったら、その場に応じて割り振り方も考えなければならない。これが実際のプログラムだったら、ターゲットとなる計算機のCPU数や、計算のために割くことのできるCPU数に応じて動的に変えなければならないという意味でもある。 それはそれで頭の痛い問題だ。 2006/12/31
|
|
ま、今思いついたので、最短と言えないかもしれないが。 計算の手伝いに何人でも呼べると仮定して、500枚のカードの合計を最速で計算する方法を考えてみた。 【案３】 (1)2枚のカードを山からめくる (2)カードに書いてある数を合計をし、その結果を未記入のカードに書き込む (3)結果を書いたカード1枚だけを山に戻す。(めくったカードは捨てる) …を繰り返すというものだ。 ※山に1枚しかない場合は、カードを取らないこと。 と、全員に言い聞かせて、一斉に作業を始める。 最終的に山にあるカードが1枚になったとき、全部の合計が、そのカードに書き込まれているという寸法だ。 カードを山からめくったり置くのにかかる時間を無視すると、最初、500枚のカードを2枚ずつ250人がカードを持って、計算。結果を記入したカードが戻されて、250枚の山になるのに10秒である。 次に、125人が(250人来てくれたが、残りの人は、これで仕事が終わりとなる。)2枚ずつカードを持って、10秒ほどかけて計算し、125枚の山になる。以後、63枚の山になり…となる。あとは、31,16,8,4,2,と、半分の半分で減っていき、最終的に1枚になる。 このアルゴリズムだと、500枚のカードの合計を求める場合の最短時間は、最大250人使って90秒(つまり、最多で9回の演算)となる。 ま、「山から2枚ずつめくる」や「山に戻す」といった作業も実際は時間がいくらかかかるが、片っ端から処理する場合に比べても、大幅な高速化が可能だ。 2006/12/31
|
|
現実に、250人が集まって1つのカードの山に手を伸ばしたら、大混乱になる。 もう少し整然として計算できるようにするには、こんな感じだろうか。 【案４】 ・カード置き場Aに250枚のカードの山を置き、歩いて10秒少々の場所にカード置き場Bを作ってそこに残り250枚のカードを置く。(厳密ではなく、おおむね半分で良い) ・まず、カード置き場Aから2枚のカードをめくって、歩きながら計算を行う。 ・カード置き場Bに到着した頃には計算が終わっているので、今度はカード置き場Bからカードを1枚めくってUターンし、今出た答えに今めくったカードの数を足しながら、カード置き場Aに戻る。 ・結果が出る頃にはまたカード置き場Aに戻っているので、またカードを1枚めくり、カード置き場BにUターンしながら計算する。 …これを繰り返す。 ・もし、カード置き場にカードがなければ、今持っているカードをカード置き場に置き、計算しないでただ歩いて戻る。 ・手元にカードがなければ、カード置き場から２枚めくって計算する。 ・カード置き場AまたはBにカードが1枚だけになったら終了。 という方法だ。 あとは、カード置き場A,カード置き場Bの間に物理的に何人詰め込めるかの問題になり、詰め込める人数が多いほど処理時間が短くなる。 (現実的には…歩いて往復20秒の距離(約22メートル)に250人を詰め込むのは…ま、無理だろうが。) 2006/12/31
|
|
ということで、『500枚のカードに書かれた数を合計する』という単純な問題の並列演算の解法をいくつか出して検討してみた。 これらが最適な並列演算手法かどうかは、不明である。 ただし、従来、ループ処理で実現されていた処理もアルゴリズムを変えて並列演算に最適化された形に展開できれば、猛烈な高速化・高効率化が実現できる(可能性または余地がある)ということはご理解頂けただろうか。 マルチプロセッサやマルチコアは、現状、無駄以外の何者でもない。 しかし、無駄なのではない。 利用するノウハウがないだけである。 2006/12/31
|
|
[戻る] |