软件并行开发过程.ppt

1、软 件 学 院,李 彤 博士,2007年 春,软件并行开发过程,云南省中青年学术和技术带头人培养基金项目 1998-37,云南省自然科学基金项目 98F023M 98F005G 2001F0006M,问题的提出,一、生产率低下 二、质量欠佳,背 景,并行工程 并行处理 多个程序员同时为同一个系统编码 现实生活中的各类非自觉的、偶然的并行行为,制造业并行工程,1982年，美国国防部发表了著名的R-338报告，正式提出了“并行工程”的概念：并行工程是集成地、并行地设计产品及其相关的各种过程（包括制造过程和支持过程）的系统化方法。这种方法要求产品开发人员从设计一开始就考虑产品整个生存周期中从概念形成

2、到产品报废处理的所有因素，包括质量、成本、进度、计划和用户的要求。 并行工程目前已成为制造业研究与实践的热点领域。在国外已成功地应用于航空、航天、电子、汽车等领域，如福特汽车公司、波音公司、洛克希德公司、丰田汽车公司。 我国并行工程的研究始于90年代初，国家科委在863计划中设立了一些课题支持并行工程的研究，已有少数几家企业开始实施并行工程，并取得了新产品开发样机周期缩短、产品综合技术经济指标好、符合市场需求、经济效益好等效益。,并行工程现状,1）并行性：各种活动并行交叉进行。既包括各个部件开发的并行交叉，又包括各个阶段的并行交叉。 2）流程改善：通过改善与优化工作流程，提高产品质量。 3）尽

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

4、程类 获取过程 供应过程 开发过程 运行过程 维护过程,3. 组织过程类 管理过程 基础设施过程 改进过程 培训过程,2. 支持过程类 文档编制过程 配置管理过程 质量保证过程 验证过程 确认过程 联合评审过程 审核过程 问题解决过程,过程并行 子过程并行 阶段并行 版本并行 活动并行,软件生存周期中的并行性,过 程 并 行,子 过 程 并 行,阶 段 并 行,软件开发周期,并行度,总体设计,详细设计,编 码,测 试,需求分析,版 本 并 行,活 动 并 行,SDDM模型,支持软件并行开发过程的软件过程模型： 能定义软件开发中的各并行成分、各开发活动及它们相互之间的动态关系（也包括并行关系）。

5、 能定义软件过程之间的动态关系。,任务是一个三元组T=，其中P，Q均为谓词，我们称P为前断言， 它刻划了任务T执行前的状态；Q称为后断言，它刻划了任务T执行后的状态。刻划了把输入转换为输出的操作。Ms是消息集合，其中的元素是二元组m=，表示当任务T完成时向软件过程p的活动a的任务t发送内容为m.text的消息。m.text既可以是一个字符串，也可以是一个可执行的过程,活动或者是一个任务序列T1T2Tn，它表示任务T1、T2、.、Tn顺序地执行；或者是一个软件过程。,软件过程是一个六元组P=。其中C为条件的集合，C中的条件是一个二元组,Q是一个谓词，表示条件；Ds是一个广义数据结构，是活动操作的

6、对象。A是活动的集合。A中的活动a在其前提条件具备的情况下可以执行（称为点火）。但a能否顺利进行，还要看其内部的诸任务的前断言是否具备。CA=。F（CA）（AC），称为流关系。I，OC分别称为输入接口和输出接口。软件过程P将输入接口I的广义数据结构变为输出接口O的广义数据结构。MC称为标记，它记录了过程P的一个瞬态。,系统动态开发模型是一个二元组SDDM=，Ps是软件过程的集合，Pr=|P，PPs称为优先关系集，刻画了软件过程P必须在P前执行。无优先关系的过程可以并行执行。并行执行过程中的同步关系由软件过程自行发送消息进行控制。,软件过程建模语言特征,动态性：由于软件过程是动态进行的，为支持设

7、计者动态操作，应具有描述动态行为的成分。 并行性：应具有描述不同粒度并行成分的能力。能描述软件过程级（粗粒度）、活动级（细粒度）的并行行为。 一致性：由于软件过程中有多个角色协同工作，应具有描述角色行为和角色协同工作的成分，对角色的行为进行精确的定义，并便于形式化地进行一致性检查。 完整性：软件过程包括许多方面的内容，建模语言应对其中组织、功能、行为、信息诸方面的内容加以描述，提供和表达尽可能丰富的信息。 模块性：L.Osterweil提出过“软件过程也是软件”的观点并获得了广泛的认同，软件过程模型是程序。因此，模块性是自然的要求。 支持抽象与求精：软件过程建模可采用自顶向下、逐步求精的方法进

