软件并行开发过程精品文稿.ppt

《软件并行开发过程精品文稿.ppt》由会员分享，可在线阅读，更多相关《软件并行开发过程精品文稿.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、软件并行开发过程第1页，本讲稿共52页云南省中青年学术和技术带头人培养基金项目1998-37云南省自然科学基金项目 98F023M98F005G2001F0006M第2页，本讲稿共52页问题的提出 一、生产率低下二、质量欠佳第3页，本讲稿共52页背 景 并行工程 并行处理 多个程序员同时为同一个系统编码 现 实 生 活 中 的 各 类 非 自 觉 的、偶 然 的并行行为第4页，本讲稿共52页制造业并行工程市场分析产品设计工艺设计 采 购制 造检 测装 配销 售维 修并行度进行反馈产品生存周期第5页，本讲稿共52页 1982年，美 国 国 防 部 发 表 了 著 名 的R-338 报 告，正 式

2、 提 出 了“并 行 工 程”的 概 念：并 行 工 程 是 集 成 地、并 行 地 设 计 产 品 及 其 相 关 的 各 种 过 程（包括 制 造 过 程 和 支 持 过 程）的 系 统 化 方 法。这 种 方 法 要 求 产 品 开 发 人 员 从设 计 一 开 始 就 考 虑 产 品 整 个 生 存 周 期 中 从 概 念 形 成 到 产 品 报 废 处 理 的 所有因素，包括质量、成本、进度、计划和用户的要求。并 行 工 程 目 前 已 成 为 制 造 业 研 究 与 实 践 的 热 点 领 域。在 国 外 已 成 功 地应 用 于 航 空、航 天、电 子、汽 车 等 领 域，如 福

3、 特 汽 车 公 司、波 音 公 司、洛克希德公司、丰田汽车公司。我 国 并 行 工 程 的 研 究 始 于90年 代 初，国 家 科 委 在863计 划 中 设 立 了 一 些课 题 支 持 并 行 工 程 的 研 究，已 有 少 数 几 家 企 业 开 始 实 施 并 行 工 程，并 取得 了 新 产 品 开 发 样 机 周 期 缩 短、产 品 综 合 技 术 经 济 指 标 好、符 合 市 场 需求、经济效益好等效益。并行工程现状第6页，本讲稿共52页 1）并行性：各种活动并行交叉进行。既包括各个部件开发的并行交叉，又包括各个阶段的并行交叉。2）流程改善：通过改善与优化工作流程，提高产品

4、质量。3）尽早开始工作：在信息不充分的情况下开始工作，因此要有很强的应变能力。4）集成化：强调全面优化，追求产品整体的竞争力和各小组的密切有机合作。5）强有力的支撑环境：必须有良好的支撑多小组并行协同工作的网络与计算机平台。6）强有力的管理：强调强有力的管理，保证各种并行活动协调统一地进行。并行工程特点第7页，本讲稿共52页 软件过程软件过程指软件生存周期中所涉及的一系列相关过程。过程是活动的集合，活动是任务的集合，任务是把输入转换为输出的操作。软件过程是动态的，它动态地产生、推进（执行），动态地消亡。软件过程模型是对软件过程的静态描述，是软件过程向前推进的依据。第8页，本讲稿共52页软件过程

5、-ISO/IEC 12207 1.主要过程类获取过程供应过程开发过程运行过程维护过程 3.组织过程类管理过程基础设施过程改进过程培训过程2.支持过程类 文档编制过程 配置管理过程 质量保证过程 验证过程 确认过程 联合评审过程 审核过程 问题解决过程第9页，本讲稿共52页 过程并行 子过程并行 阶段并行 版本并行 活动并行软件生存周期中的并行性第10页，本讲稿共52页 软件生存周期并 行 度软件开发过程 软件维护过程软件管理过程软件文档编制过程过 程 并 行第11页，本讲稿共52页子 过 程 并 行软件开发周期并行度子开发过程1子开发过程2子开发过程n初步需求分析集成与系统测试第12页，本讲稿

