二维快速傅里叶变换在众核处理器上的实现

肖风玉　张德学

摘 要 本文研究了开放式平铺结构的众核片上系统（Open Tiled Manycore System-on-Chip，简称OPTIMSOC）上的一款众核处理器，在该处理器上实现了二维快速傅里叶变换（two dimensional Fast Fourier transform，简称2D FFT）。实验结果表明，相较于单核处理器，众核处理器有较明显的加速效果。

关键词 二维快速傅里叶变换 众核处理器 OPTIMSOC 加速比

中图分类号：TN929.53；TP332 文献标识码：A

所谓多核处理器是指在同一个芯片上集成多个处理器核心。根据处理器核心的结构是否相同又可进一步划分为同构多核处理器和异构多核处理器。相比传统的单核处理器，多核处理器最大的优势在于其并行性，由于在一个芯片内集成了多个核心，因此在同一时间内每个核心都可以并发的执行计算任务，且互不干扰，这使得多核处理器的计算性能得到大幅度提升。此外由于多核处理器的并行性使得其不必工作在较高的工作频率也能完成与单核处理器相同的任务，降低了处理器的工作频率，延长了芯片的使用寿命。

本文首先分析了二维快速傅里叶变换（two dimensional Fast Fourier Transform，简称2D FFT）的基本原理，然后利用开放式平铺结构的众核片上系统（Open Tiled Manycore System-on-Chip，简称OPTIMSOC）上的一款众核处理器对2D FFT进行了实现。

1 2D FFT的基本原理

计算2D FFT可分为3步。第一步，对矩阵的每一列进行一维快速傅里叶变换（简称1D FFT），由于列变换之间无相关性，因此其并行性是显著的；第二步处理2D FFT的旋转因子，由于旋转因子的处理之间无相关性，因此其并行性是显著的；第三步，对矩阵的每一行进行1D FFT，由于行变换之间无相关性，因此其并行性是显著的。

2 众核处理器介绍

OPTIMSOC是一个基于库的框架平台，它允许用户构建属于自己的众核处理器。该平台基于开源规则的片上网络结构LISNOC和其它一些开源的硬件组件构成。这些硬件组件包括处理单元、存储器和输入输出设备等等。与传统的基于总线互联方式的多核处理器相比，众核处理器的一大显著特点是引入了片上网络的概念。片上网络的成功引入，解决了总线互联方式中的瓶颈，包括功耗、面积和复杂度等。使用OPTIMSOC平台构建的众核系统可以在电脑上进行仿真或者综合之后下载到FPGA开发板上进行实现。OPTIMSOC平台的出现，使得对众核处理器研究不只是停留在建模与仿真阶段，而是真正进入了设计阶段，加速了众核处理器产品的设计与开发。

OPTIMSOC平台设计者建议使用Ubuntu 12.04或14.04 LTS作为开发系统。本文在Centos 7.1系统上对OPTIMSOC平台进行了安装与配置并对平台上存在的一款众核处理器进行了分析。通过分析，该众核处理器由独立的计算单元组成，每个计算单元包含一个计算核心和一个本地存储器。计算核心采用的是OpenRisc架构的处理器，本地存储器的容量是8MB，核与核之间的通信通过LISNOC完成。值得注意的是，OPTIMSOC的安装包中已包含了单核处理器。

3 2D FFT在众核处理器上的测试

对于单核处理器的编程，可按照第一部分中介绍的2D FFT的计算步骤进行编程，即将3个计算步骤看作是三个顺序执行的任务进行编程。对于众核处理器而言，由于其核心数较多，各核心需要协同工作才能完成计算任务，因此与单核处理器相比，众核处理器的编程较为复杂。在该众核处理器中，将0核作为主核，其它核作为辅核。主核负责向其它核传送计算指令与运算数据并回收来自辅核的计算结果，辅核负责进行计算并将计算后的结果返回至主核。根据该原则，编写了在众核处理器上运行的2D FFT程序。本文在单核处理器和众核处理器上分别对256点、1024点和4096点下的2D FFT进行了测试。实验结果表明，众核处理器对2D FFT有较明显的加速效果。

4 结论

本文分析了OPTIMSOC平台上的一款众核处理器，在该众核处理器上运行了2D FFT。实验结果表明，相比单核处理器，众核处理器对2D FFT有较明显的加速效果。

但仍有一些问题需要进行深度的挖掘，包括算法并行度的进一步分析，众核处理器的共享存储问题。如果算法的并行程度分析不够，很容易造成众核处理器资源的浪费。由于本文中的众核处理器未采用共享存储，大点数情况下，核间数据交换将会占据较大部分比重，影响众核处理器的性能。因此今后的研究重点将在这两方面进行。

参考文献

[1] 黄国睿，张平，魏广博.多核处理器的关键技术及其发展趋势[J].计算机工程与设计，2009，30（10）：2414-2418.

[2] 李晓明，王韬，刘东等.走进多核时代[J].计算机科学与探索，2008（6）：561-570.

[3] 张丽君.大点数FFT的二维算法FPGA并行实现[J].无线电通信技术，2013（3）：86-88.

[4] 李丽，许居衍.片上网络发展现状及趋势浅析[J].电子产品世界，2009（1）：32-37.