软件并行开发过程

软件并行开发过程第1页，共52页，2023年，2月20日，星期日云南省中青年学术和技术带头人培养基金项目1998-37云南省自然科学基金项目

98F023M98F005G2001F0006M第2页，共52页，2023年，2月20日，星期日问题的提出

一、生产率低下二、质量欠佳第3页，共52页，2023年，2月20日，星期日背景并行工程并行处理多个程序员同时为同一个系统编码现实生活中的各类非自觉的、偶然的并行行为第4页，共52页，2023年，2月20日，星期日制造业并行工程市场分析产品设计工艺设计采购制造检测装配销售维修并行度进行反馈产品生存周期第5页，共52页，2023年，2月20日，星期日

1982年，美国国防部发表了著名的R-338报告，正式提出了“并行工程”的概念：并行工程是集成地、并行地设计产品及其相关的各种过程（包括制造过程和支持过程）的系统化方法。这种方法要求产品开发人员从设计一开始就考虑产品整个生存周期中从概念形成到产品报废处理的所有因素，包括质量、成本、进度、计划和用户的要求。并行工程目前已成为制造业研究与实践的热点领域。在国外已成功地应用于航空、航天、电子、汽车等领域，如福特汽车公司、波音公司、洛克希德公司、丰田汽车公司。我国并行工程的研究始于90年代初，国家科委在863计划中设立了一些课题支持并行工程的研究，已有少数几家企业开始实施并行工程，并取得了新产品开发样机周期缩短、产品综合技术经济指标好、符合市场需求、经济效益好等效益。并行工程现状第6页，共52页，2023年，2月20日，星期日

1）并行性：各种活动并行交叉进行。既包括各个部件开发的并行交叉，又包括各个阶段的并行交叉。2）流程改善：通过改善与优化工作流程，提高产品质量。3）尽早开始工作：在信息不充分的情况下开始工作，因此要有很强的应变能力。4）集成化：强调全面优化，追求产品整体的竞争力和各小组的密切有机合作。5）强有力的支撑环境：必须有良好的支撑多小组并行协同工作的网络与计算机平台。6）强有力的管理：强调强有力的管理，保证各种并行活动协调统一地进行。并行工程特点第7页，共52页，2023年，2月20日，星期日

软件过程软件过程指软件生存周期中所涉及的一系列相关过程。过程是活动的集合，活动是任务的集合，任务是把输入转换为输出的操作。软件过程是动态的，它动态地产生、推进（执行），动态地消亡。软件过程模型是对软件过程的静态描述，是软件过程向前推进的依据。第8页，共52页，2023年，2月20日，星期日软件过程-ISO/IEC122071.主要过程类获取过程供应过程开发过程运行过程维护过程

3.组织过程类管理过程基础设施过程改进过程培训过程2.支持过程类

文档编制过程配置管理过程质量保证过程验证过程确认过程联合评审过程审核过程问题解决过程第9页，共52页，2023年，2月20日，星期日过程并行子过程并行阶段并行版本并行活动并行软件生存周期中的并行性第10页，共52页，2023年，2月20日，星期日

软件生存周期并行度软件开发过程软件维护过程软件管理过程软件文档编制过程过程并行第11页，共52页，2023年，2月20日，星期日子过程并行软件开发周期并行度子开发过程1子开发过程2子开发过程n初步需求分析集成与系统测试第12页，共52页，2023年，2月20日，星期日

阶段并行软件开发周期并行度总体设计详细设计编码测试需求分析第13页，共52页，2023年，2月20日，星期日版本并行软件生存周期并行度发行版本1的开发发行版本2的开发……发行版本n的开发第14页，共52页，2023年，2月20日，星期日活动并行

软件生存周期并行度开始编码结束编码编制模块1活动编制模块2活动编制模块n活动第15页，共52页，2023年，2月20日，星期日

SDDM模型

