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.

Semi-Partitioned Scheduling of Fork-Join Tasks using Work-Stealing

13th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing (EUC 2015). 21 to 23, Oct, 2015, Session W1-A: Multiprocessing and Multicore Architectures. Porto, Portugal.

Hard real-time multiprocessor scheduling resilient to core failures

Presented at 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2015). 19 to 21, Aug, 2015, pp 122-131. Hong Kong, China.

Task assignment algorithms for two-type heterogeneous multiprocessors

Consider the problem of assigning real-time 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 linearithmic timecomplexity algorithms, SA and SA-P, each providing the follow- ing guarantee. For a given two-type platform and a given task set, if there exists a feasible task-to-processor-type assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type, then (i) using SA, it is guaranteed to find such a feasible task-to- processor-type 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 2 a feasible task-to-processor assignment where tasks are not allowed to migrate between processors but given a platform in which processors are 1+α/times faster, where 0<α≤1. The parameter α is a property of the task set — it is the maximum utilization of any task which is less than or equal to 1.

Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 × faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.

An Approach To Publish a Data Warehouse Content as Linked Data

Mestrado em Engenharia Informática - Área de Especialização em Tecnologias do Conhecimento e Decisão

Study of behavioural and neural bases of visuo-spatial working memory with an fMRI paradigm based on an n-back task

The goal of this study was to propose a new functional magnetic resonance imaging (fMRI) paradigm using a language-free adaptation of a 2-back working memory task to avoid cultural and educational bias. We additionally provide an index of the validity of the proposed paradigm and test whether the experimental task discriminates the behavioural performances of healthy participants from those of individuals with working memory deficits. Ten healthy participants and nine patients presenting working memory (WM) deficits due to acquired brain injury (ABI) performed the developed task. To inspect whether the paradigm activates brain areas typically involved in visual working memory (VWM), brain activation of the healthy participants was assessed with fMRIs. To examine the task's capacity to discriminate behavioural data, performances of the healthy participants in the task were compared with those of ABI patients. Data were analysed with GLM-based random effects procedures and t-tests. We found an increase of the BOLD signal in the specialized areas of VWM. Concerning behavioural performances, healthy participants showed the predicted pattern of more hits, less omissions and a tendency for fewer false alarms, more self-corrected responses, and faster reaction times, when compared with subjects presenting WM impairments. The results suggest that this task activates brain areas involved in VWM and discriminates behavioural performances of clinical and non-clinical groups. It can thus be used as a research methodology for behavioural and neuroimaging studies of VWM in block-design paradigms.

Delineating environmental groundwater vulnerability and protection zones mapping in fractured rock masses

Hard‐rock watersheds commonly exhibit complex geological bedrock and morphological features. Hydromineral resources have relevant economic value for the thermal spas industry. The present study aims to develop a groundwater vulnerability approach in Caldas da Cavaca hydromineral system (Aguiar da Beira, Central Portugal) which has a thermal tradition that dates back to the late 19th century, and contribute to a better understanding of the hydrogeological conceptual site model. In this work different layers were overlaid, generating several thematic maps to arrive at an integrated framework of several key‐sectors in Caldas da Cavaca site. Thus, to accomplish a comprehensive analysis and conceptualization of the site, a multi‐technical approach was used, such as, field and laboratory techniques, where several data was collected, like geotectonics, hydrology and hydrogeology, hydrogeomorphology, hydrogeophysical and hydrogeomechanical zoning aiming the application of the so‐called DISCO method. All these techniques were successfully performed and a groundwater vulnerability to contamination assessment, based on GOD‐S, DRASTIC‐Fm, SINTACS, SI and DISCO indexes methodology, was delineated. Geographical Information Systems (GIS) technology was on the basis to organise and integrate the geodatabases and to produce all the thematic maps. This multi‐technical approach highlights the importance of groundwater vulnerability to contamination mapping as a tool to support hydrogeological conceptualisation, contributing to better decision‐making of water resources management and sustainability.

O contributo da terapia ocupacional na análise dos ajustes posturais antecipatórios em crianças com 9 e 10 anos de idade, num sistema de captura de movimento - BioStage

