Prioritizing constraint evaluation for efficient points-to analysis

Pervasive use of pointers in large-scale real-world applications continues to make points-to analysis an important optimization-enabler. Rapid growth of software systems demands a scalable pointer analysis algorithm. A typical inclusion-based points-to analysis iteratively evaluates constraints and computes a points-to solution until a fixpoint. In each iteration, (i) points-to information is propagated across directed edges in a constraint graph G and (ii) more edges are added by processing the points-to constraints. We observe that prioritizing the order in which the information is processed within each of the above two steps can lead to efficient execution of the points-to analysis. While earlier work in the literature focuses only on the propagation order, we argue that the other dimension, that is, prioritizing the constraint processing, can lead to even higher improvements on how fast the fixpoint of the points-to algorithm is reached. This becomes especially important as we prove that finding an optimal sequence for processing the points-to constraints is NP-Complete. The prioritization scheme proposed in this paper is general enough to be applied to any of the existing points-to analyses. Using the prioritization framework developed in this paper, we implement prioritized versions of Andersen's analysis, Deep Propagation, Hardekopf and Lin's Lazy Cycle Detection and Bloom Filter based points-to analysis. In each case, we report significant improvements in the analysis times (33%, 47%, 44%, 20% respectively) as well as the memory requirements for a large suite of programs, including SPEC 2000 benchmarks and five large open source programs.

Solving Dynamic Constraint Single Objective Functions using a Nature Inspired Technique

We present in this paper a new algorithm based on Particle Swarm Optimization (PSO) for solving Dynamic Single Objective Constrained Optimization (DCOP) problems. We have modified several different parameters of the original particle swarm optimization algorithm by introducing new types of particles for local search and to detect changes in the search space. The algorithm is tested with a known benchmark set and compare with the results with other contemporary works. We demonstrate the convergence properties by using convergence graphs and also the illustrate the changes in the current benchmark problems for more realistic correspondence to practical real world problems.

Dynamic Window-Constrained Scheduling for Real-Time Media Streaming

This paper describes an algorithm for scheduling packets in real-time multimedia data streams. Common to these classes of data streams are service constraints in terms of bandwidth and delay. However, it is typical for real-time multimedia streams to tolerate bounded delay variations and, in some cases, finite losses of packets. We have therefore developed a scheduling algorithm that assumes streams have window-constraints on groups of consecutive packet deadlines. A window-constraint defines the number of packet deadlines that can be missed in a window of deadlines for consecutive packets in a stream. Our algorithm, called Dynamic Window-Constrained Scheduling (DWCS), attempts to guarantee no more than x out of a window of y deadlines are missed for consecutive packets in real-time and multimedia streams. Using DWCS, the delay of service to real-time streams is bounded even when the scheduler is overloaded. Moreover, DWCS is capable of ensuring independent delay bounds on streams, while at the same time guaranteeing minimum bandwidth utilizations over tunable and finite windows of time. We show the conditions under which the total demand for link bandwidth by a set of real-time (i.e., window-constrained) streams can exceed 100% and still ensure all window-constraints are met. In fact, we show how it is possible to guarantee worst-case per-stream bandwidth and delay constraints while utilizing all available link capacity. Finally, we show how best-effort packets can be serviced with fast response time, in the presence of window-constrained traffic.

Constraint-based Mining of Frequent Arrangements of Temporal Intervals

The problem of discovering frequent arrangements of temporal intervals is studied. It is assumed that the database consists of sequences of events, where an event occurs during a time-interval. The goal is to mine temporal arrangements of event intervals that appear frequently in the database. The motivation of this work is the observation that in practice most events are not instantaneous but occur over a period of time and different events may occur concurrently. Thus, there are many practical applications that require mining such temporal correlations between intervals including the linguistic analysis of annotated data from American Sign Language as well as network and biological data. Two efficient methods to find frequent arrangements of temporal intervals are described; the first one is tree-based and uses depth first search to mine the set of frequent arrangements, whereas the second one is prefix-based. The above methods apply efficient pruning techniques that include a set of constraints consisting of regular expressions and gap constraints that add user-controlled focus into the mining process. Moreover, based on the extracted patterns a standard method for mining association rules is employed that applies different interestingness measures to evaluate the significance of the discovered patterns and rules. The performance of the proposed algorithms is evaluated and compared with other approaches on real (American Sign Language annotations and network data) and large synthetic datasets.

A tripartite microbial reporter gene system for real-time assays of soil nutrient status

