Provably good multiprocessor scheduling with resource sharing

We present a 12(1 + 3R/(4m)) competitive algorithm for scheduling implicit-deadline sporadic tasks on a platform comprising m processors, where a task may request one of R shared resources.

Provably good scheduling of sporadic tasks with resource sharing on a two-type heterogeneous multiprocessor platform

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a two-type heterogeneous multiprocessor platform where a task may request at most one of |R| shared resources. There are m1 processors of type-1 and m2 processors of type-2. Tasks may migrate only when requesting or releasing resources. We present a new algorithm, FF-3C-vpr, which offers a guarantee that if a task set is schedulable to meet deadlines by an optimal task assignment scheme that only allows tasks to migrate when requesting or releasing a resource, then FF-3Cvpr also meets deadlines if given processors 4+6*ceil(|R|/min(m1,m2)) times as fast. As far as we know, it is the first result for resource sharing on heterogeneous platforms with provable performance.

Resource sharing in global fixed-priority preemptive multiprocessor scheduling

In this paper we consider global fixed-priority preemptive multiprocessor scheduling of constrained-deadline sporadic tasks that share resources in a non-nested manner. We develop a novel resource-sharing protocol and a corresponding schedulability test for this system. We also develop the first schedulability analysis of priority inheritance protocol for the aforementioned system. Finally, we show that these protocols are efficient (based on the developed schedulability tests) for a class of priority-assignments called reasonable priority-assignments.

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.

Real-time scheduling with resource sharing on heterogeneous multiprocessors

Consider the problem of scheduling a task set τ of implicit-deadline sporadic tasks to meet all deadlines on a t-type heterogeneous multiprocessor platform where tasks may access multiple shared resources. The multiprocessor platform has m k processors of type-k, where k∈{1,2,…,t}. The execution time of a task depends on the type of processor on which it executes. The set of shared resources is denoted by R. For each task τ i , there is a resource set R i ⊆R such that for each job of τ i , during one phase of its execution, the job requests to hold the resource set R i exclusively with the interpretation that (i) the job makes a single request to hold all the resources in the resource set R i and (ii) at all times, when a job of τ i holds R i , no other job holds any resource in R i . Each job of task τ i may request the resource set R i at most once during its execution. A job is allowed to migrate when it requests a resource set and when it releases the resource set but a job is not allowed to migrate at other times. Our goal is to design a scheduling algorithm for this problem and prove its performance. We propose an algorithm, LP-EE-vpr, which offers the guarantee that if an implicit-deadline sporadic task set is schedulable on a t-type heterogeneous multiprocessor platform by an optimal scheduling algorithm that allows a job to migrate only when it requests or releases a resource set, then our algorithm also meets the deadlines with the same restriction on job migration, if given processors 4×(1+MAXP×⌈|P|×MAXPmin{m1,m2,…,mt}⌉) times as fast. (Here MAXP and |P| are computed based on the resource sets that tasks request.) For the special case that each task requests at most one resource, the bound of LP-EE-vpr collapses to 4×(1+⌈|R|min{m1,m2,…,mt}⌉). To the best of our knowledge, LP-EE-vpr is the first algorithm with proven performance guarantee for real-time scheduling of sporadic tasks with resource sharing on t-type heterogeneous multiprocessors.

A framework for programming sensor networks with scheduling and resource-sharing optimizations

Several projects in the recent past have aimed at promoting Wireless Sensor Networks as an infrastructure technology, where several independent users can submit applications that execute concurrently across the network. Concurrent multiple applications cause significant energy-usage overhead on sensor nodes, that cannot be eliminated by traditional schemes optimized for single-application scenarios. In this paper, we outline two main optimization techniques for reducing power consumption across applications. First, we describe a compiler based approach that identifies redundant sensing requests across applications and eliminates those. Second, we cluster the radio transmissions together by concatenating packets from independent applications based on Rate-Harmonized Scheduling.

Intra-type migrative scheduling of implicit-deadline sporadic tasks on two- type heterogeneous multiprocessor

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a two-type heterogeneous multiprocessor platform. Each processor is either of type-1 or type-2 with each task having different execution time on each processor type. Jobs can migrate between processors of same type (referred to as intra-type migration) but cannot migrate between processors of different types. We present a new scheduling algorithm namely, LP-Relax(THR) which offers a guarantee that if a task set can be scheduled to meet deadlines by an optimal task assignment scheme that allows intra-type migration then LP-Relax(THR) meets deadlines as well with intra-type migration if given processors 1/THR as fast (referred to as speed competitive ratio) where THR <= 2/3.

