並列プログラミング入門！＆おさらい！

並列プログラミング
カンファレンス
2010-01-31
この発表では並列プログラミング≒マルチス
レッドプログラミングです！
 並列プログラムの眠い話や嫌な話です！
 発表者がWindowsメインなプログラマなので
それに根ざす情報の偏り等がありますが、そ
こは勘弁してね！
 間違った情報・記述に気付いたら指摘して
ね！


連絡先
twitter: wraith13 (推奨)
 Mail: [email protected]

 並列プログラミングのススメ！
 並列プログラミングの仕組み！
 並列プログラミングの問題！
 並列プログラミングのミソ！
 並列プログラミングのいろいろ！
並列プログラミング入門！＆おさらい！
待ち時間の多い複数のタスクは並列で処理す
るとうんと効率的になるよ！
 昨今のCPUは並列向けだよ！


GUIとそれ以外は別スレッドにしようね！

数秒以上かかる可能性のある処理はその進捗状況も出
すようにしようね！

キャンセルもできるようにしようね！
 キャンセルできなとユーザーは暴挙に出るよ！
グリッドコンピューティングも広義での並列
だよ！
 冗長構成の意味もあるよ！

並列プログラミング入門！＆おさらい！
 シングルなコア・プロセッサの場合
一度に複数の処理を並列に実行するなんてこ
とは物理的に無理！
 各処理を時分割(タイムスライス)し順番に実
行する。

時間
CPU
スレッドA
スレッドB
スレッドC
 シングルなコア・プロセッサの場合

タイマ割り込み＋コンテキストスイッチ
 割り込み：なんらかのイベントが発生した時に実
行中の処理をほったらかして、割り込みハンドラ
として設定されている処理を実行するCPUの機能。
 コンテキストスイッチ：CPUの各種レジスタの状
態(どの処理をどのように実行中であったか→コン
テキスト)の切り替え(スイッチ)。
 タイマ割り込み以外でもI/O待ちなどのタイミン
グでコンテキストスイッチが行われる。
 マルチなコア・プロセッサの場合

シングルなコア・プロセッサの場合と違い、
一度に複数の処理を並列に実行可能！
 マルチなコア・プロセッサの場合

シングルなコア・プロセッサの場合と違い、
一度に複数の処理を並列に実行可能！

でも、実際には大量のプロセス・スレッドを
まわさないといけないので、シングルなコ
ア・プロセッサでやっていたことをそれぞれ
のコア・プロセッサで分担するだけで、本質
は変わらない。
並列プログラミング入門！＆おさらい！
 並列プログラミングには問題が特盛り！

残念ながら並列プログラミンには非常に多く
の問題があります！

嵌って泣かないようにどのような問題がある
のか一通りおさえて起きましょう！

正しくコーディングすることが難しい
ロックやメモリバリアの類の漏れがあったり、
デッドロックを起こすようなコードになっていて
もそれをソースコード上で追跡・確認することが
困難。
 ブラックリスト的手法で、問題となる共有リソー
ス(グローバル変数やAPI呼び出しを含む)へのア
クセスをカプセル化することである程度対処可能。


あるべき姿としては、共有リソースへのアクセスはホ
ワイトリスト方式が望ましいと思われる。ブラックリ
スト方式では漏れが出やすく、漏れたものは再現性が
悪くデバッグも困難な悪質なバグとなる。
 テスタビリティの劣悪さ

プログラム動作状態のパターンがスレッドの
数だけ次元単位で増加し、全ての内部状態を
網羅したテストケースなど現実的に不可能。
 パターンが膨大になる場合は、間引いて要所を押
さえてテストするものですが、この場合、現実的
に可能な範囲でテストをやっても間引き率が極端
に高くなり実質テストをやってないに等しくなる。
 そもそも各スレッドの各種状態をテスト上意図し
た形で実行させるのも困難。
 ブルートフォース的な手法に頼らざるを得ない。
 １→２が０になったり３になったり？

並列プログラミングに関係なく昔からある問
題なのですが、ある値が１から２に変化する
際にそのときどきで0に見えたり1に見えたり
２に見えたり3に見えたりするという非常に
嫌な問題が存在します。
 1と2は変化前と変化後の値なので問題ないとして
も0に見えたり3に見えたりするのは問題です！
 2→1でも全く同じ問題が起きます。
 １→２が０になったり３になったり？

CPU/マザーボードの動作クロックとは非同期
に変化する入力信号などでこの問題は再現し
ます。
 逆もしかりでCPU/マザーボード側からの出力信号
も非同期で動作するデバイスから見ると同じよう
なことが起こりえます。
 そもそも動作クロックとはこのような問題を起こ
さない為のものでもあります。
 １→２が０になったり３になったり？
2桁の2進数で1と2を表記すると01と10になり
ますが、非同期なビットの変化により値が1
から2に変化する際に00,01,10,11の全ての
ビットパターンが現れる可能性があります。
 127(0111111)から128(10000000)へ変化す
