并行编程原理及程序设计

￥*******************实践教学*******************兰州理工大学@理学院2016年春季学期并行计算课程设计!专业班级： 2013级信息与计算科学'姓名：学号：指导教师：成绩：摘要FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。

它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。

设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N^2次运算。

当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）^2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。

这样变换以后，总的运算次数就变成N+2（N/2）^2=N+N^2/2。

继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。

而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT 运算单元，那么N点的DFT变换就只需要Nlog(2)(N)次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性关键字：FFT 蝶式计算傅里叶变换。

目录摘要 (2)目录 (3)一、题目及要求 (4)题目 (4)要求 (4)二、算法设计与算法原理 (5)*算法原理与设计 (5)设计求解步骤 (6)三、算法描述与算法流程 (7)算法描述 (7)流程图 (9)四、源程序代码与运行结果 (10)源程序 (10)运行结果 (16)—五、算法分析及其优缺点 (17)算法分析 (17)优缺点 (18)六、总结 (19)七、参考文献 (20)一、题目及要求题目"对给定的α=（1,2，4，3，8，6，7，2），利用串行FFT递归算法(蝶式递归计算原理)计算其傅里叶变换的结果要求利用串行递归与蝶式递归原理，对给定的向量求解傅里叶变换的结果二、算法设计与算法原理算法原理与设计令 为n/2次单位元根，则有 . 将b 向量的偶数项和奇数项分别记为、和 注意推导中反复使用图》)2//(2~n i eπω＝2~ωω＝Tn b b b ),...,,(220-T n b b b ),...,,(131-Tn b b b ),...,,(1102-'''T nb b b ),...,,(1102-'''''',,1,1,1ln 2/p psn n n ωωωωω==-==+?设计求解步骤()()()()()()()DFTa a a a a ab b b l a a a a a a a a a a a aa a a a a a a a a aa a a a a a a a a a ab b T n T n n k k kk l k n l l l n l l l n l l l lln l n l l l l l n k kk l l l n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n 的是因此，向量奇数时：))(),...,(),((),...,,(1,,1,0)(~)(~)(~)(~)()()()()(11111013121011112222110111122224112011121211122241201)12(11)12(1)12(1)12(12)12(211201)12(122222222222222222222222222222222---+--=+----++----++---+----+-++++-+-++-=++----=-=-++-+-+-=-++-+-+-=----++++=++++++++===''∑∑ωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωω ()()()()DFTa a a a a ab b b l a a a aa a a a a a a a a a a a a a a a a a a a a a ab b T n T n n k k kl k n l l l n l l l n l l l l l l n k klk l l n n n n n n n n n n n n n n n n n n n n n 的是向量因此，偶数时：),...,,(),...,,(1,,1,0)(~)(~)(~)(~)()()()()(1111022021111222110111222411201122412112241201022222222222222222222222--+--=+---++---++--++---=+++-=+=++++++++=++++++++=+++++++++==='∑∑ ωωωωωωωωωωωωωω三、算法描述与算法流程算法描述n=8的FFT蝶式计算图图&图 FFT递归计算流程图流程图飞是否 是否是否》图输入序列长度/输入序列对应值（例如计算出前size_x/2个 exp(-j*2π*k/size_x)个值，级数i>=输出fft 结果序列开始结束计算出该级需要的W 的个数l.@组起始下标加2*l该级该组元素序数k>=X[j+k] X[j+k]lX[j+k+l]*W[(size_x/2/l)*k] X[j+k+l]-1\四、源程序代码与运行结果源程序/************FFT***********/ eal,&x[i].img);initW(); eal=cos(2*PI/size_x*i); mg=-1*sin(2*PI/size_x*i); f",x[i].real); mg>= f\n",x[i].img);else if(fabs(x[i].img)< f\n",fabs(x[i].img));并行计算－结构算法编程. 高等教育出版社（修订版），2003[2] 陈国良编著. 并行算法的设计与分析. 高等教育出版社（修订版），2002[3] 陈国良等编著. 并行计算机体系结构. 高等教育出版社，2002[4] 李晓梅等编著. 并行算法. 湖南科技出版社，1992[5] 沈志宇等编著. 并行程序设计. 国防科大出版社，1997[6] 孙家昶等编著. 网络并行计算与分布式编程环境. 科学出版社，1996[7] 王鼎兴，陈国良编著. 互联网络结构分析. 科学出版社，1990[8] 许士良编著. 计算机常用算法（第二版）. 清华大学出版社，1996[9] 都志辉编著. 高性能计算并行技术—MPI并行程序设计，清华大学出版社，2001。