O trabalho realizado teve como objetivo principal analisar os ajustes posturais antecipatórios que ocorrem durante o desempenho de uma tarefa motora fundamental (apanhar), em crianças entre os nove e os dez anos de idade, residentes no Porto e que apresentam um desenvolvimento normal com recurso ao sistema de captura e parametrização do movimento em tempo real BioStage ®. Como objetivo secundário pretendeu-se perceber de que forma este sistema pode ser uma ferramenta importante na prática clínica da terapia ocupacional. Para tal, realizou-se um estudo de natureza quantitativa e de carácter descritivo e recorreu-se a uma amostra de 12 crianças, utilizando o método de amostragem não probabilística por conveniência. A recolha de dados efetuou-se no sistema BioStage ® e foi pedido que realizassem quatro itens do subteste 5 do Bruininks-Oseretsky Test of Motor Proficiency (BOTMP) – receção bi e unilateral de uma bola com e sem ressalto no chão. Os resultados obtidos sugerem que as raparigas e as crianças mais novas demonstram ter menos estabilidade do tronco e pélvis ou menor capacidade de prever a trajetória da bola e que a receção unilateral foi mais difícil de efetuar pela maioria das crianças. Para concluir, refere-se que o BioStage ® mostra-se útil e é uma mais-valia, contribuindo de forma positiva para a prática da terapia ocupacional, uma vez que pode ser considerado como um complemento ao processo de avaliação pois faz uma análise detalhada, precisa e objetiva e identifica aspetos de difícil mensuração através da observação.

Multi-apprentice learning for meta-heuristics parameter tuning in a multi agent scheduling system

The scheduling problem is considered in complexity theory as a NP-hard combinatorial optimization problem. Meta-heuristics proved to be very useful in the resolution of this class of problems. However, these techniques require parameter tuning which is a very hard task to perform. A Case-based Reasoning module is proposed in order to solve the parameter tuning problem in a Multi-Agent Scheduling System. A computational study is performed in order to evaluate the proposed CBR module performance.

Sistema de aquisição de dados em tempo real

Neste trabalho propus-me realizar um Sistema de Aquisição de Dados em Tempo Real via Porta Paralela. Para atingir com sucesso este objectivo, foi realizado um levantamento bibliográfico sobre sistemas operativos de tempo real, salientando e exemplificando quais foram marcos mais importantes ao longo da sua evolução. Este levantamento permitiu perceber o porquê da proliferação destes sistemas face aos custos que envolvem, em função da sua aplicação, bem como as dificuldades, científicas e tecnológicas, que os investigadores foram tendo, e que foram ultrapassando com sucesso. Para que Linux se comporte como um sistema de tempo real, é necessário configura-lo e adicionar um patch, como por exemplo o RTAI ou ADEOS. Como existem vários tipos de soluções que permitem aplicar as características inerentes aos sistemas de tempo real ao Linux, foi realizado um estudo, acompanhado de exemplos, sobre o tipo de arquitecturas de kernel mais utilizadas para o fazer. Nos sistemas operativos de tempo real existem determinados serviços, funcionalidades e restrições que os distinguem dos sistemas operativos de uso comum. Tendo em conta o objectivo do trabalho, e apoiado em exemplos, fizemos um pequeno estudo onde descrevemos, entre outros, o funcionamento escalonador, e os conceitos de latência e tempo de resposta. Mostramos que há apenas dois tipos de sistemas de tempo real o ‘hard’ que tem restrições temporais rígidas e o ‘soft’ que engloba as restrições temporais firmes e suaves. As tarefas foram classificadas em função dos tipos de eventos que as despoletam, e evidenciando as suas principais características. O sistema de tempo real eleito para criar o sistema de aquisição de dados via porta paralela foi o RTAI/Linux. Para melhor percebermos o seu comportamento, estudamos os serviços e funções do RTAI. Foi dada especial atenção, aos serviços de comunicação entre tarefas e processos (memória partilhada e FIFOs), aos serviços de escalonamento (tipos de escalonadores e tarefas) e atendimento de interrupções (serviço de rotina de interrupção - ISR). O estudo destes serviços levou às opções tomadas quanto ao método de comunicação entre tarefas e serviços, bem como ao tipo de tarefa a utilizar (esporádica ou periódica). Como neste trabalho, o meio físico de comunicação entre o meio ambiente externo e o hardware utilizado é a porta paralela, também tivemos necessidade de perceber como funciona este interface. Nomeadamente os registos de configuração da porta paralela. Assim, foi possível configura-lo ao nível de hardware (BIOS) e software (módulo do kernel) atendendo aos objectivos do presente trabalho, e optimizando a utilização da porta paralela, nomeadamente, aumentando o número de bits disponíveis para a leitura de dados. No desenvolvimento da tarefa de hard real-time, foram tidas em atenção as várias considerações atrás referenciadas. Foi desenvolvida uma tarefa do tipo esporádica, pois era pretendido, ler dados pela porta paralela apenas quando houvesse necessidade (interrupção), ou seja, quando houvesse dados disponíveis para ler. Desenvolvemos também uma aplicação para permitir visualizar os dados recolhidos via porta paralela. A comunicação entre a tarefa e a aplicação é assegurada através de memória partilhada, pois garantindo a consistência de dados, a comunicação entre processos do Linux e as tarefas de tempo real (RTAI) que correm ao nível do kernel torna-se muito simples. Para puder avaliar o desempenho do sistema desenvolvido, foi criada uma tarefa de soft real-time cujos tempos de resposta foram comparados com os da tarefa de hard real-time. As respostas temporais obtidas através do analisador lógico em conjunto com gráficos elaborados a partir destes dados, mostram e comprovam, os benefícios do sistema de aquisição de dados em tempo real via porta paralela, usando uma tarefa de hard real-time.

