特徴ある並列処理

つぎのグラフでエラトステネス法の特徴を説明する。このグラフ
は１台のＣＰＵ４００ＭＨｚメモリ１２８ＭＢ相当のＰＣによる
実験例である。
横軸はメモリ使用量（１Ｋ−１００ＭＢ）で縦軸は１台のＰＣに
よる計算時間である。数値の範囲は１０の９乗から１２乗までで
ある。エラトステネス法では大量のメモリを使用する。　数値が
１０の９乗であれば１２５ＭＢ、１０の１２乗であれば１２ＧＢ
必要であり、並列処理により、データを分散させて計算する。
たとえば、１０の９乗までの計算で、等分割１０台で並列処理し、
900000000-1000000000の間の素数を計算すると１２．５ＭＢの
メモリを使い、処理時間は２１秒となる。分割数を大きくし、最
後の範囲のみに注目し、プロットしたグラフである。



メモリ使用量が５００−５００００バイト（５０ＫＢ）までは
メモリ使用量に比例して計算時間が増加する。しかし、そこから
３Ｍ−１００ＭＢまでは計算時間は増加しない。その後、メモリ
使用量が増すと、またまた増加に転じる。

この現象はキャッシュ、メモリ、ディスクの処理時間で説明でき
る。最初の増加部分はキャッシュでの処理であり、つぎのフラッ
ト部分はキャッシュとメモリでの処理であり、最後の増加部分は
ディスクスワップ処理となる。大量のメモリをとびとびにアクセ
スする問題ではこの例のような現象となる。