基于MPI的并行程序设计MPI（Message Passing Interface）是一种用于并行计算的消息传递编程接口。

它提供了一组用于在多个进程之间传递消息的函数，使得在并行计算中能够更加高效地利用计算资源。

本文将介绍MPI的基本原理和并行程序设计的一些基本概念。

MPI的基本原理是基于消息传递的，并行计算模型。

在MPI中，计算节点被组织成一个逻辑拓扑结构，每个节点都可以通过消息传递的方式与其他节点进行通信。

这种消息传递方式可以通过网络或者高速互连的硬件来实现，使得多个节点之间可以并行地进行计算。

并行程序设计的关键是分割问题和分配任务。

在MPI中，通常将任务分割成若干个较小的子任务，然后将这些子任务分配给不同的计算节点进行并行计算。

每个计算节点独立地计算自己的子任务，并通过消息传递与其他节点进行通信，最终将计算结果汇总起来。

并行程序设计的另一个重要概念是同步和异步操作。

同步操作是指在发送或接收消息时，发送进程或接收进程需要等待对应的操作完成后才能继续执行。

而异步操作则是指发送和接收消息的操作不会阻塞进程的执行，进程可以继续执行其他的计算操作。

MPI提供了一系列的同步和异步通信操作，例如MPI_Isend和MPI_Irecv函数，用于实现非阻塞的消息传递。

在并行程序设计中，性能优化是一个重要的课题。

为了提高并行计算的效率，可以采用一些优化技术，例如流水线计算、任务分发和负载均衡。

流水线计算是指将计算任务划分为若干个阶段，并将每个阶段分配给不同的计算节点进行并行计算。

任务分发是指将计算任务动态地分配给空闲的计算节点，以实现任务的并行处理。

负载均衡是指将计算任务均匀地分配给不同的计算节点，以避免一些节点的计算负载过重。

总的来说，MPI是一种基于消息传递的并行编程接口，提供了一系列的通信原语，用于在计算节点之间进行消息传递。

通过合理地分割问题、分配任务和优化计算过程，可以实现高效的并行程序设计。

在当前的多核计算环境中，MPI仍然是一种重要的并行编程模型，在科学计算、大规模数据分析等领域有着广泛的应用。

并行编程模型和并行算法设计研究随着计算机硬件的发展，单个CPU的计算能力已经无法满足人们对于计算速度和效率的要求。

因此，使用并行化的思想来进行计算已经成为了现代计算的必须选择。

并行编程模型和并行算法则是实现并行计算的重要工具。

1. 并行编程模型并行编程模型是指编写并行程序时所采用的编程方式和程序结构。

不同的并行计算机系统使用不同的并行编程模型。

同时，不同的编程语言也支持不同的并行编程模型。

主流的并行编程模型有：共享内存模型、分布式内存模型、数据流模型等。

共享内存模型是指所有的处理器都能够访问同一块共享内存。

不同的处理器之间通过共享内存进行数据交换。

具体来说，每个处理器都有自己的程序代码和执行线程，但是它们共享同一个内存空间，处理器之间可以共享变量和数据。

共享内存模型适用于处理计算密集型的问题，例如矩阵乘法，图像处理等。

分布式内存模型是指每个处理器有独立的内存空间，不同的处理器通过网络进行数据交换。

