一种动态均衡异构计算系统负载的方法

摘要

本发明公布了一种动态均衡异构计算系统负载的方法，目的是解决异构计算系统静态负载平衡方法灵活性差、效率低的问题。技术方案是先进行系统初始化及信息配置；然后为主处理器和加速器各创建一个计算负载队列，并将计算负载队列初始化；接着构建主处理器和加速器状态图，依据主处理器和加速器状态转换图，搜索处理器可工作集，依据异构计算系统实时运行情况，在各处理器间动态均衡调度负载，最后进行负载更新。采用本发明能增强异构系统计算负载均衡的灵活性，提升异构计算系统资源利用率。

主权项

一种动态均衡异构计算系统负载的方法，其特征在于包括以下步骤：第一步、系统初始化及信息配置，具体步骤如下：1.1采用异构计算系统基础软件工具集提供的初始化函数完成异构计算系统初始化；1.2获取主处理器和加速器的配置信息，即，异构系统中主处理器的个数p、每个主处理器拥有的浮点乘累加功能部件的数目m及主频f，加速器的个数p'、每个加速器拥有的浮点乘累加功能部件的数目m'及主频f'；1.3定义主处理器集合P＝{p₀,p₁,…p_i,…,p_m}，其中p_i(0≤i≤m)表示编号为i的主处理器；1.4定义加速器集合P'＝{p'₀,p'₁,…p'_i',…,p'_n}，其中p'_i'(0≤i'≤n)表示编号为i'的加速器；1.5计算主处理器的理论计算峰值R_peak＝p*m*f；1.6计算加速器的理论计算峰值R'_peak＝p'*m'*f'；1.7确定负载划分因子η＝R'_peak/R_peak；第二步、为主处理器和加速器各创建一个计算负载队列，计算负载队列包含头指针和由计算负载编号Tid及Next指针组成的结构体，具体方法如下：2.1定义负载结构体Task，其中包含负载编号Tid和指向下一个结构体的指针Next两个域；2.2创建主处理器负载队列H_Queue；2.3定义指向主处理器负载队列第一个负载的结构体头指针H_Head；2.4初始化H_Head为空(NULL)，负载编号Tid_H＝0；2.5创建加速器负载队列A_Queue；2.6定义指向加速器负载队列第一个负载的结构体头指针A_Head；2.7初始化A_Head为空，负载编号Tid_A＝0；第三步、计算负载队列初始化，具体步骤如下：3.1依据应用程序特征将负载集合T划分为T₁和T₂两个负载子集合，并且满足如下规则：$\left\{\begin{array}{c}{T}_1\cup T_2=T\\ \eta =\mathrm{compt}\left(T_1\right)/\mathrm{compt}\left(T_2\right)\end{array}\right.---\left(1\right)$其中，compt(T_i1)为负载T_i1的计算量，i1＝1,2；3.2将T₁插入队列A_Queue的头部，负载编号Tid_A＝Tid_A+1；3.3定义加速器负载队列当前指针A_Cur，A_Cur＝A_Head，加速器队列当前指针指向加速器队列头指针；3.4将T₂插入队列H_Queue的头部，负载编号Tid_H＝Tid_H+1；3.5定义主处理器计算负载队列当前指针H_Cur，H_Cur＝H_Head，主处理器计算负载队列当前指针指向主处理器队列头指针；第四步、构建主处理器和加速器状态图，定义主处理器和加速器有三种状态：忙即busy、闲即idle、异常即down，其中busy表示主处理器或加速器处于正常工作状态，idle表示主处理器或加速器正常等待工作状态，down表示主处理器或加速器异常不能正常工作；具体方法如下：4.1定义主处理器和加速器状态集合4.2依据异构系统特征和应用程序特征决定负载运行阀值ΔΓ，阀值应大于应用程序计算量与异构系统计算峰值的比值；4.3任取主处理器p_i∈P并且4.4若主处理器p_i已上电并且p_i无负载正在运行，转换p_i状态为idle，若p_i已上电并且p_i上有负载正在运行，转换p_i状态为busy，若p_i无法加电或是无法加载负载或是负载连续运行时间超过阀值ΔΓ，转换p_i状态为down；4.5Ps＝Ps+{p_i}，表示将元素p_i加入到集合Ps；4.6P＝P‑{p_i}，表示将元素p_i从集合P中删除；4.7若集合P不为空，即转4.3，否则，转4.8；4.8任取加速器p'_i'∈P'并且4.9若加速器p'_i'已加电并且p'_i'无负载正在运行，转换p'_i'状态为idle，若p'_i'已加电并且p'_i'上有负载正在运行，转换p'_i'状态为busy，若p'_i'无法加电或是无法加载负载或是负载连续运行时间超过阀值ΔΓ，转换p'_i'状态为down；4.10Ps＝Ps+{p'_i'}，表示将元素p'_i'加入到集合Ps；4.11Ps＝Ps‑{p'_i'}，表示将元素p'_i'从集合Ps中删除；4.12若集合P'不为空，即转4.8，否则，转第五步；第五步、依据主处理器和加速器状态转换图，搜索处理器可工作集，具体方法如下：5.1定义处理器可工作集5.2任取处理器p_s∈Ps；5.3若p_s的状态为idle；转5.4，否则，转5.5；5.4将该处理器加入处理器可工作集合Pwable，即Pwable＝Pwable+{p_s}；5.5Ps＝Ps‑{p_s}；5.6若转5.2；否则，转5.7；5.7若Pwable不为空，即转5.8，否则，转第八步；5.8定义主处理器可工作状态集合5.9定义加速器可工作状态集合5.10任取处理器p_wable∈Pwable；5.11若p_wable∈P，将p_wable加入集合Pw，Pw＝Pw+{p_wable}，否则，将p_wable加入集合P'w，P'w＝P'w+{p_wable}；5.12Pwable＝Pwable‑{p_wable}，表示将处理器p_wable从集合Pwable中删除；5.13若Pwable不为空，即转5.10，否则，转第六步；第六步、依据异构计算系统实时运行情况，在各处理器间动态均衡调度负载，具体方法如下：6.1若加速器可工作集不为空，即，转6.2，否则，转6.12；6.2若A_cur≠NULL，转6.3，处理加速器队列A_Queue，否则，转6.7，处理主处理器队列H_Queue；6.3将加速器队列当前负载，即加速器队列当前指针A_cur指向的负载分派给加速器p'_i'(p'_i'∈P'w)；6.4加速器队列当前指针向后移动指向下一个负载，即，A_Cur＝A_Cur‑＞Next；6.5P'w＝P'w‑{p'_i'}，表示将加速器p'_i'从集合P'w中删除；6.6若A_cur≠NULL，转6.1，否则，转6.7，处理主处理器队列H_Queue；6.7若H_cur≠NULL，转6.8，否则，转第七步，负载更新；6.8将主处理器队列当前负载，即主处理器队列当前指针H_cur指向的负载分派给加速器p'_i'(p'_i'∈P'w)；6.9H_Cur＝H_Cur‑＞Next，主处理器队列当前指针后移指向下一个负载；6.10P'w＝P'w‑{p'_i'}；6.11若H_cur≠NULL，转6.1，否则，转第七步进行负载更新；6.12若主处理器可工作集不为空，转6.13，否则，转第四步，搜索处理器可工作集；6.13若H_cur≠NULL，转6.14，处理主处理器队列H_Queue，否则，转6.18处理加速器队列A_Queue；6.14将主处理器队列当前负载，即主处理器队列当前指针H_cur指向的负载分派给主处理器p_i(p_i∈Pw)；6.15H_Cur＝H_Cur‑＞Next，加速器队列当前指针后移指向下一个负载；6.16Pw＝Pw‑{pi}；6.17若H_cur≠NULL，转6.12，否则，转6.18，处理加速器队列A_Queue；6.18将加速器队列当前负载，即加速器队列当前指针A_cur指向的负载分派给主处理器p_i(p_i∈Pw)；6.19A_Cur＝A_Cur‑＞Next；6.20Pw＝Pw‑{p_i}；6.21若A_cur≠NULL，转6.12，否则，转第七步；第七步、负载更新：7.1依据应用程序特征将待加入的负载集合T'划分为T'₁和T'₂两个计算负载子集合，并且满足如下规则：$\left\{\begin{array}{c}{T^{\prime }}_1\cup {T^{\prime }}_2=T^{\prime }\\ \eta =\mathrm{comp}\left({T^{\prime }}_1\right)/\mathrm{comp}\left({T^{\prime }}_2\right)\end{array}\right.---\left(2\right)$其中，compt(T'_t)为计算负载T'_t的计算量，{t＝1,2}；7.2将T'₁插入队列A_Queue的头部，负载编号Tid_A＝Tid_A+1；7.3A_Cur＝A_Head，加速器队列当前指针指向加速器队列头指针；7.4将T'₂插入队列H_Queue的头部，负载编号Tid_H＝Tid_H+1；7.5H_Cur＝H_Head，主处理器计算负载队列当前指针指向主处理器队列头指针；7.6若H_Cur＝NULL并且A_Cur＝NULL，转第八步，否则，转第四步；第八步、结束。