RISTニュース No．
５７（２０１４）

高速フリエ変換におけるキャッシュ最適化

筑波大学システム情報系（計算科学研究センター）
高橋 大介
高速フーリエ変換（ 、）は、科学技術計算において今日広く用いられているアルゴリズムである。本稿ではにおけるキャッシュ最適化について述べる。まず、離散フーリエ変換（
、）の定義を示した後にの基本的な考え方について説明する。さらに、




シュブロッキングが






アルゴリズムについて説明した後、キャッに対して適用できることを示す。

１．はじめにが重要になる。ここで、キャッシュミスの回高 速 フ ー リ エ 変 換（

数を減らすことができれば、主記憶のアクセ 、）は、離 散 フ ー リ エ 変 換

ス回数を減らすうえで非常に効果があるとい（える。

、）を高速

本稿では、におけるキャッシュ最適化に計算するアルゴリズムとして知られている。

について述べる。

は１９６５年のと
［１］の論２．離散フーリエ変換

文によって一般に広く知られるようになったが、１８０５年頃に
が同様のアルゴリズム

n点のデータに対するは次式で定義さを独自に発見していた［２］。

れる。

多くのアルゴリズムは処理するデータがキャッシュメモリに載っている場合には高（１）い性能を示す。しかし、問題サイズがキャッシュメモリのサイズより大きくなった場合においては著しい性能の低下をきたす。ア

また、n点のデータに対する離散フーリエルゴリズムにおける１つの目標は、いかにし変換（  、てキャッシュミスの回数を減らすかというこ逆）は次式で定義される。とにある。
近年のプロセッサの演算速度に対する主記憶のアクセス速度は相対的に遅くなってきて（２）おり、主記憶のアクセス回数を減らすことは、より重要になっている。したがって、キャッシュメモリを搭載したプロセッサにおこ こ で、x（）
お よ びy（）は複素数の値であけるアルゴリズムでは、演算回数だけでり、
である。

式（１）において、例えばn=４のとき、はなく、主記憶のアクセス回数も減らすこと−−RISTニュース No．
５７（２０１４）は以下のように計算できる。

（３）

（７）

式（３）は行列を用いれば、より簡単に（４）（８）と行列ベクトル積の形で表すことができる。
式（１）において、x（）、（y ）およびωは複素数の値であることから、この式の行列ベクトル積を計算するためには、n回の複素数乗式（７）、（８）におけるn２点は、直接算とn（n-１）回の複素数加算が必要となるこ

計算するとn４回の複素数乗算と（n２）（nとが分かる。

２１）回の複素数加算で計算できることから、この分解により計算量が約１２になること

３．高速フーリエ変換が分かる。さらに、nが２のべきである場合

３．
１ 基本的な考え方には、この分解を再帰的に行うことで、最終式（１）においてnが２で割り切れる場合に的には２点に帰着させることができ、そは、n点のデータをn２点の前半部分とn２n）に削減することがの結果演算量をO（n点の後半部分に分解することにより、n点可能になる。

は以下のように表すことができる。

の分解には、式（５）のようにn点のデータをn２点の前半部分とn２点の後半部分に 分 解 す る 周 波 数 間 引 き（ ）と、n点のデータを偶数番目と奇（５）数番目に分解する時間間引き（ ）の方法があるが、どちらの方法でも演算量は同じになる。
式（７）、（８）の考え方を素直にコーディン式（５）において、x（n２）に掛かっているは、グすると、図１のような再帰呼び出しによる周波数間引きルーチンが書ける。

より、（６）となる。
したがって、
が偶数の場合と奇数の場合に分けると、n点は以下のように２つのn２点に分解できる。
−−

RISTニュース No．
５７（２０１４）

図１

再帰呼び出しによる周波数間引きルーチンこのルーチンでは、nが２のべきである場合
n回の再帰呼び出しが行われるが、１回の呼び出し毎にn２回の複素数乗算とn回の複素数加減算が行われるので、結局O（nn）回 の 演 算 量 に な る こ と が 分 か る。また、このルーチンでは最内側ループにおいて毎回

