Notional processors: an approach for multiprocessor scheduling

Consider the problem of designing an algorithm with a high utilisation bound for scheduling sporadic tasks with implicit deadlines on identical processors. A task is characterised by its minimum interarrival time and its execution time. Task preemption and migration is permitted. Still, low preemption and migration counts are desirable. We formulate an algorithm with a utilisation bound no less than 66.¯6%, characterised by worst-case preemption counts comparing favorably against the state-of-the-art.

A two-competitive approximate schedulability analysis of CAN

Consider the problem of deciding whether a set of n sporadic message streams meet deadlines on a Controller Area Network (CAN) bus for a specified priority assignment. It is assumed that message streams have implicit deadlines and no release jitter. An algorithm to solve this problem is well known but unfortunately it time complexity is non-polynomial. We present an algorithm with polynomial time-complexity for computing an upper bound on the response times. Clearly, if the upper bound on the response time does not exceed the deadline then all deadlines are met. The pessimism of our approach is proven: if the upper bound of the response time exceeds the deadline then the response time exceeds the deadline as well for a CAN network with half the speed.

Uniprocessor EDF scheduling with mode change

Consider the problem of scheduling sporadically-arriving tasks with implicit deadlines using Earliest-Deadline-First (EDF) on a single processor. The system may undergo changes in its operational modes and therefore the characteristics of the task set may change at run-time. We consider a well-established previously published mode-change protocol and we show that if every mode utilizes at most 50% of the processing capacity then all deadlines are met. We also show that there exists a task set that misses a deadline although the utilization exceeds 50% by just an arbitrarily small amount. Finally, we present, for a relevant special case, an exact schedulability test for EDF with mode change.

The utilization bound of uniprocessor preemptive slack-monotonic scheduling is 50%

Consider the problem of scheduling a set of sporadically arriving implicit-deadline tasks to meet deadlines on a uniprocessor. Static-priority scheduling is considered using the slack-monotonic priority-assignment scheme. We prove that its utilization bound is 50%.

Global static-priority preemptive multiprocessor scheduling with utilization bound 38%

Consider the problem of scheduling real-time tasks on a multiprocessor with the goal of meeting deadlines. Tasks arrive sporadically and have implicit deadlines, that is, the deadline of a task is equal to its minimum inter-arrival time. Consider this problem to be solved with global static-priority scheduling. We present a priority-assignment scheme with the property that if at most 38% of the processing capacity is requested then all deadlines are met.

ECG signals for biometric applications: are we there yet?

The potential of the electrocardiographic (ECG) signal as a biometric trait has been ascertained in the literature over the past decade. The inherent characteristics of the ECG make it an interesting biometric modality, given its universality, intrinsic aliveness detection, continuous availability, and inbuilt hidden nature. These properties enable the development of novel applications, where non-intrusive and continuous authentication are critical factors. Examples include, among others, electronic trading platforms, the gaming industry, and the auto industry, in particular for car sharing programs and fleet management solutions. However, there are still some challenges to overcome in order to make the ECG a widely accepted biometric. In particular, the questions of uniqueness (inter-subject variability) and permanence over time (intra-subject variability) are still largely unanswered. In this paper we focus on the uniqueness question, presenting a preliminary study of our biometric recognition system, testing it on a database encompassing 618 subjects. We also performed tests with subsets of this population. The results reinforce that the ECG is a viable trait for biometrics, having obtained an Equal Error Rate of 9.01% and an Error of Identification of 15.64% for the entire test population.

Implementation of the i-GAME mechanism in IEEE 802.15.4 WPANs

This technical report describes the implementation details of the Implicit GTS Allocation Mechanism (i-GAME), for the IEEE 802.15.4 protocol. The i-GAME was implemented in nesC/TinyOS for the CrossBow MICAz mote, over our own implementation of the IEEE 802.15.4 protocol stack. This document provides the implementation details, including a description of the i-GAME software interfaces.

On the robustness of the slotine-Li and the FPT/SVD-based adaptive controllers

A comparative study concerning the robustness of a novel, Fixed Point Transformations/Singular Value Decomposition (FPT/SVD)-based adaptive controller and the Slotine-Li (S&L) approach is given by numerical simulations using a three degree of freedom paradigm of typical Classical Mechanical systems, the cart + double pendulum. The effects of the imprecision of the available dynamical model, presence of dynamic friction at the axles of the drives, and the existence of external disturbance forces unknown and not modeled by the controller are considered. While the Slotine-Li approach tries to identify the parameters of the formally precise, available analytical model of the controlled system with the implicit assumption that the generalized forces are precisely known, the novel one makes do with a very rough, affine form and a formally more precise approximate model of that system, and uses temporal observations of its desired vs. realized responses. Furthermore, it does not assume the lack of unknown perturbations caused either by internal friction and/or external disturbances. Its another advantage is that it needs the execution of the SVD as a relatively time-consuming operation on a grid of a rough system-model only one time, before the commencement of the control cycle within which it works only with simple computations. The simulation examples exemplify the superiority of the FPT/SVD-based control that otherwise has the deficiency that it can get out of the region of its convergence. Therefore its design and use needs preliminary simulation investigations. However, the simulations also exemplify that its convergence can be guaranteed for various practical purposes.

