Parallel execution of Prolog programs

OData support
Dr. Szeredi Péter
Department of Computer Science and Information Theory

The main motivation of the parallelization of computer programs is to enable the utilization of the increasingly popular multi-core architectures. However, writing an efficient parallel program is generally a big challenge. It is a natural need to make the creation of parallel programs as easy and as efficient as possible.

Logic programs describe the task at hand in a more direct way than imperative ones do, reflecting its structure more clearly. Thus in logic programs it is easier to identify parts well suited for parallelization, and this can even be done using completely automated methods. There are many parallel Prolog implementations taking advantage of this property of declarative languages.

However the support of the programmer can still be useful in some aspects such as which part of the program should be parallelized and with what level of granularity. So a system using this information can be more efficient in some cases than that using fully automated methods. Thus it is worth to examine the usefulness of a system which entrusts the indication of parts to execute in parallel to the programmer, in declarative languages as well.

The purpose of my thesis is to create such a system. The most important requirements are the following: the system should be easy to use, its parametrization should be flexible and it should try to utilize available resources as efficiently as possible.

In my thesis I first show the possibilities of parallelization of Prolog programs, and a way to implement these using the multi-threading capabilities of SWI-Prolog, a Prolog implementation (Chapter 1). Next, I provide a specification of the system to be built (Chapter 2), and present the plans of the implementation explaining the most important design decisions (Chapter 3). Subsequently, I show the details of the implementation (Chapter 4), and discuss the issues of testing and performance analysis (Chapter 5). The thesis concludes with a summary of the work done so far and a discussion of possible improvements (Chapter 6).


Please sign in to download the files of this thesis.