FFTW使用说明 课件.ppt

《FFTW使用说明 课件.ppt》由会员分享，可在线阅读，更多相关《FFTW使用说明 课件.ppt（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1,FFTW使用说明 王 武中科院超级计算中心Email: ,2010 年 5月,2,内 容 提 要一. 快速傅立叶变换二. FFTW 的使用指南三. FFTW 的技术特点四. FFTW 的调用算例五. FFTW在Unix上的安装,3,1.1.1 Fourier Transform (FT)1.1.2 Discrete Fourier Transform (DFT)One-dimension:Multi-dimension:,一. 快速傅立叶变换,4,1.1.3 DFT in Matrix-vector FormEg: DFT in 1D F is a matrix as in right:C

2、omplexity:Its applied in DSP ( Digital Signal Processing ): analyse and manipulate real-world signals by computer Toys and consumer electronics (Spectrogram ) Speech recognition Audio/video compression Medical imaging Communications Radar,一. 快速傅立叶变换,5,1.2.1 Fast Fourier Transform (FFT)Cooley & Tukey

3、 , 1965 FFT is a divide-and-conquer algorithm using binary reversal sortEg: FFT in 1DOrder: even, odd Complexity:,一. 快速傅立叶变换,01234567,04261537,6,1.2.3 Parallel FFT in 1DCombine: using butterfly computation1.2.4 FFT in Multi-dimensionEg: DFT in 2D, Complexity : reduced to 2 steps of DFT in 1DComputed

4、 by FFT，Complexity :,一. 快速傅立叶变换,0, 4 2, 6 1, 5 3, 7Log28 transform steps,7,1.3 Example: FFT for Convolution FormStep 1: FFT for x(N) and h(N) Step 2: Vec-Vec Mult: Y(n)=X(n)H(n)Step 3: IFFT for Y(N): Complexity:,一. 快速傅立叶变换,8,2.1 FFTW简单概述FFTW ( the Faster Fourier Transform in the West) 是一个快速计算离散傅里叶变换

5、的标准C语言程序集FFTW 由MIT的 M. Frigo 和 S. Johnson 开发,可计算一维或多维, 实和复数据以及任意规模的DFT.FFTW 还包含对共享和分布式存储系统的并行变换,它可自动适应你的机器, 缓存, 存储器大小, 寄存器个数 .FFTW 通常比目前其它开源Fourier变换程序都要快 !FFTW 最新版本为fftw-3.2.2FFTW下载及相关资料提供http:/ www.fftw.org,二. FFTW的使用指南,9,2.2. FFTW 计算:1)复(实)一维变换及其逆变换: 由于没有正规化:2)复(实)多维变换及其逆变换:计算一个向前变换随后一个向后变换将用 乘以输

6、入(正规化).变换的正确性检验:3)以上变换的并行实现共享和分布式存储系统,一维和多维DFT, 实变换和复变换,多线程和MPI.,二. FFTW的使用指南,10,2.3.1 复一维变换#include fftw_complex inN, outN; /定义数据类型:复数组 fftw_plan p; /定义计划 /创建计划 ,向前变换 p = fftw_create_plan(N, FFTW_FORWARD, FFTW_ESTIMATE); / ESTIMATE表示不运行任何计算/而只是建立一个合理的计划 fftw_one(p, in, out); /一维变换的输入(出)数组 fftw_dest

7、roy_plan(p); /用完后,取消计划 / 在Unix上,一个使用FFTW的程序应该与-lfftw lm相连接,二. FFTW的使用指南,11,2.3.2 复多维变换#include /对于FFTW3.0以上版本则采用fftw3.h fftw_complex inLMN; /数据类型 fftwnd_plan p; / fftwnd代表N维fftw p = fftwnd_create_plan(L, M, N, FFTW_FORWARD, FFTW_MEASURE | FFTW_IN_PLACE); /在位(in-place)变换 用输出数组覆盖组 /MEASURE即FFTW实际执行和测量