Plant-derived carbon is the substrate which drives the rate of microbial assimilation and turnover of nutrients, in particular N and P, within the rhizosphere. To develop a better understanding of rhizosphere dynamics, a tripartite reporter gene system has been developed. We used three lux-marked Pseudomonas fluorescens strains to report on soil (1) assimilable carbon, (2) N-status, and (3) P-status. In vivo studies using soil water, spiked with C, N and P to simulate rhizosphere conditions, showed that the tripartite reporter system can provide real-time assessment of carbon and nutrient status. Good quantitative agreement for bioluminescence output between reference material and soil water samples was found for the C and P reporters. With regard to soil nitrate, the minimum bioavailable concentration was found to be greater than that analytically detectable in soil water. This is the first time that bioavailable soil C, N and P have been quantified using a tripartite reporter gene system.

Essays on supply chain's flexibility: a real options approach

A presente tese investiga o processo de tomada de decisão na gestão de cadeias de abastecimento, utilizando um quadro de análise de opções reais. Especificamente, estudamos tópicos como o nível de inventário ideal para protecção contra a incerteza da procura, o momento para implementação de capacidade flexível em mercados onde existe complexidade no mix de produtos, o tempo para o reforço do factor trabalho visando requisitos de serviço ao mercado, e as decisões entre integração e outsourcing num ambiente de incerteza. Foram usadas metodologias de tempo discreto e contínuo para identificar o valor ideal e o calendário das opções a adoptar, quando a procura é estocástica. Além disso, foram considerados os efeitos dos requisitos dos mercados, como a complexidade na oferta de produtos e o nível de serviço. A procura é representada recorrendo a diferentes processos estocásticos, o impacto de saltos inesperados também é explorado, reforçando a generalização dos modelos a diferentes condições de negócio. A aplicabilidade dos modelos que apresentamos permite a diversificação e o enriquecimento da literatura sobre a abordagem de opções reais, no âmbito das cadeias de abastecimento. Níveis de inventário flexíveis e capacidades flexíveis são característicos das cadeias de abastecimento e podem ser usados como resposta à incerteza do mercado. Esta tese é constituída por ensaios que suportam a aplicação dos modelos, e consiste num capítulo introdutório (designado por ensaio I) e mais seis ensaios sobre factores que discutem o uso de medidas de flexibilidade nas cadeias de abastecimento, em ambientes de incerteza, e um último ensaio sobre a extensão do conceito de flexibilidade ao tratamento da avaliação de planos de negócio. O segundo ensaio que apresentamos é sobre o valor do inventário num único estádio, enquanto medida de flexibilidade, sujeita ao crescente condicionalismo dos custos com posse de activos. Introduzimos uma nova classificação de artigos para suportar o indicador designado por overstock. No terceiro e quarto ensaio ampliamos a exploração do conceito de overstock, promovendo a interacção e o balanceamento entre vários estádios de uma cadeia de abastecimento, como forma de melhorar o desempenho global. Para sustentar a aplicação prática das abordagens, adaptamos o ensaio número três à gestão do desempenho, para suportar o estabelecimento de metas coordenadas e alinhadas; e adaptamos o quarto ensaio à coordenação das cadeias de abastecimento, como auxiliar ao planeamento integrado e sequencial dos níveis de inventário. No ensaio cinco analisamos o factor de produção “tecnologia”, em relação directa com a oferta de produtos de uma empresa, explorando o conceito de investimento, como medida de flexibilidade nas componentes de volume da procura e gama de produtos. Dedicamos o ensaio número seis à análise do factor de produção “Mão-de-Obra”, explorando as condicionantes para aumento do número de turnos na perspectiva económica e determinando o ponto crítico para a tomada de decisão em ambientes de incerteza. No ensaio número sete exploramos o conceito de internalização de operações, demarcando a nossa análise das demais pela definição do momento crítico que suporta a tomada de decisão em ambientes dinâmicos. Complementamos a análise com a introdução de factores temporais de perturbação, nomeadamente, o estádio de preparação necessário e anterior a uma eventual alteração de estratégia. Finalmente, no último ensaio, estendemos a análise da flexibilidade em ambientes de incerteza ao conceito de planos de negócio. Em concreto, exploramos a influência do número de pontos de decisão na flexibilidade de um plano, como resposta à crescente incerteza dos mercados. A título de exemplo, usamos o mecanismo de gestão sequencial do orçamento para suportar o nosso modelo. A crescente incerteza da procura obrigou a um aumento da agilidade e da flexibilidade das cadeias de abastecimento, limitando o uso de muitas das técnicas tradicionais de suporte à gestão, pela incapacidade de incorporarem os efeitos da incerteza. A flexibilidade é claramente uma vantagem competitiva das empresas que deve, por isso, ser quantificada. Com os modelos apresentados e com base nos resultados analisados, pretendemos demonstrar a utilidade da consideração da incerteza nos instrumentos de gestão, usando exemplos numéricos para suportar a aplicação dos modelos, o que claramente promove a aproximação dos desenvolvimentos aqui apresentados às práticas de negócio.

