| 主权项 |
一种基于DVFS技术的大规模并行任务节能调度方法，其特征在于：所述方法包括以下步骤：(1)任务映射阶段：将所有处理器的初始状态均设为运行在其最高电压和最高频率状态，然后通过计算获得任务映射阶段的有向无环图调度结果的整体执行时间M<sub>HEFT</sub>；(2)任务拉伸阶段：将任务的执行电压和频率进行拉伸优化，在不影响整体性能的情况下降低能耗开销，其中，所述步骤(1)包括以下步骤：(A1)：计算所有任务的平均执行开销；设任务n<sub>i</sub>在处理器p<sub>k</sub>上的执行开销记为w<sub>i,pk</sub>，则该任务在q个处理器上的平均执行开销是该任务在所有处理器上的执行时间的均值，如下式所示：<maths num="0001" id="cmaths0001"><math><![CDATA[<mrow><mover><msub><mi>w</mi><mi>i</mi></msub><mo>‾</mo></mover><mo>=</mo><munderover><mi>Σ</mi><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>q</mi></munderover><msub><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>/</mo><mi>q</mi><mo>;</mo></mrow>]]></math><img file="FDA0000739979180000011.GIF" wi="403" he="187" /></maths>(A2)：计算所有任务的b‑level值，然后按b‑level值的降序顺序将任务压入队列Q；b‑level值是指：通过广度优先算法逆序计算从有向无环图退出节点到当前节点所有路径中最大的路径开销值；(A3)：选择所述队列Q中的第一个任务，设该任务为n<sub>i</sub>，即未被调度的b‑level值最高的任务；(A4)：循环查找所有的处理器<img file="FDA0000739979180000012.GIF" wi="363" he="88" />获得该任务在各个处理器上最早结束时间EFT(n<sub>i</sub>,p<sub>k</sub>)，选择最早结束时间最小的处理器p<sub>k</sub>，将任务n<sub>i</sub>调度到该处理器上执行；所述最早结束时间EFT(n<sub>i</sub>,p<sub>k</sub>)是通过下式得到的：任务n<sub>i</sub>在处理器p<sub>k</sub>的最早结束时间EFT(n<sub>i</sub>,p<sub>k</sub>)＝EST(n<sub>i</sub>,p<sub>k</sub>)+w<sub>i,pk</sub>，其中，EST(n<sub>i</sub>,p<sub>k</sub>)是任务n<sub>i</sub>在处理器p<sub>k</sub>的最早开始时间，<maths num="0002" id="cmaths0002"><math><![CDATA[<mrow><mi>EST</mi><mrow><mo>(</mo><msub><mi>n</mi><mi>i</mi></msub><mo>,</mo><msub><mi>p</mi><mi>k</mi></msub><mo>)</mo></mrow><mo>=</mo><msub><mi>max</mi><mrow><msub><mi>n</mi><mi>j</mi></msub><mo>∈</mo><mi>pred</mi><mrow><mo>(</mo><msub><mi>n</mi><mi>i</mi></msub><mo>)</mo></mrow></mrow></msub><mrow><mo>(</mo><mi>AFT</mi><mrow><mo>(</mo><msub><mi>n</mi><mi>j</mi></msub><mo>)</mo></mrow><mo>+</mo><msub><mi>c</mi><mrow><mi>j</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow><mo>,</mo></mrow>]]></math><img file="FDA0000739979180000021.GIF" wi="1205" he="123" /></maths>其中，AFT(n<sub>i</sub>)为任务n<sub>i</sub>的实际结束时间，n<sub>j</sub>为另外一个任务，c<sub>j,i</sub>为两个任务的通信开销，即每两个存在依赖关系的可执行任务之间的传输时间；pred(n<sub>i</sub>)为该任务的直接前驱任务集合，n<sub>j</sub>为该任务的直接前驱任务集合中的一个任务，<maths num="0003" id="cmaths0003"><math><![CDATA[<mrow><mi>pred</mi><mrow><mo>(</mo><msub><mi>n</mi><mi>i</mi></msub><mo>)</mo></mrow><mo>=</mo><mo>{</mo><msub><mo>∀</mo><msub><mi>n</mi><mi>j</mi></msub></msub><mo>|</mo><mo>∃</mo><mrow><mo>(</mo><msub><mi>n</mi><mi>j</mi></msub><mo>→</mo><msub><mi>n</mi><mi>i</mi></msub><mo>)</mo></mrow><mo>,</mo><msub><mi>n</mi><mi>i</mi></msub><mo>∈</mo><mi>DAG</mi><mo>,</mo><msub><mi>n</mi><mi>j</mi></msub><mo>∈</mo><mi>DAG</mi><mo>}</mo><mo>;</mo></mrow>]]></math><img file="FDA0000739979180000022.GIF" wi="1707" he="146" /></maths>(A5)：将已调度的任务n<sub>i</sub>移出队列Q，然后判断队列Q是否为空，如果是，则转入步骤(A6)，如果否，则返回步骤(A3)；(A6)：计算出任务映射阶段的有向无环图调度结果的整体执行时间M<sub>HEFT</sub>：<maths num="0004" id="cmaths0004"><math><![CDATA[<mrow><msub><mi>M</mi><mi>HEFT</mi></msub><mo>=</mo><mi>max</mi><mo>{</mo><mi>AFT</mi><mrow><mo>(</mo><msub><mi>n</mi><mi>i</mi></msub><mo>)</mo></mrow><mo>|</mo><msub><mo>∀</mo><msub><mi>n</mi><mi>i</mi></msub></msub><mo>∈</mo><mi>DAG</mi><mo>}</mo><mo>.</mo></mrow>]]></math><img file="FDA0000739979180000023.GIF" wi="1376" he="120" /></maths> |
