Constructs and evaluation strategies for intelligent speculative parallelism - armageddon revisited

This report addresses speculative parallelism (the assignment of spare processing resources to tasks which are not known to be strictly required for the successful completion of a computation) at the user and application level. At this level, the execution of a program is seen as a (dynamic) tree —a graph, in general. A solution for a problem is a traversal of this graph from the initial state to a node known to be the answer. Speculative parallelism then represents the assignment of resources to múltiple branches of this graph even if they are not positively known to be on the path to a solution. In highly non-deterministic programs the branching factor can be very high and a naive assignment will very soon use up all the resources. This report presents work assignment strategies other than the usual depth-first and breadth-first. Instead, best-first strategies are used. Since their definition is application-dependent, the application language contains primitives that allow the user (or application programmer) to a) indícate when intelligent OR-parallelism should be used; b) provide the functions that define "best," and c) indícate when to use them. An abstract architecture enables those primitives to perform the search in a "speculative" way, using several processors, synchronizing them, killing the siblings of the path leading to the answer, etc. The user is freed from worrying about these interactions. Several search strategies are proposed and their implementation issues are addressed. "Armageddon," a global pruning method, is introduced, together with both a software and a hardware implementation for it. The concepts exposed are applicable to áreas of Artificial Intelligence such as extensive expert systems, planning, game playing, and in general to large search problems. The proposed strategies, although showing promise, have not been evaluated by simulation or experimentation.

Complete and efficient methods for supporting side effects in independent/restricted and-parallelism

It has been shown that it is possible to exploit Independent/Restricted And-parallelism in logic programs while retaining the conventional "don't know" semantics of such programs. In particular, it is possible to parallelize pure Prolog programs while maintaining the semantics of the language. However, when builtin side-effects (such as write or assert) appear in the program, if an identical observable behaviour to that of sequential Prolog implementations is to be preserved, such side-effects have to be properly sequenced. Previously proposed solutions to this problem are either incomplete (lacking, for example, backtracking semantics) or they force sequentialization of significant portions of the execution graph which could otherwise run in parallel. In this paper a series of side-effect synchronization methods are proposed which incur lower overhead and allow more parallelism than those previously proposed. Most importantly, and unlike previous proposals, they have well-defined backward execution behaviour and require only a small modification to a given (And-parallel) Prolog implementation.

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.

3D Wavelet-based Fusion Techniques for Biomedical Imaging

Hoy en día las técnicas de adquisición de imágenes tridimensionales son comunes en diversas áreas, pero cabe destacar la relevancia que han adquirido en el ámbito de la imagen biomédica, dentro del cual encontramos una amplia gama de técnicas como la microscopía confocal, microscopía de dos fotones, microscopía de fluorescencia mediante lámina de luz, resonancia magnética nuclear, tomografía por emisión de positrones, tomografía de coherencia óptica, ecografía 3D y un largo etcétera. Un denominador común de todas esas aplicaciones es la constante necesidad por aumentar la resolución y la calidad de las imágenes adquiridas. En algunas de dichas técnicas de imagen tridimensional se da una interesante situación: aunque que cada volumen adquirido no contiene información suficiente para representar el objeto bajo estudio dentro de los parámetros de calidad requeridos por algunas aplicaciones finales, el esquema de adquisición permite la obtención de varios volúmenes que representan diferentes vistas de dicho objeto, de tal forma que cada una de las vistas proporciona información complementaria acerca del mismo. En este tipo de situación es posible, mediante la combinación de varias de esas vistas, obtener una mejor comprensión del objeto que a partir de cada una de ellas por separado. En el contexto de esta Tesis Doctoral se ha propuesto, desarrollado y validado una nueva metodología de proceso de imágenes basada en la transformada wavelet disc¬reta para la combinación, o fusión, de varias vistas con información complementaria de un mismo objeto. El método de fusión propuesto aprovecha la capacidad de descom¬posición en escalas y orientaciones de la transformada wavelet discreta para integrar en un solo volumen toda la información distribuida entre el conjunto de vistas adquiridas. El trabajo se centra en dos modalidades diferentes de imagen biomédica que per¬miten obtener tales adquisiciones multi-vista. La primera es una variante de la micro¬scopía de fluorescencia, la microscopía de fluorescencia mediante lámina de luz, que se utiliza para el estudio del desarrollo temprano de embriones vivos en diferentes modelos animales, como el pez cebra o el erizo de mar. La segunda modalidad es la resonancia magnética nuclear con realce tardío, que constituye una valiosa herramienta para evaluar la viabilidad del tejido miocárdico en pacientes con diversas miocardiopatías. Como parte de este trabajo, el método propuesto ha sido aplicado y validado en am¬bas modalidades de imagen. En el caso de la aplicación a microscopía de fluorescencia, los resultados de la fusión muestran un mejor contraste y nivel de detalle en comparación con cualquiera de las vistas individuales y el método no requiere de conocimiento previo acerca la función de dispersión puntual del sistema de imagen. Además, los resultados se han comparado con otros métodos existentes. Con respecto a la aplicación a imagen de resonancia magnética con realce tardío, los volúmenes fusionados resultantes pre-sentan una mejora cuantitativa en la nitidez de las estructuras relevantes y permiten una interpretación más sencilla y completa de la compleja estructura tridimensional del tejido miocárdico en pacientes con cardiopatía isquémica. Para ambas aplicaciones los resultados de esta tesis se encuentran actualmente en uso en los centros clínicos y de investigación con los que el autor ha colaborado durante este trabajo. Además se ha puesto a libre disposición de la comunidad científica la implementación del método de fusión propuesto. Por último, se ha tramitado también una solicitud de patente internacional que cubre el método de visualización desarrollado para la aplicación de Resonancia Magnética Nuclear. Abstract Nowadays three dimensional imaging techniques are common in several fields, but es-pecially in biomedical imaging, where we can find a wide range of techniques including: Laser Scanning Confocal Microscopy, Laser Scanning Two Photon Microscopy, Light Sheet Fluorescence Microscopy, Magnetic Resonance Imaging, Positron Emission To-mography, Optical Coherence Tomography, 3D Ultrasound Imaging, etc. A common denominator of all those applications being the constant need for further increasing resolution and quality of the acquired images. Interestingly, in some of the mentioned three-dimensional imaging techniques a remarkable situation arises: while a single volume does not contain enough information to represent the object being imaged within the quality parameters required by the final application, the acquisition scheme allows recording several volumes which represent different views of a given object, with each of the views providing complementary information. In this kind of situation one can get a better understanding of the object by combining several views instead of looking at each of them separately. Within such context, in this PhD Thesis we propose, develop and test new image processing methodologies based on the discrete wavelet transform for the combination, or fusion, of several views containing complementary information of a given object. The proposed fusion method exploits the scale and orientation decomposition capabil¬ities of the discrete wavelet transform to integrate in a single volume all the available information distributed among the set of acquired views. The work focuses in two different biomedical imaging modalities which provide such multi-view datasets. The first one is a particular fluorescence microscopy technique, Light-Sheet Fluorescence Microscopy, used for imaging and gaining understanding of the early development of live embryos from different animal models (like zebrafish or sea urchin). The second is Delayed Enhancement Magnetic Resonance Imaging, which is a valuable tool for assessing the viability of myocardial tissue on patients suffering from different cardiomyopathies. As part of this work, the proposed method was implemented and then validated on both imaging modalities. For the fluorescence microscopy application, the fusion results show improved contrast and detail discrimination when compared to any of the individual views and the method does not rely on prior knowledge of the system’s point spread function (PSF). Moreover, the results have shown improved performance with respect to previous PSF independent methods. With respect to its application to Delayed Enhancement Magnetic Resonance Imaging, the resulting fused volumes show a quantitative sharpness improvement and enable an easier and more complete interpretation of complex three-dimensional scar and heterogeneous tissue information in ischemic cardiomyopathy patients. In both applications, the results of this thesis are currently in use in the clinical and research centers with which the author collaborated during his work. An imple¬mentation of the fusion method has also been made freely available to the scientific community. Finally, an international patent application has been filed covering the visualization method developed for the Magnetic Resonance Imaging application.

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.

