Parallel execution of Prolog programs: a survey

Since the early days of logic programming, researchers in the field realized the potential for exploitation of parallelism present in the execution of logic programs. Their high-level nature, the presence of nondeterminism, and their referential transparency, among other characteristics, make logic programs interesting candidates for obtaining speedups through parallel execution. At the same time, the fact that the typical applications of logic programming frequently involve irregular computations, make heavy use of dynamic data structures with logical variables, and involve search and speculation, makes the techniques used in the corresponding parallelizing compilers and run-time systems potentially interesting even outside the field. The objective of this article is to provide a comprehensive survey of the issues arising in parallel execution of logic programming languages along with the most relevant approaches explored to date in the field. Focus is mostly given to the challenges emerging from the parallel execution of Prolog programs. The article describes the major techniques used for shared memory implementation of Or-parallelism, And-parallelism, and combinations of the two. We also explore some related issues, such as memory management, compile-time analysis, and execution visualization.

Parallelizing irregular and pointer-based computations automatically: perspectives from logic and constraint programming

Irregular computations pose sorne of the most interesting and challenging problems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such computations often use dynamic data structures, which make heavy use of pointers. This complicates all the steps of a parallelizing compiler, from independence detection to task partitioning and placement. Starting in the mid 80s there has been significant progress in the development of parallelizing compilers for logic pro­gramming (and more recently, constraint programming) resulting in quite capable paralle­lizers. The typical applications of these paradigms frequently involve irregular computations, and make heavy use of dynamic data structures with pointers, since logical variables represent in practice a well-behaved form of pointers. This arguably makes the techniques used in these compilers potentially interesting. In this paper, we introduce in a tutoríal way, sorne of the problems faced by parallelizing compilers for logic and constraint programs and provide pointers to sorne of the significant progress made in the area. In particular, this work has resulted in a series of achievements in the areas of inter-procedural pointer aliasing analysis for independence detection, cost models and cost analysis, cactus-stack memory management, techniques for managing speculative and irregular computations through task granularity control and dynamic task allocation such as work-stealing schedulers), etc.

Incremental analysis of constraint logic programs

Global analyzers traditionally read and analyze the entire program at once, in a nonincremental way. However, there are many situations which are not well suited to this simple model and which instead require reanalysis of certain parts of a program which has already been analyzed. In these cases, it appears inecient to perform the analysis of the program again from scratch, as needs to be done with current systems. We describe how the xed-point algorithms used in current generic analysis engines for (constraint) logic programming languages can be extended to support incremental analysis. The possible changes to a program are classied into three types: addition, deletion, and arbitrary change. For each one of these, we provide one or more algorithms for identifying the parts of the analysis that must be recomputed and for performing the actual recomputation. The potential benets and drawbacks of these algorithms are discussed. Finally, we present some experimental results obtained with an implementation of the algorithms in the PLAI generic abstract interpretation framework. The results show signicant benets when using the proposed incremental analysis algorithms.

Improving abstract interpretations by combining domains

This article considers static analysis based on abstract interpretation of logic programs over combined domains. It is known that analyses over combined domains provide more information potentially than obtained by the independent analyses. However, the construction of a combined analysis often requires redefining the basic operations for the combined domain. A practical approach to maintain precision in combined analyses of logic programs which reuses the individual analyses and does not redefine the basic operations is illustrated. The advantages of the approach are that proofs of correctness for the new domains are not required and implementations can be reused. The approach is demonstrated by showing that a combined sharing analysis — constructed from "old" proposals — compares well with other "new" proposals suggested in recent literature both from the point of view of efficiency and accuracy.

Global analysis of constraint logic programs

This article presents and illustrates a practical approach to the dataow analysis of constraint logic programming languages using abstract interpretation. It is rst argued that from the framework point of view it suces to propose relatively simple extensions of traditional analysis methods which have already been proved useful and practical and for exist. This is shown by proposing a simple extension of Bruynooghes traditional framework which allows it to analyze constraint logic programs. Then and using this generalized framework two abstract domains and their required abstract functions are presented the rst abstract domain approximates deniteness information and the second one freeness. Finally an approach for cobining those domains is proposed The two domains and their combination have been implemented and used in the analysis of CLP and Prolog III applications. Results from this implementation showing its performance and accuracy are also presented

Las presentaciones de trabajo en lengua inglesa: una propuesta de curso on-line.

