Designing a high performance parallel logic programming system

Compilation techniques such as those portrayed by the Warren Abstract Machine(WAM) have greatly improved the speed of execution of logic programs. The research presented herein is geared towards providing additional performance to logic programs through the use of parallelism, while preserving the conventional semantics of logic languages. Two áreas to which special attention is given are the preservation of sequential performance and storage efficiency, and the use of low overhead mechanisms for controlling parallel execution. Accordingly, the techniques used for supporting parallelism are efficient extensions of those which have brought high inferencing speeds to sequential implementations. At a lower level, special attention is also given to design and simulation detail and to the architectural implications of the execution model behavior. This paper offers an overview of the basic concepts and techniques used in the parallel design, simulation tools used, and some of the results obtained to date.

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.

Acondicionamiento y procesado de señales mediante bus CAN en vehículos monoplaza

En este proyecto se ha diseñado un sistema de adquisición y uso compartido de datos orientado a la implantación en un vehículo monoplaza de Formula SAE. Más concretamente, se encarga de recoger la información proporcionada por cuatro sensores infrarrojos de temperatura que sondearán constantemente la temperatura a la que se encuentran las ruedas del vehículo. La información, recogida en una memoria de almacenamiento masivo, se compartirá con otros dispositivos mediante un bus común. Los sensores empleados para generar la información los proporciona Melexis. Dichos sensores permiten estar todos simultáneamente conectados en un bus común gracias a su electrónica interna. Mediante el bus I2C irán conectados los cuatro sensores de nuestra aplicación (uno por cada rueda) permitiéndose añadir a posteriori más sensores o incluso otros elementos que permitan la comunicación por este tipo de bus I2C. La gestión de las tareas se realiza mediante el microcontrolador DSPIC33FJ256GP710-I/PF proporcionado por Microchip. Este es un microcontrolador complejo, por lo que para nuestra aplicación desaprovecharemos parte de su potencial. En nuestra tarjeta ha sido solamente añadido el uso de los dos I2C (uno para la tarjeta SD y el otro para los sensores), el módulo ECAN1 (para las comunicaciones por bus CAN), el módulo SPI (para acceder a una memoria Flash), 4 ADCs (para posibles mediciones) y 2 entradas de interrupción (para posible interactuación con el usuario), a parte de los recursos internos necesarios. En este proyecto se realiza tanto el desarrollo de una tarjeta de circuito impreso dedicada a resolver la funcionalidad requerida, así como su programación a través del entorno de programación facilitado por Microchip, el ICD2 Programmer. In this project, an acquisition and sharing system of data, which is oriented to be installed in a Formula SAE single-seater vehicle, has been designed. Concretely, it is responsible for getting the information supplied by four IR temperature sensors that monitor the wheels temperature. The information, which is loaded in a massive storage memory, will be shared with other devices by means of a common bus. The sensors used to generate the information are supplied by Melexis. Such specific sensors let that all they can be connected to the same bus at the same time due to their internal electronic. The four sensors will be connected through an I2C bus, one for each wheel, although we could add later more sensors or even other devices that they were able to let the I2C communication. Tasks management will be done by means of the DSPIC33FJ256GP710-I/PF microcontroller, which will be supplied by Microchip. This is a complex microcontroller, so, in our application we waste off a part of its potential. In our PCB has only been incorporated the use of the two I2C (one for the SD card and the other for the sensors), the ECAN module (to communicate devices), the SPI module (to access to the Flash memory), 4 ADC’s (for possible measurements) and 2 interrupt inputs (for possible inter-action with the user), a part of the necessary internal resources. This project aims the PCB development dedicated to solve the requested functionality and its programming through the programming environment provided by Microchip (the ICD2 programmer).

Distributed www programming using (Ciao-) prolog and the pillow library

We discuss from a practical point of view a number of ssues involved in writing distributed Internet and WWW applications using LP/CLP systems. We describe PiLLoW, a publicdomain Internet and WWW programming library for LP/CLP systems that we have designed in order to simplify the process of writing such applications. PiLLoW provides facilities for accessing documents and code on the WWW; parsing, manipulating and generating HTML and XML structured documents and data; producing HTML forms; writing form handlers and CGI-scripts; and processing HTML/XML templates. An important contribution of PÍ'LLOW is to model HTML/XML code (and, thus, the content of WWW pages) as terms. The PÍ'LLOW library has been developed in the context of the Ciao Prolog system, but it has been adapted to a number of popular LP/CLP systems, supporting most of its functionality. We also describe the use of concurrency and a highlevel model of client-server interaction, Ciao Prolog's active modules, in the context of WWW programming. We propose a solution for client-side downloading and execution of Prolog code, using generic browsers. Finally, we also provide an overview of related work on the topic.

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.

