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.

Relational and Allegorical Semantics for Constraint Logic Programming

El c��lculo de relaciones binarias fue creado por De Morgan en 1860 para ser posteriormente desarrollado en gran medida por Peirce y Schr��der. Tarski, Givant, Freyd y Scedrov demostraron que las ��lgebras relacionales son capaces de formalizar la l��gica de primer orden, la l��gica de orden superior as�� como la teor��a de conjuntos. A partir de los resultados matem��ticos de Tarski y Freyd, esta tesis desarrolla sem��nticas denotacionales y operacionales para la programaci��n l��gica con restricciones usando el ��lgebra relacional como base. La idea principal es la utilizaci��n del concepto de sem��ntica ejecutable, sem��nticas cuya caracter��stica principal es el que la ejecuci��n es posible utilizando el razonamiento est��ndar del universo sem��ntico, este caso, razonamiento ecuacional. En el caso de este trabajo, se muestra que las ��lgebras relacionales distributivas con un operador de punto fijo capturan toda la teor��a y metateor��a est��ndar de la programaci��n l��gica con restricciones incluyendo los ��rboles utilizados en la b��squeda de demostraciones. La mayor parte de t��cnicas de optimizaci��n de programas, evaluaci��n parcial e interpretaci��n abstracta pueden ser llevadas a cabo utilizando las sem��nticas aqu�� presentadas. La demostraci��n de la correcci��n de la implementaci��n resulta extremadamente sencilla. En la primera parte de la tesis, un programa l��gico con restricciones es traducido a un conjunto de t��rminos relacionales. La interpretaci��n est��ndar en la teor��a de conjuntos de dichas relaciones coincide con la sem��ntica est��ndar para CLP. Las consultas contra el programa traducido son llevadas a cabo mediante la reescritura de relaciones. Para concluir la primera parte, se demuestra la correcci��n y equivalencia operacional de esta nueva sem��ntica, as�� como se define un algoritmo de unificaci��n mediante la reescritura de relaciones. La segunda parte de la tesis desarrolla una sem��ntica para la programaci��n l��gica con restricciones usando la teor��a de alegor��as���versi��n categ��rica del ��lgebra de relaciones���de Freyd. Para ello, se definen dos nuevos conceptos de Categor��a Regular de Lawvere y _-Alegor��a, en las cuales es posible interpretar un programa l��gico. La ventaja fundamental que el enfoque categ��rico aporta es la definici��n de una m��quina categ��rica que mejora e sistema de reescritura presentado en la primera parte. Gracias al uso de relaciones tabulares, la m��quina modela la ejecuci��n eficiente sin salir de un marco estrictamente formal. Utilizando la reescritura de diagramas, se define un algoritmo para el c��lculo de pullbacks en Categor��as Regulares de Lawvere. Los dominios de las tabulaciones aportan informaci��n sobre la utilizaci��n de memoria y variable libres, mientras que el estado compartido queda capturado por los diagramas. La especificaci��n de la m��quina induce la derivaci��n formal de un juego de instrucciones eficiente. El marco categ��rico aporta otras importantes ventajas, como la posibilidad de incorporar tipos de datos algebraicos, funciones y otras extensiones a Prolog, a la vez que se conserva el car��cter 100% declarativo de nuestra sem��ntica. ABSTRACT The calculus of binary relations was introduced by De Morgan in 1860, to be greatly developed by Peirce and Schr��der, as well as many others in the twentieth century. Using different formulations of relational structures, Tarski, Givant, Freyd, and Scedrov have shown how relation algebras can provide a variable-free way of formalizing first order logic, higher order logic and set theory, among other formal systems. Building on those mathematical results, we develop denotational and operational semantics for Constraint Logic Programming using relation algebra. The idea of executable semantics plays a fundamental role in this work, both as a philosophical and technical foundation. We call a semantics executable when program execution can be carried out using the regular theory and tools that define the semantic universe. Throughout this work, the use of pure algebraic reasoning is the basis of denotational and operational results, eliminating all the classical non-equational meta-theory associated to traditional semantics for Logic Programming. All algebraic reasoning, including execution, is performed in an algebraic way, to the point we could state that the denotational semantics of a CLP program is directly executable. Techniques like optimization, partial evaluation and abstract interpretation find a natural place in our algebraic models. Other properties, like correctness of the implementation or program transformation are easy to check, as they are carried out using instances of the general equational theory. In the first part of the work, we translate Constraint Logic Programs to binary relations in a modified version of the distributive relation algebras used by Tarski. Execution is carried out by a rewriting system. We prove adequacy and operational equivalence of the semantics. In the second part of the work, the relation algebraic approach is improved by using allegory theory, a categorical version of the algebra of relations developed by Freyd and Scedrov. The use of allegories lifts the semantics to typed relations, which capture the number of logical variables used by a predicate or program state in a declarative way. A logic program is interpreted in a _-allegory, which is in turn generated from a new notion of Regular Lawvere Category. As in the untyped case, program translation coincides with program interpretation. Thus, we develop a categorical machine directly from the semantics. The machine is based on relation composition, with a pullback calculation algorithm at its core. The algorithm is defined with the help of a notion of diagram rewriting. In this operational interpretation, types represent information about memory allocation and the execution mechanism is more efficient, thanks to the faithful representation of shared state by categorical projections. We finish the work by illustrating how the categorical semantics allows the incorporation into Prolog of constructs typical of Functional Programming, like abstract data types, and strict and lazy functions.

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.

