تخصیص ایستای وظایف در سیستم‌های توزیع‌شده با استفاده از الگوریتم ژنتیک موازی
محورهای موضوعی : مدیریت صنعتی
1 - گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی واحد کرمان، کرمان، ایران
کلید واژه: الگوریتم ژنتیک سلولی, سیستم توزیع‌شده, تخصیص وظایف, الگوریتم ژنتیک موازی, الگوریتم ژنتیک جزیره‌ای,
چکیده مقاله :
در طی دو دهه اخیر، بالارفتن فوق‌العاده سرعت شبکه‌های رایانه ای و همچنین افزایش نیاز به سیستم‌هایی با کارایی بالا سبب شده است که محققان به پردازش‌های موازی و توزیع‌شده علاقه‌مند شوند. رشد سریع سیستم‌های توزیع‌شده باعث شده که مسائل گوناگونی در این زمینه مطرح شود. یکی از مهم‌ترین مسائلی که موردتوجه محققان زیادی قرارگرفته، مسئله تخصیص وظایف در این‌گونه محیط‌ها است که به‌منظور به دست آوردن بهره‌وری مؤثر از سیستم انجام می‌شود. مسئله تخصیص وظایف به‌جز در معدود موارد خاص جز مسائل NP-کامل است؛ بنابراین از فرایندهای اکتشافی برای دستیابی به راه‌حل‌های زیربهینه در مدت‌زمان مطلوب استفاده می‌شود. اگرچه از روش‌های مختلف در تحقیقات استفاده‌شده، اما هنوز پیدا کردن روش مؤثر و کارا برای این مشکل موردنیاز و مطلوب است. در این پژوهش از الگوریتم ژنتیک موازی برای پیدا کردن راه‌حل بهینه برای تخصیص یک گراف از وظایف به پردازنده‌ها در سیستم توزیع‌شده استفاده‌شده است. نتایج نشان داد الگوریتم پیشنهادی می‌تواند تخصیص‌های بهینه یا نزدیک بهینه برای مسائل با اندازه‌های گوناگون ارائه دهد. همچنین روش پیشنهادی توانست در زمان بسیار سریع‌تر از الگوریتم ژنتیک سنتی و با تسریع فراخطی، مسائل با اندازه‌های بزرگ و متوسط را حل کند.
چکیده انگلیسی:
Over the past two decades, PC speeds have increased from a few instructions per second to several million instructions per second. The tremendous speed of today's networks as well as the increasing need for high-performance systems has made researchers interested in parallel and distributed computing. The rapid growth of distributed systems has led to a variety of problems. The most important problem that has been addressed by many researchers is the task allocation in such environments in order to obtain effective system efficiency. The task allocation problem is, except in a few specific cases, an NP-complete problem; so, heuristic methods are used to achieve suboptimal solutions in the desired time. Although different methods have been used in research, finding an effective and efficient method for this problem is still needed and desirable. This study used a parallel genetic algorithm to find the optimal solution for allocating a graph of tasks to the processors in a distributed system. The results showed that the proposed algorithm can provide optimal or near-optimal allocations for problems of different sizes. Also, the proposed method was able to solve problems of large and medium-size in a much faster time than traditional genetic algorithm with super linear speedup.
منابع و مأخذ:
Aggarwal, A., Verma, R., & Singh, A. (2018a). An efficient approach for resource allocations using hybrid scheduling and optimization in distributed system. International Journal of Education and Management Engineering, 8(3), 33.
Aggarwal, A., Verma, R., & Singh, A. (2018b). An efficient approach for resource allocations using hybrid scheduling and optimization in distributed system. Int. J. Educ. Manag. Eng.(IJEME), 8(3), 33-42.
Akbari, M., & Rashidi, H. (2016). A multi-objectives scheduling algorithm based on cuckoo optimization for task allocation problem at compile time in heterogeneous systems. Expert Systems with Applications, 60, 234-248.
Alba, E. (2002). Parallel evolutionary algorithms can achieve super-linear performance. Information Processing Letters, 82(1), 7-13.
Alba, E., & Troya, J. M. (1999). A survey of parallel distributed genetic algorithms. Complexity, 4(4), 31-52.
Attiya, G., & Hamam, Y. (2003a). Hybrid Algorithm for Mapping Parallel Applications in Distributed Systems. Paper presented at the Fifth International Conference on PRAM, Poland.
Attiya, G., & Hamam, Y. (2003b). Optimal allocation of tasks onto networked heterogeneous computers using minimax criterion. Paper presented at the Proceedings of International Network Optimization Conference (INOC, 03).
Attiya, G., & Hamam, Y. (2006). Task allocation for maximizing reliability of distributed systems: A simulated annealing approach. Journal of parallel and distributed computing, 66(10), 1259-1266.
Augustine, D. P., & Raj, P. (2016). Performance Evaluation of Parallel Genetic Algorithm for Brain MRI Segmentation in Hadoop and Spark. Indian Journal of Science and Technology, 9(48).
Bharati, R., Shahakar, M., & Mahajan, R. (2014). Task Allocation Policy in Distributed Computing Using Refined Heuristics. International Journal of Emerging Technology and Advanced Engineering, 4(6).
Bharati, R. D., Jagtap, V. N., Gupta, O. C., & Landge, S. S. (2013). Task Allocation for Maximizing Reliability of Distributed Computing Systems using Dynamic Greedy Heuristic. International Journal of Advanced Research in Computer and Communication Engineering, 2(3), 1554-1557.
Braun, T. D., Siegel, H. J., Maciejewski, A. A., & Hong, Y. (2008). Static resource allocation for heterogeneous computing environments with tasks having dependencies, priorities, deadlines, and multiple versions. Journal of parallel and distributed computing, 68(11), 1504-1516.
Cai, P., Cai, Y., Chandrasekaran, I., & Zheng, J. (2016). Parallel genetic algorithm based automatic path planning for crane lifting in complex environments. Automation in Construction, 62, 133-147.
Chaubey, M., & Gupta, M. (2019). DESIGNING A TASK ALLOCATOR FRAMEWORK FOR DISTRIBUTED COMPUTING. International Journal of Advanced Research in Computer Science, 10(4).
Feng, Z.-K., Niu, W.-J., Zhou, J.-Z., Cheng, C.-T., Qin, H., & Jiang, Z.-Q. (2017). Parallel multi-objective genetic algorithm for short-term economic environmental hydrothermal scheduling. energies, 10(2), 163.
Govil, K. (2011). A smart algorithm for dynamic task allocation for distributed processing environment. International Journal of Computer Applications, 28(2), 13-19.
Govil, K., & Kumar, A. (2011). A modified and efficient algorithm for Static task assignment in Distributed Processing Environment. International Journal of Computer Applications, 23(8), 1-5.
Hamed, A. Y. (2012). Task allocation for minimizing cost of distributed computing systems using genetic algorithms. International Journal of Advanced Research in Computer Science and Software Engineering, 2(9).
Hu, Y., Li, J., & He, L. A reformed task scheduling algorithm for heterogeneous distributed systems with energy consumption constraints. Neural Computing and Applications, 1-13.
Hu, Y., Li, J., & He, L. (2019). A reformed task scheduling algorithm for heterogeneous distributed systems with energy consumption constraints. Neural Computing and Applications, 1-13.
Jiang, Y. (2015). A survey of task allocation and load balancing in distributed systems. IEEE transactions on Parallel and Distributed Systems, 27(2), 585-599.
Jiang, Y. (2016). A survey of task allocation and load balancing in distributed systems. IEEE transactions on Parallel and Distributed Systems, 27(2), 585-599.
Kacprzyk, J., & Pedrycz, W. (2015). Springer handbook of computational intelligence: Springer.
Kang, Q.-M., He, H., Song, H.-M., & Deng, R. (2010). Task allocation for maximizing reliability of distributed computing systems using honeybee mating optimization. Journal of Systems and Software, 83(11), 2165-2174.
Kang, Q., He, H., & Wei, J. (2013). An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems. Journal of parallel and distributed computing, 73(8), 1106-1115.
Khan, F. N., & Govil, K. (2013a). Cost Optimization Technique of Task Allocation in Heterogeneous Distributed Computing System. International Journal of Advanced Networking and Applications, 5(3), 1913.
Khan, F. N., & Govil, K. (2013b). Static Approach for Efficient Task Allocation in Distributed Environment. International Journal of Computer Applications, 81(15), 19-22.
Menghani, G. (2010). A fast genetic algorithm based static heuristic for scheduling independent tasks on heterogeneous systems. Paper presented at the Parallel Distributed and Grid Computing (PDGC), 2010 1st International Conference on.
Neelakantan, P., & Sreekanth, S. (2016). Task allocation in distributed systems. Indian Journal of Science and Technology, 9(31).
Sharma, G., & Martin, J. (2009). MATLAB®: a language for parallel computing. International Journal of Parallel Programming, 37(1), 3-36.
Shatz, S. M., Wang, J.-P., & Goto, M. (1992). Task allocation for maximizing reliability of distributed computer systems. IEEE Transactions on Computers, 41(9), 1156-1168.
Srinivasan, S., & Jha, N. K. (1999). Safety and reliability driven task allocation in distributed systems. IEEE transactions on Parallel and Distributed Systems, 10(3), 238-251.
Stone, H. S. (1977). Multiprocessor scheduling with the aid of network flow algorithms. IEEE transactions on Software Engineering(1), 85-93.
Sudholt, D. (2015). Parallel evolutionary algorithms Springer Handbook of Computational Intelligence (pp. 929-959): Springer.
Tyagi, R., & Gupta, S. K. (2018). A Survey on Scheduling Algorithms for Parallel and Distributed Systems Silicon Photonics & High Performance Computing (pp. 51-64): Springer.
Vidyarthi, D. P., & Tripathi, A. K. (2001). Maximizing reliability of distributed computing system with task allocation using simple genetic algorithm. Journal of Systems Architecture, 47(6), 549-554.
Wu, J. (2017). Distributed system design: CRC press.
Yadav, P., Singh, M., & Sharma, K. (2011). An optimal task allocation model for system cost analysis in heterogeneous distributed computing systems: A heuristic approach. International Journal of Computer Applications, 28(4), 30-37.
Yadav, P. K., Singh, M., & Sharma, K. (2011). Task Allocation Model for Reliability and Cost optimization in Distributed Computing System. International Journal Of Modeling, Simulation, and Scientific Computing, 2(02), 131-149.
Zhang, X.-Y., Zhang, J., Gong, Y.-J., Zhan, Z.-H., Chen, W.-N., & Li, Y. (2016). Kuhn–Munkres parallel genetic algorithm for the set cover problem and its application to large-scale wireless sensor networks. IEEE Transactions on Evolutionary Computation, 20(5), 695-710.
_||_
Aggarwal, A., Verma, R., & Singh, A. (2018a). An efficient approach for resource allocations using hybrid scheduling and optimization in distributed system. International Journal of Education and Management Engineering, 8(3), 33.
Aggarwal, A., Verma, R., & Singh, A. (2018b). An efficient approach for resource allocations using hybrid scheduling and optimization in distributed system. Int. J. Educ. Manag. Eng.(IJEME), 8(3), 33-42.
Akbari, M., & Rashidi, H. (2016). A multi-objectives scheduling algorithm based on cuckoo optimization for task allocation problem at compile time in heterogeneous systems. Expert Systems with Applications, 60, 234-248.
Alba, E. (2002). Parallel evolutionary algorithms can achieve super-linear performance. Information Processing Letters, 82(1), 7-13.
Alba, E., & Troya, J. M. (1999). A survey of parallel distributed genetic algorithms. Complexity, 4(4), 31-52.
Attiya, G., & Hamam, Y. (2003a). Hybrid Algorithm for Mapping Parallel Applications in Distributed Systems. Paper presented at the Fifth International Conference on PRAM, Poland.
Attiya, G., & Hamam, Y. (2003b). Optimal allocation of tasks onto networked heterogeneous computers using minimax criterion. Paper presented at the Proceedings of International Network Optimization Conference (INOC, 03).
Attiya, G., & Hamam, Y. (2006). Task allocation for maximizing reliability of distributed systems: A simulated annealing approach. Journal of parallel and distributed computing, 66(10), 1259-1266.
Augustine, D. P., & Raj, P. (2016). Performance Evaluation of Parallel Genetic Algorithm for Brain MRI Segmentation in Hadoop and Spark. Indian Journal of Science and Technology, 9(48).
Bharati, R., Shahakar, M., & Mahajan, R. (2014). Task Allocation Policy in Distributed Computing Using Refined Heuristics. International Journal of Emerging Technology and Advanced Engineering, 4(6).
Bharati, R. D., Jagtap, V. N., Gupta, O. C., & Landge, S. S. (2013). Task Allocation for Maximizing Reliability of Distributed Computing Systems using Dynamic Greedy Heuristic. International Journal of Advanced Research in Computer and Communication Engineering, 2(3), 1554-1557.
Braun, T. D., Siegel, H. J., Maciejewski, A. A., & Hong, Y. (2008). Static resource allocation for heterogeneous computing environments with tasks having dependencies, priorities, deadlines, and multiple versions. Journal of parallel and distributed computing, 68(11), 1504-1516.
Cai, P., Cai, Y., Chandrasekaran, I., & Zheng, J. (2016). Parallel genetic algorithm based automatic path planning for crane lifting in complex environments. Automation in Construction, 62, 133-147.
Chaubey, M., & Gupta, M. (2019). DESIGNING A TASK ALLOCATOR FRAMEWORK FOR DISTRIBUTED COMPUTING. International Journal of Advanced Research in Computer Science, 10(4).
Feng, Z.-K., Niu, W.-J., Zhou, J.-Z., Cheng, C.-T., Qin, H., & Jiang, Z.-Q. (2017). Parallel multi-objective genetic algorithm for short-term economic environmental hydrothermal scheduling. energies, 10(2), 163.
Govil, K. (2011). A smart algorithm for dynamic task allocation for distributed processing environment. International Journal of Computer Applications, 28(2), 13-19.
Govil, K., & Kumar, A. (2011). A modified and efficient algorithm for Static task assignment in Distributed Processing Environment. International Journal of Computer Applications, 23(8), 1-5.
Hamed, A. Y. (2012). Task allocation for minimizing cost of distributed computing systems using genetic algorithms. International Journal of Advanced Research in Computer Science and Software Engineering, 2(9).
Hu, Y., Li, J., & He, L. A reformed task scheduling algorithm for heterogeneous distributed systems with energy consumption constraints. Neural Computing and Applications, 1-13.
Hu, Y., Li, J., & He, L. (2019). A reformed task scheduling algorithm for heterogeneous distributed systems with energy consumption constraints. Neural Computing and Applications, 1-13.
Jiang, Y. (2015). A survey of task allocation and load balancing in distributed systems. IEEE transactions on Parallel and Distributed Systems, 27(2), 585-599.
Jiang, Y. (2016). A survey of task allocation and load balancing in distributed systems. IEEE transactions on Parallel and Distributed Systems, 27(2), 585-599.
Kacprzyk, J., & Pedrycz, W. (2015). Springer handbook of computational intelligence: Springer.
Kang, Q.-M., He, H., Song, H.-M., & Deng, R. (2010). Task allocation for maximizing reliability of distributed computing systems using honeybee mating optimization. Journal of Systems and Software, 83(11), 2165-2174.
Kang, Q., He, H., & Wei, J. (2013). An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems. Journal of parallel and distributed computing, 73(8), 1106-1115.
Khan, F. N., & Govil, K. (2013a). Cost Optimization Technique of Task Allocation in Heterogeneous Distributed Computing System. International Journal of Advanced Networking and Applications, 5(3), 1913.
Khan, F. N., & Govil, K. (2013b). Static Approach for Efficient Task Allocation in Distributed Environment. International Journal of Computer Applications, 81(15), 19-22.
Menghani, G. (2010). A fast genetic algorithm based static heuristic for scheduling independent tasks on heterogeneous systems. Paper presented at the Parallel Distributed and Grid Computing (PDGC), 2010 1st International Conference on.
Neelakantan, P., & Sreekanth, S. (2016). Task allocation in distributed systems. Indian Journal of Science and Technology, 9(31).
Sharma, G., & Martin, J. (2009). MATLAB®: a language for parallel computing. International Journal of Parallel Programming, 37(1), 3-36.
Shatz, S. M., Wang, J.-P., & Goto, M. (1992). Task allocation for maximizing reliability of distributed computer systems. IEEE Transactions on Computers, 41(9), 1156-1168.
Srinivasan, S., & Jha, N. K. (1999). Safety and reliability driven task allocation in distributed systems. IEEE transactions on Parallel and Distributed Systems, 10(3), 238-251.
Stone, H. S. (1977). Multiprocessor scheduling with the aid of network flow algorithms. IEEE transactions on Software Engineering(1), 85-93.
Sudholt, D. (2015). Parallel evolutionary algorithms Springer Handbook of Computational Intelligence (pp. 929-959): Springer.
Tyagi, R., & Gupta, S. K. (2018). A Survey on Scheduling Algorithms for Parallel and Distributed Systems Silicon Photonics & High Performance Computing (pp. 51-64): Springer.
Vidyarthi, D. P., & Tripathi, A. K. (2001). Maximizing reliability of distributed computing system with task allocation using simple genetic algorithm. Journal of Systems Architecture, 47(6), 549-554.
Wu, J. (2017). Distributed system design: CRC press.
Yadav, P., Singh, M., & Sharma, K. (2011). An optimal task allocation model for system cost analysis in heterogeneous distributed computing systems: A heuristic approach. International Journal of Computer Applications, 28(4), 30-37.
Yadav, P. K., Singh, M., & Sharma, K. (2011). Task Allocation Model for Reliability and Cost optimization in Distributed Computing System. International Journal Of Modeling, Simulation, and Scientific Computing, 2(02), 131-149.
Zhang, X.-Y., Zhang, J., Gong, Y.-J., Zhan, Z.-H., Chen, W.-N., & Li, Y. (2016). Kuhn–Munkres parallel genetic algorithm for the set cover problem and its application to large-scale wireless sensor networks. IEEE Transactions on Evolutionary Computation, 20(5), 695-710.
_||_