8、行。应支持不同抽象级的过程描述，并具有用低层详细描述替换高层抽象描述的手段。,基于Petri网，具有较好的并行表达能力和动态表达能力，便于并行控制。 具有面向对象的特征，支持数据抽象、信息隐蔽和过程抽象，支持消息传递和单重继承。 能表达各软件过程、子开发过程、活动之间的关系，能定义角色与活动之间的关系。 可表示不同抽象级的过程模型，支持以角色为中心的逐步求精的过程建模方法。 一个软件过程模型就是一个SDDML程序。 支持模型重用和过程重用。,SDDML主要特征,任务定义,:=TASK ; BEGIN ; END; :=PREASSERTION :=POSTASSERTION :=|()|NOT

9、|AND|OR|IMPLY|IFF|COND(,)|ALL()()|EXISTS()() :=MESSAGE BEGIN END :=SEND TO :=.|.,活动 定义,:=ACTIVITY FROM IMPORTS ; EXPORTS ; LOCALS ; BEGIN END; :=| := := := :=STRUCTURE BEGIN :;: END :=PERFORMED BY .: ; :=PD|PM|SA|DR|PR|CP|MA|GL|,:=PROCESS FROM BEGIN ; ; END; :=CONDITION SET BEGIN ; END :=ACTIVITY SE

10、T BEGIN ; END :=ARC SET BEGIN ; END :=(,) | (,),软 件过 程 定义,系 统 动 态 开 发 模 型,:=#define ; SDDM FROM BEGIN ; END. :=PROCESS PRIORITY SET BEGIN (,:=MARKING SET BEGIN .;. END :=:,SDDM模型,#define d2: 初步需求分析; /*将术语“初步需求分析”符号化*/ #define d41: 子开发过程1; /*将术语“子开发过程1”符号化*/ #define c14: 结束维护; /*将术语“结束维护”符号化*/ SDDM s

11、ample1 PROCESS 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);(d

12、6,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程序,基于 SDDML 的过程建模方法,PROCEDURE Process_Mo

13、deling; 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中还有需要细化的活动 THEN BEGIN 将每一个需

14、要细化的活动标识为一个软件过程，这些软件过程构成集合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)

15、END; /*End of Process_Modeling*/,基于Petri网、严格形式化，可以精确地描述并行的软件过程和软件过程内部的并行成分。 层次化，可用来构造不同抽象级的软件过程，可通过实际的执行来验证不同抽象级的软件过程模型的一致性。 可以挖掘软件过程内部的并行性，延拓局部的并行性到全局，提高了软件过程的并行度。,SDDM和SDDML,相关类型,构造活动相关图,算法 (构造活动相关图ARG) 输入：活动集E=A1，A2，An；input(Ai)，output(Ai) (i=1，2，n)；顺序关系S=|Ai在Aj之前进行；控制关系C=|Ai决定Aj是否进行。 输出：活动相关图ARG

16、=。 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 END

17、END.,构造软件过程模型,算法 (构造软件过程模型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，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) EN

18、D END; FOR 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 END END.,并行性挖掘,活动相关图构造的软件过程模型,活动并行化,算法（将活动A并行化） 输入：活动A，A的前流FIRST(A)，A的后流FOLLOW(A)。 输出：软件过程模型P=。 BEGIN 构造A中任务的相关图TRG； 由TRG构造A中任务的相关关系R； 构造A的任务集合T关于R的商集T/R,得划分块的集合Tb1，Tb2，Tbn ；

19、 将每一个划分块定义为一个新活动，新活动中不改变原任务进行的顺序，得活动集Ab=A1，A2，An；/*Ab中每一个元素为一个任务序列*/ E:=AbA，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:=FFIRST(A/A)FOLLOW(A”/A) END.,活动并行化,划分块之间的相关关系判别,算法（划分块之间的相关关系判别） 输入：活动集A=A1，A2，An，A的同步关系RA，活动Ai 的输入、输出数据集input(Ai)、output(Ai) (i=1，2，

20、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:=1 TO tj DO /*块Bbj中有tj 个活动*/ BE

21、GIN 判别Abii，Bbjj之间的相关关系；/* AbiiAbi，BbjjBbj*/ IF Abii与Bbjj 相关 THEN ABi，j:=true END END.,算法（并行性延拓） 输入：软件过程模型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 划分块之间的相关关系判别算法获得布尔数组

22、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(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中不存在任何