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.

An Introductory Course on Constraint Logic Programming

The purpose of this document is to serve as the printed material for the seminar "An Introductory Course on Constraint Logic Programming". The intended audience of this seminar are industrial programmers with a degree in Computer Science but little previous experience with constraint programming. The seminar itself has been field tested, prior to the writing of this document, with a group of the application programmers of Esprit project P23182, "VOCAL", aimed at developing an application in scheduling of field maintenance tasks in the context of an electric utility company. The contents of this paper follow essentially the flow of the seminar slides. However, there are some differences. These differences stem from our perception from the experience of teaching the seminar, that the technical aspects are the ones which need more attention and clearer explanations in the written version. Thus, this document includes more examples than those in the slides, more exercises (and the solutions to them), as well as four additional programming projects, with which we hope the reader will obtain a clearer view of the process of development and tuning of programs using CLP. On the other hand, several parts of the seminar have been taken out: those related with the account of fields and applications in which C(L)P is useful, and the enumerations of C(L)P tools available. We feel that the slides are clear enough, and that for more information on available tools, the interested reader will find more up-to-date information by browsing the Web or asking the vendors directly. More details in this direction will actually boil down to summarizing a user manual, which is not the aim of this document.

Constraint-based runtime prediction of SLA violations in service orchestrations

Service compositions put together loosely-coupled component services to perform more complex, higher level, or cross-organizational tasks in a platform-independent manner. Quality-of-Service (QoS) properties, such as execution time, availability, or cost, are critical for their usability, and permissible boundaries for their values are defined in Service Level Agreements (SLAs). We propose a method whereby constraints that model SLA conformance and violation are derived at any given point of the execution of a service composition. These constraints are generated using the structure of the composition and properties of the component services, which can be either known or empirically measured. Violation of these constraints means that the corresponding scenario is unfeasible, while satisfaction gives values for the constrained variables (start / end times for activities, or number of loop iterations) which make the scenario possible. These results can be used to perform optimized service matching or trigger preventive adaptation or healing.

Tools for constraint visualisation: The VIFID/TRIFID tool

Visualisation of program executions has been used in applications which include education and debugging. However, traditional visualisation techniques often fall short of expectations or are altogether inadequate for new programming paradigms, such as Constraint Logic Programming (CLP), whose declarative and operational semantics differ in some crucial ways from those of other paradigms. In particular, traditional ideas regarding the behaviour of data often cannot be lifted in a straightforward way to (C)LP from other families of programming languages. In this chapter we discuss techniques for visualising data evolution in CLP. We briefly review some previously proposed visualisation paradigms, and also propose a number of (to our knowledge) novel ones. The graphical representations have been chosen based on the perceived needs of a programmer trying to analyse the behaviour and characteristics of an execution. In particular, we concentrate on the representation of the run-time values of the variables, and the constraints among them. Given our interest in visualising large executions, we also pay attention to abstraction techniques, i.e., techniques which are intended to help in reducing the complexity of the visual information.

Specialization and optimization of constraint programs with dynamic scheduling

In this report we discuss some of the issues involved in the specialization and optimization of constraint logic programs with dynamic scheduling. Dynamic scheduling, as any other form of concurrency, increases the expressive power of constraint logic programs, but also introduces run-time overhead. The objective of the specialization and optimization is to reduce as much as possible such overhead automatically, while preserving the semantics of the original programs. This is done by program transformation based on global analysis. We present implementation techniques for this purpose and report on experimental results obtained from an implementation of the techniques in the context of the CIAO compiler.

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.

Independence and search space preservation in dynamically scheduled constraint logic languages

This paper performs a further generalization of the notion of independence in constraint logic programs to the context of constraint logic programs with dynamic scheduling. The complexity of this new environment made necessary to first formally define the relationship between independence and search space preservation in the context of CLP languages. In particular, we show that search space preservation is, in the context of CLP languages, not only a sufficient but also a necessary condition for ensuring that both the intended solutions and the number of transitions performed do not change. These results are then extended to dynamically scheduled languages and used as the basis for the extension of the concepts of independence. We also propose several a priori sufficient conditions for independence and also give correctness and efficiency results for parallel execution of constraint logic programs based on the proposed notions of independence.

Timing performances of a data acquisition system for time of flight PET

We are investigating the performances of a data acquisition system for Time of Flight PET, based on LYSO crystal slabs and 64 channels Silicon Photomultipliers matrices (1.2 cm2 of active area each). Measurements have been performed to test the timing capability of the detection system (SiPM matices coupled to a LYSO slab and the read-out electronics) with both test signal and radioactive source.

A constraint-based approach to quality assurance in service choreographies.

Knowledge about the quality characteristics (QoS) of service com- positions is crucial for determining their usability and economic value. Ser- vice quality is usually regulated using Service Level Agreements (SLA). While end-to-end SLAs are well suited for request-reply interactions, more complex, decentralized, multiparticipant compositions (service choreographies) typ- ically involve multiple message exchanges between stateful parties and the corresponding SLAs thus encompass several cooperating parties with interde- pendent QoS. The usual approaches to determining QoS ranges structurally (which are by construction easily composable) are not applicable in this sce- nario. Additionally, the intervening SLAs may depend on the exchanged data. We present an approach to data-aware QoS assurance in choreographies through the automatic derivation of composable QoS models from partici- pant descriptions. Such models are based on a message typing system with size constraints and are derived using abstract interpretation. The models ob- tained have multiple uses including run-time prediction, adaptive participant selection, or design-time compliance checking. We also present an experimen- tal evaluation and discuss the benefits of the proposed approach.

