基于多核系统NoC架构的静态列表调度算法.PDF

第３３卷第４期 计 算 机 应 用 研 究 Ｖｏｌ．３３Ｎｏ．４ ２０１６年４月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ａｐｒ．２０１６ 基于多核系统 ＮｏＣ架构的静态列表调度算法  李东生 ，李　龙，王　骁，高　杨 （电子工程学院，合肥２３００３７） 摘　要：在单芯片多核系统中，ＮｏＣ已成为主流片上通信架构。有效的任务调度是挖掘计算并行性的重要方 法。在经典静态列表调度基础上，针对ＨＥＦＴ算法中节点排序会得出较多的优先级相同节点的问题，提出一种 节点二次排序的调度方法。在边的调度上应用了ＡＬＡＰ原则，改进算法有效提高了调度效果。实验表明，新方 法对ｂｌ、ｂｌｃｏｍｐ、ｂｌｉｏ等节点优先权算法得出的任务列表均有良好的调度效果，适应性较好；对于２ＤＭｅｓｈ同构 ＮｏＣ架构，改进算法对三种节点优先权算法有１．１５倍的平均加速比，最大可有１．２７倍加速比。 关键词：任务调度；静态调度；片上网络；有向无环图 中图分类号：ＴＰ３０２．１　　　文献标志码：Ａ　　　文章编号：１００１３６９５（２０１６）０４１０５４０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１６．０４．０２０ ＳｔａｔｉｃｌｉｓｔｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｆｏｒＮｏＣｉｎＭＰＳＯＣ  ＬｉＤｏｎｇｓｈｅｎｇ，ＬｉＬｏｎｇ，ＷａｎｇＸｉａｏ，ＧａｏＹａｎｇ （ＥｌｅｃｔｒｏｎｉｃＥｎｇｉｎｅｅｒｉｎｇＩｎｓｔｉｔｕｔｅ，Ｈｅｆｅｉ２３００３７，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＮｏＣｂｅｃａｍｅｓｔｈｅｍａｉｎｃｏｍｍｕｎｉｃａｔｉｏｎａｒｃｈｉｔｅｃｔｕｒｅｏｆＭＰＳＯＣｓｙｓｔｅｍ．Ａｓｉｔｓｈａｒｄｗａｒｅｂｅｉｎｇｍａｔｕｒｅ，ｔｈｅｓｃｈｅｄｕ ｌｉｎｇｔｅｃｈｎｏｌｏｇｙｆｏｒＮｏＣｂｅｃｏｍｅｓｔｈｅｋｅｙｆａｃｔｏｒｓｔｏｒｅｓｔｒｉｃｔｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅｍｕｌｔｉｃｏｒｅ．Ｉｔｈａｓｂｅｅｎｂｅｃｏｍｉｎｇｔｈｅｈｏｔ ｐｏｉｎｔｔｏｒｅｓｅａｒｃｈｔｈｅｍｏｒｅａｐｐｒｏｐｒｉａｔｅｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｔｏｍａｋｅｆｕｌｌｐａｒａｌｌｅｌｉｓｍｏｆｍｕｌｔｉｃｏｒｅ．Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆ ｃｌａｓｓｉｃａｌＨＥＦＴａｌｇｏｒｉｔｈｍｄｅｃｒｅａｓｅｄｂｙｍａｎｙｎｏｄｅｓｗｉｔｈｔｈｅｓａｍｅｐｒｉｏｒｉｔｙ，ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｅｄａｎｏｖｅｌｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｔｏ ｇａｉｎｔｈｅｂｅｔｔｅｒｓｃｈｅｄｕｌｉｎｇｒｅｓｕｌｔｂｙｒａｎｋｉｎｇｔｈｏｓｅｓａｍｅｐｒｉｏｒｉｔｙｎｏｄｅｓａｇａｉｎａｎｄａｐｐｌｉｃａｔｉｏｎｏｆｔｈｅｒｕｌｅｏｆＡＬＰＡｉｎｅｄｇｅｓｓｃｈｅ ｄｕｌｉｎｇ．Ｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｈａｓｇｏｏｄａｐｐｌｉｃａｂｉｌｉｔｙｔｏｓｃｈｅｄｕｌｅｌｉｓｔｓｄｅｒｉｖｅｄｆｒｏｍｂｌ、ｂｌｃｏｍｐ、ｂｌｉｏａｎｄａｖａｒｉｅｔｙｏｆｎｏｄｅｐｒｉ ｏｒｉｔｙ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｒｅｓｕｌｔｏｆ２ＤＭｅｓｈＮｏＣｓｈｏｗｓｔｈａｔｔｈｅａｖｅｒａｇｅａｎｄｔｈｅｍａｘｉｍｕｍｓｐｅｅｄｕｐｃｏｍｐａｒｅｄｗｉｔｈｔｈｅＨＥＦＴａｌｇｏ ｒｉｔｈｍｉｓ１．１５ａｎｄ１．２７． Ｋｅｙｗｏｒｄｓ：ｔａｓｋｓｃｈｅｄｕｌｉｎｇ；ｓｔａｔｉｃｓｃｈｅｄｕｌｉｎｇ；ｎｅｔｗｏｒｋｏｎｃｈｉｐ（ＮｏＣ）；ｄｉｒｅｃｔｅｄａｃｙｃｌｉｃｇｒａｐｈ（ＤＡＧ） 点放在一个核上容易拥堵。 ０　引言