、


関数を呼び出して三角関数の値を計算しているが、高速化のためにはあらかじめこれらの値を計算しておきテーブル図２にするなどの工夫を行うことが多い。
なお、逆

を求めるには



３．
１節で示したルーチンにおける再帰と計算している部分の符号を反転させ



周波数間引き

 

ルーチンとして計算を行い、計算結果呼び出しをループに書き換えることにより、




 
アルゴリズム［１］としてよくを１n倍すればよい。

知られているアルゴリズムが導かれる。
３．
２  ア ル ゴ リ ズ ム と図２に周波数間引き

 


 アルゴリズム

ルー

 
アルゴリズムでチンを示す。
は、入力データは出力データに上書きされる−−

RISTニュース No．
５７（２０１４）（）という特徴がある。

算することにより、キャッシュミスを少なくその一方で
 アルゴリズムでできるのが特徴である。

は、出 力 デ ー タ の 順 序 が ビ ッ ト 反 転（n点を計算する際にnn×nと分解で）して得られた順序になる。出力デきるものとすると、式（１）におけるおよびータの順序を入力データと同じにするために
は、は、ビット反転して得られた順序を元通りに（９）並べ替えることが必要になるが、この並び替えはメモリアクセスの局所性が低いことからと書くことができる。そのとき、式（１）のx

キ ャ ッ シ ュ ミ ス が 多 発 す る。さ ら に、とyは次のような二次元配列（ アルゴリズムの最内側ループで表すことができる。

）

では２のべき乗飛びのストライドアクセスになっていることから、キャッシュラインコンフリクトも多発する。したがって、階層型メ（１０）モリを意識した場合、




 
アルゴ
リズムは必ずしも好ましいアルゴリズムではない。

したがって式（１）は式（１１）のように変 
のアルゴリズムは、入力デ形できる。

ータは出力データに上書きされる、いわゆるアルゴリズムであったが、入力データ と 出 力 デ ー タ を 別 の 配 列 に す る






（１１）



アルゴリズムを構成することもできる。



 アルゴリズムとしてよく知られ７］ているのは、 アルゴリズム［３

式（１１）から次に示されるような、である。

アルゴリズム［４５］が導かれる。

１：転置
 アルゴリズムでは、入力データが 出 力 デ ー タ に 上 書 き で き な い た め、 アルゴリズムに比べて必要と
２：n組のn点

なるメモリ容量が２倍になる。しかし、最内側ループが連続アクセスになっており、またビット反転順に並べ替える処理が不要になっている。したがって、階層型メモリへの適合性という観点からは、 アルゴリズ
ムが アルゴリズムに比べて有
３：ひねり係数の乗算利であるといえる。
４．



４：転置アルゴリズム

キャッシュメモリを有効に活用することのできる、







アルゴリズム［４５］について説明する。





アルゴリズ

ムでは、一次元を二次元表現で表して計−−

RISTニュース No．
５７（２０１４）
５：n組のn点

６：転置



３ に お け るは、ひ ね り 係 数［６］と呼ばれる１の原始根であり、複素数である。図３に







アルゴリズムを示す。

１および４において行列の転置を行っているが、これは

２および５におけるのメモリアクセスを連続にするためである。さらに、

６の行列の転置は入力データと出力データの順序を同じにするために必要になる。






において、

１、４、６の行列の転置および、
３のひねり係数の乗算をブロック化した







アルゴリズムが文献［５］に示されている。しかし、
こ のア ル ゴ リ ズ ム で は の部分と行列の転置の部分が分離されているため、



においてキャッシュメモリに載っていたデータが行列の転置の際に有効に再利用されないという問題点が図３ある。ここで、３回の行列の転置がキャッ


アルゴリズムシュメモリを搭載した計算機においてボトルアルゴリズムは以下のようになる。

ネックとなる。


１：
nn×nの大きさの複素数配列
５．ブロック










アルゴリズムに入力データが入っているとする。このとにおいて、さらにキャッシュき、n×nの大きさの配列からn列ずつデ内のデータを有効に再利用し、キャッシュミータを転置しながら、n×nの大きさの作業スの回数を少なくするため、





