Performance Analysis of a Strategy to Distribute And-work and Or-work in Parallel Logic Programming Systems

• Inês de Castro Dutra UFRJ

DOI: https://doi.org/10.5753/sbac-pad.1995.19880

Resumo

This paper studies the performance of Andorra-I, a parallel logic programming system that exploits and-parallelism and or-parallelism with a novel strategy to distribute and-work and or-work among processors. The strategy, work-guided guides it’s decisions by looking at the amount of current and-work and or-work avaliable in an application during execution. The scheduler decision strategy moves workers from one parallel task to another according to the tasks sizes. Results show that the work-guided strategy works quite well and produces better results than the ones produced with a version of Andorra-I that does not a flow dynamic migration of workers during execution. We believe that this strategy can be applied to other parallel logic programming systems that aim to exploit both and-and or-parallelism in a single framework.

Palavras-chave: and-or scheduling, and-or parallelism, logic programming, parallelism, Andorra-I, performance evaluation

Referências

Khayri A. M. Ali and Roland Karlsaon. The Muse or-parallel Prolog Model and its Performance. ln Proceedings of the 1990 North American Conference on Logic Programming, pages 757-776. MIT Press, October 1990.

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., editor, PARLE91: 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 scaleable, reconfigurable, distributed-memory multiprocessor. In Proceedings of Parallel Architecture and Languages Europe. Springer Verlag, 1991.

Keith L. Clark, F. G. McCabe, and S. Gregory. IC-PROLOG - language features. In K. L. Clark and S. A. Tärnlund, editora, Logic Programming, pages 253-266. Academic Press, London, 1982.

William Clocksin. Principies of the DelPhi Parallel lnference Machine. Computer Journal, 30(5):386-392, 1987.

J. A. Crammond. Scheduling and Variable Assignment in the Parallel Parlog Implementation. In Procecdings of the 1990 North American Conference on Logic Programming, pages 642-657, October 1990.

J. A. Crammond. The Abstract Machine and Implementation of Parallel Parlog. Technical report, Dept. of Computing, Imperial College, London, June 1990.

Inês Dutra. A Flexible Scheduler for Andorra-I. In A Beaumont and G. Gupta, editors, Lecture Note8 in Computer Science 569, Parallel Execution of Logic Programs, pages 70-82. Springer-Verlag, June 1991.

Inês Dutra. Strategies for Scheduling And- and Or-Work in Parallel Logic Programming Systems. In Proceedings of the 1994 International Logic Programming Symposium, pages 289-304. MIT Press, 1994.

Inês Dutra. Distributing And- and Or-Work in the Andorra-I Parallel Logic Programming System. PhD thesis, University of Bristol, Department of Computer Science, February 1995. Ph.D. thesis.

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.

Wai-Keong Foong. Or-Parallel Prolog with Heuristic Task Distribution. In Lecture Noltes in Artificial Intelligence 592, Logic Programming Russian Conference, pages 193-200, 1991.

Manuel Hermenegildo. An Abstract Machine for Restricted And-Parallel Execution of Logic Programs. In Ehud Shapiro, editor, Proceedings of the Third International Conference on Logic Programming, pages 25-39. Springer-Verlag, 1986.

Manuel V. Hermenegildo. Relating Goal Scheduling, Precedence, and Memory Management in AND-parallel Execution of Logic Programs. In Jean-Louis Lassez, editor, Logic Programming: Proceedings of the Fourth International Conference, Volume 2, pages 556-575. The MIT Press, 1987.

Ewing Lusk, David H. D. Warren, Seif Haridi, et al. The Aurora Or-parallel Prolog System. In Proceedings of the 1988 International Conference on Fifth Generation Compuler Systems, pages 819-830. ICOT, Tokyo, Japan, November 1988.

Vitor Santos Costa, David H. D. Warren, and Rong Yang. The Andorra-I Preprocessor: Supporting full Prolog on the Basic Andorra model. In Proceedings of the Eighth International Conference on Logic Programming, pages 443-456. MIT Press, 1991.

David C. Sehr and Laxmikant V. Kal. Estimating the Inherent Parallelism in Prolog Programs. In Proceedings of the 1992 International Conference on Fifth Generation Computer Systems, pages 783-790. ICOT, 1992.

Kish Shen. Studies of And/Or Parallelism in Prolog. PhD thesis, Computer Laboratory, University of Cambridge, 1992.

Rad Yousef Sindaha. Branch-Level Scheduling in Aurora: The Dharmo Scheduler. PbD thesis, University of Bristol, Department of Computer Science, In preparation, 1993.

Evan Tick. Compile Time Granularity Analysis for Parallel Logic Programming Systems. New Generation Col(lpuling, 7(2,3):325-337, 1990.

David H. D. Warren. The Andorra model. Presented at Gigalips Project workshop, University of Manchester, March 1988.

Rong Yang, Tony Beaumont, Ins Dutra, Vitor Santos Costa, and David H. D. Warren. Per formance of the Compiler-Based Andorra-I System. In Proceedings of the Tenth International Conference on Logic Programming, pages 150-166. MIT Press, June 1993.

Rong Yang, Vitor Santos Costa, and David H. O. Warren. The Andorra-I Engine: A parallel implementation of the Basic Andorra model. In Proceedings of the Eighth International Conference on Logic Programming, pages 825-839. MIT Press, 1991.