SuperPIとライトアロケートキャッシュ


K6派の人々にとってとても不思議だったことのひとつにSuperPIとライトアロケートキャッシュの関係があります。

ライトアロケート機能は、K6の懐刀のひとつで、これをオンにすると実行速度が3-5%あがります。これは大体1クラス上のCPUを買った場合と同じですから非常に重宝された機能です。このキャッシュ機能はL1データキャッシュに適用されます。普通のデータキャッシュだと書き込み時にキャッシュにヒットしない場合、キャッシュ自身は変化させずに単にデータをメモリーに書き込んでしまいます。しかし、ライトアロケート機能を使うと、書き込み時にキャッシュにヒットしない場合、一度メモリー上のデータをキャッシュに読み込みます。これは「書き込みがおきたメモリーアドレス近辺では、データアクセスが再発生する確率が高い」という統計的な事実に基づくものです。いったんキャッシュに読み込んでおけば何かに使えるだろうと言う発想ですね。実際サブルーチンの先頭でメモリーの初期化を行う場合など、この仮定が成立する場合は非常に多くあります。

ところが、なぜかSuperPIではライトアロケート機能を使うと遅くなりました。ライトアロケート機能はランダムライトに非常に弱いので「SuperPIにもランダムライトがあるんじゃないか」などといわれました。で、本当にあるのでしょうか?

円周率の計算には四則と平方根の計算が出てきます。多桁の計算は、多桁の数を分割して数桁ずつ倍精度浮動小数点数にパックして行います。このパックした浮動小数点数を配列に格納し、順に足していけば加算ができますし、逆の減算も簡単です。この場合桁上げ処理を考えてもこの加減算にはランダムライトはありません。除算と平方根は加減乗の組み合わせで実現できますから、あとは乗算にランダムライトがあるかどうか調べることになります。

多桁の乗算は筆算式では行いません。もし力ずくでやると途方も無い時間がかかります。そこで、FFTと逆FFTを使って計算をおこないます。手順としては

  1. 乗数と被乗数をそれぞれFFTにかける
  2. FFTの結果の要素同士を掛け合わせる
  3. その結果に逆FFTを施す
  4. 桁上げ処理をする

要素同士の掛け算は読んで計算して書き込みですからランダムライトはありません。アクセスも順アクセスです。桁上げ処理も同じです。残るFFTと逆FFTですが、この二つは実は同じ演算ですので、ここではFFTだけ見ましょう。

FFTは二つの部分に別れます。FFT本体とビット逆順アクセスです。FFT本体は配列を飛び飛びにアクセスすることはありますが、どの番地に対しても必ず読み出し、計算、書き込みの順で処理をしますので、ライトアロケートが発生するようなランダムライトはありません。となると、ビット逆順アクセスです。これがビンゴでして、ビット逆順アドレスには次の二つの方法があります。

ビンゴ。どうやら後者を使っているようです。が、ここで大どんでん返しがあります。FFTと逆FFTをうまく組み合わせると、多桁の乗算の場合に限ってビット反転アクセスは不要になるのです(あ〜れ〜っ)。

机上の寝言ということで、「SuperPIって本当はその辺手を抜いてんじゃないの?」というおとろしい疑問が今日の寝言です(^^;


参考URL

FFT と AGM による円周率計算プログラム
国内最強のFFTページを擁する、大浦氏のサイトです。
FPU・SIMD濃緑研究所
FPU/3DNow!/SSEで遊んでいます(^^)