A Task Scheduling Algorithm for Large Graph Processing Cloud in Computing

您当前的位置：

首页 >

文章列表页 >

A Task Scheduling Algorithm for Large Graph Processing Cloud in Computing

更新时间：2025-07-09

- A Task Scheduling Algorithm for Large Graph Processing Cloud in Computing
- Vol. 46, Issue 12, Pages: 116-122(2012)
- 作者机构：
  
  北京邮电大学网络与交换技术国家重点实验室,北京,10087
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP311
- Online First：10 December 2012，
  
  Published：2012
- 稿件说明：
移动端阅览
A Task Scheduling Algorithm for Large Graph Processing Cloud in Computing[J]. 2012, 46(12): 116-122.
DOI：

A Task Scheduling Algorithm for Large Graph Processing Cloud in Computing[J]. 2012, 46(12): 116-122. DOI：

摘要

针对云计算环境下调度算法必须考虑资源租赁成本的问题

提出一种新的基于粒子群优化的大规模图状数据处理任务调度算法(LGPPSO). 首先

该算法将图状数据处理任务调度方案编码为粒子群中粒子的位置

并利用任务的调度长度和资源租赁成本建立适应度函数来评价当前粒子的优劣程度

然后重新定义粒子群的参数和相关操作

最后在算法的每一次迭代过程中

粒子不断更新自身的速度和位置

以获得任务调度的近似最优解. 模拟实验结果表明:在仅以调度长度为目标时

LGPPSO算法的调度长度比异构最早完成时间任务调度算法(HEFT)平均降低约12.3%; 在以调度长度和资源租赁成本为目标时

与成本感知任务调度算法(CCSH)相比

在资源租赁成本基本一致的情况下

LGPPSO算法的调度长度平均降低约9.97%.

Abstract

A new task scheduling algorithm for large graph processing based on particle swarm optimization(short for LGPPSO)is proposed to take the monetary cost in cloud computing into account. The schedule plan for large graph processing task is expressed as position of particles

and both the monetary cost and the schedule length are used in the fitness function. The parameters and operations of the particles in LGPPSO are then redefined. The velocity and position of particles are updated at each iteration to get a near-optimal solution. Simulation results show that the average schedule length of LGPPSO algorithm is reduced by about 12.3% compared to the heterogeneous earliest finish time algorithm

and is reduced by about 9.97% compared to the cost conscious scheduling heuristic algorithm with similar resource rental cost.

关键词

Keywords

references

MALEWICZ G, AUSTERN M H, BIK A J, et al. Pregel: a system for large-scale graph processing[C]∥Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 2010:135-146.

于戈,谷峪,鲍玉斌,等.云计算环境下大规模图数据处理技术 [J].计算机学报,2011,34(10):1753-1767.

YU Ge, GU Yu, BAO Yubin, et al. Large scale graph data processing on cloud computing environments [J]. Chinese Journal of Computers, 2011, 34(10):1753-1767.

ARMBRUST M, FOX A, GIFFITH R, et al. Above the clouds: a Berkeley view of cloud computing [EB/OL].(2009-10-08)[2012-04-03]. http:∥www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.html.

BUYYA R, YEO C S, VENUGOPAL S, et al. Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility [J]. Future Generation Computer Systems, 2009,25(6):599-616.

ULLMAN J K. NP-complete scheduling problems[J]. Journal of Computer and Systems Sciences, 1975, 10(3): 498-500.

TOPCUOGLU K, HARIRI S, WU M. Performance-effective and low-complexity task scheduling for heterogeneous computing [J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.

BOZDA D, ZGNER F, CATALYUREK R U. A task duplication based bottom-up scheduling algorithm for heterogeneous environments [C]∥Proceedings of the 20th International Parallel and Distributed Processing Symposium. Piscataway, NJ, USA: IEEE, 2006:160-172.

YANG T, GERASOULI A. DSC: scheduling parallel tasks on an unbounded number of processors[J]. IEEE Transactions on Parallel and Distributed Systems, 1994, 5(9):951-967.

DEELMAN E, SINGH G, SU M H, et al. Pegasus: a framework for mapping complex scientific workflows onto distributed systems[J]. Scientific Programming, 2005,13(3): 219-237.

ISARD M, BUDIU M, YU Yuan, et al. Dryad: distributed data-parallel programs from sequential building blocks[C]∥Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems. New York, USA: ACM, 2007: 59-72.

WARNEKE D, KAO O. Nephele: efficient parallel data processing in the cloud [C]∥Proceedings of the 2nd Workshop on Many-Task Computing on Grids and Supercomputers. New York, USA: ACM, 2009: 1-10.

LI Jian, SU Sen, CHENG Xiang, et al. Cost-conscious scheduling for large graph processing in the cloud [C]∥Proceedings of the 13th International Conference on High Performance Computing and Communications. Piscataway, NJ, USA: IEEE, 2011: 808-813.

Amazon Amazon Elastic Compute Cloud [EB/OL].(2009-03-01)[2012-05-17].http:∥calculator.s3.amazonaws.com/calc5.html.

Google.Google app engine [EB/OL].(2010-04-20)[2011-07-03]. http:∥cloud.google.com/pricing/compute-engine.html.

ZHU Q, AGRAWAL G. Resource provisioning with budget constraints for adaptive applications in cloud environments [C]∥Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing. New York, USA: ACM, 2010: 304-307.

ULUNGU G, TEGHEM J. Multiobjective combinatorial optimization problems: a survey[J]. Journal of Multi-Criteria Decision Analysis, 1994, 3(2): 83-104.

KENNEDY J, EBERHART R. Particle swarm optimization[C]∥Proceedings of the International Conference on Neural Networks. Piscataway, NJ, USA: IEEE, 1995: 1942-1948.

HOLLAND J. Adaptation in natural and artificial systems [D].Boston, MA,USA: Massachusetts Institute of Technology,1992.

程祥,张忠宝,苏森,等. 基于粒子群优化的虚拟网络映射算法[J].电子学报, 2011, 39(10): 2240-2244.

CHENG Xiang, ZHANG Zhongbao, SU Sen, et al. Virtual network embedding based on particle swarm optimization[J]. Chinese Journal of Electronics, 2011, 39(10):2240-2244.

BARBOSA J G, MOREIRA R. Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters[J]. Parallel Comput, 2011, 37(8): 428-438.

Institut National de Recherche en Informatique et en Automatique. DAG generation program [EB/OL].(2005-04-09)[2012-03-12]. http:∥www.loria.fr/～suter/dags/html.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Face Recognition with Features Extraction Based on Particle Swarm Optimization

Profile Error Calculation for Gas Turbine Blade Based on Subdivision Approach Algorithm and Particle Swarm Optimization

Performance-Evaluation-Based Meta-Task Scheduling Algorithm

A Constructing Method of Reference Maps for Geomagnetic Navigation Using Rectangular Harmonic Analysis and Support Vector Machine

Deployment and Scheduling of Virtual Machines in Cloud Computing: An “AHP” Approach

Related Author

郭崇慧 2

温浩 1

赵万华 1

廖平 3

刘学云 2

王建录 1

胡志刚

胡周君

Related Institution

State Key Laboratory of Integrated Service Networks, Xidian University

School of Mechanical Engineering, Xi'an Jiaotong University

School of Information Science and Engineering, Central South University

Laboratory of Accurate Guidance and Simulation, The Second Artillery Engineering College

Shaanxi Province Key Laboratory of Computer Network, Xi'an Jiaotong University

⁰