ACE: And/OrParallel 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 stackcopying 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 orparallelism, independent andparallelism, dependent
andparallelism and their dataparallel forms. The system is extremely
efficient (approximately 5% parallel overhead) and has shown excellent
speedups 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,
runtime optimization, to extensions.
Click here to
see a report (pdf) on the ACE Project.
Execution Models

G. Gupta, M. Hermenegildo, V. Santos Costa, "AndOr 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. 298321.

G. Gupta and V. Santos Costa, "Optimal Implementation of AndOr Parallel
Prolog," (selected papers from PARLE'92: Parallel Architectures and Languages
Europe), Journal of Future Generation Computer Systems, Vol 10,
No. 1 pp. 7192, Elsevier Science Publishers, Apr. 1994.

G. Gupta, E. Pontelli, M. Hermenegildo, V. Santos Costa, "A Stackcopying
Approach to Parallel Execution of Prolog." Proceedings of the International
Conference on Logic Programming '94, Italy. MIT Press. pp. 93109.

E. Pontelli, G. Gupta, "Implementation Mechanisms for Dependent Andparallelism"
In Proc. International Conference on Logic Programming, MIT Press,
July 1997. pp. 123137.

G. Gupta, M. Hermenegildo, "Recomputation based Implementations of AndOr
Parallel Prolog," In Proceedings of the International Conference on
Fifth Generation Computer Systems (FGCS '92), Tokyo, Japan, June '92,
pages 770782,

G. Gupta and M. Hermenegildo, "ACE: And/Orparallel Copyingbased Execution
of Logicprograms," 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 "AndOr 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. 617632.

G. Gupta, V. Santos Costa, E. Pontelli, "Shared Paged Binding Array: A
Universal Datastructure for Parallel Logic Programming," In Proc. NSF/ICOT
workshop on Parallel Logic Programming, T. Chikayama and E. Tick (Eds).
University of Oregon CISTR9404. Mar. 1994.

G. Gupta, V. Santos Costa, R. Yang, M. Hermenegildo, "IDIOM: A Model for
Integrating Dependentand, Independentand and Orparallelism," In Proceedings
of International Logic Programming Symposium, MIT Press, 1991, pages
152166.
Handling Cuts/SideEffects

G. Gupta, V. Santos Costa, "Cuts and Sideeffects in AndOr Parallel Prolog,"
Journal of Logic Programming, Vol 27(1), April 96, 4571.

G. Gupta, V. Santos Costa "Complete and Efficient Methods for supporting
Cuts and Sideeffects in And/Or Parallel Prolog," In Proceedings of
IEEE International Symposium on Parallel and Distributed Processing,
IEEE Computer Society Press, pages 288295, Dec., 1992.
Runtime Optimizations and Efficiency Issues

E. Pontelli, G. Gupta, D. Tang, M. Hermenegildo, M. Carro, "Improving the
Efficiency of Nondeterministic Independent Andparallel Logic Programming
Systems," Journal of Computer Languages, Vol. 22, No. 23, pp. 115142,
Oct. 1996.

E. Pontelli, G. Gupta, "Efficient Parallel Implementation of Backtracking
in Nondeterministic Languages" In International Conference on Parallel
Processing, IEEE Press, Aug, 1998, pp. 338345.

G. Gupta and E. Pontelli, "Optimization Schemas for Nondeterministic Systems
and Languages," (Extended Paper). In Proceedings of the 1997 IEEE on
Parallel Processing Symposium. IEEE Press, Apr '97. pp. 428435.

G. Gupta and E. Pontelli, "Last Alternative Optimization," In Proceedings
of the 1996 IEEE Symposium on Parallel and Distributed Computing. IEEE
Press, pp. 538541.

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 Orparallelism and Andparallelism,"
In European Conference on Parallel Processing '95, Stockholm, Sweden,
Springer Verlag Lecture Notes 966, pp. 4354.

E. Pontelli, G. Gupta "Dataparallel Logic Programming in &ACE" In
Proceedings of the 1995 IEEE Syposium on Parallel and Distributed Computing.
IEEE Press, pp. 424431, TX, Oct. '95.<

E. Pontelli, G. Gupta, D. Tang, "Determinacy Driven Optimization of Andparallel
Logic Programming Systems" In Proc. 1995 International Conference on
Logic Programming, MIT Press, Tokyo, pp. 615630. June '95.

G. Gupta and B. Jayaraman, "Optimizing AndOr Parallel Implementations,"
In Proceedings of International Logic Programming Symposium, MIT
Press, Oct. 1990, pp. 737756.
Overview

E. Pontelli and G. Gupta, "Parallel Symbolic Computation with ACE," In
Annals of Artificial Intelligence and Mathematics, 21 (1997) 359395,
Dec. '97.

G. Gupta, E. Pontelli. "ACE: A High Performance Parallel Prolog System,"
Proceedings of Joint Conference on Declarative Programming. June
1997, pp. 2531. 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 417295.

E. Pontelli, G. Gupta, "Exploiting Maximal Parallelism in Prolog" In 8th
International Conference on Parallel and Distributed Systems, Orlando,
FL, pp. 131136.
Extensions
Performance

E. Pontelli, G. Gupta, J. Wiebe, D. Farwell, "Natural Language Multiprocessing:
A Case Study," In Proc. AAAI '98, pp. 7682. July 1998.

E. Pontelli, G. Gupta, M. Hermenegildo, "&ACE: A High Performance
Parallel Prolog System," In Proc. 9th International Parallel Processing
Symposium, IEEE Press, 1995, pp. 564571.
Compiletime Analysis
Visualization