On the uses of attributed variables in parallel and concurrent 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 defined, 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.

Some methodological issues in the design of CIAO, a generic, parallel concurrent constraint system

We informally discuss several issues related to the parallel execution of logic programming systems and concurrent logic programming systems, and their generalization to constraint programming. We propose a new view of these systems, based on a particular definition of parallelism. We argüe that, under this view, a large number of the actual systems and models can be explained through the application, at different levéis of granularity, of only a few basic principies: determinism, non-failure, independence (also referred to as stability), granularity, etc. Also, and based on the convergence of concepts that this view brings, we sketch a model for the implementation of several parallel constraint logic programming source languages and models based on a common, generic abstract machine and an intermedíate kernel language.

Towards CIAO-Prolog - A parallel concurrent constraint system

Abstract is not available.

Analysis of concurrent constraint logic programs with a fixed scheduling rule

The analysis of concurrent constraint programs is a challenge due to the inherently concurrent behaviour of its computational model. However, most implementations of the concurrent paradigm can be viewed as a computation with a fixed scheduling rule which suspends some goals so that their execution is postponed until some condition awakens them. For a certain kind of properties, an analysis defined in these terms is correct. Furthermore, it is much more tractable, and in addition can make use of existing analysis technology for the underlying fixed computation rule. We show how this can be done when the starting point is a framework for the analysis of sequential programs. The resulting analysis, which incorporates suspensions, is adequate for concurrent models where concurrency is localized, e.g. the Andorra model. We refine the analysis for this particular case. Another model in which concurrency is preferably encapsulated, and thus suspensions are local to parts of the computation, is that of CIAO. Nonetheless, the analysis scheme can be generalized to models with global concurrency. We also sketch how this could be done, and we show how the resulting analysis framework could be used for analyzing typical properties, such as suspensión freeness.

Advanced Topics in Resource Analysis: Certification, Incrementality, Concurrency and Array-Sensitivity

