Please wait a minute...
J4  2013, Vol. 47 Issue (9): 1547-1553    DOI: 10.3785/j.issn.1008-973X.2013.09.005
计算机技术,无线电电子学     
 基于能量模型的可分负荷调度算法的研究
刘端阳1 ,谢建平2,曹衍龙3
1.浙江工业大学 计算机学院, 浙江 杭州 310023;2.丽水学院 工学院, 浙江 丽水323000;
3.浙江大学 机械工程学系,浙江 杭州 310027
Research on divisible load scheduling algorithm based on energy model
LIU Duan-yang1 , Xie Jian-ping2, CAO Yan-long3
1.College of Computer Science, Zhejiang University of Technology, Hangzhou 310023, China;
2. Institute of Technology, Lishui University, Lishui 323000,China;3. Department of Mechanical Engineering,
Zhejiang University, Hangzhou 310027, China
 全文: PDF  HTML
摘要:

为了解决分布式计算系统能量消耗成本高的问题,在具有动态电压调节技术计算处理器的基础上,研究总线型网络环境中可分负荷的能量调度问题.根据能量与处理器速度的N次幂关系,在忽略网络延迟和给定运行时间的前提下,以最小化能量消耗为优化目标,建立可分负荷调度问题模型.采用非线性规划方法和Kuhn-Tucker条件,提出新的基于能量模型的负荷调度方案,并设计了相应的算法流程.对新方案和其他调度方案进行了对比和分析,结果显示新方案能耗率减少了10%~30%,验证了新方案在节能方面的有效性和优越性.

Abstract:

 In order to solve the problem of high energy consumption ratio in distributed computing systems, this paper bases on processors that are capable of dynamic voltage scaling, and studies energy-aware scheduling problems about divisible loads in bus networks. According to N-time power relations between energy and speed of a processor, and under the premise of ignoring network delay and given deadline time, this paper targets minimizing energy consumption, and builds a problem model about divisible loads scheduling. Then, this paper uses non-linear programming and Kuhn-Tucker conditions, proposes a new divisible loads scheduling scheme based on energy model, and designs its programming flow. At last, it compares this new scheduling scheme with other schemes by experiments, data show its energy consumption ratio decreases 10% to 30%, and its effectiveness and superiority on energy saving is proved. 

出版日期: 2013-09-01
:  TP 393.4  
基金资助:

国家自然科学基金资助项目(50975257);国家自然科学基金青年项目资助(61202204).

通讯作者: 曹衍龙,男,副教授.     E-mail: sdcaoyl@zju.edu.cn
作者简介: 刘端阳(1975-),男,副教授, 从事分布式计算的教学科研工作.E-mail: ldy@zjut.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  

引用本文:

刘端阳 ,谢建平,曹衍龙.  基于能量模型的可分负荷调度算法的研究[J]. J4, 2013, 47(9): 1547-1553.

LIU Duan-yang , Xie Jian-ping, CAO Yan-long. Research on divisible load scheduling algorithm based on energy model. J4, 2013, 47(9): 1547-1553.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2013.09.005        http://www.zjujournals.com/eng/CN/Y2013/V47/I9/1547

