Cellular automata approach to task scheduling

• Autorzy: Święcicka A. , Seredyński F.
• Języki publikacji: EN

Abstrakty

EN

In this paper we propose using cellular automata (CAs) to perform distributed scheduling tasks of a parallel program in the two processor system. We consider a program graph as a CA with elementaty cells interacting locally according to a certain rule which must be found. Effective rules for a CA are discovered by a genetic algorithm (GA). With these rules, CA-based scheduler is able to find allocations which minimize the total execution time of the program in the two processor system. We also show a possibility of reusing knowledge gained during solving instances of the scheduling problem. Keywords: cellular automata, genetic algorithms, scheduling problem.

Słowa kluczowe

EN

cellular automata; genetic algorithms; scheduling problem

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2003
• Tom: Vol. 1(1)
• Strony: 37--46
• Opis fizyczny: Bibliogr. 15 poz., rys., tab., wykr.

Twórcy

autor

Święcicka A.

• Computer Science Department, Białystok University of Technology

autor

Seredyński F.

• The University of Podlasie, Computer Science Department, Institute of Computer Science, Polish Academy of Sciences

Bibliografia

• [Błaż88] Błażewicz, J.: Złożoność obliczeniowa problemów kombinatorycznych. Wydawnictwa Naukowo-Techniczne, Warszawa, 1988.
• [Das94] R. Das, M. Mitchell, J.P. Crutchfield: A Genetic Algorithm Discovers Particle-Based Computation in Cellular Automata. In Y. Davidor, H.-P. Schwefel, R. Männer (eds.), Parallel Problem Solving from Nature-PPSN III, LNCS 866, Springer, 344-353, 1994.
• [ElRew94] El-Rewini, H., Lewis, T. G., Ali, H. H.: Task Scheduling in Parallel and Distributed Systems. PTR Prentice Hall, Englewood Cliffs, New Jersey, 1994.
• [Gar79] Gary, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
• [Kwo96] Kwok, Y.-K., Ahmad, I.: Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors. IEEE Transactions on Parallel and Distributed Systems, Vol. 7, No. 5, 506-521,1996.
• [Kwo97] Kwok, Y.-K., Ahmad, I.: Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. Journal of Parallel and Distributed Computing 47, No. 1, 58-77, 1997.
• [Nab95] Nabhan, T. M., Zomaya, A. Y.: A parallel simulated annealing algorithm with low communication overhead. IEEE Transactions on Parallel and Distributed Systems 6, No. 12, 1226-1233, 1995.
• [Sal98] Salleh, S., Zomaya, A. Y.: Multiprocessor Scheduling Using Mean-Field Annealing. Parallel and Distributed Processing, LNCS 1388, 288-296, Springer, 1998.
• [Ser98] Seredyński, F.: Discovery with Genetic Algorithm Scheduling Strategies for Cellular Automata. Parallel Problem Solving from Nature PPSN V, LNCS 1498, A. E. Eiben, T. Back, M. Schoenauer and H.-P. Schwefel (eds.), Springer, 643-65, 1998.
• [Sip97] M. Sipper, Evolution of Parallel Cellular Machines, LNCS 1194, Springer, 1997.
• [SwSOOa] A. Święcicka, F. Seredyński, Evolving Cellular Automata Structures to Solve Multiprocessor Scheduling Problem, Intelligent Information Systems IX, Proceedings of the Workshop held in Bystra, Poland, June 12-16, 115-119, 2000.
• [SwSOOb] A. Święcicka, F. Seredyński, Cellular Automata Approach to Scheduling Problem, PARELEC 2000 International Conference on Parallel Computing in Electrical Engineering, Trois-Rivieres, Quebec, Canada, August 27-30, 29-33, 2000.
• [SSJ01] A. Święcicka, F. Seredyński, M. Jażdżyk, Cellular Automata Approach to Scheduling Problem in Case of Modifications of a Program Graph, Intelligent Information Systems X, Proceedings of the Workshop held in Zakopane, Poland, June 18-21, 155-166, 2001.
• [SSL98] A. Święcicka, F. Seredyński, K. Łuszczyk, Cellular Automata-Based Multiprocessor Scheduling, PARELEC’98 International Conference on Parallel Computinq in Electrical Engineering, Białystok, September 2-5, 264-268, 1998.
• [Wolf84] S. Wolfram, Universality and complexity in cellular automata, Physica D, 10, 1984, pp. 1-35.