Algoritmos Genéticos para Escalonamento de Processadores
Resumo
ln its generic formulation, processor scheduling is a NP-Complete problem. Many different approaches have been proposed to the scheduling problem and one of them is the use of Genetic Algorithms (GA). These algorithms work using an analogy with living beings, mimicking their ability to adapt to the environment. The aim of this paper is to present a tentative of classification of GAbased processor schedulers and describe some of the results achieved and some aspects of GA that can interfere with the quality of the results.
Palavras-chave:
Processor scheduling, genetic algorithms
Referências
ADAM, Thomas; CHANDY, K.M.; DICKSON, J. R. A comparison of list schedules for Parallel processing Systems, CACM, 17: 12 (1974), 685-690.
ALBA, Enrique; ALDANA, J.F.; TROYA, José, M. Load Balancing and Query Optimization in Dataflow Parallel Evaluation of Datalog Programs, Proceedings of the 1994 lnternational Conference on Parallel and Distributed Systems, Lionel M. Ni (ed.), IEEE Computer Society Press, pp. 682-688, 1994
BAUMGARTNER, Joey; COOK, Diane, J. A. genetic algorithm for load balancing in parallel computers. In Proceedings of the Seventh lnternational Conference on Industrial and Engineering Applications of Artificial lntelligence and Expert Systems, pages 619-628, 1994.
BAUMGARTNER, Joey; COOK, Diane. J. A.; SHIRAZI, Behrooz, Genetic solutions to the load balancing problem. Proc of ICPP 95 Workshop, pp 72-78.
BOER, Bart de, Classifier System: A Useful Approach to Machine Learning ?, Master's Thesis, Leiden University, 1994
CANTÚ-PAZ, Erick Designing Efficient and Accurate Parallel Genetic Algorithms IlliGal Report No. 99017 July 1999 Illinois Genetic Algorithms Laboratory
CORRÊA, Ricardo C.; FERREIRA, Afonso; REBREYEND, Pascal Scheduling Multipocessors Tasks with Genetic Algorithms, IEEE Transaction On Parallel and Distribute Systems, Vol 10, No.8, pp 825-837 August 1999
DHODDI, Muhammad K.; AHMAD, lmtiaz; STORER, Robert. Shemus: synthesis of heterogeneous multiprocessor systems. Microprocessors and Microsystems. 19(6):pp 311-319, 1995
DODD, N. Optimisation of network structure using genetic techniques. In Proceedings of the International Joint Conference on Neural Networks, pages 965-970, 1990
DUSSA-ZIEGER. Klaudia; SCHWEHM, Markus Scheduling of Parallel Programs on Configurable Multiprocessors by Genetic Algorithms, Journal of Approximate Reasoning, Special Issue on 'Approximative Methods in Scheduling', Vol 19 (1-2) 23-38, 1998
GAREY, Michael R.; JOHNSON. David S. Computers and lntractabilily: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.
GOLDBERG. David E. Genetic Algorithms in Search. Optimization, and Machine Learning. AddisonWesley Publishing Company, 1989.
GRAJCAR. Martin Genetic List Scheduling Algorithm for Scheduling and Allocation on a Loosely Coupled Heterogeneous Multiprocessor System; Proceedings of the 36th Design Automation Conference (DAC), p. 280-285, New Orleans, 1999. ISBN 0-7803-5560-1
GREFENSTETTE, John J. Conditions for implicit parallelism. In Foundations of Genetic Algorithms, G. J. E. Rawlins (ed.), Bloomington, IN: Morgan Kaufmann. (199la)
HIRONORI Kasahara; SEINOSUKE Narita. Parallel processing of robot-arm contrat computation ona multiprocessor system. IEEE Journal of Robotics and Automation, RA-1(2):pp104-113, 1985.
DE JONG, Kenneth A.; SPEARS, Willian M. Using genetic algorithms to solve NP-complete problems, Proc. 3rd lnt'nl Conf. Genet. Algorithms, Morgan Kaufmann, 1989, 124-132.
KREMIEN. O.; KRAMER, J. Methodical analysis of adaptive load sharing algorithms. IEEE Transactions on Parallel and Distributed Systems. 3(6):747-760, November 1992.
KWOK, Yu-Kwong; AHMAD, lshfaq, Efficient Scheduling of Arbitrary Task Graphs to Multiprocessors Using A Parallel Genetic Algorithm, Journal of Parallel and Distributed Computing, vol. 47, no. 1, pp. 58-77, November 1997.
KWOK, Yu-Kwong, AHMAD, lshfaq, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, vol. 7. no. 5, pp. 506-521. May 1996.
MACDOUGALL, M. H. Simulaling Computer Systems : Techniques and Tools. The MIT Press, 1987
MICHALEWICZ. Zbigniew. Genetic Algorithms+Data Structures=Evolution Programs, 3rd edition. Springer, 1996.
PRAKASH, S.; PARKER, A. C. SOS: synthesis of application-specific heterogeneous multiprocessor systems, Journal of Parallel and Distributed Computing, vol. 16, no. 4, pp. 38-51, 1992
REBREYEND, P. SANDNES, F. E.; MEGSON, G. M. Static Mulliprocessor Task Graph Scheduling in the Genetic Paradigm: A Comparison of Genotype Representations, Laboratoire de l'Informatique du Parallelisme ' Ecole Normale Sup'erieure de Lyon, Research Report N. 98-25, 1998
SANDNES, F.E.; MEGSON, G.M. lmproved Static Multiprocessor Scheduling Using Cyclic Task Graphs - A Genetic Approach. IPPS'97 Workshop on Randomised Parallel Computing, 1997.
SCHWEHM, Markus; WALTER, Thomas (1994): Mapping and Scheduling by Genetic Algorithms, In: Buchberger, B. and Yolkert, J. (Eds.): Parallel Processing: CONPAR 94 - VAPP VI'Third Joint Int. Conf. Vector and Parallel Processing in Linz, Austria, September 1994, Springer Yerlag, LNCS 854, pp. 832-841
SPEARS, Willian M. Adapting Crossover in Evolutionary Algorithms, in Proceedings of 4th Annual Conf on Evolutionary Computing, ed Fogel, 1995, MIT Press.
SRINIYAS, M.; PATNAIK, L.M. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms, IEEE Trans. Sys .. Man and Cybernetics, vol. 24, no. 4, Apr. 1994, pp. 656-667.
SUNG-HO, Woo; SUNG-BONG Yang; SHIN-DUG, Kim; Tack-Don Han, Task scheduling in distributed computing systems with a genetic algorithm , Proceedings of the High-Performance Computing on the lnformation Superhighway, HPC-Asia '97, 1997
TANESE, Reiko. Distributed Genetic Algorithm for Function Optimization. PhD. dissertation. Department of Electrical Engineering and Computer Science. University of Michigan, 1989
WOLPERT, David H.; MACREADY, Willian G. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, April 1996.
YANG, Tao; GERASOULIS, Apostolos, "A Fast Static Scheduling Algorithm for DAGs on an Unbounded Number of Processors", Proceedings of Supercomputing 91, pages 633-642. Albuquerque, 1991.
ZHOU, Songnian. A Trace-driven simulation study of dynamic load balancing. Technical Report UCB/CSD 87/305, University of California, Berkely, 1986.
ALBA, Enrique; ALDANA, J.F.; TROYA, José, M. Load Balancing and Query Optimization in Dataflow Parallel Evaluation of Datalog Programs, Proceedings of the 1994 lnternational Conference on Parallel and Distributed Systems, Lionel M. Ni (ed.), IEEE Computer Society Press, pp. 682-688, 1994
BAUMGARTNER, Joey; COOK, Diane, J. A. genetic algorithm for load balancing in parallel computers. In Proceedings of the Seventh lnternational Conference on Industrial and Engineering Applications of Artificial lntelligence and Expert Systems, pages 619-628, 1994.
BAUMGARTNER, Joey; COOK, Diane. J. A.; SHIRAZI, Behrooz, Genetic solutions to the load balancing problem. Proc of ICPP 95 Workshop, pp 72-78.
BOER, Bart de, Classifier System: A Useful Approach to Machine Learning ?, Master's Thesis, Leiden University, 1994
CANTÚ-PAZ, Erick Designing Efficient and Accurate Parallel Genetic Algorithms IlliGal Report No. 99017 July 1999 Illinois Genetic Algorithms Laboratory
CORRÊA, Ricardo C.; FERREIRA, Afonso; REBREYEND, Pascal Scheduling Multipocessors Tasks with Genetic Algorithms, IEEE Transaction On Parallel and Distribute Systems, Vol 10, No.8, pp 825-837 August 1999
DHODDI, Muhammad K.; AHMAD, lmtiaz; STORER, Robert. Shemus: synthesis of heterogeneous multiprocessor systems. Microprocessors and Microsystems. 19(6):pp 311-319, 1995
DODD, N. Optimisation of network structure using genetic techniques. In Proceedings of the International Joint Conference on Neural Networks, pages 965-970, 1990
DUSSA-ZIEGER. Klaudia; SCHWEHM, Markus Scheduling of Parallel Programs on Configurable Multiprocessors by Genetic Algorithms, Journal of Approximate Reasoning, Special Issue on 'Approximative Methods in Scheduling', Vol 19 (1-2) 23-38, 1998
GAREY, Michael R.; JOHNSON. David S. Computers and lntractabilily: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.
GOLDBERG. David E. Genetic Algorithms in Search. Optimization, and Machine Learning. AddisonWesley Publishing Company, 1989.
GRAJCAR. Martin Genetic List Scheduling Algorithm for Scheduling and Allocation on a Loosely Coupled Heterogeneous Multiprocessor System; Proceedings of the 36th Design Automation Conference (DAC), p. 280-285, New Orleans, 1999. ISBN 0-7803-5560-1
GREFENSTETTE, John J. Conditions for implicit parallelism. In Foundations of Genetic Algorithms, G. J. E. Rawlins (ed.), Bloomington, IN: Morgan Kaufmann. (199la)
HIRONORI Kasahara; SEINOSUKE Narita. Parallel processing of robot-arm contrat computation ona multiprocessor system. IEEE Journal of Robotics and Automation, RA-1(2):pp104-113, 1985.
DE JONG, Kenneth A.; SPEARS, Willian M. Using genetic algorithms to solve NP-complete problems, Proc. 3rd lnt'nl Conf. Genet. Algorithms, Morgan Kaufmann, 1989, 124-132.
KREMIEN. O.; KRAMER, J. Methodical analysis of adaptive load sharing algorithms. IEEE Transactions on Parallel and Distributed Systems. 3(6):747-760, November 1992.
KWOK, Yu-Kwong; AHMAD, lshfaq, Efficient Scheduling of Arbitrary Task Graphs to Multiprocessors Using A Parallel Genetic Algorithm, Journal of Parallel and Distributed Computing, vol. 47, no. 1, pp. 58-77, November 1997.
KWOK, Yu-Kwong, AHMAD, lshfaq, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, vol. 7. no. 5, pp. 506-521. May 1996.
MACDOUGALL, M. H. Simulaling Computer Systems : Techniques and Tools. The MIT Press, 1987
MICHALEWICZ. Zbigniew. Genetic Algorithms+Data Structures=Evolution Programs, 3rd edition. Springer, 1996.
PRAKASH, S.; PARKER, A. C. SOS: synthesis of application-specific heterogeneous multiprocessor systems, Journal of Parallel and Distributed Computing, vol. 16, no. 4, pp. 38-51, 1992
REBREYEND, P. SANDNES, F. E.; MEGSON, G. M. Static Mulliprocessor Task Graph Scheduling in the Genetic Paradigm: A Comparison of Genotype Representations, Laboratoire de l'Informatique du Parallelisme ' Ecole Normale Sup'erieure de Lyon, Research Report N. 98-25, 1998
SANDNES, F.E.; MEGSON, G.M. lmproved Static Multiprocessor Scheduling Using Cyclic Task Graphs - A Genetic Approach. IPPS'97 Workshop on Randomised Parallel Computing, 1997.
SCHWEHM, Markus; WALTER, Thomas (1994): Mapping and Scheduling by Genetic Algorithms, In: Buchberger, B. and Yolkert, J. (Eds.): Parallel Processing: CONPAR 94 - VAPP VI'Third Joint Int. Conf. Vector and Parallel Processing in Linz, Austria, September 1994, Springer Yerlag, LNCS 854, pp. 832-841
SPEARS, Willian M. Adapting Crossover in Evolutionary Algorithms, in Proceedings of 4th Annual Conf on Evolutionary Computing, ed Fogel, 1995, MIT Press.
SRINIYAS, M.; PATNAIK, L.M. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms, IEEE Trans. Sys .. Man and Cybernetics, vol. 24, no. 4, Apr. 1994, pp. 656-667.
SUNG-HO, Woo; SUNG-BONG Yang; SHIN-DUG, Kim; Tack-Don Han, Task scheduling in distributed computing systems with a genetic algorithm , Proceedings of the High-Performance Computing on the lnformation Superhighway, HPC-Asia '97, 1997
TANESE, Reiko. Distributed Genetic Algorithm for Function Optimization. PhD. dissertation. Department of Electrical Engineering and Computer Science. University of Michigan, 1989
WOLPERT, David H.; MACREADY, Willian G. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, April 1996.
YANG, Tao; GERASOULIS, Apostolos, "A Fast Static Scheduling Algorithm for DAGs on an Unbounded Number of Processors", Proceedings of Supercomputing 91, pages 633-642. Albuquerque, 1991.
ZHOU, Songnian. A Trace-driven simulation study of dynamic load balancing. Technical Report UCB/CSD 87/305, University of California, Berkely, 1986.
Publicado
25/10/2000
Como Citar
CORRÊA, Jan Mendonça; MELO, Alba Cristina.
Algoritmos Genéticos para Escalonamento de Processadores. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 1. , 2000, São Pedro/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2000
.
p. 21-26.
DOI: https://doi.org/10.5753/wscad_estendido.2000.19138.
