スゴ技

平成26年度春基本情報技術者試験【問3】（その2）

Blog：IT・情報処理BLOG | 2014.05.25

ブログの3男佐藤です。

…思いを馳せす過去問をお手元において進めましょう、平成２６年春問３の設問２です。

この問題というか設問、プログラムを細切れにするという話です。

細切れ話の解決に向かう前に、前提知識の再チェック、プログラムの粒度に関わるお話。
私達が使うプログラムは主にストレージ(ディスク)に格納されており、OSがどこかからの要求にあわせてメモリ(いわゆる主記憶)に読み込んで実行します。ストレージ上のプログラム1つに対し、マルチタスクのOSであれば、複数箇所でメモリに読み込んで同時に実行させる仕組みを持ちます¹。実際の実行はCPUが(主記憶から)命令を読み込んで行うものなので、CPUの割り当てがなされている状態がいわゆる実行中となります。マルチコア(CPU)であれば、理論上CPU数だけ同時に実行中状態にできます。このメモリに読み込まれており、CPUを割り当てられて実行する単位が大雑把にですがプロセスです。マルチタスクの「タスク」は「プロセス」に置き換えて考えてもらっていいでしょう。よくわからんという人もおられるかもしれませんが、プログラム1個からプロセスn個が生成されていても不思議な話ではないというレベルで強引に考えてもらってもいいかな。各プロセスは理論上メモリが独立して存在しており、互いをいじる(参照、更新)することはOSができなくしています²。だからこその同時並列の実行が可能となっているのです。

で、この問題に登場するスレッド、これはプロセスの中で各所にCPUを別個に割り当てて並列で処理させることとなります。プロセスという単位より細かいところで分割していることになります。あくまでプロセスの内側ですので、プロセスでやっていたデータ共有手段を考えなくても普通に見えてしまいます。参照、更新好きにしなさい状態です。プロセス間に比べれば、スレッド間の通信は気楽に行えてしまいます。単純に読み書きすればいいのですから。

ということで、ある処理内容を細切れにして、それぞれを別スレッドという形にしてしまえば、各スレッドを並列で処理できるので素早く処理できると言いたいのでしょう。設問2の図3はまさにそれを示しているのです。
実際今のコンピューターみたいにマルチコア(CPU)となると、ひとつひとつを丁寧に進めていく³と、他のコアが暇になってしまいます⁴。
マルチタスクのシステムなら基本的にそういう暇をしているコアにOS(スケジューラー)が別のタスクを割り当てることで利用率向上を狙います。
でも、今やってる仕事に対して効率的に働かせるのであれば、スレッド分割し、それぞれをコアに割り当てることで計算性能を向上させてしまおうということになるのです。
設問1はいくつにスレッド分解を行い、いくつのコア(CPU)に縛り付けることで処理速度を(理論上)5倍以上に高められるのかということを調べていたと見ることができるのです。

ところがこのスレッド分割、良くも悪くもスレッドのため、処理に使うデータは同じ空間を参照します。データの保護という観点で見ると、プロセスなら独立していますのでやりやすいのですが、スレッドだから仕方ない(前述のように、プロセス内ですからそのまま読み書きできてしまう)。

このような問題に対するひとつの考え方に、データの従属性というものがよく出てきます。
連続する処理を並列化させたいというときに、

ある計算の結果を次の計算で利用するときは、単純に並列化できません(処理に順番があるため、その部分は順序だって行う必要があります)
ある計算が使用するつもりの値が他のスレッドで書き換えられるようなことがあるのなら、単純に並列化できません(タイミングにより読み込む値が変わってしまうことになりますから)
ふたつのスレッドが同じ領域に結果を出力してはいけません(後に書き出しているスレッドの処理が有効になってしまうから)

このあたりを小難しく書いたのが、Wikipediaの並列計算に出ているデータ従属性ではないかと思います。

と、いろいろ書いたところで問題に向かいましょう。

問題の図3で、ループ内を分割して並列するという話が出ています(ループアンローリングという手法です)。100回ループを25回ループ×4にすることで4つのスレッドに分割してなんとなく4倍にしてみない?というところです。この図が伏線になっています。

空欄bに該当するのはプログラム1です。この計算、a[i]の値はa[i-1]の値を参照しています。nを100とすると、図3に近くなります。このとき、a[26]を計算したいと思ったら、「a[26] ← a[25] + b[25]」という式になりますが、a[25]は別スレッドの値になっているのですね。これ、先ほど書いた中で出てきている「ある計算の結果を別の計算で利用するとき」に該当しています。選択肢で該当するものはアとなります。

空欄cに該当するのはプログラム2です。このプログラムは逆に(連続的に逐一処理していれば)未来に書き換えられる予定のデータを読み込んでいます。すでにa[ ]には、事前の処理で何らかの値が入っているのでしょう。逐一処理なら問題になりませんが、先ほどと同様にn=100として図3のような4スレッド分割をしてみると、「a[25] ← a[26]+a[25]」となります。26番目は別スレッドで書き換えられる可能性があるため、これも並列化できなくなってしまうのですね。選択肢で該当するものはウです。

ここまでの2つのプログラム、ループ展開するときの境界域を考えてみればあっさり解けてしまう問題なんですね。

一方でプログラム3、ループ内においては定数とされそうなmの値がポイントになります。実はここで処理しようとしているデータa[ ]がn個でおわらず、その後も継続しているという状況(少なくともn+m番までは存在している)であれば、今回の処理範囲(1〜n)において、1+m〜n+m番は書き換えられません。数値に置き換えてかんがえてみれば、