6、共52页 阶 段 并 行软件开发周期并行度总体设计详细设计编 码测 试需求分析第13页，本讲稿共52页版 本 并 行软件生存周期并 行 度发行版本1的开发发行版本2的开发发行版本n的开发第14页，本讲稿共52页活 动 并 行 软件生存周期并 行 度开 始 编 码结 束 编 码编制模块1活动编制模块2活动编制模块n活动第15页，本讲稿共52页 SDDM 模型 支持软件并行开发过程的软件过程模型：能定义软件开发中的各并行成分、各开发活动及它们相互之间的动态关系（也包括并行关系）。能定义软件过程之间的动态关系。第16页，本讲稿共52页任务是一个三元组T=，其中P，Q均为谓词，我们称P为前断言，它刻划

7、了任务T执行前的状态；Q称为后断言，它刻划了任务T执行后的状态。刻划了把输入转换为输出的操作。Ms是消息集合，其中的元素是二元组m=，表示当任务T完成时向软件过程p的活动a的任务t发送内容为 m.text的消息。m.text既可以是一个字符串，也可以是一个可执行的过程第17页，本讲稿共52页活动或者是一个任务序列T1T2Tn，它表示任务T1、T2、.、Tn顺序地执行；或者是一个软件过程。第18页，本讲稿共52页软件过程是一个六元组P=。其中C为条件的集合，C中的条件是一个二元组,Q是一个谓词，表示条件；Ds是一个广义数据结构，是活动操作的对象。A是活动的集合。A中的活动a在其前提条件具备的情况

8、下可以执行（称为点火）。但a能否顺利进行，还要看其内部的诸任务的前断言是否具备。CA=。F（CA）（AC），称为流关系。I，O C分别称为输入接口和输出接口。软件过程P将输入接口I的广义数据结构变为输出接口O的广义数据结构。M C称为标记，它记录了过程P的一个瞬态。第19页，本讲稿共52页n系统动态开发模型是一个二元组SDDM=，Ps是软件过程的集合，Pr=|P，P Ps称为优先关系集，刻画了软件过程P必须在P前执行。无优先关系的过程可以并行执行。并行执行过程中的同步关系由软件过程自行发送消息进行控制。C4软件开发过程的图形表示 软件开发过程的图形表示子开发过程1子开发过程2子开发过程n初 步

9、 需 求 分 析 集 成 与 系 统 测 试初步需求分析子开发过程1子开发过程2子开发过程n集成与系统测试C1A1C2iA2i C3iA3第20页，本讲稿共52页 软件过程建模语言特征 动态性：由于软件过程是动态进行的，为支持设计者动态操作，应具有描述动态行为的成分。并行性：应具有描述不同粒度并行成分的能力。能描述软件过程级（粗粒度）、活动级（细粒度）的并行行为。一致性：由于软件过程中有多个角色协同工作，应具有描述角色行为和角色协同工作的成分，对角色的行为进行精确的定义，并便于形式化地进行一致性检查。完整性：软件过程包括许多方面的内容，建模语言应对其中组织、功能、行为、信息诸方面的内容加以描述

10、，提供和表达尽可能丰富的信息。模块性：L.Osterweil提出过“软件过程也是软件”的观点并获得了广泛的认同，软件过程模型是程序。因此，模块性是自然的要求。支持抽象与求精：软件过程建模可采用自顶向下、逐步求精的方法进行。应支持不同抽象级的过程描述，并具有用低层详细描述替换高层抽象描述的手段。第21页，本讲稿共52页基于Petri网，具有较好的并行表达能力和动态表达能力，便于并行控制。具有面向对象的特征，支持数据抽象、信息隐蔽和过程抽象，支持消息传递和单重继承。能表达各软件过程、子开发过程、活动之间的关系，能定义角色与活动之间的关系。可表示不同抽象级的过程模型，支持以角色为中心的逐步求精的过程

11、建模方法。一个软件过程模型就是一个SDDML程序。支持模型重用和过程重用。SDDML主要特征第22页，本讲稿共52页 任务定义:=TASK;BEGIN;END;:=PREASSERTION:=POSTASSERTION:=|()|NOT|AND|OR|IMPLY|IFF|COND(,)|ALL()()|EXISTS()():=MESSAGE BEGIN END:=SEND TO:=.|.第23页，本讲稿共52页 活动 定义:=ACTIVITY FROM IMPORTS;EXPORTS;LOCALS;BEGIN END;:=|:=:=:=:=STRUCTURE BEGIN:;:END:=PERF