A pseudo-medium-wide 8-competitive interface for two-level compositional real-time scheduling of constrained- deadline sporadic tasks on a uniprocessor

Compositional real-time scheduling clearly requires that ”normal” real-time scheduling challenges are addressed but challenges intrinsic to compositionality must be addressed as well, in particular: (i) how should interfaces be described? and (ii) how should numerical values be assigned to parameters constituting the interfaces? The real-time systems community has traditionally used narrow interfaces for describing a component (for example, a utilization/bandwidthlike metric and the distribution of this bandwidth in time). In this paper, we introduce the concept of competitive ratio of an interface and show that typical narrow interfaces cause poor performance for scheduling constrained-deadline sporadic tasks (competitive ratio is infinite). Therefore, we explore more expressive interfaces; in particular a class called medium-wide interfaces. For this class, we propose an interface type and show how the parameters of the interface should be selected. We also prove that this interface is 8-competitive.

Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors

A preliminary version of this paper appeared in Proceedings of the 31st IEEE Real-Time Systems Symposium, 2010, pp. 239–248.

Scalable and Efficient Configuration of TimeDivision Multiplexed Resources

Consumer-electronics systems are becoming increasingly complex as the number of integrated applications is growing. Some of these applications have real-time requirements, while other non-real-time applications only require good average performance. For cost-efficient design, contemporary platforms feature an increasing number of cores that share resources, such as memories and interconnects. However, resource sharing causes contention that must be resolved by a resource arbiter, such as Time-Division Multiplexing. A key challenge is to configure this arbiter to satisfy the bandwidth and latency requirements of the real-time applications, while maximizing the slack capacity to improve performance of their non-real-time counterparts. As this configuration problem is NP-hard, a sophisticated automated configuration method is required to avoid negatively impacting design time. The main contributions of this article are: 1) An optimal approach that takes an existing integer linear programming (ILP) model addressing the problem and wraps it in a branch-and-price framework to improve scalability. 2) A faster heuristic algorithm that typically provides near-optimal solutions. 3) An experimental evaluation that quantitatively compares the branch-and-price approach to the previously formulated ILP model and the proposed heuristic. 4) A case study of an HD video and graphics processing system that demonstrates the practical applicability of the approach.

Partilha de Pontos de Interesse, Vídeos e Experiências Sensoriais Baseada no Contexto do Utilizador

A evolução tecnológica das últimas décadas na área das Tecnologias da Informação e Comunicação (TIC) contribuiu para a proliferação de fontes de informação e de sistemas de partilha de recursos. As diversas redes sociais são um exemplo paradigmático de sistemas de partilha tanto de informação como de recursos (e.g. audiovisuais). Essa abundância crescente de recursos e fontes aumenta a importância de sistemas capazes de recomendar em tempo útil recursos personalizados, tendo por base o perfil e o contexto do utilizador. O objetivo deste projeto é partilhar e recomendar locais, artigos e vídeos em função do contexto do utilizador assim como proporcionar uma experiência mais rica de reprodução dos vídeos partilhados, simulando as condições de gravação dos vídeos. Este sistema teve como inspiração dois projetos anteriormente desenvolvidos de partilha e recomendação de locais, artigos e vídeos turísticos em função da localização do utilizador. O sistema desenvolvido consiste numa aplicação distribuída composta por um módulo cliente Android, que inclui a interface com o utilizador e o consumo direto de serviços externos de suporte, e um módulo servidor que controla o acesso à base de dados central e inclui o serviço de recomendação baseado no contexto do utilizador. A comunicação entre os módulos cliente e servidor utiliza um protocolo do nível de aplicação dedicado. As recomendações geradas pelo sistema têm por base o perfil de utilizador, informação contextual (posição do utilizador, data e hora atual e velocidade atual do utilizador) e podem ser geradas a pedido do utilizador ou automaticamente, caso sejam encontrados pontos de interesse de grande relevância para o utilizador. Os pontos de interesse recomendados são apresentados com recurso ao Google Maps, incluindo o período de funcionamento, artigos complementares e a reprodução imersiva dos vídeos relacionados. Essa imersão tem em consideração as condições meteorológicas, temporais e espaciais aquando da gravação do vídeo.

Relatório de estágio de qualificação profissional

