تخصیص ایستای وظایف در سیستم‌های توزیع‌شده با استفاده از الگوریتم ژنتیک موازی
الموضوعات :
Monire Taheri Sarvetamin
1
(گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی واحد کرمان، کرمان، ایران)
الکلمات المفتاحية: الگوریتم ژنتیک سلولی, سیستم توزیع‌شده, تخصیص وظایف, الگوریتم ژنتیک موازی, الگوریتم ژنتیک جزیره‌ای,
ملخص المقالة :
در طی دو دهه اخیر، بالارفتن فوق‌العاده سرعت شبکه‌های رایانه ای و همچنین افزایش نیاز به سیستم‌هایی با کارایی بالا سبب شده است که محققان به پردازش‌های موازی و توزیع‌شده علاقه‌مند شوند. رشد سریع سیستم‌های توزیع‌شده باعث شده که مسائل گوناگونی در این زمینه مطرح شود. یکی از مهم‌ترین مسائلی که موردتوجه محققان زیادی قرارگرفته، مسئله تخصیص وظایف در این‌گونه محیط‌ها است که به‌منظور به دست آوردن بهره‌وری مؤثر از سیستم انجام می‌شود. مسئله تخصیص وظایف به‌جز در معدود موارد خاص جز مسائل NP-کامل است؛ بنابراین از فرایندهای اکتشافی برای دستیابی به راه‌حل‌های زیربهینه در مدت‌زمان مطلوب استفاده می‌شود. اگرچه از روش‌های مختلف در تحقیقات استفاده‌شده، اما هنوز پیدا کردن روش مؤثر و کارا برای این مشکل موردنیاز و مطلوب است. در این پژوهش از الگوریتم ژنتیک موازی برای پیدا کردن راه‌حل بهینه برای تخصیص یک گراف از وظایف به پردازنده‌ها در سیستم توزیع‌شده استفاده‌شده است. نتایج نشان داد الگوریتم پیشنهادی می‌تواند تخصیص‌های بهینه یا نزدیک بهینه برای مسائل با اندازه‌های گوناگون ارائه دهد. همچنین روش پیشنهادی توانست در زمان بسیار سریع‌تر از الگوریتم ژنتیک سنتی و با تسریع فراخطی، مسائل با اندازه‌های بزرگ و متوسط را حل کند.
المصادر:
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.
_||_
