FFTW在物探领域的并行应用实现.pdf

《FFTW在物探领域的并行应用实现.pdf》由会员分享，可在线阅读，更多相关《FFTW在物探领域的并行应用实现.pdf（49页珍藏版）》请在一课资料网上搜索。

1、FFTW在物探领域的并行实现在物探领域的并行实现 吴迪 目录 FFT简述 FFTW简介 FFTW用法 并行代码优化 总结 3 一一 FFT简述简述 模拟域 FT 模拟域 DFT 时间域 t 连续 频率域 s 连续 时间域 n 离散 频率域 k 离散 4 1 1 1 Fourier Transform FT 2 Forward FT kx F kf x edx 2 Inverse FT kx f xF k edk 一一 FFT简述简述 5 1 1 2 Discrete Fourier Transform DFT One dimension Multi dimension 1 2 0 0 1 1

2、n rki n nrknn k yF xyx wwern 2 with 0 1 1 1 i i i n nii wernid 12 1 12 21 1 121 12 111 11 000 d d nnn rkr krk ddnnn kkk y iix kkwww 一一 FFT简述简述 目录 FFT简述 FFTW简介 FFTW用法 并行代码优化 总结 7 FFTW the Fastest Fourier Transform in the West 由麻省理工学院计算机科学实验室超级计算技术组开 发的一套离散傅立叶变换 DFT 的计算库 开源 高效和 标准C语言编写的代码使其得到了非常广泛的应用

3、Intel 的数学库和Scilib 类似于Matlab的科学计算软件 都使用 FFTW做FFT计算 二二 FFTW简介简介 8 FFTW是计算离散Fourier变换 DFT 的快速C程序的一 个完整集合 1 它可计算一维或多维 实和复数据以及任意规模的 DFT 2 FFTW输入数据长度任意 3 FFTW支持任意多维数据 4 FFTW 支持SSE SSE2 Altivec和MIPS指令集 二二 FFTW简介简介 9 5 FFTW 还包含对共享和分布式存储系统的并行变换 它可自动适应你的机器 缓存 存储器大小 寄存器个数 FFTW 通常比目前其它开源Fourier变换程序都要快 FFTW 最新版本

4、为fftw 3 3 3 http www fftw org 二二 FFTW简介简介 lib machine ix86 def libfftw3 3 def 10 二二 FFTW简介简介 11 6 FFTW有三个版本的数据类型 double float和long double 使用方法如下 链接对应的库 比如libfftw3 3 libfftw3f 3 或 ibfftw3l 3 包含同样的头文件fftw3 h 将所有以小写 fftw 开头的名字替换为 fftwf float 版本 或 fftwl long double版本 比如将 fftw complex替换为fftwf complex 将ff

5、tw execute替换 为fftwf execute等 二二 FFTW简介简介 lib machine ix86 def libfftw3 3 def 目录 FFT简述 FFTW简介 FFTW用法 并行代码优化 总结 二二 FFTW用法用法 13 1 复一维变换复一维变换 include fftw complex in N out N 定义数据类型 复数组 fftw plan p 定义计划 创建计划 向前变换 p fftw plan dft 1d N in out FFTW FORWARD FFTW ESTIMATE ESTIMATE表示不运行任何计算而只是建立一个合理的计 划 fftw o

6、ne p in out 一维变换的输入 出 数组 fftw destroy plan p 用完后 取消计划 在Unix上 一个使用FFTW的程序应该与 lfftw lm相连接 二二 FFTW用法用法 14 typedef double fftw complex 2 FFTW默认使用双精度浮点进行运算 用户可以 使用float和long double来改变运算精度 虽然更 高精度的数据进行运算理论上会得到更高精度的结 果 但是由于软件系统和硬件的限制往往适得其反 因此用户要结合软硬件 系统来选择FFTW的数据类型 一 数据格式 二二 FFTW用法用法 15 void fftw malloc si

7、ze t n void fftw free void p fftw malloc考虑了数据对齐 以便使用SIMD指 令加速 所以最好不要用C函数malloc替代 而且 不要将fftw malloc和free delete等混用 尽量使 用fftw malloc分配数组 而不是上面的固定数组 因为固定数组是在栈上分配的 并且未考虑对齐 二 内存申请与释放 二二 FFTW用法用法 16 fftw plan fftw plan dft 1d int n fftw complex in fftw complex out int sign unsigned flags 第一个参数n是你要进行变换的数据大