Accessing Planktothrix species diversity and associated toxins using quantitative real-time PCR in natural waters

Tese de Doutoramento em Biologia apresentada à Faculdade de Ciências da Universidade do Porto, 2015.

Label-free Detection of Microcystin-LR in Waters Using Real-Time Potentiometric Biosensors Based on Single-Walled Carbon Nanotubes Imprinted Polymers

Microcystin-LR (MC-LR) is a dangerous toxin found in environmental waters, quantified by high performance liquid chromatography and/or enzyme-linked immunosorbent assays. Quick, low cost and on-site analysis is thus required to ensure human safety and wide screening programs. This work proposes label-free potentiometric sensors made of solid-contact electrodes coated with a surface imprinted polymer on the surface of Multi-Walled Carbon NanoTubes (CNTs) incorporated in a polyvinyl chloride membrane. The imprinting effect was checked by using non-imprinted materials. The MC-LR sensitive sensors were evaluated, characterized and applied successfully in spiked environmental waters. The presented method offered the advantages of low cost, portability, easy operation and suitability for adaptation to flow methods.

Stereo-Based Head Pose Tracking Using Iterative Closest Point and Normal Flow Constraint

In this text, we present two stereo-based head tracking techniques along with a fast 3D model acquisition system. The first tracking technique is a robust implementation of stereo-based head tracking designed for interactive environments with uncontrolled lighting. We integrate fast face detection and drift reduction algorithms with a gradient-based stereo rigid motion tracking technique. Our system can automatically segment and track a user's head under large rotation and illumination variations. Precision and usability of this approach are compared with previous tracking methods for cursor control and target selection in both desktop and interactive room environments. The second tracking technique is designed to improve the robustness of head pose tracking for fast movements. Our iterative hybrid tracker combines constraints from the ICP (Iterative Closest Point) algorithm and normal flow constraint. This new technique is more precise for small movements and noisy depth than ICP alone, and more robust for large movements than the normal flow constraint alone. We present experiments which test the accuracy of our approach on sequences of real and synthetic stereo images. The 3D model acquisition system we present quickly aligns intensity and depth images, and reconstructs a textured 3D mesh. 3D views are registered with shape alignment based on our iterative hybrid tracker. We reconstruct the 3D model using a new Cubic Ray Projection merging algorithm which takes advantage of a novel data structure: the linked voxel space. We present experiments to test the accuracy of our approach on 3D face modelling using real-time stereo images.

Incremental Verification of Timing Constraints for Real-Time Systems

Testing constraints for real-time systems are usually verified through the satisfiability of propositional formulae. In this paper, we propose an alternative where the verification of timing constraints can be done by counting the number of truth assignments instead of boolean satisfiability. This number can also tell us how “far away” is a given specification from satisfying its safety assertion. Furthermore, specifications and safety assertions are often modified in an incremental fashion, where problematic bugs are fixed one at a time. To support this development, we propose an incremental algorithm for counting satisfiability. Our proposed incremental algorithm is optimal as no unnecessary nodes are created during each counting. This works for the class of path RTL. To illustrate this application, we show how incremental satisfiability counting can be applied to a well-known rail-road crossing example, particularly when its specification is still being refined.

Differential epipolar constraint in mobile robot egomotion estimation

The estimation of camera egomotion is a well established problem in computer vision. Many approaches have been proposed based on both the discrete and the differential epipolar constraint. The discrete case is mainly used in self-calibrated stereoscopic systems, whereas the differential case deals with a unique moving camera. The article surveys several methods for mobile robot egomotion estimation covering more than 0.5 million samples using synthetic data. Results from real data are also given

The tenant as a customer: can good service improve real estate performance?

Customer Relationship Management (CRM) theory suggests that good customer service results in satisfied customers, who in turn are more likely to remain loyal and recommend the service provider to others. Proponents of good customer service for tenants claim that landlords should see a return on any investment in their customer service, in the form of enhanced real estate performance. This paper begins by reviewing research on customer service returns in other industries. Through consideration of the characteristics of real estate markets, the paper explains how factors such as (inter alia) lease terms, property market cycles, and property type, might determine the relationship between customer service and real estate performance. The paper concludes that further research is needed to isolate specific aspects of customer service that are most appreciated by customers. It suggests that the financial returns which accrue to landlords adopting a customer-focused approach might indeed be quantified, and suggests an appropriate method for such future research.