で用配列

に転送する。ここでブロックサと行列イズnは配列
が２キャッシュに載るよは分離されていたの転置を統合した、ブロック

アうに定める。

２：
n組のn点


ルゴリズムを構成することができる。４章で説明した





を

２キャッシュに載っているn×n配列

において、nn×nとし、nをブロックサイズとする。ここで、プの上で行う。ここで各


ロセッサは

キャッシュメモリを１キャッシュ内で行えるものとする。

搭載しているものと仮定する。ブロック−−
３：



 

は、ほぼを行った後２

RISTニュース No．
５７（２０１４）

ブロック


アルゴリズムのプログラムは図４のようになる。
このプログラムにおいて、はブロックサイズ、はパディングサイズ、は作業用の配列である。図５にブロック

アルゴリズムのメモリ配置を示す。なお、図５において、配列、、の中の１から１６の数字は、配列のアクセス順序を示している。
また、作業用の配列

にパディングを施すことにより、配列

から配列にデータ を 転 送 す る 際 や、配 列上 で


を行う際にキャッシュラインコンフリクトの発生を極力防ぐことができる。このパディングは、配列の先導次元（  ）が２のべき乗となっている場合、これが２のべき乗にならないようにすることで、行列の転置において２のべき乗飛びのストライドアクセスになることを防ぐために用いられる。
ブロック


アルゴリズムは、いわゆる
アルゴリズム［４］となる。
つまり、ブロックアルゴリズム

ではn点の演算回数はO（nn）であるのに対し、主記憶のアクセス回数は理想的にはO（n）で済む。
図４ブロック

なお、本稿では
２および

４の各

アルゴリズム

は１キャッシュに載ると想定しているが、問題サイズが非常に大きい場
キャッシュに残っているn×n配列
の合には各

各要素にひねり係数の乗算を行う。そしてらないことも十分予想される。このような場

このn×n配列

のデータをn列ずつ転合は二次元表現ではなく、多次元表現［８，置しながら元のn×n配列の同じ場所に再９］を用いて、各び格納する。

小さくすることにより、１キャッシュ内で
４：n組 のn点

各

をが１キャッシュに載の問題サイズをを計算することができる。たの 上 で 行 う。こ こ で も 各n×n配 列

だし、三次元以上の多次元表現を用いた場合

には
アルゴリズムとすることはでは、ほぼキャッシュ内で行えきず、例えば三次元表現を用いた場合にはる。


 ア ル ゴ リ ズ ム に な る。こ の よ う
５：
最後にこのn×n配列をn列ずに、多次元表現の次元数を大きくするに従っつ転置して、n×n配列に格納する。
−−RISTニュース No．
５７（２０１４）

図５

ブロック


アルゴリズムのメモリ配置て、より大きな問題サイズのに対応するの結果主記憶のアクセス回数も少なくするこことが可能になるが、その一方で主記憶のアとができる。データがキャッシュに入り切らクセス回数が増加する。これは、ブロックないような大きな問題サイズのでは、ブ

ロック

においても性能はキャッシュメモリの容量に依存することを示している。

本稿で述べたブロック化の手法は、他のア

なお、 アルゴリズム（例えばプリケーションの高速化にも適用できると考 ア ル ゴ リ ズ ム）を

２、４ の


は効果的である。

えられる。に用いたとしても、余分に必要となる配列の大きさは参考文献で済む。

また、一次元の結果が転置された出力

［１］




 

で構わなければ、

５の行列の転置は省 


略することができる。この場合、作業用の配


列はの大きさの配列だけで済む  
６．まとめ
本稿では、におけるキャッシュ最適化に つ い て 述 べ た。ブ ロ ッ ク     
［２］


ことが分かる。

 








では、キャッシュメモリの再利用率を高くする



［３］

ことにより、キャッシュミスを少なくし、そ
−− 

RISTニュース No．
５７（２０１４）     ［４］
                ［５］
  ［８］             ［６］     ［９］
  ［７］      −−     