"インテルスレッディング・ビルディング・ブロック" James Reinders 著

バッハのカンタータを BGM にフィーヌ・ブルゴーニュをやりながら、マイク・ガンカーズの本(前々記事)や、ブライアン・カーニハンとロブ・パイクの本(前記事)でコンピュータ哲学の郷愁に浸っていると、またもや本棚の奥底から考古学的な書物が出土された。オライリー君の本は、手っ取り早く手段を習得し、そしてそのまま... という群れが、納戸の一画を占拠してやがる。コレクションってやつは、集めるという行為の方が目的となって、知識を深めようという本来の目的を見失わせるところがある。
本書もその例に漏れず、満載されたコード事例を辞書代わりに用い、著者が力説する思いについては読み飛ばしたことだろう。仕事が忙しい！とは、威厳をまとった実に都合のよい言い訳である。こうして古書を漁ってノスタルジアに耽り、おまけに、これをネタにお喋りがかっぱえびせん状態になるのも、引退勧告を受け入れているようなものか...

さて、Intel Threading Building Blocks(TBB)とは、C++ の STL を拡張した並列処理用テンプレートライブラリであり、こいつがプログラマのための書であることは言うまでもない。
しかしながら、おいらはプログラマではない。むかーし五年間ほど、リアルタイム OS を書いていた時期があるものの、あくまでもハードウェア設計者であり、専門はプロセッサである。特定用途向けの CPU や DSP など。
とはいえ、効率的で合理的なシステムを構築する上で、ハードウェア側からの視点だけでは不十分である。それは、ソフトウェア設計者とて同じことだろう。
かつて、CPU パフォーマンスを最大限に引き出すためにアセンブラ言語で書き、また、高性能なコンパイラを求めた。今でこそ低水準な扱いを受ける C 言語だが、当時は高級言語として輝き、実装では物足りないほどであった。特にリアルタイム性の厳しい組込み系システムでは、ハードウェアとソフトウェアが協調してカスタマイズされる。命令セットやタスクの同期、あるいは割り込みといった機能を。
やがて、ムーアの法則に従い半導体の性能そのものが向上すると、汎用的なリアルタイム OS によって抽象化が進んだ。アプリケーション設計者は余計なことを考えずに済み、タスク設計に傾注できるようになったのである。
そして、プロセッサのマルチコア化が進むと、言語システムのレベルでマルチスレッド用ライブラリが整備されるとは、凄い時代だなぁ... などと思い本書を手に取ったのが、十年ぐらい前であろうか...
ところで、抽象化ってやつは、恐ろしい戦略である。おまじないを書いただけで、なんとなく動いてしまうし、それで理解した気分にもなれる。プログラミング言語には、おまじないめいた記述が実に多い。その代表といえば、"stdio.h" であろう。アセンブラ言語にも、ハードウェアを定義するためのおまじないがある。これらのおまじないは、時にはテーブルと呼ばれ、時にはやライブラリと呼ばれる。そして、STL を置き換えるように記述する TBB もまた、おまじないめいている。
ちなみに、ライブラリの中身を読むことが、プログラミング言語の習得における良い方法の一つと言えよう。なにしろ達人が書いたコードなのだから。ただ、書き方をパクるのではなく、考え方をパクりたい...

コンピューティングの並列思考そのものは古く、個人的にも三十年前には触れていた。メインフレームがそれだ。当時、TSS(Time Sharing System)という用語が流行った。メインフレーム設計者たちは、キャッシュのアルゴリズムだけが妙に詳しかったり、命令セットの効率性ばかりを追求したり、システムバスのアーキテクチャに執念を燃やしたりと専門技術が細分化され、全体構造となると意外と理解していなかった。
そして今日、パソコンや携帯端末のレベルでマルチコア化が進み、おまけに、マルチスレッド環境までも当たり前になると、もはや専門技術に執着している場合ではあるまい。
ただ、マルチタスクだから、マルチスレッドだからといって、必ずしもパフォーマンスが向上するわけではない。実際、シングルで処理した方が速いケースも少なくない。それは、開発プロジェクトのように、いくら技術者を増員しても日程が縮まらないばかりか、かえって無駄な管理作業を増やして混乱させる状況に似ている。それでも、人海戦術のお好きなお偉いさんをよく見かけるけど。
シングルタスクで十分な処理でも、マルチタスク OS 上で実行させることのメリットはある。例外処理やハードウェア割り込み、あるいは、システム暴走の抑制などの監視機能を、OS 側に任せることができるのだから。
例えば、ファクトリーオートメーションのような分野では、常に製造工程を監視する必要があり、マルチタスクの恩恵をかなり受けている。バックアップ電源が整備されているとはいえ、災害などで起こるイレギュラーなシャットダウンなども考慮される。シングルタスクの時代には、一つのプログラムがシステム全体をよくクラッシュさせていたのである。
そういえば、むかーし、ネイティブコードにこだわるお偉いさんがいた。スクリプト言語がまだ地位を獲得していない時代、技術雑誌に実行効率の側面から言語システムの比較が掲載されると、流行り用語に群がり、開発効率よりも優先させるから頭が痛い！信頼性までも向上すると思い込むようで、おいらはネイティブおじさんと呼んでいた。
そして今、ネイティブスレッドにこだわるお偉いさんがいる...

