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.

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.

Global and Partitioned Multiprocessor Fixed Priority Scheduling with Deferred Pre-emption

This article introduces schedulability analysis for global fixed priority scheduling with deferred preemption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of global fixed priority pre-emptive scheduling (gFPPS) and global fixed priority non-pre-emptive scheduling (gFPNS). We show how schedulability can be improved using gFPDS via appropriate choice of priority assignment and final non-pre-emptive region lengths, and provide algorithms which optimize schedulability in this way. Via an experimental evaluation we compare the performance of multiprocessor scheduling using global approaches: gFPDS, gFPPS, and gFPNS, and also partitioned approaches employing FPDS, FPPS, and FPNS on each processor.

An automated maneuver control framework for a remotely operated vehicle

OCEANS, 2001. MTS/IEEE Conference and Exhibition (Volume:2 )

A Novel Runtime Monitoring Architecture

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

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.

Towards the Combination of Work-Stealing and Semi-Partitioned Scheduling for Parallel Tasks

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

Towards the Combination of Work-Stealing and Semi-Partitioned Scheduling for Parallel Tasks

Poster presented in Work in Progress Session, 28th GI/ITG International Conference on Architecture of Computing Systems (ARCS 2015). 24 to 26, Mar, 2015. 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.

Overhead-aware schedulability evaluation of semi-partitioned real-time schedulers

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

Uso Sustentável de Vapor

Em 2006, a IEA (Agência Internacional de Energia), publicou alguns estudos de consumos mundiais de energia. Naquela altura, apontava na fabricação de produtos, um consumo mundial de energia elétrica, de origem fóssil de cerca 86,16 EJ/ano (86,16×018 J) e um consumo de energia nos sistemas de vapor de 32,75 EJ/ano. Evidenciou também nesses estudos que o potencial de poupança de energia nos sistemas de vapor era de 3,27 EJ/ano. Ou seja, quase tanto como a energia consumida nos sistemas de vapor da U.E. Não se encontraram números relativamente a Portugal, mas comparativamente com outros Países publicitados com alguma similaridade, o consumo de energia em vapor rondará 0,2 EJ/ano e por conseguinte um potencial de poupança de cerca 0,02 EJ/ano, ou 5,6 × 106 MWh/ano ou uma potência de 646 MW, mais do que a potência de cinco barragens Crestuma/Lever! Trata-se efetivamente de muita energia; interessa por isso perceber o onde e o porquê deste desperdício. De um modo muito modesto, pretende-se com este trabalho dar algum contributo neste sentido. Procurou-se evidenciar as possibilidades reais de os utilizadores de vapor de água na indústria reduzirem os consumos de energia associados à sua produção. Não estão em causa as diferentes formas de energia para a geração de vapor, sejam de origem fóssil ou renovável; interessou neste trabalho estudar o modo de como é manuseado o vapor na sua função de transporte de energia térmica, e de como este poderá ser melhorado na sua eficiência de cedência de calor, idealmente com menor consumo de energia. Com efeito, de que servirá se se optou por substituir o tipo de queima para uma mais sustentável se a jusante se continuarem a verificarem desperdícios, descarga exagerada nas purgas das caldeiras com perda de calor associada, emissões permanentes de vapor para a atmosfera em tanques de condensado, perdas por válvulas nos vedantes, purgadores avariados abertos, pressão de vapor exageradamente alta atendendo às temperaturas necessárias, “layouts” do sistema de distribuição mal desenhados, inexistência de registos de produção e consumos de vapor, etc. A base de organização deste estudo foi o ciclo de vapor: produção, distribuição, consumo e recuperação de condensado. Pareceu importante incluir também o tratamento de água, atendendo às implicações na transferência de calor das superfícies com incrustações. Na produção de vapor, verifica-se que os maiores problemas de perda de energia têm a ver com a falta de controlo, no excesso de ar e purgas das caldeiras em exagero. Na distribuição de vapor aborda-se o dimensionamento das tubagens, necessidade de purgas a v montante das válvulas de controlo, a redução de pressão com válvulas redutoras tradicionais; será de destacar a experiência americana no uso de micro turbinas para a redução de pressão com produção simultânea de eletricidade. Em Portugal não se conhecem instalações com esta opção. Fabricantes da República Checa e Áustria, têm tido sucesso em algumas dezenas de instalações de redução de pressão em diversos países europeus (UK, Alemanha, R. Checa, França, etc.). Para determinação de consumos de vapor, para projeto ou mesmo para estimativa em máquinas existentes, disponibiliza-se uma série de equações para os casos mais comuns. Dá-se especial relevo ao problema que se verifica numa grande percentagem de permutadores de calor, que é a estagnação de condensado - “stalled conditions”. Tenta-se também evidenciar as vantagens da recuperação de vapor de flash (infelizmente de pouca tradição em Portugal), e a aplicação de termocompressores. Finalmente aborda-se o benchmarking e monitorização, quer dos custos de vapor quer dos consumos específicos dos produtos. Esta abordagem é algo ligeira, por manifesta falta de estudos publicados. Como trabalhos práticos, foram efetuados levantamentos a instalações de vapor em diversos sectores de atividades; 1. ISEP - Laboratório de Química. Porto, 2. Prio Energy - Fábrica de Biocombustíveis. Porto de Aveiro. 3. Inapal Plásticos. Componentes de Automóvel. Leça do Balio, 4. Malhas Sonix. Tinturaria Têxtil. Barcelos, 5. Uma instalação de cartão canelado e uma instalação de alimentos derivados de soja. Também se inclui um estudo comparativo de custos de vapor usado nos hospitais: quando produzido por geradores de vapor com queima de combustível e quando é produzido por pequenos geradores elétricos. Os resultados estão resumidos em tabelas e conclui-se que se o potencial de poupança se aproxima do referido no início deste trabalho.