El Análisis de Consumo de Recursos o Análisis de Coste trata de aproximar el coste de ejecutar un programa como una función dependiente de sus datos de entrada. A pesar de que existen trabajos previos a esta tesis doctoral que desarrollan potentes marcos para el análisis de coste de programas orientados a objetos, algunos aspectos avanzados, como la eficiencia, la precisión y la fiabilidad de los resultados, todavía deben ser estudiados en profundidad. Esta tesis aborda estos aspectos desde cuatro perspectivas diferentes: (1) Las estructuras de datos compartidas en la memoria del programa son una pesadilla para el análisis estático de programas. Trabajos recientes proponen una serie de condiciones de localidad para poder mantener de forma consistente información sobre los atributos de los objetos almacenados en memoria compartida, reemplazando éstos por variables locales no almacenadas en la memoria compartida. En esta tesis presentamos dos extensiones a estos trabajos: la primera es considerar, no sólo los accesos a los atributos, sino también los accesos a los elementos almacenados en arrays; la segunda se centra en los casos en los que las condiciones de localidad no se cumplen de forma incondicional, para lo cual, proponemos una técnica para encontrar las precondiciones necesarias para garantizar la consistencia de la información acerca de los datos almacenados en memoria. (2) El objetivo del análisis incremental es, dado un programa, los resultados de su análisis y una serie de cambios sobre el programa, obtener los nuevos resultados del análisis de la forma más eficiente posible, evitando reanalizar aquellos fragmentos de código que no se hayan visto afectados por los cambios. Los analizadores actuales todavía leen y analizan el programa completo de forma no incremental. Esta tesis presenta un análisis de coste incremental, que, dado un cambio en el programa, reconstruye la información sobre el coste del programa de todos los métodos afectados por el cambio de forma incremental. Para esto, proponemos (i) un algoritmo multi-dominio y de punto fijo que puede ser utilizado en todos los análisis globales necesarios para inferir el coste, y (ii) una novedosa forma de almacenar las expresiones de coste que nos permite reconstruir de forma incremental únicamente las funciones de coste de aquellos componentes afectados por el cambio. (3) Las garantías de coste obtenidas de forma automática por herramientas de análisis estático no son consideradas totalmente fiables salvo que la implementación de la herramienta o los resultados obtenidos sean verificados formalmente. Llevar a cabo el análisis de estas herramientas es una tarea titánica, ya que se trata de herramientas de gran tamaño y complejidad. En esta tesis nos centramos en el desarrollo de un marco formal para la verificación de las garantías de coste obtenidas por los analizadores en lugar de analizar las herramientas. Hemos implementado esta idea mediante la herramienta COSTA, un analizador de coste para programas Java y KeY, una herramienta de verificación de programas Java. De esta forma, COSTA genera las garantías de coste, mientras que KeY prueba la validez formal de los resultados obtenidos, generando de esta forma garantías de coste verificadas. (4) Hoy en día la concurrencia y los programas distribuidos son clave en el desarrollo de software. Los objetos concurrentes son un modelo de concurrencia asentado para el desarrollo de sistemas concurrentes. En este modelo, los objetos son las unidades de concurrencia y se comunican entre ellos mediante llamadas asíncronas a sus métodos. La distribución de las tareas sugiere que el análisis de coste debe inferir el coste de los diferentes componentes distribuidos por separado. En esta tesis proponemos un análisis de coste sensible a objetos que, utilizando los resultados obtenidos mediante un análisis de apunta-a, mantiene el coste de los diferentes componentes de forma independiente. Abstract Resource Analysis (a.k.a. Cost Analysis) tries to approximate the cost of executing programs as functions on their input data sizes and without actually having to execute the programs. While a powerful resource analysis framework on object-oriented programs existed before this thesis, advanced aspects to improve the efficiency, the accuracy and the reliability of the results of the analysis still need to be further investigated. This thesis tackles this need from the following four different perspectives. (1) Shared mutable data structures are the bane of formal reasoning and static analysis. Analyses which keep track of heap-allocated data are referred to as heap-sensitive. Recent work proposes locality conditions for soundly tracking field accesses by means of ghost non-heap allocated variables. In this thesis we present two extensions to this approach: the first extension is to consider arrays accesses (in addition to object fields), while the second extension focuses on handling cases for which the locality conditions cannot be proven unconditionally by finding aliasing preconditions under which tracking such heap locations is feasible. (2) The aim of incremental analysis is, given a program, its analysis results and a series of changes to the program, to obtain the new analysis results as efficiently as possible and, ideally, without having to (re-)analyze fragments of code that are not affected by the changes. During software development, programs are permanently modified but most analyzers still read and analyze the entire program at once in a non-incremental way. This thesis presents an incremental resource usage analysis which, after a change in the program is made, is able to reconstruct the upper-bounds of all affected methods in an incremental way. To this purpose, we propose (i) a multi-domain incremental fixed-point algorithm which can be used by all global analyses required to infer the cost, and (ii) a novel form of cost summaries that allows us to incrementally reconstruct only those components of cost functions affected by the change. (3) Resource guarantees that are automatically inferred by static analysis tools are generally not considered completely trustworthy, unless the tool implementation or the results are formally verified. Performing full-blown verification of such tools is a daunting task, since they are large and complex. In this thesis we focus on the development of a formal framework for the verification of the resource guarantees obtained by the analyzers, instead of verifying the tools. We have implemented this idea using COSTA, a state-of-the-art cost analyzer for Java programs and KeY, a state-of-the-art verification tool for Java source code. COSTA is able to derive upper-bounds of Java programs while KeY proves the validity of these bounds and provides a certificate. The main contribution of our work is to show that the proposed tools cooperation can be used for automatically producing verified resource guarantees. (4) Distribution and concurrency are today mainstream. Concurrent objects form a well established model for distributed concurrent systems. In this model, objects are the concurrency units that communicate via asynchronous method calls. Distribution suggests that analysis must infer the cost of the diverse distributed components separately. In this thesis we propose a novel object-sensitive cost analysis which, by using the results gathered by a points-to analysis, can keep the cost of the diverse distributed components separate.

Automatic compile-time parallelization of CLP programs by analysis and transformation to a concurrent constraint language.

