云计算环境下的大规模图状数据处理任务调度算法

李健; 黄庆佳; 刘一阳; 苏森

您当前的位置：

首页 >

文章列表页 >

云计算环境下的大规模图状数据处理任务调度算法

更新时间：2025-07-09

- 云计算环境下的大规模图状数据处理任务调度算法
- A Task Scheduling Algorithm for Large Graph Processing Cloud in Computing
- 西安交通大学学报 2012年46卷第12期页码：116-122
- 作者机构：
  
  北京邮电大学网络与交换技术国家重点实验室,北京,10087
- 作者简介：
- 基金信息：
  
  : 2012-06-27. 作者简介:李健(1988-),男,博士生;苏森(通信作者),男,教授,博士生导师. 基金项目: 国家自然科学基金资助项目(61170274)
- DOI：
  中图分类号： TP311
- 网络首发：2012-12-10，
  
  纸质出版：2012
- 稿件说明：
移动端阅览
李健, 黄庆佳, 刘一阳, 等. 云计算环境下的大规模图状数据处理任务调度算法[J]. 西安交通大学学报, 2012,46(12):116-122.

A Task Scheduling Algorithm for Large Graph Processing Cloud in Computing[J]. 2012, 46(12): 116-122.
李健, 黄庆佳, 刘一阳, 等. 云计算环境下的大规模图状数据处理任务调度算法[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.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

利用粒子群优化的人脸特征提取识别算法

结合分割逼近和粒子群法的燃气轮机叶片轮廓度误差计算

一种基于性能评估的元任务调度算法

采用矩谐分析和支持向量机的地磁导航基准图构建方法

云环境下基于多属性层次分析的虚拟机部署与调度策略