支持软件并行开发过程的软件过程模型：能定义软件开发中的各并行成分、各开发活动及它们相互之间的动态关系（也包括并行关系）。能定义软件过程之间的动态关系。第16页，共52页，2023年，2月20日，星期日任务是一个三元组T=<{P}，{Q}，Ms>，其中{P}，{Q}均为谓词，我们称{P}为前断言，它刻划了任务T执行前的状态；{Q}称为后断言，它刻划了任务T执行后的状态。<{P}，{Q}>刻划了把输入转换为输出的操作。Ms是消息集合，其中的元素是二元组m=<p.a.t，m.text>，表示当任务T完成时向软件过程p的活动a的任务t发送内容为m.text的消息。m.text既可以是一个字符串，也可以是一个可执行的过程第17页，共52页，2023年，2月20日，星期日活动或者是一个任务序列T1T2…Tn，它表示任务T1、T2、...、Tn顺序地执行；或者是一个软件过程。第18页，共52页，2023年，2月20日，星期日软件过程是一个六元组P=<C，A，F，I，O，M>。其中C为条件的集合，C中的条件是一个二元组<{Q},Ds>,{Q}是一个谓词，表示条件；Ds是一个广义数据结构，是活动操作的对象。A是活动的集合。A中的活动a在其前提条件具备的情况下可以执行（称为点火）。但a能否顺利进行，还要看其内部的诸任务的前断言是否具备。C∩A=Φ。F（C×A）∪（A×C），称为流关系。I，OC分别称为输入接口和输出接口。软件过程P将输入接口I的广义数据结构变为输出接口O的广义数据结构。MC称为标记，它记录了过程P的一个瞬态。第19页，共52页，2023年，2月20日，星期日系统动态开发模型是一个二元组SDDM=<Ps，Pr>，Ps是软件过程的集合，Pr={<P，P’>|P，P’∈Ps}称为优先关系集，<P，P’>刻画了软件过程P必须在P’前执行。无优先关系的过程可以并行执行。并行执行过程中的同步关系由软件过程自行发送消息进行控制。C4软件开发过程的图形表示子开发过程1子开发过程2子开发过程n初步需求分析

集成与系统测试初步需求分析子开发过程1子开发过程2子开发过程n集成与系统测试C1A1C2iA2iC3iA3第20页，共52页，2023年，2月20日，星期日

软件过程建模语言特征动态性：由于软件过程是动态进行的，为支持设计者动态操作，应具有描述动态行为的成分。并行性：应具有描述不同粒度并行成分的能力。能描述软件过程级（粗粒度）、活动级（细粒度）的并行行为。一致性：由于软件过程中有多个角色协同工作，应具有描述角色行为和角色协同工作的成分，对角色的行为进行精确的定义，并便于形式化地进行一致性检查。完整性：软件过程包括许多方面的内容，建模语言应对其中组织、功能、行为、信息诸方面的内容加以描述，提供和表达尽可能丰富的信息。模块性：L.Osterweil提出过“软件过程也是软件”的观点并获得了广泛的认同，软件过程模型是程序。因此，模块性是自然的要求。支持抽象与求精：软件过程建模可采用自顶向下、逐步求精的方法进行。应支持不同抽象级的过程描述，并具有用低层详细描述替换高层抽象描述的手段。第21页，共52页，2023年，2月20日，星期日基于Petri网，具有较好的并行表达能力和动态表达能力，便于并行控制。具有面向对象的特征，支持数据抽象、信息隐蔽和过程抽象，支持消息传递和单重继承。能表达各软件过程、子开发过程、活动之间的关系，能定义角色与活动之间的关系。可表示不同抽象级的过程模型，支持以角色为中心的逐步求精的过程建模方法。一个软件过程模型就是一个SDDML程序。支持模型重用和过程重用。

SDDML主要特征第22页，共52页，2023年，2月20日，星期日

任务定义<任务>::=TASK<任务名>{<消息定义>;}BEGIN<前断言>;<后断言>;{<消息发送>;}END;<前断言>::=PREASSERTION<谓词表达式><后断言>::=POSTASSERTION<谓词表达式><谓词表达式>::=<简单布尔表达式>|(<谓词表达式>)|NOT<谓词表达式>|<谓词表达式>AND<谓词表达式>|<谓词表达式>OR<谓词表达式>|<谓词表达式>IMPLY<谓词表达式>|<谓词表达式>IFF<谓词表达式>|COND(<谓词表达式>,<谓词表达式>,<谓词表达式>)|ALL(<变量名>)(<谓词表达式>)|EXISTS(<变量名>)(<谓词表达式>)<消息定义>::=MESSAGE<消息名>BEGIN<消息内容>END<消息发送>::=SEND<消息名>TO<目标><目标>::=<软件过程名>.<活动名>.<任务名>|<软件过程名>.<条件名>

第23页，共52页，2023年，2月20日，星期日

活动定义<活动>::=ACTIVITY<活动名>[FROM<活动名>]{<任务>}[IMPORTS<输入数据结构>;][EXPORTS<输出数据结构>;][LOCALS<局部数据结构>;]BEGIN<活动体>END;<活动体>::=<任务序列>|<软件过程名><输入数据结构>::=<广义数据结构><输出数据结构>::=<广义数据结构><局部数据结构>::=<广义数据结构><广义数据结构>::=STRUCTURE<广义数据结构名>BEGIN<变量名>:<变量类型>{;<变量名>:<变量类型>}END<任务序列>::=PERFORMEDBY<层次>.<角色名>:<任务名>{;<任务名>}<角色名>::=PD|PM|SA|DR|PR|CP|MA|GL|<用户自定义角色名>

