摘要
传统任务分配问题通常以最小化计算代价和节点间通信代价的总代价为研究目标.在多核集群系统中,需要同时考虑节点内冲突代价.本文研究了以最小化计算代价、节点间通信代价和节点内冲突代价的总代价为目标的多核集群任务分配问题.通过建立任务分配问题与最小费用流问题的等价关系来分析节点内冲突代价对问题复杂性的影响关系.结果表明冲突代价成为影响问题复杂性的一个重要因素,给出并证明了冲突代价和节点间通信代价对问题复杂性的影响关系.最后,进一步讨论了各种复杂性下的多核集群任务分配问题的解法以及本文定理与结论的可应用性与有效性.
Traditional TAP (Task Assignment Problem) is generally to minimize total execution cost and inter-node communcatoion cost. This paper investigates New TAP (NTAP) considering additive conflict cost in emerging mttlfi-core cluster systems.We analyze the complexity of the NTAP with network flow method and conclude that the conflict cost is a key to the complexity of the NTAP, and derromtrate the relationships between the complexity and the two costs including conflict cost and inter-node communication cost.Moreover,the solutions to the NTAP, and the applicability and effectiveness of the theorems and conclusions are also discussed.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2012年第2期241-246,共6页
Acta Electronica Sinica
基金
国家自然科学基金(No.60873256)
中央高校基本科研业务费专项资金(No.DUT11SX09)
关键词
任务分配
复杂度分析
最小费用流
冲突代价
多核集群
task assignment
complexity analysis
minimum cost flow
conflict cost
mtflti-core clusters