分布式内存模型适用于处理大规模数据的问题，例如分布式搜索算法，网络流等。

数据流模型是指程序中的每个任务（数据处理的最小单元）都会自动调度，并且只有当其需要的输入数据已经可用时才会被执行。

数据流模型适用于一些数据密集型的数据流应用中，例如视频处理、音频处理等。

2. 并行算法设计并行算法则是指在并行计算机上开发有效的算法以解决各种应用问题。

并行算法设计的一个重要目标是提高算法的效率。

同时，在设计并行算法时还必须考虑到可扩展性，即算法必须能够有效地扩展到更多的处理器。

并行算法设计的过程包括：确定并行编程模型、定义问题的并行算法、确定并行算法的并行性。

在确定并行编程模型的同时，一些问题需要考虑到如何将问题分解为多个子问题，如何将数据分配到不同的处理器，如何同步不同的处理器等。

在定义问题的并行算法时，采用一些基本算法，例如排序算法、图搜索算法等，并且利用并行算法所具有的特点进行改进和优化。

同时，还要考虑到并行算法的负载分配、负载平衡等问题。

并行程序设计并行程序设计并行程序设计是指将一个任务或问题分解成多个子任务，然后同时执行这些子任务，以提高程序的运行效率和响应速度。

本文将介绍并行程序设计的概念、原则和常用的并行编程模型。

概念并行程序设计是一种计算思维方式，通过利用计算机多核心、多处理器或者分布式系统的能力，将一个大的问题分解成多个小的子问题，并且让这些子问题可以同时被处理。

通过同时处理多个子问题，可以大大提高程序的处理速度。

并行程序设计原则并行程序设计有一些基本原则，下面是其中几个重要的原则：1. 任务划分：将一个大的任务划分成多个小的子任务。

划分任务时需要注意任务之间的依赖关系，以保证划分后的任务可以并行执行。

2. 任务分配：将划分后的子任务分配给可用的计算资源，如多核心、多处理器或分布式系统中的节点。

任务分配需要考虑计算资源的负载均衡，以充分利用计算资源的能力。

3. 任务通信：并行程序中的任务之间通常需要进行数据交换或同步操作。

任务通信需要合理选择通信方式，并通过合适的同步机制来确保数据的一致性和正确性。

4. 任务合并：在一些情况下，多个子任务的处理结果需要进行合并。

任务合并需要保证合并操作的正确性和效率，同时还要考虑合并操作可能引入的额外开销。

并行编程模型为了简化并行程序的设计与开发，人们提出了一系列并行编程模型。

下面介绍几种常用的并行编程模型：1. 共享内存模型：多个线程共享同一块内存地质空间，线程之间通过读写共享内存来进行通信和同步。

常见的共享内存模型有OpenMP和Cilk等。

2. 消息传递模型：多个进程或线程通过消息的方式进行通信。

每个进程或线程有独立的内存空间，通过发送和接收消息来实现进程间的通信和同步。

常见的消息传递模型有MPI和PVM等。

3. 数据流模型：任务之间通过数据流进行通信。

任务根据数据的可用性来进行执行，并将处理结果传递给下游任务。

数据流模型可以以图形化的方式表示任务之间的依赖关系。

常见的数据流模型有GPGPU和FPGA等。

本科生课程大纲课程属性：公共基础/通识教育/学科基础/专业知识/工作技能，课程性质：必修、选修一、课程介绍1.课程描述：《并行编程原理与程序设计》是地球信息科学与技术专业海洋测绘与地理信息系统方向的选修课，也是勘查技术与工程专业的选修课。

地球物理信息解译中的计算量十分庞大，常规串行电脑和软件无法解决地球物理资料的解译问题，必须采用并行算法合并行计算机来解决地球物理资料的处理、解释合反演工作。

目前，微机群和GPU机群在地球物理领域的应用日益广泛，“地球信息科学与技术”和“勘查技术与工程”专业必需掌握并行编程的基本原理与方法才能实现地学信息高效解译得目的，本课程主要学习基于微机群的MPI 程序设计方法和基于GPU集群的CUDA程序设计方法，并进行适当的上机实践。