8、小 n可以是 任何大小的正整数 接下来的两个参数是输入输出数组 的指针 这两个指针可以相同 表示就地转换以节省空 间 第四个参数sign 可以是FFTW FORWARD 1 或 FFTW BACKWARD 1 指出变换的方向 从技术角度讲 它是变换中的指数标志 三 一维计算方案 二二 FFTW用法用法 17 参数flags可以是FFTW MEASURE或FFTW ESTIMATE FFTW MEASURE表示FFTW会先计算一些FFT并测量所用的时间 以便为大小为n的变换寻找最优的计算方法 依据 机器配置和变 换的大小 n 这个过程耗费约数秒 时钟clock精度 FFTW ESTIMATE则相

9、反 它直接构造一个合理的但可能是次最优 的方案 总体来说 如果你的程序需要进行大量相同大小的FFT 并且初始化时间不重要 可以使用FFTW MEASURE FFTW MEASURE 模式下in和out数组中的值会被覆盖 所以该方式应该在用户初 始化输入数据in之前完成 二二 FFTW用法用法 18 fftw plan fftw plan dft 2d int n0 int n1 fftw complex in fftw complex out int sign unsigned flags fftw plan fftw plan dft 3d int n0 int n1 int n2 fftw

10、 complex in fftw complex out int sign unsigned flags fftw plan fftw plan dft int rank const int n fftw complex in fftw complex out int sign unsigned flags 四 多维计算方案 二二 FFTW用法用法 19 多维复数据的DFT同一维复数据的DFT用法类似 数 组in out为行优先方式 存储 fftw plan dft是一个通用的复 DFT函数 可以执行一维 二维或多维复DFT 比如对于图 像 2维数据 其变换为 fftw plan dft 2d

11、 height width 85 因为原始图像数据为height width的矩 阵 即第一维 n0 为行数 height 二二 FFTW用法用法 20 void fftw execute const fftw plan plan 一旦变换方案创建完成你就可以刷新使用你的输入 输出数组而执行多次变换 实际的变换计算工作由 fftw execute plan 来完成 完成变换后调用 fftw destroy plan plan 销毁方案 void fftw destroy plan fftw plan plan 五 方案执行 二二 FFTW用法用法 21 2 复多维变换复多维变换 include

12、 对于FFTW3 0以上版本则采用fftw3 h fftw complex in L M N 数据类型 fftwnd plan p fftwnd代表N维fftw p fftw plan dft 3d L M N in out FFTW FORWARD FFTW MEASURE 在位 in place 变换 用输出数组覆盖组 MEASURE即FFTW实际执行和测量几个FFT的执行时间 以发现计算规模为N的变换的最好方式 fftwnd one p fftwnd destroy plan p 程序编译时需与 lfftwnd lfftw lm相连接 二二 FFTW用法用法 22 3 实一维变换实一维变

13、换 include 专门针对实型数据的rfftw变换 数据类型 double in N out N rfftw plan p 计划 int k 创建计划 实到复的变换 复到实则为逆变换 p fftw plan r2r 1d N in out FFTW R2HC FFTW ESTIMATE rfftw one p in out rfftw destroy plan p 程序编译时需与 lrfftw lfftw lm相连接 二二 FFTW用法用法 23 4 实多维变换实多维变换 include 专门针对实型数据的rfftw变换 数据类型 double in M N out M N rfftw pl

14、an p 计划 int k 创建计划 实到复的变换 复到实则为逆变换 p fftw plan r2r 2d M N in out FFTW R2HC FFTW R2HC FFTW ESTIMATE rfftwnd one p in out rfftwnd destroy plan p 程序编译时需与 lrfftwnd lfftw lm相连接 二二 FFTW用法用法 24 5 FFTW的的多线程并行多线程并行 1 头文件 2 线程初始化 int fftw threads init void 3 指定线程数 fftw plan with nthreads num 4 线程清除 fftw clean

