Dynamic adaptation of stability periods for service level agreements

A QoS adaptation to dynamically changing system conditions that takes into consideration the user’s constraints on the stability of service provisioning is presented. The goal is to allow the system to make QoS adaptation decisions in response to fluctuations in task traffic flow, under the control of the user. We pay special attention to the case where monitoring the stability period and resource load variation of Service Level Agreements for different types of services is used to dynamically adapt future stability periods, according to a feedback control scheme. System’s adaptation behaviour can be configured according to a desired confidence level on future resource usage. The viability of the proposed approach is validated by preliminary experiments.

Implementation of a dominance protocol for wireless medium access

Consider the problem of scheduling sporadic message transmission requests with deadlines. For wired channels, this has been achieved successfully using the CAN bus. For wireless channels, researchers have recently proposed a similar solution; a collision-free medium access control (MAC) protocol that implements static-priority scheduling. Unfortunately no implementation has been reported, yet. We implement and evaluate it to find that the implementation indeed is collision-free and prioritized. This allows us to develop schedulability analysis for the implementation. We measure the response times of messages in our implementation and find that our new response-time analysis indeed offers an upper bound on the response times. This enables a new class of wireless real-time systems with timeliness guarantees for sporadic messages and it opens-up a new research area: schedulability analysis for wireless networks.

Fractional dynamics of a system with particles subjected to impacts

This paper studies the dynamics of a system composed of a collection of particles that exhibit collisions between them. Several entropy measures and different impact conditions of the particles are tested. The results reveal a Power Law evolution both of the system energy and the entropy measures, typical in systems having fractional dynamics.

An optimal boundary fair scheduling

Nowadays, many real-time operating systems discretize the time relying on a system time unit. To take this behavior into account, real-time scheduling algorithms must adopt a discrete-time model in which both timing requirements of tasks and their time allocations have to be integer multiples of the system time unit. That is, tasks cannot be executed for less than one time unit, which implies that they always have to achieve a minimum amount of work before they can be preempted. Assuming such a discrete-time model, the authors of Zhu et al. (Proceedings of the 24th IEEE international real-time systems symposium (RTSS 2003), 2003, J Parallel Distrib Comput 71(10):1411–1425, 2011) proposed an efficient “boundary fair” algorithm (named BF) and proved its optimality for the scheduling of periodic tasks while achieving full system utilization. However, BF cannot handle sporadic tasks due to their inherent irregular and unpredictable job release patterns. In this paper, we propose an optimal boundary-fair scheduling algorithm for sporadic tasks (named BF TeX ), which follows the same principle as BF by making scheduling decisions only at the job arrival times and (expected) task deadlines. This new algorithm was implemented in Linux and we show through experiments conducted upon a multicore machine that BF TeX outperforms the state-of-the-art discrete-time optimal scheduler (PD TeX ), benefiting from much less scheduling overheads. Furthermore, it appears from these experimental results that BF TeX is barely dependent on the length of the system time unit while PD TeX —the only other existing solution for the scheduling of sporadic tasks in discrete-time systems—sees its number of preemptions, migrations and the time spent to take scheduling decisions increasing linearly when improving the time resolution of the system.

Tolerância a falhas em sistemas de tempo-real distribuídos e embebidos

Este documento descreve um modelo de tolerância a falhas para sistemas de tempo-real distribuídos. A sugestão deste modelo tem como propósito a apresentação de uma solu-ção fiável, flexível e adaptável às necessidades dos sistemas de tempo-real distribuídos. A tolerância a falhas é um aspeto extremamente importante na construção de sistemas de tempo-real e a sua aplicação traz inúmeros benefícios. Um design orientado para a to-lerância a falhas contribui para um melhor desempenho do sistema através do melhora-mento de aspetos chave como a segurança, a confiabilidade e a disponibilidade dos sis-temas. O trabalho desenvolvido centra-se na prevenção, deteção e tolerância a falhas de tipo ló-gicas (software) e físicas (hardware) e assenta numa arquitetura maioritariamente basea-da no tempo, conjugada com técnicas de redundância. O modelo preocupa-se com a efi-ciência e os custos de execução. Para isso utilizam-se também técnicas tradicionais de to-lerância a falhas, como a redundância e a migração, no sentido de não prejudicar o tempo de execução do serviço, ou seja, diminuindo o tempo de recuperação das réplicas, em ca-so de ocorrência de falhas. Neste trabalho são propostas heurísticas de baixa complexida-de para tempo-de-execução, a fim de se determinar para onde replicar os componentes que constituem o software de tempo-real e de negociá-los num mecanismo de coordena-ção por licitações. Este trabalho adapta e estende alguns algoritmos que fornecem solu-ções ainda que interrompidos. Estes algoritmos são referidos em trabalhos de investiga-ção relacionados, e são utilizados para formação de coligações entre nós coadjuvantes. O modelo proposto colmata as falhas através de técnicas de replicação ativa, tanto virtual como física, com blocos de execução concorrentes. Tenta-se melhorar ou manter a sua qualidade produzida, praticamente sem introduzir overhead de informação significativo no sistema. O modelo certifica-se que as máquinas escolhidas, para as quais os agentes migrarão, melhoram iterativamente os níveis de qualidade de serviço fornecida aos com-ponentes, em função das disponibilidades das respetivas máquinas. Caso a nova configu-ração de qualidade seja rentável para a qualidade geral do serviço, é feito um esforço no sentido de receber novos componentes em detrimento da qualidade dos já hospedados localmente. Os nós que cooperam na coligação maximizam o número de execuções para-lelas entre componentes paralelos que compõem o serviço, com o intuito de reduzir atra-sos de execução. O desenvolvimento desta tese conduziu ao modelo proposto e aos resultados apresenta-dos e foi genuinamente suportado por levantamentos bibliográficos de trabalhos de in-vestigação e desenvolvimento, literaturas e preliminares matemáticos. O trabalho tem também como base uma lista de referências bibliográficas.

