主权项 |
一种基于任务复制与聚簇的并行任务分配方法,其特征在于步骤如下:步骤1:初始化并对子节点无约束类节点进行复制;步骤2:应用DCPEZ过程,依据为聚簇的调度不增加原则,对任务进行聚簇,步骤3:在聚簇关系的基础上对其余可复制节点进行复制;步骤4:重复步骤2,得到最终复制聚簇结果;所述DCPEZ步骤如下:步骤1)初始化每条边均为“未被访问过”;步骤2)扫描此刻的DAG,找出那些至少含有一条未被访问边的关键路径,否则找出那些至少含有一条未被访问边的次关键路径;步骤3)把关键路径上边的权值按降序进行排列;步骤4)从被选择的DCP上挑选一条未被访问的具有最大权值的边,如果这样的边不止一条,那么则按如下的规则选取:如果cij=cki并且tni<tnk,那么选择边eij,把这条边设置为“访问过”的标志;如果把这条边的权值赋为0能够满足如下条件,也就是此赋0操作不会产生另外一条不同的关键路径,它的长度不会等于甚至大于当前关键路径的长度。合并这两个簇;重复此步骤直到此DCP上的所有边都己经访问过;步骤5)对赋0操作产生簇中的多复制节点进行单一化处理;循环执行步骤2)~步骤5),直到DAG上的所有边都已经被访问过;步骤6)检查这些不同的簇,看它们是否还能够进一步合并但不会增加程序的并行执行时间。若合并再进行下单一化处理。 |