通过本课程的学习，可使学生了解和掌握大型科学与工程问题中的基本并行编程技术，初步具备编写大型并行应用程序的能力。

2.设计思路：本课程的讲授内容主要包括两大部分：第一部分：MPI并行程序设计部分：第一章并行程序设计基础主要内容：并行计算；并行编程模型与并行语言；并行算法第二章 MPI简介主要内容：什么是MPI；MPI的目的，产生与发展；MPI的语言绑定；目前主要的MPI实现；SPMD并行机上并行程序的执行过程第三章第一个MPI程序主要内容：MPI实现的“Hello World”；c与Fortran语言的MPI程序的一些惯例第四章六个接口构成的MPI子集主要内容：子集介绍；MPI预定义的数据类型；MPI数据类型匹配与数据转换；MPI消息；第五章简单的MPI程序示例主要内容：获取机器名字和MPI版本号；数据接力传送；任意进程间互相问候，任意源和任意标识的使用；编写安全的MPI程序第六章 MPI并行程序的两种基本模式主要内容：对等模式的MPI程序设计；主从模式的MPI程序设计，标准通信模式的特点与消息传递过程第七章不同通信模式MPI并行程序设计主要内容：四种通信模式（标准，缓存，同步与就绪），了解集中通信模式的划分依据，掌握四种通信模式的优缺点及实现方式第八章非阻塞通信MPI程序设计主要内容：阻塞通信；非阻塞通信简介；非阻塞标准发送与接收；非阻塞通信与其他三种通信模式的结合；非阻塞通信的完成第九章组通信MPI程序设计主要内容：组通信的消息通信功能，同步功能和计算功能；广播；收集；散发；组收集；全互换、同步、归约、组归约、归约并散发操作的函数形式、使用方法与执行过程；几个相关示例程序第二部分：CUDA并行程序设计部分：第一章引言主要内容：异构并行算法，现代GPU的体系结构，为什么需要更高的速度和并行化，应用程序加速，并行编程语言和模型第二章 GPU计算的发展历程主要内容：图形流水线的发展，固定功能的图形流水线时代，可编程实时图形流水线的发展，图形与计算结合的处理器，GPGPU：一个中间步骤，GPU计算，可扩展的GPU，发展近况，未来的发展趋势第3章 CUDA简介主要内容：PC架构，GPU硬件结构，CPU与GPU，数据并行性，CUDA的程序结构第4章 CUDA环境搭建主要内容：简介，在Windows下安装软件开发工具包，Visual Studio，工程，64位用户，创建工程，Linux，安装调试器，编译模型，错误处理第5章线程网格、线程块以及线程，主要内容：简介，线程，问题分解，CPU与GPU的不同，任务执行模式，GPU 线程，CUDA内核，线程块，线程网格，跨幅与偏移，X与Y方向的线程索引，线程束，分支，GPU的利用率，线程块的调度第6章数据并行执行模型，主要内容：向量加法kernel函数，设备全局存储器与数据传输，kernel函数与线程，函数声明，启动kernel函数，预定义变量，CUDA的线程组织，线程与多维数据映射，矩阵乘法——一个更加复杂的kernel函数，线程同步和透明的可扩展性，线程块的资源分配，线程调度与容许时延第三部分：上机实践部分：本课程实践部分的设计思路为：以并行程序设计的方法为主线，结合地学信息处理中的实际问题，让学生掌握MPI和CUDA程序设计的基本方法和技能。

并行程序设计原理随着计算机技术的飞速发展，计算机系统的处理能力不断提高，但是单个处理器的性能已经无法满足现代应用的大量计算需求。

人们开始将多个处理器组成一个并行计算机系统，以提高处理能力。

并行计算机系统具有多个处理器，并且这些处理器能够同时处理不同的任务，从而提高计算能力。

利用并行计算机系统开发并行程序需要特定的技术和方法。