15、up threads 二二 FFTW用法用法 25 5 FFTW的的多线程并行多线程并行 void fftw execute dft const fftw plan p fftw complex in fftw complex out void fftw execute split dft const fftw plan p double ri double ii double ro double io void fftw execute dft r2c const fftw plan p double in fftw complex out 二二 FFTW用法用法 26 void fftw

16、execute split dft r2c const fftw plan p double in double ro double io void fftw execute dft c2r const fftw plan p fftw complex in double out void fftw execute split dft c2r const fftw plan p double ri double ii double out void fftw execute r2r const fftw plan p double in double out 二二 FFTW用法用法 27 二二

17、 FFTW用法用法 28 二二 FFTW用法用法 29 5 FFTW的的多线程注意事项多线程注意事项 使用操作系统的线程类库 openMP时 在fftw中 只有fftw execute函数是线程安 全的 如fft plan系列函数都是使用共享数据的 不能并行 需要将fftw plan等函数放到一个线 程中或使用锁进行保证同时只有一个fftw plan 函数正在运行 目录 FFT简述 FFTW简介 FFTW用法 并行代码优化 总结 三三 并行代码优化并行代码优化 一 消除冗余计算 float getResidual float val float grid double approximate

18、times grid return qAbs val approximate 三三 并行代码优化并行代码优化 二 降低计算强度 1 1 加法运算替代乘法 加法运算替代乘法 for i 0 i n i int ni n i for j 0 j n j a ni j b j for i 0 i n i for j 0 j n j a ni j b j ni n 三三 并行代码优化并行代码优化 二 降低计算强度 2 2 移位运算替代乘法 除法 移位运算替代乘法 除法 x 16 x 16 x 4 3 3 乘法运算替代除法运算 乘法运算替代除法运算 int i j k m m i j k int i j

19、 k m m i j k 三三 并行代码优化并行代码优化 三 减少内存访问冲突 利用局部变量替代全局变量利用局部变量替代全局变量 三三 并行代码优化并行代码优化 四 数据对齐 现代计算机中内存空间都是按照现代计算机中内存空间都是按照bytebyte划分的 从理论上划分的 从理论上 讲似乎对任何类型的变量的访问可以从任何地址开始 但事讲似乎对任何类型的变量的访问可以从任何地址开始 但事 实却并非如此 有些平台每次读都是从偶地址开始 如果一实却并非如此 有些平台每次读都是从偶地址开始 如果一 个个intint型 假设为型 假设为32 32 位系统 如果存放在偶地址开始的地方 位系统 如果存放在偶地

20、址开始的地方 那么一个读周期就可以读出 而如果存放在奇地址开始的地那么一个读周期就可以读出 而如果存放在奇地址开始的地 方 就可能会需要方 就可能会需要2 2个读周期 并对两次读出的结果的高低个读周期 并对两次读出的结果的高低 字节进行拼凑才能得到该字节进行拼凑才能得到该intint数据 显然在读取效率上下降数据 显然在读取效率上下降 很多 这也是空间和时间的博弈 很多 这也是空间和时间的博弈 CPUCPU数据访问粒度 数据访问粒度 2 2 4 4 6 6 8 8 3232字节字节 GPUGPU数据访问粒度 数据访问粒度 3232 6464 128128字节字节 三三 并行代码优化并行代码优化

21、 结构体 或类 相同类型的数据尽量放在一起结构体 或类 相同类型的数据尽量放在一起 结构体 或类 内大的数据类型尽量放在前面结构体 或类 内大的数据类型尽量放在前面 struct MyStructB char a double b float c int d int e sizeof MyStructB 32 struct MyStructB double b float c int d int e char a sizeof MyStructB 24 struct MyStructA char a int c char b sizeof MyStructA 12 struct MyStruc

22、tA char a char b int c sizeof MyStructA 8 pragma pack Number pragma pop 三三 并行代码优化并行代码优化 五 分支优化 movl edi 4 rbp movl esi 8 rbp movl 4 rbp eax cmpl eax 8 rbp cmovge 8 rbp eax movl edi 4 rbp movl esi 8 rbp movl 4 rbp eax cmpl 8 rbp eax jle L2 movl 4 rbp eax movl eax 12 rbp jmp L4 L2 movl 8 rbp eax movl