8、几个FFT的执行时间 以发现计算规模为N的变换的最好方式 ; fftwnd_one(p, /程序编译时需与-lfftwnd lfftw lm相连接,二. FFTW的使用指南,12,2.3.3 实一维变换#include /专门针对实型数据的rfftw变换/ 数据类型 fftw_real inN, outN; rfftw_plan p; /计划 int k /创建计划 ,实到复的变换,复到实则为逆变换 p = rfftw_create_plan(N, FFTW_REAL_TO_COMPLEX, FFTW_ESTIMATE); rfftw_one(p, in, out); rfftw_destro

9、y_plan(p); /程序编译时需与-lrfftw lfftw lm相连接,二. FFTW的使用指南,13,2.3.4 实多维变换#include /专门针对实型数据的rfftw变换/ 数据类型 fftw_real inM, N, outM, N; rfftw_plan p; /计划 int k /创建计划 ,实到复的变换,复到实则为逆变换 p = rfftwnd_create_plan(M, N, FFTW_REAL_TO_COMPLEX, FFTW_ESTIMATE); rfftwnd_one(p, in, out); rfftwnd_destroy_plan(p); /程序编译时需与-

10、lrfftwnd lfftw lm相连接,二. FFTW的使用指南,14,2.4.1. FFTW的多线程并行1.头文件: 或 2.线程初始化: int fftw_threads_init(void); 3.用到的函数fftw_threads_one(nthreads, plan, in, out); /一维复变换fftwnd_threads_one(nthreads, plan, in, out); /n维复变换rfftw_threads_one(nthreads, plan, in, out); /一维实变换rfftwnd_threads_one(nthreads, plan, in, ou

11、t); /n维实变换以一维复变换为例用 fftw_threads_one (nthreads, plan, in, out) 代替调用单机 fftw_one (plan, in, out) 在Unix上,使用并行复变换的程序应该与-lfftw_threads - lfftw - lm相连接, 使用并行实变换的程序应与-lrfftw_threads -lfftw_threads -lrfftw -lfftw lm 相连接,二. FFTW的使用指南,15,2.4.2. FFTW的MPI并行调用头文件创建计划:fftw_mpi_plan fftw_mpi_create_plan(MPI_Comm c

12、omm, int nFFTW_FORWARD, FFTW_ESTIMATE );用完后通过fftw_mpi_destroy_plan(plan)来取消.3. 变换函数为:void fftw_mpi(fftw_mpi_plan p, int n_fields, fftw_complex *local_data,fftw_complex *work); 返回时, local_data包含局限于当前进程的输出部分, 可调用:void fftw_mpi_local_sizes(fftw_mpi_plan p, int *local_n, int *local_start,int *local_n_af

13、ter_transform,int *local_start_after_transform,int *total_local_size);在Unix上, FFTW MPI的程序应与MPI库和-lfftw_mpi -lfftw -lm连接.,二. FFTW的使用指南,16,3.1 The PlannerFor a given N, there are many factorizationsnot clear a priori which is bestEg: 32768 =16x8x8x32=64x16x32The planner tries them “all” and picks the

14、best oneuses actual runtime timing measurementsresult is encoded in a “plan”Uses dynamic programming to reduce no. of possible plansremembers optimal sub-plans for small sizesThe Runtime Planneroptimizes FFTW for your CPU, your cache size, etc.IdeasModern architectures are invalidating conventional

15、wisdom about what is fast no new wisdom is emergingIn the name of performance, designers have sacrificed: predictability, repeatability, composabilityHand-optimization of programs is becoming impractical,三 FFTW的技术特点,17,3.2 The Codelet GeneratorGenerates highly-optimized transforms of small sizes for

16、m the base cases of the FFT recursionManipulates abstract syntax tree which is unparsed to Cknows about complex arithmetic, etc.The codeletscomposable blocks of optimized code computer generatedAdvantagesLong, unrolled code takes advantage of: optimizing compilers (instruction scheduling, etc.), lar

17、ge register setsApplies tedious optimizationsEasy to experiment with different algorithmsprime factor, split-radix (transform sizes not a power of 2)various optimization schemes,三 FFTW的技术特点,18,3.3 The ExecutorExecutes the plan by composing codeletsExplicit recursion divide-and-conquer uses all level

18、s of the memory hierarchyfit in cacheNovel storage for the twiddle factorsstore them in the order they are used3.4 FFTW is Easy to UseCOMPLEX An, Bn; fftw_plan plan; plan = fftw_create_plan(n); /* create the plan */fftw(plan, A); /* use the plan */fftw(plan, B); /* re-use the plan */fftw_destroy_pla

19、n(plan) /* destroy the plan*/,三 FFTW的技术特点,19,4.1 调用说明FFTW 的C函数允许Fortran程序调用 .fftw/fftwnd/rfftw/rfftwnd 由fftw_f77/fftwnd_f77/rfftw_f77/rfftwnd_f77所替代 3.函数的大多数参数相同, 少数例外:plan变量在C中为fftw_plan, rfftw_plan等类型，Fortran上对64位机器用integer*8 类型 Fortran数组列存储,C为行存储, integer对应于int, real对应于floatfortran/fftw_f77.i中已将选

20、项参数化integer FFTW_FORWARD, FFTW_BACKWARDparameter(FFTW_FORWARD=-1, FFTW_BACKWARD=1integer FFTW_OUT_OF_PLACE, FFTW_IN_PLACEparameter(FFTW_OUT_OF_PLACE=0)parameter(FFTW_IN_PLACE=8) integer FFTW_ESTIMATE, FFTW_MEASUREparameter (FFTW_ESTIMATE=0, FFTW_MEASURE=1),四 FFTW 的调用算例,20,4.2 串行一维复变换的例子/C编译环境fftw_co

21、mplex inN, *outN;fftw_plan plan;plan = fftw_create_plan(N, FFTW_FORWARD, FFTW_ESTIMATE);fftw_one(plan, in, out);fftw_destroy_plan(plan);/ Fortran编译环境double complex in, outdimension in(N), out(N)integer plancall fftw_f77_create_plan(plan, N, FFTW_FORWARD, FFTW_ESTIMATE)call fftw_f77_one(plan, in, out

22、)call fftw_f77_destroy_plan(plan),四 FFTW 的调用算例,21,4.3. 并行一维复变换的例子#include int main(int argc, char *argv) const int N = 128; fftwnd_mpi_plan plan; fftw_complex *data; MPI_Comm comm=MPI_COMM_WORLD; MPI_Init(,四 FFTW 的调用算例,22,4.4. FFTW的数值测试scwangLB$ locate fftw/soft/fftw-215 fftw_test fftw_mpi_testscydf

23、LB270108 /fftw/fftw-f90/2ds_test$ %Demo,表1：串行性能（深腾7000, x86_64, 时间: 秒, 浮点性能: Mflops）,表2：并行效率（深腾7000, x86_64, 4096 x 4096 ）,四 FFTW 的调用算例,计算时间：T(Forward_plan)+T(Forward_FFT)+T(Inverse_plan)+T(Inverse_FFT),23,1) FFTW带有一个GNU形式的configure程序,安装很简单:tar xvfz fftw-3.0.1.tar.gz ./configure make make install这将建

24、立单机形式的复和实变换库以及测试程序 2) 对于某些系统, configure脚本知道好的CFLAG. 如果你的系统不知道, 可用如下命令编译 FFTW:./ configure CC=“”,CFLAGS=”configure 也可接受一些FFTW说明的标志 :-enable-float 生成一个单精度版的FFTW -enable-threads 使能够编译和安装FFTW线程库 -enable-mpi 使能够编译和安装FFTW的MPI库 -disable-fortran 禁止FFTW库中包含Fortran可调用程序 3) 比如调用 dfftw_one或 sfftw_one 之前的安装选项为: ./configure -prefix=/home_soft/soft/ia64/lib/Mathlib/fftw-2.1.5 CC=icc MPICC=icc CFLAGS=-O3 F77=ifort FFLAGS=-O3 -enable-double -enable-type-prefix -enable-mpi -enable-fortran -enable-shared (double/float对应于双精度或单精度)make make install,五. FFTW在Unix上的安装,24,谢谢,