1. 並列思考
並列思考の基本的な戦略に、パイプライン時分割処理がある。まず、一つの流れ作業を分割してパイプライン化し、複数の流れ作業を時間単位で同時に処理できるようにする。このとき重要なのは、それぞれの作業に待ち時間が生じないように分割単位を一定時間でスライスすること。この一つの流れ作業がタスクであり、分割した単位がスレッドということになる。
そして、スレッドの単位をいかに効率的にマッピングできるかは、プロセッサとの相談ということになるが、アプリケーション設計者が、いちいちプロセッサのご機嫌伺いをしている場合ではない。
そこで、TBB は、そんなことを意識せずとも、自動的にスレッドマッピングをやってくれるというのだから、なんとも狐につままれたような... そんな気分になった記憶が蘇る。
マルチコア環境を与えられれば、それぞれのコアにタスクを割り当てて同時に処理しようと、誰でも考えるだろう。メモリ領域さえ互いに侵さなければ、大した問題にはならないはず。それでもリソースの競合は起こるけど。
さらに、一つのタスクをスレッドに分割して、これを並列で処理しようというのだから尋常ではない。当然ながら、メモリ競合やデッドロックの問題を深刻化させ、スレッドの前後関係などシーケンスの問題までも生じる。
ここで重要な概念は、タイムスライスとウィンドウ(時間幅)、そして、分割の正当性の検証ということになろう。実際、キャッシュの方がはるかに役立つ場面は少なくない。キャッシュで済むなら、わざわざマルチスレッドなんて高度な技を持ち出さなくとも。
ただ、キャッシュはキャッシュで、単純に未使用期間でデータを退避させているわけではなく、連想方式を組み合わせたりと様々な工夫がなされる。
TBB は、タスクとデータの不必要な移動を避けるようにキャッシュアクセスまでも考慮されているという。自動生成されたスレッドがキャッシュと相性がいいのは、なんとも心強い。
プロセッサ効率の最も良いケースは、演算処理が主体となるプログラムで、一つの物理スレッドに一つの論理スレッドがマッピングされているような状況である。
では、TBBってやつは、プロセッサのスレッド構造だけでなく、キャッシュ構造までも知っているというのか？
ただ、いくらハードウェア構造を知り尽くしているとしても、コンパイラが万能とは考えにくい。ロックを避ける価値は大いにあるが、デバックを困難にしかねない。TBB は、ロックの必要性を軽減してくれるが、ロックから解放してくれるわけではなさそうである。デッドロックと競合をいかに回避するかという問題はいつまでもつきまとうだろうし、メモリアロケートの問題もまた、最も悩ましい問題の一つとしてあり続けるだろう...
「プログラミングの真理の1つは、最良の直列アルゴリズムが最良の並列アルゴリズムであることはめったになく、その逆もまためったにない...」

2. スケジューリングと parallel_for
パイプラインの処理能力は、スライスしたトークンによって制限される。パイプラインが ｎ 個のトークンで構成される場合、ｎ より多くの操作を並列に実行することはできない。ｎ値が低すぎると並列性が悪くなり、高すぎるとバッファなどのリソースを浪費する。
また、処理時間の最も遅い直列ステージに引っ張られる。それはプログラムだけでなく、システム I/O やネットワークポートなどのリソースである場合も多々ある。
最適なウィンドウサイズを模索するのは、実に骨が折れる。この面倒な作業を誰かが代替してくれるなら、並列処理は病みつきになりそう。スレッドではなく、タスクで考えるという安心感を与えてくれれれば...
本書は、その醍醐味を語るために、parallel_for テンプレートを中心的な話題にしている。タスク・スケジューラという高度な方法も提供されるが、まずは parallel_for を検討してみては... と勧めてくれる。
「なぜクィックソートのような再帰的なアルゴリズムが再帰テンプレートを使用する代わりに parallel_for テンプレートを使用すべきなのかを理解したとき、アプリケーションにスレッディング・ビルディング・ブロックを実装する方法を理解したことになる...」
ここで注目したいのは、「再帰連鎖反応」という概念である。スケジューラは、ツリー構造のタスクグラフで最も効率良く動作するという。それは、幅優先のスチールと深さ優先の作業という両面の戦略が最もうまく適用できるからであると。
例えば、マスタータスクが n 個の子を直接生成するには、O(n) ステップ必要だが、ツリー構造のフォークでは O(log n) ステップあればいい。ただ、ドメインがツリー構造でないことがよくある。それでもツリーマップは可能で、parallel_for は反復空間で動作し、バイナリーツリーに再帰的にマップするという。こうした並列思考の根底にアムダールの法則を匂わせ、直列ステージをなるべく減らしたいという動機を誘う。
ちなみに、コンピュータアーキテクトのジーン・アムダール氏はこう言ったそうな。
「ほぼ同じ大きさの直列処理の速度が改善されないのであれば、並列処理の速度を改善しようとする労力は無駄になる。」