|
|
- 2017
考虑处理机下线时间的可分任务调度优化模型
|
Abstract:
随着科学应用逐渐趋于数据密集型计算，为并行与分布式系统寻求高效的任务调度策略成了研究的热点问题。已有的可分任务调度模型均假设所有处理机都能100%的完成子任务的计算，即处理机在完成任务计算之前一直保持在线状态。实际上，并行与分布式系统中不同处理机的在线时间可能不同。若忽略处理机的在线时间，为其分配的任务量过大，则任务的完成时间可能超出处理机的下线时间，从而造成任务的计算无法按时完成。因此，为处理机分配任务时应充分考虑处理机下线时间的限制。为解决上述问题，该文提出了一种新的考虑处理机下线时间的可分任务调度优化模型，并设计了全局优化遗传算法求解该模型。最后，通过仿真实验结果验证了模型和算法的有效性。
| [1] | VEERAVALLI B, LI X, KO C C. On the influence of start-up costs in scheduling divisible loads on bus networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(12):1288-1305. |
| [2] | MURUGESAN G, CHELLAPPAN C. Multi-source task scheduling in grid computing environment using linear programming[J]. International Journal of Computational Science and Engineering, 2014, 9(1):80-85. |
| [3] | ROSAS C, SIKORA A, JORBA J, et al. Improving performance on data-intensive applications using a load balancing methodology based on divisible load theory[J]. International Journal of Parallel Programming, 2013, 42(1):94-118. |
| [4] | HU M, VEERAVALLI B. Requirement-aware strategies for scheduling real-time divisible loads on clusters[J]. Journal of Parallel and Distributed Computing, 2013, 73(8):1083-1091. |
| [5] | BHARADWAJ V, GHOSE D, MANI V. Optimal sequencing and arrangement in distributed single-level tree networks with communication delays[J]. IEEE Transactions on Parallel and Distributed Systems, 1994, 5(9):968-976. |
| [6] | KIM H J, JEE G I, LEE J G. Optimal load distribution for tree network processors[J]. IEEE Transactions on Aerospace and Electronic Systems, 1996, 32(2):607-612. |
| [7] | BHARDWAJ V, GHOSE D, MANI V, et al. Scheduling divisible loads in parallel and distributed systems[M]. Los Alamitos CA:IEEE Computer Society Press, 1996. |
| [8] | MANI V, GHOSE D. Distributed computation in linear networks:Closed-form solutions[J]. IEEE Transactions on Aerospace and Electronic Systems, 1994, 30(2):471-483. |
| [9] | GHOSE D, MANI V. Distributed computation with communication delays:Asymptotic performance analysis[J]. Journal of Parallel and Distributed Computing, 1994, 23(3):293-305. |
| [10] | SURESH S, MANI V, OMKAR S N. The effect of start-up delays in scheduling divisible loads on bus networks:an alternate approach[J]. Computers & Mathematics with Applications, 2003, 46(10):1545-1557. |
| [11] | LIN W, LIANG C, WANG J Z, et al. Bandwidth aware divisible task scheduling for cloud computing[J]. Software:Practice and Experience, 2014, 44(2):163-174. |
| [12] | HOSEINYFARAHABADY M R, LEE Y C, ZOMAYA A Y. Randomized approximation scheme for resource allocation in hybrid-cloud environment[J]. The Journal of Supercomputing, 2014, 69(2):576-592. |
| [13] | SHI H, WANG W, KWOK N M, et al. Adaptive indexed divisible load theory for wireless sensor network workload allocation[J]. International Journal of Distributed Sensor Networks, 2013(1):1-18. |
| [14] | DAI L, SHEN Z, CHEN T, et al. Analysis and modeling of task scheduling in wireless sensor network based on divisible load theory[J]. International Journal of Communication Systems, 2014, 27(5):721-731. |
| [15] | HU M, VEERAVALLI B. Dynamic scheduling of hybrid real-time tasks on clusters[J]. IEEE Transactions on Computers, 2014, 63(12):2988-2997. |
