[发明专利]大规模异构计算系统中任务计算量具有随机性的调度方法

摘要

本发明针对大规模异构计算系统环境下任务执行时间具有随机性及优先约束依赖关系，提出了一种高效的任务调度方法。该方法主要由以下几步构成：第一步，针对应用程序的每个任务，计算其随机sb_level值；第二步，对已就绪任务队列中的每个任务查找最优处理机，并计算每对任务－处理机的随机动态级SDL；第三步：利用操作算子＜比较随机动态级SDL的大小，确定最优任务－处理机对；第四步：将任务调度到相应的处理机上执行，并把已就绪的任务加入就绪任务队列；第五步：更新目标计算系统的相关参数。采用该方法，较之现有面向异构计算系统的调度方法相比具有调度长度短、加速比高等性能优势。

主权项

一种大规模异构计算系统中任务计算量具有随机性的调度方法，其特征在于，包括如下步骤：第一步，对运行在大规模异构计算系统环境下所有服从正态分布的随机有向无环并行应用程序，求就绪任务队列中任务v_x到出口任务v_exit的随机近似路径长度sb_level(v_x)，其中sb_level(v_x)为：$sb\_level\left(v_x\right)={\mathrm{MAX}}_{e_{x,i}\∈E,v_i\∈succ\left(v_x\right)}\{w\left(e_{x,i}\right)+sb\_level\left(v_i\right)\}+\frac{w\left(v_x\right)}{\stackrel{\‾}{w\left(p\right)}},$其中e_x,i表示任务间的数据通信量，v_x，v_i是任务节点，且任务v_x是任务v_i具有优先约束性的前驱任务，E为所有通信边集合，succ(v_x)为任务v_x的直接后继任务集，w(v_x)表示任务节点v_x的计算需求，w(e_x,i)表示通信边e_x,i的通信需求，是计算系统平均计算能力；对于出口任务v_exit，$sb\_level\left(v_{exit}\right)=\frac{N({\mathrm{\μ}}_{exit},{\mathrm{\σ}}_{exit}^2)}{\stackrel{\‾}{w\left(p\right)}};$其中sb_level(v_exit)为任务v_exit本身的随机近似路径长度，是任务v_exit服从正态分布的计算量；第二步，为了给已就绪任务队列中的每个任务查找最优处理机，将就绪任务队列中的每个任务都分别与所有的处理机逐一配对，并计算由此产生的每对任务－处理机的随机动态级SDL，其任务－处理机对的随机动态级SDL为：SDL(v_i,p_x)＝sb_level(v_i)‑EST(v_i,p_x)+Δ(v_i,p_x)；其中EST(v_i,p_x)是任务v_i在处理机p_x上的最早开始执行时间，Δ(v_i,p_x)代表计算资源的差异性；第三步：将第二步中所得到的SDL(v_i,p_x)进行比较，以获得最优任务－处理机对；比较随机动态级SDL的大小是利用操作算子＜来实现，操作算子＜的实现方法是对任意两个服从正态分布的随机动态级SDL(X₁)和SDL(X₂)，当x＝x₁时，随机动态级SDL(X₁)的累积分布函数F(SDL(X₁))＝0.9；x＝x₂时，随机动态级SDL(X₂)的累积分布函数F(SDL(X₂))＝0.9，则操作算子＜计算如下：$SDL\left(X_1\right)\<SDL\left(X_2\right)=\left\{\begin{array}{cc}SDL\left(X_2\right),& for{x}_1\<x_2\\ SDL\left(X_1\right),& otherwise\end{array}\right.$其中x是自变量，x₁是x定义域上的点，x₂是x定义域上的另一点；第四步：将最优任务－处理机对的任务调度到相应的处理机上执行；在任务调度后，若还有原来受此任务约束的任务，则将这些任务变为就绪任务，再将这些变为就绪任务的任务加入就绪任务队列；第五步：检查就绪任务队列中所有任务是否调度完毕，如果调度完毕则输出任务－处理机对序列；否则更新目标计算系统的参数，并返回第二步重新计算所有就绪任务－处理机对的SDL(v_i,p_x)，这样循环执行第二、三、四、五步直至就绪任务队列中所有任务均调度完毕。