Or-Parallel Scheduling Strategies Revisited
Resumo
Parallel logic programming systems have been studied for more than a decade. Techniques and scheduling strategies for or-parallel systems have been established for systems that run on centralised memory architectures. As new parallel platforms such as clusters of workstations or clusters of PCs gain populariry, these techniques vastly studied for centralised memory systems may become obsolete and inefficient. In this work we study several scheduling strategies commonly used in or-parallel systems designed for centralised memory architetcures. We simulate these strategies on different parallel environments in order to estimate the costs associated to these scheduling strategies in each environment. We use a benchmark set commonly studied by the or-parallel community. Our study concentrates on simulating top-most, bottom-most, and left-most strategies while modeling costs associated to centralised and distributed memory architectures. We then aimplement our own strategy that selects best work based on the costs to move to a piece of work. Our results show that depending on the characteristics of the search tree none of the three strategies: top, bottom or lefr-most can yield good results. Our proposed strategy based on taking minor costs tasks proved to produce better results than any of these fixed strategies, particulary for distributed-memory platforms.
Referências
Anthony Beaumont. Scheduling in Or-Parallel Prolog Systems. PhD thesis, University of Bristol, Department of Computer Science, in preparation, 1993.
Anthony Beaumont, S. Muthu Raman, and Péter Szeredi. Flexible Scheduling of Or-Parallelism in Aurora: The Bristol Scheduler. In Aarts, E. H. L. and van Leeuwen, J., and Rem, M., editors, PARLE’91: Conference on Parallel Architectures and Languages Europe, volume 2, pages 403–420. Springer Verlag, June 1991. Lecture Notes in Computer Science 506.
J. Briat, M. Favre, C. Geyer, and J. Chassin. Scheduling of Or-parallel Prolog on a Scalable, Reconfigurable, Distributed-Memory Multiprocessor. In Proceedings of Parallel Architecture and Languages Europe, Springer Verlag, 1991.
Adriana Marino Carrusca. Estudo de Estratégias de Escalonamento para Andorra-I. Master's thesis, COPPE/Sistemas, UFRJ, MSc thesis, in preparation, 1999.
A. P. Centeno and C. Geyer. Penelope – Um Modelo de Escalonador Hierárquico para o Sistemas Plosys. In X Simpósio Brasileiro de Arquitetura de Computadores, SBAC-PAD, Setembro 1998.
Ana Paula Bluhm Centeno. Penelope – Um Modelo de Escalonador Hierárquico para o Sistemas Plosys. Master's thesis, Universidade Federal do Rio Grande do Sul, Instituto de Informática, Curso de Pós-Graduação em Ciência da Computação, 1999.
William Clocksin. Principles of the DelPhi Parallel Inference Machine. Computer Journal, 30(5):386–392, 1987.
É. Morel, J. Briat, Chassin de Kergommeaux, and C. Geyer. Parallelism and Implementation of Logic and Constraint Logic Programming, chapter Side-effects in PloSys OR-parallel Prolog on Distributed Memory Machines. Nova Science, Inc., 1999.
K. Kumon et al. Kabu-Wake: A New Parallel Method and Its Evaluation. In Proceedings of CompCon 86, pages 168–172, 1986.
M. J. Fernández, M. Carro, and M. V. Hermenegildo. IDRA (Ideal Resource Allocation): A Tool for Computing Ideal Speedups. In ICLP’94 Pre-Conference Workshop on Parallel and Data-Parallel Execution of Logic Languages, Facultad de Informática, Universidad Politécnica de Madrid, June 1994.
Gopal Gupta and Enrico Pontelli. Stack-Splitting: A Simple Technique for Implementing Or-Parallelism and And-Parallelism on Distributed Machines. In Proceedings of the 1999 International Conference on Logic Programming, 1999.
Douglas R. Hofstadter. Gödel, Escher, Bach: an eternal golden braid. Harmondsworth: Penguin, 1980.
Ewing Lusk, David H. D. Warren, Seif Haridi, et al. The Aurora Or-parallel Prolog System. New Generation Computing, 7(2,3):243–271, 1990.
E. Morel, J. Briat, J. Chassin de Kergommeaux, and C. Geyer. Side Effects in PloSys OR-parallel Prolog on Distributed Memory Machines. In JICSLP’96 Post-Conference Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, Bonn, Germany, September 1996.
Kish Shen. An Investigation of the Argonne Model of Or-Parallel Prolog. Master's thesis, University of Manchester, 1986.
Kish Shen. Studies of And/Or Parallelism in Prolog. PhD thesis, Computer Laboratory, University of Cambridge, 1992.
Fernando M. A. Silva. Implementations of Logic Programming Systems, chapter Or-Parallelism on Distributed Shared Memory Architectures. Kluwer Academic Pub., 1994.
Raéd Yousef Sindaha. Branch-Level Scheduling in Aurora: The Dharma Scheduler. In Proceedings of the 1993 International Logic Programming Symposium, pages 403–419, October 1993.
K. Villaverde, H. Guo, E. Pontelli, and G. Gupta. Incremental Stack-Splitting: A Simple Technique for Implementing Or-Parallelism and And-Parallelism on Distributed Machines. In Proceedings of the Workshop on Parallelism and Implementation Technologies for (Constraint) Logic Programming Languages, 2000.
