Efficient management of backtracking in and-parallelism

A backtracking algorithm for AND-Parallelism and its implementation at the Abstract Machine level are presented: first, a class of AND-Parallelism models based on goal independence is defined, and a generalized version of Restricted AND-Parallelism (RAP) introduced as characteristic of this class. A simple and efficient backtracking algorithm for R A P is then discussed. An implementation scheme is presented for this algorithm which offers minimum overhead, while retaining the performance and storage economy of sequent ial implementations and taking advantage of goal independence to avoid unnecessary backtracking ("restricted intelligent backtracking"). Finally, the implementation of backtracking in sequential and AND-Parallcl systems is explained through a number of examples.

Parallelism and implementation of logic and constraint logic programming

CIAO is an advanced programming environment supporting Logic and Constraint programming. It offers a simple concurrent kernel on top of which declarative and non-declarative extensions are added via librarles. Librarles are available for supporting the ISOProlog standard, several constraint domains, functional and higher order programming, concurrent and distributed programming, internet programming, and others. The source language allows declaring properties of predicates via assertions, including types and modes. Such properties are checked at compile-time or at run-time. The compiler and system architecture are designed to natively support modular global analysis, with the two objectives of proving properties in assertions and performing program optimizations, including transparently exploiting parallelism in programs. The purpose of this paper is to report on recent progress made in the context of the CIAO system, with special emphasis on the capabilities of the compiler, the techniques used for supporting such capabilities, and the results in the áreas of program analysis and transformation already obtained with the system.

The role of computational logic as a hinge paradigm among deduction, problem solving, programming, and parallelism

This paper presents some brief considerations on the role of Computational Logic in the construction of Artificial Intelligence systems and in programming in general. It does not address how the many problems in AI can be solved but, rather more modestly, tries to point out some advantages of Computational Logic as a tool for the AI scientist in his quest. It addresses the interaction between declarative and procedural views of programs (deduction and action), the impact of the intrinsic limitations of logic, the relationship with other apparently competing computational paradigms, and finally discusses implementation-related issues, such as the efficiency of current implementations and their capability for efficiently exploiting existing and future sequential and parallel hardware. The purpose of the discussion is in no way to present Computational Logic as the unique overall vehicle for the development of intelligent systems (in the firm belief that such a panacea is yet to be found) but rather to stress its strengths in providing reasonable solutions to several aspects of the task.

Towards high-level execution primitives for and-parallelism: preliminary results

Most implementations of parallel logic programming rely on complex low-level machinery which is arguably difflcult to implement and modify. We explore an alternative approach aimed at taming that complexity by raising core parts of the implementation to the source language level for the particular case of and-parallelism. Therefore, we handle a signiflcant portion of the parallel implementation mechanism at the Prolog level with the help of a comparatively small number of concurrency-related primitives which take care of lower-level tasks such as locking, thread management, stack set management, etc. The approach does not eliminate altogether modiflcations to the abstract machine, but it does greatly simplify them and it also facilitates experimenting with different alternatives. We show how this approach allows implementing both restricted and unrestricted (i.e., non fork-join) parallelism. Preliminary experiments show that the amount of performance sacriflced is reasonable, although granularity control is required in some cases. Also, we observe that the availability of unrestricted parallelism contributes to better observed speedups.

Towards a high-level implementation of flexible parallelism primitives for symbolic languages

An abstract is not available.

Estrategias Avanzadas de Tabulación y Paralelismo en Programas Lógicos = Advanced Evaluation Strategies for Tabling and Parallelism in Logic Programs

