多核心环境下任务分配的复杂性和求解模型分析
1绪论
1.1研究背景和意义随着集群技术、SMP(SymmetricalMulti-Processing)系统和多核技术的发展，分布式计算在科学研究、工程计算以及商业计算等领域得到了越来越多的应用。并行分布式计算虽然极具发展前景，但同时也提出了大量富于挑战性的课题，任务调度就是其中的一个很重要的问题。任务调度问题是研究如何将一组计算任务合理地或最优化地分配到分布式系统中各处理单元。如果这个问题得不到解决，则有可能导致分布式计算效率低下，更有甚者，有可能造成并行计算效率不如单机计算，乃至计算失败。
任务调度具有广泛的应用基础，除并行计算领域外，任务调度问题还是其他诸多领域中密切关注的问题。例如，网格，云计算，P2P，普适计算，流媒体，交通领域，自动化，系统工程等。因此，从应用角度来说，任务调度问题作为诸多领域共同面对的普遍性问题，具有重要的研究意义。任务可以不受优先关系的约束而相互作用或进行通信，这类任务的调度问题称为任务分配，它是属于略微简化了一点的调度问题。任务分配问题不需要强调任务在分布式系统上的执行次序，在一个或多个处理机组成的分布式系统中，相互作用的任务应尽可能分配到多个处理机上，以充分利用系统资源。处理器】处理器2计算代价图1.1传统任务分配问题传统的任务分配问题主要关心两方面的因素〔’〕，即计算代价与通信代价，在分布式系统中，尤其是松祸合系统中，处理器间通信代价成为影响整个并行计算的瓶颈。Stone}}}(1977)首次在分布式计算领域提出了任务分配问题，并设计了经典的Stone模型，其目标就是最小化计算代价与通信代价之和。传统的任务分配问题研究中所使用的并行计算环境是由单核处理器构建的，如图1.1所示。然而，随着计算机硬件获得了巨大的性能提升，多核处理器成为主流。
截止2007年，高性能计算机Top500中，有20%采用多核处理器，Intel公司的80核处理器预计3年内上市，Tilera公司己经生产出100核的处理器，核的数量预计每两年会翻一翻。在这种情况下，传统的任务分配理论面临前所未有的巨大挑战。1.2传统任务分配问题1.2.1任务调度问题分类调度的目标是通过合理的策略将任务分配到处理器上，以最小化程序完成时间。广义上，任务调度可以分为静态任务调度(StaticScheduling)和动态任务调度(DynamicScheduling)两种形式。并行程序调度作业调度(独立任务)映射与调度(多交互任务)动态调度静态调度任务交互图任务优先图图1.2任务调度问题分类方法Fig.1.2Ataxonomyoftheapproachestotheschedulingproblem静态任务调度:通常是在编译时完成的，并行程序的属性(任务处理时间，通信量，数据依赖，同步需求等)是提前预知的[5,6]。因此，并行程序可以用一个节点和边都带权
参考文献
[1] STONE H S. Multiprocessor scheduling with the aid of network flow algorithms[J]. IEEE Transaction on Software and Engineering, 1977, 3(1):85-93.
[2] LO V M. Heuristic algorithms for task assignment in distributed systems[J].IEEETransaction on Computers, 1988, 37(11):1384-1397.
[3] Multi-core in High Performance Computing[R/OL]. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=1FD53EBFE1C904CEOFBF48226DA169B1?doi二10. 1. 1. 102. 7666&rep=repl&type=pdf,
[4] CHAI L, GAO Q, PANDA D K. Understanding the Impact of Multi-Core Architecture in Cluster Computing:A Case Study with Intel Dual-Core System[C].7th IEEEInternational Symposium on Cluster
[5] CHU W W, LAN M T, HELLERSTEIN J. Estimation of inter module communication (IMC)and its applications in distributed processing systems[J].IEEE Transaction on
[6] GAJSKI D D, PIER J. Essential issues in multiprocessors Systems[J].Computer, IEEEComputer Society Press, 1985, 18(6):9-2 7.
[7] AHMAD I, GHAFOOR A. Semi-distributed load balancing for massively parallel multicomputer systems[J].IEEE Transaction on Software and Engineering, 1991, 17 (10):987-100.
[8] GERASOULIS A, YANG T. On the granularity and clustering of directed acyclic taskgraphs[J].IEEE Transaction on Parallel and Distributed Systems, 1993,4 (6):686-701.
[9] SHEN C C, TSAI W H. A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax Criterion[J].IEEE Transaction onComputers, 1985, 34 (3):197-203.
[10] EFE K. Heuristic models of task assignment scheduling in distributed systems[J]. Computer, 1982, 15 (6):50-56.
[11] KOBROSLY W. Implementation of an optimal task allocation strategy[C].SouthernTier Technical Conference, Proceedings of the 1988 IEEE, 1988:212-219.
[12] AHAMD I, DHODHI M K, GHAFOOR A. Task assignment in distributed computing systems[C].Computers and Communications, IEEE Fourteenth Annual International Phoenix 1995, Conference Proc
摘要 4-5
Abstract 5-6
1 绪论 9-21
1.1 研究背景和意义 9-10
1.2 传统任务分配问题 10-12
1.2.1 任务调度问题分类 10-11
1.2.2 任务分配问题描述 11-12
1.3 传统任务分配问题面临的挑战 12-13
1.4 多核环境任务分配问题的提出 13-15
1.5 相关问题研究现状 15-19
1.5.1 国外研究现状 15-18
1.5.2 国内研究现状 18-19
1.6 本文的工作 19-20
1.7 本文的章节安排 20-21
2 传统任务分配问题与求解模型 21-31
2.1 问题定义和假设 21-22
2.2 任务通信网络模型 22-23
2.2.1 任务交互图模型 22
2.2.2 任务优先图模型 22-23
2.2.3 时变任务交互图模型模型 23
2.3 任务交互图模型的拓扑结构 23-26
2.3.1 树形结构 23-24
2.3.2 部分K树结构 24-25
2.3.3 线阵网络结构 25-26
2.4 经典求解模型 26-30
2.4.1 最小化计算代价与通信代价之和 26-27
2.4.2 最小化通信代价 27-28
2.4.3 最小化计算代价、通信代价和冲突代价之和 28-30
2.5 本章小结 30-31
3 多核环境任务分配问题的NP困难性证明 31-38
3.1 NP复杂性理论 31-33
3.2 0-1任务分配问题的NP完全性 33-36
3.2.1 考虑冲突代价的任务分配问题 33-35
3.2.2 多核环境任务分配问题 35-36
3.3 多核环境任务分配问题的NP困难性 36-37
3.4 本章小结 37-38
4 通信代价对多核环境任务分配问题复杂性的影响 38-49
4.1 节点间和节点内通信代价的计算 38-39
4.2 选取最小费用流问题作为种子问题 39-40
4.3 多核环境任务分配问题的最小费用流模型 40-44
4.3.1 一致代价问题最小费用流模型 40-41
4.3.2 一般代价问题最小费用流模型 41-44
4.4 通信代价对多核任务分配问题复杂性的影响 44-46
4.5 将凹函数转化为带固定费用的凹函数 46-48
4.6 本章小结 48-49