Using Compile-Time Granularity Information to Support Dynamic Work Distribution in Parallel Logic Programming Systems

• Inês de Castro Dutra UFRJ
• Vítor Santos Costa Universidade do Porto
• Jorge L. V. Barbosa UCPEL
• Claudio F. R. Geyer UFRGS

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

Resumo

A very important component of a parallel system that generates irregular computational patterns is its work distribution strategy Scheduling strategies for these kinds of systems must be smart enough in order to dynamically balance workload while not incurring a very high overhead. Logic programs running on parallel logic programming systems are examples of irregular parallel computations. The two main forms of parallelism exploited by parallel logic programming systems are: and parallelism, that arises when several literals in the body of a clause can execute in parallel, and or-parallelism, that arises when several alternative clauses in the data base program can be selected in parallel. In this work we show that scheduling strategies for distributing and work and or-work in parallel logic programming systems must combine information obtained at compile-time with runtime information whenever possible, in order to obtain better performance. The information obtained at compile-time has two advantages over current implemented systems that use only runtime information: (1) the user does not need to adjust parameters in arder to estimate sizes of and-work and or-work for the programs; (2) the schedulers can use more accuratc estimates of sizes of and-work and or-work to make belter decisions at runtime. We did our experiments with Andorra-I, a parallel logic programming system that exploits both determinare and-parallelism and or-parallelism. In order to obtain compile-time granularity information we used the ORCA tool. Our benchmark set ranges from programs containing and parallelism only, or-parallelism only and a combination of both and-, and or-parallelism. Our results show that, when well designed, scheduling strategies can actually benefit from compile-time granularity information.

Palavras-chave: logic programming, parallelism, granularity analysis

Referências

Khayri A. M. Ali and Roland Karlsson. The Muse Or-parallel Prolog Model and its Performance. In Proceedings of the 1990 North American Conference on Linux Programming. pages 757-776. MIT Press, October 1990.

Reem Bahgat. Solving Resource Allocation Problems in Pandora. Technical repon. Imperial College, Department of Computing. 1990.

Reem Bahgat. Non-Deterministic Concurrent Logic Programming in Pandora, volume 37. World Scientific, Singapore, 1993. Series in Computer Science.