Integrating software testing and run-time checking in an assertion verification framework

We have designed and implemented a framework that unifies unit testing and run-time verification (as well as static verification and static debugging). A key contribution of our approach is that a unified assertion language is used for all of these tasks. We first propose methods for compiling runtime checks for (parts of) assertions which cannot be verified at compile-time via program transformation. This transformation allows checking preconditions and postconditions, including conditional postconditions, properties at arbitrary program points, and certain computational properties. The implemented transformation includes several optimizations to reduce run-time overhead. We also propose a minimal addition to the assertion language which allows defining unit tests to be run in order to detect possible violations of the (partial) specifications expressed by the assertions. This language can express for example the input data for performing the unit tests or the number of times that the unit tests should be repeated. We have implemented the framework within the Ciao/CiaoPP system and effectively applied it to the verification of ISO-prolog compliance and to the detection of different types of bugs in the Ciao system source code. Several experimental results are presented that ¡Ilústrate different trade-offs among program size, running time, or levéis of verbosity of the messages shown to the user.

Hiord: A type-free higher-order logic programming language with predicate abstraction

A new formalism, called Hiord, for defining type-free higherorder logic programming languages with predicate abstraction is introduced. A model theory, based on partial combinatory algebras, is presented, with respect to which the formalism is shown sound. A programming language built on a subset of Hiord, and its implementation are discussed. A new proposal for defining modules in this framework is considered, along with several examples.

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.

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.

Using attributed variables in the implementation of concurrent and parallel logic programming systems

Incorporating the possibility of attaching attributes to variables in a logic programming system has been shown to allow the addition of general constraint solving capabilities to it. This approach is very attractive in that by adding a few primitives any logic programming system can be turned into a generic constraint logic programming system in which constraint solving can be user deñned, and at source level - an extreme example of the "glass box" approach. In this paper we propose a different and novel use for the concept of attributed variables: developing a generic parallel/concurrent (constraint) logic programming system, using the same "glass box" flavor. We argüe that a system which implements attributed variables and a few additional primitives can be easily customized at source level to implement many of the languages and execution models of parallelism and concurrency currently proposed, in both shared memory and distributed systems. We illustrate this through examples and report on an implementation of our ideas.

Towards a concurrent semantics-based analysis of CC and CLP. principles and practice of constraint programming

Abstract is not available.

Introduction to the 26th international conference on logic programming special issue

Abstract is not available

Agent Programming in Ciao Prolog

The agent programming landscape has been revealed as a natural framework for developing “intelligence” in AI. This can be seen from the extensive use of the agent concept in presenting (and developing) AI systems, the proliferation of agent theories, and the evolution of concepts such as agent societies (social intelligence) and coordination.

Program analysis, debugging and optimization using the ciao system preprocessor

We present a tutorial overview of Ciaopp, the Ciao system preprocessor. Ciao is a public-domain, next-generation logic programming system, which subsumes ISO-Prolog and is specifically designed to a) be highly extensible via librarles and b) support modular program analysis, debugging, and optimization. The latter tasks are performed in an integrated fashion by Ciaopp. Ciaopp uses modular, incremental abstract interpretation to infer properties of program predicates and literals, including types, variable instantiation properties (including modes), non-failure, determinacy, bounds on computational cost, bounds on sizes of terms in the program, etc. Using such analysis information, Ciaopp can find errors at compile-time in programs and/or perform partial verification. Ciaopp checks how programs cali system librarles and also any assertions present in the program or in other modules used by the program. These assertions are also used to genérate documentation automatically. Ciaopp also uses analysis information to perform program transformations and optimizations such as múltiple abstract specialization, parallelization (including granularity control), and optimization of run-time tests for properties which cannot be checked completely at compile-time. We illustrate "hands-on" the use of Ciaopp in all these tasks. By design, Ciaopp is a generic tool, which can be easily tailored to perform these and other tasks for different LP and CLP dialects.