エントリー

2010年08月03日の記事は以下のとおりです。

コンピュータ基礎の基礎~マルチプロセッサとマルチスレッド

  • 2010/08/03 17:00
  • カテゴリー:備忘録

 さて,今日はマルチプロセッサとマルチスレッドについてです。

 CPUは1980年代のRISCから1990年代のスーパースカラ,そして2000年代に入りマルチプロセッサに,その進化の方向が移ってきました。RISCはパイプラインとコンパイラ技術によって高速化をしようという試みでしたが,次にやってきたスーパースカラはソフトはそのまま変えずに,出来るだけハードウェアで並列な命令実行を行うものでした。CPU設計者が無茶な意地を張っていた時代です。

 そしてスーパースカラに限界が見えて,マルチプロセッサの時代になりますが,これはマルチプロセッサを前提にしたソフトウェアを作らなければ全く高速にはならず,その点でハードウェア設計者が再びソフトウェア設計者に頭を下げた,と言っていいかも知れません。

----

問題:
 ある問題について,その実行時間の95%は完全に並列処理が可能で,Nプロセッサを利用することによりN倍性能が向上する。しかし,残りの5%は全く並列処理を行うことが出来ない。この問題を10台のプロセッサを用いて並列処理を行った場合,1台で実行するのに比べて何倍高速に実行することが可能か?

----

 まず最初に,マルチプロセッサとアムダールの法則についてです。

 仕組みや構造はちょっと置いておいて,2つのプロセッサを用いると,処理時間は1/2になりそうなものです。とはいえ,人間でも同じですが,二人が手分けして仕事をしても,なかには手分けできない仕事もあります。こういうものはどちらかが処理するかありません。

 System360の設計者で,後に富士通と一緒にSystem360互換機をビジネスにするジーン・アムダールは,プロセッサの数と同時実行不可能な命令の割合から,最終的な処理速度がどれくらい高速化されるかを公式にしました。これがアムダールの法則です。

 プロセッサの数をNとし,同時に実行出来ない命令の処理時間の割合をFとします。

 まず,Fが0,つまり全ての命令が同時に実行出来るという状態を考えると,プロセッサの数が1の時に比べて,1/Nの時間で処理が終わります。

 逆に,Fが1,つまり全ての命令が同時に実行出来ないという状態を考えると,プロセッサの数であるNに全く関係なく,1つのプロセッサで処理せねばなりませんから,プロセッサの数が1のと同じ処理時間,つまり1倍となります。

 では,Fが0.5,つまり半分は同時に実行出来る場合はどうなるかです。Nに関係なく,絶対にかかってしまう処理時間は0.5です。残りの0.5は1/Nになりますね。もしプロセッサが2つだったら,0.5+0.5*1/2で,0.75です。プロセッサが1つの時に比べて0.75の時間で処理が終わるということになります。

 さて,一般化しましょう。プロセッサが1つ時に比べて,どのくらいの処理時間がかかるのかは,

 F + ((1-F) / N)

 ですね。何倍高速,と言う言い方にするには,これの逆数をとればよいです。

 では,この式を使って早速問題を解いてみましょう。

---
回答:
 全体の処理時間を1とすると,同時に実行出来ない時間は0.05,同時に実行出来る時間は0.95である。プロセッサの数が10であるから,プロセッサが1台の時の処理時間を1とすると,このシステムでは,

 0.05 + 0.95*1/10 = 0.145

 の時間で済むことになる。よって1/0.145=6.90倍高速に実行が可能である。
