Problem-Independent Approach to Multiprocessor Dependent Task Scheduling

• Autorzy: Król D. , Zydek D. , Koszałka L.
• Języki publikacji: EN

Abstrakty

EN

This paper concerns Directed Acyclic Graph task scheduling on parallel executors. The problem is solved using two new implementations of Tabu Search and genetic algorithm presented in the paper. A new approach to solution coding is also introduced and implemented in both metaheuristics algorithms. Results given by the algorithms are compared to those generated by greedy LPT and SS-FF algorithms; and HAR algorithm. The analysis of the obtained results of multistage simulation experiments confirms the conclusion that the proposed and implemented algorithms are characterized by very good performance and characteristics.

Słowa kluczowe

EN

tasks scheduling; DAG; genetic algorithm; tabu search; makespan

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2012
• Tom: Vol. 58, No. 4
• Strony: 369--379
• Opis fizyczny: Bibliogr. 29 poz., wykr.

Twórcy

autor

Król D.

• Department of Electrical Engineering, Idaho State University, USA

autor

Zydek D.

• Department of Electrical Engineering, Idaho State University, USA

autor

Koszałka L.

• Department of Systems and Computer Networks, Wrocław University of Technology, Poland

Bibliografia

• [1] E. G. Coffman and J. L. Bruno, Teoria szeregowania zadań (in EnglishTheory of Tasks Scheduling). Warsaw: Wydawnictwa Naukowo- Techniczne, 1980.
• [2] G. C. I. Centre. (2012, Jun) International grid activities. [Online]. Available: www.gridcomputing.com
• [3] D. Zydek, H. Selvaraj, G. Borowik, and T. Luba, „Energy characteristic of processor allocator and network-on-chip”, International Journal of Applied Mathematics and Computer Science, vol. 21, no. 2, pp. 385-399, 2011, DOI: 10.2478/v10006-011-0029-7.
• [4] D. Zydek, H. Selvaraj, L. Koszalka, and I. Pozniak-Koszalka, „Evaluation scheme for noc-based cmp with integrated processor management system”, International Journal of Electronics and Telecommunications, vol. 56, no. 2, pp. 157-168, 2010, DOI: 10.2478/v10177-010-0021-4.
• [5] D. Zydek, N. Shlayan, E. Regentova, and H. Selvaraj, „Review of packet switching technologies for future noc”, in Proceedings of 19th International Conference on Systems Engineering (ICSEng 2008), 2008, pp. 306-311, DOI: 10.1109/ICSEng.2008.47.
• [6] C. Wang, Z. Li, and S. Zhu, „Minimizing total tardiness on parallel machines based on genetic algorithm”, in Control and Decision Conference, 2008. CCDC 2008. Chinese, 2008, pp. 165-169, DOI: 10.1109/CCDC.2008.4597291.
• [7] H. Jingui and L. Rongheng, „Approximation algorithms on multiprocessor task scheduling”, in Computer Engineering and Technology, 2009. ICCET'09, International Conference, 2009, pp. 303-307, DOI: 10.1109/ICCET.2009.68.
• [8] D. Zydek, G. Chmaj, A. Shawky, and H. Selvaraj, „Location of processor allocator and job scheduler and its impact on cmp performance”, International Journal of Electronics and Telecommunications, vol. 58, no. 1, pp. 9-14, 2012, DOI: 10.2478/v10177-012-0001-y.
• [9] D. Zydek, H. Selvaraj, and L. Gewali, „Synthesis of processor allocator for torus-based chip multiprocessors”, in Proceedings of 7th InternationalConference on Information Technology: New Generations (ITNG 2010), 2010, pp. 13-18, DOI: 10.1109/ITNG.2010.145.
• [10] J. C. Liou and M. A. Palis, „A comparison of general approaches to multiprocessor scheduling”, in IPPS'97 Proceedings of the 11th International Symposium on Parallel Processing, 1997, pp. 152-156, DOI: 10.1109/IPPS.1997.580873.
• [11] R. Nossal, „An evolutionary approach to multiprocessor scheduling of dependent tasks”, in the 1st International Workshop on Biologically Inspired Solutions to Parallel Processing Problems, 1998, pp. 279-287.
• [12] M. S. Jelodar, S. N. Fakhraie, F. Montazeri, S. M. Fakhraie, and M. N.Ahmadabadi, „A representation for genetic-algorithm-based multiprocessor task scheduling”, in IEEE Congress on Evolutionary Computation,CEC 2006, 2006, pp. 340-347, DOI: 10.1109/CEC.2006.1688328.
• [13] K. P. Belkhale and P. Banerjee, „Approximate algorithms for the partitionable independent task scheduling problem”, in Proceedings of the 19th International Conference on Parallel Processing, 1990, pp. 72-75.
• [14] X. Cai, C.-Y. Lee, and T.-L. Wong, „Multiprocessor task scheduling to minimize the maximum tardiness and the total completion time”,IEEE Transactions on Robotics and Automation, vol. 16, no. 6, pp. 824-830, 2000, DOI: 10.1109/70.897792.
• [15] G. Łabiak and G. Borowik, „Statechart-based controllers synthesis in FPGA structures with embedded array blocks”, International Journal of Electronics and Telecommunications, vol. 56, pp. 13-24, 2010, DOI: 10.2478/v10177-010-0002-7.
• [16] G. Borowik, M. Rawski, G. Łabiak, A. Bukowiec, and H. Selvaraj, „Efficient logic controller design”, in Fifth International Conference on Broadband and Biomedical Communications (IB2Com), Malaga, Spain, Dec. 2010, pp. 1-6, DOI: 10.1109/IB2COM.2010.5723633.
• [17] J. Barbosa, C. Morais, R. Nobrega, and A. Monteiro, „Static scheduling of dependent parallel tasks on heterogeneous clusters”, in 2005 IEEE International Conference on Cluster Computing, 2005, pp. 1-8, DOI: 10.1109/CLUSTR.2005.347024.
• [18] H. R. Boveiri, „Aco-mts: A new approach for multiprocessor task scheduling based on ant colony optimization”, in Intelligent and Advanced Systems (ICIAS), 2010 International Conference, 2010, pp. 1-5, DOI: 10.1109/ICIAS.2010.5716203.
• [19] R. C. Correa, A. Ferreira, and P. Rebreyend, „Scheduling multiprocessor tasks with genetic algorithms”, IEEE Transactions on Paralleland Distributed Systems, vol. 10, no. 8, pp. 825-837, 1999, DOI: 10.1109/71.790600.
• [20] T. Davidovic and T. G. Crainic, „Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems”, Computers and Operations Research, vol. 33, no. 8, pp. 2155-2177, 2006, DOI: 10.1016/j.cor.2005.01.005.
• [21] X. Kong, W. Xu, and J. Liu, „A permutation-based differential evolution algorithm incorporating simulated annealing for multiprocessor scheduling with communication delays”, in ICCS'06, Proceedings of the 6th International Conference on Computational Science, vol. Part I, 2006, pp. 514-521, DOI: 10.1007/11758501_70.
• [22] A. M. Rahmani and M. Rezvani, „A novel genetic algorithm for static task scheduling in distributed systems”, International Journal of Computer Theory and Engineering, vol. 1, no. 1, pp. 1-6, 2009, DOI: 10.7763/IJCTE.2009.V1.1.
• [23] Y. K. Kwok and I. Ahmad, „Benchmarking the task graph scheduling algorithms”, in Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International ... and Symposium on Parallel and Distributed Processing 1998, 1998, pp. 531-537, DOI: 10.1109/IPPS.1998.669967.
• [24] I. Ahmad and Y. -K. Kwok, „On parallelizing the multiprocessor scheduling problem”, IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 4, pp. 414-431, 1999, DOI: 10.1109/71.762819.
• [25] M. Drozdowski, „Scheduling multiprocessor tasks - an overview”, European Journal of Operational Research, vol. 94, no. 2, pp. 215-230, 1996, DOI: 10.1016/0377-2217(96)00123-3.
• [26] F. Ghedjati and M. -C. Portmann, „Dynamic heuristics for the generalized job-shop scheduling problem”, in IEEE International Conference on Systems, Man and Cybernetics, 2009, SMC 2009, 2009, pp. 2562-2567, DOI: 10.1109/ICSMC.2009.5346326.
• [27] R. R. A. Rudek, „A flowshop scheduling problem with machine deterioration and maintenance activities”, in Proceedings of the 17th International Conference on Methods and Models in Automation and Robotics, 2012, pp. 40-45.
• [28] A. Y. Zomaya, C. Ward, and B. Macey, „Genetic scheduling for parallel processor systems: comparative studies and performance issues”, IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 8, pp. 795-812, 1999, DOI: 10.1109/71.790598.
• [29] Z. Michalewicz and D. B. Fogel, How to Solve It: Modern Heuristics Second Edition. Springer, 2004.