基于多核处理器的并行3D-FFT研究

摘要

随着计算任务量的增加，单核处理器已不能满足用户需求，主要原因是功耗问题限制了单核处理器不断提高性能的途径。而多核处理器的问世，为多任务、大数据难题提供了解决方案。3D-FFT是科学与工程研究中最重要的算法之一，在计算机视觉和模式识别，视频电话和核磁共振成像算法中，都有着至关重要的作用。如何在多核处理器上更快速的进行3D-FFT计算，是科学研究中首要面临的难题。本文针对并行3D-FFT在多核处理上的应用，从数据预处理，数据计算和数据转置三个方面对3D-FFT算法进行研究。
　　本研究主要内容包括：⑴在数据预处理阶段，为避免出现有的核满载，有的核空转现象，采用负载均衡算法让每个核心平均处理任务。同时，为了避免计算阶段数据在核心之间不必要的迁移，提出线程与CPU亲和性算法，让数据在指定的CPU核心运行。为解决共享内存多核处理器伪共享难题，提出缓存行填充算法，使得属于不同核心的数据被分在独立的缓存行内。在2核心与8核心下测试算法缓存命中率，实验表明，缓存行填充以及线程与CPU亲和性算法，2核心下，一级数据缓存未命中率平均降低了0.2%，三级缓存未命中率平均降低了0.2%，8核心下分别降低了0.2%与0.1%。⑵在数据计算阶段，以多列FFT算法为基础，使用多线程并行化处理。对于FFT每次计算，使用经典六步快速傅里叶变换算法把数据划分成更小的数据量进行计算，加快处理速度。对位反转处理过程，采用两端反转策略进行优化，一次处理四个数据点，使算法时间复杂度降为原来的一半。⑶在数据转置阶段，提出全局转置优化算法，减少参与核间通信数据点的总数，从而加快全局转置速度。与现有全局转置算法相比，通信时间平均减少0.05秒，约提高9.5%。并使用多核模拟器Sniper Simulator对其功耗进行统计，在8个计算核心下，全局转置优化算法与现有转置算法，核间功耗，核与内存功耗以及一级数据缓存功率消耗均值分别约为20W和22W，7.2W和7.5W以及16.9W和17.1W。⑷为进一步体现算法性能优越性，与已有的FFTW和OpenMP多线程进行比较。在8核心下，与FFTW和OpenMP缓存未命中率相比，3D-FFT全局转置优化算法缓存未命中率几乎为0。与FFTW计算三维离散傅里叶变换的库函数相比，在2核心下，3D-FFT全局转置优化算法算法性能是其1.59倍，8核心下是4.93倍。若对FFTW库函数使用OpenMP开辟多个线程进行加速，3D-FFT全局转置优化算法性能表现在2核心与8核心下分别是多线程OpenMP的1.07倍与1.48倍。

目录

第一章 绪 论

1.1课题研究的背景和意义

1.2国内外研究现状

1.3主要研究内容

1.4论文结构

第二章 3D-FFT算法2D分解与计算

2.1共享内存多核处理器

2.2 3D-FFT算法

2.3 2D分解并行3D-FFT算法

2.4 FFT计算

2.5算法复杂度分析

2.6本章小结

第三章 基于缓存的3D-FFT的任务划分算法

3.1 基于线程亲和的任务划分

3.2 缓存行填充算法

3.3实验与分析

3.4算法复杂度分析

3.5本章小结

第四章 面向多核的3D-FFT全局转置算法

4.1 问题的描述

4.2 全局转置算法

4.3全局转置通信代价分析

4.4 3D-FFT算法多级并行策略

4.5 算法复杂度分析

4.6 本章小结

第五章 实验测试与性能评价

5.1目标评价参数

5.2 Sniper Simulator 简介

5.3 3D-FFT全局转置优化算法算法性能

5.4 3D-FFT全局转置优化算法功率消耗

5.5 3D-FFT与其它方法对比

5.6本章小结

结论

参考文献

声明

致谢