Effectiveness of abstract interpretation in automatic parallelization: a case study in logic programming

We report on a detailed study of the application and effectiveness of program analysis based on abstract interpretation to automatic program parallelization. We study the case of parallelizing logic programs using the notion of strict independence. We first propose and prove correct a methodology for the application in the parallelization task of the information inferred by abstract interpretation, using a parametric domain. The methodology is generic in the sense of allowing the use of different analysis domains. A number of well-known approximation domains are then studied and the transformation into the parametric domain defined. The transformation directly illustrates the relevance and applicability of each abstract domain for the application. Both local and global analyzers are then built using these domains and embedded in a complete parallelizing compiler. Then, the performance of the domains in this context is assessed through a number of experiments. A comparatively wide range of aspects is studied, from the resources needed by the analyzers in terms of time and memory to the actual benefits obtained from the information inferred. Such benefits are evaluated both in terms of the characteristics of the parallelized code and of the actual speedups obtained from it. The results show that data flow analysis plays an important role in achieving efficient parallelizations, and that the cost of such analysis can be reasonable even for quite sophisticated abstract domains. Furthermore, the results also offer significant insight into the characteristics of the domains, the demands of the application, and the trade-offs involved.

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

Monitor s��smico interactivo

Este trabajo tiene como objetivos la monitorizaci��n en tiempo real de la actividad s��smica, tanto pr��xima como lejana, a partir de los datos s��smicos registrados por una estaci��n de banda ancha, y el desarrollo de un sistema de difusi��n interactiva de informaci��n actualizada de terremotos, destinado al p��blico general. Ambas fuentes de informaci��n se mostrar��n a trav��s de una Unidad de Visualizaci��n denominada ���Monitor S��smico Interactivo���. El registro de los datos s��smicos se realiza utilizando el sensor de tres componentes de la estaci��n s��smica GUD, perteneciente a la Red Digital de Banda Ancha y transmisi��n digital del Instituto Geogr��fico Nacional, instalada en la Bas��lica del Valle de los Ca��dos, en lalocalidad de Guadarrama (Madrid). En la E.T.S.I. Topograf��a, Geodesia y Cartograf��a se ha instalado un ordenador con conexi��n a Internet, para la recepci��n y almacenamiento de los datos, y los programas Scream y Drumplot desarrollados por Guralp, necesarios para la monitorizaci��n de la se��al s��smica en tiempo real. A partir de estos datos, mediante aplicaciones desarrolladas bajo programaci��n Linux y haciendo uso de las herramientas que ofrece el software SAC (Seismic Analysis Code), se genera adem��s un registro gr��fico y una pel��cula animada de dicha segmentaci��n para cada evento. Se ha configurado un servidor de correo y una cuenta para la recepci��n de dos tipos de mensajes de correo, enviados desde la sede central del Instituto Geogr��fico Nacional, con la informaci��n de los eventos registrados por GUD una vez revisados: - Mensajes enviados diariamente, con un listado de eventos ocurridos en los 30 ��ltimos d��as. - Mensajes con la informaci��n en cuasi tiempo real de la ��ltima alerta s��smica. Se ha desarrollado el programa ���saco��� para la gesti��n del correo recibido que analiza la informaci��n s��smica, la almacena en ficheros y ejecuta sobre ellos las aplicaciones de dibujo. Estas aplicaciones han sido previamente desarrolladas bajo programaci��n Linux y software GMT (Generic Mapping Tools), y a partir de ellas se generan autom��ticamente las distintas im��genes que se visualizan en el Monitor S��smico: un mapa de sismicidad pr��xima en la Pen��nsula Ib��rica, un mapa de sismicidad lejana en el mundo, un mapa de detalle para localizar y representar la ��ltima alerta generada, los listados con la informaci��n de los eventos representados en los mapas, los registros gr��ficos y las pel��culas animadas de dichos sismogramas. Monitor S��smico Interactivo ha sido desarrollado para ofrecer adem��s la posibilidad de interactuar con la Unidad de Visualizaci��n: se ha creado una base de datos para uso cient��fico donde se almacenan todos los eventos registrados por GUD. As�� el usuario puede realizar una petici��n, a trav��s del env��o de un mensaje de correo, que le permite visualizar de forma instant��nea las im��genes que muestran la informaci��n de cualquier terremoto de su inter��s. ABSTRACT This study is aimed at real-time monitoring of both near and distant seismic activityfrom the seismic data recorded by a broadband seismic station, and the development of an interactive broadcast system of updated information of earthquakes, for the general public. Bothsources of information are displayed through a display unit called "Interactive Seismic Monitor". The seismic data recording is carried out by using the three-component sensor of the GUD seismic station, which belongs to the Digital Network Broadband and digital broadcast of the National Geographic Institute, housed in the Basilica of The Valley of the Fallen, in the town of Guadarrama (Madrid). A computer with Internet connection has been installed in E.T.S.I. Surveying, Geodesy and Cartography for receiving and storing data, together with Scream and Drumplot programs, developed by Guralp, which are necessary for monitoring the real time seismic signal. Based on the data collected, through programming applications developed under Linux system and using the software tools provided by the SAC (Seismic Analysis Code), a chart recorder and an animated gif image of the segmentation for each event are also generated. A mail server and a mail account have been configured for the receipt of two types of email messages, sent from the National Geographic Institute head office, with the information of the events recorded by GUD after being reviewed: - Messages sent daily, providing a list of events in the past 30 days. - Messages containing information on near real-time seismic of the last seismic alert. A program called "saco" has also been developed for handling mail received that analyzes the seismic data, which stores it in files and runs drawing applications on them. These applications have been previously developed under Linux system and software programming GMT (Generic Mapping Tools), and from them different images that are displayed on the Seismic Monitor are automatically generated: a near seismicity Iberian peninsula map, a distant seismicity world map, a detailed map to locate and represent the last seismic alert generated, the lists with the information of the events depicted in the maps,together with the charts and the animated gif image of such seismograms. Interactive Seismic Monitor has been developed to offer any user the possibility of interacting with the display unit: a database has been created for scientific use which stores all the events recorded by GUD. Thus, any user could make a request, by sending an e-mail that allows them to view instantly all the images showing the information of any earthquake of interest on the display unit.

