Project Summary

Logic Programming (LP) provides a high-level, declarative approach to programming. In general, logic programs can be seen as executable specifications that despite their simple declarative and procedural semantics allow for designing very complex and efficient applications. The inherent non-determinism in the way logic programs are structured as simple collections of alternative logic clauses makes LP very attractive for the exploitation of implicit parallelism.

Many parallel LP systems implemented for shared and distributed memory architectures exist in the literature, but most of them are no longer available, maintained or supported. The success of these systems was mainly driven by the fact that parallelism was exploited implicitly. However, the lack of control over some of the main factors that often limit performance in parallel systems restricted the interest and applicability of these systems to real-world applications.

Although interest on the whole area of declarative parallel programming laid dormant for a number of years, the increasing availability and popularity of multi-core processors has rekindled the interest in the area, e.g., as shown by the Intel sponsored conferences on 'Declarative Aspects of Multicore Programming', where our research team has participated since the very beginning. Multi-core architectures are turning into a viable high-performance, affordable and standardized alternative to the traditional (and often expensive) parallel architectures. The number of cores per processor is expected to continue to increase, further expanding the potential for parallelism.

Motivated by the intrinsic and strong potential that LP has for implicit parallelism, the LEAP project aims at investigating novel techniques to efficiently exploit parallelism from large scale real-world applications in low cost multi-core architectures, thus building capacity to put LP environments as part of the general ecosystem of high-performance parallel computing. To achieve these goals, the LEAP project still establishes its foundations on implicit parallelism but relies on high-level explicit parallel constructs to trigger parallel execution. These explicit parallel constructs can be used not only to allow users to annotate the sub-computations that are best candidates for parallel execution, but also to instruct or pass specific information to the LP execution system about the sub-computations at hand by using pre-defined directives. For example, we may have directives to define the number of workers, the execution model and the scheduling strategy to be used, directives to define granularity and load balancing policies, or directives to define restrictions regarding speculative work and predicate side-effects.

In its essence, the LEAP project resembles the OpenMP, the Intel Threading Building Blocks or the MapReduce specifications for multi-core processor parallelism. A program begins as a single worker that executes sequentially until reaching a parallel construct. When reaching a parallel construct, the execution model launches a set of additional workers to exploit in parallel the sub-computation at hand. Parallel execution is then handled implicitly by the execution model taking into account the directive restrictions. By taking advantage of these explicit parallel constructs, a user can write parallel logic programs from scratch or parallelise existing sequential programs by incrementally pinpoint the sub-computations that can benefit from parallelism, using the available directives to test and fine tune the program in order to achieve best performance.

Combining the inherent implicit parallelism of LP with explicit high-level parallel constructs will clearly enhance the expressiveness and declarative style of LP and greatly simplify parallel programming. Nevertheless, materializing this major guideline of the LEAP project in concrete, efficient and reliable implementations of these high-level parallel constructs, embraces a lot of research work, new contributions and challenging goals to be addressed. On the one hand, we intend to approach these problems by investigating novel models for exploiting implicit parallelism from large logic programming applications tailored to multi-core architectures, building up on our previous experience on the design and implementation of sequential, parallel and distributed LP systems, with support for extensions such as Tabling. On the other hand, we intend to guide and validate our proposals by using concrete LP environments, such as: April, an Inductive Logic Programming environment; ProbLog, a Probabilistic Logic Learning environment; Logtalk, an object-oriented logic programming environment, among others. Although our research work will be driven by these particular environments, we believe that our contributions can be of much broader interest for many other real-world LP environments and applications.

Past Publications

Parallel Logic Programming Systems on Scalable Architectures
V. Santos Costa, R. Bianchini, and Inês C. Dutra. Journal of Parallel and Distributed Computing, 60(7):835-852, 2000.

YapDss: an Or-Parallel Prolog System for Scalable Beowulf Clusters
R. Rocha, F. Silva and R. Martins. Portuguese Conference on Artificial Intelligence, Springer, LNAI 2902, pages 136-150, 2003.

On Applying Or-Parallelism and Tabling to Logic Programs
R. Rocha, F. Silva, and V. Santos Costa. Journal of Theory and Practice of Logic Programming, Cambridge University Press, volume 5 (1&2), pages 161-205. 2005.

On Supporting Parallelism in a Logic Programming System
V. Santos Costa. Workshop on Declarative Aspects of Multicore Programming, pages 77-91, 2008.

High Level Thread-Based Competitive Or-Parallelism in Logtalk
P. Moura, R. Rocha and Sara C. Madeira. International Symposium on Practical Aspects of Declarative Languages, Springer, LNCS 5418, pages 107-121, 2009.