ACE: And/Or-Parallel Implementation of Prolog

This project aims to build a high performance parallel implementation of Prolog on multiprocessor architectures based on the the ACE model. The ACE model uses stack-copying and a novel memory mapping scheme to represent the multiple environment that exist at runtime. To date, a system has been built that runs on the Sequent Symmetry and the Sun Sparc Multiprocessor. The ACE system exploits or-parallelism, independent and-parallelism, dependent and-parallelism and their data-parallel forms. The system is extremely efficient (approximately 5% parallel overhead) and has shown excellent speed-ups on a variety of benchmarks (some as long as 35,000 lines, written by others). The ACE project has been funded by grants from the National Science Foundation. The most comprehensive document describing the ACE system can be found in Enrico Pontelli's 1997 Ph.D. Thesis. The project has been done in collaboration with Universidad Politecnica de Madrid and University of Porto.

Papers

There are numerous papers written on all aspects of the ACE system, ranging from implementation techniques, performance evaluation, execution vizualization, run-time optimization, to extensions. Click here to see a report (pdf) on the ACE Project.

Execution Models

G. Gupta, M. Hermenegildo, V. Santos Costa, "And-Or Parallel Prolog: A Recomputation Based Approach," (selected papers from International conference on Fifth Generation Computer Systems 1992), New Generation Computing: An International Journal, Vol. 11 (3,4), June 1993, pp. 298-321.
G. Gupta and V. Santos Costa, "Optimal Implementation of And-Or Parallel Prolog," (selected papers from PARLE'92: Parallel Architectures and Languages Europe), Journal of Future Generation Computer Systems, Vol 10, No. 1 pp. 71-92, Elsevier Science Publishers, Apr. 1994.
G. Gupta, E. Pontelli, M. Hermenegildo, V. Santos Costa, "A Stack-copying Approach to Parallel Execution of Prolog." Proceedings of the International Conference on Logic Programming '94, Italy. MIT Press. pp. 93-109.
E. Pontelli, G. Gupta, "Implementation Mechanisms for Dependent And-parallelism" In Proc. International Conference on Logic Programming, MIT Press, July 1997. pp. 123-137.
G. Gupta, M. Hermenegildo, "Recomputation based Implementations of And-Or Parallel Prolog," In Proceedings of the International Conference on Fifth Generation Computer Systems (FGCS '92), Tokyo, Japan, June '92, pages 770-782,
G. Gupta and M. Hermenegildo, "ACE: And/Or-parallel Copying-based Execution of Logic-programs," In Proceedings of ICLP '91 Workshop on Parallel Execution of Logic Programs, Springer Verlag, Lecture Notes in Computer Science 569, Dec. 1991.
G. Gupta, V. Santos Costa "And-Or Parallelism in Full Prolog with Paged Binding Arrays," In Proceedings of Parallel Architectures and Languages Europe (PARLE), Springer Verlag Lecture Notes Computer Science 605, Paris, June 1992, pp. 617-632.
G. Gupta, V. Santos Costa, E. Pontelli, "Shared Paged Binding Array: A Universal Data-structure for Parallel Logic Programming," In Proc. NSF/ICOT workshop on Parallel Logic Programming, T. Chikayama and E. Tick (Eds). University of Oregon CIS-TR-94-04. Mar. 1994.
G. Gupta, V. Santos Costa, R. Yang, M. Hermenegildo, "IDIOM: A Model for Integrating Dependent-and, Independent-and and Or-parallelism," In Proceedings of International Logic Programming Symposium, MIT Press, 1991, pages 152-166.

Handling Cuts/Side-Effects

Run-time Optimizations and Efficiency Issues

E. Pontelli, G. Gupta, D. Tang, M. Hermenegildo, M. Carro, "Improving the Efficiency of Non-deterministic Independent And-parallel Logic Programming Systems," Journal of Computer Languages, Vol. 22, No. 2-3, pp. 115-142, Oct. 1996.
E. Pontelli, G. Gupta, "Efficient Parallel Implementation of Backtracking in Non-deterministic Languages" In International Conference on Parallel Processing, IEEE Press, Aug, 1998, pp. 338-345.
G. Gupta and E. Pontelli, "Optimization Schemas for Non-deterministic Systems and Languages," (Extended Paper). In Proceedings of the 1997 IEEE on Parallel Processing Symposium. IEEE Press, Apr '97. pp. 428-435.
G. Gupta and E. Pontelli, "Last Alternative Optimization," In Proceedings of the 1996 IEEE Symposium on Parallel and Distributed Computing. IEEE Press, pp. 538-541.
E. Pontelli, G. Gupta, "Nested Parallel Call Optimization" In Proceedings of the 10th IEEE International Parallel Processing Symposium, IEEE Press, Waikiki, Hawaii, April '96.
E. Pontelli, G. Gupta, "On the Duality between Or-parallelism and And-parallelism," In European Conference on Parallel Processing '95, Stockholm, Sweden, Springer Verlag Lecture Notes 966, pp. 43-54.
E. Pontelli, G. Gupta "Data-parallel Logic Programming in &-ACE" In Proceedings of the 1995 IEEE Syposium on Parallel and Distributed Computing. IEEE Press, pp. 424-431, TX, Oct. '95.<
E. Pontelli, G. Gupta, D. Tang, "Determinacy Driven Optimization of And-parallel Logic Programming Systems" In Proc. 1995 International Conference on Logic Programming, MIT Press, Tokyo, pp. 615-630. June '95.
G. Gupta and B. Jayaraman, "Optimizing And-Or Parallel Implementations," In Proceedings of International Logic Programming Symposium, MIT Press, Oct. 1990, pp. 737-756.

Overview

E. Pontelli and G. Gupta, "Parallel Symbolic Computation with ACE," In Annals of Artificial Intelligence and Mathematics, 21 (1997) 359-395, Dec. '97.
G. Gupta, E. Pontelli. "ACE: A High Performance Parallel Prolog System," Proceedings of Joint Conference on Declarative Programming. June 1997, pp. 25-31. Invited talk by G. Gupta.
G. Gupta, V. Santos Costa "A Systematic Approach to exploiting Implicit Parallelism in Prolog," In 26th Hawaii International Conference on System Sciences, Maui Island, Jan., 1993, pages 417-295.
E. Pontelli, G. Gupta, "Exploiting Maximal Parallelism in Prolog" In 8th International Conference on Parallel and Distributed Systems, Orlando, FL, pp. 131-136.

Extensions

Performance

Compile-time Analysis

E. Pontelli, G. Gupta, F. Pulvirenti, A. Ferro, "Automatic Compile-Time Parallelization of Prolog Programs for Dependent And-Parallelism," In Proc. International Conference on Logic Programming, MIT Press, July 1997. pp. 108-122.

Visualization

R. Vaupel, E. Pontelli, G. Gupta, "Visualization of And/Or-parallel Execution of Logic Programs," In Proc. International Conference on Logic Programming, MIT Press, July 1997. pp. 271-285.