並列化について

質問

計算処理において、並列に出来ることと出来ないことが
あるとわかったのですが、具体的にはどういったことでしょうか？

例えば、重ねあわせが可能なら、並列化が可能といったような感じでしょうか？

ご面倒かと思いますが詳しく教えてください。
よろしくお願いします。

回答No.1

trytobe · ベストアンサー

「何か計算した結果を使わないと、次の計算ができない」という場合には、並列にできません。

でも、うまく式を変形すれば、その計算待ちの回数（段数）を減らして、同時並行で計算を分担させることができます。

人間が作業するときと同じで、分担して各部品をつくっておき、最後に持ち寄って組み立てれば完成できることがあるのです。

例えば、１＋２＋３＋４＋５＋６＋７＋８＝ を計算するときに、一つずつ足していくと、

（（（（（（（１＋２）＋３）＋４）＋５）＋６）＋７）＋８）＝

と７段階の結果待ちになります。一方で、

（（（１＋２）＋（３＋４））＋（（５＋６）＋（７＋８）））＝

と最初にペアを作って分担させれば、３段階で済みます。（そのかわりに最初の１段階目は計算を４系列に並列できなければなりません）

なお、上記は掛け算という回路を使わない前提で、足し算という同じ機能しかない場合、いくつか計算機を同時に稼動させると時間短縮ができるか、という例です。１機しかなければ、上のように順番に計算することになり、４機あれば下のように枝分かれするように分担させられるのです。

このように、計算方法＝アルゴリズムを見直すことで、並列化＝同時計算・分散コンピューティングができる可能性が生まれるわけです。