本文将介绍并行程序设计的原理。

1. 并行处理的基本原理并行处理是指多个处理器同时执行不同的任务。

在并行计算机系统中，每个处理器都可以独立地执行任务，而这些处理器之间通过共享存储器进行通信和数据交换。

（1）任务分配：并行处理需要将任务分配给多个处理器，以实现多个处理器的协同工作。

（2）通信与同步：并行处理需要处理器之间进行通信和同步，确保数据的正确性和计算的一致性。

（3）负载均衡：在并行计算机系统中，要保证所有处理器都得到合理的任务分配，以实现尽可能平衡的负载，从而提高整个系统的效率和性能。

2. 并行程序的基本特点并行程序具有一下几个特点：（1）可扩展性：并行程序可以随着处理器数量的不断增加而提高计算能力，形成高性能的计算机系统。

（2）复杂性：并行程序处理的问题一般比串行程序复杂，需要更多的算法和技巧，也需要更加严格的编程规范和方法。

（3）可重复性：并行程序的结果应该是可重复的，即在多次执行相同的任务时得到相同的结果。

（4）可移植性：并行程序应该具有可移植性，即可以在不同的计算机系统中执行，而不需要对程序进行太多的修改。

（1）分解问题：设计并行程序需要将整个问题分解成多个子问题，以方便并行计算。

（2）任务调度：设计并行程序需要合理地安排任务的执行顺序，以尽可能避免处理器的空闲时间，提高计算效率。

4. 并行程序的设计方法在设计并行程序时，需要遵循一些基本的方法：（1）数据并行：数据并行是指将数据分成多个部分，分配给不同的处理器并行处理。

这种方法适用于数据独立性较强的问题。

（4）管道并行：管道并行是指将整个计算过程分成多个部分，每个部分交替执行。

并行编程原理及程序设计并行编程是一种编程方法，通过同时执行多个计算任务来提高计算机程序的性能和效率。

在传统的串行编程中，计算机程序按照顺序执行指令，只有一个计算任务在运行。

而并行编程可以同时运行多个计算任务，并利用多核处理器、并发技术和分布式系统来实现。

并行编程的核心原则是任务分解和任务调度。

首先，需要将一个大的计算任务分解为多个小的子任务，这些子任务可以并行执行。

然后，通过合理的任务调度算法将这些子任务分配给不同的处理器或计算节点进行执行。

最后，将子任务的计算结果合并得到最终的计算结果，完成整个并行计算过程。

并行编程的程序设计需要考虑以下几个方面：1.并行算法的设计：针对不同的并行计算问题，需要设计符合并行计算模型的算法。

并行算法通常包括任务分解、任务调度、数据通信等关键步骤。

合理的算法设计可以充分利用并行计算资源，提高程序的速度和效率。

2.数据共享与同步：在并行编程中，多个计算任务可能需要共享数据。

数据共享的正确性和一致性是保证并行程序正确运行的关键。

为了避免数据竞争和死锁等并发问题，需要使用同步机制，如锁、信号量、条件变量等来确保数据访问的顺序和正确性。

3.并行性调度：并行编程中，任务调度的策略对程序的性能和效率有着重要影响。

任务调度算法应根据任务的性质、数据依赖关系和计算资源的情况进行合理的调度决策，以最大程度地提高并行任务的并发度和执行效率。

4.数据分布和通信：在分布式并行编程中，不同的计算节点之间需要进行数据交换和通信。

数据分布的合理性和通信开销的减少是影响分布式并行程序性能和效率的关键因素。

合理的数据分布和高效的通信机制可以减少通信开销，提高程序的性能和可扩展性。

5. 调试和优化：并行编程中，bug 的调试和性能的优化具有一定的挑战性。

并行程序的错误可能涉及到多个计算任务和多个计算节点，调试过程相对复杂。

而性能优化则需要通过有效的算法设计、数据分布和通信机制来减少资源竞争，提高并行任务的并发度和执行效率。