Automatic compile-time parallelization of logic programs for restricted, goal-level, independent and-parallelism.

A framework for the automatic parallelization of (constraint) logic programs is proposed and proved correct. Intuitively, the parallelization process replaces conjunctions of literals with parallel expressions. Such expressions trigger at run-time the exploitation of restricted, goal-level, independent and-parallelism. The parallelization process performs two steps. The first one builds a conditional dependency graph (which can be implified using compile-time analysis information), while the second transforms the resulting graph into linear conditional expressions, the parallel expressions of the &-Prolog language. Several heuristic algorithms for the latter ("annotation") process are proposed and proved correct. Algorithms are also given which determine if there is any loss of parallelism in the linearization process with respect to a proposed notion of maximal parallelism. Finally, a system is presented which implements the proposed approach. The performance of the different annotation algorithms is compared experimentally in this system by studying the time spent in parallelization and the effectiveness of the results in terms of speedups.

Exploiting goal independence in the analysis of logic programs

This paper illustrates the use of a top-down framework to obtain goal independent analyses of logic programs, a task which is usually associated with the bottom-up approach. While it is well known that the bottomup approach can be used, through the magic set transformation, for goal dependent analysis, it is less known that the top-down approach can be used for goal independent analysis. The paper describes two ways of doing the latter. We show how the results of a goal independent analysis can be used to speed up subsequent goal dependent analyses. However this speed-up may result in a loss of precisi��n. The influence of domain characteristics on this precisi��n is discussed and an experimental evaluation using a generic top-down analyzer is described.

Relating data���parallelism and (and���) parallelism in logic programs

Much work has been done in the ��reas of and-parallelism and data parallelism in Logic Programs. Such work has proceeded to a certain extent in an independent fashion. Both types of parallelism offer advantages and disadvantages. Traditional (and-) parallel models offer generality, being able to exploit parallelism in a large class of programs (including that exploited by data parallelism techniques). Data parallelism techniques on the other hand offer increased performance for a restricted class of programs. The thesis of this paper is that these two forms of parallelism are not fundamentally different and that relating them opens the possibility of obtaining the advantages of both within the same system. Some relevant issues are discussed and solutions proposed. The discussion is illustrated through visualizations of actual parallel executions implementing the ideas proposed.

