多核集群任务分配问题复杂性分析  被引量:3

Complexity Analysis of Task Assignment Problem on Multi-Core Clusters

在线阅读下载全文

作  者:谭国真[1] 杨际祥[1] 王凡[1] 潘东[1] 

机构地区:[1]大连理工大学计算机科学与技术学院,辽宁大连116024

出  处:《电子学报》2012年第2期241-246,共6页Acta Electronica Sinica

基  金:国家自然科学基金(No.60873256);中央高校基本科研业务费专项资金(No.DUT11SX09)

摘  要:传统任务分配问题通常以最小化计算代价和节点间通信代价的总代价为研究目标.在多核集群系统中,需要同时考虑节点内冲突代价.本文研究了以最小化计算代价、节点间通信代价和节点内冲突代价的总代价为目标的多核集群任务分配问题.通过建立任务分配问题与最小费用流问题的等价关系来分析节点内冲突代价对问题复杂性的影响关系.结果表明冲突代价成为影响问题复杂性的一个重要因素,给出并证明了冲突代价和节点间通信代价对问题复杂性的影响关系.最后,进一步讨论了各种复杂性下的多核集群任务分配问题的解法以及本文定理与结论的可应用性与有效性.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.

关 键 词:任务分配 复杂度分析 最小费用流 冲突代价 多核集群 

分 类 号:TP301[自动化与计算机技术—计算机系统结构]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象