试论基于petri网的并行分布计算中的调度问题的研究

《试论基于petri网的并行分布计算中的调度问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP302密级：公开UDC：单位代码：10424学位论文基于Petri网的并行分布计算中的调度问题的研究孔德华申请学位级别：硕士学位专业名称：计算机软件与理论指导教师姓名：吴哲辉职称：教授山东科技大学二〇〇六年五月论文题目：基于Petri网的并行分布计算中的调度问题的研究作者姓名：孔德华入学时间：2003年9月专业名称：计算机软件与理论研究方向：Petri网理论及应用指导教师：吴哲辉职称：教授论文提交日期：2006年5月论文答辩日期：2006年月日授予学位日期：THESTUDYABOUTSCHEDULINGQ

2、UESTIONINPARALLELANDDISTRIBUTEDCOMPUTINGBASEDONPETRINETADissertationsubmittedinfulfillmentoftherequirementsofthedegreeofMASTEROFPHILOSOPHYfromShandongUniversityofScienceandTechnologybyKongDehuaSupervisor:ProfessorWuZhehuiCollegeofInformationScienceandEngineerin

3、gMay2006声明本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。硕士生签名：日期：AFFIRMATIONIdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofMasterofPhilosophyinShandongUniversityofScienceandTechnology,iswhollymy

4、ownworkguidedbymysupervisorunlessreferencedofacknowledge.Thedocumenthasnotbeensubmittedforqualificationatanyotheracademicinstitute.Signature:Date:摘要本文基于Petri网模型对调度问题建模、分析，该方法能够容易地考虑任务调度环境的各种实际限制条件，如共享资源的交替使用，缓冲区的申请与释放，任务之间的先后顺序等；能够容易地监控任务的并发执行的情形；能够容易地把模型和搜索算法结

5、合在一起。本文综合考虑任务的划分、通信的协调和同步几个方面的问题。为了获得低通信延迟和负载平衡的任务调度方案，我们尝试把任务图进行分割，分割的目标是割边集合的权重最小（通信时间最短），分割后各子图的顶点权重和大体相等（负载平衡）。图形分割问题本身也是NP问题，我们采用目前已有的启发式的分割方法，以获得次优解。其具体步骤是用图形分割算法分割任务图，把任务聚族，使得不同族之间任务通讯量最小。根据任务族的划分结果，把同一族任务分配到同一局部环境（同一节点，或高速局域网），并借此建立Petri网模型。对同一族内任务建立Pet

6、ri网模型，求解不考虑任务间通讯的局部最优的任务调度方案。对各任务族Petri网同步合成，通过网的合成及合成后一些性质寻找全局较优的任务调度解。为了缓解状态空间的爆炸问题我们构造同步可达图SRG。同步可达图SRG只是描述Petri网模块间同步变迁发生时的状态的变化，而对于模块内局部变迁的发生引起的状态变化则用局部可达树LRG来描述，由于模块间的交互相对较少，而同一阶段模块内的状态变化又相对独立，无须把它们进行组合，而是分开考虑，这样降低了问题的组合程度。这种方法对于规模较大的任务图Petri网系统可以分块研究，而任意

7、两个模块Petri网的LRG所代表的状态又可以是并发存在的，所以可以并行生成各个LRG。关键词：Petri网，资源控制网，内联子网合成，资源合成网，LRG，SRG，并行分布式调度AbstractSchedulingquestionismodeledandanalysisedbyPetrinetinthispaper.Variousconstraintconditionssuchasshareresourcesbeingusedinturn,bufferbeingrequestedorreleased,theprece

8、denceconstraintsamongtasksbeingabidedbyinschedulingcanbeeasilyconsiderdusingPetrinet.ThesituationaboutparallelexecutionoftaskscanbeeasilysupervisedusingPetrinet.Searchingalg