23、eax 12 rbp L4 movl 12 rbp eax leave ret 汇编指令汇编指令 汇编指令汇编指令 int max1 int a int b if a b return a else return b int max2 int a int b return a b a b 用条件表达式替换分支 用条件表达式替换分支 三三 并行代码优化并行代码优化 五 分支优化 三三 并行代码优化并行代码优化 尽量避免 if 条件 执行语句1 else 执行语句2 五 分支优化 三三 并行代码优化并行代码优化 五 分支优化 三三 并行代码优化并行代码优化 六 数据局部性 1 1 顺序访存效率高于

24、随机访存 顺序访存效率高于随机访存 IEESHOT3D SGY 180544IEESHOT3D SGY 180544道 文件大小道 文件大小578M578M 三三 并行代码优化并行代码优化 单道顺序读取源程序单道顺序读取源程序 0 594 秒秒 单道任意读取源程序单道任意读取源程序 1 578 秒秒 六 数据局部性 三三 并行代码优化并行代码优化 2 2 尽量使用数组替代链表 链表严重伤害数据局 尽量使用数组替代链表 链表严重伤害数据局 部性 部性 3 3 尽量安排常用数据在空间上相邻 尽量安排常用数据在空间上相邻 vector vector 好好 于于 listlist 4 4 尽量使用局部

25、变量替代全局变量 尽量使用局部变量替代全局变量 特别要注意 特别要注意 c语言向语言向fortran函数 传入函数 传入 数组参数时 两类语言的差异数组参数时 两类语言的差异 六 数据局部性 三三 并行代码优化并行代码优化 七 提高指令并行 while n p q float a 100 sum sum 0 0f for int i 0 i 100 i sum a i for int i 0 i n i p i q i float a 100 sum1 sum2 sum3 sum4 sum sum1 0 0 sum2 0 0 sum3 0 0 sum4 0 0 for int i 0 i 10

26、0 i 4 sum1 a i sum2 a i 1 sum3 a i 2 sum4 a i 3 sum sum4 sum3 sum1 sum2 三三 并行代码优化并行代码优化 八 内存分配效率与碎片 a a 频繁申请和释放内存 会造成重要的性能损失 特频繁申请和释放内存 会造成重要的性能损失 特 别是并行程序 别是并行程序 b b 频繁申请和释放内存 会形成大量的内存碎片 引频繁申请和释放内存 会形成大量的内存碎片 引 起内存页的换入换出 起内存页的换入换出 解决办法解决办法 1 尽量使用栈内临时存储 不申请堆内存储 尽量使用栈内临时存储 不申请堆内存储 请掌握请掌握alloc malloc和

27、和calloc的区别的区别 2 内存内存cache 申请好的内存重复使用 申请好的内存重复使用 三三 并行代码优化并行代码优化 九 函数调用 a a 用宏定义替代函数 有时还能提升代码的可维用宏定义替代函数 有时还能提升代码的可维 护性 护性 b b 内联函数内联函数inline inline 牺牲空间来节省函数调用的开销 一般用作牺牲空间来节省函数调用的开销 一般用作 比较小的函数比较小的函数 目录 FFT简述 FFTW简介 FFTW用法 并行代码优化 总结 四四 总结总结 一 一 合理利用合理利用FFTWFFTW库可提高物探方法软件实现速库可提高物探方法软件实现速 度和稳定性 度和稳定性

28、二 二 并行计算无论采用何种方式 代码优化是必不并行计算无论采用何种方式 代码优化是必不 可少的 可少的 三 三 FFTWFFTW库提供了多种并行机制供用户选择使用 库提供了多种并行机制供用户选择使用 四 四 在编程尽量使用跨平台的编程技术 例如使用在编程尽量使用跨平台的编程技术 例如使用 C C C C 语言进行编程 语言进行编程 四四 总结总结 该多媒体部分内容参阅了一些网友该多媒体部分内容参阅了一些网友 的微博和网友上传的材料 出处已记不的微博和网友上传的材料 出处已记不 清楚 在此表示感谢 文中的内容若有清楚 在此表示感谢 文中的内容若有 不妥之处请告知作者 不妥之处请告知作者 Email zichangwu Email zichangwu