Dentro de los paradigmas de programación en el mundo de la informática tenemos la "Programación Lógica'', cuyo principal exponente es el lenguaje Prolog. Los programas Prolog se componen de un conjunto de predicados, cada uno de ellos definido en base a reglas que aportan un elevado nivel de abstracción y declaratividad al programador. Sin embargo, las formulación con reglas implica, frecuentemente, que un predicado se recompute varias veces para la misma consulta y además, Prolog utiliza un orden fijo para evaluar reglas y objetivos (evaluación SLD) que puede entrar en "bucles infinitos'' cuando ejecuta reglas recursivas declarativamente correctas. Estas limitaciones son atacadas de raiz por la tabulación, que se basa en "recordar'' en una tabla las llamadas realizadas y sus soluciones. Así, en caso de repetir una llamada tendríamos ya disponibles sus soluciones y evitamos la recomputación. También evita "bucles infinitos'' ya que las llamadas que los generan son suspendidas, quedando a la espera de que se computen soluciones para las mismas. La implementación de la tabulación no es sencilla. En particular, necesita de tres operaciones que no pueden ser ejecutadas en tiempo constante simultáneamente. Dichas operaciones son: suspensión de llamadas, relanzamiento de llamadas y {acceso a variables. La primera parte de la tesis compara tres implementaciones de tabulación sobre Ciao, cada una de las cuales penaliza una de estas operaciones. Por tanto, cada solución tiene sus ventajas y sus inconvenientes y se comportan mejor o peor dependiendo del programa ejecutado. La segunda parte de la tesis mejora la funcionalidad de la tabulación para combinarla con restricciones y también para evitar computaciones innecesarias. La programación con restricciones permite la resolución de ecuaciones como medio de programar, mecanismo altamente declarativo. Hemos desarrollado un framework para combinar la tabulación con las restricciones, priorizando objetivos como la flexibilidad, la eficiencia y la generalidad de nuestra solución, obteniendo una sinergia entre ambas técnicas que puede ser aplicada en numerosas aplicaciones. Por otra parte, un aspecto fundamental de la tabulación hace referencia al momento en que se retornan las soluciones de una llamada tabulada. Local evaluation devuelve soluciones cuando todas las soluciones de la llamada tabulada han sido computadas. Por contra, batched evaluation devuelve las soluciones una a una conforme van siendo computadas, por lo que se adapta mejor a problemas donde no nos interesa encontrar todas las soluciones. Sin embargo, su consumo de memoria es exponencialmente peor que el de local evaluation. La tesis presenta swapping evaluation, que devuelve soluciones tan pronto como son computadas pero con un consumo de memoria similar a la de local evaluation. Además, se implementan operadores de poda, once/1, para descartar la búsqueda de soluciones alternativas cuando encontramos la solución deseada. Por último, Prolog adopta con relativa facilidad soluciones para paralelismo gracias a su flexibilidad en el control de la ejecución y a que sus asignaciones son lógicas. La tercera parte de la tesis extiende el paralelismo conjuntivo de Ciao para trabajar con programas no deterministas, lo que presenta dos problemas principales: los objetivos atrapados y la recomputación de objetivos. Las soluciones clásicas para los objetivos atrapados rompían muchos invariantes de la ejecución Prolog, siendo soluciones difíciles de mantener y de extender, que la experiencia nos dice que han caído en desuso. Nosotros proponemos una solución modular (basada en la implementación de swapping evaluation), localizada y que no rompe los invariantes de la ejecución Prolog, pero que mantiene un alto rendimiento de la ejecución paralela. En referencia a la recomputación de objetivos paralelos en presencia de no determinismo hemos adaptado ténicas derivadas de la tabulación para memorizar computaciones de estos objetivos y evitar su recomputación.

A note on data-parallelism and (and-parallel) prolog

Abstract is not available.

A simulation study on parallel backtracking with solution memoing for independent and-parallelism

Goal-level Independent and-parallelism (IAP) is exploited by scheduling for simultaneous execution two or more goals which will not interfere with each other at run time. This can be done safely even if such goals can produce multiple answers. The most successful IAP implementations to date have used recomputation of answers and sequentially ordered backtracking. While in principle simplifying the implementation, recomputation can be very inefficient if the granularity of the parallel goals is large enough and they produce several answers, while sequentially ordered backtracking limits parallelism. And, despite the expected simplification, the implementation of the classic schemes has proved to involve complex engineering, with the consequent difficulty for system maintenance and expansion, and still frequently run into the well-known trapped goal and garbage slot problems. This work presents ideas about an alternative parallel backtracking model for IAP and a simulation studio. The model features parallel out-of-order backtracking and relies on answer memoization to reuse and combine answers. Whenever a parallel goal backtracks, its siblings also perform backtracking, but after storing the bindings generated by previous answers. The bindings are then reinstalled when combining answers. In order not to unnecessarily penalize forward execution, non-speculative and-parallel goals which have not been executed yet take precedence over sibling goals which could be backtracked over. Using a simulator, we show that this approach can bring significant performance advantages over classical approaches.

Automatic unrestricted independent and-parallelism in logic programs

We present new algorithms which perform automatic parallelization via source-to-source transformations. The objective is to exploit goal-level, unrestricted independent andparallelism. The proposed algorithms use as targets new parallel execution primitives which are simpler and more flexible than the well-known &/2 parallel operator, which makes it possible to generate better parallel expressions by exposing more potential parallelism among the literals of a clause than is possible with &/2. The main differences between the algorithms stem from whether the order of the solutions obtained is preserved or not, and on the use of determinacy information. We briefly describe the environment where the algorithms have been implemented and the runtime platform in which the parallelized programs are executed. We also report on an evaluation of an implementation of our approach. We compare the performance obtained to that of previous annotation algorithms and show that relevant improvements can be obtained.

Towards extracting non-strict independent and-parallelism using sharing and freeness information

Logic programming systems which exploit and-parallelism among non-deterministic goals rely on notions of independence among those goals in order to ensure certain efficiency properties. "Non-strict" independence (NSI) is a more relaxed notion than the traditional notion of "strict" independence (SI) which still ensures the relevant efficiency properties and can allow considerable more parallelism than SI. However, all compilation technology developed to date has been based on SI, presumably because of the intrinsic complexity of exploiting NSI. This is related to the fact that NSI cannot be determined "a priori" as SI. This paper fills this gap by developing a technique for compile-time detection and annotation of NSI. It also proposes algorithms for combined compile- time/run-time detection, presenting novel run-time checks for this type of parallelism. Also, a transformation procedure to eliminate shared variables among parallel goals is presented, attempting to perform as much work as possible at compiletime. The approach is based on the knowledge of certain properties about run-time instantiations of program variables —sharing and freeness— for which compile-time technology is available, with new approaches being currently proposed.

Independence, Global analysis, and parallelism, in dinamically scheduled constraint logic programming.

El punto de vista de muchas otras aplicaciones que modifican las reglas de computación. En segundo lugar, y una vez generalizado el concepto de independencia, es necesario realizar un estudio exhaustivo de la efectividad de las herramientas de análisis en la tarea de la paralelizacion automática. Los resultados obtenidos de dicha evaluación permiten asegurar de forma empírica que la utilización de analizadores globales en la tarea de la paralelizacion automática es vital para la consecución de una paralelizarían efectiva. Por último, a la luz de los buenos resultados obtenidos sobre la efectividad de los analizadores de flujo globales basados en la interpretación abstracta, se presenta la generalización de las herramientas de análisis al contexto de los lenguajes lógicos restricciones y planificación dinámica.

Techniques for improving the inherent parallelism in programs /

Thesis (M.S.) - University of Illinois at Urbana-Champaign.

Parallelism exposure and exploitation in programs /

Microfilm of typescript. Ann Arbor, Mich. : University Microfilms, 1971.

Notes on the use of parallelism in ultrahigh speed computer designs /

"December 12, 1955"

Parallelism exploitation and scheduling,

Vita.