ネタもと→インテル スレッディング・ビルディング・ブロックの概要

どうして、こう、中途半端な記事を上げられるのか、不思議。ハッ！こうしてトラックバックさせることで、記事の参照数を増やそうという魂胆か？！

さてさて。何でもかんでもマルチ スレッドに出来るか、というと、そうでもありません。マルチ スレッドの、向き不向きがあります。それをまず、検証するのが、今回のエントリ。

ちょっと考えたのですが、Quick Sort のアルゴリズムが説明しやすいかな？

ご存知ではない方のために、ごくごく簡単に説明しておきます。例えば、次のような数値が与えられているとして、これを1から順番に並べたいとします。

{ 1, 8, 4, 10, 65, 3, 87, 5, 90, 52, 31, 78, 45, 9, 34, 67, 11, 41, 99, 75, 21 }

第1ステップは、ここから適当に1つを選びます。例えば、「75」とします。この、「適当にひとつを選ぶ」という事についても、蘊蓄が色々あるので調べてみて下さい。
第2ステップは、この「75」より小さいものは「75」の左へ、大きいものは「75」の右へ、順番は適当で良いので寄せます。

{ { 1, 8, 4, 10, 65, 3, 5, 52, 31, 45, 9, 34, 67, 11, 41, 21 }, [75], { 87, 90, 78, 99 } }

すると、「75」の位置が確定しました。
第3ステップは、確定した数値の右と左で、2つのステップを繰り返します。

しまった。「75より小さい」「75より大きい」としてしまった。当然、「75が複数あったらどうなるの？」という疑問が生じます。大きい方か、小さい方か、どちらか決めて、寄せます。

と、ここで、考えます。これから行う事は、「1．ひとつの数値を選ぶ。」「2．その数値と全ての数値を比べ、大小によって分類する（ここでは、あえてソートと言わない）。」「3．分類された項目の数が1つになるまで、分類結果に対して1と2を繰り返す。」です。分類しなければならない範囲は異なりますが、しなければならない作業は同じです。つまり、for や while による繰り返し、あるいは再帰構文によって、表現できることがわかります。

マルチ スレッドが効率的に機能する（箇所のひとつ）のは、ここです。マルチで作業することが、互いに影響を及ぼしあわない。そして、それがそれなりに時間がかかるとき、です。

複数の処理で行う事が、互いに影響を及ぼしあうときを考えます。処理Ａが読み込む値は、処理Ｂが計算します。このとき、処理Ａは、処理Ｂが計算を終えてしまうまで、待機しておかなければなりません。この場合、処理Ａと処理Ｂを平行に実行させる意味はありません。

遅いけれども、アルゴリズムの説明によく用いられる、バブル ソートというソート方法があります。これは、マルチ スレッドで行う事で、高速化が見込めるでしょうか。検証します。

まず、アルゴリズムの確認です。バブル ソートは、配列の終端（あるいは始端）から2つの要素を比較し、より小さい方（大きい方）を配列の始端（終端）の方へ入れ替えます。1度配列の要素を全て比較すると、一番小さいものが始端にきています。これを、何度も繰り返します。

{ 1, 8, 4, 10, 65, 3, 87, 5, 90, 52, 31, 78, 45, 9, 34, 67, 11, 41, 99, [ 75, 21 ] }

75と21を比べると、21の方が小さいので、入れ替える。以下、順に前へ移動していく。

{ 1, 8, 4, 10, 65, 3, 87, 5, 90, 52, 31, 78, 45, 9, 34, 67, 11, 41, [ 99, 21 ], 75 }
{ 1, 8, 4, 10, 65, 3, 87, 5, 90, 52, 31, 78, 45, 9, 34, 67, 11, [ 41, 21 ], 99, 75 }
{ 1, 8, 4, 10, 65, 3, 87, 5, 90, 52, 31, 78, 45, 9, 34, 67, [ 11, 21] , 41, 99, 75 }
{ 1, 8, 4, 10, 65, 3, 87, 5, 90, 52, 31, 78, 45, 9, 34, [ 67, 11] , 21, 41, 99, 75 }
{ 1, 8, 4, 10, 65, 3, 87, 5, 90, 52, 31, 78, 45, 9, [ 34, 11 ], 67, 21, 41, 99, 75 }
{ 1, 8, 4, 10, 65, 3, 87, 5, 90, 52, 31, 78, 45, [ 9, 11 ], 34, 67, 21, 41, 99, 75 }

ここから面倒なので早送り

{ 1, 8, 4, 10, 65, 3, 87, [ 5, 9 ], 90, 52, 31, 78, 45, 11, 34, 67, 21, 41, 99, 75 }
{ 1, 8, 4, 10, 65, [ 3, 5 ], 87, 9, 90, 52, 31, 78, 45, 11, 34, 67, 21, 41, 99, 75 }
{ [ 1, 3 ], 8, 4, 10, 65, 5, 87, 9, 90, 52, 31, 78, 45, 11, 34, 67, 21, 41, 99, 75 }

やっと先頭が確定。今度は99と75を比べるところから、またスタート。

バブル ソートは、二重のループが使われます。ループするのだから、マルチ スレッドにすると速くなるでしょうか。

残念ながら、バブル ソートは、マルチ スレッド化出来ません。2回目のループで比較するのは、1回目のループで比較した結果だからです。内側のループも、外側のループも、ひとつ手前の回の結果が必要なので、順次処理するしかないのです。

このように、ある処理をするために、別の処理の結果が必要な場合、マルチ スレッド化することは出来ません。「必要」な処理が済むまで、出来ないのですから。

このことは、システム開発の「工程」に照らし合わせると、より理解できるのではないでしょうか。システムを作り上げるために、必要な「処理」が洗い出されます。その処理の依存性を明らかにして、「処理群」を作ります。処理群を、担当者に割り当てます。この、「担当者に割り当てる」というところが、複数のスレッドを作ることになるわけです。

このとき、並行に処理させられる処理群は、リソース、つまり担当者の数によって決まります。担当者の数を超えて平行な処理群を作っても、誰かが一人で処理群を切り換えながら処理を行うため、効率は上がらず、返って切り換えのために効率を落とすことになるかもしれません。もちろん、処理内容によって、実際にどうなのかは異なります。待ち時間が多い処理ならば、その待ち時間を他の処理群に割り当てることで、効率的に処理できるかもしれません。もちろん、他の処理の結果に依存しないことが前提です。

どの様なところに、マルチ スレッドが活きるか。それを見極めるために、まず、分析ということですね。実行するべき事同士が、結果に依存しないなら、並行に処理させられます。結果に依存するなら、平行には出来ません。やるべき事を把握していれば、何も難しくはありません。