[1] ROBERTAZZI T G. Ten reasons to use divisible load theory[J]. Computer, 2003, 36(5): 63-68.
[2] BHARADWAJ V, GHOSE D, MANI V, et al. Scheduling divisible loads in parallel and distributed systems [M]. Los Alamitos, CA, USA : IEEE Computer Society Press, 1996.
[3] BURD T D, BRODERSEN R W. Design issues for dynamic voltage scaling [C]∥ Proceedings of the 2000 International Symposium on Low Power Electronics and Design. New York, USA: ACM, 2000: 9-14.
[4] BURD T.D, PERING T.A, STRATAKOS A J, et al. A dynamic voltage scaled microprocessor system [J]. IEEE Journal of Solid-State Circuits, 2000, 35(11): 1571-1580.
[5] SUBRATA R, ZOMAYA A Y, LANDFELDT B. Cooperative power-aware scheduling in grid computing environments [J]. Journal of Parallel and Distributed Computing, 2010,70(2): 200-222.
[6] YAO F, DEMERS A, SHENKER S. A scheduling model for reduced CPU energy [C]∥ Proceedings of the 36th Annual Symposium on Foundations of Computer Science. Milwaukee, Wisconsin: IEEE Computer Society, 1995:374-382.
[7] Li X, BHARADWAJ V, KO C. Distributed image processing on a network of workstations [J]. International Journal of Computers and Applications, 2003, 25(2): 1-10.
[8] BLAZEWICZ J, DROZDOWSKI M, MARKIEWICZ M. Divisible task scheduling-concept and verification [J]. Parallel Computing, 1999, 25(1): 87-98.
[9] CHAN S, BHARADWAJ V, GHOSE D. Large matrix-vector products on distributed bus networks with communication delays using the divisible load paradigm: performance and simulation [J]. Mathematics and Computers in Simulation, 2001, 58(1): 71-92.
[10] BHARADWAJ V, BARLAS G. Access time minimization for distributed multimedia applications [J]. Multimedia Tools and Applications, 2000, 12(2/3): 235-256.
[11] YU D, ROBERTAZZI T G. Divisible load scheduling for grid computing [C]∥ Proceedings of the 15th International Conference on Parallel and Distributed Computing and Systems. Marina del Rey, USA : ACTA Press, 2003:392-401.
[12] LIN X, LU Y, DEOGUN J, et al. Real-time divisible load scheduling for cluster computing [C]∥ Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium. Washington, DC, USA: IEEE Computer Society, 2007: 303-314.
[13] DAI L, SHEN Z, CHANG Y L. DTSWC: A task scheduling algorithm in wireless sensor networks with co-processor based on divisible load theory [C]∥ Proceedings of the Interna tional Conference On Computer and Communication Technologies in Agriculture Engineering. Chengdu, China : IEEE Computer Society, 2010:494-497.
[14] SHIH W C, TSENG S S, YANG C T. Performance study of parallel programming on cloud computing environments using MapReduce [C]∥ Proceedings of the 2010 International Conference on Information Science and Applications. Seoul, Korea : IEEE Computer Society, 2010: 18.
[15] BHARADWAJ V, GHOSE D, ROBERTAZZI T G. Divisible load theory: a new paradigm for load scheduling in distributed systems [J]. Cluster Computing, 2003, 6(1): 7-17.
[16] BEAUMONT O, CASANOVA H, LEGRAND A, et al. Scheduling divisible loads on star and tree networks: results and open problems [J]. IEEE Transaction Parallel and Distributed Systems, 2005, 16(3): 207-218.
[17] CARROLL T E, GROSU D. Strategyproof mechanisms for scheduling divisible loads in bus-networked distributed systems [J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(8):1124-1135.
[18] AYDI H, MEJIA-ALVAREZ P, MOSSE D, et al. Dynamic and aggressive scheduling techniques for power-aware real-time systems [C]∥ Proceedings of the 22nd IEEE Real-Time Systems Symposium. London UK: IEEE Computer Society, 2001: 95105.
[19] SHIN D, KIM J. Dynamic voltage scaling of mixed task sets in priority-driven systems [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(3): 438-453.
[20] XU R, MELHEM R, MOSSE D. Energy-aware scheduling for streaming applications on chip multiprocessors [C]∥Proceedings of the 28th IEEE International Real-Time Systems Symposium. Washington, DC, USA:IEEE Computer Society, 2007: 25-38.
[21] LI K. Scheduling parallel tasks on multiprocessor computers with efficient power management [C]∥ Proceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum. Atlanta, GA : IEEE Computer Society , 2010:18.
[22] CUBERT RM, FISHWICK P. Sim++ Reference Manual [M]. Gainsville, FL , USA: University of Florida, 1995.
[23] GROSU D, CHRONOPOULOS A T, LEUNG M Y. Cooperative load balancing in distributed systems [J]. Concurrency and Computation: Practice & Experience, 2008, 20(16): 1953-1976.

[1] 刘端阳, 曹衍龙. 计算网格中激励惩罚模型的研究[J]. J4, 2010, 44(9): 1687-1691.