12、ORMED BY.:;:=PD|PM|SA|DR|PR|CP|MA|GL|第24页，本讲稿共52页:=PROCESS FROM BEGIN;END;:=CONDITION SET BEGIN;END:=ACTIVITY SET BEGIN;END:=ARC SET BEGIN;END:=(,)|(,)软 件过 程 定义第25页，本讲稿共52页 系 统 动 态 开 发 模 型:=#define;SDDM FROM BEGIN;END.:=PROCESS PRIORITY SET BEGIN(,软件过程名);(,软件过程名)END:=MARKING SET BEGIN.;.END:=:第26页，本

13、讲稿共52页 并行度软件生存周期初步需求分析子开发过程1子开发过程2子开发过程n集成与系统测试软件开发过程DPd1 d2 d31d3n d41d4n d51d5n d6d7维护需求分析维护活动测试软件维护过程MPm1 m3 m5m7m6m4m2启动开发成本管理过程管理配置管理结束开发问题定义角色管理启动维护维护管理结束维护软件管理过程MGPc12c1c2c3c4 c51c54 c61c64 c71c74 c8c9c10c15 c13c14c11SDDM 模型第27页，本讲稿共52页#define d2:初步需求分析;/*将术语“初步需求分析”符号化*/#define d41:子开发过程1;/*

14、将术语“子开发过程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

15、 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/*初始标记为仅有MGP中的条件c1一个元素的集合*/END./*End of SDDM sample1 SDDML 程序第28页，本讲稿共52页 基于 SD

16、DML 的过程建模方法PROCEDURE Process_Modeling;PROCEDURE Process_Refining(p:process;i:integer);BEGIN 在p所应该涉及的范围内标识第i层角色，这些角色构成集合Ri;分析Ri中角色所处理的广义数据结构、活动、任务及它们与外界的联系（消息）;根据Ri中角色所处理的内容用SDDML定义活动（每一个角色定义一个活动）;分析Ri中角色所实施的活动之间的关系;根据Ri中角色所实施的活动及它们之间的关系用SDDML定义软件过程p;IF i0 THEN 验证软件过程p同第i-1层软件过程之间的一致性;IF 软件过程p中还有需要细化

17、的活动 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_Refi

18、ning(p,0)END;/*End of Process_Modeling*/第29页，本讲稿共52页 基于Petri网、严格形式化，可以精确地描述并行的软件过程和软件过程内部的并行成分。层次化，可用来构造不同抽象级的软件过程，可通过实际的执行来验证不同抽象级的软件过程模型的一致性。可以挖掘软件过程内部的并行性，延拓局部的并行性到全局，提高了软件过程的并行度。SDDM 和SDDML第30页，本讲稿共52页 相关类型定义：活动相关图是一个三元组ARG=。V，为活动节点集，其中元素称为活动。D VV，为有向边集，其中元素称为有向边。R：D，o，c，称为相关函数。定义：活动A的输入数据集记为inp

19、ut(A)，输出数据集记为output(A)。除input(A)和output(A)外，其它数据均认为局部于活动A。第31页，本讲稿共52页 相关类型定义：在活动相关图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的进行结

20、果，则称A1控制相关于A2，记为A1c A2，c为控制相关类型。第32页，本讲稿共52页 构造活动相关图算法(构造活动相关图ARG)输入：活动集E=A1，A2，An；input(Ai)，output(Ai)(i=1，2，n)；顺序关系S=|Ai在Aj之前进行；控制关系C=|Ai决定Aj是否进行。输出：活动相关图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(

21、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.第33页，本讲稿共52页 构造软件过程模型算法(构造软件过程模型P)输入：活动相关图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，V

22、j)c)THEN/*Vi，VjV且Vi，VjE*/BEGIN C:=C Cij;F:=F(Vi，Cij)，(Cij，Vj)END;IF(Vi，Vj)D)(R(Vi，Vj)=c)THEN BEGIN C:=C Ci;F:=F(Vi，Ci)，(Ci，Vj)END END;FOR i:=1 TO n DO BEGIN IF Vi=THEN BEGIN C:=C Ci”;F:=F(Vi，Ci”)END;IF Vi=THEN BEGIN C:=C Ci;F:=F(Ci，Vi);M:=M Ci END ENDEND.第34页，本讲稿共52页 并行性挖掘 rr(a)A1A2(b)V1V2分解活动前后的活动相

