软件并行开发过程推选优秀ppt.ppt

软件并行开发软件并行开发(kif)过程过程第一页，共52页。云南省中青年学术和技术(jsh)带头人培养 项目1998-37云南省自然科学(zrnkxu)项目 98F023M98F005G2001F0006M第二页，共52页。问题问题(wnt)的提出的提出 一、生产率一、生产率低下低下二、质量二、质量(zhling)欠佳欠佳第三页，共52页。背背 景景并行并行(bngxng)(bngxng)工程工程并行并行(bngxng)(bngxng)处理处理多个程序员同时为同一个系统编码多个程序员同时为同一个系统编码现现实实生生活活中中的的各各类类非非自自觉觉的的、偶偶然然的的并并行行(bngxng)(bngxng)行为行为第四页，共52页。#define d41:子开发过程1;/*将术语“子开发过程1”符号化*/IF output(Ai)output(Aj)THENSDDML程序(chngx)既可以是一个字符串，也可以是一个可执行的过程一致性：由于软件过程中有多个角色协同工作，应具有描述角色行为和角色协同工作的成分，对角色的行为进行精确的定义，并便于形式化地进行一致性检查。3）尽早开始工作：在信息不充分的情况下开始工作，因此要有很强的应变能力。/*AbiiAbi，BbjjBbj*/并行执行过程中的同步关系由软件过程自行发送消息进行控制。#define d2:初步需求分析;/*将术语“初步需求分析”符号化*/既可以是一个字符串，也可以是一个可执行的过程FOR j:=1 TO tj DO/*块Bbj中有tj 个活动*/制造业并行工程制造业并行工程市场分析产品设计工艺设计 采 购制 造检 测装 配销 售维 修并行度进行反馈产品生存周期第五页，共52页。1982年年，国国防防部部发发表表了了著著名名的的R-338报报告告，正正式式提提出出了了“并并行行工工程程”的的概概念念：并并行行工工程程是是集集成成地地、并并行行地地设设计计产产品品及及其其相相关关的的各各种种过过程程（包包括括制制造造过过程程和和支支持持过过程程）的的系系统统化化方方法法。这这种种方方法法要要求求产产品品开开发发人人员员从从设设计计一一开开始始就就考考虑虑产产品品整整个个生生存存周周期期中中从从概概念念形形成成到到产产品品报报废废处处理理的的所所有有因因素素，包包括质量、成本、进度、计划和用户的要求。括质量、成本、进度、计划和用户的要求。并并行行工工程程目目前前(mqin)已已成成为为制制造造业业研研究究与与实实践践的的热热点点领领域域。在在国国外外已已成成功功地地应应用用于于航航空空、航航天天、电电子子、汽汽车车等等领领域域，如如福福特特汽汽车车公公司司、波波音音公公司司、洛克希德公司、丰田汽车公司。洛克希德公司、丰田汽车公司。我我国国并并行行工工程程的的研研究究始始于于90年年代代初初，国国家家科科委委在在863计计划划中中设设立立了了一一些些课课题题支支持持并并行行工工程程的的研研究究，已已有有少少数数几几家家企企业业开开始始实实施施并并行行工工程程，并并取取得得了了新新产产品品开开发发样样机机周周期期缩缩短短、产产品品综综合合技技术术经经济济指指标标好好、符符合合市市场场需需求求、经经济效益好等效益。济效益好等效益。并行工程现状(xinzhung)第六页，共52页。1）并并行行性性：各各种种活活动动并并行行交交叉叉进进行行。既既包包括括各各个个部部件件开开发发的的并并行交叉，又包括各个阶段的并行交叉。行交叉，又包括各个阶段的并行交叉。2）流程改善：通过改善与优化工作流程，提高产品质量。）流程改善：通过改善与优化工作流程，提高产品质量。3）尽尽早早开开始始工工作作：在在信信息息不不充充分分的的情情况况下下开开始始工工作作，因因此此要要有有很强的应变能力。很强的应变能力。4）集集成成化化：强强调调(qing dio)全全面面优优化化，追追求求产产品品整整体体的的竞竞争争力力和各小组的密切有机合作。和各小组的密切有机合作。5）强强有有力力的的支支撑撑环环境境：必必须须有有良良好好的的支支撑撑多多小小组组并并行行协协同同工工作作的网络与计算机平台。的网络与计算机平台。6）强强有有力力的的管管理理：强强调调(qing dio)强强有有力力的的管管理理，保保证证各各种种并并行活动协调统一地进行。行活动协调统一地进行。并行工程特点(tdin)第七页，共52页。软件(run jin)过程软件过程(guchng)指软件生存周期中所涉及的一系列相关过程(guchng)。过程(guchng)是活动的集合，活动是任务的集合，任务是把输入转换为输出的操作。软件过程(guchng)是动态的，它动态地产生、推进（执行），动态地消亡。软件过程(guchng)模型是对软件过程(guchng)的静态描述，是软件过程(guchng)向前推进的依据。第八页，共52页。软件(run jin)过程-ISO/IEC 12207 1.主要过程类获取过程供应过程开发(kif)过程运行过程维护过程 3.组织过程类管理过程基础设施(j ch sh sh)过程改进过程培训过程2.支持过程类 文档编制过程 配置管理过程 质量保证过程 验证过程 确认过程 联合评审过程 审核过程 问题解决过程第九页，共52页。过程并行(bngxng)子过程并行(bngxng)阶段并行(bngxng)版本并行(bngxng)活动并行(bngxng)软件生存软件生存(shngcn)周周期中的并行性期中的并行性第十页，共52页。软件生存周期并 行 度软件开发过程软件维护过程软件管理过程软件文档编制过程过 程 并 行第十一页，共52页。子子 过过 程程 并并 行行软件开发周期并行度子开发过程1子开发过程2子开发过程n初步需求分析集成与系统测试第十二页，共52页。阶 段 并 行软件(run jin)开发周期并行度总体设计详细(xingx)设计编 码测 试需求(xqi)分析第十三页，共52页。版版 本本 并并 行行软件生存周期并 行 度发行版本1的开发发行版本2的开发发行版本n的开发第十四页，共52页。:=PD|PM|SA|DR|PR|CP|MA|GL|E:=V;C:=;F:=;M:=;IF i0 THEN 验证软件过程p同第i-1层软件过程之间的一致性;3）尽早开始工作：在信息不充分的情况下开始工作，因此要有很强的应变能力。由TRG构造A中任务的相关关系R；Process_Refining(p,0)CCM建模方法(fngf):F:=FFF”;构造软件过程(guchng)模型能描述软件过程级（粗粒度）、活动级（细粒度）的并行行为。:=|CCM模型(mxng)例第四十三页，共52页。S:=SS;MC称为标记，它记录了过程P的一个瞬态。活 动 并 行 软件生存周期并 行 度开 始 编 码结 束 编 码编制模块1活动编制模块2活动编制模块n活动第十五页，共52页。SDDM模型(mxng)支持软件并行开发过程(guchng)的软件过程(guchng)模型：能定义软件开发中的各并行成分、各开发活动及它们相互之间的动态关系（也包括并行关系）。能定义软件过程(guchng)之间的动态关系。第十六页，共52页。任务是一个三元组T=其中P，Q均为谓词，我们称P为前断言，它刻划了任务T执行前的状态；Q称为后断言，它刻划了任务T执行后的状态。刻划了把输入转换为输出的操作。Ms是消息集合，其中的元素是二元组，m.text，表示当任务T完成(wn chng)时向软件过程p的活动a的任务t发送内容为的消息。既可以是一个字符串，也可以是一个可执行的过程第十七页，共52页。活动或者是一个任务序列T1T2Tn，它表示任务T1、T2、.、Tn顺序(shnx)地执行；或者是一个软件过程。第十八页，共52页。软件过程是一个六元组P=。其中 C为 条 件 的 集 合，C中 的 条 件 是 一 个 二 元 组,Q是一个谓词，表示条件；Ds是一个广义数据结构，是活动操作的对象。A是活动的集合。A中的活动a在其前提条件具备的情况下可以执行（称为点火）。但a能否顺利进行，还要看其内部的诸任务(rn wu)的前断言是否具备。CA=。F（CA）（AC），称为流关系。I，OC分别称为输入接口和输出接口。软件过程P将输入接口I的广义数据结构变为输出接口O的广义数据结构。MC称为标记，它记录了过程P的一个瞬态。第十九页，共52页。n系统动态(dngti)开发模型是一个二元组SDDM=，Ps是软件过程的集合，Pr=|P，PPs称为优先关系集，刻画了软件过程P必须在P前执行。无优先关系的过程可以并行执行。并行执行过程中的同步关系由软件过程自行发送消息进行控制。C4软件开发过程的图形表示软件开发过程的图形表示子开发过程1子开发过程2子开发过程n初 步 需 求 分 析 集 成 与 系 统 测 试初步需求分析子开发过程1子开发过程2子开发过程n集成与系统测试C1A1C2iA2iC3iA3第二十页，共52页。软件软件(run jin)过程建模语言特过程建模语言特征征动态性：由于软件过程是动态进行的，为支持设计者动态操作，应具有描述动态行为的成分。并行性：应具有描述不同粒度并行成分的能力。能描述软件过程级（粗粒度）、活动级（细粒度）的并行行为。一致性：由于软件过程中有多个角色协同工作，应具有描述角色行为和角色协同工作的成分，对角色的行为进行精确的定义并便于形式化地进行一致性检查。完整性：软件过程包括许多方面的内容，建模语言应对其中组织、功能、行为、信息诸方面的内容加以描述，提供和表达尽可能丰富的信息。模块性：提出过“软件过程也是软件”的观点并获得了广泛的认同，软件过程模型是程序。因此，模块性是自然(zrn)的要求。支持抽象与求精：软件过程建模可采用自顶向下、逐步求精的方法进行。应支持不同抽象级的过程描述，并具有用低层详细描述替换高层抽象描述的手段。第二十一页，共52页。基于Petri网，具有较好的并行表达能力和动态表达能力，便于并行控制。具有面向对象的特征，支持数据抽象、信息隐蔽和过程抽象，支持消息传递和单重继承。能表达各软件过程、子开发过程、活动之间的关系，能定义角色与活动之间的关系。可表示不同(b tn)抽象级的过程模型，支持以角色为中心的逐步求精的过程建模方法。一个软件过程模型就是一个SDDML程序。支持模型重用和过程重用。SDDML主要(zhyo)特征第二十二页，共52页。任务(rn wu)定义:=TASK ;BEGIN;END;:=PREASSERTION:=POSTASSERTION:=|()|NOT|AND|OR|IMPLY|IFF|COND(,)|ALL()()|EXISTS()():=MESSAGE BEGIN END:=SEND TO:=.|.第二十三页，共52页。活动(hu dng)定义:=ACTIVITY FROM IMPORTS;EXPORTS;LOCALS;BEGIN END;:=|:=:=:=:=STRUCTURE BEGIN:;:END:=PERFORMED BY.:;:=PD|PM|SA|DR|PR|CP|MA|GL|第二十四页，共52页。:=PROCESS FROM BEGIN;END;:=CONDITION SET BEGIN;END:=ACTIVITY SET BEGIN;END:=ARC SET BEGIN;END:=(,)|(,)软软 件过件过 程程 定义定义(dngy)第二十五页，共52页。系 统 动 态 开 发 模 型:=#define;SDDM FROM BEGIN;END.:=PROCESS PRIORITY SET BEGIN(,软件过程名);(,软件过程名)END:=MARKING SET BEGIN.;.END:=:第二十六页，共52页。并行度软件生存周期初步需求分析子开发过程1子开发过程2子开发过程n集成与系统测试软件开发过程DPd1 d2 d31d3n d41d4n d51d5n d6d7维护需求分析维护活动测试软件维护过程MPm1m3m5m7m6m4m2启动开发成本管理过程管理配置管理结束开发问题定义角色管理启动维护维护管理结束维护软件管理过程MGPc12c1c2c3c4 c51c54 c61c64 c71c74 c8c9c10c15c13c14c11SDDM模型(mxng)第二十七页，共52页。#define d2:初步需求分析;/*将术语“初步需求分析”符号化*/#define d41:子开发过程1;/*将术语“子开发过程1”符号化*/#define c14:结束维护;/*将术语“结束维护”符号化*/SDDM sample1PROCESS DP /*定义软件开发过程DP*/ACTIVITY d2 ;/*定义活动d2中任务、数据结构等*/ACTIVITY d41;/*定义活动d41中任务、数据结构等*/ACTIVITY d6 ;/*定义活动d6中任务、数据结构等*/BEGIN CONDITION SET BEGIN d1;d31;d3n;d51;d5n;d7 END;/*DP中条件(圆圈)集*/ACTIVITY SET BEGIN d2;d41;d4n;d6 END;/*DP中活动(方框)集*/ARC SET BEGIN(d1,d2);(d2,d31);(d2,d3n);(d6,d7)END /*DP中弧(箭头)集*/END;/*End of PROCESS DP*/PROCESS MP ;/*定义软件维护过程MP*/PROCESS MGP ;/*定义软件管理过程MGP*/BEGIN PROCESS PRIORITY SET BEGIN(DP,MP)END;/*DP必须在MP前启动*/MARKING SET BEGIN MGP.c1 END /*初始标记(bioj)为仅有MGP中的条件c1一个元素的集合*/END./*End of SDDM sample1 SDDML程序程序(chngx)第二十八页，共52页。基于基于(jy)SDDML(jy)SDDML 的过程建模方法的过程建模方法PROCEDURE Process_Modeling;PROCEDURE Process_Refining(p:process;i:integer);BEGIN 在p所应该涉及的范围(fnwi)内标识第i层角色，这些角色构成集合Ri;分析Ri中角色所处理的广义数据结构、活动、任务及它们与外界的联系（消息）;根据Ri中角色所处理的内容用SDDML定义活动（每一个角色定义一个活动）;分析Ri中角色所实施的活动之间的关系;根据Ri中角色所实施的活动及它们之间的关系用SDDML定义软件过程p;IF i0 THEN 验证软件过程p同第i-1层软件过程之间的一致性;IF 软件过程p中还有需要细化的活动 THEN BEGIN 将每一个需要细化的活动标识为一个软件过程，这些软件过程构成集合Si;FOR Si中的每一个软件过程pi DO Process_Refining(pi,i+1)END;利用继承机制定义细化后的系统动态开发模型，用以说明第i-1层中需细化的活动在第i层中已被软件过程p所替代 END;/*End of Process_Refining*/BEGIN 标识构成软件过程模型的诸软件过程，这些软件过程构成集合S;确定S中软件过程之间的优先关系;根据S中软件过程及它们之间的优先关系，用SDDML定义系统动态开发模型;FOR S中的每一个软件过程p DO Process_Refining(p,0)END;/*End of Process_Modeling*/第二十九页，共52页。基于Petri网、严格形式化，可以精确地描述并行的软件过程和软件过程内部的并行成分。层次化，可用来构造不同抽象级的软件过程，可通过实际的执行来验证不同抽象级的软件过程模型的一致性。可以挖掘软件过程内部的并行性，延拓局部的并行性到全局qunj)，提高了软件过程的并行度。SDDM和SDDML第三十页，共52页。相关类型定义：活动相关图是一个三元组ARG=。V，为活动节点集，其中元素称为活动。DVV，为有向边集，其中元素称为有向边。R：D，o，c，称为相关函数。定义：活动A的输入数据集记为input(A)，输出数据集记为output(A)。除input(A)和output(A)外，其它数据均认为局部于活动A。第三十一页，共52页。相关(xinggun)类型定义：在活动相关图ARG=中，对A1，A2V，A1在A2之前进行：（1）若output(A1)input(A2)，则称A1正相关于A2，记为A1A2，为正相关类型。（2）若output(A2)input(A1)，则称A1反相关于A2，记为A1 A2，为反相关类型。（3）若output(A1)output(A2)，则称A1输出相关于A2，记为A1oA2，o为输出相关类型。定义：在活动相关图ARG=中，对A1，A2V，若A2进行与否取决于A1的进行结果，则称A1控制相关于A2，记为A1c A2，c为控制相关类型。第三十二页，共52页。构造活动(hu dng)相关图算法(构造活动相关图ARG)输入：活动集E=A1，A2，An；input(Ai)，output(Ai)(i=1，2，n)；顺序关系S=|Ai在Aj之前进行；控制关系C=|Ai决定Aj是否(sh fu)进行。输出：活动相关图ARG=。BEGIN V:=E;D:=;R:=;FOR i:=1 TO n DO FOR j:=1 TO n DO BEGIN IF S THEN BEGIN IF output(Ai)input(Aj)THEN BEGIN D:=D(Ai，Aj);R:=R END;IF output(Aj)input(Ai)THEN BEGIN D:=D(Ai，Aj);R:=R END;IF output(Ai)output(Aj)THEN BEGIN D:=D(Ai，Aj);R:=R END END;IF C THEN BEGIN D:=D(Ai，Aj);R:=R END ENDEND.第三十三页，共52页。构造软件过程(guchng)模型算法(构造软件过程模型P)输入：活动相关(xinggun)图ARG=。输出：软件过程模型P=。BEGIN E:=V;C:=;F:=;M:=;FOR i:=1 TO n DO /*n为V、E中的节点数*/FOR j:=1 TO n DO BEGIN IF(Vi，Vj)D)(R(Vi，Vj)c)THEN /*Vi，VjV且Vi，VjE*/BEGIN C:=CCij;F:=F(Vi，Cij)，(Cij，Vj)END;IF(Vi，Vj)D)(R(Vi，Vj)=c)THEN BEGIN C:=CCi;F:=F(Vi，Ci)，(Ci，Vj)END ENDFOR i:=1 TO n DO BEGIN IF Vi=THEN BEGIN C:=CCi”;F:=F(Vi，Ci”)END;IF Vi=THEN BEGIN C:=CCi;F:=F(Ci，Vi);M:=MCi END ENDEND.第三十四页，共52页。并行性挖掘(wju)rr(a)A1A2(b)V1V2分解活动前后的活动相关图V3V4V5V6 活动相关(xinggun)图构造的软件过程模型C23C12C45C25C1V1V2V3C3”C4V4V5V6C56C6”第三十五页，共52页。C4C1C51”C3”C23A1A2A4A3A5A6活动相关图构造的软件过程模型C12C14C6”cc/oA1A2A3A4A5A6活动相关图第三十六页，共52页。活动(hu dng)并行化算法（将活动(hu dng)A并行化）输入：活动(hu dng)A，A的前流FIRST(A)，A的后流FOLLOW(A)。输出：软件过程模型P=。BEGIN 构造A中任务的相关图TRG；由TRG构造A中任务的相关关系R；构造A的任务集合T关于R的商集T/R,得划分块的集合Tb1，Tb2，Tbn；将每一个划分块定义为一个新活动(hu dng)，新活动(hu dng)中不改变原任务进行的顺序，得活动(hu dng)集Ab=A1，A2，An；/*Ab中每一个元素为一个任务序列*/E:=AbA，A”；F:=；C:=C1C2，Cn，C1”，C2”，Cn”；FOR i:=1 TO n DO F:=F(A，Ci)，(Ci”，A”)，(Ci，Ai)，(Ai，Ci”)；F:=FFIRST(A/A)FOLLOW(A”/A)END.第三十七页，共52页。(a)CABAA1A2AnCA”BB1B2BmB”(b)活动(hu dng)并行化第三十八页，共52页。划分块之间的相关(xinggun)关系判别算法（划分块之间的相关关系判别）输入：活动集A=A1，A2，An，A的同步关系RA，活动Ai 的输入、输出数据集input(Ai)、output(Ai)(i=1，2，n)；活动集B=B1，B2，Bm，B的同步关系RB，活动Bj 的输入、输出数据集input(Bj)、output(Bj)(j=1，2，m)。输出：表明(biomng)划分块之间是否相关的二维数组AB，划分Ab，Bb。BEGIN构造A关于RA的商集A/RA，得划分Ab=Ab1，Ab2，Abs；构造B关于RB的商集B/RB，得划分Bb=Bb1，Bb2，Bbt；AB1.s，1.t:=false；FOR i:=1 TO s DO FOR j:=1 TO t DO FOR i:=1 TO si DO/*块Abi中有si个活动*/FOR j:=1 TO tj DO/*块Bbj中有tj 个活动*/BEGIN 判别Abii，Bbjj之间的相关关系；/*AbiiAbi，BbjjBbj*/IF Abii与Bbjj 相关 THEN ABi，j:=true ENDEND.第三十九页，共52页。算法（并行性延拓）输入：软件过程模型P=；活动集A=A1，A2，An，A的同步关系RA，活动Ai 的输入、输出数据集input(Ai)、output(Ai)(i=1，2，n)；活动集B=B1，B2，Bm，B的同步关系RB，活动Bj 的输入、输出数据集input(Bj)、output(Bj)(j=1，2，m)。输出：延拓中并行性后得到的新软件过程模型P=。BEGIN CALL 划分块之间的相关关系判别算法获得(hud)布尔数组AB及划分Ab，Bb；E:=E-A”，B；C:=C-C；F:=F-FIRST(A”)-FIRST(B)-FOLLOW(A”)-FOLLOW(B)；FOR i:=1 TO s DO/*Ab中有s 个划分块*/BEGIN FOR j:=1 TO t DO/*Bb中有t 个划分块*/IF ABi，j THEN BEGIN E:=EBj，Ai”；C:=CCij；FOR j:=1 TO tj DO /*块Bbj中有tj个活动：Bj1，Bj2，*/F:=F(Bj，FCjj)；/*FCjj为指向Bjj的条件*/F:=F(Ai”，Cij)，(Cij，Bj)；FOR i:=1 TO si DO /*块Ab i中有si个活动：Ai1，Ai2，*/F:=F(LCiiAi”)/*LCii表示Aii所指向的条件*/END;IF AB第i行均为false THEN /*Ab第i块不同Bb中任何一块有相关关系*/FOR i:=1 TO si DO F:=F(LCii，B”)END;FOR j:=1 TO t DO IF AB第j列均为false THEN/*Ab中不存在任何一块与Bb中第j块有相关关系*/FOR j:=1 TO tj DO F:=F(A，FCjj)END.第四十页，共52页。AA21A22A2bA2”B2B21B22B2dB”A11A12A1aA1”B1B11B12B1cA k1A k2A kjA k”BkBk1Bk2Bkm并行性延拓第四十一页共52页。并行控制(kngzh)模型CCM定义：=(S，T，F，C)称为一个CCM模型，如果：(1)(S，T，F)是一个网；(2)C是一个标记集合(jh)，若M1 和M2 为C中任意二个标记，则必然有一个广义步序列g1g2 gn，使得标记M1 转换为M2，记为M1 M2。广义步或者是一步s，或一步的逆s-1。(3)对T中任一活动e，必存在C中的一个标记，使e在此标记下能点火。第四十二页，共52页。串行块ei ej第四十三页，共52页。并行(bngxng)块eiej第四十四页，共52页。互斥块ejei第四十五页，共52页。同步(tngb)块eje0enei第四十六页，共52页。重复块ei ej第四十七页，共52页。基本块 启动过程 过程进行 结束过程 start process finish第四十八页，共52页。CCM建模方法(fngf)输入:启动过程指令“start”，结束过程指令“finish”，过程进行“process”，根据过程进行需要确定的可以并行进行的活动及相应的条件。输出:CCM模型=(S,T,F,C)BEGIN S:=start,finish;T:=process;F:=,;C:=start;F”:=;LS:=;FS:=;WHILE T中尚有活动可细化 DO BEGIN e:=T中任一可细化元素;根据需要，将e 细化为某一种基元块，并将该块中用虚线框围住的部分(b fen)形式地表示为三元组=（S，T，F);T:=Te;加所有的t到集合LS中(tT且所有形如(t,c)的边基元块且c没有被虚线框围住);加所有的t到集合FS中(tT且所有形如(c,t)的边基元块且c没有被虚线框围住);WHILE F中有形如和的边f DO BEGIN F:=F f ;根据实际需要形成形如或的边加到F”中（eLS,e”FS，ce，c”e）；END；S:=SS;T:=TT;F:=FFF”;END;输出=(S,T,F,C)END.第四十九页，共52页。一个CCM模型的建立过程第五十页，共52页。需求确认2完成集成测试验证原型2一致性验证1划分开始划分确认2划分确认1需求分析2需求分析1需求确认1需求确认3划分调整1一致性验证2验收测试调整确认2调整确认1设计2设计1构造原型2构造原型1设计确认2设计确认1设计确认3划分调整2调整确认4调整确认3原型确认2原型确认1执行原型2执行原型1验证原型1集成确认确认原型4优化原型2优化原型1原型确认3图4.11 一个细化后的CCM模型错误识别错误识别CCM模型(mxng)例第五十一页，共52页。谢 谢 ！第五十二页，共52页。