Energy-aware task mapping onto heterogeneous platforms using DVFS and sleep states

Heterogeneous multicore platforms are becoming an interesting alternative for embedded computing systems with limited power supply as they can execute specific tasks in an efficient manner. Nonetheless, one of the main challenges of such platforms consists of optimising the energy consumption in the presence of temporal constraints. This paper addresses the problem of task-to-core allocation onto heterogeneous multicore platforms such that the overall energy consumption of the system is minimised. To this end, we propose a two-phase approach that considers both dynamic and leakage energy consumption: (i) the first phase allocates tasks to the cores such that the dynamic energy consumption is reduced; (ii) the second phase refines the allocation performed in the first phase in order to achieve better sleep states by trading off the dynamic energy consumption with the reduction in leakage energy consumption. This hybrid approach considers core frequency set-points, tasks energy consumption and sleep states of the cores to reduce the energy consumption of the system. Major value has been placed on a realistic power model which increases the practical relevance of the proposed approach. Finally, extensive simulations have been carried out to demonstrate the effectiveness of the proposed algorithm. In the best-case, savings up to 18% of energy are reached over the first fit algorithm, which has shown, in previous works, to perform better than other bin-packing heuristics for the target heterogeneous multicore platform.

A framework for memory contention analysis in multi-core platforms

The last decade has witnessed a major shift towards the deployment of embedded applications on multi-core platforms. However, real-time applications have not been able to fully benefit from this transition, as the computational gains offered by multi-cores are often offset by performance degradation due to shared resources, such as main memory. To efficiently use multi-core platforms for real-time systems, it is hence essential to tightly bound the interference when accessing shared resources. Although there has been much recent work in this area, a remaining key problem is to address the diversity of memory arbiters in the analysis to make it applicable to a wide range of systems. This work handles diverse arbiters by proposing a general framework to compute the maximum interference caused by the shared memory bus and its impact on the execution time of the tasks running on the cores, considering different bus arbiters. Our novel approach clearly demarcates the arbiter-dependent and independent stages in the analysis of these upper bounds. The arbiter-dependent phase takes the arbiter and the task memory-traffic pattern as inputs and produces a model of the availability of the bus to a given task. Then, based on the availability of the bus, the arbiter-independent phase determines the worst-case request-release scenario that maximizes the interference experienced by the tasks due to the contention for the bus. We show that the framework addresses the diversity problem by applying it to a memory bus shared by a fixed-priority arbiter, a time-division multiplexing (TDM) arbiter, and an unspecified work-conserving arbiter using applications from the MediaBench test suite. We also experimentally evaluate the quality of the analysis by comparison with a state-of-the-art TDM analysis approach and consistently showing a considerable reduction in maximum interference.

Formal Contracts for Runtime Verification Support in the Ada Programming Language

Poster presented in The 28th GI/ITG International Conference on Architecture of Computing Systems (ARCS 2015). 24 to 26, Mar, 2015. Porto, Portugal.

Efficiency of strengthening techniques assessed for existing masonry buildings