る場合は0(00000000)～255(1111111)の範
囲の値に見えてしまう可能性があります。

 １→２が０になったり３になったり？

ハミング距離が1の場合には問題が再現しま
せん。
 例えば2⇔3の場合は10⇔11で、変化するビットの
数が1なので問題が起きようがない。
 cf. グレイコード
 １→２が０になったり３になったり？

昨今の一般的な並列プログラミングの範囲内
ではCPUネイティブな整数値がレジスタやメ
モリ上でそのような問題を起こすようなこと
はないかもしれませんが、並列プログラミン
グの非同期性が複数の値でひとつの意味を成
すデータ上で同種の問題を招きます。
 「ビットの集合」が「複数の値」に姿を変えただ
け。
 シングルトンオブジェクトの初期化問題
C/C++などの低レベル寄りの言語ではシング
ルスレッドでは問題の無いシングルトンオブ
ジェクトの初期化がマルチスレッドの状況下
においては複数のスレッドが同時に初期化を
試行し競合を起こす問題があります。
 関数ローカルなstatic変数などもシングルト
ンオブジェクトである為、同じ問題を起こす。

 シングルトンオブジェクトの初期化問題
簡単な回避方法としてはメインスレッドで最
初に初期化してしまう。
 後述のアウトオブオーダーの問題やCPUのコ
アローカルなキャッシュの問題など、嫌らし
い問題があるので上記以外の方法の実装が必
要な場合は信頼のおけるライブラリの利用を
推奨！

 アウトオブオーダー実行

アウトオブオーダー実行は、よく「プログラ
ムは思った通りではなく書いた通りに動く」
と言われますが、それを覆し「プログラムは
書いた通りにすら動かない」ようにする為の
CPUの機能！
 アウトオブオーダー実行
アウトオブオーダー実行は、よく「プログラ
ムは思った通りではなく書いた通りに動く」
と言われますが、それを覆し「プログラムは
書いた通りにすら動かない」ようにする為の
CPUの機能！
 などと言うのは半分冗談です。


<ぼそっ>でも残念ながら半分事実です。</ぼそっ>

アウトオブオーダー実行

アウトオブオーダー実行は、プログラムを順序ど
おりに実行しなくても問題ない場合にプログラム
を本来の実行順序とは異なる順序で実行すること
でCPUがより高速に動作する為の機能です。

･･･でも、「プログラムを順序どおりに実行しな
くても問題ない場合」であることの判断がシング
ルスレッドを前提としており、マルチスレッド的
な観点からはある意味、指示を無視して勝手な順
序でプログラムを実行するという困った事に。
 アウトオブオーダー実行

マルチスレッド的な観点から実行順序が重要
である場合には、メモリバリアを使うことで
この問題を回避できます。
 同期オブジェクト関連を始めとする、マルチス
レッド関連のAPI等にはメモリバリアの機能を含
むものが多数あります。
 POSIXでは一部の関数群でメモリバリアの機能を
含むものと含まないものが用意されているので注
意が必要です。
 CPUコアローカルなキャッシュ
マルチコア・マルチプロセッサな環境ではそ
れぞれのコア・プロセッサごとにキャッシュ
を持っています。
 これは同じデータのコピーを複数持つことを
意味し、あるタイミングで同じハズのデータ
を参照してもコアによって異なる値になりま
す。
 この問題もメモリバリアにより回避すること
ができます。


スレッドローカルストレージ

スレッドローカルストレージ：
スレッド別データの保存先。
 スレッド別のグローバル変数として使える。


マルチスレッドなプログラミングで重宝する機能
なのですが、スレッドを跨いで使うスマートポイ
ンタの類と組み合わさると、スマートポインタの
参照先を解放するコードにスレッドローカルスト
レージへのアクセスが含まれると意図した本来ア
クセスするべきデータとは異なるデータにアクセ
スしてしまうという自体が発生し得ます。

外部のAPIなどにこのような地雷があると怖い。
 各スレッドは均等な速度では動作しない

そもそもマルチプロセス、マルチスレッド等
をコントロールするOSの判断により、均等な
タイムスライスとはならない。
 同じ系列のOSであってもタイムスライスのロジッ
クはOSのバージョンによっても異なります。

実行優先度等が同一で全く同じような処理を
実行していても参照するメモリがCPUの
キャッシュにたまたま存在するかどうかと
言ったような条件が実行速度には著しく影響
を及ぼす。

並行処理のオーバーヘッド
コンテキストスイッチを実行するのにも当然時間
的コストが存在し、コンテキストスイッチが頻繁
に行われていれば効率が悪くなります。
 ひとつのスレッドから見れば、潤沢に使えるCPU
