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.

Automatic parallelization of irregular and pointer-based computations: perspectives from logic and constraint programming

Irregular computations pose some 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. In the past decade there has been significant progress in the development of parallelizing compilers for logic programming and, more recently, constraint programming. The typical applications of these paradigms frequently involve irregular computations, which arguably makes the techniques used in these compilers potentially interesting. In this paper we introduce in a tutorial way some of the problems faced by parallelizing compilers for logic and constraint programs. These include the need for inter-procedural pointer aliasing analysis for independence detection and having to manage speculative and irregular computations through task granularity control and dynamic task allocation. We also provide pointers to some of the progress made in these áreas. In the associated talk we demónstrate representatives of several generations of these parallelizing compilers.

Hybrid wind-diesel power plant valuation and optimization using real option theory and dynamic programming

El sistema de energía eólica-diesel híbrido tiene un gran potencial en la prestación de suministro de energía a comunidades remotas. En comparación con los sistemas tradicionales de diesel, las plantas de energía híbridas ofrecen grandes ventajas tales como el suministro de capacidad de energía extra para "microgrids", reducción de los contaminantes y emisiones de gases de efecto invernadero, y la cobertura del riesgo de aumento inesperado del precio del combustible. El principal objetivo de la presente tesis es proporcionar nuevos conocimientos para la evaluación y optimización de los sistemas de energía híbrido eólico-diesel considerando las incertidumbres. Dado que la energía eólica es una variable estocástica, ésta no puede ser controlada ni predecirse con exactitud. La naturaleza incierta del viento como fuente de energía produce serios problemas tanto para la operación como para la evaluación del valor del sistema de energía eólica-diesel híbrido. Por un lado, la regulación de la potencia inyectada desde las turbinas de viento es una difícil tarea cuando opera el sistema híbrido. Por otro lado, el bene.cio económico de un sistema eólico-diesel híbrido se logra directamente a través de la energía entregada a la red de alimentación de la energía eólica. Consecuentemente, la incertidumbre de los recursos eólicos incrementa la dificultad de estimar los beneficios globales en la etapa de planificación. La principal preocupación del modelo tradicional determinista es no tener en cuenta la incertidumbre futura a la hora de tomar la decisión de operación. Con lo cual, no se prevé las acciones operativas flexibles en respuesta a los escenarios futuros. El análisis del rendimiento y simulación por ordenador en el Proyecto Eólico San Cristóbal demuestra que la incertidumbre sobre la energía eólica, las estrategias de control, almacenamiento de energía, y la curva de potencia de aerogeneradores tienen un impacto significativo sobre el rendimiento del sistema. En la presente tesis, se analiza la relación entre la teoría de valoración de opciones y el proceso de toma de decisiones. La opción real se desarrolla con un modelo y se presenta a través de ejemplos prácticos para evaluar el valor de los sistemas de energía eólica-diesel híbridos. Los resultados muestran que las opciones operacionales pueden aportar un valor adicional para el sistema de energía híbrida, cuando esta flexibilidad operativa se utiliza correctamente. Este marco se puede aplicar en la optimización de la operación a corto plazo teniendo en cuenta la naturaleza dependiente de la trayectoria de la política óptima de despacho, dadas las plausibles futuras realizaciones de la producción de energía eólica. En comparación con los métodos de valoración y optimización existentes, el resultado del caso de estudio numérico muestra que la política de operación resultante del modelo de optimización propuesto presenta una notable actuación en la reducción del con- sumo total de combustible del sistema eólico-diesel. Con el .n de tomar decisiones óptimas, los operadores de plantas de energía y los gestores de éstas no deben centrarse sólo en el resultado directo de cada acción operativa, tampoco deberían tomar decisiones deterministas. La forma correcta es gestionar dinámicamente el sistema de energía teniendo en cuenta el valor futuro condicionado en cada opción frente a la incertidumbre. ABSTRACT Hybrid wind-diesel power systems have a great potential in providing energy supply to remote communities. Compared with the traditional diesel systems, hybrid power plants are providing many advantages such as providing extra energy capacity to the micro-grid, reducing pollution and greenhouse-gas emissions, and hedging the risk of unexpected fuel price increases. This dissertation aims at providing novel insights for assessing and optimizing hybrid wind-diesel power systems considering the related uncertainties. Since wind power can neither be controlled nor accurately predicted, the energy harvested from a wind turbine may be considered a stochastic variable. This uncertain nature of wind energy source results in serious problems for both the operation and value assessment of the hybrid wind-diesel power system. On the one hand, regulating the uncertain power injected from wind turbines is a difficult task when operating the hybrid system. On the other hand, the economic profit of a hybrid wind-diesel system is achieved directly through the energy delivered to the power grid from the wind energy. Therefore, the uncertainty of wind resources has increased the difficulty in estimating the total benefits in the planning stage. The main concern of the traditional deterministic model is that it does not consider the future uncertainty when making the dispatch decision. Thus, it does not provide flexible operational actions in response to the uncertain future scenarios. Performance analysis and computer simulation on the San Cristobal Wind Project demonstrate that the wind power uncertainty, control strategies, energy storage, and the wind turbine power curve have a significant impact on the performance of the system. In this dissertation, the relationship between option pricing theory and decision making process is discussed. A real option model is developed and presented through practical examples for assessing the value of hybrid wind-diesel power systems. Results show that operational options can provide additional value to the hybrid power system when this operational flexibility is correctly utilized. This framework can be applied in optimizing short term dispatch decisions considering the path-dependent nature of the optimal dispatch policy, given the plausible future realizations of the wind power production. Comparing with the existing valuation and optimization methods, result from numerical example shows that the dispatch policy resulting from the proposed optimization model exhibits a remarkable performance in minimizing the total fuel consumption of the wind-diesel system. In order to make optimal decisions, power plant operators and managers should not just focus on the direct outcome of each operational action; neither should they make deterministic decisions. The correct way is to dynamically manage the power system by taking into consideration the conditional future value in each option in response to the uncertainty.