A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors

Consider the problem of determining a task-toprocessor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct kinds of processors. We propose a polynomialtime approximation scheme (PTAS) for this problem. It offers the following guarantee: for a given task set and a given platform, if there exists a feasible task-to-processor assignment, then given an input parameter, ϵ, our PTAS succeeds, in polynomial time, in finding such a feasible task-to-processor assignment on a platform in which each processor is 1+3ϵ times faster. In the simulations, our PTAS outperforms the state-of-the-art PTAS [1] and also for the vast majority of task sets, it requires significantly smaller processor speedup than (its upper bound of) 1+3ϵ for successfully determining a feasible task-to-processor assignment.

Real-time scheduling with resource sharing on uniform multiprocessors

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a uniform multiprocessor platform where each task may access at most one of |R| shared resources and at most once by each job of that task. The resources have to be accessed in a mutually exclusive manner. We propose an algorithm, GIS-vpr, which offers the guarantee that if a task set is schedulable to meet deadlines by an optimal task assignment scheme that allows a task to migrate only when it accesses or releases a resource, then our algorithm also meets the deadlines with the same restriction on the task migration, if given processors 4 + 6|R| times as fast. The proposed algorithm, by design, limits the number of migrations per job to at most two. To the best of our knowledge, this is the first result for resource sharing on uniform multiprocessors with proven performance guarantee.

Supporting parallelism in server-based multiprocessor systems

Developing an efficient server-based real-time scheduling solution that supports dynamic task-level parallelism is now relevant to even the desktop and embedded domains and no longer only to the high performance computing market niche. This paper proposes a novel approach that combines the constantbandwidth server abstraction with a work-stealing load balancing scheme which, while ensuring isolation among tasks, enables a task to be executed on more than one processor at a given time instant.

Pose Estimation using a C-Arm Fluoroscope

Os métodos clínicos que são realizados com recurso a tecnologias de imagiologia têm registado um aumento de popularidade nas últimas duas décadas. Os procedimentos tradicionais usados em cirurgia têm sido substituídos por métodos minimamente invasivos de forma a conseguir diminuir os custos associados e aperfeiçoar factores relacionados com a produtividade. Procedimentos clínicos modernos como a broncoscopia e a cardiologia são caracterizados por se focarem na minimização de acções invasivas, com os arcos em ‘C’ a adoptarem um papel relevante nesta área. Apesar de o arco em ‘C’ ser uma tecnologia amplamente utilizada no auxílio da navegação em intervenções minimamente invasivas, este falha na qualidade da informação fornecida ao cirurgião. A informação obtida em duas dimensões não é suficiente para proporcionar uma compreensão total da localização tridimensional da região de interesse, revelando-se como uma tarefa essencial o estabelecimento de um método que permita a aquisição de informação tridimensional. O primeiro passo para alcançar este objectivo foi dado ao definir um método que permite a estimativa da posição e orientação de um objecto em relação ao arco em ‘C’. De forma a realizar os testes com o arco em ‘C’, a geometria deste teve que ser inicialmente definida e a calibração do sistema feita. O trabalho desenvolvido e apresentado nesta tese foca-se num método que provou ser suficientemente sustentável e eficiente para se estabelecer como um ponto de partida no caminho para alcançar o objectivo principal: o desenvolvimento de uma técnica que permita o aperfeiçoamento da qualidade da informação adquirida com o arco em ‘C’ durante uma intervenção clínica.