Performance of Sparse Binding Arrays for Or-Parallelism
Resumo
One important problem in the design of novel logic programming systems is the support of several forms of implicit parallelism. A new binding model, the Sparse Binding Array (SBA), has been proposed for the efficient and simplified integration of Independent-And, Determinate-And and Or-parallelism. In this paper we report on the use of this model for pure Or-parallelism. The work discusses the major implementation issues in supporting this binding model for pure Or-parallelism. We show that an implementation based on this Binding model is more efficient then the original Aurora using tbe traditional Binding Array model [16]. Moreover, we explain how the notion of a variable level can be used to reduce overheads of the Orparallel system. Our results in supporting pure or-parallelism show that the approach is very promissing for combined paralell systems.
Referências
K. A. M. Ali and R. Karlsson. The Muse Or-parallel Prolog Model and its Performance. In Proceedings of the North American Conference on Logic Programming, pages 757-776. MIT Press, October 1990.
A. Beaumont, S. M. Raman, P. Szeredi, and D. H. D. Warren. Flexible Scheduling of OR-Parallelism in Aurora: The Bristol Scheduler. In PARLE91: Conference on Parallel Architectures and Languages Europe, volume 2, pages 403-420. Springer Verlag, June 1991.
M. Carlsson. On the efficiency of optimised shallow backtracking in Compiled Prolog. In Proceedings of the Sixth lnternational Conference on Logic Programming, pages 3-15. MIT Press, June 1989.
M. Carlsson. Design and Implementation of an OR-Parallel Prolog Engine. SICS Dissertation Series 02, The Royal Institute of Technology, 1990.
G. Gupta, V. S. Costa, and E. Pontelli. Shared Paged Binding Array: A Universal Datastructure for Parallel Logic Programming. In Proceedings of the Twelveth lnternational Conference on Logic Programming, to appear.
G. Gupta, M. Hermenegildo, and V. S. Costa. And-Or Parallel Prolog: A Recomputation based Approach. New Generation Computing, 11(3,4):770-782, 1993.
G. Gupta and B. Jayaraman. On Criteria for Or-Parallel Execution Models of Logic Programs." In Proceedings of the North American Conference on Logic Programming, pages 604-623. MIT Press, October 1989.
G. Gupta and V. Santos Costa. And-Or Parallelism in Full Prolog with Paged Binding Arrays. In LNCS 605, PARLE'92 Parallel Architectures and Languages Europe, pages 617-632. Springer-Verlag, June 1992.
M. V. Hermenegildo and K. Greene. &-Prolog and its Performance: Exploiting lndependent And-Parallelism. In Proceedings of the Seventh lntemational Conference on Logic Programming, pages 253-268. MIT Press, June 1990.
R. Karlsson. A High Performance OR-parallel Prolog System. SICS Dissertation Series 07, The Royal Institute of Technology, 1991.
E. Lusk, R. Butler, T. Disz, R. Olson, R. Overbeek, R. Stevens, D. H. D. Warren, A. Calderwood, P. Szeredi, S. Haridi, P. Brand, M. Carlsson, A. Ciepelewski, and B. Hausman. The Aurora or-parallel Prolog system. In International Conference on Fifth Generation Computer Systems 1988, pages 819-830. ICOT, Tokyo, Japan, Nov. 1988.
J. Montelius and K. A. M. Ali. An And/Or-Parallel Implementation of AKL. Proc. NSF/ICOT Workshop on Parallel Logic Programming and its Environments, CIS-94-04, University of Oregon, Mar. 1994.
V. Santos Costa, M. E. Correia, and F. Silva. Aurora and Friends on the Sun (Extended Abstract). In 2nd COMPULOG NET Workshop on Parallelism and Implementation Technologies, Madrid, 1994.
V. Sa.p.tos Costa, D. H. D. Warren, and R. Yang. Andorra... I: A Parallel Prolog System that Transparently Exploits both And-and Or-Parallelism. In Third ACM SIGPLAN Symposium on Principies & Practice of Parallel Programming PPOPP, pages 83-93. ACM press, April 1991. SIGPLAN Notices vol 26(7), July 1991.
D. H. D. Warren. An Abstract Prolog Instruction Set. Technical Note 309, SRI International, 1983.
D. H. D. Warren. The SRI model for or-parallel execution of Prolog-abstract design and implementation issues. In Proceedings of the 1987 Symposium on Logic Programming, pages 92-102, 1987.
A. Beaumont, S. M. Raman, P. Szeredi, and D. H. D. Warren. Flexible Scheduling of OR-Parallelism in Aurora: The Bristol Scheduler. In PARLE91: Conference on Parallel Architectures and Languages Europe, volume 2, pages 403-420. Springer Verlag, June 1991.
M. Carlsson. On the efficiency of optimised shallow backtracking in Compiled Prolog. In Proceedings of the Sixth lnternational Conference on Logic Programming, pages 3-15. MIT Press, June 1989.
M. Carlsson. Design and Implementation of an OR-Parallel Prolog Engine. SICS Dissertation Series 02, The Royal Institute of Technology, 1990.
G. Gupta, V. S. Costa, and E. Pontelli. Shared Paged Binding Array: A Universal Datastructure for Parallel Logic Programming. In Proceedings of the Twelveth lnternational Conference on Logic Programming, to appear.
G. Gupta, M. Hermenegildo, and V. S. Costa. And-Or Parallel Prolog: A Recomputation based Approach. New Generation Computing, 11(3,4):770-782, 1993.
G. Gupta and B. Jayaraman. On Criteria for Or-Parallel Execution Models of Logic Programs." In Proceedings of the North American Conference on Logic Programming, pages 604-623. MIT Press, October 1989.
G. Gupta and V. Santos Costa. And-Or Parallelism in Full Prolog with Paged Binding Arrays. In LNCS 605, PARLE'92 Parallel Architectures and Languages Europe, pages 617-632. Springer-Verlag, June 1992.
M. V. Hermenegildo and K. Greene. &-Prolog and its Performance: Exploiting lndependent And-Parallelism. In Proceedings of the Seventh lntemational Conference on Logic Programming, pages 253-268. MIT Press, June 1990.
R. Karlsson. A High Performance OR-parallel Prolog System. SICS Dissertation Series 07, The Royal Institute of Technology, 1991.
E. Lusk, R. Butler, T. Disz, R. Olson, R. Overbeek, R. Stevens, D. H. D. Warren, A. Calderwood, P. Szeredi, S. Haridi, P. Brand, M. Carlsson, A. Ciepelewski, and B. Hausman. The Aurora or-parallel Prolog system. In International Conference on Fifth Generation Computer Systems 1988, pages 819-830. ICOT, Tokyo, Japan, Nov. 1988.
J. Montelius and K. A. M. Ali. An And/Or-Parallel Implementation of AKL. Proc. NSF/ICOT Workshop on Parallel Logic Programming and its Environments, CIS-94-04, University of Oregon, Mar. 1994.
V. Santos Costa, M. E. Correia, and F. Silva. Aurora and Friends on the Sun (Extended Abstract). In 2nd COMPULOG NET Workshop on Parallelism and Implementation Technologies, Madrid, 1994.
V. Sa.p.tos Costa, D. H. D. Warren, and R. Yang. Andorra... I: A Parallel Prolog System that Transparently Exploits both And-and Or-Parallelism. In Third ACM SIGPLAN Symposium on Principies & Practice of Parallel Programming PPOPP, pages 83-93. ACM press, April 1991. SIGPLAN Notices vol 26(7), July 1991.
D. H. D. Warren. An Abstract Prolog Instruction Set. Technical Note 309, SRI International, 1983.
D. H. D. Warren. The SRI model for or-parallel execution of Prolog-abstract design and implementation issues. In Proceedings of the 1987 Symposium on Logic Programming, pages 92-102, 1987.
Publicado
04/08/1996
Como Citar
COSTA, Vítor Santos; CORREIA, Manuel Eduardo; SILVA, Fernando.
Performance of Sparse Binding Arrays for Or-Parallelism. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 8. , 1996, Recife.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1996
.
p. 151-160.
DOI: https://doi.org/10.5753/sbac-pad.1996.19823.
