3

一般にプログラムを並列化してもある程度で計算速度は頭打ちになると知りました。けれどそれは、ハードウェア記述言語でも同じことですか?

2 件の回答 2

3

成り立ちます。アムダールの法則(Amdahl's law)とは具体的な実現方式について述べたものでなく、あらゆる並列処理に対して普遍的に成り立つ法則です。

アムダールの法則は、逐次処理だと所要時間Tを要するタスク(解決したい計算問題)に対して、本質的に逐次処理が不可欠なサブタスクTsと並列処理可能なサブタスクTpとに2分したとき、「N個のプロセッサで並列処理したら理論上どれだけ所要時間を短縮可能か?」を予測するために用いられます。 逐次処理でのサブタスクTs:Tpの比率が(1-p):pのとき、つまり与えられたタスクのうちp(0≦p≦1)だけが並列化可能なとき、N並列処理での理論下限処理時間Tnは次式で求まります。

Tn = T * ((1 - p) + p / N)

例)全体の80%が並列化可能(残り20%は逐次処理が必須)なタスクを4並列処理する場合、p=0.8, N=4よりTn = (0.2+0.8/4)T = 0.4T、つまり逐次処理に比べて「40%の処理時間で済む=2.5倍速く処理可能」なことを示します。この結果は、見方によっては「4並列で処理しても2.5倍しか速くならない」ことも示唆しています。さらに推し進めて"無限の並列度"(N=∞)で並列処理した場合でさえTn = 0.2Tを下回らない、すなわち「このタスクを5倍以上高速化することは原理的に不可能」と分かります。

なお、アムダールの法則から求まるのはあくまで理論値であり、現実には並列による処理オーバーヘッドが必ず存在します。この並列化オーバーヘッドの存在により、並列度Nを増やしていくと性能が頭打ちになるどころか、逆に並列度を増やすほど性能劣化につながるケースも多々あります。

(ごく一部の並列処理では"超線形(super linear)特性"を示す例外もありますがここでは無視します)

3

アムダールの法則は、ハードウェア構成にも同じことがいえます。というか、区別すべき物でもないような気がします。

待ち合わせするようなロジックが組まれている場合は、全体の処理時間の最小は当然その処理時間に拘束されます。例えば、入力が一塊になっているシリアルデータを扱うのであれば、回路がデータを記憶域に乗せるまで、別の処理を待たせているような状態になり、全体の処理はその時間より小さくなりません。ハードウェア記述言語での記述、というか、ストリーム・プロセッシングで特異なのは、処理を時間ではなく奥行きのある空間で考えられることですが、これは複数コアの汎用CPUにあわせた、別の言語によるプログラミングとそう変わりはないでしょう。

考えつくところで大きな違いは2つ、クロックの扱いと収穫逓減の違い、があると思います。一般にいうCPUを介したプログラムでは、処理の最小の時間単位として動作クロックが存在していますが、ハードウェアのデザインの視点から見たクロック信号はどちらかといえば処理の最長時間の基準になる物です(ロジックを詰め込むという発想から)。また、FPGA などを利用して数百のロジックを並列化する場合、汎用CPUを並べるよりも並列処理による効率向上の減衰(Diminishing returns)がとても低くなるので、非常に小さな処理を、重さにあわせて多数はめ込み積み上げるような職人技が有効になってくるのでしょう。

この質問に回答するには、ログインする必要があります。