のキャッシュも各スレッドで使い回すことになれ
ばキャッシュのヒット率も悪くなり実行速度に影
響します。
 ロックやメモリバリアの類のオーバーヘッド
 適切な範囲を超える並行処理は著しいパフォーマ
ンス低下を招くことがあります。


曖昧な「スレッドセーフ」という言葉



まず「スレッドセーフな言語/ライブラリだからマル
チスレッドで使っても安心」は間違いの始まり。
例えば先述の「１→２が０になったり３になったり」
する問題を特別な指示も必要とせず勝手に解決して
くれるスレッドセーフな言語/ライブラリなど存在し
ません。
スレッドセーフを謳う言語/ライブラリ等を使うのは
有意義な事ですが、なにをもってしてスレッドセー
フを謳っているのか？どういう使い方をした時に
どういう問題が起きないことを保証しているのか？
そのあたりが明記されていない「スレッドセーフ」
は要注意です。
 いくつかの問題はプログラミング言語や
その環境がしっかりしてれば解消/軽減で
きる話でもあり、よりよい言語/環境の出
現が望まれる。
並列プログラミング入門！＆おさらい！
 並列プログラミングの多様な問題に嵌ら
ない為にコードに持たせるべき性質につ
いてもおさえておきましょう！
 アトミック
アトミック：中間状態が存在しないこと。
 例えば「１→２が０になったり３になった
り」も中間状態が存在することに起因する問
題で、中間状態が存在しなければこの問題は
発生しない。
 複数の値を持つオブジェクトもそのアクセス
を全てメソッドで隠蔽し、ロック等の排他制
御を行うことで外部からはアトミックである
ように振る舞える。

 ステートレス

ステートレス：状態を持たないこと。

並列プログラミングにおける各種問題は並列
動作するコンテキストから状態を共有するこ
とに起因する為、そもそも状態を持たなけれ
ば(あるいは共有しなければ)問題も発生しな
い。
 ロックフリー
ロックフリー：ロックを行わないこと。
 並列プログラミングではロックの使用を迫ら
れる場面が多いが、ロックは速度的なコスト
が高く、またデッドロックを起こす危険も孕
む為、安易なロックの多用は慎むべき。
 しかし、下手にロックフリーを狙って余計な
バグを埋め込んでしまうというリスクもあり、
難しいところ。

 並列処理を正しくコーディングすることは難しい。
並列プログラミング入門！＆おさらい！
 CPUの並列対応

ハイパースレッディング：
 擬似的にひとつのコアが複数のコアであるように
振る舞う仕組み。

マルチコア：
 ひとつのプロセッサに複数のコアを搭載。
 Kernelレベルを除けば通常、ソフトウェアから見
ればマルチプロセッサとの違いはない。

マルチプロセッサ
 同じ基盤に複数のCPUを搭載。
 通常、同一のCPUを使用する必要がある。

いろいろな並列動作

プロセス(process):


スレッド(thread):


同一プロセス上で並列動作する仕組み/機能
ファイバー(fiber):


一般的にはOS上で動作するプログラムの基本単位
コンテキストスイッチを明示的に行う軽量なスレッド
コルーチン(co-routine):

プログラミング言語的にサポートされているファイ
バー
 同期オブジェクト

並列プログラムが非同期で動作するが故に発
生する問題を回避するための仕組みのひとつ。

同期オブジェクトを使うことで非同期に動作
している並列プログラム間で同期を取ること
ができます！

ミューテックス

もっとも基本的な排他制御用同期オブジェクト。

ロックに成功したスレッドのみが処理を継続。同
じミューテックスに対して一度にロックできるの
はひとつのスレッドのみ。ロックに失敗したス
レッドはロックに成功するまで待機、あるいは処
理を放棄。

Windowsではロックに成功した処理が再帰的な構造に
なっている場合、ロック後の再入であっても同一ス
レッドであればロックに成功した扱いになる。POSIX
の場合はデッドロックとなる。
 ミューテックス
WindowsでもPOSXIでもメモリバリアを含む。
 マルチスレッド関連のAPIの中でも非常に重
い部類なので注意。
 Windowsでは同一プロセス内のマルチスレッ
ド状況下で、ミューテックスの代りにクリ
ティカルセクション系のAPIを使用すること
もできる。


その他の同期オブジェクト

シグナル


セマフォ


主に待機用に使われる同期オブジェクト。
共有リソースに同時にアクセスするスレッド・プロセ
スの「数」を調整するのに使われる同期オブジェクト。
ReaderWriterLock

共有リソースへのリード目的のロックであれば同時に
複数のロックを許し、ライト目的のロックであれば
(リード目的を含め)ひとつのロックしか許さないよう
な同期オブジェクト。
 インターロック系API
インクリメント、デクリメント、値の比較、
値の交換などといった操作をアトミックに行
う為に提供されているAPI。
 速度的コストは良好。

並列プログラミング入門＆おさらい

Download Report