PEDECIBA INFORMÁTICA TESIS DE DOCTORADO EN INFORMÁTICA - PDF

Description
PEDECIBA INFORMÁTICA Instituto de Computación, Facultad de Ingeniería Universidad de la República Montevideo, Uruguay TESIS DE DOCTORADO EN INFORMÁTICA Parallel evolutionary algorithms for scheduling on

Please download to get full document.

View again

of 122
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Devices & Hardware

Publish on:

Views: 18 | Pages: 122

Extension: PDF | Download: 0

Share
Transcript
PEDECIBA INFORMÁTICA Instituto de Computación, Facultad de Ingeniería Universidad de la República Montevideo, Uruguay TESIS DE DOCTORADO EN INFORMÁTICA Parallel evolutionary algorithms for scheduling on heterogeneous computing and grid environments Sergio Nesmachnow Abril de 2010 Supervisores: Enrique Alba, Héctor Cancela Tribunal: Celso Ribeiro, El-Ghazali Talbi (revisores), Irene Loiseau, Alberto Pardo, María Urquhart Parallel evolutionary algorithms for scheduling on heterogeneous computing and grid environments Nesmachnow, Sergio ISSN Tesis de Doctorado en Informática Reporte Técnico RT PEDECIBA Instituto de Computación - Facultad de Ingeniería Universidad de la República Montevideo, Uruguay, abril de 2010 Parallel evolutionary algorithms for scheduling on heterogeneous computing and grid environments Abstract This thesis studies the application of sequential and parallel evolutionary algorithms to the scheduling problem in heterogeneous computing and grid environments, a key problem when executing tasks in distributed computing systems. Since the 1990 s, this class of systems has been increasingly employed to provide support for solving complex problems using high-performance computing techniques. The scheduling problem in heterogeneous computing systems is an NP-hard optimization problem, which has been tackled using several optimization methods in the past. Among many new techniques for optimization, evolutionary computing methods have been successfully applied to this class of problems. In this work, several evolutionary algorithms in their sequential and parallel variants are specifically designed to provide accurate solutions for the problem, allowing to compute an efficient planning for heterogeneous computing and grid environments. New problem instances, far more complex than those existing in the related literature, are introduced in this thesis in order to study the scalability of the presented parallel evolutionary algorithms. In addition, a new parallel micro-chc algorithm is developed, inspired by useful ideas from the multiobjective optimization field. Efficient numerical results of this algorithm are reported in the experimental analysis performed on both well-known problem instances and the large instances specially designed in this work. The comparative study including traditional methods and evolutionary algorithms shows that the new parallel micro-chc is able to achieve a high problem solving efficacy, outperforming previous results already reported for the problem and also having a good scalability behavior when solving high dimension problem instances. In addition, two variants of the scheduling problem in heterogeneous environments are also tackled, showing the versatility of the proposed approach using parallel evolutionary algorithms to deal with both dynamic and multiobjective scenarios. Keywords: Parallel evolutionary algorithms, Scheduling, Heterogeneous computing, Grid computing ii Algoritmos evolutivos paralelos para planificación de tareas en entornos heterogéneos Resumen Esta tesis estudia la aplicación de algoritmos evolutivos secuenciales y paralelos para el problema de planificación de tareas en entornos de cómputo heterogéneos y de computación grid. Desde la década de 1990, estos sistemas computacionales han sido utilizados con éxito para resolver problemas complejos utilizando técnicas de computación de alto desempeo. El problema de planificación de tareas en entornos heterogéneos es un problema de optimización NP-difícil que ha sido abordado utilizando diversas técnicas. Entre las técnicas emergentes para optimización combinatoria, los algoritmos evolutivos han sido aplicados con éxito a esta clase de problemas. En este trabajo, varios algoritmos evolutivos en sus versiones secuenciales y paralelas han sido específicamente diseados para alcanzar soluciones precisas para el problema de planificación de tareas en entornos de heterogéneos, permitiendo calcular planificaciones eficientes para entornos que modelan clusters de computadores y plataformas de computación grid. Nuevas instancias del problema, con una complejidad mucho mayor que las previamente existentes en la literatura relacionada, son presentadas en esta tesis con el objetivo de analizar la escalabilidad de los algoritmos evolutivos propuestos. Complementariamente, un nuevo método, el micro-chc paralelo es desarrollado, inspirado en ideas útiles provenientes del área de optimización multiobjetivo. Resultados numéricos precisos y eficientes se reportan en el análisis experimental realizado sobre instancias estándar del problema y sobre las nuevas instancias específicamente diseadas en este trabajo. El estudio comparativo que incluye a métodos tradicionales para planificación de tareas, los nuevos métodos propuestos y algoritmos evolutivos previamente aplicados al problema, demuestra que el nuevo micro-chc paralelo es capaz de alcanzar altos valores de eficacio, superando a los mejores resultados previamente reportados en la literatura del área y mostrando un buen comportamiento de escalabilidad para resolver las instancias de gran dimensión. Además, dos variantes del problema de planificación de tareas en entornos heterogéneos han sido inicialmente estudiadas, comprobándose la versatilidad del enfoque propuesto para resolver las variantes dinámica y multiobjetivo del problema. Palabras clave: Algoritmos evolutivos paralelos, Planificación de tareas, Computación heterogénea, Computación grid Contents 1 Introduction 3 2 Parallel evolutionary algorithms Introduction Evolutionary algorithms Genetic algorithm CHC algorithm Parallel evolutionary algorithms Master-slave PEAs Cellular PEAs Distributed subpopulations PEAs Parallel micro-chc algorithm Summary Scheduling in heterogeneous computing environments Heterogeneous computing HCSP formulation Problem model considerations HCSP computational complexity Execution time estimation Expected time to compute estimation model Methods for generating ETC scenarios HCSP instances Instances from Braun et al. (2001) Grid infrastructures New HCSP instances Static scheduling using execution time estimation Traditional scheduling heuristics Metaheuristics for scheduling using ETC Summary Related work: EAs for HC scheduling Introduction : HSCP on multiprocessors : HCSP on distributed environments : Heterogeneous grid scheduling Summary iii iv CONTENTS 5 Parallel evolutionary algorithms for the HCSP The MALLBA library Problem encoding Fitness function Population initialization Evolutionary operators Exploitation: recombination Exploration: mutation and reinitialization Local search: randomized PALS Speeding up the pµ-chc search Accelerated convergence in pµ-chc Parallel model of pµ-chc Summary Experimental analysis HCSP instances Development and execution platform Parameter settings Stopping criterion Population size Operators probabilities Parallel algorithms Probabilities within the evolutionary operators Summary: best parameter configurations Results and discussion Results for HCSP instances from Braun et al. (2001) Results for the new large-sized HCSP instances Parallel CHC Parallel micro-chc Comparison with lower bounds for the preemptive HCSP Small HCSP instances New large HCSP instances Summary Tracking the makespan evolution and the execution time Comparative makespan evolution of CHC algorithms Makespan evolution and execution time of pµ-chc Scalability analysis and parallel performance Parallel CHC Parallel micro CHC Summary Two HCSP variants: rescheduling and multiobjective approach Introduction Dynamic HCSP: rescheduling with pµ-chc Dynamic HCSP model Rescheduling algorithms Experimental analysis Concluding remarks CONTENTS v 7.3 Multiobjective HCSP: makespan and flowtime Introduction Multiobjective optimization problems Multiobjective HCSP formulation Multiobjective evolutionary algorithms MOEAs for the HCSP Experimental analysis Concluding remarks Summary Conclusions and future work Conclusions Future work A HCSP instances generator and test suites 119 A.1 HCSP instances generator A.2 Test suites B Best solutions for the HCSP test suite from Braun et al. (2001) 127 C Related publications by the author 133 Bibliography 135 List of Figures 2.1 Diagram of a master slave PEA Diagram of a cellular PEA Diagram of a distributed subpopulation PEA Scheduling in an HC environment Details of the HCSP instances generator Format of the HCSP instance files Timeline of EAs applied to the HCSP UML for MALLBA classes Task oriented encoding Machine oriented encoding Two-level parallel model used in pµ-chc Analysis of the operators probabilities (sequential algorithms, u i hilo.0) Analysis of the operators probabilities (parallel algorithms) Sample results when configuring the number of subpopulations in pchc Sample results when configuring the number of subpopulations in pµ-chc Comparison of pchc against the best-known methods for the HCSP pchc improvement over traditional heuristics pµ-chc improvements with respect to deterministic heuristics pµ-chc improvements regarding the consistency classification pµ-chc improvements with respect to pchc HCSP scenario specification in GMPL/AMPL Relationship between GAP(optimum) and GAP(LB) pµ-chc improvements with respect to the best deterministic heuristic results and the computed lower bounds for HCSP instances by Braun et al. (2001) pµ-chc improvements with respect to the best deterministic heuristic result and the computed lower bounds for the preemptive HCSP version Makespan evolution for CHC algorithms on u i hihi Makespan evolution for CHC algorithms on u s lohi Evolution of the makespan improvement ratio for pµ-chc Execution times required to achieve a given improvement threshold Scalability analysis for pchc Parallel performance and scalability of pchc Scalability analysis for pµ-chc vii viii LIST OF FIGURES 6.21 Scalability and parallel performance analysis for pµ-chc Rescheduling in a dynamic scenario Pareto fronts for consistent HCSP instances Pareto fronts for inconsistent HCSP instances Pareto fronts for semiconsistent HCSP instances List of Tables 3.1 Heterogeneity and consistency combinations in the ETC model Parameters of ETC models Details of sampled grid and volunteer distributed computing platforms Summary of metaheuristic methods applied to solve the HCSP EAs applied to the HSCP Sample results when configuring the number of subpopulations in pchc Sample results when configuring the number of subpopulations in pµ-chc Best parameter configurations (sequential algorithms) Best parameter configurations (parallel algorithms) Results of the sequential EAs for the HCSP Comparative results: sequential EAs vs. deterministic heuristics Comparative results: sequential EAs vs. previous EAs for the HCSP Results of parallel EAs for the HCSP Improvement factors and statistical analysis when using parallel CHC pchc and other methods for HCSP instances by Braun et al. (2001) Results of pµ-chc for HCSP instances from Braun et al. (2001) pµ-chc improvement factors over pchc pµ-chc and other methods for HCSP instances by Braun et al. (2001) pchc results for new HCSP instances with dimension pchc results for new HCSP instances with dimension pchc results for new HCSP instances with dimension pchc results for new HCSP instances with dimension pchc improvements over traditional heuristics pµ-chc results for new HCSP instances with dimension pµ-chc results for new HCSP instances with dimension pµ-chc results for new HCSP instances with dimension pµ-chc results for new HCSP instances with dimension pµ-chc improvements regarding the consistency classification pchc and pµ-chc comparative results for new HCSP instances pµ-chc improvements with respect to pchc pµ-chc comparison with lower bounds (dimension ) Comparison between pµ-chc results and lower bounds calculated for the preemptive HCSP (large instances) Summary: gaps between pµ-chc results and lower bounds for the preemptive HCSP version ix x LIST OF TABLES 6.29 Trade-off between solution quality and execution time (pchc and pµ- CHC) Makespan results of pµ-chc and Min-Min for the dynamic HCSP Improvements of pµ-chc using the rescheduling strategy over the traditional pµ-chc and the two Min-Min variants Results of MOEAs for the multiobjective HCSP Efficacy metrics of MOEAs for the multiobjective HCSP Diversity metrics of MOEAs for the multiobjective HCSP Comparison of MOE-NSGA-II and pµ-chc against previous evolutionary techniques for the multiobjective HCSP Summary of the main experimental results Acknowledgments The research project reported in this thesis would not have been possible without the scientific, personal, and financial support of many people and organizations. I would like to express my gratitude to my supervisors Héctor Cancela and Enrique Alba for guiding the research, and providing their helpful orientation, support and assistance in writing reports and publications. Very special thanks to all my partners at Centro de Cálculo and Instituto de Computación, Facultad de Ingeniería, Universidad de la República, specially my buddies at CeCal: Eduardo Fernández, Pablo Ezzatti, Martín Pedemonte, and Gerardo Ares; and IO: Franco Robledo, Alfredo Olivera, and Antonio Mauttone. Also thanks to all the good friends at Networking and Emerging Optimization, Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, España: Francisco Luna, Jamal Toutouh, José Manuel García Nieto, Juan José Durillo, Guillermo Molina, Gabriel Luque, and Francisco Chicano. Darío De León and Alexis Rodríguez worked in graduate projects related with the research reported in this thesis, and their work was useful for specific parts of the study. I would like to thank all my family and friends who helped me get through all these years of Ph.D. studies, particularly when far away from home: mom and dad, Ale, my beloved Marcela, Auro and Aurora, and my good friends Chomba, Andrea, Raúl, and Paula. A special gratitude to Fefi, who assisted me with the thesis correction process. I also acknowledge to several unknown reviewers of the related publications that provided helpful comments to improve the content of this thesis. The research was partially supported by Comisión Sectorial de Investigación Científica (CSIC), Universidad de la República, Uruguay; Programa de Desarrollo de las Ciencias Básicas (PEDECIBA), Universidad de la República, Uruguay; and Agencia Nacional de Investigación e Innovación (ANII), Uruguay. 1 Chapter 1 Introduction In the last fifteen years, the fast increase of the processing power of low-cost computers and the rapid development of high-speed networking technologies have boosted the use of distributed computing environments for solving complex problems. Starting from small clusters of homogeneous computers in the 1980 s, as for today distributed computing environments include platforms formed by hundreds or thousands of heterogeneous computing resources widespread around the globe, providing the computing power needed for solving complex problems arising in many areas of application. Nowadays, a common platform for distributed computing usually comprises a heterogeneous collection of computers able to work cooperatively. At a higher level of abstraction, the expression grid computing has become popular to denote the set of distributed computing techniques that work over a large loosely-coupled virtual supercomputer, formed by combining together many heterogeneous components of different characteristics and computing power. This infrastructure has made it feasible to provide pervasive and costeffective access to a collection of distributed computing resources for solving problems that demand large computing power (Foster and Kesselman, 1998). A crucial problem when using such heterogeneous computing (HC) environments consists in finding a planning strategy or scheduling for a set of tasks to be executed. The goal of the scheduling problem is to optimally assign the computing resources by satisfying some efficiency criteria, usually related to the total execution time or resource utilization. Frequently, the scheduling strategy is devoted to optimize the makespan, a metric that quantifies the total execution time of the tasks in the system, even though alternative metrics have also been taken into account in many scheduling problem variants (e.g. flowtime, that evaluates the sum of the finishing times of the tasks, and several other metrics related to the resources utilization). Scheduling problems on multiprocessor systems have been widely studied in operational research, and numerous methods have been proposed for finding accurate schedules in reasonable times (El-Rewini et al., 1994; Leung et al., 2004). In their classic formulation, scheduling problems assume a computing environment composed by homogeneous resources. However, in the 1990 s decade the research community started to pay attention to scheduling problems on HC environments, specially due to the popularization of distributed computing and the growing use of heterogeneous clusters (Freund et al., 1994; Eshaghian, 1996). In the last ten years, significant effort has been made to study the scheduling problem on HC environments, since this platform provides the efficiency required for distributed and grid computing techniques. 3 4 Introduction Traditional scheduling problems are NP-hard (Garey and Johnson, 1979), thus classic exact methods are only useful for solving problem instances of reduced size. The research community has been searching for new scheduling techniques that are able to improve upon the traditional exact ones, whose low efficiency often makes them useless in practice for solving large-dimension scheduling problems in reasonable times. When dealing with large-dimension computing environments, ad-hoc heuristic and metaheuristic techniques have shown up as promising methods for solving the HC and grid scheduling problems. Although these methods do not guarantee success in computing an optimal solution for the problem, they get appropriate quasi-optimal schedules that usually satisfy the efficiency requirements for real-life scenarios, in reasonable times. Among a broad set of modern metaheuristic techniques for optimization, evolutionary algorithms (EAs) (Bäck et al., 1997) have emerged as flexible and robust methods for solving the heterogeneous computing scheduling problem (HCSP), achieving the high level of problem solving efficacy also shown in many other areas of application. Although they usually require longer execution times in the order of few minutes than ad-hoc heuristics, EAs consistently find better solutions than ad-hoc heuristic methods, so they are competitive schedulers for distributed HC and grid systems where large tasks with execution times in the order of minutes, hours, and even days are submitted for execution (Braun et al., 2001; Tupcouglu et al., 2002). In order to further improve the efficiency of EAs, parallel implementations became a popular option to speed up the search, allowing to reach high quality results in a reasonable execution time even for hard-to-solve optimization problems (Cantú-Paz, 2000; Alba, 2005). EAs and other metaheuristics have been frequently applied to the HCSP and related problem variants in the last ten years. The most relevant proposals included Genetic Algorithms (GA) (Wang et al., 1997; Braun et al., 2001; Zomaya and Teh, 2001; Page and Naughton, 2005; Xhafa et al., 2008c), Memetic Algorithms (MA) (Xhafa, 2007), cellular MA (cma) (Xhafa et al., 2008a), and also hybrid methods combining EAs with other optimization techniques. Two relevant works have obtained the best-known results when facing a set of low-sized de-facto standard HCSP instances using non-evolutionary metaheuristics: an hybrid combining Ant Colony Optimization (ACO) and T
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks