3g 手机网站建设,wordpress短信验证码,外贸网站优化在线推广,wordpress自豪的采用如果这篇博客对您有用的话#xff0c;可以给我点个赞吗#xff0c;这对我很重要#xff0c;谢谢#xff01;❤️ 文章目录2 基础并行计算2.1 并行算法的基础知识2.1.1 并行算法的基本概念2.1.2 并行算法的表达2.1.3 并行算法的复杂性度量2.1.3.1 概述2.1.3.2 串行和并行算法… 如果这篇博客对您有用的话可以给我点个赞吗这对我很重要谢谢❤️ 文章目录2 基础并行计算2.1 并行算法的基础知识2.1.1 并行算法的基本概念2.1.2 并行算法的表达2.1.3 并行算法的复杂性度量2.1.3.1 概述2.1.3.2 串行和并行算法的复杂性度量2.1.3.3 Brent定理2.1.4 并行算法中的同步和通信2.1.4.1 并行算法的同步2.1.4.2 并行算法的通信2.2 并行计算模型的回顾2 基础并行计算
2.1 并行算法的基础知识
2.1.1 并行算法的基本概念
在开始这一小节之前容我们先了解几个概念
术语解释算法解题方法和步骤的精确描述并行算法一些可同时执行的诸进程的集合这些进程互相作用和协调动作从而达到给定问题的求解数值算法基于数值计算原理使用代数运算的一类算法非数值算法基于比较关系使用符号运算的一类算法同步算法一种隐含同步要求的诸进程执行必须相互等待的一类并行算法异步算法一种显式同步要求的诸进程执行不必相互等待的一类并行算法确定算法算法的每一步都明确指定下一步如何进行的一类算法随机算法算法执行时随机从指定范围内选择某些参数以此确定算法运行过程的一类算法分布算法泛指由通信链路连接的多个场点或节点协同完成计算的一类并行算法
其中算法我们提倡用形式描述即用计算机的某种编程语言来描述。对于算法来说算法可以简单地范围串行算法和并行算法。串行算法和并行算法是相对于物理设备来讲的如果一个算法运行在单处理机上那么我们说其为串行算法如果一个算法是允许在并行机不包含并行单处理机或者多处理机上那么该算法为并行算法。
对于一般算法来说还可以分为数值算法和非数值算法。对于数值算法来说我们可以用矩阵等代数处理方法进行计算而对于非数值算法来说我们一般用比较如ab而非35\frac3553这类具体数的计算过程。
还有一种是我们可以分为同步算法和异步算法同步算法可以用于银行转账此时关于转账的转账人进程和被转账人进程必须同步进行而对于进程来说是具有异步性的当我们对于一件事要分成很多步骤来执行时就可以使用异步算法一步一步走下去如同接力棒一般。当然对于大多数情况同步算法相对于异步算法来说会比较慢因为同步算法要求两个进程必须同步进行如果此时一个进程较慢那么较快的进程需等待而异步算法不要求一件事必须做完才能做下一件事它可以错开进行无需等待。
并行算法中实际上蕴含着分布式算法在一些场景中并行算法有时候用的是多计算机那么此时并行算法即为分布式算法而当并行算法用在多处理器单机上时并行算法就不是分布式算法了。关于并行算法和分布式算法的区别在1.1.4我们已经谈过了这里就不过多介绍了。分布式算法有时候也叫网络算法或者叫做分而治之方法因为对于分布式集群一般是通过网络来连接的故名为网络算法。
最后谈到的是确定算法和随机算法对于我们的这门学科来说我们一般谈论的都是确定算法。
2.1.2 并行算法的表达
对于并行算法的表达我们一般可以有两种形式物理描述和形式描述。
在前面我们曾经提到过我们在这门课用的会是形式描述即用编程语言来描述算法但是却不是一定要能运行。类似于学习数据结构和算法时用类C语言来描述算法一般我们在并行算法中也引入了类Algol和类Pascal来描述算法。
还有一种描述是用物理描述即直接用语义来描述比如用文字指明哪里该并行哪里该串行。
在形式描述中用类Algol和类Pascal来描述算法的时候有的是串行语言有的是并行语言如果要在代码中使其并行我们可以假如并行语句。如下所示
par-do语句
for i 1 to n par-do
...
end forfor all语句
for all Pi,where 0ik do...end for对于第一个示例来说其过程实际上是我们给进程编号1到n其中计算内容例如有aibia_ib_iaibi那么进程1做a1b1a_1b_1a1b1,进程2做a2b2a_2b_2a2b2以此类推并且n个进程是并行的在做这样一件事。需要注意的是一般以for开头就要以end for结尾这是一个必须的工作。当然也不强制要求一定要用这种形式你也可以用C中学过的花括号括起也是可以的。
同时在书写的过程中一定要注意缩进虽然这不是一种强制要求但这是一种好习惯方便阅读的层次。
对于第二个示例来说PiP_iPi既可以表示进程也可以表示处理器具体情况具体分析而上面的代码说明了对于编号i0ik的进程都做省略号部分代码所做的事。其中i可以是以0为索引n-1为结束也可以是1开始n结束这看个人喜好。
2.1.3 并行算法的复杂性度量
2.1.3.1 概述
一个并行算法设计好了 一定要度量其复杂性。在数据结构与算法的课中我们曾经谈论一个算法的复杂度是用渐进复杂度量衡量的这里同样地我们也是用复杂度的渐进表示即n趋近于无穷大时。
设f(n)和g(n)是自然数集合上的两个函数其中CC1,C2CC_1,C_2CC1,C2都是正整数。那么有上界f(n)O(g(n)),f(n)Cg(n)f(n) O(g(n)),f(n)Cg(n)f(n)O(g(n)),f(n)Cg(n)也有下界f(n)Ω(g(n)),f(n)Cg(n)f(n) \Omega(g(n)),f(n)Cg(n)f(n)Ω(g(n)),f(n)Cg(n)。
其中紧致界为f(n)Θ(g(n)),C1g(n)f(n)C2g(n)f(n) \Theta(g(n)),C_1g(n)f(n)C_2g(n)f(n)Θ(g(n)),C1g(n)f(n)C2g(n)。其中紧致界也叫精确界。
上面的每次可能听着很懵但是如果我换一个术语你马上就懂了上界叫做最坏复杂度下界叫做最好复杂度。最坏时间复杂度和最好时间复杂度时间相差的区域即为精确界。
2.1.3.2 串行和并行算法的复杂性度量
对于串行算法的复杂性度量一般分析两种即最坏情况下的复杂度和期望复杂度其中期望复杂度也叫平均复杂度。这些在数据结构中都已学过这里不细讲。
而对于并行算法的复杂性度量一般有四种运行时间t(n)、处理器数p(n)、并行算法成本c(n)和总运算量W(n)。其中c(n) t(n)×p(n)W(n)为并行算法求解问题时所完成的总的操作步数。
2.1.3.3 Brent定理
Brent定理衡量了W(n)和T(n)的关系。令W(n)是某并行算法A在运行时间T(n)内所执行的运算量则A使用p台处理器可在t(n) O(W(n)/pT(n))时间内执行完毕。
在上面的叙述中可以看出
W(n)和c(n)密切相关P O(W(n)/T(n))时W(n)和c(n)两者是渐进一致的对于任意的pc(n)W(n)
2.1.4 并行算法中的同步和通信
2.1.4.1 并行算法的同步
同步是在时间上强使各执行进程在某一点必须互相等待这种方式可用软件、硬件和固件的办法来实现。 上面的同步概念可以用一个例子来说明假如一个老师带领一帮学生去公司实习实习这件事就是并行算法需要干的事而干这件事是需要所有学生都到达而各学生相当于进程每个进程具有异步性有的进程执行快有的进程执行慢快的进程则需要等待慢的进程而这个等待的方式可以用软硬件和固件来调控。 如果拿共享存储多处理器上进行求和算法来演示同步语句的话即如下所示
输入A (a0,...,an−1)(a_0,...,a_{n-1})(a0,...,an−1)处理器p
输出S ∑ai\sum a_i∑ai
Begin(1)S 0(2)for all Pi where 0ip-1 do //启动多个处理器(2.1)for j i to n step p do //把任务分配给每个处理器L Laj //求局部和end for(2,3)lock(S) //上锁S SL //互斥提交(2.4)unlock(S) //解锁end forEnd以上这个例子我们曾经在1.1.3讲过对于共享存储多处理器做一个求和工作来说它相当于有多少个进程就把这个求和分成多少段进程分配的每段求和相当于在求一个局部和所有进程求完和后就需要求总和。由于每个进程计算的速度可能不一所以就需要进程同步机制在共享存储多处理器上这种机制只用临界区来体现的。
临界区这个概念我们曾经在操作系统提到过临界区是保存临界资源的而临界资源指的是一个时间段只允许一个进程使用的资源。各进程需要互斥地访问临界资源。对于共享存储多处理器来说每个局部和求解完成后各个进程需要互斥地往临界区中提交局部和当所有局部和提交完成后才进行求总和。
2.1.4.2 并行算法的通信
对于共享存储多处理器来说其通常采用global read(x,y)和global write(x,y)来传递消息。
在操作系统我们曾经学到过共享存储使用共享存储的方式进行进程通信的话操作系统会在内存中开辟一个共享空间让两个进程进行通信。假如两个进程想要互相通信则一个进程将消息写于共享存储单元中然后另外一个进程去该单元读该消息。
而对于分布存储多计算机来说其采用的为send(x,i)和receive(y,i)来传递消息。
同样地在操作系统中我们也曾经学到过消息传递这也是为什么分布存储多计算机被称为消息传递多计算机的原因。其使用消息传递所谓消息传递就是进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的“发送消息/接受消息”两个原语进行数据交换。
下面我们给出通信语句示例
算法环连接的分布存储多计算机上矩阵向量乘算法
输入处理器数pA划分为B A[1…n,(i-1)r1…ir],r n/px划分为w w[(i-1)r1;ir]
输出P1P_1P1保存乘积AX
begin(1)Compute z Bw(2)if i 1 then yi 0 else receive(y,left) endif(3)y yz(4)send(y.right)(5)if i 1 then receive(y,left)
End2.2 并行计算模型的回顾
在前面我们已经提到了并行计算模型并行计算模型是算法设计者与体系结构家之间的一个桥梁是并行算法设计和分析的基础它屏蔽掉并行机的差异从并行机中抽取若干个能反映计算特性的可计算或可测量的参数并按照模型所定义的计算行为为构造成本函数以此进行算法的复杂度分析。
我们对模型的基本要求是计算模型应提供反映并行机计算特性的一组时间参数它包括cpu性能参数多层存储访问时间和网络通信特性参数等。在计算模型中我们应该定义计算过程行为如同步式和异步式。也应该给出计算并行算法时间复杂度的成本函数。
我们设计的算法除非是那些学纯理论的人可以不用应用否则其都是要应用在并行机上。应用在并行机上有两种情况特别和普遍。特别指的是设计的算法只能用于某一种并行机上而普遍则是大多数通用。从学术观点来看我们更希望设计的算法可以实现后者的情况。
按照模型所定义计算行为我们在此基础上进行并行算法的设计。根据模型参数和计算行为构造成本函数。并且我们结合在具体并行机上所测量的模型参数进行并行算法运行时间理论分析。