A syntactic approach to combining functional notation, lazy evaluation, and higher-order in LP systems

Nondeterminism and partially instantiated data structures give logic programming expressive power beyond that of functional programming. However, functional programming often provides convenient syntactic features, such as having a designated implicit output argument, which allow function cali nesting and sometimes results in more compact code. Functional programming also sometimes allows a more direct encoding of lazy evaluation, with its ability to deal with infinite data structures. We present a syntactic functional extensión, used in the Ciao system, which can be implemented in ISO-standard Prolog systems and covers function application, predefined evaluable functors, functional definitions, quoting, and lazy evaluation. The extensión is also composable with higher-order features and can be combined with other extensions to ISO-Prolog such as constraints. We also highlight the features of the Ciao system which help implementation and present some data on the overhead of using lazy evaluation with respect to eager evaluation.

Functional notation and lazy evaluation in Ciao

Certain aspects of functional programming provide syntactic convenience, such as having a designated implicit output argument, which allows function cali nesting and sometimes results in more compact code. Functional programming also sometimes allows a more direct encoding of lazy evaluation, with its ability to deal with infinite data structures. We present a syntactic functional extensión of Prolog covering function application, predefined evaluable functors, functional definitions, quoting, and lazy evaluation. The extensión is also composable with higher-order features. We also highlight the Ciao features which help implementation and present some data on the overhead of using lazy evaluation with respect to eager evaluation.

Transient behavior of a system composed of conductive thin wire structures excited by harmonic and lightning type signals

The transient response of a system of independent electrodes buried in a semi-infinite conducting medium is studied. Using a simple and versatile numerical scheme written by the authors and based on the Electric Field Integral Equation (EFIE), the effect caused by harmonic signals ranging on frequency from Hz to hundred of MHz, and also by lightning type driving signal striking at a remote point far from the conductors, is extensively studied. The value of the scalar potential appearing on the electrodes as a function of the frequency of the applied signal is one of the variables investigated. Other features such as the input impedance at the injection point of the signal and the Ground Potential Rise (GPR) over the electrode system are also discussed

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.

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.

WWW Programming using computational logic systems (and the PiLLoW/Ciao library)

We discuss from a practical point of view a number of issues involved in writing Internet and WWW applications using LP/CLP systems. We describe Pd_l_oW, a public-domain Internet and WWW programming library for LP/CLP systems which we argüe significantly simplifies the process of writing such applications. Pd_l_oW provides facilities for generating HTML structured documents, producing HTML forms, writing form handlers, accessing and parsing WWW documents, and accessing code posted at HTTP addresses. We also describe the architecture of some application classes, using a high-level model of client-server interaction, active modules. We then propose an architecture for automatic LP/CLP code downloading for local execution, using generic browsers. Finally, we also provide an overview of related work on the topic. The PiLLoW library has been developed in the context of the &- Prolog and CIAO systems, but it has been adapted to a number of popular LP/CLP systems, supporting most of its functionality.

Beam Spectral Element with FRP Debonding

