ネタもと→インテル スレッディング・ビルディング・ブロックの概要
どうして、こう、中途半端な記事を上げられるのか、不思議。ハッ!こうしてトラックバックさせることで、記事の参照数を増やそうという魂胆か?!
さてさて。何でもかんでもマルチ スレッドに出来るか、というと、そうでもありません。マルチ スレッドの、向き不向きがあります。それをまず、検証するのが、今回のエントリ。
ちょっと考えたのですが、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 による繰り返し、あるいは再帰構文によって、表現できることがわかります。
マルチ スレッドが効率的に機能する(箇所のひとつ)のは、ここです。マルチで作業することが、互いに影響を及ぼしあわない。そして、それがそれなりに時間がかかるとき、です。
複数の処理で行う事が、互いに影響を及ぼしあうときを考えます。処理Aが読み込む値は、処理Bが計算します。このとき、処理Aは、処理Bが計算を終えてしまうまで、待機しておかなければなりません。この場合、処理Aと処理Bを平行に実行させる意味はありません。
遅いけれども、アルゴリズムの説明によく用いられる、バブル ソートというソート方法があります。これは、マルチ スレッドで行う事で、高速化が見込めるでしょうか。検証します。
まず、アルゴリズムの確認です。バブル ソートは、配列の終端(あるいは始端)から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回目のループで比較した結果だからです。内側のループも、外側のループも、ひとつ手前の回の結果が必要なので、順次処理するしかないのです。
このように、ある処理をするために、別の処理の結果が必要な場合、マルチ スレッド化することは出来ません。「必要」な処理が済むまで、出来ないのですから。
このことは、システム開発の「工程」に照らし合わせると、より理解できるのではないでしょうか。システムを作り上げるために、必要な「処理」が洗い出されます。その処理の依存性を明らかにして、「処理群」を作ります。処理群を、担当者に割り当てます。この、「担当者に割り当てる」というところが、複数のスレッドを作ることになるわけです。
このとき、並行に処理させられる処理群は、リソース、つまり担当者の数によって決まります。担当者の数を超えて平行な処理群を作っても、誰かが一人で処理群を切り換えながら処理を行うため、効率は上がらず、返って切り換えのために効率を落とすことになるかもしれません。もちろん、処理内容によって、実際にどうなのかは異なります。待ち時間が多い処理ならば、その待ち時間を他の処理群に割り当てることで、効率的に処理できるかもしれません。もちろん、他の処理の結果に依存しないことが前提です。
どの様なところに、マルチ スレッドが活きるか。それを見極めるために、まず、分析ということですね。実行するべき事同士が、結果に依存しないなら、並行に処理させられます。結果に依存するなら、平行には出来ません。やるべき事を把握していれば、何も難しくはありません。
投稿日時 : 2009年12月16日 22:40