The Azores archipelago is a zone with a vast cultural heritage, presenting a building stock mainly constructed in traditional stone masonry. It is known that this type of construction exhibits poor behaviour under seismic excitations; however it is extensively used in seismic prone areas, such as this case. The 9th of July of 1998 earthquake was the last seismic event in the islands, leaving many traditional stone constructions severely damaged or totally destroyed. This scenario led to an effort by the local government of improving the seismic resistance of these constructions, with the application of several reinforcement techniques. This work aims to study some of the most used reinforcement schemes after the 1998 earthquake, and to assess their effectiveness in the mitigation of the construction’s seismic vulnerability. A brief evaluation of the cost versus benefit of these retrofitting techniques is also made, seeking to identify those that are most suitable for each building typology. Thus, it was sought to analyze the case of real structures with different geometrical and physical characteristics, by establishing a comparison between the seismic performance of reinforced and non-reinforced structures. The first section contains the analysis of a total of six reinforcement scenarios for each building chosen. Using the recorded 1998 earthquake accelerograms, a linear time-history analysis was performed for each reinforcement scenario. A comparison was then established between the maximum displacements, inter-storey drift and maximum stress obtained, in order to evaluate the global seismic response of each reinforced structure. In the second part of the work, the examination of the performance obtained in the previous section, in relation to the cost of implementing each reinforcement technique, allowed to draw conclusions concerning the viability of implementing each reinforcement method, based on the book value of the buildings in study.

Multithreading RTOS processor design

Tese de Doutoramento Plano Doutoral em Engenharia Eletrónica e de Computadores.

Forearm surface EMG signals recognition and muscoloskeletal system dynamics identification using intelligent computational methods

Biosignals processing, Biological Nonlinear and time-varying systems identification, Electomyograph signals recognition, Pattern classification, Fuzzy logic and neural networks methods

Approximating subtree distances between Phylogenies

We give a 5-approximation algorithm to the rooted Subtree-Prune-and-Regraft (rSPR) distance between two phylogenies, which was recently shown to be NP-complete by Bordewich and Semple [5]. This paper presents the first approximation result for this important tree distance. The algorithm follows a standard format for tree distances such as Rodrigues et al. [24] and Hein et al. [13]. The novel ideas are in the analysis. In the analysis, the cost of the algorithm uses a \cascading" scheme that accounts for possible wrong moves. This accounting is missing from previous analysis of tree distance approximation algorithms. Further, we show how all algorithms of this type can be implemented in linear time and give experimental results.

Anàlisi del sistema operatiu RTLinux e implementació d'un entorn de desenvolupament de tasques en temps real (aplicat al control de processos)

El projecte "Anàlisi del sistema operatiu RTLinux i implementació d'un entorn de desenvolupament de tasques en temps real" analitza la possibilitat de crear un entorn de desenvolupament de tasques en temps real per poder crear sistemes de control complex, tot això mitjançant codi lliure. Inicialment es fa un aprenentatge sobre el concepte de temps real, després s'elegeix el sistema operatiu en temps real RTLinux per a crear l'entorn de desenvolupament utilitzant el llenguatge de programació Tcl/Tk. Es creen un conjunt d'aplicacions (pel control computacional) per estudiar la viabilitat de la construcció de l'entorn desitjat per facilitar la tasca de l'usuari final. Aquest projecte obre multitud de possibles camins a continuar: comunicació remota, implementació de planificadors, estudi de controladors, etc.

Coupling and monotonicity of queueing processes

The main purpose of this work is to give a survey of main monotonicity properties of queueing processes based on the coupling method. The literature on this topic is quite extensive, and we do not consider all aspects of this topic. Our more concrete goal is to select the most interesting basic monotonicity results and give simple and elegant proofs. Also we give a few new (or revised) proofs of a few important monotonicity properties for the queue-size and workload processes both in single-server and multi- server systems. The paper is organized as follows. In Section 1, the basic notions and results on coupling method are given. Section 2 contains known coupling results for renewal processes with focus on construction of synchronized renewal instants for a superposition of independent renewal processes. In Section 3, we present basic monotonicity results for the queue-size and workload processes. We consider both discrete-and continuous-time queueing systems with single and multi servers. Less known results on monotonicity of queueing processes with dependent service times and interarrival times are also presented. Section 4 is devoted to monotonicity of general Jackson-type queueing networks with Markovian routing. This section is based on the notable paper [17]. Finally, Section 5 contains elements of stability analysis of regenerative queues and networks, where coupling and monotonicity results play a crucial role to establish minimal suficient stability conditions. Besides, we present some new monotonicity results for tandem networks.

Propagation connectivity of random hypergraphs

We study the concept of propagation connectivity on random 3-uniform hypergraphs. This concept is inspired by a simple linear time algorithm for solving instances of certain constraint satisfaction problems. We derive upper and lower bounds for the propagation connectivity threshold, and point out some algorithmic implications.