Please wait a minute...
J4  2013, Vol. 47 Issue (9): 1547-1553    DOI: 10.3785/j.issn.1008-973X.2013.09.005
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
Download:   PDF(0KB) HTML
Export: BibTeX | EndNote (RIS)      


 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. 

Published: 01 September 2013
CLC:  TP 393.4  
Cite this article:

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.

URL:     OR



[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] LIU Duan-Yang, CAO Yan-Long. Research on incentive penalty model in computational grids[J]. J4, 2010, 44(9): 1687-1691.