第24页，共52页，2023年，2月20日，星期日<软件过程>::=PROCESS<软件过程名>[FROM<软件过程名>]{<活动>}BEGIN[<条件集定义>;][<活动集定义>;][<弧集定义>]END;<条件集定义>::=CONDITIONSETBEGIN<条件名>{;<条件名>}END<活动集定义>::=ACTIVITYSETBEGIN<活动名>{;<活动名>}END<弧集定义>::=ARCSETBEGIN<弧元素>{;<弧元素>}END<弧元素>::=(<条件名>,<活动名>)|(<活动名>,<条件名>)软件过程定义第25页，共52页，2023年，2月20日，星期日

系统动态开发模型

<系统动态开发模型>::={#define<术语定义>;}SDDM<SDDM模型名>[FROM<SDDM模型名>]{<软件过程>}BEGIN[<软件过程优先集>;][<初始标记>]END.<软件过程优先集>::=PROCESSPRIORITYSETBEGIN(<软件过程名>,<软件过程名){;(<软件过程名>,<软件过程名)}END<初始标记>::=MARKINGSETBEGIN<软件过程名>.<条件名>{;<软件过程名>.<条件名>}END<术语定义>::=<标识符>:<字符串>

第26页，共52页，2023年，2月20日，星期日

并行度软件生存周期初步需求分析子开发过程1子开发过程2子开发过程n集成与系统测试软件开发过程DPd1

d2d31~d3nd41~d4nd51~d5nd6d7维护需求分析维护活动测试软件维护过程MPm1m3m5m7m6m4m2启动开发成本管理过程管理配置管理结束开发问题定义角色管理启动维护维护管理结束维护软件管理过程MGPc12c1c2c3c4c51~c54c61~c64c71~c74c8c9c10c15c13c14c11SDDM模型第27页，共52页，2023年，2月20日，星期日#defined2:初步需求分析;/*将术语“初步需求分析”符号化*/#defined41:子开发过程1;/*将术语“子开发过程1”符号化*/……#definec14:结束维护;/*将术语“结束维护”符号化*/SDDMsample1PROCESSDP/*定义软件开发过程DP*/ACTIVITYd2…;/*定义活动d2中任务、数据结构等*/ACTIVITYd41…;/*定义活动d41中任务、数据结构等*/……ACTIVITYd6…;/*定义活动d6中任务、数据结构等*/BEGINCONDITIONSETBEGINd1;d31;…;d3n;d51;…;d5n;d7END;/*DP中条件(圆圈)集*/ACTIVITYSETBEGINd2;d41;…;d4n;d6END;/*DP中活动(方框)集*/ARCSETBEGIN(d1,d2);(d2,d31);…;(d2,d3n);…;(d6,d7)END/*DP中弧(箭头)集*/END;/*EndofPROCESSDP*/PROCESSMP…;/*定义软件维护过程MP*/PROCESSMGP…;/*定义软件管理过程MGP*/BEGINPROCESSPRIORITYSETBEGIN(DP,MP)END;/*DP必须在MP前启动*/MARKINGSETBEGINMGP.c1END/*初始标记为仅有MGP中的条件c1一个元素的集合*/END./*EndofSDDMsample1SDDML程序第28页，共52页，2023年，2月20日，星期日

基于SDDML的过程建模方法PROCEDUREProcess_Modeling;PROCEDUREProcess_Refining(p:process;i:integer);BEGIN

在p所应该涉及的范围内标识第i层角色，这些角色构成集合Ri;

分析Ri中角色所处理的广义数据结构、活动、任务及它们与外界的联系（消息）;

根据Ri中角色所处理的内容用SDDML定义活动（每一个角色定义一个活动）;

分析Ri中角色所实施的活动之间的关系;

根据Ri中角色所实施的活动及它们之间的关系用SDDML定义软件过程p;IFi<>0THEN验证软件过程p同第i-1层软件过程之间的一致性;IF软件过程p中还有需要细化的活动THENBEGIN

将每一个需要细化的活动标识为一个软件过程，这些软件过程构成集合Si;FORSi中的每一个软件过程piDOProcess_Refining(pi,i+1)END;

利用继承机制定义细化后的系统动态开发模型，用以说明第i-1层中需细化的活动在第i层中已被软件过程p所替代

END;/*EndofProcess_Refining*/BEGIN

标识构成软件过程模型的诸软件过程，这些软件过程构成集合S;

确定S中软件过程之间的优先关系;

根据S中软件过程及它们之间的优先关系，用SDDML定义系统动态开发模型;FORS中的每一个软件过程p’DOProcess_Refining(p’,0)END;/*EndofProcess_Modeling*/第29页，共52页，2023年，2月20日，星期日

基于Petri网、严格形式化，可以精确地描述并行的软件过程和软件过程内部的并行成分。层次化，可用来构造不同抽象级的软件过程，可通过实际的执行来验证不同抽象级的软件过程模型的一致性。可以挖掘软件过程内部的并行性，延拓局部的并行性到全局，提高了软件过程的并行度。SDDM和SDDML第30页，共52页，2023年，2月20日，星期日

相关类型定义：活动相关图是一个三元组ARG=<V，D，R>。V≠Φ，为活动节点集，其中元素称为活动。DV×V，为有向边集，其中元素称为有向边。R：D→{δ，δ，δo，δc}，称为相关函数。定义：活动A的输入数据集记为input(A)，输出数据集记为output(A)。除input(A)和output(A)外，其它数据均认为局部于活动A。第31页，共52页，2023年，2月20日，星期日

相关类型定义：在活动相关图ARG=<V，D，R>中，对A1，A2∈V，A1在A2之前进行：（1）若output(A1)∩input(A2)≠Φ，则称A1正相关于A2，记为A1δA2，δ为正相关类型。（2）若output(A2)∩input(A1)≠Φ，则称A1反相关于A2，记为A1δA2，为反相关类型。（3）若output(A1)∩output(A2)≠Φ，则称A1输出相关于A2，记为A1δoA2，δo为输出相关类型。定义：在活动相关图ARG=<V，D，R>中，对A1，A2∈V，若A2进行与否取决于A1的进行结果，则称A1控制相关于A2，记为A1δcA2，δc为控制相关类型。第32页，共52页，2023年，2月20日，星期日

构造活动相关图算法(构造活动相关图ARG)输入：活动集E={A1，A2，…，An}；input(Ai)，output(Ai)(i=1，2，…，n)；顺序关系S={<Ai，Aj>|Ai在Aj之前进行}；控制关系C={<Ai，Aj>|Ai决定Aj是否进行}。输出：活动相关图ARG=<V，D，R>。BEGINV:=E;D:=Φ;R:=Φ;FORi:=1TOnDOFORj:=1TOnDOBEGINIF<Ai，Aj>∈STHENBEGINIFoutput(Ai)∩input(Aj)≠ΦTHENBEGIND:=D∪{(Ai，Aj)};R:=R∪{<(Ai，Aj)，δ>}END;IFoutput(Aj)∩input(Ai)≠ΦTHENBEGIND:=D∪{(Ai，Aj)};R:=R∪{<(Ai，Aj)，δ>}END;IFoutput(Ai)∩output(Aj)≠ΦTHENBEGIND:=D∪{(Ai，Aj)};R:=R∪{<(Ai，Aj)，δo>}ENDEND;IF<Ai，Aj>∈CTHENBEGIND:=D∪{(Ai，Aj)};R:=R∪{<(Ai，Aj)，δc>}ENDENDEND.第33页，共52页，2023年，2月20日，星期日

构造软件过程模型算法(构造软件过程模型P)输入：活动相关图ARG=<V，D，R>。输出：软件过程模型P=<C，E，F，M>。BEGINE:=V;C:=Φ;F:=Φ;M:=Φ;FORi:=1TOnDO/*n为V、E中的节点数*/FORj:=1TOnDOBEGINIF((Vi，Vj)∈D)∧(R(Vi，Vj)≠δc)THEN/*Vi，Vj∈V且Vi，Vj∈E*/BEGINC:=C∪{Cij};F:=F∪{(Vi，Cij)，(Cij，Vj)}END;IF((Vi，Vj)∈D)∧(R(Vi，Vj)=δc)THENBEGINC:=C∪{Ci};F:=F∪{(Vi，Ci)，(Ci，Vj)}ENDEND;FORi:=1TOnDOBEGINIFVi·=ФTHENBEGINC:=C∪{Ci”};F:=F∪{(Vi，Ci”)}END;IF·Vi=ФTHENBEGINC:=C∪{Ci’};F:=F∪{(Ci’，Vi)};M:=M∪{Ci’}ENDENDEND.第34页，共52页，2023年，2月20日，星期日

并行性挖掘rr(a)A1A2(b)V1V2分解活动前后的活动相关图V3V4V5V6活动相关图构造的软件过程模型C23C12C45C25C1’●V1V2V3C3”C4’●V4V5V6C56C6”第35页，共52页，2023年，2月20日，星期日

C4C1’C51”C3”C23●A1A2A4A3A5A6活动相关图构造的软件过程模型C12C14C6”cc/oA1A2A3A4A5A6活动相关图第36页，共52页，2023年，2月20日，星期日

活动并行化算法（将活动A并行化）输入：活动A，A的前流FIRST(A)，A的后流FOLLOW(A)。输出：软件过程模型P=<C，E，F>。BEGIN

构造A中任务的相关图TRG；由TRG构造A中任务的相关关系R；构造A的任务集合T关于R的商集T/R,得划分块的集合{Tb1，Tb2，…，Tbn}；将每一个划分块定义为一个新活动，新活动中不改变原任务进行的顺序，得活动集Ab={A1，A2，…，An}；/*Ab中每一个元素为一个任务序列*/E:=Ab∪{A’，A”}；F:=Φ；

C:={C1’，C2’，…，Cn’，C1”，C2”，…，Cn”}；

FORi:=1TOnDOF:=F∪{(A’，Ci’)，(Ci”，A”)，(Ci’，Ai)，(Ai，Ci”)}；

F:=F∪FIRST(A’/A)∪FOLLOW(A”/A)END.第37页，共52页，2023年，2月20日，星期日

(a)C’ABA’A1A2AnC’A”B’B1B2BmB”(b)活动并行化第38页，共52页，2023年，2月20日，星期日

划分块之间的相关关系判别算法（划分块之间的相关关系判别）输入：活动集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)。输出：表明划分块之间是否相关的二维数组AB，划分Ab，Bb。BEGIN构造A关于RA的商集A/RA，得划分Ab={Ab1，Ab2，…，Abs}；构造B关于RB的商集B/RB，得划分Bb={Bb1，Bb2，…，Bbt}；AB[1..s，1..t]:=false；FORi:=1TOsDOFORj:=1TOtDOFORi’:=1TOsiDO/*块Abi中有si个活动*/FORj’:=1TOtjDO/*块Bbj中有tj个活动*/BEGIN

