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

发布时间：2020-08-05 20:48

【摘要】：本文基于Petri网模型对调度问题建模、分析，该方法能够容易地考虑任务调度环境的各种实际限制条件，如共享资源的交替使用，缓冲区的申请与释放，任务之间的先后顺序等；能够容易地监控任务的并发执行的情形；能够容易地把模型和搜索算法结合在一起。 本文综合考虑任务的划分、通信的协调和同步几个方面的问题。为了获得低通信延迟和负载平衡的任务调度方案，我们尝试把任务图进行分割，分割的目标是割边集合的权重最小(通信时间最短)，分割后各子图的顶点权重和大体相等(负载平衡)。图形分割问题本身也是NP问题，我们采用目前已有的启发式的分割方法，以获得次优解。 其具体步骤是用图形分割算法分割任务图，把任务聚族，使得不同族之间任务通讯量最小。根据任务族的划分结果，把同一族任务分配到同一局部环境(同一节点，或高速局域网)，并借此建立Petri网模型。对同一族内任务建立Petri网模型，求解不考虑任务间通讯的局部最优的任务调度方案。对各任务族Petri网同步合成，通过网的合成及合成后一些性质寻找全局较优的任务调度解。为了缓解状态空间的爆炸问题我们构造同步可达图SRG。同步可达图SRG只是描述Petri网模块间同步变迁发生时的状态的变化，而对于模块内局部变迁的发生引起的状态变化则用局部可达树LRG来描述，由于模块间的交互相对较少，而同一阶段模块内的状态变化又相对独立，无须把它们进行组合，而是分开考虑，这样降低了问题的组合程度。这种方法对于规模较大的任务图Petri网系统可以分块研究，而任意两个模块Petri网的LRG所代表的状态又可以是并发存在的，所以可以并行生成各个LRG。
【学位授予单位】：山东科技大学
【学位级别】：硕士
【学位授予年份】：2006
【分类号】：TP338.6
【图文】：

二((M;7*城:)}}(M几。M几))根据各个状态M的存在时间区间和M包含的元素(任务)画出表示调度方案的Gantt图如图.64所示，图中的粗线把两族任务分开，粗线上方和下方各表示同族任务可以在局部环境内使用多台处理机来处理，在局部环境中不考虑通信开销。图中的数据1一9表示被执行的任务序号，数据10表示任务1向任务3、4、5的通信，

【引证文献】

相关硕士学位论文 前1条

1 田银花;网格任务调度模型及算法的Petri网模型研究[D];山东科技大学;2007年

本文编号：2781857