Low-complexity timing synchronization scheme for MB-OFDM UWB receiver based on sign-bit

A unified low complexity sign-bit correlation based symbol timing synchronization scheme for Multiband Orthogonal Frequency Division Multiplexing (MB-OFDM) Ultra Wideband (UWB) receiver system is proposed. By using the time domain sequence of the packet/frame synchronization preamble, the proposed scheme is in charge of detecting the upcoming MB-OFDM symbol and it estimates the exact boundary of the start of Fast Fourier Transform (FFT) window. The proposed algorithm is implemented by using an efficient Hardware-Software co-simulation methodology. The effectiveness of the proposed synchronization scheme and the optimization criteria is confirmed by hardware implementation results.

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

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

Reconstructing the Timing and Dispersion Routes of HIV-1 Subtype B Epidemics in The Caribbean and Central America: A Phylogenetic Story.

The Caribbean and Central America are among the regions with highest HIV-1B prevalence worldwide. Despite of this high virus burden, little is known about the timing and the migration patterns of HIV-1B in these regions. Migration is one of the major processes shaping the genetic structure of virus populations. Thus, reconstruction of epidemiological network may contribute to understand HIV-1B evolution and reduce virus prevalence. We have investigated the spatio-temporal dynamics of the HIV-1B epidemic in The Caribbean and Central America using 1,610 HIV-1B partial pol sequences from 13 Caribbean and 5 Central American countries. Timing of HIV-1B introduction and virus evolutionary rates, as well as the spatial genetic structure of the HIV-1B populations and the virus migration patterns were inferred. Results revealed that in The Caribbean and Central America most of the HIV-1B variability was generated since the 80 s. At odds with previous data suggesting that Haiti was the origin of the epidemic in The Caribbean, our reconstruction indicated that the virus could have been disseminated from Puerto Rico and Antigua. These two countries connected two distinguishable migration areas corresponding to the (mainly Spanish-colonized) Easter and (mainly British-colonized) Western islands, which indicates that virus migration patterns are determined by geographical barriers and by the movement of human populations among culturally related countries. Similar factors shaped the migration of HIV-1B in Central America. The HIV-1B population was significantly structured according to the country of origin, and the genetic diversity in each country was associated with the virus prevalence in both regions, which suggests that virus populations evolve mainly through genetic drift. Thus, our work contributes to the understanding of HIV-1B evolution and dispersion pattern in the Americas, and its relationship with the geography of the area and the movements of human populations.

Phosphorylation Controls Timing of Cdc6p Destruction: A Biochemical Analysis

The replication initiation protein Cdc6p forms a tight complex with Cdc28p, specifically with forms of the kinase that are competent to promote replication initiation. We now show that potential sites of Cdc28 phosphorylation in Cdc6p are required for the regulated destruction of Cdc6p that has been shown to occur during the Saccharomyces cerevisiae cell cycle. Analysis of Cdc6p phosphorylation site mutants and of the requirement for Cdc28p in an in vitro ubiquitination system suggests that targeting of Cdc6p for degradation is more complex than previously proposed. First, phosphorylation of N-terminal sites targets Cdc6p for polyubiquitination probably, as expected, through promoting interaction with Cdc4p, an F box protein involved in substrate recognition by the Skp1-Cdc53-F-box protein (SCF) ubiquitin ligase. However, in addition, mutation of a single, C-terminal site stabilizes Cdc6p in G2 phase cells without affecting substrate recognition by SCF in vitro, demonstrating a second and novel requirement for specific phosphorylation in degradation of Cdc6p. SCF-Cdc4p– and N-terminal phosphorylation site–dependent ubiquitination appears to be mediated preferentially by Clbp/Cdc28p complexes rather than by Clnp/Cdc28ps, suggesting a way in which phosphorylation of Cdc6p might control the timing of its degradation at then end of G1 phase of the cell cycle. The stable cdc6 mutants show no apparent replication defects in wild-type strains. However, stabilization through mutation of three N-terminal phosphorylation sites or of the single C-terminal phosphorylation site leads to dominant lethality when combined with certain mutations in the anaphase-promoting complex.

Nucleotide binding and autophosphorylation of the clock protein KaiC as a circadian timing process of cyanobacteria

A negative feedback control of kaiC expression by KaiC protein has been proposed to generate a basic oscillation of the circadian clock in the cyanobacterium Synechococcus sp. PCC 7942. KaiC has two P loops or Walker's motif As, that are potential ATP-/GTP-binding motifs and DXXG motifs conserved in various GTP-binding proteins. Herein, we demonstrate that in vitro KaiC binds ATP and, with lower affinity, GTP. Point mutation by site-directed mutagenesis of P loop 1 completely nullified the circadian rhythm of kaiBC expression and markedly reduced ATP-binding activity. Moreover, KaiC can be autophosphorylated in vitro. These results suggest that the nucleotide-binding activity of KaiC plays important roles in the generation of circadian oscillation in cyanobacteria.