一种新的异构多核平台下多类型DAG调度方法.pdfVIP

第４２卷第２期计算机应用研究Ｖｏｌ４２Ｎｏ２

２０２５年２月ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓＦｅｂ．２０２５

一种新的异构多核平台下多类型ＤＡＧ调度方法



左俊杰，肖锋，黄姝娟，沈超，郝鹏涛，陈磊

（西安工业大学计算机科学与工程学院，西安７１００２１）

摘要：异构多核处理器在异构环境中受限于处理器种类，只能在特定处理器上执行。现有调度方法通常使用

多类型ＤＡＧ（ｄｉｒｅｃｔｅｄａｃｙｃｌｉｃｇｒａｐｈ）任务模型进行模拟，但调度方法往往忽略不同核上的通信开销，或未考虑处

理器与节点的对应关系，导致调度时间开销较大，处理器资源未充分利用，任务效率低。针对上述问题，提出了

ＰＮＩＦ（ｐｒｏｃｅｓｓｏｒｎｏｄｅｉｍｐａｃｔｆａｃｔｏｒ）算法。该算法引入了两个对节点优先级具有重大影响的比例因子，将它们加

入到节点优先级的计算中从而确定任务执行顺序。实验结果表明，ＰＮＩＦ比ＰＥＦＴ、ＨＥＦＴ、ＣＰＯＰ在调度长度上分

别平均提升５．９０２％、１９．４０２％、２５．８３１％，有效缩短了整体调度长度，提升了处理器资源利用率。

关键词：异构多核处理器；多类型ＤＡＧ任务；任务调度；影响因子；ＰＮＩＦ算法

中图分类号：ＴＰ３９１文献标志码：Ａ文章编号：１００１３６９５（２０２５）０２０２６０５１４０５

ｄｏｉ：１０．１９７３４／ｊ．ｉｓｓｎ．１００１３６９５．２０２４．０５．０２３７

ＮｏｖｅｌｓｃｈｅｄｕｌｉｎｇｍｅｔｈｏｄｆｏｒｍｕｌｔｉｔｙｐｅＤＡＧｏｎｈｅｔｅｒｏｇｅｎｅｏｕｓｍｕｌｔｉｃｏｒｅｐｌａｔｆｏｒｍｓ



ＺｕｏＪｕｎｊｉｅ，ＸｉａｏＦｅｎｇ，ＨｕａｎｇＳｈｕｊｕａｎ，ＳｈｅｎＣｈａｏ，ＨａｏＰｅｎｇｔａｏ，ＣｈｅｎＬｅｉ

（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉ’ａｎＴｅｃｈｎｏｌｏｇｉｃａｌＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ７１００２１，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｉｎａｈｅｔｅｒｏｇｅｎｅｏｕｓｅｎｖｉｒｏｎｍｅｎｔ，ｈｅｔｅｒｏｇｅｎｅｏｕｓｍｕｌｔｉｃｏｒｅｐｒｏｃｅｓｓｏｒｓａｒｅｌｉｍｉｔｅｄｔｏｐｒｏｃｅｓｓｏｒｔｙｐｅｓａｎｄｃａｎｏｎｌｙｅｘｅ

ｃｕｔｅｏｎｓｐｅｃｉｆｉｃｐｒｏｃｅｓｓｏｒｓ．ＴｈｅｅｘｉｓｔｉｎｇｓｃｈｅｄｕｌｉｎｇｍｅｔｈｏｄｓｕｓｕａｌｌｙｕｓｅｔｈｅＤＡＧｔａｓｋｍｏｄｅｌｔｏｓｉｍｕｌａｔｅ，ｂｕｔｔｈｅｙｏｆｔｅｎｉｇｎｏｒｅ

ｔｈｅｃｏｍｍｕｎｉｃａｔｉｏｎｏｖｅｒｈｅａｄｏｎｄｉｆｆｅｒｅｎｔｃｏｒｅｓ，ｏｒｄｏｎｏｔｃｏｎｓｉｄｅｒｔｈｅｃｏｒｒｅｓｐｏｎｄｉｎｇｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎｐｒｏｃｅｓｓｏｒｓａｎｄ

ｎｏｄｅｓ，ｗｈｉｃｈｌｅａｄｓｔｏｌａｒｇｅｓｃｈｅｄｕｌｉｎｇｔｉｍｅｏｖｅｒｈｅａｄ，ｕｎｄｅｒｕｔｉｌｉｚａｔｉｏｎｏｆｐｒｏｃｅｓｓｏｒｒｅｓｏｕｒｃｅｓ，ａｎｄｌｏｗｔａｓｋｅｆｆｉｃｉｅｎｃｙ．Ｔｈｉｓｐａ

ｐｅｒｐｒｏｐｏｓｅｄＰＮＩＦ（ｐｒｏｃｅｓｓｏｒｎｏｄｅｉｍｐａｃｔｆａｃｔｏｒ）ａｌｇｏｒｉｔｈｍｔｏｓｏｌｖｅｔｈｅａｂｏｖｅｐｒｏｂｌｅｍｓ．Ｔｈｅａｌｇｏｒｉｔｈｍｉｎｔｒｏｄｕｃｅｄｔｗｏｓｃａｌｅ

ｆａｃｔｏｒｓｗｈｉｃｈｈａｄａｓｉｇｎｉｆｉｃａｎｔｉｍｐａｃｔｏｎｔｈｅｐｒｉｏｒｉｔｙｏｆｔｈｅｎｏｄｅ，ａｎｄａｄｄｅｄｔｈｅｍｔｏｔｈｅｃａｌｃｕｌａｔｉｏｎｏｆｔｈｅｎｏｄｅｐｒｉｏｒｉｔｙｔｏ

ｄｅｔｅｒｍｉｎｅｔｈｅｔａｓｋｅｘｅｃｕｔｉｏｎｏｒｄｅｒ．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｃｏｍｐａｒｅｄｗｉｔｈＰＥＦＴ，ＨＥＦＴａｎｄＣＰＯＰ，ＰＮＩＦｉｎｃｒｅａｓｅｓｔｈｅ

ｓｃｈｅｄｕｌｅｌｅｎｇｔｈｂｙ５．９０２％，１９．４０２％ａ