Simple telemedicine for developing regions: Camera phones and paper-based microfluidic devices for real-time, off-site diagnosis

This article describes a prototype system for quantifying bioassays and for exchanging the results of the assays digitally with physicians located off-site. The system uses paper-based microfluidic devices for running multiple assays simultaneously, camera phones or portable scanners for digitizing the intensity of color associated with each colorimetric assay, and established communications infrastructure for transferring the digital information from the assay site to an off-site laboratory for analysis by a trained medical professional; the diagnosis then can be returned directly to the healthcare provider in the field. The microfluidic devices were fabricated in paper using photolithography and were functionalized with reagents for colorimetric assays. The results of the assays were quantified by comparing the intensities of the color developed in each assay with those of calibration curves. An example of this system quantified clinically relevant concentrations of glucose and protein in artificial urine. The combination of patterned paper, a portable method for obtaining digital images, and a method for exchanging results of the assays with off-site diagnosticians offers new opportunities for inexpensive monitoring of health, especially in situations that require physicians to travel to patients (e.g., in the developing world, in emergency management, and during field operations by the military) to obtain diagnostic information that might be obtained more effectively by less valuable personnel.

Constraint-based conversion of fiction text to a time-based graphical representation

This paper presents a method for converting unrestricted fiction text into a time-based graphical form. Key concepts extracted from the text are used to formulate constraints describing the interaction of entities in a scene. The solution of these constraints over their respective time intervals provides the trajectories for these entities in a graphical representation.

Three types of entity are extracted from fiction books to describe the scene, namely Avatars, Areas and Objects. We present a novel method for modeling the temporal aspect of a fiction story using multiple time-line representations after which the information extracted regarding entities and time-lines is used to formulate constraints. A constraint solving technique based on interval arithmetic is used to ensure that the behaviour of the entities satisfies the constraints over multiple universally quantified time intervals. This approach is demonstrated by finding solutions to multiple time-based constraints, and represents a new contribution to the field of Text-to-Scene conversion. An example of the automatically produced graphical output is provided in support of our constraint-based conversion scheme.

Um metamodelo da linguagem de modelagem real time UML, de suporte à criação de dicionário de dados para ferramentas de modelagem de sistema tempo real, visando a verificação de consistência dos modelos

A computação de tempo real é uma das áreas mais desafiadoras e de maior demanda tecnológica da atualidade. Está diretamente ligada a aplicações que envolvem índices críticos de confiabilidade e segurança. Estas características, inerentes a esta área da computação, vêm contribuindo para o aumento da complexidade dos sistemas tempo real e seu conseqüente desenvolvimento. Isto fez com que mecanismos para facilitar especificação, delimitação e solução de problemas passem a ser itens importantes para tais aplicações. Este trabalho propõe mecanismos para atuarem no desenvolvimento de sistemas de tempo real, com o objetivo de serem empregados como ferramenta de apoio no problema da verificação de presença de inconsistências, que podem vir a ocorrer nos vários modelos gerados partir da notação da linguagem de modelagem gráfica para sistemas de tempo real - UML-RT(Unified Modeling Language for Real Time). Estes mecanismos foram projetados através da construção de um metamodelo dos conceitos presentes nos diagramas de classe, de objetos, de seqüência, de colaboração e de estados. Para construir o metamodelo, utiliza-se a notação do diagrama de classes da UML (Unified Modeling Language). Contudo, por intermédio das representações gráficas do diagrama de classes não é possível descrever toda a semântica presente em tais diagramas. Assim, regras descritas em linguagem de modelagem OCL (Object Constraint Language) são utilizadas como um formalismo adicional ao metamodelo. Com estas descrições em OCL será possível a diminuição das possíveis ambigüidades e inconsistências, além de complementar as limitações impostas pelo caráter gráfico da UML. O metamodelo projetado é mapeado para um modelo Entidade&Relacionamento. A partir deste modelo, são gerados os scripts DDL (Data Definition Language) que serão usados na criação do dicionário de dados, no banco de dados Oracle. As descrições semânticas escritas através de regras em OCL são mapeadas para triggers, que disparam no momento em que o dicionário de dados é manipulado. O MET Editor do SiMOO-RT é a ferramenta diagramática que faz o povoamento dos dados no dicionário de dados. SiMOO-RT é uma ferramenta orientada a objetos para a modelagem, simulação e geração automática de código para sistemas de tempo real.