クリティカルパス長

pが 程度, つまりいわゆる並列度が少ない状態を考える. このような場 合, このアルゴリズムが終了するまでの時間は, 必要な処理の量(割るプロセッ サ数)ではなく, クリティカルパス長, つまり, 全体として並列化していない (あるいはできない)部分の処理の長さで決まるようになる.

具体的には, 「 を求めるには, および が求まっ ていなくてはならない」という規則が, 絶対に同時には実行され得ない処理 (依存し合う処理)を生み出す. その長さは, いくらプロセッサ台数を増やして, 通信オーバーヘッドを零にしても, 縮めることはできない. これは, 比較的短 い文をたくさんのプロセッサで処理する状況( )を近似してい る. 実際, 文の長さが25程度で, プロセッサ数256台, などという時には以下 の考察が役に立つ.

再び, と を与えられて, そこからそれらを通信で取り寄せ て, を求めるまでにかかる時間を, 一定値Mとする. 今,

とすると, を求めるのに, と が必要なことか ら,

および,

がわかる. ここから,

がいえる. 特に,

がいえる. ここから,

がいえる. すなわち, が求まるまでに, (n-1)Mかかる. しかしこ れは, 逐次での計算量 に比べると, オーダーが さがっており, 使用しているプロセッサ数(1/2 N(N-1))を損なう値にはなっていない.