Particle Swarm Optimization based Sequential and Parallel Tasks Scheduling Model for Heterogeneous Multiprocessor Systems

• Autorzy: Kumar P. R. , Babu P. , Palani S.

Identyfikatory

DOI

10.3233/FI-2015-1225

• Języki publikacji: EN

Abstrakty

EN

Multiprocessors have emerged as a powerful computing means for running real-time applications, especially where a uniprocessor system would not be sufficient enough to execute all the tasks. The high performance and reliability of multiprocessors have made them a powerful computing resource. Such computing environment requires an efficient algorithm to determine when and on which processor a given task should be executed. In multiprocessor systems, an efficient scheduling of sequential and parallel tasks onto the processors is known to be NP- Hard problem. In this paper, the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint on homogeneous and heterogeneous multiprocessor computers through independent sequential and parallel tasks are proposed. These problems emphasize the tradeoff between power and performance and are defined such that the power-performance product is optimized by fixing one factor and minimizing the other and vice versa. The performance of the proposed algorithm with optimal solution is validated using Particle Swarm Optimization (PSO) The PSO algorithm achieves 47.5% and 32% of power savings for scheduling sequential and parallel tasks to the processors respectively and also 45.5% of energy saving are achieved for scheduling both sequential or parallel tasks to the processors.

Słowa kluczowe

EN

multiprocessor; embedded system; energy and power optimization; PSO algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 139, nr 1
• Strony: 43--65
• Opis fizyczny: Bibliogr. 28 poz., tab., wykr.

Twórcy

autor

Kumar P. R.

• P.S.R Engineering College Sivakasi, Tamilnadu, India

autor

Babu P.

• K.S. Rangasamy College of Technology Tiruchengode, Tamilnadu, India

autor

Palani S.

• Suharsan Engineering College Pudukkottai, Tamilnadu, India

Bibliografia

