没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记128(2005)3-19www.elsevier.com/locate/entcs一种面向并发和数据并行元计算的Armelle Merlin1LIFO,Universit′edGA'ETANHains2LIFO,Universit′ed摘要CCS(Calculus of Communicating System)进程代数是一个著名的同步和通信的形式化模型,用于分析协议或分布式程序中的安全性和活性,以及最近的工作中它们的安全属性。BSP(Bulk-synchronousparallelism)是一种数据并行计算的算法和编程模型。这对可扩展并行算法的设计、分析和编程有一定的参考价值。许多当前的发展需要集成的分布式和并行编程:网格系统在互联网上共享资源,安全可靠的全球访问并行计算机系统,地理分布的机密数据随机访问系统等,这样的软件服务必须提供安全性,活性和安全性的保证,以及可扩展的和可靠的性能。因此,需要正式的模型来结合并行性能和并发行为。考虑到这一目标,我们在这里提出了一个集成的BSP与CCS语义,概括其成本(性能)模型和素描其应用程序调度问题的元计算。保留字:并发,代价模型,数据并行,CCS,BSP1电子邮件:Armelle. lifo.univ-orleans.fr2电子邮件地址:ghains@lifo.univ-orleans.fr1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.04.0014A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)31介绍我们将首先在这里介绍BSP和CCS的基本原理。在第一节中,我们将提出一个CCS扩展来表示类BSP过程。第二部分将介绍进程代数的形式化常用工具。然后,我们描述了一个正式的成本模型,这个扩展的代数在标准的图论的方式:将“定制”半环元素的CCS过程中的过渡系统中的路径集。最后,我们概述了它在元计算调度问题中的应用,以及一些未来的发展。完整的技术发展情况见技术报告[8]。1.1BSP模型BSP执行模型[13]将pidenti- cal处理器上的并行计算表示为计算超步(pasyn-tom-tom计算)和通信超步(具有全局同步的处理器之间的下图表示BSP超步。BSP成本模型通过基于p、处理器的顺序速度、网络带宽g和延迟L的简单公式,将执行时间估计为顺序操作时间的倍数。计算超步之后的同步超步的执行时间由下式估计:时间=最大wi+最大hig+L0≤i p0≤i pP1 P2P3. . .Pp其中hi=max(hi+,hi−)且hi+(分别)hi-)是发送的消息的总大小(分别为接收)。这里wi是处理器i在计算超步期间的顺序速度因此,BSP是一个简化的和可移植的并行架构模型,用于算法设计,可扩展性分析和编程。一种类似ML的BSP编程语言BS-λ[7]是λ演算的BSP扩展该模型适用于纯数据并行,但缺乏描述元计算系统的表达能力,这导致了进一步描述的工作。全球同步. . .全球同步时间...A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)35αα1.2关于CCS[10][11][12][13][14][15][16][17][19]1.2.1定义所有的过程表达式都在集合E中。A是名称或输入标签的无限集合,并且A是名称或输出标签的集合。 A和A′是相连的 , 是 通过()的投射。L=A ,A是标签的集合。 A和A都是逆命题。标签也称为动作或事件。下面是一个进程(或代理表达式)的语法,其中α∈ L,X是任何过程变量:• P::= 0 |α.P|P + P|P\α|设X = P在P中|recX:P|(P|P)|X• 作用::= α|τ其中α∈ L. 注:τ无逆。1.2.2规则局部项的转换语义如下图所示。规则ACT涉及前缀运算符,SUM涉及求和,RES 涉及限制,LET 涉及重新标记,REC 涉及递归,ASYNCL ,ASYNCR和ASYNCR是并行组合法αα.P→PαJαJSUMPi→PiRECP[X←recX:P]→PαJαJPi+P j→PirecX:P→PαJαJ总和Pj→PjP→PASYNCL1αJαJPi+P j→PjP→α PJP|Q→P |QP→αPJQ→α<$QJRESα(α∈/{β,β<$})PARτJJPβ→PJβP|Q→P |QαLETQ[X←P] →RαASYNCRQ→QJ设X=P在Q → RP中|Q → P |Q注释1.1符号LET IN 用于共享子项中的项(没有- out递归),符号P[X<$Q]是数学替换([X<$Q]是元操作,不是进程代数语法的一部分1.2.3强互模拟Milner提出了E上的一个二元关系,S强互模拟,记为E。他揭露了一种消除平行构图的方法|的限制和重新标记,以获得由于扩展定律的双相似S项。0J6A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)3如果一个序列项不包含递归,那么它是有限序列项。Milner提出了一个公理系统A1,它是关于有限个串行代理的,具有+交换、结合、幂等和0作为+的单位。命题1.2设P和Q是有限项。P = Q2一种数据并行进程代数在本节中,我们将描述BSPA(BSP进程代数)的语法和语义。与BSλ中一样,进程代数被划分为局部(分别为全局级)表示来自并行系统的各个处理器(分别是并行系统的组合或CCS语义中隐含的隔离的2.1地方进程地方一级是CCS,略有变化。这个级别上的动作可以由并行系统的任何处理器在本地完成。2.1.1定义我们引入了一个本地标签put,它表示特定的BSP交换。该标签与对应于要交换的数据的一组替换σ相关联。λ是σ的一个子集,也是一个置换集。 这种构造对应于根据要发送的这些数据的目的地来封装数据。• 作用::= α|放[σ] |τ其中α ∈ L. 注:τ和put没有逆。• σ::= [i←λ]表示由put引起的交换的替换的句法范畴。i是发送λ替换的处理器的编号。此类别可以为空。• λ::=[X←P]表 示要发送的替换的语法范畴Subst此类别也可以为空。2.1.2地方细则本地术语的转换语义与CCS的转换语义相同。因为put[σ]操作只出现在全局级别的规则上。2.2全球进程接下来,我们介绍全球层面。其定义、语法和语义与局部级别非常相似,除了同步屏障。A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)3700在本节中,我们将始终引用一个固定大小的向量,它表示 一个固定大小p的并行机(BSλ-like [7])。2.2.1定义Ev是全局(进程)表达式的集合。Ev,FIN是不带rec的全局表达式的集合。我们定义• 这些集合是:输入标签AV=A{α@ip|i∈0,.., p−1, α∈A},输出labelsA<$V=A<$$>{<$α <$@i<$p|i∈0,.., p−1,α<$∈A<$}且LV=AV<$A<$V。• 处理器位置编号i::= 0 |1|......这是什么?| p − 1• 项V::= 0 v|α.V|V + V|V\α|设X = V在V|recX:V|(五)|你好,|⟨P,.., P |X ,其中α ∈ LV。对于每个p ≥ 1,存在全局过程向量Pp,代表一个参与集体数据并行计算的一组本地进程,如MPI通信器。当不相关时,未指定尺寸。 假设p个进程被分配给p个不同的处理器。• 动作V::= α|T σ,π|⟨τ @ ij⟩p|τ Net其中α∈ LV· α@ i如果hi/=j,则α@ip可以与α<$α<$或α<$@jp同步。· Tσ,π是Tijσiπj的缩写。 它类似于全局同步的τ化。σi是处理器i发送的替换集合,πj是处理器j接收的替换集合。· πτ@ijπp是两个不同点(i)之间的τ同步在平行向量中。(j)过程·τNet是处理器之间通过外部网络的同步,即在两个平行向量之间。2.2.2全球规则全局进程的转换语义由下表中的规则集定义。法α。V→αVαJαJSUMVi→ViLETW[X←V]→WαJαJVi+V j→Vi设X=V在W→WαJαJ总和Vj→VjRECV[X←recX:V]→V1αJαJVi+Vj→VjrecX:V→VαRESV→V(α/=β/=β<$)ASYNCLVV→αVJαJαJVβ→Vβ第0页|V1 →V0|V10J8A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)3αJαJ阿杰ASYNCRVV1→V1PARV V0→V0V1→V1αJτ网络JJ第0页|V 1 →V 0|V1第0页|V1 →V0 |V1αJASYNCPi→Piα∈ L<${τ}(α@i)CUP... .,P,.......、PP... .,PJ,..., P0ip−1p→α0iJĀJp−1pPi→PiPj→Pji=/J多氯酮(τ@ijpCUP,. ..,P,. ..,P...、.、PP... .,PJ,...,PJ.. 、.、P0ij放[σi]JPp−1p→0ijp−1p等时i−→ Pi∈{0,.,p−1}Tσ,ππi=σ(p−1)i你... . σ0iP 0,.,Pp−1 −→π 0(PJ),. ..,πp−1(PJ)p0p−1p规则ACT、SUM0、SUM1、RES、LET、REC、ASYNCLV、ASYNCRV和PARV都是普通的ASYNC是一个发射(或接收),在并行向量内部的iDUOCHRONE是两个进程之间的交换,平行向量,注意α放置。规则ISOCHRONE是屏障。如定义2.2.1所示,有一个构造函数。. 为每台并行机提供数据处理器i实现事件put[σi],σi是从Pi发送的替换集合,πj是Pj接收的替换集合。为了应对可能并发替换到同一个变量,我们定义优先级时间成本是BSP理论的一个关键组成部分,将在4.2节中根据这种通信量的度量来定义。2.3示例多氯酮Parv等时<......、Pi,.Pj,。。>><......、Pi,. >>|...<...、Pj,。。>>Fig. 1. 同步的主要情况< P0,...,Pp−1>• 多氯酮这是一个四处理器并行系统的例子。处理器0和2通过规则DUOCHRONE同步。a、b、a、c⟨a@0⟩2→ ⟨ a、b、0、c和4a、b、a、c2014年2月4日→ ⟨ a、b、0、c和4• ASYNC+PARVa、b、a、c2019年02月04日→0,b, 0,c4两个不同的并行系统,用带根的项表示,可以像CCS中一样同步。如果这种类型的两个同步是可能的,那么它们不可能是同时的。这表示我们保留A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)393 2 32作为理论的一部分,并且意味着外部网络串行化通信。a、b、c|b,<$a 100,b,c|⟨b,¯0⟩3 2↓τNet↓τNeta,0,c|0,a<$|10,000日元• 等时线,p= 4图2显示了四个处理器之间的通信超步(以及同步屏障)。2 31← [X←α]230← [Y←γ,X←δ]2 30← [X←α]6 7第四章五、(X+Y),放45.X,放6 76 1 ← [X ← γ] 7.X,放入[]。(X+Y)1002← [X←β]3←[X←α]↓Tσ,πδ+γ,α,β,α+β图二. 示例:等时酮4 53← [Y←β]3强互模拟我们将Milner的互模拟定义扩展这将允许我们验证转换规则,以将我们的过程表达式减少到特定形式(转换系统的显式描述),以定义它们的成本。3.1整体项的强互模拟性质在本节中,我们将假设项是封闭的,以便将它们简化为序列形式。我们的并行系统构造器减少到CCS的并行compo- sition在没有障碍同步(模处理器索引)。这就引出了引理3.1Lemma3. 1P,QpP|Q若put∈/P且put∈/Q.引理3.2 P0,.,P p−1P σ(0),.,P σ(p−1)<$p其中σ是任何置换。命题3.3整体项的Sum +是结合的,交换的,幂等的,单位为V.并联组成|对于全局项,它是结合的、可交换的,并且以0 V为单位。3210A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)3命题3.4以下规则用于消除限制:• V\α<$V如果α∈/L(V) ·V\α<$V\α·V\α\βV\β\α·(W|V)\αW\α|V\α如果α∈/L(V)<$L(W).命题3.5数据并行向量的扩展律设V≠P0,.,Pp−1<$p\β,则ΣVα @ i。{不...P,PJ,P... . 中文(简体)→αPJ, αβ,α/=put}pi−1ii+1 pii+τ@ij。我. . . . , PJ, . . . , PJ, . . . α\β:P→αPJ, P→α¯PJ,i=j}pi jpiijjΣ+T。{PJ,.,PJ中文(简体)put[σi]PJ}。σ,π0p−1pi−→i命题3.6全局平行合成的展开律LetV(V0|V1|.... . . 你 好 。 . |Vn)\βn≥1V{α. (五)|.... . . 你 好 。 . |VJ|.... . . 你 好 。 . |V)\β:V→α Vj, αi=β}2010年10月20日+{τ. (五)|.... . . 你 好 。 . |VJ|.... . . 你 好 。 . |VJ|.... . . 你 好 。 . |V)\β:V→αVJ, V→α<$VJ, i/=j}净0i jn iijj3.7一个全局项是有限的,如果它只包含有限求和(SUM)而不包含递归(REC)。 全局项P是串行的,如果它不包含并行复合(CCS|或数据并行处理器。. P中任何递归的定义方程都不包含平行复合、限制或重新标记。通过展开,每一个有限全局项都可以等价于一个有限序列全局项。命题3.8设V和W是序列有限项和整体项。 VW iA1V=W关于进程代数的最后一点说明是,CCS被称为具有语法语义,因为|b=a.b + b. a忽略了a和b同时发生的可能性。BSPA具有相同的语义。在下一节中,我们将介绍一个考虑成本的成本模型4成本模型并行编程研究人员通常将并行性能模型称为成本模型,我们将使用这个术语。在BSP之后,我们将定义一个成本模型,其中执行时间与本地进程的步骤数和全局通信超步所需时间的估计有关。结果是一个符合操作语义的成本模型。由于进程被认为是模互模拟,因此很自然地要求这种等价的代价是稳定的主要A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)311这样做的结果是,成本忽略了任何进程的替代副本的存在至于互模拟定律P+PP,这是一个合理的并行执行时间的概念:同一进程的额外副本不会增加最坏情况下的时间。我们将我们的研究限制在CCS强互模拟关系上,而忽略了所谓的弱互模拟关系。 这在成本模型的背景下被证明如下。 弱互模拟将导致(通过τ.P <$P)基本成本C(τ)= 1(例如,在半环[3](N<${−∞},max,+,−∞,0)C(τ)= 1 = 0),这相当于将相同的成本分配给τ100000.P和τ.P,而第一项表示大量的内部同步。这与使用成本作为执行时间的估计是不一致的。[1]在信息流分析的背景下给出了驳回弱互模拟的其他动机。在下面的小节中,我们回顾了半环具有哪些性质,我们建立了一个特殊的半环S|基于BSPA的并行性质,我们给出了代价规则,并定义了一种最终获得合适代价的方法.4.1半环S的定义|4.1.1半环基础一个幂等半环(S,S,S,S,0,1)必须证明S是结合的,交换的,幂等的,并且有0作为单位。并且,这个n是结合的,被0吸收,以1为单位,并且在n上是分配的。这个理论是通用的:它基于任何可能的幂等半环。 S的元素称为S标量。以下是可能实例的示例:• (N<${−∞},max, +,−∞,0)计算最长路径,也就是最坏情况下的时间复杂度。• (N<${ +∞},min,+,+∞,0),计算最早的死锁时间。• (Bool,Bool,Bool,False,True),它计算转换系统中的可达性• (P(Act),n,concat,n,n)是一种计算跟踪语言.• (N→max(i,j),∞,a@0),计算进程使用的最大处理器数4.1.2半环S的定义|在本节中,设S是任意半环。我们需要测量图中的路径[3] 这是CCS过程的语义:所谓的标记转换12A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)3- 是的⎟⎜⎟系统的节点是进程,边变迁和边标签是事件。P+P<$ P需要x<$x =x的性质,即<$是幂等的过程定律和互模拟应该尊重成本的要求。由于流程成本与执行路径集相关联,因此它必须表示障碍。BSP程序的成本在一个超步完成之前是未知的。成本可以是表示屏障之前每个处理器上的累积时间它可以是包含由两个相邻异步阶段包围的屏障的成本的信息的三元组:标量表示屏障的成本,并且两个向量表示在异步计算之前/之后的异步计算的成本屏障需要一种特殊的半环来表示这一点,我们将分两步定义它:从S到Sp和从S到S p。|.首先,我们定义幺半群Sp=(Sp<$(Sp×S ×Sp),<$,1),其中1=联系我们⎜1 ⎟- 是的其中,k适用于点到点的向量。⎝ ⎠1⎛ ⎞v0定义4.1设v=0⎝.vp−1埃森⎠v=v0我... p-1。定义4.2我们定义了这个幺半群上的运算v,w,vJ和wJ都是载体x和XJ是标量。ⓈVJ(vJ,xJ,wJ)vv vJ(v<$vJ,xJ,wJ)(v,x,w)(v,x,w<$vJ)Σ(v,x<$(w<$vJ)<$xJ,wJ)当两个向量连接时,它们只是点对点连接(缩写为vvJ)。当一个三元组后面跟着一个向量时,该向量被点对点连接到三元组的最后一个或“未来”向量。当一个向量后面跟着一个三元组时,该向量被点对点连接到三元组当一个三元组后面跟着一个三元组时,也就是说由于我们的模型中存在两个较好的解决方案,因此可以实现数据中心传输或矢量并将其转换为标量(使用操作),以连接到三元组的标量命题4.3是结合的,以1为单位。A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)313MULT从这个结合幺半群,我们然后建立半环S|=(IPFIN(Sp),0,1)前一个元素的有限集合,其中0=0,1={1}。集合的并是结合的、交换的和幂等的。为了简单起见,我们将用上面的0和1的唯一元素来标识单例集。接下来的步骤是证明当将k提升到值集(向量或三元组)时,k在k上的分布性,由于k的性质,这是微不足道的4.2将成本与流程相我们的成本按连续形式的有限流程进行评估。我们假设限制和平行组合已经被消除。EFIN是有限过程的集合(没有递归)。我们将定义C:EF IN→S|在工作步骤中:(i) 我们消除\和|从E FIN的条款,通过应用扩展法[9]。我们还将基本成本C(α)分配给事件α。(ii) 剩下的运营商则被允许进入。,+和0的变量。性质C因此用规则4.2.1来验证,其中PDc意味着C(P)被求值为半环元素c。考虑到网格应用中网络流量的可变性,BSP常数g和L在这里可以被认为是随机变量。通过构建,这种成本理论能够表达交织(通过|)和同时(通过.. .#21453;事件的发生4.2.1地方细则在应用了扩展定律之后,我们只需要前缀、求和和重新标记的规则。C(0)=0PD cACTα.PDC(α)βcPDc QDCP+QDc+JQ[X←P]Dc让设X=P在QDc中4.2.2全球规则C is noweextended to afunctionalnC|从所有有限的Serial项到S|[第4.1节。2]。由展开式3.5、3.6得到的有限级数项和整体项V,既不包含λ,也不包含λ。.纳普河|,但只有。,+,0,并让。 随着扩张应用定律,T σ,π,α @ ip的出现 出现 Tσ,πcost表示14A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)3Σ通信和同步屏障的BSP执行时间。α@i当您在本年度未进行协作时,会发生成本(C的某些差异|在定义4.4)。C|(0)=0(i. e.{})ViDc VjDcJ总和Vi +Vj DccJE、D、cACTα。EDC|(α)αc其中α∈ LVU[X←V]Dc让设X = V在UDc定义4.4C|:Ev→S|(i) C|(α@iαp)=→1 [i→<$C(α)]即其中ei<$→C(α)和dj<$→∞是p-向量,吉岛㈡C|(α)=(1,C(α),1)Σ Σ㈢C|(T) =(1,(h+h−)gL,1)(here1是σ,π伊鲁伊河半环Sp),h+=p−1|σ ij|h −=p−1|σ ki|哪里|σ|是ij=0ik =0替换的语法大小σ和指数g表示重复的产品如果σ= X1←P1,. X n←P n那么|σ|= P的语法大小。|.|. 哪里|P|是4.2.3成本考虑互模拟引理4.5(稳定性)全局有限项级数V的稳定性W:VWC|(V)=C|(W).4.3减少标量的成本:观察我们已经建立了一个矢量BSP半环S|以真实地表示流程的合理消耗。 这个半环必须特别地表示非对称性。 即使S是全序的,例如(N <${−∞},max,+,−∞,0),S中的两个计算函数也是非负序的|. 我们从观察者的角度出发,得到了通常的成本概念:一组向量成本的标量和成本的总阶。为此,我们定义了一个观测函数,它将我们的元素转换为S|intoascalar calaroffS. 然后,我们有工具来比较成本。 然而,我们将注意到,这种观察不是合成的,因为它像一个障碍:一般来说,Obs不保持λ。定义4.6We定义Obs:S|→S:Σ• bs(v)=v向量被忽略。• 0bs((v,x,w))=ΣvxΣw减少三元组:两个向量都被处理并添加到中心标量中。A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)315我⎜⎜⎟⎟• 并且该函数是对S的集合(元素)的n个限制|)如下:· Obs({X})=Obs(X)其中X可以是v或(v,x,w)· Obs(A<$B)=Obs(A)<$Obs(B)。4.4示例在本节C节中,|(α)=a,C|(β)=b, .我们使用emi-ring(N{−∞},max,+,−∞,0)其计算转换系统中的最长路径,即最坏情况的扩展时间。• ASYNCC|(<α,β>α)=αC|((αβ@0. ββ@1)+(ββ@1)α@0))=C|(α@0. β@1)βC|(β@1.α@0)=aa=a。Obs(a,b)=Max(a,b).b b b b b• 等时线,p= 4我们在这里发展已经在2.3节的图2中看到的例子。首先,我们需要计算πi及其对PJ的应用。然 后 我们需要计算差h i,其中|α| =的|β|=的|γ| =的|δ|= t和a = b = c = d = w。Maxh+=Maxh−=3t. C|(V)=C|(Tσ,π)C|(十). C|(Tσ,π)=(→1,3tg+L,→1)⎛i⎞i⎛ ⎞⎜w ⎟ ⎜w ⎟⎜ ⎟ ⎜ ⎟⎜w⎟ ⎜ w⎟C|(s)=100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000(V)=(→ 1,3 t g + L,V)O b s(C(V))= 3 t g + L + w。||⎜w⎟ ⎜ w⎟⎝ ⎠ ⎝ ⎠w w5元计算的应用:调度我们现在有一个完整的成本模型。我们可以将其应用于网格计算中常见的调度问题。一个典型的情况是在同一台并行机上调度两个数据并行进程,而不干扰,同时最大限度地提高性能。我们概述了我们的模型如何描述这种情况,从而选择最有效的调度解决方案,同时确保两个数据并行过程的一致重叠的可能性。我们将使用p= 2,但这个例子很容易扩展到更大的p。假设两个数据16A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)3并行应用P和Q,每个可能在一个或两个处理器上执行。问题是在双处理器系统上找到两个进程的最快一致调度。A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)317我我我们使用半环(N <${−∞},max,+,−∞,0)。 对于这些例子,我们引入一个新的符号:Pp将缩写为P:i = 0,.,p− 1 p。设P = P_b。put []. b. put []:i = 0,...,1 p,Q = a. 将[σ]. a. put [σ]:i = 0,...,1 p和C|(a)=ta,C|(b)=tb。 Letσbeasetofsymometric“he a vy“s ub s zones,也就是说,s ub stitutions that had a v e a significationcannot t sizize. 特亨角|(Tσ,π)=gh+L,Obs(C|(P))=2tb+2L且Obs(C|(Q))=2ta+2L+2gh。一个是他控制克莱顿在并行程序中,P将被认为是计算边界进程,Q是一个通信绑定进程。我们列举可能的调度取决于有多少处理器被每个进程使用。(i) P和Q分布在两个处理器上。如果我们天真地使用P I=P0|Q0,P1|Q1p=b。 put []. b. put [] |a. 将[σ]. a. put [σ]:i =0,.., 如果P = 1,则P0可以实现与Q 1的势垒,从而导致不相干(不想要的)通信。因为一个看跌期权可以被其他看跌期权引入函数[,]来调度局部子进程是有用的。不失一般性,我们假设P和Q中的变量不相交。[,]:Proc2→Proc定义如下:• [A,0]=A和[0,B] =B• [a. A,b.B] = a. [A,b.B]+ b. [a.A,B]其中a,b/=放置• [A+AJ,B] = [A,B]+ [AJ,B]且[A,B+BJ] = [A,B]+ [A,BJ]• [put.A,b.B] = b. [put.A,B]和[a.A,put.B] = a. [A,put.B]• [put [σ0].A,put [σ1].B] = put [σ0]. 放[σ1]。[A,B]则我们可以将PI改写为PJ=<$[P0,Q0],[P1,Q1]<$p:PJ= PutX = Put。放[σ]。0英寸设Y=a.b.X+b.a.X,设Z = put []。将[σ].Y放入a.b.Z + b.a.Z:i = 0,..,1英镑⎛ ⎞C|(PJ)=(ta+tb, t+t+4gh+4L,1)。 Obs(C|(PJ))=2t+ 2t +我4gh+4L。a Bta+tb我a b(ii) P在一个处理器上被串行化,Pser=b.b.b.b.b. ττp,Q分布在两个处理器上。P II=P ser|Q0,Q1p =b.b.|a. 将[σ]. a. put [σ],a. 将[σ]. a. put[σ]pObs(C|(PII))=2ta+4tb+4gh+2L(iii) 与PII相同,其中Q在一个处理器上序列化Qser=a.a.cσ.a.a.cσ其中cσ是实现与put[σ]相同的替换(σ)的局部动作。它的成本是ph而不是pgh(在本地,g因子的成本是1)。P分布在两个处理器上。P III= P0,P1|Q serp = b。put []. b. put [],b. put []. b. put [] |a.a.c σ.a.a.c σp18A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)3Obs(C|(PIII))=4ta+2tb+4h+2L(iv) 每个进程都在一个处理器上序列化PIV= Pser , Q serp = b.b..b.b.τ , a.a.cσ.a.a.c σpObs(C|(PIV))=max(4tb,4ta+4h)。从上述成本估计中,可以选择具有最少执行时间的调度。一般来说,它取决于g和L的数值,但符号比较是可能的。例如,我们可以根据max(4tb, 4ta + 4h)的结果,象征性地知道PIV PII或PIV PIII。这两种情况都表明,与序列化两个程序相比,只分发其中一个程序是无用的。这里是第一种情况的解释(很容易适用于第二种情况):C|(PSer)>C|(QSer),C|(QSer)>C|(Qi)和dC|(Q0) =C|( Q1),C|(Pr|Q0,Q1<$p) =max(C|(PSer|Q0),C|(Q1))=C|(PSer|Q0)=C|(PSer)+C|(Q0),henceC|(PII)>C|(PIV)。从这个例子中可以清楚地看出,这个问题的大规模版本的解决方案可以机械地计算。另一个典型的元计算问题是分发一个进程,如P=P0,.,P3在两个双处理器系统上运行,同时防止阻塞和最小化执行时间.由此产生的过程的形式为:|P2、P3并且应该通过两个2进程屏障和两个系统之间的一些点对点同步(规则PARV)来实现4进程屏障一个技术问题是通过点对点同步将消息从一个系统发送到另一个系统。我们在[8]中提出了一个简单的解决方案:引入一个6结论这项研究强调了这样一个事实,即CCS的“交织”语义可以调和与数据并行(因此BSP)的概念,同时采取行动。此外,一个通用的成本模型可以被设计成概括CCS转换系统中的路径的标准概念和通信和同步障碍的同时并行执行的BSP概念Krishnan因此,我们赞成BSP的并行计算的观点。[4] 提出时间模型。跃迁时间以概率形式给出,并保持了扩展律。该模型不考虑动作的构成。我们的模型并提出了适应算法,A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)319一个全局演算我们可以将概率模型浸入我们的模式中,但是我们需要通过两个随机变量的和(在(N<${−∞},max, +,−∞,0)中的乘积)来计算两条路径的组成:第一次跃迁的时间+下一次跃迁的时间。这个模型的使用将取决于这个计算的复杂性,我们还没有研究过。由于我们模型的代数性质,我们在第5节中手动完成的工作可以通过矩阵上的经典算法机械地完成[3]。我们的模型然后,我们将能够将我们的形式主义应用于设计正确,安全和最佳的可扩展元计算过程,特别是通过自动分析工具,如模型检查器。我们正在考虑的其他扩展是移动性([11,2])及其在并行系统背景下对安全属性的应用([1])最后一个问题是后进先出和CEA之间的一个当前项目的对象,这里开发的形式主义将给出一个现实的数据并行分布和性能模型。我们正在研究的理论的另一个应用涉及拒绝服务攻击。在[6]中,Lafrance和Mullins从服务器的角度对事务的内存成本进行了我们的模型通过允许内存成本沿着轨迹增加和减少来改进他们的另一个改进是有一个二进制构造函数来实现.. . - 是的引用[1]S. Anantharaman和G.海恩斯基于同步互模拟的信息流分析方法。在第三次关键系统自动验证研讨会上:(AVOCS[2] G. Fournet和G.贡蒂尔反应CHAM和连接演算。在第23届ACM编程语言原理研讨会(POPL[3] M. Gondran n dM. 我不知道。第三章,语法分析。1985年的EYRolles。LesAlg'ebresde Chemins.[4] 作者:Joost-Pieter Katoen,Pedro R.迪卡里奥进程代数中的一般分布。计算机科学讲义,2090:375[5] 克里希南。分布式CCS。并发理论:统一和扩展:CONCUR-91,LNCS:527,第393-407页。Springer,1991年8月。[6] S. Lafrance和J. Mullins。使用容许干扰检测拒绝服务漏洞。第六届国际正式方法研讨会。英国计算机协会(BCS)的电子计算研讨会(eWiC)。在J.M.莫里斯湾Aziz和F. Oehl,编辑,2003年。[7] F.卢莱格湾Hains,和C.富瓦西函数式BSP程序的演算。Science of Computer Programming,37(120A. Merlin,G.Hains/Electronic Notes in Theoretical Computer Science 128(2005)3[8] A. Merlin和G.海恩斯一个批量同步并行进程代数。 Rapport de RechercheRR-2004-06,LIFO,Universit'ed'Or l'ea n s,2004. http://www.univ-orleans.fr/SCIENCES/LIFO.[9] R.米尔纳通信和并发。普伦蒂斯-霍尔,1989年。[10] R.米尔纳并发进程的操作和代数语义。在J. Van Leeuwen,编辑,理论计算机科学手册。North-Holland,MIT-Press,1990.[11] R. Milner,J. Parrow,and D.沃克移动过程的演算,I和II。 信息与计算,100(1):1[12] X. Rebeuf.Unmod`eledecoutsymboliquepourlesprramemesparall`elespronesad'ependancesstructurees. 2000年时,Doctorat'U niversi t' e,U niversit 'e d ' O r l'eans s。[13] L. 勇敢一 桥接模型 为 平行 计算Communications of the ACM,33(8):103,August 1990.
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功