2940


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


CC BY-SA 3.0
2014-12-31T17:19:12.853
2863
2017-05-21T23:24:27.397
2017-05-21T23:24:27.397
19110
question
vhdl hdl
ハードウェア記述言語でのプログラムの並列化でもアムダールの法則は成り立ちますか？


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

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

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


CC BY-SA 3.0
2015-01-01T05:37:03.173
2886
2015-01-01T06:18:23.230
2015-01-01T06:18:23.230
4978
4978
2863
answer


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

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

[code]

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

例）全体の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)特性"を示す例外もありますがここでは無視します）


CC BY-SA 3.0
2015-01-02T06:49:03.920
2940
2015-01-02T07:06:19.393
2015-01-02T07:06:19.393
49
49
2863
answer