Rapid prototyping for biomedical engineering: current capabilities and Challenges

A new set of manufacturing technologies has emerged in the past decades to address market requirements in a customized way and to provide support for research tasks that require prototypes. These new techniques and technologies are usually referred to as rapid prototyping and manufacturing technologies, and they allow prototypes to be produced in a wide range of materials with remarkable precision in a couple of hours. Although they have been rapidly incorporated into product development methodologies, they are still under development, and their applications in bioengineering are continuously evolving. Rapid prototyping and manufacturing technologies can be of assistance in every stage of the development process of novel biodevices, to address various problems that can arise in the devices' interactions with biological systems and the fact that the design decisions must be tested carefully. This review focuses on the main fields of application for rapid prototyping in biomedical engineering and health sciences, as well as on the most remarkable challenges and research trends.

CDAPubMed: a browser extension to retrieve EHR-based biomedical literature

Over the last few decades, the ever-increasing output of scientific publications has led to new challenges to keep up to date with the literature. In the biomedical area, this growth has introduced new requirements for professionals, e.g., physicians, who have to locate the exact papers that they need for their clinical and research work amongst a huge number of publications. Against this backdrop, novel information retrieval methods are even more necessary. While web search engines are widespread in many areas, facilitating access to all kinds of information, additional tools are required to automatically link information retrieved from these engines to specific biomedical applications. In the case of clinical environments, this also means considering aspects such as patient data security and confidentiality or structured contents, e.g., electronic health records (EHRs). In this scenario, we have developed a new tool to facilitate query building to retrieve scientific literature related to EHRs. Results: We have developed CDAPubMed, an open-source web browser extension to integrate EHR features in biomedical literature retrieval approaches. Clinical users can use CDAPubMed to: (i) load patient clinical documents, i.e., EHRs based on the Health Level 7-Clinical Document Architecture Standard (HL7-CDA), (ii) identify relevant terms for scientific literature search in these documents, i.e., Medical Subject Headings (MeSH), automatically driven by the CDAPubMed configuration, which advanced users can optimize to adapt to each specific situation, and (iii) generate and launch literature search queries to a major search engine, i.e., PubMed, to retrieve citations related to the EHR under examination. Conclusions: CDAPubMed is a platform-independent tool designed to facilitate literature searching using keywords contained in specific EHRs. CDAPubMed is visually integrated, as an extension of a widespread web browser, within the standard PubMed interface. It has been tested on a public dataset of HL7-CDA documents, returning significantly fewer citations since queries are focused on characteristics identified within the EHR. For instance, compared with more than 200,000 citations retrieved by breast neoplasm, fewer than ten citations were retrieved when ten patient features were added using CDAPubMed. This is an open source tool that can be freely used for non-profit purposes and integrated with other existing systems.