The concept of independence has been recently generalized to the constraint logic programming (CLP) paradigm. Also, several abstract domains specifically designed for CLP languages, and whose information can be used to detect the generalized independence conditions, have been recently defined. As a result we are now in a position where automatic parallelization of CLP programs is feasible. In this paper we study the task of automatically parallelizing CLP programs based on such analyses, by transforming them to explicitly concurrent programs in our parallel CC platform (CIAO) as well as to AKL. We describe the analysis and transformation process, and study its efficiency, accuracy, and effectiveness in program parallelization. The information gathered by the analyzers is evaluated not only in terms of its accuracy, i.e. its ability to determine the actual dependencies among the program variables, but also of its effectiveness, measured in terms of code reduction in the resulting parallelized programs. Given that only a few abstract domains have been already defined for CLP, and that none of them were specifically designed for dependency detection, the aim of the evaluation is not only to asses the effectiveness of the available domains, but also to study what additional information it would be desirable to infer, and what domains would be appropriate for further improving the parallelization process.

OSIA: Out-of-order scheduling for in-order arriving in concurrent multi-path transfer.

One major problem of concurrent multi-path transfer (CMT) scheme in multi-homed mobile networks is that the utilization of different paths with diverse delays may cause packet reordering among packets of the same ?ow. In the case of TCP-like, the reordering exacerbates the problem by bringing more timeouts and unnecessary retransmissions, which eventually degrades the throughput of connections considerably. To address this issue, we ?rst propose an Out-of-order Scheduling for In-order Arriving (OSIA), which exploits the sending time discrepancy to preserve the in-order packet arrival. Then, we formulate the optimal traf?c scheduling as a constrained optimization problem and derive its closedform solution by our proposed progressive water-?lling solution. We also present an implementation to enforce the optimal scheduling scheme using cascaded leaky buckets with multiple faucets, which provides simple guidelines on maximizing the utilization of aggregate bandwidth while decreasing the probability of triggering 3 dupACKs. Compared with previous work, the proposed scheme has lower computation complexity and can also provide the possibility for dynamic network adaptability and ?ner-grain load balancing. Simulation results show that our scheme signi?cantly alleviates reordering and enhances transmission performance.

Tropospheric scintillation with concurrent rain attenuation at 50 GHz in Madrid

Tropospheric scintillation can become a significant impairment in satellite communication systems, especially in those with low fade-margin. Moreover, fast amplitude fluctuations due to scintillation are even larger when rain is present on the propagation path. Few studies of scintillation during rain have been reported and the statistical characterization is still not totally clear. This paper presents experimental results on the relationship between scintillation and rain attenuation obtained from slant-path attenuation measurements at 50 GHz. The study is focused on the probability density function (PDF) of various scintillation parameters. It is shown that scintillation intensity, measured as the standard deviation of the amplitude fluctuations, increases with rain attenuation; in the range 1-10 dB this relationship can be expressed by power-law or linear equations. The PDFs of scintillation intensity conditioned to a given rain attenuation level are lognormal, while the overall long-term PDF is well fltted by a generalized extreme valué (GEV) distribution. The short-term PDFs of amplitude conditioned to a given intensity are normal, although skewness effects are observed for the strongest intensities. A procedure is given to derive numerically the overall PDF of scintillation amplitude using a combination of conditional PDFs and local statistics of rain attenuation.

Damage mechanisms in the handling of fruits

The recognition of an increasing and worldwide demand for high quality in fruits and vegetables has grown in recent years. Evidence of severe problems of mechanical damage is increasing, and this is affecting the trade of fruits in European and other countries. The potential market for fresh high-quality vegetables and fruits remains restricted by the lack of quality of the majority of products that reach consumers; this is the case for local as well as import/export markets, so a reduction in the consumption of fresh fruits in favour of other fixed-quality products (dairy in particular) may become widespread. In a recent survey (King, 1988, cited in Bellon, 1989), it appears that, for the moment, one third of the surveyed consumers are still continuing to increase their fresh produce consumption. The factors that appear as being most important in influencing the shopping behaviour of these consumers are taste/flavour, freshness/ripeness, appealing look, and cleanliness. Research on mechanical damage in fruit and vegetables has been underway for several years. The first research made on physical properties of fruits was in fact directed towards analysing the response to slow or rapid loading of selected fruits (Fridley et al, 1968; Horsefield et al., 1972). From that time on, research has expanded greatly, and different aspects of the problem have been approached. These include applicable mechanical models for the contact problem, the response of biological tissues to loading, devices for detecting damage causes in machines and equipment, and procedures for sensing bruises in grading and sorting. This chapter will be devoted to the study of actual research results relative to the cause and mechanisms of mechanical damage in fruits (secondarily in vegetables), the development of bruises in these commodities, the models that have been used up to now, and the different factors which have been recognized as influencing the appearance and development of mechanical damage in fruits. The study will be focused mainly on contact-damage - that is, slow or rapid loads applied to the surface of the products and causing bruises. (A bruise is defined as an altered volume of fruit tissues below the skin that is discoloured and softened.) Other types of mechanical damage, like abrasion and scuffing, punctures and cuts, will be also mentioned briefly.

