Complexity Analysis of Task Assignment Problem on Multi-Core Clusters

TAN Guo-zhen; YANG Ji-xiang; WANG Fan; PAN Dong

doi:10.3969/j.issn.0372-2112.2012.02.006

您当前的位置：

首页 >

文章列表页 >

Complexity Analysis of Task Assignment Problem on Multi-Core Clusters

更新时间：2025-07-16

- Complexity Analysis of Task Assignment Problem on Multi-Core Clusters
- Acta Electronica Sinica Vol. 40, Issue 2, Pages: 241-246(2012)
- 作者机构：
  
  大连理工大学计算机科学与技术学院,辽宁,大连,116024
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2012.02.006
  CLC： TP301
- Published：2012
- 稿件说明：
移动端阅览
TAN Guo-zhen, YANG Ji-xiang, WANG Fan, et al. Complexity Analysis of Task Assignment Problem on Multi-Core Clusters[J]. Acta Electronica Sinica, 2012, 40(2): 241-246.
DOI：

TAN Guo-zhen, YANG Ji-xiang, WANG Fan, et al. Complexity Analysis of Task Assignment Problem on Multi-Core Clusters[J]. Acta Electronica Sinica, 2012, 40(2): 241-246. DOI： 10.3969/j.issn.0372-2112.2012.02.006.

摘要

传统任务分配问题通常以最小化计算代价和节点间通信代价的总代价为研究目标.在多核集群系统中

需要同时考虑节点内冲突代价.本文研究了以最小化计算代价、节点间通信代价和节点内冲突代价的总代价为目标的多核集群任务分配问题.通过建立任务分配问题与最小费用流问题的等价关系来分析节点内冲突代价对问题复杂性的影响关系.结果表明冲突代价成为影响问题复杂性的一个重要因素

给出并证明了冲突代价和节点间通信代价对问题复杂性的影响关系.最后

进一步讨论了各种复杂性下的多核集群任务分配问题的解法以及本文定理与结论的可应用性与有效性.

Abstract

Traditional TAP (Task Assignment Problem) is generally to minimize total execution cost and inter-node communication cost.This paper investigates New TAP (NTAP) considering additive conflict cost in emerging multi-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 demonstrate 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.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