23、关图V3V4V5V6 活动相关图构造的软件过程模型C23C12C45C25C1V1V2V3C3”C4V4V5V6C56C6”第35页，本讲稿共52页 C4C1C51”C3”C23A1A2A4A3A5A6活动相关图构造的软件过程模型C12C14C6”cc/oA1A2A3A4A5A6活动相关图第36页，本讲稿共52页 活动并行化算法（将活动A并行化）输入：活动A，A的前流FIRST(A)，A的后流FOLLOW(A)。输出：软件过程模型P=。BEGIN 构造A中任务的相关图TRG；由TRG构造A中任务的相关关系R；构造A的任务集合T关于R的商集T/R,得划分块的集合Tb1，Tb2，Tbn；将每一个划

24、分块定义为一个新活动，新活动中不改变原任务进行的顺序，得活动集Ab=A1，A2，An；/*Ab中每一个元素为一个任务序列*/E:=Ab A，A”；F:=；C:=C1，C2，Cn，C1”，C2”，Cn”；FOR i:=1 TO n DO F:=F(A，Ci)，(Ci”，A”)，(Ci，Ai)，(Ai，Ci”)；F:=F FIRST(A/A)FOLLOW(A”/A)END.第37页，本讲稿共52页(a)CABAA1A2AnC A”BB1B2BmB”(b)活动并行化第38页，本讲稿共52页 划分块之间的相关关系判别算法（划分块之间的相关关系判别）输入：活动集A=A1，A2，An，A的同步关系RA，活

25、动Ai 的输入、输出数据集input(Ai)、output(Ai)(i=1，2，n)；活动集B=B1，B2，Bm，B的同步关系RB，活动Bj 的输入、输出数据集input(Bj)、output(Bj)(j=1，2，m)。输出：表明划分块之间是否相关的二维数组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:

26、=1 TO tj DO/*块Bbj中有tj 个活动*/BEGIN 判别Abii，Bbjj之间的相关关系；/*AbiiAbi，BbjjBbj*/IF Abii与Bbjj 相关 THEN ABi，j:=true ENDEND.第39页，本讲稿共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

27、=。BEGIN CALL 划分块之间的相关关系判别算法获得布尔数组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:=E Bj，Ai”；C:=C Cij；FOR j:=1 TO tj DO/*块Bbj中有tj个活动：Bj1，Bj2，*/F:=F(Bj，FCjj)；/*FCjj为指向Bjj的条件*/F:=F(Ai”，Cij)，(

28、Cij，Bj)；FOR i:=1 TO si DO/*块Ab i中有si个活动：Ai1，Ai2，*/F:=F(LCii，Ai”)/*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.第40页，本讲稿共52页 AA21A22A2bA2”B2B21B22B2dB

29、”A11A12A1aA1”B1B11B12B1cA k1A k2A kjA k”BkBk1Bk2Bkm并行性延拓第41页，本讲稿共52页 并行控制模型CCM定义：=(S，T，F，C)称为一个CCM模型，如果：(1)(S，T，F)是一个网；(2)C是一个标记集合，若M1 和M2 为C中任意二个标记，则必然有一个广义步序列g1g2 gn，使得标记M1 转换为M2，记为M1 M2。广义步或者是一步s，或一步的逆s-1。(3)对T中任一活动e，必存在C中的一个标记，使e在此标记下能点火。第42页，本讲稿共52页 串行块ei ej第43页，本讲稿共52页 并行块eiej第44页，本讲稿共52页 互斥块e

30、jei第45页，本讲稿共52页 同步块eje0enei第46页，本讲稿共52页 重复块ei ej第47页，本讲稿共52页 基本块 启动过程 过程进行 结束过程 start process finish第48页，本讲稿共52页 CCM 建模方法输入:启动过程指令“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

31、:=T中任一可细化元素;根据需要，将e 细化为某一种基元块，并将该块中用虚线框围住的部分形式地表示为三元组=（S，T，F);T:=Te;加所有的t到集合LS中(t T且所有形如(t,c)的边基元块且c没有被虚线框围住);加所有的t到集合FS中(t T且所有形如(c,t)的边基元块且c没有被虚线框围住);WHILE F中有形如和的边f DO BEGIN F:=F f;根据实际需要形成形如或的边加到F”中（e LS,e”FS，c e，c”e）；END；S:=S S;T:=T T;F:=F F F”;END;输出=(S,T,F,C)END.第49页，本讲稿共52页 一个CCM 模型的建立过程第50页，本讲稿共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 模型例第51页，本讲稿共52页谢 谢！第52页，本讲稿共52页