アルゴリズム 並列処理の限界？アムダールの法則を解説
計算機の処理を速くするために、複数の処理装置で同時に作業を行う方法を並列処理と言います。アムダールの法則とは、この並列処理を施した際に、処理全体がどれくらい速くなるかを予測する法則です。理想的には、処理装置の数を増やせば増やすほど作業は速く終わるように思えます。しかし、プログラムの中には、どうしても順番に処理しなければならない部分があります。例えば、前の作業の結果を使って次の作業を行う場合などです。このような部分は、いくら処理装置を増やしても速くなりません。アムダールの法則は、この並列処理できない部分が全体の処理速度にどう影響するかを示してくれます。
アムダールの法則を使うと、並列処理できる部分の割合と処理装置の数から、全体の処理速度の向上率を計算できます。例えば、プログラム全体のうち90%が並列処理でき、10%が並列処理できないとします。このプログラムを10個の処理装置で実行した場合、どれくらい速くなるでしょうか。アムダールの法則によれば、並列処理できない部分が全体の速度向上を制限するため、処理装置をいくら増やしても、10倍以上には速くなりません。具体的には、計算によって向上率の上限が分かります。
アムダールの法則は、並列処理による性能向上の効果をあらかじめ予測し、最適な処理装置の数などを検討する際に役立ちます。並列処理は、近年の計算機システムにおいて欠かせない技術です。しかし、その効果を最大限に引き出すためには、アムダールの法則を理解し、プログラムのどの部分が並列処理できて、どの部分が並列処理できないかをきちんと見極める必要があります。並列処理できない部分をいかに減らせるかが、処理全体を速くするための重要な鍵となります。