The behaviour of the interface between the FRP and the concrete is the key factor controlling debonding failures in FRP-strengthened RC structures. This defect can cause reductions in static strength, structural integrity and the change in the dynamic behavior of the structure. The adverse effect on the dynamic behavior of the defects can be utilized as an effective means for identifying and assessing both the location and size of debonding at its earliest stages. The presence of debonding changes the structural dynamic characteristics and might be traced in modal parameters, dynamic strain and wave patterns etc. Detection of minor local defects, as those origin of a future debonding, requires working at high frequencies so that the wavelength of the excited is small and sensitive enough to detect local damage. The development of a spectral element method gives a large potential in high-frequency structural modeling. In contrast to the conventional finite element, since inertial properties are modeled exactly few elements are necessary to capture very accurate solutions at the highest frequencies in large regions. A wide variety of spectral elements have been developed for structural members over finite and semi-infinite regions. The objective of this paper is to develop a Spectral Finite Element Model to efficiently capture the behavior of intermediate debonding of a FRP strengthened RC beam during wave-based diagnostics.

Resonadores piezoeléctricos de cizalladura: estudio de la formación de biofilms y caracterización de fluidos magneto‐reológicos

La presente tesis revisa y analiza algunos aspectos fundamentales relativos al comportamiento de los sensores basados en resonadores piezoeléctricos TSM (Thickness Shear Mode), así como la aplicación de los mismos al estudio y caracterización de dos medios viscoelásticos de gran interés: los fluidos magnetoreológicos y los biofilms microbianos. El funcionamiento de estos sensores está basado en la medida de sus propiedades resonantes, las cuales varían al entrar en contacto con el material que se quiere analizar. Se ha realizado un análisis multifrecuencial, trabajando en varios modos de resonancia del transductor, en algunas aplicaciones incluso de forma simultánea (excitación pulsada). Se han revisado fenómenos como la presencia de microcontactos en la superficie del sensor y la resonancia de capas viscoelásticas de espesor finito, que pueden afectar a los sensores de cuarzo de manera contraria a lo que predice la teoría convencional (Sauerbrey y Kanazawa), pudiéndonos llevar a incrementos positivos de la frecuencia de resonancia. Además, se ha estudiado el efecto de una deposición no uniforme sobre el resonador piezoeléctrico. Para ello se han medido deposiciones de poliuretano, modelándose la respuesta del resonador con estas deposiciones mediante FEM. El modelo numérico permite estudiar el comportamiento del resonador al modificar distintas variables geométricas (espesor, superficie, no uniformidad y zona de deposición) de la capa depositada. Se ha demostrado que para espesores de entre un cuarto y media longitud de onda aproximadamente, una capa viscoelástica no uniforme sobre la superficie del sensor, amplifica el incremento positivo del desplazamiento de la frecuencia de resonancia en relación con una capa uniforme. Se ha analizado también el patrón geométrico de la sensibilidad del sensor, siendo también no uniforme sobre su superficie. Se han aplicado sensores TSM para estudiar los cambios viscoelásticos que se producen en varios fluidos magneto-reológicos (FMR) al aplicarles distintos esfuerzos de cizalla controlados por un reómetro. Se ha podido ver que existe una relación directa entre diversos parámetros reológicos obtenidos con el reómetro (fuerza normal, G’, G’’, velocidad de deformación, esfuerzo de cizalla…) y los parámetros acústicos, caracterizándose los FMR tanto en ausencia de campo magnético, como con campo magnético aplicado a distintas intensidades. Se han estudiado las ventajas que aporta esta técnica de medida sobre la técnica basada en un reómetro comercial, destacando que se consigue caracterizar con mayor detalle algunos aspectos relevantes del fluido como son la deposición de partículas (estabilidad del fluido), el proceso de ruptura de las estructuras formadas en los FMR tanto en presencia como en ausencia de campo magnético y la rigidez de los microcontactos que aparecen entre partículas y superficies. También se han utilizado sensores de cuarzo para monitorear en tiempo real la formación de biofilms de Staphylococcus epidermidis y Eschericia coli sobre los propios resonadores de cristal de cuarzo sin ningún tipo de recubrimiento, realizándose ensayos con cepas que presentan distinta capacidad de producir biofilm. Se mostró que, una vez que se ha producido una primera adhesión homogénea de las bacterias al sustrato, podemos considerar el biofilm como una capa semi-infinita, de la cual el sensor de cuarzo refleja las propiedades viscoelásticas de la región inmediatamente contigua al resonador, no siendo sensible a lo que sucede en estratos superiores del biofilm. Los experimentos han permitido caracterizar el módulo de rigidez complejo de los biofilms a varias frecuencias, mostrándose que el parámetro característico que indica la adhesión de un biofilm tanto en el caso de S. epidermidis como de E. coli, es el incremento de G’ (relacionado con la elasticidad o rigidez de la capa), el cual viene ligado a un incremento de la frecuencia de resonancia del sensor. ABSTRACT This thesis reviews and analyzes some key aspects of the behavior of sensors based on piezoelectric resonators TSM (Thickness Shear Mode) and their applications to the study and characterization in two viscoelastic media of great interest: magnetorheological fluids and microbial biofilms. The operation of these sensors is based on the analysis of their resonant properties that vary in contact with the material to be analyzed. We have made a multi-frequency analysis, working in several modes of resonance of the transducer, in some applications even simultaneously (by impulse excitation). We reviewed some phenomena as the presence of micro-contacts on the sensor surface and the resonance of viscoelastic layers of finite thickness, which can affect quartz sensors contrary to the conventional theory predictions (Sauerbrey and Kanazawa), leading to positive resonant frequency shifts. In addition, we studied the effect of non-uniform deposition on the piezoelectric resonator. Polyurethane stools have been measured, being the resonator response to these depositions modeled by FEM. The numerical model allows studying the behavior of the resonator when different geometric variables (thickness, surface non-uniformity and deposition zone) of the deposited layer are modified. It has been shown that for thicknesses between a quarter and a half of a wavelength approximately, non-uniform deposits on the sensor surface amplify the positive increase of the resonance frequency displacement compared to a uniform layer. The geometric pattern of the sensor sensitivity was also analyzed, being also non-uniform over its surface. TSM sensors have been applied to study the viscoelastic changes occurring in various magneto-rheological fluids (FMR) when subjected to different controlled shear stresses driven by a rheometer. It has been seen that there is a direct relationship between various rheological parameters obtained with the rheometer (normal force, G', G'', stress, shear rate ...) and the acoustic parameters, being the FMR characterized both in the absence of magnetic field, and when the magnetic field was applied at different intensities. We have studied the advantages of this technique over the characterization methods based on commercial rheometers, noting that TSM sensors are more sensitive to some relevant aspects of the fluid as the deposition of particles (fluid stability), the breaking process of the structures formed in the FMR both in the presence and absence of magnetic field, and the rigidity of the micro-contacts appearing between particles and surfaces. TSM sensors have also been used to monitor in real time the formation of biofilms of Staphylococcus epidermidis and Escherichia coli on the quartz crystal resonators themselves without any coating, performing tests with strains having different ability to produce biofilm. It was shown that, once a first homogeneous adhesion of bacteria was produced on the substrate, the biofilm can be considered as a semi-infinite layer and the quartz sensor reflects only the viscoelastic properties of the region immediately adjacent to the resonator, not being sensitive to what is happening in upper layers of the biofilm. The experiments allow the evaluation of the biofilm complex stiffness module at various frequencies, showing that the characteristic parameter that indicates the adhesion of a biofilm for the case of both S. epidermidis and E. coli, is an increased G' (related to the elasticity or stiffness of the layer), which is linked to an increase in the resonance frequency of the sensor.

Interfacing prolog and VRML and its application to constraint visualization

A number of data description languages initially designed as standards for trie WWW are currently being used to implement user interfaces to programs. This is done independently of whether such programs are executed in the same or a different host as trie one running the user interface itself. The advantage of this approach is that it provides a portable, standardized, and easy to use solution for the application programmer, and a familiar behavior for the user, typically well versed in the use of WWW browsers. Among the proposed standard description languages, VRML is a aimed at representing three dimensional scenes including hyperlink capabilities. VRML is already used as an import/export format in many 3-D packages and tools, and has been shown effective in displaying complex objects and scenarios. We propose and describe a Prolog library which allows parsing and checking VRML code, transforming it, and writing it out as VRML again. The library converts such code to an internal representation based on first order terms which can then be arbitrarily manipulated. We also present as an example application the use of this library to implement a novel 3-D visualization for examining and understanding certain aspects of the behavior of CLP(FD) programs.

From eventual to atomic and locally atomic CC programs: A concurrent semantics

We present a concurrent semantics (i.e. a semantics where concurrency is explicitely represented) for CC programs with atomic tells. This allows to derive concurrency, dependency, and nondeterminism information for such languages. The ability to treat failure information puts CLP programs also in the range of applicability of our semantics: although such programs are not concurrent, the concurrency information derived in the semantics may be interpreted as possible parallelism, thus allowing to safely parallelize those computation steps which appear to be concurrent in the net. Dually, the dependency information may also be interpreted as necessary sequentialization, thus possibly exploiting it to schedule CC programs. The fact that the semantical structure contains dependency information suggests a new tell operation, which checks for consistency only the constraints it depends on, achieving a reasonable trade-off between efficiency and atomicity.

Independent AND-parallel implementation of narrowing

We present a parallel graph narrowing machine, which is used to implement a functional logic language on a shared memory multiprocessor. It is an extensión of an abstract machine for a purely functional language. The result is a programmed graph reduction machine which integrates the mechanisms of unification, backtracking, and independent and-parallelism. In the machine, the subexpressions of an expression can run in parallel. In the case of backtracking, the structure of an expression is used to avoid the reevaluation of subexpressions as far as possible. Deterministic computations are detected. Their results are maintained and need not be reevaluated after backtracking.