原題 "The Art of Concurrency"
プロセッサの進化は、ムーアの法則に従って勢いづいてきたが、ここへ来て、クロック周波数は発熱と電力の物理学に屈服しつつある。現在ではエネルギー問題とも相まって省電力化を求める傾向があり、ちょいとダウンクロックさせてでも別の道を探ろうとする。
その一つの方向性に、並行コンピューティング技法がある。いまや、マルチコアやマルチスレッドは当たり前。一人の仕事を大勢に割り振れば、すぐに終わる... と行きたいところだが、うまく分担できなければ、むしろ混乱を招く。オーバヘッドってやつは、仕事を割り振る作業や仕事を集約する作業だけでなく、人間関係の衝突からも生じる。人海戦術で、人の海に溺れることはよくあることだ。マルチスレッド戦術を用いたところで同じこと...
本書で注目したいのは、スレッド化の正当性と、その性能評価である。全般的に、まず逐次ソースコードが提示され、これを並行化するというやり方で、それぞれの実装に対して「実行効率、簡潔性、可搬性、スケーラビリティ」の四つの観点から評価するというストーリー立て...
尚、千住治郎訳版(オライリー・ジャパン)を手に取る。
古くから、プロセッサの性能を最大限に引き出すためのコード手法が工夫されてきた。それも芸術の域に達するような...
リソースが思いっきりショボい時代には、アセンブラ言語に勢いがあり、コンパイラ効率もイマイチで、機械語でガチガチに書いたこともあったっけ。C 言語はというと、高級言語の地位にあって、まるで王子様気取り。リアルタイムシステムでは、使えねぇヤツだと囁かれた。それが今では、低級言語に格下げ！
本書のコード事例でも、最小公倍数的な存在として C 言語が採用され、低級な抽象観念しかイメージできないネアンデルタール人には、むしろ馴染み深い。
リソースが贅沢になれば、それをフル活用するための手法が生まれ、マルチコアが目の前にぶら下がっていれば、これに適合したコードが編み出される。そこで、OS がアプリケーション単位で割り振ったり、プロセス毎に切り替えたり、あるいは、ライブラリが暗黙にスレッド分割してくれれば、ありがたい。
但し、OS に任せるにしても、ライブラリに頼るにしても、根本的な仕掛けを知ると知らないでは大違い。
マルチスレッドプログラミングで最も目につく問題といえば、メモリアクセスの衝突であろうか。スレッド群を公平にスケジューリングすれば、各々がどんな処理をしようが知ったこっちゃない。スケジューラが中身を知らなければ、問題の特定も難しくなる。
本書は、信頼性を重視する立場から、実績のあるライブラリの導入を推奨し、汎用的なライブラリとして OpenMP や Intel TBB(Threading Building Blocks)を用いた事例が多く紹介される。なるべくなら、スクラッチでスレッドを作成することは避けたい。手っ取り早くテンプレートを真似るのが無難か。
スレッド単位で扱えば、それなりに危険を伴うであろう。メモリ領域の衝突やデータの競合も生じ、分割の粒度を細かくすれば、オーバーヘッドも増える。ノイマン型アーキテクチャであるからには、どんな処理であれ、どんなソースコードであれ、スレッド分割することは可能であろうが、あらゆるスレッドが並行化できるわけでもあるまい。逐次処理の多くは何らかの形で依存性を持ち、独立した関数コールや実行順序を問わないループが見つかれば儲けもの。スレッドが単独で起動/終了が可能か？スリープ/再開が可能か？スレッド間の依存性はどうか？などと頭を悩ますぐらいなら、最初から OS に委ねた方が賢明やもしれん。
一つの教訓として、並行性はより上位層で実装すべし！というのがあり、本書でも八つのルールの中で二番目に提示される。アプリケーション単独で性能向上を目指すなら、スレッド単位で検討するべきであろうが、ちょいと捻くれた目で、もっと大雑把にアプリケーション単位やプロセス単位でやるのもあり。そして、OS の性能が悪い！と愚痴るのさ。大昔、コンパイラの性能が悪い！と愚痴ったように...
経験則は告げる、いずれリソースが解決してくれる...と。そして、リソース設計者は、いつも下働きを強いられる運命にあるのさ！これも愚痴かぁ。ムーアの法則にも喰ってかかる... このぉ、人間の欲望に見透かされた法則め！
1. 並行アルゴリズムの正当性と性質
M. Ben-Ari というコンピュータ科学の教授が、並行アルゴリズムの正当性と性質を一般化したそうな。それを四つにまとめると、こんな感じ...
- プログラムとは連続したアトミックな実行文である。
- 並行プログラムは複数のスレッド内のアトミックなインタリーブである。
- アトミックな実行文のすべての組み合わせは、ここで検証する並行アルゴリズムのすべての性質を満たさなければならない。
- どのインタリーブでもスレッドの実行文が不公平に除外されることはない。
しかしながら、スレッドすべての組み合わせにおいて、結果が同じになるようにインタリーブするには、かなりの戦略がいる。それぞれのアプリケーション分野における経験値や勘所も必要である。現実には、処理順が規定されるような前後依存を持つスレッドも多く、どんなに頑張っても隅々まで並行化することはできまい。実は、最も扱いの厄介なものが、「公平性」ってやつかもしれん。人間社会と同様に...
2. タスク分解とデータ分解
ソースコードのスレッド化には、大まかに二つのモデルがあるという。「タスク分解」と「データ分解」である。おいらの場合、並列化というと、タスク分解に目がいってしまうが、データ構造とセットで考える必要がありそうだ。
更新処理が独立していれば、並列化できることはすぐにイメージできるし、既にデータ構造をそのようにしている。オブジェクト指向のカプセル化も突き詰めれば、これに通ずるものがある。画像情報のような連続性を保つ大規模なデータ配列を分割することも、効率性を考慮して既にやっている。フィルタのアルゴリズムでは、チャンク(データ分割)の概念も必要である。ただ、スレッド化という視点が抜けていた。
3. 逐次ソースコードの並行化と、そのストーリー立て...
まず、数値演算が並列化に向いていることを匂わせてくれる。いきなりπを近似する数値積分や帰納変数が飛び出し、ループのネスト構造が線形代数の行列式と重なって見えたり、そのまま DFT, FFT, FIR, IIR などの実装がイメージできたり。個人的には、数値演算ライブラリの BLAS や LAPACK を似たような感覚で利用している。
次に、並列和やプリフィックスキャンで軽く流す。この二つのアルゴリズムは、その単純さゆえに並列化の指標になっているという。
そして、MapReduce 構造に並行化を見る。Map と Reduce の二つの組み合わせは、LISP などの関数型言語、あるいは、Ruby や Python でも見かける手法である。
Map 処理は、入力データを何らかの値と組み合わせて、キーと値のペアを生成する。ペアの生成処理を完全に独立させれば、並行化が見えてくる。
Reduce 処理は、Map 処理の結果を集約して、目的に応じた結果を出力する。この二段階の処理構造によってデータがアルゴリズムから分離され、タスクの独立性が高まることを見て取れる。
さらに、ソートとサーチに主眼を置く。一昔前、CPU 時間の 80% 以上はソートに費やされると言われた。昨今、画像処理系の規模が大きくなったとはいえ、現在でもソートやサーチが重要であることに変わりはあるまい。データベースにアクセスすれば、 クエリの結果が表示され、検索エンジンにキーワードをかければ、URL 一覧が表示され、いつもソートとサーチが暗躍している。
どちらもプログラム入門で題材とされるアルゴリズムだが、スレッド化となると侮れない。ソートとサーチに限ったことではないが、いつもバックグラウンドで動作していて欲しい処理があり、そうしたすべてが並列化の対象となろう...
最後に、データの関連性を視覚化するグラフアルゴリズムに並行化を見る。二次元空間に配置されるノードとエッジからなる有限集合を想定し、これらをツリー構造で図示し、各ノードの関係を隣接行列で記述する。ノードは要素、エッジは二つのノードを連結する枝。
そして、エッジの重みの合計を最小とするアルゴリズムを並行化する。そう、グラフ理論でよく見かける最小スパニングツリー(MST: Minimum Spanning Tree)ってやつだ。MST の有名なアルゴリズムに、Kruskal 法と Prim 法がある。本書では両方の逐次コードが紹介されるが、並行化では、Prim のアルゴリズムが採用されている。どちらも重み行列と連結成分で構成されるが、Kruskal のアルゴリズムはスレッドセーフなヒープの実装が必要など、ちと面倒なようである。
4. スレッド設計の八つのルール
本書は、スレッド設計モデルに適用すべき八つの単純なルールを提示している。単純なだけに、すべてを守るのも難しそうだ。ルールは破るためにある... とは、誰の言葉かは知らんが...
ルール1: 真に独立した処理を特定する。
ルール2: 並行性はより上位で実装する。
ルール3: コア数増加に備えスケーラビリティ対応を早期に計画する。
ルール4: スレッドセーフなライブラリを使用する。
ルール5: 適切なスレッドモデルを採用する。
ルール6: 実行順序を前提としない。
ルール7: ローカル変数を使用する、できなければロックで保護する。
ルール8: 並行性向上のためのアルゴリズム変更を恐れない。
5. 性能指標
本書は、性能指標に高速化率と実行効率を挙げている。高速化率は、逐次実行と並列実行の実行時間の比率である。
実行効率は、リソースの消費効率を示し、高速化率をコア数で割って算出される。
高速化率では、 Amdahl の法則と Gustafson-Barsis の法則が紹介される。前者が、逐次ソースコードを並列化することで達成できる高速化率を予測するのに対して、後者は、既存の並列ソースコードからダイレクトに算出する。
[Amdahl の法則]
| 高速化率 ≤ | 1 (1 - pctPar) + pctPar/p |
(pctPar: 並行実行時間の割合, p: コア数)
逐次実行時間を 1 とした時、並列化前の実行時間 1 - pctPar と並列化後の実行時間 pctPar/p の合計を分母に配置して、その割合で高速化率の限界を予測する。
[Gustafson-Barsis の法則]
| 高速化率 ≤ | p + (1 - P)s |
(p: コア数, s: 並列化できない部分の逐次実行時間の割合)
コア数の増加に伴い、データ量も増加することを考慮している。コア数が増えれば、処理したいプログラムの規模が大きくなり、データ量も増えることは予測できる。
現在では、コア数とスレッド数の関係も微妙だ。当然ながら、コア数をはるかに超えるスレッド数の要求もあれば、Intel の THyper-Threading のように、1つのコアで複数のスレッドに対応する仕掛けもある。高速化率と実行効率は、コア数に対してどのくらいの量のスレッド数を起動するのが割りに合うか、という指標にはなる。
しかし、いくらタフな計算を要求されるによせ、システムが完全に乗っ取られるのは、どうであろう。内部からのイベント要求もあれば、外部からの割り込みも発生する。昔から、CPU 資源は周辺機器との取り合いの中にある。
スレッドの公平性は、あらゆるスレッドを受け付ける方向で調整するように仕組まれる。だが実は、総合的な観点から不公平性にこそシステムの合理性があるのやもしれん。いずれにせよ、システムリソースの使用率は、常に余裕を持っておきたい。人間と同様に...
0 コメント:
コメントを投稿