Improving the competitiveness of the Spanish port system by optimising the cargo handling service

Port services, and in particular the cargo handling service, are responsible for the greatest share of costs incurred during the passage of cargo through a port. The provision of these services reliably and efficiently is crucial in a sector in which there is great opacity. This study has provided the responsible administration ? the Port Authority ? with a tool enabling objective decision making both when it comes to issuing the corresponding licenses and during the period of service provision. Furthermore, we have proposed a series of measures whose application would improve the conditions of service provision and reduce the costs incurred by the passage of cargo through the port.

Tomatoes for processing in the 90's: Postharvest handling.

Processing tomato industry has a high potential in Spain. Variety testing and mechanization studies and applications have been performed during the last 15 years. Many factors affect the quality and product losses during post-harvest handling which may be classified as: main or external factors: those related to the systems, procedures and devices; and fruit factors: those related to fruit properties. A research project is being carried on in the area of Vegas del Guadiana (Badajoz, Spain) to study these factors and to estimate costs, and to develop improved post-harvest handling practices.

Damage Mechanisms in the Handling of fruits.

Recent findings on the importance of losses due to damage incidence, on causes and on mechanisms of damage in fruits are reviewed and discussed. Incidence of damage in different fruits in some European markets has been -proved to be very high. Structure of fruit flesh and skin (hystology) is of foremost importance in the response of fruits to impacts and to compression. Continuous variation of fruit compositional and structural characteristics during maturation has to be taken into consideration when studying damage susceptibility.

Use of electronic fruits to evaluate fruit damage along the handling process.

Two electronic fruits (SEP-1, Simulated Electronic Product, developed in Scotland, and Techmark IS-100, Instrumented Sphere, developed in USA) have been compared in laboratory tests and then used to evaluate handling operations, in several cooperatives of two areas of Spain: Lérida (pome fruits) and Valencia (stone fruits). Advantages of each device were evaluated. Harvest, mechanical bin unloading, and grading line transfers and sizers were identified as operations causing fruit damage.

Neural bruise prediction models for fruit handling and machinery evaluation.

Some neural bruise prediction models have been implemented in the laboratory, for the most traded fruit species and varieties, allowing the prediction of the acceptability or rejectability for damages, with respect to the EC Standards. Different models have been built for both quasi-static (compression) and dynamic (impact) loads covering the whole commercial ripening period of fruits. A simulation process has been developed gathering the information on laboratory bruise models and load sensor calibrations for different electronic devices (IS-100 and DEA-1, for impact and compression loads respectively). Some evaluation methodology has been designed gathering the information on the mechanical properties of fruits and the loading records of electronic devices. The evaluation system allows to determine the current stage of fruit handling process and machinery.

Effects of precooling and degreening treatments on the susceptibility of peach and citrus to handling damage.

Mechanical damage to fruits results from a combination of fruit properties and of damage inflicting effects by the handling equipment. Treatments were applied to fruits which affect mechanical damage susceptibility: precooling for stone fruits and degreening to citrus fruits. Laboratory tests (compression, impact, tumbling, abrasion) and field tests (damage in the handling lines) were applied to (3) peach, (2) apricot, (2) orange and (1) lemon varieties. Hydroor-air-cooling influence positively peach and apricot firmness and cause a significant reduction in: number of bruised fruits, and size of visible bruise, when combined with a low level of loading during handling. Degreening also affects the resistance of citrus fruits to handling, when compared to green fruits.