Testing Nelder-Mead Based Repulsion Algorithms for Multiple Roots of Nonlinear Systems via a Two-Level Factorial Design of Experiments

This paper addresses the challenging task of computing multiple roots of a system of nonlinear equations. A repulsion algorithm that invokes the Nelder-Mead (N-M) local search method and uses a penalty-type merit function based on the error function, known as 'erf', is presented. In the N-M algorithm context, different strategies are proposed to enhance the quality of the solutions and improve the overall efficiency. The main goal of this paper is to use a two-level factorial design of experiments to analyze the statistical significance of the observed differences in selected performance criteria produced when testing different strategies in the N-M based repulsion algorithm. The main goal of this paper is to use a two-level factorial design of experiments to analyze the statistical significance of the observed differences in selected performance criteria produced when testing different strategies in the N-M based repulsion algorithm.

Self-optimization for dynamic scheduling in manufacturing systems

Scheduling is a critical function that is present throughout many industries and applications. A great need exists for developing scheduling approaches that can be applied to a number of different scheduling problems with significant impact on performance of business organizations. A challenge is emerging in the design of scheduling support systems for manufacturing environments where dynamic adaptation and optimization become increasingly important. In this paper, we describe a Self-Optimizing Mechanism for Scheduling System through Nature Inspired Optimization Techniques (NIT).

Contexts-management strategy in considering the security in urban computing based on urban design

Urban Computing (UrC) provides users with the situation-proper information by considering context of users, devices, and social and physical environment in urban life. With social network services, UrC makes it possible for people with common interests to organize a virtual-society through exchange of context information among them. In these cases, people and personal devices are vulnerable to fake and misleading context information which is transferred from unauthorized and unauthenticated servers by attackers. So called smart devices which run automatically on some context events are more vulnerable if they are not prepared for attacks. In this paper, we illustrate some UrC service scenarios, and show important context information, possible threats, protection method, and secure context management for people.