Q&A
fortranは７７？９０？９５の何れでしょう？
ご覧頂きありがとうございます。
FORTRANで多次元FFTのプログラムを作っている者です。
多次元FFTのプログラム自体は完成したのですが、
それを行うためのデータを格納する配列のサイズが大きすぎ、
プログラムを実行しようとしても強制終了となってしまう、
という問題に悩んでいます。
現在のプログラムは、1次元FFTのプログラムを繰り返して多次元のFFTを計算するものです。
つまり、例えば2次元であれば、
あるデータ
F(idx, jdt) (i=1,…,N1, j=1,…,N2)
について、
まず x についての長さ N1 の1次元FFTを t を動かしながら N2 回行い、
次に t についての長さ N2 の1次元FFTを x を動かしながら N1 回行って計算する、
という方法です。
その際用いるデータは、
a(i, j)=F(idx, jdt)
のように2次元の配列となっています。
ここで、私が計算したいデータは、
F(x, y, z, t)
という4次元のデータなのですが、
上に述べたように計算しようとすると、配列も
a(i, j, k, l)=F(idx, jdy, kdz, ldt)
と4次元のものを使わなくてはならず、
サイズが爆発的に大きくなり、強制終了となってしまいます。
そこでお聞きしたいのですが、
多次元のFFTについて、プログラムが強制終了とならないよう、
配列のサイズを節約するには、どのような方法があるでしょうか。
ちなみに、コンパイル時は、-mcmodel=large のオプションをつけて行っています。
どうかご回答よろしくお願いいたします。
回答2件
0
ベストアンサー
仮にサンプルの各次元の数が2**10で各データが16ビットだとすると、単純に考えて2**10**4*2 = 2**41バイトの物理メモリが必要になってしまいますね。
1次元FFTの計算を分割して行うことで、各ステップでメモリに置いておかなければならないデータの量を減らすことはできると思います。たとえば上述の例ではN1 = p1**2 (p1 = 2**5) なので、2次元化FFTを実行すれば各ステップでの計算に必要なメモリ量はデータp1・N2・N3・N4個分に減らせます。さらにN2に対しても同様にすれば、p1・p2・N3・N4個分にまで減らせます。
ただし、計算量は増えます。2次元化FFTでは通常のFFTを2回 (以上) 実行するほか、計算途中のデータを並べ替える処理も実行しなければなりません (2次元化FFTの説明はこれが分かりやすかったです)。また、計算に必要ない領域のデータを外部記憶 (ディスクなど) に追い出し、必要になったらメモリに読み込む処理があるため、I/Oに費やす時間が無視できなくなります。
こういったマイナス要因があってもなお、許容できる時間内で結果が出せそうであれば、試す価値はあると思います。
(追記)
「2次元化FFT」というのは正式な呼び名ではないかもしれません。「six-step FFT」のほうがウェブ検索でよくヒットします。詳しい解説としては、たとえば計算物質科学イニシアティブでの2014年の講義「大規模系での高速フーリエ変換1」などはどうでしょう。「n=n1n2に対するFFTアルゴリズム」のところからです。
簡単に言うと、N = n1・n2個のサンプルをn1 × n2の2次元に配列し直し、n1個の行とn2個の列のそれぞれで1次元FFTを実行し、それら2・n1・n2回のFFTの結果からN個の場合のFFTの結果を計算する、という手法です。計算の各ステップでは、n1個またはn2個のデータだけがメモリ上にあればいいことになります。必要ないデータは外部記憶に書き出し、必要になったら読み込みます。
上記の講義でも述べているように、もともとこの手法は、FFTのサンプル数がCPUのキャッシュメモリのサイズと比較して大きいと、キャッシュミスが多発して処理速度が著しく低下する、ということへの対策として考えられたようです。しかし今回の場合は、メインメモリをディスクに、キャッシュメモリをメインメモリに置きかえて考えてみて下さい。
(11/12さらに追記。また前回追記分で式がおかしいところを直しました)
ともかく、この手法は1次元FFTについて計算の各ステップで必要なメモリを節約しているだけで、4次元分の計算が必要なことは変わりません。でも、1次元分だけに適用して他の次元は全範囲をメモリに置くとしても、回答冒頭の例では必要メモリ量が2**5 * 2**10**3 * 2 = 2**36バイトに減らせます。かなり現実的な数字になってきますね。
投稿2016/11/11 03:01
編集2016/11/12 15:30
総合スコア4317
回答ありがとうございます。
FFTしたいデータを最初から全て配列として読み込んでしまうのではなく、
一部は外部のファイルに保存しておいて、
そこから必要な分だけ随時読み込む、ということでしょうか？
また、
>1次元FFTの計算を分割して行うことで、各ステップでメモリに置いておかなければならないデータの量を減らすことはできると思います。たとえば上述の例ではN1 = p1**2 (p1 = 2**5) なので、2次元化FFTを実行すれば各ステップでの計算に必要なメモリ量はデータp1・N2・N3・N4個分に減らせます。さらにN2に対しても同様にすれば、p1・p2・N3・N4個分にまで減らせます。
とご回答頂きましたが、ここについてもう少しだけ詳しく説明頂けましたら幸いです。
追記ありがとうございます。
>簡単に言うと、N = n1・n2個のサンプルをn1 × n2の2次元に配列し直し、n1個の行とn2個の列のそれぞれで1次元FFTを実行し、それら2・n1・n2回のFFTの結果からN個の場合のFFTの結果を計算する
なるほど、そういうことだったんですね！
ご説明頂いてやっとわかりました。
とりあえず、ご提示頂いたページを見ながら、実際にプログラムへの導入を考えてみたいと思います。
ご回答ありがとうございました。
0
Fortran90という事で、手っ取り早く参考になるページを。
Segmentation fault: 巨大な配列の場合
この中で、コンパイルの際に（泥臭い方法だけど）オプションをつけて回避する方法。（絶対とは言えないけど、以降の参考になると思った）
それと実行のオプションの説明があります。
投稿2016/11/10 07:34
総合スコア3747
回答有り難うございます。
-mcmodel=largeの他にもオプションがあったんですね。
ぜひ試してみたいと思います。
ですが、やはりプログラムの方は特に改善しようがないのでしょうか…。
ソースを見ていないので、経験から言いますと’トリッキー’な方法になってしまい本来の解析より’確かさ’の確認や’デバッグ’に時間を取られることになると考えます。
ありがとうございます。
やはり難しいのですね。
とりあえず教えて頂いたページに書いてあった
ulimit -s unlimited
のオプションを使ってみようと思います。
ありがとうございました。
あなたの回答
tips
プレビュー
