たとえばなしで見る誇張の少ない「並行」と「並列」
まえおき
参考
前回の記事では「並行の間違った理解を正すため」に分かりやすさを優先し若干(相当)誇張を入れて「間違いとは言いきれないけれども必ずしも正しいとも言えない」形で並行計算と並列計算を定義しました。
特に並列計算については記事の本題ではなかったために相当に雑な定義となっていました。その件に関していくらか指摘もありましたので、ある種の責任を果たすために前回よりももう少し真面目にその差異を示しておこうと思います。
ただ読み始める前に、大前提として並行計算と並列計算という言葉は使う箇所、すなわち必要とされるシーンが異なっているために差異を考えるという行為それ事態にあまり意味がありません。見た目や一部の性質は似ていても必要とされるシーンは大きく異なる言葉なんだということを念頭に置いた上で以下を読んでください。
ちなみに私はちょっとハードウェアにも詳しいソフトウェアエンジニアという視点を持っています。
TL;DR
- 並行計算と並列計算に共通する性質
- 大タスクを小タスクに分解して計算処理する
- 複数プロセッサで計算処理することでパフォーマンスの向上が期待できる
- 並行計算特有の性質
- 小タスク間の依存(≒相互作用)があったりなかったりする
- プロセッサが多いほど大タスクの完了にかかる時間が短くなる(≒応答性の改善)
- 並列計算特有の性質
- 小タスクは互いに独立している(=依存はない)
- プロセッサが多いほど単位時間に計算処理可能な大タスクのサイズが増す(≒スループットの改善)
たとえばなし: 年賀状編
そろそろ年末ということで年賀状を準備している人もいるかと思います(私は年賀状を書かなくなって長いのですが)。年賀状を出すという問題を解決するまでに必要な工程を考えてみましょう。
- 年賀状を買う
- 印刷に必要な材料(プリンタのインクとか)を買う
- 図案を(考えて)決定する
- 印刷する
- 宛名書きする
- ポストに投函する
今どきはデータ入稿で出すところまで全部やってくれるサービスもありますが、まぁそこは年に一度のご挨拶というぬくもりにあふれた作業ということで無視してください。
こうやって分けた工程は頭から順番に逐次的に実施すれば問題は解決します。ある工程は前段までの工程が終わっていることが開始条件になります。年賀状を買ってきても図案が決まらなければ印刷は開始できませんよね。一方でいくつかの工程には依存関係がないか弱かったりで前段の工程が完全に完了する前に開始できます。
1と2の買い物は3の図案を考えながらでも行え、時間が節約できます。さらにもしも1と2の買う場所が別でパートナーがいるならば手分けして買い物をすることで所要時間が短くなります。1,2,3が済めば4の印刷を開始できますが、5の宛名書きは全部の印刷が終わるのを待つまでもなく1枚印刷できた時点で始められます。6も同様に宛名を書き終わったものから順にポストへ投函できますが、ポストまで往復することを考えれば普通は5の宛名書きが全部終わってから行ったほうが労力的な効率は良いでしょう。
これが並行計算です。このように単一プロセッサでも実施はできますが、複数プロセッサにより問題解決全体にかかる所要時間が短くなるようにするのが並行です。場合によっては複数プロセッサを導入できない、利用可能な全プロセッサを活かしきれない工程も存在します。
さてここで4の印刷という工程に注目してみましょう。プリンタで印刷するとして仮に1分に5枚印刷でき全部で300枚印刷するならば、全てを印刷するまでにかかる時間は60分です。しかし同じ性能のプリンタをもう1台追加できるなら30分で済みます。1枚を印刷するという工程は別の1枚を印刷する工程に依存してないからです。さらに1台追加して3台体制で印刷できるならば20分で300枚の印刷が完了します。
もうひとつ5の宛名書きという工程に注目しましょう。仮に1枚の宛名(と短い相手毎の挨拶)を書くのに1分かかるとすれば300枚を書くには300分かかってしまいますね。しかし5人で作業を分担するならば60分で書き終わる算段が付けられます。こちらも1枚の宛名を書くという工程同士の依存がないのです。つまりもしも15人で取り掛かれるのならば20分で300枚の宛名書きが完了します。
これが並列計算です。プロセッサを増やすことで単位時間あたりに処理可能な仕事量=スループットがリニアに増え、結果的に全工程にかかる時間が短くなります。
この例でみたように並行と並列は1つの問題に共存しえます。もちろんここで設定した問題は一人=単一プロセッサで逐次的な解決もできます。
たとえばなし: 現代的なCPU編
別の記事でCPU(M1)に付いて書いたので、ちょっとそれになぞらえてもう一例考えてみましょう。CPUの1つのコアが命令を実行する際にはおおまかに以下の工程≒パイプラインを経る必要があります。
- フェッチ: メモリから命令を読みだす
- デコード: 命令を解釈し必要なデータを揃える
- 実行: 命令を実行する
- 書き戻し: 計算結果を格納する
先の記事ではIPC=サイクルあたりの命令実行数あたりに着目しました。これは全工程を複数命令に対して同時に行う=並列に行うという意味です。M1の例ですと最大8個の命令を同時にフェッチして、デコードして、実行して、書き戻すことができます。命令間の依存関係がありますから常に8個ずつということではありませんし、実行に関しては最大630命令同時に捌ける可能性があります。
さらにこうやって実行する命令間には依存があったりなかったりします。ある命令が前の命令の実行結果に依存したりしなかったりするという意味です。その依存関係を考慮して破綻の無い範囲で実行順序を入れ替えて可能な限り並列計算する命令を多くする仕組みがアウト・オブ・オーダー実行というやつです。この並べ替えそのものは並行計算に属する技術といってよいでしょう。
ここまではただ1つの命令がパイプラインを通過する場合の話です。フェッチから書き戻しまでの4工程は逐次手続きで、よくある並行計算の誤解例と同じなのですがその内側には並列も並行も両方とも内包していました。しかし話はここでは終わりません。
ある命令をフェッチし終わりデコードを始めたら、フェッチを担当する領域≒プロセッサはどうするのが効率良いでしょうか? そうです遊ばせておくのはもったいないので次の命令をフェッチします。1つ前の命令のデコードと現在の命令のフェッチは独立した作業=並列計算と言えます。
プログラマであれば条件分岐のifを知っているでしょう。この条件分岐がCPU内の実行工程で発生したとき、それまでに済んでいる先読みに相当するフェッチとデコードはキャンセルされ無駄になります。これは命令間に依存があった一例で、前述の並列計算の前提条件が崩れる並行計算的な相互作用によるものです。このレイヤでも並列と並行が共存し始めましたね。
ここまではシングルコアの内部で起こる話でした。次はマルチコアで考えてみましょう。各コアはそれぞれ独立して命令を実行していきます。完全に並列です。その状況であるコアがI/Oを占有して…例えばファイルを書いたとしましょう。この時、別のコアも同じファイルを書いてしまえばおそらくひどいことが起こります。そのため通常は排他制御が必要です。この排他制御を伴ったリソースアクセスという課題は並行計算のものです。また並列と並行が共存し始めましたね。
このようにCPUの中で起こりうることをざっと概観しただけで三層にわたって並列計算的な事象と並行計算的な事象が共存しているのが観測できました。ちなみにここでの並行・並列の分類は「計算」視点によるもので、CPUを設計する視点で語る際には全部を並列と呼んでいる気がします。
まとめ
並行・並列計算の混在例を2つの例で紹介してみました。「これは並行だ」「いや並列だ」と明確に分けた話ではないのですが、おおよそどういうものを並行や並列と捉えているかの紹介にはなったかと思います。また事前に示したそれぞれの性質について例を通して検討・理解を進めていただけたらなと思います。
以下は蛇足
蛇足: 個人的な体験に基づくはなし
並行計算はボトムアップ的に使う・作ることが多いです。既存・既知の小タスクがあって、それらを良い感じに組み合わせて目的の大タスクを効率よく実行できるようにする、みたいな。具体的にはCIでビルドやドキュメント生成を並行化しつつテストはビルド後に並列化して全体として短い実行時間で終わるようにするとか。
一方で並列計算はトップダウン的に決まることが多いです。たとえばレイトレーシングをするときに個々のピクセル値の計算は別のピクセル値に依存しませんが、最初は逐次的に計算するようにしました。そのあとやはり依存してないのだからとラスタラインごとに並列計算するように改めました。ただコレを実現しているのはGoのgoroutineという並行計算のための機能ですね。
Discussion