收稿日期： ２０１０唱０９唱１７； 修回日期： ２０１０唱１１唱０９ 基金项目： 国家“８６３” 计划资助项目（２００９ＡＡ０１Ｚ１１０） ；西北工业大学研究生创新资助项
目（０９０２４）
作者简介： 赵丽丽（１９８５唱） ，女，甘肃环县人，主要研究方向为流处理器体系结构、编程模型（ ｄｕｂｌｙ＠１２６．ｃｏｍ） ；张盛兵（１９６８唱） ，男，教授，博士，
主要研究方向为 ＳｏＣ 系统、处理器体系结构；张萌（１９７８唱），男，讲师，博士，主要研究方向为体系结 构、快速 建模；姚涛（１９８２唱） ，男，博士，主要研究
方向为体系结构、多核处理器．
基 于 ＣＵＤＡ 的 高 速 ＦＦＴ 计 算
倡
赵丽丽， 张盛兵， 张 萌， 姚 涛
（西北工业大学 计算机学院， 西安 ７１００７２）
摘 要： 针对快速傅里叶算法 ＦＦＴ 在图形图像处理和科学计算领域的重要作用，提出了一种基于 ＣＵＤＡ 的高速
ＦＦＴ 计算方法，在分析 ＧＰＵ 硬件平台执行模式及 ＦＦＴ 算法并行性特征的基础上，采用多线程并行的映射方法实
现算法，并从存储层次优化算法。 实验结果表明了该算法的高效性，且优化后的 ＦＦＴ 加速比能达到 ＣＵＦＦＴ 库加
速比的 ２ ～６ 倍。
关键词： 图形处理器； 统一计算架构； 映射策略； 存储层次
中图分类号： ＴＰ３１２ 文献标志码： Ａ 文章编号： １００１唱３６９５（２０１１）０４唱１５５６唱０４
ｄｏｉ：１０．３９６９ ／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１１．０４．１００
Ｈｉｇｈ ｐｅｒｆｏｒｍａｎｃｅ ＦＦＴ ｃｏｍｐｕｔａｔｉｏｎ ｂａｓｅｄ ｏｎ ＣＵＤＡ
ＺＨＡＯ Ｌｉ唱ｌｉ， ＺＨＡＮＧ Ｓｈｅｎｇ唱ｂｉｎｇ， ＺＨＡＮＧ Ｍｅｎｇ， ＹＡＯ Ｔａｏ
（Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ＆ Ｔｅｃｈｎｏｌｏｇｙ， Ｎｏｒｔｈｗｅｓｔｅｒｎ Ｐｏｌｙｔｅｃｈｎｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ， Ｘｉ’ ａｎ ７１００７２， Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ： Ｔｈｅ Ｆｏｕｒｉｅｒ ｔｒａｎｓｆｏｒｍ ｉｓ ｅｓｓｅｎｔｉａｌ ｆｏｒ ｍａｎｙ ｉｍａｇｅ ｐｒｏｃｅｓｓｉｎｇ ａｎｄ ｓｃｉｅｎｔｉｆｉｃ ｃｏｍｐｕｔｉｎｇ ｔｅｃｈｎｉｑｕｅｓ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎ唱
ｔｅｄ ａｎ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｔｏ ａｃｃｅｌｅｒａｔｅ ＦＦＴ ｃｏｍｐｕｔａｔｉｏｎ ｂａｓｅｄ ｏｎ ＣＵＤＡ．Ｂａｓｅｄ ｏｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ ＧＰＵ ａｒｃｈｉｔｅｃｔｕｒｅ ａｎｄ ａｌｇｏ唱
ｒｉｔｈｍ ｐａｒａｌｌｅｌｉｓｍ ｆｅａｔｕｒｅ， ｂｒｏｕｇｈｔ ａ ｍａｐｐｉｎｇ ｓｔｒａｔｅｇｙ ｕｓｅｄ ｍｕｌｔｉｔｈｒｅａｄ， ａｎｄ ｅｘｐｌｏｒｅｄ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｉｎ ｍｅｍｏｒｙ ｈｉｅｒａｒｃｈｙ．Ｔｈｅ
ｒｅｓｕｌｔｓ ｏｎ ＣＵＤＡ ｓｈｏｗ ａｎ ｉｍｐｒｏｖｅｍｅｎｔ， ｔｈｅ ａｖｅｒａｇｅ ｓｐｅｅｄｕｐ ｒｅａｃｈｅｓ ２ ～６Ｘ ｃｏｍｐａｒｅｄ ｗｉｔｈ ＣＵＦＦＴ ｓｕｐｐｌｉｅｄ ｂｙ ＮＶＩＤＩＡ ｌｉｂｒａｒｙ．
Ｋｅｙ ｗｏｒｄｓ： ＧＰＵ（ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｏｒ ｕｎｉｔｓ）； ＣＵＤＡ（ｃｏｍｐｕｔｅ ｕｎｉｆｉｅｄ ｄｅｖｉｃｅ ａｒｃｈｉｔｅｃｔｕｒｅ）； ｍａｐｐｉｎｇ ｓｔｒａｔｅｇｙ； ｍｅｍｏｒｙ ｈｉｅ唱
ｒａｒｃｈｙ
０ 引言
快速傅里叶变换 ＦＦＴ
［１］
（ｆａｓｔ Ｆｏｕｒｉｅｒ ｔｒａｎｓｌａｔｉｏｎ）自其诞生的
四十多年时间中一直受到科学研究和工程计算的广泛应用，特
别是在量子物理、光谱分析、音／视频流信号处理、石油勘探、地
震预报、天气预报、概率论、编码理论、医学断层诊断等领域。
ＦＦＴ 算法具有计算密集型和存储密集型的特点，被用做 ＨＰＣ
［２］
、
ＮＡＳ
［３］
的并行测试基准。 由于 ＦＦＴ 的分治特点，许多新型的处
理器架构相继出现，如 Ｃｅｌｌ、Ｉｍａｇｉｎｅ 以及图形处理单元（ＧＰＵ）。
Ｆｉｒｅｓｔｒｅａｍ 等人都在研究 ＦＦＴ 算法的并行计算的实现。
微电子产业的发展使得 ＧＰＵ 性能迅速提高。 ＧＰＵ 通过增
加并行计算和存储器控制单元提高计算能力和存储带宽，而成
本较之多处理器的工作站则显著降低。 面对 ＧＰＵ 巨大的计算
资源和较高的可编程能力，人们已经不满足将 ＧＰＵ 的应用只
局限于处理图形渲染计算任务，而更加关注基于 ＧＰＵ 的通用
计算 ＧＰＧＰＵ
［４］
（ｇｅｎｅｒａｌ ｐｕｒｐｏｓｅ ＧＰＵ）。
Ｋｅｎｎｅｔｈ 等人
［５］
最早开始研究 ＦＦＴ 算法在 ＧＰＵ 上的实现，
采用 ＯｐｅｎＧＬ 和 Ｃｇ 语言开发应用程序，实现对 ＧＰＵ 中定点单
元和段单元的程序控制，但程序向硬件映射的限制较多，控制
复杂。 随着 ＧＰＵ 的发展，相应的 ＧＰＵ 可编程平台也得到发
展。 ２００７ 年 ＮＶＩＤＩＡ 公司推出的统一计算平台 ＣＵＤＡ
［６］
，使用
ＣＵＤＡ 指令集（ＩＳＡ）以及 ＧＰＵ 内部的并行计算引擎，提出一种
在高性能图形处理单元加速应用的解决方案。 其实现的 ＦＦＴ
库，即 ＣＵＦＦＴ
［７］
库，是基于 ＦＦＴＷ
［８］
的移植，较之 ＣＰＵ 已经能
达到很高的加速比，但还没有充分发挥 ＧＰＵ 多线程执行的潜
力。 本文通过深入分析 ＦＦＴ 算法的并行性特征，提出一种优
化的线程并行映射方法，充分利用算法的同址特点以及存储架
构特点，提高算法并行度，实现了对 ＦＦＴ 算法的加速及优化。
１ ＧＰＵ唱ＣＰＵ 协同的 ＣＵＤＡ 编程
目前主流的 ＧＰＧＰＵ 均采用 ＣＰＵ唱ＧＰＵ 异构核 协同 的架
构
［１０］
。 ＣＵＤＡ 编 程模型 中，ＧＰＵ 经 北 桥 通 过 ＰＣＩ唱Ｅ 总 线 与
ＣＰＵ 连接，ＣＰＵ 负责逻辑性较强的事务计算，ＧＰＵ 主要是以大
量线程实现面向吞吐量的数据并行计算，适合处理计算密集度
高、逻辑分支简单的大规模数据并行任务。
ＣＵＤＡ 编程模型中将 ＣＰＵ 作为主机（ｈｏｓｔ），ＧＰＵ 作为协处
理器或是设备端（ｄｅｖｉｃｅ）。 一个完整的 ＣＵＤＡ 程序包括一系
列的 ｈｏｓｔ 端的串行处理步骤和 ｄｅｖｉｃｅ 端的 ｋｅｒｎｅｌ 函数并行步
骤，其运行流程如图 １ 所示。 主机端负责初始化 ＧＰＵ 设备、准
备数据、分配显存空间及发起 ｈｏｓｔ 到 ｄｅｖｉｃｅ 的数据传输，数据
通过 ＰＣＩ唱Ｅ 总线从主存拷贝到显存。 设备端从显存读取数据，
进行并行计算，输出结果回存显存。 主机端再将结果数据拷贝
到主存，释放显存空间，完成一个完整的 ＣＵＤＡ 应用。
可编程 ＧＰＵ 已发展成为一种高度并行化、多线程、多核的
第 ２８ 卷第 ４ 期
２０１１ 年 ４ 月
计 算 机 应 用 研 究
Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ
Ｖｏｌ畅２８ Ｎｏ畅４
Ａｐｒ畅２０１１
weixin_39841856
- 粉丝: 484
- 资源: 1万+
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- ARM Cortex-A(armV7)编程手册V4.0.pdf
- ABB机器人保养总结解析.ppt
- 【超详细图解】菜鸡如何理解双向链表的python代码实现
- 常用网络命令的使用 ipconfig ping ARP FTP Netstat Route Tftp Tracert Telnet nslookup
- 基于单片机控制的DC-DC变换电路
- RS-232接口电路的ESD保护.pdf
- linux下用time(NULL)函数和localtime()获取当前时间的方法
- Openstack用户使用手册.docx
- KUKA KR 30 hA,KR 60 hA机器人产品手册.pdf
- Java programming with JNI
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0