Relatório EPE - Relatório de estágio em Educação Pré-Escolar:O relatório de estágio para a qualificação profissional foi realizado no âmbito da unidade curricular de Prática Pedagógica Supervisionada na Educação Pré-Escolar, sendo esta parte integrante do Mestrado em Educação Pré-Escolar e Ensino do 1º ciclo do Ensino Básico. Todo o trabalho desenvolvido no presente relatório teve como objetivo dar a conhecer, de forma crítica, reflexiva e sustentada, as experiências vividas pela formanda com o grupo de crianças que acompanhou, num total de 210 horas de estágio, iniciado em fevereiro e terminado em junho do presente ano. A prática pedagógica de um educador de infância influencia diretamente o desenvolvimento das crianças, bem como o desenvolvimento do próprio docente, contituindo para o desenvolvimento de competências fundamentais para a sua prática futura. Com vista a uma planificação focada nas necessidades e interesses evidenciados pelo grupo de crianças, o educador deve observar, planear, agir, avaliar, comunicar e articular, levando a cabo, paralelamente, a investigaçãoação como forma de refletir sobre a sua prática e sobre os efeitos da mesma, em si e nas crianças. Tendo por base estes pressupostos, foram observadas necessidades de desenvolvimento, interesses e resultados de aprendizagem, que permitiram a planificação de atividades a realizar, por forma a atingir os objetivos traçados para o desenvolvimento de capacidades nas crianças. Para isso, recorreu-se a estratégias inovadoras e diversificadas, suportadas pelos modelos curriculares High/Scope e Reggio Emilia, e também pela Metodologia de Trabalho de Projeto. O trabalho desenvolvido em torno da unidade curricular visa competências como a mobilização de saberes, a adoção de estratégias diferenciadas, a tomada de decisões conscientes e adequadas, o desenvolvimento de projetos de investigação e o desenvolvimento e consolidação de competências socioprofissionais e pessoais. Neste sentido, contribuiu para o desenvolvimento pessoal e para o crescimento profissional da mestranda, através das intervenções realizadas com o grupo de crianças. As diferentes etapas do processo educativo acompanharam afincadamente esta etapa, na medida em que contribuiram para um maior conhecimento da formanda quanto à ação e à planificação. Importa salientar que as atividades desenvolvidas ao longo deste período visaram o desenvolvimento de todas as áreas e domínios de conteúdo, nas crianças, com mais ênfase na área da formação pessoal e social e na área do conhecimento do mundo.

The generalized multiprocessor periodic resource interface model for hierarchical multiprocessor scheduling

Composition is a practice of key importance in software engineering. When real-time applications are composed it is necessary that their timing properties (such as meeting the deadlines) are guaranteed. The composition is performed by establishing an interface between the application and the physical platform. Such an interface does typically contain information about the amount of computing capacity needed by the application. In multiprocessor platforms, the interface should also present information about the degree of parallelism. Recently there have been quite a few interface proposals. However, they are either too complex to be handled or too pessimistic.In this paper we propose the Generalized Multiprocessor Periodic Resource model (GMPR) that is strictly superior to the MPR model without requiring a too detailed description. We describe a method to generate the interface from the application specification. All these methods have been implemented in Matlab routines that are publicly available.

Energy resources scheduling in competitive environment

The increasing use of distributed generation units based on renewable energy sources, the consideration of demand-side management as a distributed resource, and the operation in the scope of competitive electricity markets have caused important changes in the way that power systems are operated. The new distributed resources require an entity (player) capable to make them able to participate in electricity markets. This entity has been known as Virtual Power Player (VPP). VPPs need to consider all the business opportunities available to their resources, considering all the relevant players, the market and/or other VPPs to accomplish their goals. This paper presents a methodology that considers all these opportunities to minimize the operation costs of a VPP. The method is applied to a distribution network managed by four independent VPPs with intensive use of distributed resources.

A capacity sharing and stealing strategy for open real-time systems

This paper focuses on the scheduling of tasks with hard and soft real-time constraints in open and dynamic real-time systems. It starts by presenting a capacity sharing and stealing (CSS) strategy that supports the coexistence of guaranteed and non-guaranteed bandwidth servers to efficiently handle soft-tasks’ overloads by making additional capacity available from two sources: (i) reclaiming unused reserved capacity when jobs complete in less than their budgeted execution time and (ii) stealing reserved capacity from inactive non-isolated servers used to schedule best-effort jobs. CSS is then combined with the concept of bandwidth inheritance to efficiently exchange reserved bandwidth among sets of inter-dependent tasks which share resources and exhibit precedence constraints, assuming no previous information on critical sections and computation times is available. The proposed Capacity Exchange Protocol (CXP) has a better performance and a lower overhead when compared against other available solutions and introduces a novel approach to integrate precedence constraints among tasks of open real-time systems.