• [1] Ranjithkumar, P., Palani, S.: An Efficient Energy and Schedule Length Model for Multiprocessor Computers, International Journal of Computer Applications in Technology, 44(2),2012, 217-225.
• [2] Braun, T.D., Siegel, H.J., Beck, N., Boloni, L.L., Maheswaran, M., Reuther, A.I., Robertson, J.P., Theys, M.D., Yao, B., Hensgen, D., Freund, R.F.: A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks Onto Heterogeneous Distributed Computing Systems, Journal of Parallel and Distributed Computing, 61(6), 2001, 810-837.
• [3] Li, K.: Performance Analysis of Power-Aware Task Scheduling Algorithms on Multiprocessor Computers with Dynamic Voltage and Speed, IEEE Trans. on Parallel And Distributed Systems, 19(11), 2008, 1484-1497.
• [4] Yao, F., Demers, A., Shenker, S.: A Scheduling Model for Reduced CPU energy ,, Proc. of the 36th Annual Symposium on Foundations of Computer Science, 374-382, 1995.
• [5] Shin, Y., Choi, K.: Power Conscious Fixed Priority Scheduling for Hard Real-time Systems, Proc. of the 36th ACM/IEEE Conference on Design Automation Conference,134-139, 1999.
• [6] Hong, I., Potkonjak, M., Srivastava, M.B.: On-line Scheduling of Hard Real-time Tasks on Variable Voltage Processor, Proc. of the 1998 IEEE/ACM International Conference on Computer-aided Design (ICCAD 98), 653-656, 1998.
• [7] Ishihara, T.,Yasuura, H.: Voltage Scheduling Problems for Dynamically Variable Voltage Processors: Proc. of the International Symposium on Low Power Electronics and Design,197-202, 1998.
• [8] Jejurikar, R., Gupta, R.: Energy Aware Task Scheduling with Task Synchronization for Embedded Real Time Systems, Proc. of International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES), 164-169, 2002.
• [9] Kenli Li, XiaoyongTang, Keqin Li.: Energy-Efficient Stochastic Task Scheduling on Heterogeneous Computing Systems ,IEEE Trans.Parallel Distrib.Syst.,74(7)2014,2662-2672.
• [10] Chen, X., Zheng, J., Chen, Y., Li, H., Zhang, W., WeiLiao, S., Wang, J.: Fine-grained dynamic voltage scaling on OLED display, IEEE Asia and South Pacific Design Automation Conference (ASPDAC), 2012.
• [11] Dargie, W.: Dynamic power management in wireless sensor networks: State-of-the-art, Sensors Journal, IEEE, 12(5), 2012, 1518-1528.
• [12] Rahimi, A., Salehi, M.E.,hammadi, S., Fakhraie, S.M.: Low-energy GALS NoC with FIFO Monitoring Dynamic Voltage Scaling, Elsevier Microelectronics Journal,42(6),2010,889-896.
• [13] Zhang, L., Chen, Y., Sun, R., Jing, S., Yang, B.: A Task Scheduling Algorithm Based on PSO for Grid Computing, International Journal of Computational Intelligence Research, 4(1),2008, 37-43.
• [14] Anderson, J., Brandenburg, B.: The OMLP Family of Optimal Multiprocessor Real-Time Locking Protocols, Design Automation for Embedded Systems, special issue on selected papers from the 9th International Conference on Embedded Software, 1-66, July, 2012.
• [15] Zhang, F., Chanson, S.T.: Blocking-aware Processor Voltage Scheduling for Real-time Tasks, ACM Transactions in Embedded Computing Systems, 3(2),2010,307-335.
• [16] Brandenburg, B., Anderson, J.: Spin-Based Reader-Writer Synchronization for Multiprocessor Real-Time Systems, Real-Time Systems, special issue on selected papers from Euromicro Conference on Real-Time Systems, 46(1),2010, 25-87.
• [17] Quan, G., Hu, X.: Energy Efficient Fixed Priority Scheduling for Real Time Systems on Variable Voltage Processors, Proc. of the 38th Conference on Design Automation,828-833, 2011.
• [18] Bamakhrama, M., Stefanov, T.: Hard-Real-Time Scheduling of Data-Dependent Tasks in Embedded Streaming Applications, Proc.of the 9th ACM International Conference on Embedded Software , 195-204, 2011.
• [19] Zhao, B., Aydin, H., Zhu, D.: Reliability-Aware Dynamic Voltage Scaling for Energy-Constrained Rea –Time Embedded Systems, IEEE transactions on Computer Design, 4(3), 2008, 633-639.
• [20] Yu, Y., Prasnna, V.K.: Power-aware Resource Allocation for Independent Tasks in Heterogeneous Real-time Systems: , IEEE Ninth International Conference on Parallel and Distributed Systems, 341- 348, 2002.
• [21] Schmitz, M., AlHashimi, B., Eles, P.: System Level Design Techniques for Energy Efficient Embedded Systems, Kluwer Academic Publishers, 2004.
• [22] Gorjiara, B., Bagherzadeh, N.: Ultra-Fast and Efficient Algorithm for Energy Optimization by Gradient-Based Stochastic Voltage and Task Scheduling, ACM Trans. on Design Automation of Electronic Systems,12(4),2007,1-20.
• [23] Lesage, B., Puaut, I.: PRETI: partitioned real-time shared cache for mixed-criticality real-time systems, Proc.of 17th International Conference on Real-time and Network Systems, 45-54, 2012.
• [24] Zhang, Y., Wang, S., Phillip, P., Jia, G.: Binary PSO with mutation operator for feature selection using decision tree applied to spam detection, Knowledge-Based Systems,64,2014,22-31.
• [25] Zhang, Y., Yan, J., Wei, G., Wu, L.: Find multi-objective paths in stochastic networks via chaotic immune PSO. Expert Systems with Applications ,37,2010, 1911-1919.
• [26] Li, K.: Energy efficient scheduling of parallel tasks on multiprocessor computers; Journal of Supercomputing, 60(2),2012,223-247.
• [27] Zhai, B., Blaauw, D., Sylvester, D., Flautner, K.: Theoretical and Practical Limits of Dynamic Voltage Scaling, Proc.of the 41st Design Automation Conference, 868-873, 2004.
• [28] Tasgetiren, M. F., Liang, Y.C., Sevkli, M., Gencyilmaz, G.: Particle Swarm Optimization and Differential Evolution for Single Machine Total Weighted Tardiness Problem, International Journal of Production Research, 44(22),2006, 4737-4754.