并行计算Parallel Computing
主讲人徐云
Spring, 2014
第二篇并行算法的设计
第五章并行算法与并行计算模型第六章并行算法基本设计策略第七章并行算法常用设计技术第八章并行算法一般设计过程
第七章并行算法常用设计技术7.1 划分设计技术
7.1.1 均匀划分技术
7.1.2 方根划分技术
7.1.3 对数划分技术
7.1.4 功能划分技术
7.2 分治设计技术
7.3 平衡树设计技术
7.4 倍增设计技术
7.5 流水线设计技术
均匀划分技术（1）
划分方法
n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p
示例：MIMD-SM模型上的PSRS排序
begin
(1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个p i处理
A[(i-1)n/p+1..in/p]
(2)局部排序：p i调用串行排序算法对A[(i-1)n/p+1..in/p]排序
(3)选取样本：p i从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素
(4)样本排序：用一台处理器对p2个样本元素进行串行排序
(5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并
播送给其他p i
(6)主元划分：p i按主元将有序段A[(i-1)n/p+1..in/p]划分成p段
(7)全局交换：各处理器将其有序段按段号交换到对应的处理器中
(8)归并排序：各处理器对接收到的元素进行归并排序
end.
均匀划分技术（2）
例7.1 PSRS 排序过程。N=27，p=3，PSRS 排序如下：
15464893396729114366940896197122154539784583227337220614153946487291931221364054616989972027323353587284976397212406920337261220
33
39
40
69
72
72
33
69
61415394648729193122136405461698997202732335358728497
6141561415394648729193122136405461698997202732335358728497
394648729193122136405461698997202732335358728497
(a)均匀划分：(b)局部排序：(c)正则采样：(d)采样排序：(e)选择主元：
(f)主元划分：(h)归并排序：(g)全局交换：
第七章并行算法常用设计技术7.1 划分设计技术
7.1.1 均匀划分技术
7.1.2 方根划分技术
7.1.3 对数划分技术
7.1.4 功能划分技术
7.2 分治设计技术
7.3 平衡树设计技术
7.4 倍增设计技术
7.5 流水线设计技术
方根划分技术（1）
划分方法
n 个元素A[1..n]分成A[(i -1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2)
示例：SIMD -CREW 模型上的Valiant 归并(1975年发表)
//有序组A[1..p]、B[1..q], (假设p<=q), 处理器数begin
(1)方根划分: A,B 分别按；(2)段间比较: A 划分元与B 划分元比较(至多对)，
确定A 划分元应插入B 中的区段；
(3)段内比较: A 划分元与B 相应段内元素进行比较，并插入适当的位置；(4)递归归并: B 按插入的A 划分元重新分段，与A 相应段(A 除去原划分元)
构成了成对的段组，对每对段组递归执行(1)~(3)，直至A 组为0时，递归结束; 各组仍按分配处理器；
end.
?
?
pq
k =??pq k =????????）、分成若干段（和q j p i q j p i ~1~1==????q p ???pq k =
方根划分技术（2）
示例: A={1,3,8,9,11,13,15,16},p=8; B={2,4,5,6,7,10,12,14,17},q=9
A: 1 3 8* 9 11 13* 15 16
B: 2 4 5* 6 7 10* 12 14 17*
????)
2,3,
8===p p p （????)
3,3,
9===q q q （{(1)(2)
A: 1 3 8* 9 11 13* 15 16
B: 2 4 5* 6 7 10* 12 14 17*
{ (3)
A 1: 1 3 (p 1=2) A 2: 9 11 (p 2=2) A 2: 15 16
B 1: 2 4 5 6 7 8(q 1=6) B 2: 10 12 13(q 2=3) B 3: 14 17A 1: 1 3* (p 1=2) ...... ......B 1: 2 4 5* 6 7 8*(q 1=6) ...... ......A 11: 1* A 11: ...... ......B 11: 2 3* B 12: 4 5 6 7 8 ...... ......A:
B: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
方根划分技术（3）
算法分析
(1)算法在并行递归过程中所需的处理器数≤??pq k = 段间比较:????q p ?比较对数≤??k pq ＝； 段内比较:
??????
k pq q p ＝）－（
≤?1
递归调用: 设A,B 分成若干子段对为(p 1,q 1), (p 2,q 2),…… 则∑p i ≤p, ∑q i ≤q, 由Cauchy 不等式＝>
?
???????k pq q p q p q p i
i i i i i =≤≤
≤
∑∑∑∑
综上，整个过程可用处理器数??pq k =完成。
(2)时间分析
记λi 是第i 次递归后的A 组最大长度，＝>p =0λ, ????
i
p i i ?≤≤≤?2
1"λλ
算法在C i 常数=λ时终止递归，即12+≤≤?C p C i
常数常数＝> 1log log C p i 常数+≤ 由(1)知算法中其他各步的时间为O(1), 所以Valiant 归并算法时间
q p p O q p t k ≤=)
log (log ),(
第七章并行算法常用设计技术7.1 划分设计技术
7.1.1 均匀划分技术
7.1.2 方根划分技术
7.1.3 对数划分技术
7.1.4 功能划分技术
7.2 分治设计技术
7.3 平衡树设计技术
7.4 倍增设计技术
7.5 流水线设计技术
对数划分技术
划分方法
n个元素A[1..n]分成A[(i-1)logn+1..ilogn]，i=1~n/logn
示例：PRAM-CREW上的对数划分并行归并排序
(1)归并过程: 设有序组A[1..n]和B[1..m]
j[i]=rank(b ilogm:A)为b ilogm在A中的位序，即A中小于等于b ilogm的元素个数(2)例：A=(4,6,7,10,12,15,18,20), B=(3,9,16,21) n=8, m=4
=>logm=log4=2
=> j[1]=rank(b logm:A)=rank(b2:A)=rank(9:A)=3, j[2]=…=8
B0: 3, 9 B1: 16, 21
A0: 4, 6, 7 A1: 10, 12, 15, 18, 20
A和B归并化为(A0, B0)和(A1, B1)的归并
第七章并行算法常用设计技术7.1 划分设计技术
7.1.1 均匀划分技术
7.1.2 方根划分技术
7.1.3 对数划分技术
7.1.4 功能划分技术
7.2 分治设计技术
7.3 平衡树设计技术
7.4 倍增设计技术
7.5 流水线设计技术
功能划分技术（1）
划分方法
n个元素A[1..n]分成等长的p组，每组满足某种特性。
示例：(m, n)选择问题(求出n个元素中前m个最小者) 功能划分：要求每组元素个数必须大于m；
算法：p194算法7.4
输入：A=(a1,…,a n); 输出：前m个最小者；
Begin
(1) 功能划分：将A划分成g=n/m组，每组含m个元素；
(2) 局部排序：使用Batcher排序网络将各组并行进行排序；
(3) 两两比较：将所排序的各组两两进行比较，从而形成MIN序列；
(4) 排序-比较：对各个MIN序列，重复执行第(2)和第(3)步，直至
选出m个最小者。
End
功能划分技术（2）
第七章并行算法常用设计技术7.1 划分设计技术
7.2 分治设计技术
7.2.1 并行分治设计步骤
7.2.2 双调归并网络
7.3 平衡树设计技术
7.4 倍增设计技术
7.5 流水线设计技术
并行分治设计步骤
将输入划分成若干个规模相等的子问题；
同时(并行地)递归求解这些子问题； 并行地归并子问题的解，直至得到原问题的解。
第七章并行算法常用设计技术7.1 划分设计技术
7.2 分治设计技术
7.2.1 并行分治设计步骤
7.2.2 双调归并网络
7.3 平衡树设计技术
7.4 倍增设计技术
7.5 流水线设计技术
双调归并网络（1）
双调序列(p195定义7.2)
(1,3,5,7,8,6,4,2,0)(8,7,6,4,2,0,1,3,5)(1,2,3,4,5,6,7,8)以上都是双调序列
Batcher 定理
给定双调序列(x 0,x 1,…,x n -1), 对于s i =min{x i ,x i+n/2}和
l i =max{x i ,x i+n/2}，则小序列(s 0,s 1,…,s n -1)和大序列(l 0,l 1,…,l n -1)仍是双调序列。
双调归并网络（2） (4,4)双调归并网络
双调归并网络（3） Batcher双调归并算法
输入：双调序列X=(x0,x1,…,x n-1)
输出：非降有序序列Y=(y0,y1,…,y n-1)
Procedure BITONIC_MERG(x)
Begin
(1)for i=0 to n/2-1 par-do
(1.1) s i=min{x i,x i+n/2}
(1.2) l i=max{x i,x i+n/2}
end for
(2)Recursive Call:
(2.1)BITONIC_MERG(MIN=(s0,…,s n/2-1))
(2.2)BITONIC_MERG(MIN=(l0,…, l n/2-1))
(3)output sequence MIN followed by sequence MAX End
课程实验报告课程名称：并行与串行数据结构与算法 专业班级：ACM1301 学号：U201315057 姓名：李海锋 指导教师：陆枫 报告日期：2015.9.23 计算机科学与技术学院
目录 1、课程设计概述 (2) 1.1 课设目的 (2) 1.2 课设要求 (2) 1.3 实验环境 (3) 2、系统总体设计 (4) 2.1 系统主模块结构体 (4) 2.2 找附近的最近的三个某地 (5) 2.3 找两点之间最短路径 (6) 2.4 数据录入模块 (7) 3、数据结构和算法详细设计 (7) 3.1 地图的存储 (7) 3.1.1 地图背景图片的存储 (7) 3.1.2 地图点 (7) 3.2 找附近的最近的特定地点（findNearby） (8) 3.3 找最短路径 (8) 4、程序实现简要说明 (9) 4.1开发环境 (9) 4.2 支持包 (9) 4.3 函数原型 (10) MainActivity.java:实现了地图主要功能 (10) Setting.java：地图数据的录入 (12) 4.4 函数功能调用关系 (14) MainActivity.java：地图主要功能程序 (15) Setting.java：数据录入程序 (15) 5、程序测试及结果分析 (16) 5.1 功能测试 (16)
5.2 测试结果分析 (22) 6、复杂度分析 (22) 6.1 输入地点名查找，鼠标点击显示 (22) 6.2 找两点之间的最短路径(dijkstra) (22) 6.3 找附近最近的三个某地 (22) 7、软件的用户使用说明 (23) 8、特色与不足 (23) 8.1 特色 (23) 8.2 不足 (23) 九、主要参考文献 (24)
并行计算综述 姓名：尹航学号：S131020012 专业：计算机科学与技术摘要：本文对并行计算的基本概念和基本理论进行了分析和研究。主要内容有：并行计算提出的背景，目前国内外的研究现状，并行计算概念和并行计算机类型，并行计算的性能评价，并行计算模型，并行编程环境与并行编程语言。 关键词：并行计算；性能评价；并行计算模型；并行编程 1. 前言 网络并行计算是近几年国际上并行计算新出现的一个重要研究方向，也是热门课题。网络并行计算就是利用互联网上的计算机资源实现其它问题的计算，这种并行计算环境的显著优点是投资少、见效快、灵活性强等。由于科学计算的要求，越来越多的用户希望能具有并行计算的环境，但除了少数计算机大户（石油、天气预报等）外，很多用户由于工业资金的不足而不能使用并行计算机。一旦实现并行计算，就可以通过网络实现超级计算。这样，就不必要购买昂贵的并行计算机。 目前，国内一般的应用单位都具有局域网或广域网的结点，基本上具备网络计算的硬件环境。其次，网络并行计算的系统软件PVM是当前国际上公认的一种消息传递标准软件系统。有了该软件系统，可以在不具备并行机的情况下进行并行计算。该软件是美国国家基金资助的开放软件，没有版权问题。可以从国际互联网上获得其源代码及其相应的辅助工具程序。这无疑给人们对计算大问题带来了良好的机遇。这种计算环境特别适合我国国情。 近几年国内一些高校和科研院所投入了一些力量来进行并行计算软件的应用理论和方法的研究，并取得了可喜的成绩。到目前为止，网络并行计算已经在勘探地球物理、机械制造、计算数学、石油资源、数字模拟等许多应用领域开展研究。这将在计算机的应用的各应用领域科学开创一个崭新的环境。 2. 并行计算简介[1] 2.1并行计算与科学计算 并行计算（Parallel Computing），简单地讲，就是在并行计算机上所作的计算，它和常说的高性能计算（High Performance Computing）、超级计算（Super Computing）是同义词，因为任何高性能计算和超级计算都离不开并行技术。
西安科技大学 计算机科学与技术学院 实习报告 课程：大数据和并行计算 班级：网络工程 姓名： 学号：
前言 大数据技术(big data)，或称巨量资料，指的是所涉及的资料量规模巨大到无法通过目前主流软件工具，在合理时间内达到撷取、管理、处理、并整理成为帮助企业经营决策更积极目的的资讯。在维克托·迈尔-舍恩伯格及肯尼斯·库克耶编写的《大数据时代》中大数据指不用随机分析法（抽样调查）这样的捷径，而采用所有数据进行分析处理。大数据的4V特点：Volume（大量）、Velocity（高速）、Variety（多样）、Value（价值）。 特点具体有： 大数据分析相比于传统的数据仓库应用，具有数据量大、查询分析复杂等特点。《计算机学报》刊登的“架构大数据：挑战、现状与展望”一文列举了大数据分析平台需要具备的几个重要特性，对当前的主流实现平台——并行数据库、MapReduce及基于两者的混合架构进行了分析归纳，指出了各自的优势及不足，同时也对各个方向的研究现状及作者在大数据分析方面的努力进行了介绍，对未来研究做了展望。 大数据的4个“V”，或者说特点有四个层面：第一，数据体量巨大。从TB级别，跃升到PB级别；第二，数据类型繁多。前文提到的网络日志、视频、图片、地理位置信息等等。第三，处理速度快，1秒定律，可从各种类型的数据中快速获得高价值的信息，这一点也是和传统的数据挖掘技术有着本质的不同。第四，只要合理利用数据并对其进行正确、准确的分析，将会带来很高的价值回报。业界将其归纳为4个“V”——Volume（数据体量大）、Variety（数据类型繁多）、Velocity（处理速度快）、Value（价值密度低）。 从某种程度上说，大数据是数据分析的前沿技术。简言之，从各种各样类型的数据中，快速获得有价值信息的能力，就是大数据技术。明白这一点至关重要，也正是这一点促使该技术具备走向众多企业的潜力。 1.大数据概念及分析 毫无疑问，世界上所有关注开发技术的人都意识到“大数据”对企业商务所蕴含的潜在价值，其目的都在于解决在企业发展过程中各种业务数据增长所带来的痛苦。 现实是，许多问题阻碍了大数据技术的发展和实际应用。 因为一种成功的技术，需要一些衡量的标准。现在我们可以通过几个基本要素来衡量一下大数据技术，这就是——流处理、并行性、摘要索引和可视化。 大数据技术涵盖哪些内容? 1.1流处理 伴随着业务发展的步调，以及业务流程的复杂化，我们的注意力越来越集中在“数据流”而非“数据集”上面。 决策者感兴趣的是紧扣其组织机构的命脉，并获取实时的结果。他们需要的是能够处理随时发生的数据流的架构，当前的数据库技术并不适合数据流处理。 1.2并行化 大数据的定义有许多种，以下这种相对有用。“小数据”的情形类似于桌面环境，磁盘存储能力在1GB到10GB之间，“中数据”的数据量在100GB到1TB之间，“大数据”分布式的存储在多台机器上，包含1TB到多个PB的数据。 如果你在分布式数据环境中工作，并且想在很短的时间内处理数据，这就需要分布式处理。 1.3摘要索引 摘要索引是一个对数据创建预计算摘要，以加速查询运行的过程。摘要索引的问题是，你必须为要执行的查询做好计划，因此它有所限制。 数据增长飞速，对摘要索引的要求远不会停止，不论是长期考虑还是短期，供应商必须对摘要索引的制定有一个确定的策略。 1.4数据可视化 可视化工具有两大类。
《并行算法设计与分析》考题与答案 一、1.3，处理器PI的编号是： 解：对于n ×n 网孔结构,令位于第j行，第k 列（0≤j，k≤n-1）的处理器为P i（0≤i≤n2-1）。以16处理器网孔为例,n=4（假设j、k由0开始）： 由p0=p(j,k)=p(0,0) P8=p(j,k)=p(2,0) P1=p(j,k)=p(0,1) P9=p(j,k)=p(2,1) P2=p(j,k)=p(0,2) P10=p(j,k)=p(2,2) P3=p(j,k)=p(0,3) P11=p(j,k)=p(2,3) P4=p(j,k)=p(1,0) P12=p(j,k)=p(3,0) P5=p(j,k)=p(1,1) P13=p(j,k)=p(3,1) P6=p(j,k)=p(1,2) P14=p(j,k)=p(3,2) P7=p(j,k)=p(1,3) P15=p(j,k)=p(3,3) 同时观察i和j、k之间的关系，可以得出i的表达式为：i= j * n+k
一、1.6矩阵相乘（心动算法） a)相乘过程 设 A 矩阵= 121221122121 4321 B 矩阵=1 23443212121121 2 【注】矩阵元素中A(i,l)表示自左向右移动的矩阵，B(l,j)表示自上向下移动的矩阵，黑色倾斜加粗标记表示已经计算出的矩阵元素,如12, C(i,j)= C(i,j)+ A(i,l)* B(l,j) 1 2、
4、
6、
8、
10 计算完毕 b)可以在10步后完成，移动矩阵长L=7，4*4矩阵N=4,所以需要L+N-1=10
基于FPGA的并行计算技术 更新于2012-03-13 17:15:57 文章出处:互联网 1 微处理器与FPGA 微处理器普遍采用冯·诺依曼结构，即存储程序型计算机结构，主要包括存储器和运算器2个子系统。其从存储器读取数据和指令到运算器，运算结果储存到存储器，然后进行下一次读取-运算-储存的操作过程。通过开发专门的数据和指令组合，即控制程序，微处理器就可以完成各种计算任务。冯·诺依曼型计算机成功地把信息处理系统分成了硬件设备和软件程序两部分，使得众多信息处理问题都可以在通用的硬件平台上处理，只需要开发具体的应用软件，从而极大地降低了开发信息处理系统的复杂性。然而，冯·诺依曼型计算机也有不足之处，由于数据和指令必须在存储器和运算器之间传输才能完成运算，使得计算速度受到存储器和运算器之间信息传输速度的限制，形成所谓的冯·诺依曼瓶颈[1]；同时，由于运算任务被分解成一系列依次执行的读取-运算-储存过程，所以运算过程在本质上是串行的，使并行计算模式在冯·诺依曼型计算机上的应用受到限制。 受到半导体物理过程的限制，微处理器运算速度的提高已经趋于缓慢，基于多核处理器或者集群计算机的并行计算技术已经逐渐成为提高计算机运算性能的主要手段。并行计算设备中包含多个微处理器，可以同时对多组数据进行处理，从而提高系统的数据处理能力。基于集群计算机的超级计算机已经成为解决大型科学和工程问题的有利工具。然而，由于并行计算设备中的微处理器同样受冯·诺依曼瓶颈的制约，所以在处理一些数据密集型，如图像分析等问题时，计算速度和性价比不理想。 现场可编程门阵列（FPGA）是一种新型的数字电路。传统的数字电路芯片都具有固定的电路和功能，而FPGA可以直接下载用户现场设计的数字电路。FPGA技术颠覆了数字电路传统的设计-流片-封装的工艺过程，直接在成品PFGA芯片上开发新的数字电路，极大地扩大了专用数字电路的用户范围和应用领域。自从20世纪80年代出现以来，FPGA技术迅速发展，FPGA芯片的晶体管数量从最初的数万个迅速发展到现在的数十亿个晶体管[2]，FPGA 的应用范围也从简单的逻辑控制电路发展成为重要的高性能计算平台。 FPGA芯片中的每个逻辑门在每个时钟周期都同时进行着某种逻辑运算，因此FPGA本质上是一个超大规模的并行计算设备，非常适合用于开发并行计算应用。目前，FPGA已被成功地应用到分子动力学、基因组测序、神经网路、人工大脑、图像处理、机器博弈等领域，取得了数十到数千倍的速度提高和优异的性价比[3-18]。
Monte Carlo Methods in Parallel Computing Chuanyi Ding ding@https://www.doczj.com/doc/5c6497854.html, Eric Haskin haskin@https://www.doczj.com/doc/5c6497854.html, Copyright by UNM/ARC November 1995 Outline What Is Monte Carlo? Example 1 - Monte Carlo Integration To Estimate Pi Example 2 - Monte Carlo solutions of Poisson's Equation Example 3 - Monte Carlo Estimates of Thermodynamic Properties General Remarks on Parallel Monte Carlo What is Monte Carlo? ? A powerful method that can be applied to otherwise intractable problems ? A game of chance devised so that the outcome from a large number of plays is the value of the quantity sought ?On computers random number generators let us play the game ?The game of chance can be a direct analog of the process being studied or artificial ?Different games can often be devised to solve the same problem ?The art of Monte Carlo is in devising a suitably efficient game.
第四章 并行算法的设计基础 习题例题： 1. 试证明Brent 定理：令W (n)是某并行算法A 在运行时间T(n)内所执行的运算数量，则 A 使用p 台处理器可在t(n)＝O(W(n)／p+T(n))时间内执行完毕。 2. 假定P i （1≤i ≤n ）开始时存有数据d i , 所谓累加求和指用 1 i j j d =∑来代替P i 中的原始值 d i 。 算法 PRAM-EREW 上累加求和算法 输入： P i 中保存有d i , l ≤ i ≤ n 输出： P i 中的内容为 i j j l d =∑ begin for j = 0 to logn – 1 do for i = 2j + 1 to n par-do (i) P i = d i-(2^i) (ii) d i = d i + d i-(2^j) endfor endfor end (1)试用n=8为例，按照上述算法逐步计算出累加和。 (2)分析算法时间复杂度。 3. 在APRAM 模型上设计算法时，应尽量使各处理器内的局部计算时间和读写时间大致 与同步时间B 相当。当在APRAM 上计算M 个数的和时，可以借用B 叉树求和的办法。 假定有j 个处理器计算n 个数的和，此时每个处理器上分配n/p 个数，各处理器先求出自身的局和；然后从共享存储器中读取它的B 个孩子的局和，累加后置入指定的共享存储单元SM 中；最后根处理器所计算的和即为全和。算法如下： 算法 APRAM 上求和算法 输入： n 个待求和的数 输出： 总和在共享存储单元SM 中 Begin (1) 各处理器求n/p 个数的局和,并将其写入SM 中 (2) Barrier (3) for k = [ log B ( p(B – 1) + 1) ] – 2 downto 0 do 3.1 for all P i , 0 ≤ i ≤ p – 1,do if P i 在第k 级 then P i 计算其B 各孩子的局和并与其自身局和相加,然后将结果写入SM 中 endif
《计算机系统结构》大作业 对并行算法的介绍和展望 专业计算机科学与技术 班级 111 学号 111425020133 姓名完颜杨威 日期 2014年4月17日 河南科技大学国际教育学院
对并行算法的介绍和展望 我们知道，算法是求解问题的方法和步骤。而并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法的研究涉及到理论、设计、实现、应用等多个方面，要保持并行算法研究的持续性和完整性，需要建立一套完整的“理论－设计－实现－应用”的学科体系，也就是所谓的并行算法研究的生态环境。其中，并行算法理论是并行算法研究的理论基础，包含并行计算模型和并行计算复杂性等；并行算法的设计与分析是并行算法研究的核心内容；并行算法的实现是并行算法研究的应用基础，包含并行算法实现的硬件平台和软件支撑技术等；并行应用是并行算法研究的发展动力，除了包含传统的科学工程计算应用外，还有新兴的与社会相关的社会服务型计算应用等。 并行算法主要分为数值计算问题的并行算法和非数值计算问题的并行算法。而并行算法的研究主要分为并行计算理论、并行算法的设计与分析、和并行算法的实现三个层次。现在，并行算法之所以受到极大的重视，是为了提高计算速度、提高计算精度，以及满足实时计算需要等。然而，相对于串行计算，并行计算又可以划分成时间并行和空间并行。时间并行即流水线技术，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。任何一个并行算法必须在一个科学的计算模型中进行设计。我们知道，任何算法必须有计算模型。任何并行计算模型必须要有为数不多、有明确定义的、可以定量计算的或者可以实际测量的参数，这些参数可以构成相应函数。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。 经过多年的发展，我国在并行算法的研究上也取得了显著进展，并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用、生物工程等领域，理论研究与应用普及均取得了很大发展。随着高性价比可扩展集群并行系统的逐步成熟和应用，大规模电力系统潮流并行计算和分布式仿真成为可能。目前，并行算法在地震数据处理中应用已较为成熟，近年来向更实用的基于PC机群的并行技术发展.然而，在非地震方法中，并行算法应用较少见文献报道，研究尚处于初级研究阶段。在大地电磁的二维和三维正、反演问题上，并行计算技术逐渐得到越来越多关注和重视.随着资源和能源需求的增长，地球物理勘探向深度和广度快速发展，大幅增长的数据量使得高性能并行计算机和高效的并行算法在勘探地球物理学中的发展和应用将占据愈来愈重要的地位。计算机技术在生物医学领域已经广泛应用，实践证明，并行算法在生物医学工程的各个领域中具有广泛的应用价值，能有效提高作业效率。随着电子科学技术的发展，电磁问题变得越来越复杂，为了在有限的计算机资源条件下求解大规模复杂电磁问题，许电磁学家已
第5章 并行算法的一般设计策略 习题例题： 1、 令n是待排序的元素数，p＝2d是d维超立方中处理器的数目。假定开始随机选定主元x，并将其播送给所有其他处理器，每个处理器按索接收到的x，对其n/p个元素按照≤x 和＞x进行划分，然后按维进行交换。这样在超立方上实现的快排序算法如下： 算法5.6 超立方上快排序算法 输入：n个元素，B = n/p, d = log p 输出： 按超立方编号进行全局排序 Begin (1)id = processor’s label (2)for i=1 to d do (2.1) x = pivot / * 选主元 * / (2.2) 划分B为B1和B2满足B1 ≤B＜B2 (2.3) if第i位是零 then (i) 沿第i维发送B2给其邻者 (ii) C = 沿第i维接收的子序列 (iii) B= B1∪C else (i) 沿第i维发送B1给其邻者 (ii) C = 沿第i维接收的子序列 (iii) B= B2∪C endif endfor (3)使用串行快排序算法局部排序B = n/p个数 End ① 试解释上述算法的原理。 ② 试举一例说明上述算法的逐步执行过程。 2、 ① 令T = babaababaa。P =abab，试用算法5.4计算两者的匹配情况。 ② 试分析KMP算法为何不能简单并行化。 3、 给定序列（33，21，13，54，82，33，40，72）和8个处理器，试按照算法5.2构造一棵为在PRAM-CRCW模型上执行快排序所用的二叉树。 4、 计算duel(p, q)函数的算法如下： 算法5.7 计算串匹配的duel(p, q) 的算法 输入： WIT〔1: n-m+1〕，1≤p＜q≤n-m+1，(p - q) ＜ m/2 输出： 返回竞争幸存者的位置或者null（表示p和q之一不存在） Begin if p=null then duel= q else
《并行算法》课程总结与复习 Ch1 并行算法基础 1.1 并行计算机体系结构 并行计算机的分类 ?SISD,SIMD,MISD,MIMD； ?SIMD,PVP,SMP,MPP,COW,DSM 并行计算机的互连方式 ?静态：LA(LC),MC,TC,MT,HC,BC,SE ?动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) 1.2 并行计算模型 PRAM模型：SIMD-SM， 又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW SIMD-IN模型：SIMD-DM 异步APRAM模型：MIMD-SM BSP模型：MIMD-DM，块内异步并行，块间显式同步 LogP模型：MIMD-DM，点到点通讯 1.3 并行算法的一般概念 并行算法的定义 并行算法的表示 并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 并行算法的WT表示：Brent定理、WT最优 加速比性能定律 并行算法的同步和通讯 Ch2 并行算法的基本设计技术 基本设计技术 平衡树方法：求最大值、计算前缀和 倍增技术：表序问题、求森林的根 分治策略：FFT分治算法 划分原理： 均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择) 流水线技术：五点的DFT计算 Ch3 比较器网络上的排序和选择算法 3.1 Batcher归并和排序 0-1原理的证明 奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数)
双调归并网络：计算流程和复杂性(比较器个数和延迟级数) Batcher排序网络：原理、种类和复杂性 3.2 (m, n)-选择网络 分组选择网络 平衡分组选择网络及其改进 Ch4 排序和选择的同步算法 4.1 一维线性阵列上的并行排序算法 4.2 二维Mesh上的并行排序算法 ShearSort排序算法 Thompson&Kung双调排序算法及其计算示例 4.3 Stone双调排序算法 4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 Ch5 排序和选择的异步和分布式算法 5.1 MIMD-CREW模型上的异步枚举排序算法 5.2 MIMD-TC模型上的异步快排序算法 5.3分布式k-选择算法 Ch6 并行搜索 6.1 单处理器上的搜索 6.2 SIMD共享存储模型上有序表的搜索：算法 6.3 SIMD共享存储模型上随机序列的搜索：算法 6.4 树连接的SIMD模型上随机序列的搜索：算法 6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 Ch8 数据传输与选路 8.1 引言 信包传输性能参数 维序选路(X-Y选路、E-立方选路) 选路模式及其传输时间公式 8.2 单一信包一到一传输 SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 8.3 一到多播送 SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法8.4 多到多播送 SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法8.5 贪心算法(书8.2) 二维阵列上的贪心算法 蝶形网上的贪心算法 8.6 随机和确定的选路算法(书8.3) Ch12矩阵运算
Hadoop部署 所需要的软件 使用VMwareWorkstationPro搭建虚拟机，安装操作系统 Ubuntu14.04。 JDK1.8 Hadoop2.6.0 1.在Ubuntu中安装JDK 将JDK解压缩到 /home/kluas/java 在~/.bash_profile中配置环境变量，并通过source~/.bash_profile生效。 #java export JAVA_HOME=/home/kluas/java/jdk export JRE_HOME=/home/kluas/java/jdk/jre export PATH=$JAVA_HOME/bin;$JRE_HOME/bin:$PATH export CLASSPATH=$JAVA_HOME/lib:$JRE_HOME/lib:$CLASSPATH 检验JDK是否安装成功 java –version 2.配置ssh信任关系，实现无密码登录 生成机器A的公私密钥对：ssh-keygen -t rsa，之后一路回车。在~/.ssh 目录下生成公钥id_rsa.pub，私钥id_ras。 拷贝机器A的id_rsa.pub到机器B的认证文件中： cat id_rsa.pub >> ~/.ssh/authorized_keys 这时候机器A到机器B的信任关系就建立好了，此时在机器A可以不需要密码直接ssh登录机器B了 3.安装Hadoop2.6.0 解压hadoop软件包，编辑/etc/profile文件，并追加 export HADOOP_HOME=/usr/kluas/Hadoop export PATH=HADOOP_HOME/bin:$PATH 运行 source /etc/profile命令 修改配置文件hadoop目录etc/Hadoop/Hadoop-env.sh追加： export JAVA_HOME=/home/kluas/java/jdk 修改配置文件hadoop目录下etc/Hadoop/core-site.xml追加：
Schlumberger Private ECLIPSE 并行运算实现方法 1. 在MODEL_NAME.DATA 文件中的RUNSPEC 部分添加下列关键字： PARALLEL 4 / 2. 在并行机上自己的数据文件夹中创建一个新的文件，如名为：hosts. 若想用4个CPU 计算模型，则此模型内容可作如下设置，从而制定运算所用的节点及CPU ： js031 js031 js032 js032 等。 其中js031, js032为并行机中各计算节点的名字。 3. 在此文件夹内执行并行运算，所用命令如下： @mpieclipse –hostfile hosts MODEL_NAME (黑油模型) 或 @mpie300 –hostfile hosts MODEL_NAME (组分模型) 4. 然后会出现如下状态信息，提示选择并行链接方式： [ecl@gri01 e100]$ @mpieclipse -hostfile hosts PARALLEL Specify Parallel InterConnect required ? 1 - Ethernet / Gigabit 2 - Myrinet 3 - Scali Select 1-3 [default 1 - Ethernet / Gigabit] : 1 5. 此时，选择1，出现如下信息： Running version 2006.1 Running Parallel Eclipse 100 on Machine type linux_x86_64 Local config file ECL.CFG exists, OK to use ('n' deletes local file) (Y/n)?: y 5. 选择Y ，出现如下信息，模拟运算即可正常运行： Using local config file ECL.CFG Running MPICH software from /apps/ecl/tools/linux_x86_64/mpich_x86_64 Number of processors required is = 4 Running Parallel Eclipse 100 on Machine type linux_x86_64 version 2006.1 …… 1 READING RUNSPEC 2 READING TITLE
基于OpenMP的并行求和算法的研究与分析【摘要】目前几乎所有主流cpu厂商都致力于大力发展多核处理器，增加芯片支持的并行能力，从而提升计算机运算速度。本文主要探讨近来流行的多核计算技术，介绍一种重要的工业标准openmp，以及通过一个基于openmp的并行求和的简单例子来分析和说明并行计算效率与传统串行计算效率比较的优势。 【关键词】多核处理；并行求和算法；多线程；openmp 0.引言 多核技术始终是近年来全球计算机技术发展的重要内容。自从英特尔在2006年底发布了全球第一基于openmp的并行遗传算法探讨397款主流服务器四核处理器后，英特尔一直致力于推动多核应用生态系统的成熟与发展。实际上，从2002年推出超线程技术开始，英特尔就开始了向多核技术转型的步伐。最终，英特尔公司将四个计算“大脑”装入一枚处理器中，随着至强5300的诞生，计算机行业宣告正式进入了多核时代。 多核计算将成为一种广泛普及的计算模式，影响企业和消费者用户的使用模式。如目前的服务器应用，要求高的吞吐率和在多处理器上的多线程应用；internet的应用、p2p和普适计算的应用都促使了计算机性能的不断提升。大型企业的erp、crm等复杂应用，科学计算、政府的大型数据库管理系统、数字医疗领域、电信、金融等都需要高性能计算，多核技术可以满足这些应用的需求。 本文主要探讨近来流行的多核计算技术，介绍一种重要的工业
标准openmp，以及通过一个基于openmp的并行求和的简单例子来分析和说明并行计算效率与传统串行计算效率比较的优势。 1.openmp openmp是一种适用于多种硬件平台的共享存储编程的工业应用标准，提供了一个可用的编程模型，具有简单、可移植性和可扩展性，灵活支持多线程和负载平衡的潜在能力，目前支持fortran语言，c和c++。openmp规范中定义的制导指令、运行库和环境变量，能够在保证程序可移植性的前提下，按照标准将已有的串行程序逐步并行化。 openmp程序开始于一个单独的主线程。主线程会一直串行地执行，直到遇见第一个并行域才开始并行执行。并行域表示该部分程序计算量大，需要多个处理器共同来处理以提高效率和运行速度；并行区间以外的部分表示该部分的程序不适宜或者不能并行执行，只能由一个处理器来执行。主线程创建一队并行线程，然后，并行域中的代码在不同的线程队中并行执行，当主线程在并行域中执行完后，它们或被同步或被中断，最后只有主线程在执行。实际上，所有的openmp的并行化，都是通过使用嵌入到c/c++或foaran源代码中的编译制导语句来达到的。在具体实现时，在并行域开始处添加openmp制导指令#pragma，另外，openmp是独立于平台的，如果编译器不支持openmp，将会自动忽略预处理指令#pragma，程序依然可以按照串行程序代码顺利编译执行。 2.传统求和算法
第十二章 并行程序设计基础 习题例题： 1、假定有n 个进程P(0)，P(1)，…，P(n -1)，数组元素][i a 开始时被分配给进程P(i )。试写出求归约和]1[]1[]0[-+++n a a a 的代码段，并以8=n 示例之。 2、假定某公司在银行中有三个账户X 、Y 和Z ，它们可以由公司的任何雇员随意访问。雇员们对银行的存、取和转帐等事务处理的代码段可描述如下： /*从账户X 支取￥100元*/ atomic { if (balance[X] > 100) balance[X] = balance[X]-100； } /*从账户Y 存入￥100元*/ atomic {balance[Y] = balance[Y]-100；} /*从账户X 中转￥100元到帐号Z*/ atomic { if (balance[X] > 100){ balance[X] = balance[X]-100； balance[Z] = balance[Z]+100； } } 其中，atomic {}为子原子操作。试解释为什么雇员们在任何时候（同时）支、取、转帐时，这些事务操作总是安全有效的。 3、考虑如下使用lock 和unlock 的并行代码： parfor (i = 0；i < n ；i++){ noncritical section lock(S)； critical section unlock(S)； }
假定非临界区操作取T ncs时间，临界区操作取T cs时间，加锁取t lock时间，而去锁时间可忽略。则相应的串行程序需n( T ncs + T cs )时间。试问： ①总的并行执行时间是多少？ ②使用n个处理器时加速多大？ ③你能忽略开销吗？ 4、计算两整数数组之内积的串行代码如下： Sum = 0； for(i = 0；i < N；i++) Sum = Sum + A[i]*B[i]； 试用①相并行；②分治并行；③流水线并行；④主-从行并行；⑤工作池并行等五种并行编程风范，写出如上计算内积的并行代码段。 5、图12.15示出了点到点和各种集合通信操作。试根据该图解式点倒点、播送、散步、收集、全交换、移位、归约与前缀和等通信操作的含义。 图12.15点到点和集合通信操作
第五章并行算法的一般设计策略 习题例题: １、令n是待排序的元素数,p＝2ｄ是d维超立方中处理器的数目。假定开始随机选定主元x，并将其播送给所有其他处理器，每个处理器按索接收到的x,对其n／p个元素按照≤ x和>x 进行划分，然后按维进行交换。这样在超立方上实现的快排序算法如下： 算法５.6 超立方上快排序算法 输入：n个元素，Ｂ= n/p, d ＝lｏg ｐ 输出:按超立方编号进行全局排序 Ｂｅｇin (1)iｄ=proｃesｓｏr’s labeｌ (2)fｏrｉ=１to d do (2.１) x = piｖoｔ/ * 选主元 * / （2.２) 划分B为B1和Ｂ2满足B1 ≤B<Ｂ2 （2.3）if第i位是零thｅn (i) 沿第i维发送B２给其邻者 （iｉ）C ＝沿第i维接收的子序列 (ｉii) Ｂ＝B1∪Ｃ eｌse (i）沿第ｉ维发送B1给其邻者 （ii) C=沿第i维接收的子序列 （iii) B= B2∪Ｃ eｎdif enｄｆｏｒ (3)使用串行快排序算法局部排序Ｂ= n/p个数 Eｎd ①试解释上述算法的原理。 ②试举一例说明上述算法的逐步执行过程。 2、①令T＝bａbaaｂabaa。P ＝abａｂ，试用算法5.4计算两者的匹配情况。 ②试分析KMP算法为何不能简单并行化。 3、给定序列（3３,2１,13，５4,8２，33,４0，７2）和8个处理器,试按照算法5.2构造一棵为在ＰRAM-CRCW模型上执行快排序所用的二叉树。 4、计算dｕel（ｐ, q)函数的算法如下: 算法5.7 计算串匹配的ｄuel（p，q）的算法 输入：WIＴ〔１:n－ｍ+1〕，１≤p MapReduce并行计算技术发展综述 摘要:经过几年的发展,并行编程模型MapReduce产生了若干个改进框架,它们都是针对传统MapReduce的不足进行的修正或重写.本文阐述和分析了这些研究成果,包括:以HaLoop为代表的迭代计算框架、以Twitter为代表的实时计算框架、以ApacheHama为代表的图计算框架以及以ApacheY ARN为代表的框架管理平台.这些专用系统在大数据领域发挥着越来越重要的作用. MapReduce[1]是Google公司于2004年提出的能并发处理海量数据的并行编程模型,其特点是简单易学、适用广泛,能够降低并行编程难度,让程序员从繁杂的并行编程工作中解脱出来,轻松地编写简单、高效的并行程序.针对上述问题,MapReduce并行编程模型的最大优势在于能够屏蔽底层实现细节,有效降低并行编程难度,提高编程效率.其主要贡献在于: 使用廉价的商用机器组成集群,费用较低,同时又能具有较高的性能; 松耦合和无共享结构使之具有良好的可扩展性; 用户可根据需要自定义Map、Reduce和Partition等函数; 提供了一个运行时支持库,它支持任务的自动并行执行.提供的接口便于用户高效地进行任务调度、负载均衡、容错和一致性管理等; MapReduce适用范围广泛,不仅适用于搜索领域,也适用于满足MapReduce要求的其它领域计算任务 2 MapReduce总体研究状况 最近几年,在处理TB和PB级数据方面,MapReduce 已经成为使用最为广泛的并行编程模型之一.国内外MapReduce相关的研究成果主要有以下几方面: (1)在编程模型改进方面:MapReduce存在诸多不足.目前,典型研究成果有Barrier-lessMapReduce[6]、MapReduceMerge[7]、Oivos[8]、Kahnprocessnetworks[9]等.但这些模型均仅针对MapReduce某方面的不足,研究片面,并且都没有得到广泛应用,部分模型也不成熟 (2)在模型针对不同平台的实现方面:典型研究成果包括:Hadoop[10]、Phoenix[11,12]、Mars13]、CellMapRe-duce[14]、Misco[15]和Ussop[16]部分平台(例如:GPUs和Cell/B.E.)由于底层硬件比较复杂,造成编程难度较大,增加了用户编程的负担. \(3)在运行时支持库(包括:任务调度、负载均衡和容错)方面:常用的任务调度策略是任务窃取,但该策略有时会加大通信开销.典型的研究成果包括:延迟调度策略[17]、LATE调度策略[18]和基于性能驱动的任务调度策略[19]等.在容错方面的典型研究成果是reduce对象[20].目前,运行时支持库中针对一致性管理和资源分配等方面的研究相对较少. (4)在性能分析与优化方面: 目前, 文献[ 21]主要研究在全虚拟环境下MapReduce 性能分析, 文献[ 22]则提出了名为MRBench 的性能分析评价指标. 性能优化典型成果包括: 几何规划[ 23]、动态优先级管理[ 24]和硬件加速器[ 25]等. 着眼于性能, 结合运行时支持库, 将是MapReduce研究的热点之一. (5)在安全性和节能方面: 安全性方面典型研究成果是Sec ureMR模型[ 2 6]. 文献[ 27]和文献[ 28] 则在节能方面做了相应的研究. 目前国内外在安全性和节能方面的研究成果相对较少, 但是这方面研究的重要性已经得到了越来越多的重视. 如果一个模型没有很高的安全性, 同时也没有很好地考虑功耗问题, 那对其大范围推广将产生致命的影响. (6)在实际应用方面: MapReduce 应用范围广泛,Google 等诸多公司都在使用MapReduce 来加速或者简化各自公司的业务[ 29]. MapReduce 还广泛应用于云计算[ 3 0]和图像处理[ 31]等领域. 随着科技的进步, MapRe -duc e 将会得到越来越广泛的应用 .国内学者MapReduce 相关研究成果主要集中在实际应用方面. 例如, 把MapReduce 应用于模式发现[ 32]和数据挖掘[ 3 3]等领域. 部分研究成果涉及模型针对不同平台的实现、任务调度、容错和性能评估优化. 例如, 文献[ 34]提出了名为FPMR 的基于FPGA 平台的 并行计算编程技术浅析 范增禄１，薛峰２ （１．河北省气象局河北石家庄０５００２１２．国家气象中心北京１０００８１） 【摘要】：随着高性能应用和运算需求的迅猛发展，单台高性能计算机已经不能胜任一些超大规模应用问题的解决。这就需要将多台计算机资源通过高速网络连接起来，构成计算集群，共同解决大型应用问题。并行程序的编程模型、运行环境和调试环境，以及如何选取适合需求的开发与运行环境，等等，都要比串行程序复杂得多，而这些问题无疑都是值得我们认真考虑的。本文将试图就此展开讨论。 【关键词】：并行计算模式集群高性能计算机测试 １．并行计算技术概述 ６０年代初期，由于晶体管技术与存储器技术的发展导致并行计算机的出现，这一时期的典型代表就是ＩＢＭ３６０。创建和使用并行计算机的主要原因是因为并行计算机是解决单处理器速度瓶颈的最好方法之一。并行计算机是由一组处理单元组成的，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。 就单台计算机系统而言，采用ＳＭＰ技术是扩展其性能的比较有效的方法，它可以将系统中的多个操作系统分布在多个处理器上执行以获得并行处理的效果。ＳＭＰ技术可以通过多线程并行来提高性能。通过采用并行多线程技术，服务器可以通过ＳＭＰ技术同时处理多个应用请求，使得这些程序获得了更好的运行效果，而且在台式机的专业应用软件中，并行多线程技术的采用也日益增多。 伴随ＳＭＰ技术的出现，带来另外的问题，那就是当应用增加时，虽然可以通过增加处理器的方法来扩展系统能力，但是，一方面需要有扩展连接处理器的系统总线的高超技术，并不是每个系统厂商都能做到，另一方面由于对共享资源的竞争所造成的系统瓶颈，使得单机系统的性能呈非线性增长。因此，当应用增加超过单机系统的承受能力时，就采用集群系统（ＣＬＵＳ－ＴＥＲ）。在集群系统中，每台服务器处理各自的工作，提供各自的服务。当需要更高的的性能以适应更多的应用时，既可以升级原有的服务器（增加更多的处理器、内存和存储等），又可以在集群系统中增加新的服务器。更进一步，集群系统在平衡和扩展整个计算机应用系统的工作负载的同时，也为用户提供了高性能和高可用性。 １９７７年，ＤＥＣ公司推出了以ＶＡＸ为结点机的松散耦合的集群系统，并成功地将ＶＭＳ操作系统移植到该系统上。２０世纪９０年代后，随着ＲＩＳＣ技术的发展运用和高性能网络产品的出现，集群系统在性能价格比（Ｃｏｓｔ／Ｐｅｒｆｏｒｍａｎｃｅ）、可扩展性（Ｓｃａｌａ－ｂｉｌｉｔｙ）、可用性（Ａｖａｉｌａｂｉｌｉｔｙ）等方面都显示出了很强的竞争力，尤其是它在对现有单机上的软硬件产品的继承和对商用软硬件最新研究成果的快速运用，从两方面表现出传统ＭＰＰ无法比拟的优势。 这里所介绍的高性能计算环境，从程序开发角度主要分为以下两类：一大类是共享内存系统，包括并行向量机（ＰＶＰ，Ｐａｒ－ａｌｌｅｌＶｅｃｔｏｒＰｒｏｃｅｓｓｏｒ）、分布式共享存储多处理机（ＤＳＭ，Ｄｉｓ－ｔｒｉｂｕｔｉｅｄＳｈａｒｅｄＭｅｍｏｒｙ）和对称多处理机（ＳＭＰ，ＳｙｍｍｅｔｒｉｃａｌＭｕｌｔｉＰｒｏｃｅｓｓｉｎｇ）等结构，其特点是多个处理器拥有物理上共享的内存，如ＨＰ的ＳｕｐｅｒＤｏｍｅ，我国曙光１号，ＳＧＩＰｏｗｅｒＣｈａｌ－ｌｅｎｇｅ等；另一大类是分布存储系统（ＤＭＰ），如大规模并行处理机（ＭＰＰ，ＭａｓｓｉｖｅｌｙＰａｒａｌｌｅｌＰｒｏｃｅｓｓｏｒ）和集群系统（Ｃｌｕｓｔｅｒ），其特点是系统由多个物理上分布的结点组成，每个结点拥有自己的内存，结点通过高速以太网或专用高速网络连接。 由于以上两类并行环境差别较大，其采用的并行编程方法也不同的。我们将分别介绍这两类系统上的开发环境与开发工具，同时也略带介绍一下其他类型的并行编程开发模式：ＨＰＦ、并行库、串行并行化与多模式混合使用等。 ２．并行程序的开发模式 ２．１．共享内存模式 共享内存并行模式编程相对较为简单，程序员不用考虑数据在内存中的位置，进程管理及同步操作由系统完成。但是用这种方式编制的程序通常并行效率不高，因为它属于细粒度并行，主要针对循环进行并行处理。另外共享内存并行模式只能运行在共享内存类型的计算机系统上。 在共享内存模型中，一个并行程序由多个共享内存的并行任务组成，数据的交换通过隐含地使用共享数据来完成。此编程模式一般仅需指定可以并行执行的循环，而不需考虑计算与数据如何划分，以及如何进行任务间通信，编译器会自动完成上述功能。 ２．１．１．ＯｐｅｎＭＰ 目前业界流行的共享内存模型开发标准是ＯｐｅｎＭＰ。ＯｐｅｎＭＰ定义了一套编译指导语句，用于指定程序的并行性、数据的共享／私有等信息。其目标是为ＳＭＰ系统提供可移植、可扩展的开发接口。Ｉｎｔｅｌ，ＤＥＣ，ＳｉｌｉｃｏｎＧｒａｐｈｉｃｓ，Ｋｕｃｈ＆Ａｓｓｏｃｉａｔｅｓ和ＩＢＭ早在１５年前就联合定义了ＯｐｅｎＭＰ早期标准。新的ＯｐｅｎＭＰ标准由ＯｐｅｎＭＰＡｒｃｈｉｔｅｃｔｕｒｅＲｅｖｉｅｗＢｏａｒｄ于１９９７年推出，现在已发展到２．０版。 作为一套可移植可扩展的标准ＯｐｅｎＭＰ为程序员提供了一个简单和灵活的接口，可以方便地为共享内存的多处理器平台增加并行机制。大部分高性能计算机厂商和软件厂商，例如。ＯｐｅｎＭＰ在所有的架构上都支持使用Ｃ／Ｃ＋＋和ＦＯＲＴＲＡＮ进行共享内存并行编程，包括基于Ｍｉｃｒｏｓｏｆｔ？ＷｉｎｄｏｗｓＮＴ？和ＵＮＩＸ？操作系统的构架。ＯｐｅｎＭＰ还使用编译器指令和库函数，帮助并行应用程序员使用Ｃ／Ｃ＋＋和ＦＯＲＴＲＡＮ创建多线程应用。 对于包含有多个耗时的循环的应用，ＯｐｅｎＭＰ特别有用，它可以将工作划分为多个线程。任一应用中划分粗糙的循环级别的并行机制的数量往往比较有限，限制了应用程序的可扩展性。一个并行区域可能嵌入在其它并行区域之内，但是它们缺省的执行方式是必须使用一个线程组来串行执行。ＯｐｅｎＭＰ使用ｆｏｒｋ－ｊｏｉｎ并行机制，程序首先顺序执行，然后转换成为并行程序。 ＯｐｅｎＭＰ允许程序员使用划分良好的循环级并行机制来扩展应用，实现多处理。它们可以添加划分粗糙的并行机制，同时仍然能保留以前在扩展方面所做的投资。使用这种增量式的开发战略，程序员可以避免转向消息传递或其它并行编程模型时所具有的风险。 要开发新的应用，程序员必须分析原始问题，将它分解为多个使用共享和本地数据的任务，确定数据之间的依赖性，然后重MapReduce并行计算技术发展综述
并行计算编程技术浅析
相关主题
文本预览