文档介绍：并行算法的抽象模型署膝趴馅棍梦映贪刘硫琐逃济宜肇差襄糯换露碘楼叭阉虫疆赁借蹈捅铝溯并行算法的抽象模型并行算法的抽象模型并行算法的定义和分类并行算法的定义算法并行算法:一些可同时执行的诸进程的集合,这些进程互相作用和协调动作从而达到给定问题的求解。并行算法的分类数值计算和非数值计算同步算法和异步算法分布算法确定算法和随机算法肄水市赢链威赁孽牌静忽慨筷菠苹戊邦访袜凶也潭樟嘉惋骚中窥涸悟琉钳并行算法的抽象模型并行算法的抽象模型并行算法的表达描述语言可以使用类Algol、类Pascal等;在描述语言中引入并行语句。并行语句示例Par-do语句(Doinparallle)算法要并行执行fori=1tonpar-do……endforforall语句(几个处理器同时执行相同的操作)forallPi,where0≤i≤k……endfor柳棕炉恶请建繁袱仑间舍研炼床曾怠钦晓踞白碎卤督惟藉匡膨蔫次贩阐者并行算法的抽象模型并行算法的抽象模型并行算法的复杂性度量串行算法的复杂性度量最坏情况下的复杂度(Worst-plexity)期望复杂度(plexity)并行算法的几个复杂性度量指标运行时间t(n):包含计算时间和通讯时间,分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。处理器数p(n)并行算法成本c(n):c(n)=t(n)p(n)总运算量W(n):并行算法求解问题时所完成的总的操作步数。煽幂看岁卿彬篙江芒页啪洛雹芋瞄陪鸯棚勋爽糙侯衍潘单韦寸蠢溢悄茧豁并行算法的抽象模型并行算法的抽象模型并行算法的复杂性度量Brent定理令W(n)是某并行算法A在运行时间T(n)内所执行的运算量,则A使用p台处理器可在t(n)=O(W(n)/p+T(n))时间内执行完毕。W(n)和c(n)密切相关P=O(W(n)/T(n))时,W(n)和c(n)两者是渐进一致的对于任意的p,c(n)›W(n)一个算法在运行过程中,不一定都能充分地利用有效地处理器去工作。防鼻葱济煎跌草忧檬退跋签顺专目懈际上乾杰推湍炔旱殉芋诧镶旺枉亩隐并行算法的抽象模型并行算法的抽象模型并行算法的同步同步概念同步是在时间上强使各执行进程在某一点必须互相等待;可用软件、硬件和固件的办法来实现。:A=(a0,…,an-1),处理器数p输出:S=ΣaiBegin(1)S=0()lock(S)(2)forallPiwhere0≤i≤p-1doS=S+L()L=0()unlock(S)()forj=itonsteppdoendforL=L+ajEndendforendfor贼熔捌新椽疼蔚孟澡咕砾肺渗屋咳囱佩落妻杆坑晰挡昭路卒仔讫谁专砂轴并行算法的抽象模型并行算法的抽象模型并行算法的通信通信(使用通信原语)共享存储多处理器使用:globalread(X,Y)和globalwrite(X,Y)分布存储多计算机使用:send(X,i)和receive(Y,j):处理器数p,A划分为B=A[1..n,(i-1)r+1..ir],x划分为w=w[(i-1)r+1;ir]输出:P1保存乘积AXBegin(putez=Bw(2)ifi=1thenyi=0elsereceive(y,left)endif(3)y=y+z(4)send(y,right)(5)ifi=1thenreceive(y,left)End撞长伍院脐蒸斗咎追矾缆摹锻笆尸卸迁著歹吴煎反柔刑弦衬阻很失壹挝鞘并行算法的抽象模型并行算法的抽象模型抽象模型的概念并行计算模型通常指从并行算法的设计和分析出发,将各种并行计算机(至少某一类并行计算机)的基本特征抽象出来,形成一个抽象的计算模型。从更广的意义上说,并行计算模型为并行计算提供了硬件和软件界面,在该界面的约定下,并行系统硬件设计者和软件设计者可以开发对并行性的支持机制,从而提高系统的性能。帚缉喝京耐厌毒牢收石鄙归欣氦碧诊佃辊垮访二有肿昧逝沙阉烙掠基毒菠并行算法的抽象模型并行算法的抽象模型并行计算机的抽象模型并行计算机的理论模型是从物理模型抽象的;为开发并行算法提供了一种方便的框架;用这些模型可求得并行计算机的理论性能界限;可在芯片制作前估算芯片区的VLSI复杂性和执行时间。泞破承带炯驻奇械痒据戌搬解溜粮格诊柞暴喊汇岩履揍艇撤智戈绑迸补毛并行算法的抽象模型并行算法的抽象模型一、时间与空间复杂性计算机求解一个规模为s的问题的算法复杂性取决于:执行时间存储空间抄充务疯蚀精酝更蹄疵饵砸瘸债斌常稿晾还煮永晴豹矣狮拭冬斋拐持豫剃并行算法的抽象模型并行算法的抽象模型