Strict and non-strict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions.

This paper presents some fundamental properties of independent and-parallelism and extends its applicability by enlarging the class of goals eligible for parallel execution. A simple model of (independent) and-parallel execution is proposed and issues of correctness and efficiency discussed in the light of this model. Two conditions, "strict" and "non-strict" independence, are defined and then proved sufficient to ensure correctness and ef��ciency of parallel execution: if goals which meet these conditions are executed in parallel the solutions obtained are the same as those produced by standard sequential execution. Also, in absence of failure, the parallel proof procedure does not gen��rate any additional work (with respect to standard SLD-resolution) while the actual execution time is reduced. Finally, in case of failure of any of the goals no slow down will occur. For strict independence the results are shown to hold independently of whether the parallel goals execute in the same environment or in sep��rate environments. In addition, a formal basis is given for the automatic compile-time generation of independent and-parallelism: compile-time conditions to efficiently check goal independence at run-time are proposed and proved sufficient. Also, rules are given for constructing simpler conditions if information regarding the binding context of the goals to be executed in parallel is available to the compiler.

Automatic binding-related error diagnosis in logic programs

This paper proposes a diagnosis algorithm for locating a certain kind of errors in logic programs: variable binding errors that result in abstract symptoms during compile-time checking of assertions based on abstract interpretation. The diagnoser analyzes the graph generated by the abstract interpreter, which is a provably safe approximation of the program semantics. The proposed algorithm traverses this graph to find the point where the actual error originates (a reason of the symptom), leading to the point the error has been reported (the symptom). The procedure is fully automatic, not requiring any interaction with the user. A prototype diagnoser has been implemented and preliminary results are encouraging.

A flexible (C)LP-based approach to the analysis of object-oriented programs

Static analyses of object-oriented programs usually rely on intermediate representations that respect the original semantics while having a more uniform and basic syntax. Most of the work involving object-oriented languages and abstract interpretation usually omits the description of that language or just refers to the Control Flow Graph(CFG) it represents. However, this lack of formalization on one hand results in an absence of assurances regarding the correctness of the transformation and on the other it typically strongly couples the analysis to the source language. In this work we present a framework for analysis of object-oriented languages in which in a first phase we transform the input program into a representation based on Horn clauses. This allows on one hand proving the transformation correct attending to a simple condition and on the other being able to apply an existing analyzer for (constraint) logic programming to automatically derive a safe approximation of the semantics of the original program. The approach is flexible in the sense that the first phase decouples the analyzer from most languagedependent features, and correct because the set of Horn clauses returned by the transformation phase safely approximates the standard semantics of the input program. The resulting analysis is also reasonably scalable due to the use of mature, modular (C)LP-based analyzers. The overall approach allows us to report results for medium-sized programs.

User-definable resource bounds analysis for logic programs

We present a static analysis that infers both upper and lower bounds on the usage that a logic program makes of a set of user-definable resources. The inferred bounds will in general be functions of input data sizes. A resource in our approach is a quite general, user-defined notion which associates a basic cost function with elementary operations. The analysis then derives the related (upper- and lower-bound) resource usage functions for all predicates in the program. We also present an assertion language which is used to define both such resources and resourcerelated properties that the system can then check based on the results of the analysis. We have performed some preliminary experiments with some concrete resources such as execution steps, bytes sent or received by an application, number of files left open, number of accesses to a dat��base, number of calis to a procedure, number of asserts/retracts, etc. Applications of our analysis include resource consumption verification and debugging (including for mobile code), resource control in parallel/distributed computing, and resource-oriented specialization.

Context-sensitive multivariant assertion checking in modular programs

We propose a modular, assertion-based system for verification and debugging of large logic programs, together with several interesting models for checking assertions statically in modular programs, each with different characteristics and representing different trade-offs. Our proposal is a modular and multivariant extensi��n of our previously proposed abstract assertion checking model and we also report on its implementation in the CiaoPP system. In our approach, the specification of the program, given by a set of assertions, may be partial, instead of the complete specification required by raditional verification systems. Also, the system can deal with properties which cannot always be determined at compile-time. As a result, the proposed system needs to work with safe approximations: all assertions proved correct are guaranteed to be valid and all errors actual errors. The use of modular, context-sensitive static analyzers also allows us to introduce a new distinction between assertions checked in a particular context or checked in general.