ECG-based biometrics: A real time classification approach

Behavioral biometrics is one of the areas with growing interest within the biosignal research community. A recent trend in the field is ECG-based biometrics, where electrocardiographic (ECG) signals are used as input to the biometric system. Previous work has shown this to be a promising trait, with the potential to serve as a good complement to other existing, and already more established modalities, due to its intrinsic characteristics. In this paper, we propose a system for ECG biometrics centered on signals acquired at the subject's hand. Our work is based on a previously developed custom, non-intrusive sensing apparatus for data acquisition at the hands, and involved the pre-processing of the ECG signals, and evaluation of two classification approaches targeted at real-time or near real-time applications. Preliminary results show that this system leads to competitive results both for authentication and identification, and further validate the potential of ECG signals as a complementary modality in the toolbox of the biometric system designer.

Desenvolver o conhecimento sintático explícito no 1.º ciclo do ensino básico

Dissertação apresentada à Escola Superior de Educação de Lisboa para obtenção de grau de mestre em Didática da Língua Portuguesa

Examination timetabling automation using hybrid meta-heuristics

Trabalho de projeto realizado para obtenção do grau de Mestre em Engenharia Informática e de Computadores

Mining social individuals movements and friends based on mobile devices

Trabalho de Projeto realizado para obtenção do grau de Mestre em Engenharia Informática e de Computadores

Martulus e a questão polimétrica

O presente trabalho foi realizado como parte integrante do mestrado em música da Escola Superior de Música de Lisboa (ESML), e procurou explorar a utilização de “novos ritmos” (Belling, 2010), sobretudo a polimetria em uma peça para piano e percussão intitulada de “Martulus”, com pequena influência de células rítmicas afro-brasileiras e composta durante o último semestre do mestrado. A polimétrica realiza-se na peça sobrepondo, em vários momentos, os diferentes instrumentos em compassos diferentes uns dos outros o que resulta no fato de as barras de compassos por vezes não serem simétricas e o primeiro tempo do compasso acontecer em vários momentos diferentes, os instrumentos que utilizam duas claves, como o piano e a marimba, puderam utilizar às vezes de compassos diferentes em cada clave de forma sobreposta. A peça termina com o compasso de 0/8 e sem barras de compasso, o 8 do denominador faz alusão as colcheias que passa a ser a única forma de guia para os instrumentistas e ausência de primeiro tempo deixando a música suspensa sem acentos implícitos. A peça foi composta para 7 instrumentistas e 7 instrumentos; piano, marimba, tímpano, bumbo grande, caixa, congas, bongôs, e da forma como foi escrita um mesmo percussionista não pode tocar mais do que um instrumento.

ErasmusApp: A Location-Based Collaborative System for Erasmus Students

This paper reports on the design and development of an Android-based context-aware system to support Erasmus students during their mobility in Porto. It enables: (i) guest users to create, rate and store personal points of interest (POI) in a private, local on board database; and (ii) authenticated users to upload and share POI as well as get and rate recommended POI from the shared central database. The system is a distributed client / server application. The server interacts with a central database that maintains the user profiles and the shared POI organized by category and rating. The Android GUI application works both as a standalone application and as a client module. In standalone mode, guest users have access to generic info, a map-based interface and a local database to store and retrieve personal POI. Upon successful authentication, users can, additionally, share POI as well as get and rate recommendations sorted by category, rating and distance-to-user.

Task assignment algorithms for two-type heterogeneous multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising two different types of processors—such a platform is referred to as two-type platform. We present two low degree polynomial time-complexity algorithms, SA and SA-P, each providing the following guarantee. For a given two-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then (i) using SA, it is guaranteed to find such an assignment where the same restriction on task migration applies but given a platform in which processors are 1+α/2 times faster and (ii) SA-P succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which processors are 1+α times faster. The parameter 0<α≤1 is a property of the task set; it is the maximum of all the task utilizations that are no greater than 1. We evaluate average-case performance of both the algorithms by generating task sets randomly and measuring how much faster processors the algorithms need (which is upper bounded by 1+α/2 for SA and 1+α for SA-P) in order to output a feasible task assignment (intra-migrative for SA and non-migrative for SA-P). In our evaluations, for the vast majority of task sets, these algorithms require significantly smaller processor speedup than indicated by their theoretical bounds. Finally, we consider a special case where no task utilization in the given task set can exceed one and for this case, we (re-)prove the performance guarantees of SA and SA-P. We show, for both of the algorithms, that changing the adversary from intra-migrative to a more powerful one, namely fully-migrative, in which tasks can migrate between processors of any type, does not deteriorate the performance guarantees. For this special case, we compare the average-case performance of SA-P and a state-of-the-art algorithm by generating task sets randomly. In our evaluations, SA-P outperforms the state-of-the-art by requiring much smaller processor speedup and by running orders of magnitude faster.