Desde la explosión de crecimiento de internet que comenzó en los años 90, se han ido creando y poniendo a disposición de los usuarios diversas herramientas para compartir información y servicios de diversas formas, desde el nacimiento del primer navegador hasta nuestros días, donde hay infinidad de lenguajes aplicables al ámbito web. En esta fase de crecimiento, en primer lugar, de cara a usuarios individuales, saldrían herramientas que permitirían a cada cual hacer su web personal, con sus contenidos expuestos. Más adelante se fue generando el fenómeno “comunidad”, con, por ejemplo, foros, o webs en las que había múltiples usuarios que disfrutaban de contenidos o servicios que la web ofreciese. Este crecimiento del mundo web en lo comunitario ha avanzado en muchas ramas,entre ellas, por supuesto, la educacional, surgiendo plataformas como la que es base del proyecto que a continuación se presenta, y herramienta básica y prácticamente ya imprescindible en la enseñanza universitaria: Moodle. Moodle es una herramienta diseñada para compatir recursos y diseñar actividades para el usuario potencial, complementando su aprendizaje en aula, o incluso siendo una vía autónoma de aprendizaje en sí misma. Se ha realizado un estudio sobre el estado de saludo de los contenidos que se exponen en Moodle, y se ha encontrado que una gran mayoría de los cursos que se pueden visitar tienen un gran número de carencias. Por un lado, hay pocos con material original explotado exclusivamente para el curso, y, si tienen material original, no se ha observado una especial atención por la maquetación. Por otro lado, hay muchos otros sin material original, y, en ambos casos, no se ha encontrado ningún curso que ofrezca material audiovisual exclusivo para el curso, presentando algunos en su lugar material audiovisual encontrado en la red (Youtube, etc). A la vista de estos hechos, se ha realizado un proyecto que intenta aportar soluciones ante estas carencias, y se presenta un curso procedente de diversas referencias bibliográficas, para la parte textual, y material audiovisual original e inédito que también se ha explotado específicamente para este curso. Este material ha sido por un lado vídeo, que se ha visionado, editado y subtitulado con software de libre distribución, y por otro lado, audio, que complementa un completo glosario que se ha añadido como extra al curso y cuyo planteamiento no se ha encontrado en ningún curso online de los revisados. Todo esto se ha envuelto en una maquetación cuidada que ha sido fruto del estudio de los lenguajes web html y CSS, de forma que, por un lado, el curso sea un lugar agradable en el que aprender dentro de internet, y por otro, se pudiesen realizar ciertas operaciones que sin estos conocimientos habrían sido imposibles, como la realización del glosario o la incrustación de imágenes y vídeos. A su vez, se ha tratado de dar un enfoque didáctico a toda la memoria del proyecto, de forma que pueda ser de utilidad a un usuario futuro que quisiese profundizar en los usos de Moodle, introducirse en el lenguaje web, o introducirse en el mundo de la edición de vídeo. ABSTRACT: Since the explosion of Internet growth beginning in the 90s, many tools have been created and made available for users to share information and services in various ways, from the birth of the first browser until today, where there are plenty of web programming languages. This growth stage would give individual users tools that would allow everyone to make an own personal website, with their contents exposed. Later, the "community" phenomenon appeared with, for example, forums, or websites where multiple users enjoyed the content or web services that those websites offered. Also, this growth in the web community world has progressed in many fields, including education, with the emerge of platforms such as the one that this project uses as its basis, and which is the basic and imperative tool in college education: Moodle. Moodle is a tool designed to share resources and design activities for the potential user, completing class learning, or even letting this user learn in an autonomous way. In this project a study on the current situation of the content present in Moodle courses around the net has been carried out, and it has been found that most of them lack of original material exploited exclusively for the courses, and if they have original material, there has been not observed concern on the layout where that material lies. On the other hand, there are many other with non original material, and in both cases, there has not been found any course that offers audio- visual material made specifically for the course, instead of presenting some audiovisual material found on the net (Youtube, etc). In view of these facts, the project presented here seeks to provide solutions to these shortcomings, presenting a course with original material exploited from various references, and unpublished audioevisual material which also has been exploited specifically for this course. This material is, on one hand, video, which has been viewed, edited and subtitled with free software, and on the other, audio, which complements a comprehensive glossary that has been added as an extra feature to the course and whose approach was not found in any of the online courses reviewed. All of this has been packaged in a neat layout that has been the result of the study of web languages HTML and CSS, so that first, the course was a pleasant place to learn on the internet, and second, certain operations could be performed which without this knowledge would have been impossible, as the glossary design or embedding images and videos. Furthermore, a didactic approach has been adopted to the entire project memory, so it can be useful to a future user who wanted to go deeper on the uses of Moodle, containing an intro into the web language, or in the world video editing.

