期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

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

Complexity Analysis of Task Assignment Problem on Multi-Core Clusters
下载PDF
导出
摘要 传统任务分配问题通常以最小化计算代价和节点间通信代价的总代价为研究目标.在多核集群系统中,需要同时考虑节点内冲突代价.本文研究了以最小化计算代价、节点间通信代价和节点内冲突代价的总代价为目标的多核集群任务分配问题.通过建立任务分配问题与最小费用流问题的等价关系来分析节点内冲突代价对问题复杂性的影响关系.结果表明冲突代价成为影响问题复杂性的一个重要因素,给出并证明了冲突代价和节点间通信代价对问题复杂性的影响关系.最后,进一步讨论了各种复杂性下的多核集群任务分配问题的解法以及本文定理与结论的可应用性与有效性. 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
分类号 TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献21

  • 1Mcknight G,Carman G.Energy absorption and damp-ing in magnetostrictive composites[J].Materials for Smart Systems, Materials Research Society Symposium,2000,604:267-272.
  • 2Mcknight G,Carman G.[112] Oriented Terfenol-D composites[J].Materials Transactions,2002,43(5):1008-1014.
  • 3Mcknight G,Carman G.Large Magnetostriction in Or-iented Particle Terfenol-D Composites[C].Proceedings of the ASME International Mechanical Engineering Congress and Exposition[M].2001.1-6.
  • 4Pasquale M,Lim S.High frequency magnetic proper-ties of polymer-bonded Terfenol-D composites[J].J Appl Phys,1999,85(8):4633-4635.
  • 5Sandlund L,Fahlander M,Cedell T,et al.Magnetostr-iction,elastic moduli,and coupling factors of composite Terfenol-D[J].J Appl Phys,1994,75(10): 5656-5658.
  • 6Ruiz de Angulo L,Abell J,Harris I.Magnetostrictive properties of polymer bonded Terfenol-D [J]. Journal of Magnetism and Magnetic Materials, 1996,157-158:508-509.
  • 7杨际祥,谭国真,王荣生.多核软件的几个关键问题及其研究进展[J].电子学报,2010,38(9):2140-2146. 被引量：17
  • 8Mcknight G.[112]Oriented Terfenol-D composites[D].University of California: Los Angeles,2002.
  • 9涂碧波,邹铭,詹剑锋,赵晓芳,樊建平.多核处理器机群Memory层次化并行计算模型研究[J].计算机学报,2008,31(11):1948-1955. 被引量：16
  • 10杨际祥,谭国真,王荣生.并行与分布式计算动态负载均衡策略综述[J].电子学报,2010,38(5):1122-1130. 被引量：43

二级参考文献46

  • 1杨学军,窦勇,胡庆丰.Progress and Challenges in High Performance Computer Technology[J].Journal of Computer Science & Technology,2006,21(5):674-681. 被引量：7
  • 2Hwang Kai著,王鼎兴等译.高等计算机系统结构--并行性、可扩展性、可编程性.北京:清华大学出版社,1995
  • 3Zhang Yun-Quan, Chen Guo-Liang, Sun Guang-Zhong, Miao Qian-Kun. Models of parallel computation: A survey and classification. Frontiers of Computer Science in China, 2007, 1(2): 156-165
  • 4Krste Asanovic, Ras Bodik, Bryan Christopher Catanzaro et al. The landscape of parallel computing research: A view from Berkeley. Electrical Engineering and Computer Sciences, University of California at Berkeley: Technical Report No: UCB/EECS-2006-183, 2006
  • 5Cameron K, Sun X H. Quantifying locality effect in data access delay: Memory LogP//Proceedings of the 2003 IEEE International Parallel and Distributed Processing Symposium (IPDPS'03). Nice, France, 2003:212-219
  • 6Cameron Kirk W, Ge Rong, Sun Xian-He. LognP and Log3P: Accurate analytical models of point-to-point communication in distributed systems. IEEE Transactions on Computers, MARCH 2007, 56(3): 314-327
  • 7Chai Lei, Gao Qi, Panda Dhabaleswar K. Understanding the impact of multi-core architecture in cluster computing: A case study with Intel dual-core system//Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid(CCGrid'07). Rio de Janeiro, Brazil, 2007:471-478
  • 8Alam Sadaf R, Barrett Richard F, Kuehn Jeffery A, Roth Philip C, Vetter Jeffrey S. Characterization of scientific workloads on systems with multi-core processors//Proceedings of the International Symposium on Workload Characterization. Los Alamitos, CA, USA, 2006:225-235
  • 9Kielmann Thilo, Bal Henri E. Fast measurement of LogP parameters for message passing platforms//Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing. Cancun, Mexico, 2000: Lecture Notes in Computer Science, Springer-Verlag, London, UK, 2000: 1176- 1183
  • 10Torsten Hoefler, Andre Lichei, Wolfgang Rehm. Low-overhead LogGP parameter assessment for modern interconnection networks//Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS'07). Long Beach, California, USA, 2007:403-410

共引文献74

同被引文献35

  • 1J Calandrino, J Anderson, D Baumberger. A hybrid real-time scheduling approach for large-scale multi-core platforms[ A]. Proceedings of the 19th Euromicro Conference on Real-Time Systems[C]. USA: IEEE Press,2007.247 - 258.
  • 2P Puschner, C Koza. Calculating the maximum execution time of real-time program[J]. Real-time Systems, 1989,1(2) : 159 - 176.
  • 3C Liu, A Sivasubramaniam, M T Kandemir. Organizing the last line of defense before hitting the memory wall for CMP[ A ]. Proceedings of HPCA[C]. USA: IEEE Press,2004.176 - 185.
  • 4Chen Shimin, Gibbons PhiUip B, Kozuch Michael. Scheduling threads for constructive cache sharing on CMPsE A ]. Proceedings of Annual ACM Symposium on Parallel Algorithms and Architectures[C] .New York: ACM,2007.105- 115.
  • 5M Paolieri et al. Hardware support for WCET analysis of hard real-time multicore systems[ A]. Proceedings of the 36th Annual International Symposium on Computer Architecture[C]. NY, USA: ACM Press, 2009.66 - 75.
  • 6A Andrei, P Eles, Z Peng, J Rosen. Predictable implementation of real-time applications on multiprocessor systems-on-chip [A].Proceedings of the 21st International Conference on VLSI Design[C]. USA: IEEE Press,2008. 103110.
  • 7Chattopadhyay, A Roychoudhury, T Mitra. Modeling shared cache and bus in multi-cores for timing analysis[A]. Proceedings of SCOPES[C].NY, USA:ACM Press,2010.57 - 67.
  • 8Fangyuan Chen, Dongsong Zhang, Zhiying Wang. Static analysis of run-time inter-thread interferences in shared cache multi-core architectures based on instruction fetching timing[A]. Proceedings of CSAE[ C ]. USA: IEEE Press, 2011. 208 - 212.
  • 9Lundqvist T, Stenstrom P. Timing anomalies in dynamically scheduled microprocessors [A]. Proceedings of IEEE Real- Time Systems Symposium[ C ]. USA: IEEE Press, 1999.12 - 21.
  • 10Langenbach M, Thesing S, Heckmann R. Pipeline modeling for timing analysis[A]. Proceedings of Static Analysis Symposium[C]. USA: ACM Press, 2002.294 - 309.

引证文献3

二级引证文献11

电子学报
2012年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部