----

 アムダールの法則によると,プロセッサを10台も使い,しかも命令の並列性を95%まで高めても,7倍弱までしか速度が上がらないのです。なんだか割が合いませんが,プロセッサの数を2つに減らし,しかも命令の並列性が80%まで悪化していると,1.67倍にしかなりません。プロセッサの数を増やすことも大事ですが,実際には命令の並列性を高めることがもっと大切なのです。

 マルチプロセッサには,大きく分けて対象型と非対称型があります。例えば汎用CPUとDSPの組み合わせのように,プログラムを分け,それぞれのプロセッサの役割も決められているようなシステムは非対称型と言われますが,何せいろいろな方法がありますのできちんとした定義は難しいです。

 一方の対象型は,プログラムも役割も同一です。また共有しているメモリへのアクセスについても時間的空間的に平等です。その共有メモリについて,全てのメモリを同じアドレスで複数のプロセッサにアクセスが可能になっているものを集中共有メモリ方式といい,プロセッサごとにローカルメモリを持つものを分散共有メモリ方式と言います。

 言うまでもなく,同じメモリに全てのCPUがアクセス可能というのはプログラムを書くのが楽ですし,わかりやすいですからほとんどがこの方式といってもよいと思いますが,何分メモリが1つ,バスも1つですから,あるCPUがアクセスをしていたら,他のCPUは待たされてしまいます。処理速度がバスのせいで上がらないというわけです。おのずとCPUの数は制限を受けてしまいます。

 一方の分散共有メモリ方式は,命令の局所性をあてにして,バスを使わず自分だけのメモリをガンガンアクセス出来る仕組みですので,プロセッサの数はいくらでも増やすことが出来ます。

 しかし,他のCPUのローカルメモリにアクセスに行くには時間がかかってしまう傾向があります。これではマルチプロセッサでの高速処理が,メモリのアクセスでふっとんでしまいかねません。

 それぞれに一長一短がありますので,システムの規模やコストによって使い分けられています。

 ここでは,対象型の集中共有メモリ方式を例に考えていきます。

 バスとメモリを共有しているのですが,CPUごとにキャッシュメモリを置いてやると,バスやメモリへのアクセスが激減します。しかもキャッシュメモリはソフトウェアにはほとんど影響を与えません。これでマルチプロセッサは万々歳といいたいところなのですが,大きな問題があります。

 キャッシュというのは,メインメモリの一部を高速なメモリに蓄えておくものでした。メインメモリとキャッシュの内容が食い違うことが起こるので,これをどうやって解消するかという問題が,キャッシュでは重要なテーマの1つだったことを思い出して下さい。

 これがマルチプロセッサになると,さらに深刻です。なぜなら,自分の手元にあるキャッシュのアドレスを,他のプロセッサが変更しているかもしれず,その場合自分に変更の覚えがなくても,自分の手元のキャッシュの内容がメインメモリと食い違っていることがあるわけです。

 こうなるともうキャッシュの内容を信用できなくなってしまいます。さすがにまずいので,何らかの対策を取って,それぞれのCPUが持っているキャッシュの内容の一致をしなければなりません。これをキャッシュのコヒーレンシを保証するといいます。

 手段としてはいくつかありますが,ここではMESIプロトコルについて考えてみましょう。

 MESIプロトコルとは,

Modified
Exclusive
Shared
Invalid

 の頭文字を取ったものです。この4つはキャッシュメモリの状態を示すステートで,キャッシュのタグに書き込まれています。これらを持つステートマシンを考えます。4つのステートの状態を以下に示します。

M
 キャッシュメモリとメインメモリは不一致で,他のキャッシュメモリにはキャッシュされていない。

E
 キャッシュメモリとメインメモリは一致しており,他のキャッシュメモリにはキャッシュされていない。

S
キャッシュメモリとメインメモリは一致しており,しかも他のキャッシュメモリにもキャッシュされている。