Some challenges for constraint programming

We propose a number of challenges for future constraint programming systems, including improvements in implementation technology (using global analysis based optimization and parallelism), debugging facilities, and the extensión of the application domain to distributed, global programming. We also briefly discuss how we are exploring techniques to meet these challenges in the context of the development of the CIAO constraint logic programming system.

Strategic directions in constraint programming

An abstract is not available.

High-level characteristics of or-and independent and-parallelism in prolog

Although studies of a number of parallel implementations of logic programming languages are now available, their results are difficult to interpret due to the multiplicity of factors involved, the effect of each of which is difficult to sepárate. In this paper we present the results of a high-level simulation study of or- and independent and-parallelism with a wide selection of Prolog programs that aims to determine the intrinsic amount of parallelism, independently of implementation factors, thus facilitating this separation. We expect this study will be instrumental in better understanding and comparing results from actual implementations, as shown by some examples provided in the paper. In addition, the paper examines some of the issues and tradeoffs associated with the combination of and- and or-parallelism and proposes reasonable solutions based on the simulation data obtained.

Heap analysis in the presence of collection libraries

Memory analysis techniques have become sophisticated enough to model, with a high degree of accuracy, the manipulation of simple memory structures (finite structures, single/double linked lists and trees). However, modern programming languages provide extensive library support including a wide range of generic collection objects that make use of complex internal data structures. While these data structures ensure that the collections are efficient, often these representations cannot be effectively modeled by existing methods (either due to excessive analysis runtime or due to the inability to represent the required information). This paper presents a method to represent collections using an abstraction of their semantics. The construction of the abstract semantics for the collection objects is done in a manner that allows individual elements in the collections to be identified. Our construction also supports iterators over the collections and is able to model the position of the iterators with respect to the elements in the collection. By ordering the contents of the collection based on the iterator position, the model can represent a notion of progress when iteratively manipulating the contents of a collection. These features allow strong updates to the individual elements in the collection as well as strong updates over the collections themselves.

A model for inter-module analysis and optimizing compilation

Recent research into the implementation of logic programming languages has demonstrated that global program analysis can be used to speed up execution by an order of magnitude. However, currently such global program analysis requires the program to be analysed as a whole: sepárate compilation of modules is not supported. We describe and empirically evalúate a simple model for extending global program analysis to support sepárate compilation of modules. Importantly, our model supports context-sensitive program analysis and multi-variant specialization of procedures in the modules.

A framework for assertion-based debugging in constraint logic programming

We propose a general framework for assertion-based debugging of constraint logic programs. Assertions are linguistic constructions which allow expressing properties of programs. We define assertion schemas which allow writing (partial) specifications for constraint logic programs using quite general properties, including user-defined programs. The framework is aimed at detecting deviations of the program behavior (symptoms) with respect to the given assertions, either at compile-time or run-time. We provide techniques for using information from global analysis both to detect at compile-time assertions which do not hold in at least one of the possible executions (i.e., static symptoms) and assertions which hold for all possible executions (i.e., statically proved assertions). We also provide program transformations which introduce tests in the program for checking at run-time those assertions whose status cannot be determined at compile-time. Both the static and the dynamic checking are provably safe in the sense that all errors flagged are definite violations of the specifications. Finally, we report on an implemented instance of the assertion language and framework.

Towards independent and-parallelism in CLP

In this paper we propose a complete scheme for automatic exploitation of independent and-parallelism in CLP programs. We first discuss the new problems involved because of the different properties of the independence notions applicable to CLP. We then show how independence can be derived from a number of standard analysis domains for CLP. Finally, we perform a preliminary evaluation of the efficiency, accuracy, and effectiveness of the approach by implementing a parallehzing compiler for CLP based on the proposed ideas and applying it on a number of CLP benchmarks.

Automatic optimization of dynamic scheduling in logic programs

Abstract is not available.

IDRA (IDeal Resource Allocation): Computing ideal speedups in parallel logic programming

We present a technique to estimate accurate speedups for parallel logic programs with relative independence from characteristics of a given implementation or underlying parallel hardware. The proposed technique is based on gathering accurate data describing one execution at run-time, which is fed to a simulator. Alternative schedulings are then simulated and estimates computed for the corresponding speedups. A tool implementing the aforementioned techniques is presented, and its predictions are compared to the performance of real systems, showing good correlation.