J. L. V. Barbosa and C. F. R. Geyer. Análise de Complexidade na Programação em Lógica: Taxonomia. Modelo Granlog e Análise OU. In XXIII Conferência Latino Americana de Informática. V Encontro Chileno de Computação da Sociedade Chilena de Computação (CLEI - PANEL'97). November 1997.

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.

Anthony Beaumont and David H. D. Warren. Scheduling Speculative Work in Or-Parallel Prolog Systems. In Proceedings of the Tenth International Conference on Logic Programming, pages 135-149. MIT Press, June 1993.

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 Archirecture and Languages Europe. Springer Verlag, 199 1.

Manuel Eduardo Correia, F. M. A. Silva, and V. Santos Costa. The SBA: Exploiting orthogonality in OR-AND Parallel Systems. In Proceedings of the 1997 International Logic Programming Symposium, October 1997. also published as Technical Repon DCC-97-3, DCCFC & LIACC, Universidade do Porto, April, 1997.

Barry Crabtree. A clustering system to network control, British Telecom. March 1991.

Saumya K. Debray, Nai-Wei Lin, and Manuel Hermenegildo. Task Granularity Analysis in Logic Programs. In Proceedings of the ACM SIGPLAN'90 Conference on Programming Language Design and Implementation. pages 174-188. June 1990.

A. K. Dewdney. Mathematical Recreations - A Compendium of Math Abuse from around the World. Scientific American, 263(5):142-145, September 1990.

I. C. 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. Also available as technical repon CSTR-94-09, from the Department of Computer Science, University of Bristol. England.

I. C. Dutra. Distributing And-and Or-Work in the Andorra-1 Parallel Logic Programming System. PhD thesis, University of Bristol. Department of Computer Science, February 1995. available at http://www.cos.ufrj.br/~ines.

I. C. Dutra. Performance Analysis of a Strategy to Distribute And-work and Or-work in Parallel Logic Programming Systems. In Proceedings of the VIII Brazilian Symposium on Computer Architecture and High Performance Processing - SBAC-PAD, pages 449-463, 1995.

I. C. Dutm. Distributing And-Work and Or-Work in Parallel Logic Programming Systems. In Proceedings of the 29th Hawaii International Conference on System Sciences, pages 646-655. IEEE, 1996.

FERRARI, O. N. O uso e implementação de informações de granulosidade no plosys. Tmbalho individual, Universidade Federal Do Rio Grande Do Sul, 1998.

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

Gopal Gupta. M. V. Hermencgildo, E. Pontelli, and V. Santos Costa. ACE: And/Or-parallel Copying-based Execution of Logic Programs. In Procudings of the Eleventh International Conference on Logic Programming, Italy, June 1994.

Gopal Gupta. Enrico Pontelli, and Manuel Hermenegildo. &ACE: A High Performance Parallel Prolog System. In Proceedings of the First International Symposium on Parallel Symbolic Computation, PASC0 '94, 1994.

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.

Sverker Jansson and Seif Haridi. Programming Paradigms of the Andorra Kernel Language. In Proceedings of the 1991 International Logic Programming Symposium, pages 167- 186. MIT Press, October 1991.

Nai-Wei Lin and Saumya K. Oebray. Cost Analysis of Logic Programs. Technical Repon, Department of Computer Science, The University of Arizona, August 1992.

Zheng Lin. Self-Organising Task Scheduling for Parallel Execution of Logic Programs. In Proceedings of the 1992 InternationaL Conference on Fifth Generation Computer Systems, pages 859-868. ICOT. 1992.

Ricardo Lopes and V. Santos Costa. The BEAM: Towards a first EAM Implementation. In Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, October 1997. Pon Jefferson.

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

Johan Montelius. Penny, A Parallel Implementation of AKL. PhD thesis, Swcdish Institute for Computer Science, SICS, Sweden, May 1997.

Remco Moolenaar and Bart Demoen. Optimization Techniques for non-deterministic promotion in the Andorra Kernel Language. In Proceedings of the Compulog-Net, Madrid, May 1993.

E. Morei, 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.

V. Santos Costa. Compile-Time Analysis for the Parallel Execution of Logic Program in Andorra-1. PhD thesis. Department of Computer Science. University of Bristol, August 1993.

V. Santos Costa, O. H. O. Warren, and R. Yang. Andorra-1: A Parallel Prolog System that Transparently Exploits both And-and Or-Parallelism. In Third ACM SIGPLAN Symposium on Principies & Practice of Parallel Programming, pages 83-93. ACM press, April 1991. SIGPLAN Notices vol 26(7), July 1991.

Vitor Santos Costa, David H. O. Warren, and Rong Yang. The Andorra-1 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.

Vitor Santos Costa and Rong Yang. Andorra-1 User's Guide and reference manual. Technical repon. University of Bristol, Computer Science Depanment, Sept 1990. Internal Repon, Gigalips Project.

Kish Shen. Overview of DASWAM: Exploitation of Dependent And-parallelism. J. of Logic Prog., 29(1 - 3), 1996.

Kish Shen. Vitor Santos Costa, and Andy King. A New Metric for Controlling Granularity for Parallel Execution. In Joint International Conference and Symposium on Logic Programming. Manchester, UK, June 1998.

Evan Tick. Compile Time Granularity Analysis for Parallel Logic Programming Systems. In Proceedings of the 1988 International Conference on Fifth Generation Computer Systems. ICOT, 1988.

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

Kazunori Ueda and Masao Morita. A New Implementation Technique for A ar GHC. In Proceedings of the Seventh International Conference on Logic Programming, pages 3-17. MIT Press, June 1990.

David H. O. Warren. The SRI Model for Or-Parallel Execution of Prolog- Abstract Design and Implementation Issues. In Proceedings of the 1987 International Logic Programming Symposium, pages 92-102. 1987.

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

Rong Yang. Implementation Notes on the Andorra Model. Technical repon, University of Bristol. Computer Science Department, Sept 1989. Internal Repon, Gigalips Project.

Rong Yang. Solving simple substitution ciphers in Andorra-1. In Proceedings of the Sixth International Conference on Logic Programming, pages 113-128. MIT Press, June 1989.

Rong Yang, Tony Beaumont, Inês Dutra, Vítor Santos Costa, and David H. O. Warren. Performance of the Compiler-Based Andorra-1 System. In Proceedings of the Tenth International Conference on Logic Programming, pages 150-166. MIT Press, June 1993.

Rong Yang, Vítor Santos Costa, and David H. O. Warren. The Andorra-1 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.