I
 キャッシュメモリの内容が無効であることを示す。


 基本的には,Sのステートになるように制御がかかります。この制御を行うのが,メインメモリとキャッシュメモリの間に入る,スヌープコントローラです。スヌープとはのぞき見という意味だそうです。

 さて,2つのCPUが同じアドレスのデータをリードした場合を考えます。最初に1つ目のCPUがリードを行うと,1つ目のステートはIからEに遷移します。続いて2つ目のCPUのアクセスが起こると,1つ目のステートはEからSに遷移し,2つ目のステートはIからSになります。2つともSになっていますので,全てのデータが一致していますね。コヒーレンシは保たれています。

 ここでCPU1が書き込みを行ったとします。キャッシュの内容がメインメモリと不一致になりましたので,ステートはMに遷移します。同時に2つ目のステートはSからIになり,キャッシュを無効とします。無効になったのですから,1つ目のキャッシュの内容は2つ目のキャッシュにはキャッシュされていないことになり,Mで矛盾は生じません。

 そしてここでスヌープコントローラの出番です。スヌープコントローラは2つのキャッシュのステートがSになるように動きます。ここでは,1つ目のキャッシュの内容をメインメモリに書き出します。そしてそのデータを2つ目のキャッシュにも書きます。

 このことで2つのキャッシュとメインメモリの3つが全て一致しましたので,1つ目のキャッシュはMからSへ,2つ目のキャッシュのステートはIからSに遷移します。こうして,出来るだけSになるようにして,コヒーレンシを維持するのです。

 対象型のマルチプロセッサにおいては,CPUがいつアクセスを行ってそのデータが有効でなくてはなりません。しかしデータの保存場所がメインメモリだけではなく,それぞれのCPUのそばにも存在しているので,基本的には全てのデータが一致していないと,マルチプロセッサシステムとしては成り立ちません。


 さてさて,ここまででCPUの数は複数に出来ました。しかし前述の通り,複数の命令が同時に実行出来るようにしないと,CPUが同時に動いてはくれません。

 ぱっと思いつくのは,メモリ空間さえも独立しているプロセスを単位として,CPUに割り付けて同時実行することです。しかし,あくまでそのプロセスは1つのCPUで動いていますから,そのプロセスが重いときには,他の手の空いているCPUは手伝ってあげられません。

 かといってOSにはプロセスの中身を見て分割する機能まではありませんから,1つのプロセスを複数のCPUに割り当てることは不可能です。

 そこで,各プロセスの中に「ここは同時に動かしますよ」という印を付けることにします。

 こうして,同じプロセスの内で同時に動くのがスレッドです。同じプロセスですからそれぞれのスレッドは同じメモリ空間で動いています。

 実は,プロセスが情報の共有を行おうとすると,プロセス間通信などを行う事になりますが,これは結構オーバーヘッドも大きく,効率的とはいえません。しかしスレッドはメモリ空間が同じですから,グローバル変数で共有出来るので,とても高速で効率がよいのです。

 そして,わざわざ明示してくれた「同時に動かしますよ」と書かれたスレッドを,複数のCPUに割り当てるのです。どうですか,メモリは共有でグローバル変数で情報のやりとりが出来,同時実行可能とわざわざソフト屋が書いてくれているのです。

 ソフト屋さんとしては,これまで1つのプロセスを書いているつもりで済んでいたのが,どれとどれを同時に実行するかを考えて,スレッドという形で分割しないといけないことになりました。

 プロセスを分割してスレッドにする方法は,大きく分けて2つあります。1つはフォークジョインモデルで,文字通りソフト屋さんが同時実行可能な部分でスレッドと生成し,ソフト屋さんが設定した同期ポイントによってメインのスレッドと同期します。

 POSIXの場合,スレッドの生成はpthread_createで行います。こうして複数のスレッドが生成され,それぞれが同時実行される時に,CPUが複数あればスレッドをCPUに割り当てることで,処理能力を向上させることが出来るわけです。そして各スレッドの結果は,設定された同期ポイントで同期されます。

 しかし,いかにスレッドが軽いとはいえ,スレッドの生成や同期にはそれなりの時間も手間もかかります。スレッドに分割して複数CPUに割り当てて高速化出来ても,これらのオーバーヘッドで食いつぶしてしまうようだと意味がありませんから,スレッドとして同時実行される時間が十分に長い場合ことが条件です。

 もう1つはスレッドプールモデルと呼ばれます。これは複数のスレッドが定期的に実行されることが先に分かっている場合に有効な方法で,これら複数のスレッドをひとまとめにしたスレッドのプールを作成します。

 そして,このプールに情報を入力することで,複数のスレッドが動作して処理されていくのです。スレッドの生成をいちいち行いませんし,同期も頻繁に行いません。それにあらかじめスレッドをひとまとめにしておく関係で,各スレッドの対称性が高い,つまり似たような単位に区切って置けるということで,処理の効率が随分よくなります。


 ということで,例えばWEBブラウザでGoogle Chromeなどは1つのタブを1つのスレッドで処理しています。ですからCPUが増えれば増える程,同時に処理されるタブの数が増えるので,タブをたくさん立ち上げても処理速度が落ちません。また,タブの1つがエラーを出してこけても,スレッドという単位で独立していますから,そのタブが落ちて終わるだけです。(もちろんスレッドで共有されたメモリが壊されてしまえばプロセス,つまりアプリケーションが丸ごと落ちることもあります)

 しかし,CPUが1つしかない時には,スレッドの生成や同期に時間がかかってしまうので,そうした処理を行わない他のブラウザの方が軽くなることになります。そう考えると,マルチコアが当たり前になった昨今のパソコンを使い切るのが,Google Chromeということになりますね。

 そして,CPUの進化がマルチコアと言う方向に進んでいる現在,ソフトを書く上でもどことどこを同時に実行出来るか考え,それをスレッドという単位でまとめることがとても重要な技術になってきます。こうして半導体の進歩とソフトウェアの進歩は歩調を合わせることになり,コンピュータ全体の処理能力が高まっていくことになりました。どちらか一方だけではだめ,そんな時代が来たことを改めて感じます。

ページ移動

  • 前のページ
  • 次のページ
  • ページ
  • 1

ユーティリティ

2010年08月

1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 - - - -

検索

エントリー検索フォーム
キーワード

ユーザー

新着画像

新着エントリー

過去ログ

Feed