判别Abii’，Bbjj’之间的相关关系；/*Abii’∈Abi，Bbjj’∈Bbj*/IFAbii’与Bbjj’

相关THENAB[i，j]:=trueENDEND.第39页，共52页，2023年，2月20日，星期日

算法（并行性延拓）输入：软件过程模型~P=<~C,~E,~F>；活动集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=<C，E，F>。BEGINCALL划分块之间的相关关系判别算法获得布尔数组AB及划分Ab，Bb；

E:=~E-{A”，B’}；C:=~C-{C’}；

F:=~F-FIRST(A”)-FIRST(B’)-FOLLOW(A”)-FOLLOW(B’)；

FORi:=1TOsDO/*Ab中有s个划分块*/BEGINFORj:=1TOtDO/*Bb中有t个划分块*/IFAB[i，j]THENBEGINE:=E∪{Bj’，Ai”}；

C:=C∪{Cij}；

FORj’:=1TOtjDO/*块Bbj中有tj个活动：Bj1，Bj2，…*/F:=F∪{(Bj’，FCjj’)}；/*FCjj’为指向Bjj’的条件*/F:=F∪{(Ai”，Cij)，(Cij，Bj’)}；

FORi’:=1TOsiDO/*块Abi中有si个活动：Ai1，Ai2，…*/F:=F∪{(LCii’，Ai”)}/*LCii’表示Aii’所指向的条件*/END;IFAB第i行均为falseTHEN/*Ab第i块不同Bb中任何一块有相关关系*/FORi’:=1TOsiDOF:=F∪{(LCii’，B”)}END;FORj:=1TOtDOIFAB第j列均为falseTHEN/*Ab中不存在任何一块与Bb中第j块有相关关系*/FORj’:=1TOtjDOF:=F∪{(A’，FCjj’)}END.第40页，共52页，2023年，2月20日，星期日

A’A21A22A2bA2”B2’B21B22B2dB”A11A12A1aA1”B1’B11B12B1cAk1Ak2AkjAk”Bk’Bk1Bk2Bkm并行性延拓第41页，共52页，2023年，2月20日，星期日

并行控制模型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页，2023年，2月20日，星期日

串行块eiej第43页，共52页，2023年，2月20日，星期日

并行块eiej第44页，共52页，2023年，2月20日，星期日

互斥块ejei第45页，共52页，2023年，2月20日，星期日

同步块eje0enei第46页，共52页，2023年，2月20日，星期日

重复块ei