基于多水平划分法和赋权有向超图的云计算任务调度方法

摘要

本发明涉及一种云计算环境下的基于多水平划分法和赋权有向超图的云计算任务调度方法，其采用赋权有向超图描述任务的资源需求及依赖关系，并生成相应的赋权有向超图文件；然后启动基于多水平划分法的赋权有向超图划分程序，对生成的赋权有向超图进行划分；最后依据赋权有向超图的划分结果构造任务子集，通过MapReduce任务调度模型对其进行映射和调度。采用本发明的基于多水平划分法和赋权有向超图的云计算任务调度方法，不仅仅有效地提高了任务调度的效率，还显著地提高了任务划分的性能，具有较好的实用性。

主权项

一种基于多水平划分法和赋权有向超图的云计算任务调度方法，其特征在于，具体步骤如下：步骤1，类型类度分析，输入云计算环境下用户提交的任务，并对其进行类型和类度的分析，确定任务的并行化程度和特点；步骤2，进程粒度分解，根据用户任务的并行化程度和特点，以及云计算的资源共享分配方式等独特性质，对用户任务按照进程粒度级别进行分解；步骤3，资源特性分析，根据云计算的资源共享分配方式等独特性质，对分解后的任务进行资源特性分析；步骤4，赋权有向超图文件生成，依据对任务资源特性的分析结果，建立描述其资源需求及依赖关系的赋权有向超图模型，并按照改进压缩的文件存储格式保存为赋权有向超图文件；步骤5，赋权有向超图划分，启动基于多水平划分法的赋权有向超图划分程序，读取赋权有向超图文件，采用改进压缩的内存存储格式对赋权有向超图进行存储，对生成的赋权有向超图进行划分，将最终得到的划分结果存储在赋权有向超图划分文件中；步骤6，任务子集构造，在检测到基于多水平划分法的赋权有向超图划分程序完成划分之后，从赋权有向超图划分文件中读取相应的划分结果，依据赋权有向超图的划分结果构造进程级任务子集；步骤7，任务映射调度，通过MapReduce任务调度模型，对基于赋权有向超图优化划分构造的任务子集进行映射和调度，实现在云计算环境中的任务提交与执行，有效地均衡云计算平台的负载和缩短整个任务完成的时间跨度；上述的步骤4中，所述的赋权有向超图的改进压缩的文件存储格式的如下：步骤4.1，文件格式的第1行第1个参数代表着有向赋权超边的数目m，第2个参数代表着赋权结点的数目n；步骤4.2，文件格式的第2行开始到第m+1行的每行代表着一条有向赋权超边的相关信息，第1个数值为有向赋权超边的权值信息，其余数值为有向赋权超边的结点信息，其中每行的最后一个数值代表有向赋权超边的尾端结点信息，且有向赋权超边的源端结点信息处于有向赋权超边的权值信息和尾端结点信息之间；步骤4.3，文件格式的第m+2行开始到第m+n+1行的每行代表着一个赋权结点的权值信息；上述的步骤5中，所述的基于多水平划分法的赋权有向超图划分程序的步骤如下：步骤5.1，读取赋权有向超图文件，采用改进压缩的内存存储格式对赋权有向超图进行存储；步骤5.2，进入到多水平划分法的粗化阶段，采用赋权有向超图的结点匹配程序将当前水平层粗化赋权有向超图的某些结点结合在一起，得到下一水平层的粗化赋权有向超图，重复此过程直到粗化赋权有向超图足够小为止，即得到一个最小赋权有向超图；步骤5.3，进入到多水平划分法的初始划分阶段，运行基于FM方法的赋权有向超图划分程序，得到最小赋权有向超图的初始划分；步骤5.4，多水平划分法优化阶段的离散群智能搜索程序初始化，初始化全体群智能粒子的全局历史最优位置向量和每个群智能粒子的自身位置向量、自身速度向量、自身历史最优位置向量；步骤5.5，进入到多水平划分法的优化阶段，从最小赋权有向超图投影回初始赋权有向超图，在每一水平层的细化赋权有向超图中，采用离散群智能搜索程序对细化赋权有向超图的投影划分进行优化；步骤5.6，进入到平衡阶段，运行基于FM‑EE方法的赋权有向超图划分程序；由于在基于多水平划分法的赋权有向超图划分过程中，可能违背赋权有向超图划分问题的平衡约束条件，因此在基于多水平划分法的赋权有向超图划分所求解的基础上，运行基于FM‑EE方法的赋权有向超图划分方法，使划分解满足平衡约束条件，从而得到赋权有向超图划分问题的划分解；步骤5.7，将最终得到的赋权有向超图划分结果存储在赋权有向超图划分文件中；上述的步骤5.1中，所述的赋权有向超图的改进压缩的内存存储格式如下；步骤5.1.1，使用vwgts数组存储赋权有向超图中结点的权值信息，且vwgts数组的大小为赋权有向超图中的结点个数；步骤5.1.2，使用xadj数组存储每个结点所有邻接有向超边列表的起始位置信息，即第i个结点的终止位置为第i+1个结点的起始位置减1，且xadj数组的大小为赋权有向超图中的结点个数加1，xadj数组最后一个元素用于存放最后一个结点的终止位置；步骤5.1.3，使用adjncy数组存储每个结点所有邻接有向超边的列表信息，第i个结点的邻接有向超边列表存储在adjncy数组中，从adjncy[xadj[i]]到adjncy[xadj[i+1]‑1]；步骤5.1.4，使用eptr数组存储每条有向超边所包含的结点列表的起始位置信息，即第j条有向超边的终止位置为第j+1条有向超边的起始位置减1，且eptr数组的大小为赋权有向超图中的有向超边个数加1，eptr数组最后一个元素用于存放最后一条有向超边的终止位置；步骤5.1.5，使用eind数组存储每条有向超边所包含结点的列表信息，其中每条有向超边的尾端结点只有1个，且每条有向超边尾端结点的所有直接前驱结点都包含在该有向超边的源端子集中；第j条有向超边的结点列表存储在eind数组中，从eind[eptr[j]]到eind[eptr[j+1]‑1]，其中第j条有向超边的源端结点为eind[eptr[j]]到eind[eptr[j+1]‑2]，第j条有向超边的尾端结点为eind[eptr[j+1]‑1]；步骤5.1.6，使用hewgts数组存储有向超边的权值信息，且hewgts数组的大小为赋权有向超图中的有向超边数目；上述的步骤5.2中，所述的当前水平层粗化赋权有向超图的结点匹配程序的步骤如下：步骤5.2.1，标注当前水平层粗化赋权有向超图中所有结点处于未匹配状态；步骤5.2.2，运行赋权有向超图的结点核值计算程序，基于结点属性函数值进行当前水平层粗化赋权有向超图中所有结点的核值求解，并按照结点的核值进行非严格降序排序；步骤5.2.3，按照结点核值的非严格降序访问处于未匹配状态的结点v；如果结点v还有邻接结点未匹配，那么选取处于没有匹配状态的且权值最大的邻接超边的邻接结点u和结点v匹配，且标注这两个结点为匹配状态；如果结点v所有邻接匹配结点处于匹配状态，那么结点v仍处于未匹配状态，在粗化过程中直接拷贝到下一水平层的粗化赋权有向超图中；步骤5.2.4，步骤重复上一步，直至所有结点访问结束；上述的步骤5.2.2中，所述的赋权有向超图的结点核值计算程序的步骤如下：步骤5.2.2.1，计算出所有结点的属性函数值；步骤5.2.2.2，对所有结点的属性函数值进行非严格降序排序；步骤5.2.2.3，按照结点属性函数值的非严格降序次序访问每个结点，计算每个结点的核值；上述的步骤5.2.2.2中，所述的结点属性函数值的非严格降序排序的步骤如下：步骤5.2.2.2.1，根据结点的属性函数值属于在一定范围内的整数，扫描所有结点的属性函数值，统计每一种属性函数值的结点个数，存储在计数辅助数组bin中；步骤5.2.2.2.2，针对每一种属性函数值，借助计数辅助数组bin，计算出在所有结点的属性函数值中，小于该属性函数值的结点个数，存储在位置辅助数组pos中；步骤5.2.2.2.3，扫描所有结点的属性函数值，针对每一个结点的属性函数值，借助位置辅助数组pos，得到该结点的属性函数值在非严格降序排序的次序，并将该次序存储在次序辅助数组vert中；上述的步骤5.2.2.3中，所述的结点v的核值计算的步骤如下：步骤5.2.2.3.1，将结点v的属性函数值作为核值输出；步骤5.2.2.3.2，标记结点v从所在的超边e中删除；步骤5.2.2.3.3，如果超边e删除结点v后，仍包含两个及以上未被标记删除的结点，则超边e仍然存在，否则删除超边e；步骤5.2.2.3.4，重新计算结点v的邻接结点u的属性函数值；步骤5.2.2.3.5，如果邻接结点u的属性函数值大于结点v的属性函数值，更新邻接结点u的属性函数值，并且借助计数辅助数组bin、位置辅助数组pos和次序辅助数组vert的信息，快速更新邻接结点u在所有结点的属性函数值非严格降序排序的次序；否则不更新邻接结点u的属性函数值及其排序的次序；上述的步骤5.4中，所述的离散群智能搜索程序的初始化步骤如下：步骤5.4.1，初始化全体群智能粒子的全局历史最优位置向量，设定全局历史最优位置向量为最小赋权有向超图的初始划分；步骤5.4.2，初始化每个群智能粒子的自身位置向量，遍历每个群智能粒子并设定每个群智能粒子的自身位置向量为最小赋权有向超图的初始划分，即群智能粒子在最小赋权有向超图的每个维度空间的位置；群智能粒子在最小赋权有向超图的某维度空间的位置，代表着该维度空间对应的最小赋权有向超图结点所处划分的结点子集；步骤5.4.3，初始化每个群智能粒子的自身速度向量，遍历每个群智能粒子并在速度阈值范围内，随机给定每个群智能粒子在每个维度空间的速度向量；步骤5.4.4，初始化每个群智能粒子的自身历史最优位置向量，遍历每个群智能粒子并设定每个群智能粒子的自身位置向量为自身历史最优位置向量；上述的步骤5.5中，所述的离散群智能搜索程序的步骤如下：步骤5.5.1，投影每个群智能粒子的自身位置向量，遍历每个群智能粒子并依据每个群智能粒子的上一水平层粗化赋权有向超图的自身位置向量投影到当前水平层的细化赋权有向超图上，得到每个群智能粒子在当前水平层细化赋权有向超图的自身位置向量，即群智能粒子在当前水平层的细化赋权有向超图的每个维度空间的位置；群智能粒子在当前水平层的细化赋权有向超图的某维度空间的位置，代表着该维度空间对应的当前水平层的细化赋权有向超图结点所处划分的结点子集；步骤5.5.2，投影每个群智能粒子的自身速度向量，遍历每个群智能粒子并依据每个群智能粒子的上一水平层粗化赋权有向超图的自身速度向量投影到当前水平层的细化赋权有向超图上，得到每个群智能粒子在当前水平层细化赋权有向超图的自身速度向量，即群智能粒子在当前水平层的细化赋权有向超图的每个维度空间的速度；步骤5.5.3，计算每个群智能粒子的二维辅助数组EDG[n][m]，遍历每个群智能粒子并依据每个群智能粒子的当前水平层细化赋权有向超图的自身位置向量，计算每个群智能粒子的二维辅助数组EDG[n][m]；步骤5.5.4，快速计算每个群智能粒子在当前水平层的细化赋权有向超图的自身位置向量的割切值，遍历每个群智能粒子并依据每个群智能粒子的二维辅助数组EDG[n][m]，快速计算每个群智能粒子在当前水平层的细化赋权有向超图的自身位置向量的割切值；步骤5.5.5，循环初始化，初始化循环计数器COUNT为0；步骤5.5.6，更新每个群智能粒子的自身速度向量，遍历每个群智能粒子并依据每个群智能粒子自身的历史最优位置向量、全体群智能粒子的全局历史最优位置向量，在速度阈值范围内更新自身速度向量；步骤5.5.7，更新每个群智能粒子的自身位置向量和二维辅助数组EDG[n][m]，遍历每个群智能粒子并计算每个群智能粒子自身位置向量和自身速度向量的向量和，更新自身位置向量，进而依据群智能粒子的自身位置向量计算群智能粒子的二维辅助数组EDG[n][m]；步骤5.5.8，快速计算每个群智能粒子的自身位置向量的割切值，遍历每个群智能粒子并依据每个群智能粒子的自身位置向量和二维辅助数组EDG[n][m]，快速计算每个群智能粒子的当前水平层细化赋权有向超图的自身位置向量的割切值；如果该群智能粒子的自身位置向量的割切值小于自身历史最优位置向量的割切值，则更新该群智能粒子的历史最优位置向量为当前的自身位置向量；如果该群智能粒子的自身位置向量的割切值小于全体群智能粒子的全局历史最优位置向量的割切值，则更新全体群智能粒子的全局历史最优位置向量为该群智能粒子当前的自身位置向量；步骤5.5.9，重复步骤5.5.6、5.5.7、5.5.8，直至循环计数器COUNT到达给定的上限；上述的步骤5.5.3和步骤5.5.7中，所述的计算群智能粒子的二维辅助数组EDG[n][m]的步骤如下：步骤5.5.3.1，二维辅助数组EDG[n][m]清零；步骤5.5.3.2，读取eptr数组和eind数组存储的每条超边所包含的结点信息，基于群智能粒子的当前水平层细化赋权有向超图的自身位置向量，计算每条超边在n个划分子集V1…Vn的结点个数，即二维辅助数组EDG[n][m]的两行分别存放m条超边在n个划分子集的结点个数；上述的步骤5.5.4和步骤5.5.8中，所述的快速计算群智能粒子的自身位置向量的割切值的步骤如下：步骤5.5.4.1，划分割切值清零；步骤5.5.4.2，遍历每条超边是否结束，如果访问未结束，即存在超边e未被访问，则转步骤5.5.4.3；否则访问结束，返回划分割切值；步骤5.5.4.3，如果满足EDG[i][e] ≥1的条件1和EDG[j][e]≥1的条件2时，意味着超边e在划分子集Vi和Vj的结点个数都大于等于1，即可判定超边e是两栖边，并将划分割切值累加上当前超边的权值；否则判定超边e不是两栖边，划分割切值不变；步骤5.5.4.4，转步骤5.5.4.2；上述的步骤5.5.6中，所述的群智能粒子的自身速度向量的更新步骤如下：步骤5.5.6.1，计算出群智能粒子的当前自身速度向量与惯性权重参数的乘积；步骤5.5.6.2，计算出群智能粒子的历史最优位置向量和群智能粒子的当前自身位置向量的向量差，再和认知参数相乘；步骤5.5.6.3，计算出全体群智能粒子的全局历史最优位置向量和群智能粒子的当前自身位置向量的向量差，再和社会参数相乘；步骤5.5.6.4，计算出步骤5.5.6.1、步骤5.5.6.2、步骤5.5.6.3得到的三个乘积的向量和，更新群智能粒子的自身速度向量。