負荷分散

負荷分散は, 1箇所に負荷が固まると, その他の理由がなくてもこれ以上性能 が向上しないという上限を与える. これに関しては, 我々のタスク分散の方式 から, 文の長さが長い時( の時)にはそれほど悪くない, と簡単に いえる. 荒い近似として, 「各 を求めるのにかかる処理が大体一 定」と仮定し, その一定値をCとする.

j - i = kとなる がn - k + 1個あり, それぞれが, (k - 1)C だけの処理をすることで求まるから, 全体では,

だけの処理量である. ちょっと計算するともっとも割り当てられる処理の多い プロセッサにも, 高々

だけしか割り当てられないことがわかる. nが大きければ, 全体の処理量を pで割ったものと, この値との比は1に近付く.