Convex optimization framework for intermediate deadline assignment in soft and hard real-time distributed systems

It is generally challenging to determine end-to-end delays of applications for maximizing the aggregate system utility subject to timing constraints. Many practical approaches suggest the use of intermediate deadline of tasks in order to control and upper-bound their end-to-end delays. This paper proposes a unified framework for different time-sensitive, global optimization problems, and solves them in a distributed manner using Lagrangian duality. The framework uses global viewpoints to assign intermediate deadlines, taking resource contention among tasks into consideration. For soft real-time tasks, the proposed framework effectively addresses the deadline assignment problem while maximizing the aggregate quality of service. For hard real-time tasks, we show that existing heuristic solutions to the deadline assignment problem can be incorporated into the proposed framework, enriching their mathematical interpretation.

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.

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.

CPMD-mindful task assignment for NPS-F

The multiprocessor scheduling scheme NPS-F for sporadic tasks has a high utilisation bound and an overall number of preemptions bounded at design time. NPS-F binpacks tasks offline to as many servers as needed. At runtime, the scheduler ensures that each server is mapped to at most one of the m processors, at any instant. When scheduled, servers use EDF to select which of their tasks to run. Yet, unlike the overall number of preemptions, the migrations per se are not tightly bounded. Moreover, we cannot know a priori which task a server will be currently executing at the instant when it migrates. This uncertainty complicates the estimation of cache-related preemption and migration costs (CPMD), potentially resulting in their overestimation. Therefore, to simplify the CPMD estimation, we propose an amended bin-packing scheme for NPS-F allowing us (i) to identify at design time, which task migrates at which instant and (ii) bound a priori the number of migrating tasks, while preserving the utilisation bound of NPS-F.

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.

Practical aspects of slot-based task- splitting dispatching in its schedulability analysis

Consider the problem of scheduling a set of sporadic tasks on a multiprocessor system to meet deadlines using a tasksplitting scheduling algorithm. Task-splitting (also called semipartitioning) scheduling algorithms assign most tasks to just one processor but a few tasks are assigned to two or more processors, and they are dispatched in a way that ensures that a task never executes on two or more processors simultaneously. A certain type of task-splitting algorithms, called slot-based task-splitting, is of particular interest because of its ability to schedule tasks at high processor utilizations. We present a new schedulability analysis for slot-based task-splitting scheduling algorithms that takes the overhead into account and also a new task assignment algorithm.

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.

Aplicação de métodos estocásticos na gestão de custos de construção de condutas de saneamento

O trabalho apresentado centra-se na determinação dos custos de construção de condutas de pequenos e médios diâmetros em Polietileno de Alta Densidade (PEAD) para saneamento básico, tendo como base a metodologia descrita no livro Custos de Construção e Exploração – Volume 9 da série Gestão de Sistemas de Saneamento Básico, de Lencastre et al. (1994). Esta metodologia descrita no livro já referenciado, nos procedimentos de gestão de obra, e para tal foram estimados custos unitários de diversos conjuntos de trabalhos. Conforme Lencastre et al (1994), “esses conjuntos são referentes a movimentos de terras, tubagens, acessórios e respetivos órgãos de manobra, pavimentações e estaleiro, estando englobado na parte do estaleiro trabalhos acessórios correspondentes à obra.” Os custos foram obtidos analisando vários orçamentos de obras de saneamento, resultantes de concursos públicos de empreitadas recentemente realizados. Com vista a tornar a utilização desta metodologia numa ferramenta eficaz, foram organizadas folhas de cálculo que possibilitam obter estimativas realistas dos custos de execução de determinada obra em fases anteriores ao desenvolvimento do projeto, designadamente numa fase de preparação do plano diretor de um sistema ou numa fase de elaboração de estudos de viabilidade económico-financeiros, isto é, mesmo antes de existir qualquer pré-dimensionamento dos elementos do sistema. Outra técnica implementada para avaliar os dados de entrada foi a “Análise Robusta de Dados”, Pestana (1992). Esta metodologia permitiu analisar os dados mais detalhadamente antes de se formularem hipóteses para desenvolverem a análise de risco. A ideia principal é o exame bastante flexível dos dados, frequentemente antes mesmo de os comparar a um modelo probabilístico. Assim, e para um largo conjunto de dados, esta técnica possibilitou analisar a disparidade dos valores encontrados para os diversos trabalhos referenciados anteriormente. Com os dados recolhidos, e após o seu tratamento, passou-se à aplicação de uma metodologia de Análise de Risco, através da Simulação de Monte Carlo. Esta análise de risco é feita com recurso a uma ferramenta informática da Palisade, o @Risk, disponível no Departamento de Engenharia Civil. Esta técnica de análise quantitativa de risco permite traduzir a incerteza dos dados de entrada, representada através de distribuições probabilísticas que o software disponibiliza. Assim, para por em prática esta metodologia, recorreu-se às folhas de cálculo que foram realizadas seguindo a abordagem proposta em Lencastre et al (1994). A elaboração e a análise dessas estimativas poderão conduzir à tomada de decisões sobre a viabilidade da ou das obras a realizar, nomeadamente no que diz respeito aos aspetos económicos, permitindo uma análise de decisão fundamentada quanto à realização dos investimentos.

LSP communication in a digital age: the outcomes of teaching and learning in tertiary education

This paper discusses the changes brought by the communication revolution in teaching and learning in the scope of LSP. Its aim is to provide an insight on how teaching which was bi-dimensional, turned into a multidimensional system, gathering other complementary resources that have transformed, in a incredibly short time, the ways we receive share and store information, for instance as professionals, and keep in touch with our peers. The increasing rise of electronic publications, the incredible boom of social and professional networks, search engines, blogs, list servs, forums, e-mail blasts, Facebook pages, YouTube contents, Tweets and Apps, have twisted the way information is conveyed. Classes ceased to be predictable and have been empowered by digital platforms, innumerous and different data repositories (TILDE, IATE, LINGUEE, and so many other terminological data banks) that have definitely transformed the academic world in general and tertiary education in particular. There is a bulk of information to be digested by students, who are no longer passive but instead responsible and active for their academic outcomes. The question is whether they possess the tools to select only what is accurate and important for a certain subject or assignment, due to that overflow? Due to the reduction of the number of course years in most degrees, after the implementation of Bologna and the shrinking of the curricula contents, have students the possibility of developing critical thinking? Both teaching and learning rely on digital resources to improve the speed of the spreading of knowledge. But have those changes been effective to promote really communication? Furthermore, with the increasing Apps that have already been developed and will continue to appear for learning foreign languages, for translation among others, will the students feel the need of learning them once they have those Apps. These are some the questions we would like to discuss in our paper.

Unified overhead-aware schedulability analysis for slot-based task-splitting

Hard real- time multiprocessor scheduling has seen, in recent years, the flourishing of semi-partitioned scheduling algorithms. This category of scheduling schemes combines elements of partitioned and global scheduling for the purposes of achieving efficient utilization of the system’s processing resources with strong schedulability guarantees and with low dispatching overheads. The sub-class of slot-based “task-splitting” scheduling algorithms, in particular, offers very good trade-offs between schedulability guarantees (in the form of high utilization bounds) and the number of preemptions/migrations involved. However, so far there did not exist unified scheduling theory for such algorithms; each one was formulated in its own accompanying analysis. This article changes this fragmented landscape by formulating a more unified schedulability theory covering the two state-of-the-art slot-based semi-partitioned algorithms, S-EKG and NPS-F (both fixed job-priority based). This new theory is based on exact schedulability tests, thus also overcoming many sources of pessimism in existing analysis. In turn, since schedulability testing guides the task assignment under the schemes in consideration, we also formulate an improved task assignment procedure. As the other main contribution of this article, and as a response to the fact that many unrealistic assumptions, present in the original theory, tend to undermine the theoretical potential of such scheduling schemes, we identified and modelled into the new analysis all overheads incurred by the algorithms in consideration. The outcome is a new overhead-aware schedulability analysis that permits increased efficiency and reliability. The merits of this new theory are evaluated by an extensive set of experiments.

Soluções de melhoria de desempenho acústico na Reabilitação de Edifícios

O presente relatório enquadra-se no âmbito do estágio curricular referente ao Mestrado em Engenharia Civil – Ramo de Construções, do Instituto Superior de Engenharia do Porto. Este relatório tem como objetivo apresentar e descrever de forma sucinta as atividades desenvolvidas na empresa Porto Vivo, SRU – Sociedade de Reabilitação Urbana da Baixa Portuense, S.A., no período compreendido entre 3 de Dezembro de 2012 e 3 de Julho de 2013. O estágio realizou-se por diferentes etapas, sendo numa fase inicial mais relacionada com a pesquisa bibliográfica e enquadramento da temática da reabilitação urbana em Portugal, tendo em seguida estudado e acompanhado o projeto de obras em curso. Esta etapa consistiu, principalmente, no acompanhamento de projetos e obras de reabilitação urbana, no âmbito da atividade da Porto Vivo, SRU, desempenhando inúmeras atividades tais como: contato com técnicos responsáveis pela elaboração dos Documentos Estratégicos, análise dos projetos em curso, acompanhamento de obras de reabilitação urbana, apoio à elaboração de relatórios de acompanhamento das obras, participado em reuniões de obra com empreiteiros e projetistas, elaborado o registo fotográfico de obras particulares e executado o levantamento do edificado. A primeira parte deste relatório enquadra o tema da Reabilitação Urbana, no seu conceito mais lato descrevendo os principais incentivos e programas de apoio inerentes. Refere-se, ainda, à descrição da empresa Porto Vivo, SRU e às atividades aí desenvolvidas. Numa segunda parte do relatório, é descrito o estudo de caso relativo ao desempenho acústico de soluções construtivas no âmbito da reabilitação do património edificado. Por último, uma reflexão final de todo o período de estágio e apreciação global das atividades desenvolvidas e da sua importância na formação pessoal e profissional.

Manobras de condução assistida para veículos submarinos subactuados

A intervenção humana no manuseamento de veículos submarinos operados remotamente (ROVs) é um requisito necessário para garantir o sucesso da missão e a integridade do equipamento. Contudo, a sua teleoperação não é fácil, pelo que a condução assistida destes veículos torna-se relevante. Esta dissertação propõe uma solução para este problema para ROVs de 3DOF (surge, heave e yaw). São propostas duas abordagens distintas – numa primeira propõe-se um sistema de controlo Image Based Visual Servoing (IBVS) tendo em vista a utilização exclusiva de uma câmara (sensor existente neste tipo de sistemas) por forma a melhorar significativamente a teleoperação de um pequeno ROV; na segunda, propõe-se um sistema de controlo cinemático para o plano horizontal do veículo e um algoritmo de uma manobra capaz de dotar o ROV de movimento lateral através de uma trajectória dente-de-serra. Demonstrou-se em cenários de operação real que o sistema proposto na primeira abordagem permite ao operador de um ROV com 3DOF executar tarefas de alguma complexidade (estabilização) apenas através de comandos de alto nível, melhorando assim drasticamente a teleoperação e qualidade de inspecção do veículo em questão. Foi também desenvolvido um simulador do ROV em MATLAB para validação e avaliação das manobras, onde o sistema proposto na segunda abordagem foi validado com sucesso.

Ampliação e reabilitação de edifícios

O presente relatório encontra-se no âmbito do estágio curricular referente ao Mestrado de Engenharia Civil do Instituto Superior de Engenharia do Porto. Este decorreu entre janeiro e julho de 2013 tendo como objetivo principal a realização de um projeto de Reabilitação e Ampliação de uma Escola Primária localizada na freguesia Seixo de Manhoses, no concelho Vila Flor, destinada a um Centro integrado de valorização de recursos. A preferência pela realização de um estágio curricular deveu-se ao facto de ser possível a aplicação direta dos conhecimentos que foram sendo adquiridos durante o curso e pela possibilidade de, ao longo do estágio, serem apreendidos mais conhecimentos que pudessem vir a ser úteis aquando da entrada do estagiário no mercado de trabalho. O estágio decorreu na Associação de Municípios da Terra Quente Transmontana, em Mirandela, e durante o período do mesmo, o estagiário foi participando de forma indirecta em outros projetos que vinham a ser desenvolvidos por esta entidade. Antes do inicio do referido projeto, foram efetuadas visitas ao local de implantação do edifício, de modo a serem esclarecidos alguns aspetos importantes na realização do projecto por parte do estagiário e com vista a tentar encontrar a solução que mais se adequava ao caso em estudo. Durante o estágio, com o intuito de ver os seus objetivos serem cumpridos, o estagiário fosse inserindo na equipa de projeto e nas várias atividades que foram sendo desenvolvidas (acompanhamento de outros projetos, visita a obras inserido na equipa de fiscalização, frequência de ações de formação).

Vision-Based Assisted Teleoperation for Inspection Tasks with a Small ROV

It is well-known that ROVs require human intervention to guarantee the success of their assignment, as well as the equipment safety. However, as its teleoperation is quite complex to perform, there is a need for assisted teleoperation. This study aims to take on this challenge by developing vision-based assisted teleoperation maneuvers, since a standard camera is present in any ROV. The proposed approach is a visual servoing solution, that allows the user to select between several standard image processing methods and is applied to a 3-DOF ROV. The most interesting characteristic of the presented system is the exclusive use of the camera data to improve the teleoperation of an underactuated ROV. It is demonstrated through the comparison and evaluation of standard implementations of different vision methods and the execution of simple maneuvers to acquire experimental results, that the teleoperation of a small ROV can be drastically improved without the need to install additional sensors.

Sectorization: measures and an electromagnetism based approach

Sectorization means dividing a set of basic units into sectors or parts, a procedure that occurs in several contexts, such as political, health and school districting, social networks and sales territory or airspace assignment, to achieve some goal or to facilitate an activity. This presentation will focus on three main issues: Measures, a new approach to sectorization problems and an application in waste collection. When designing or comparing sectors different characteristics are usually taken into account. Some are commonly used, and they are related to the concepts of contiguity, equilibrium and compactness. These fundamental characteristics will be addressed, by defining new generic measures and by proposing a new measure, desirability, connected with the idea of preference. A new approach to sectorization inspired in Coulomb’s Law, which establishes a relation of force between electrically charged points, will be proposed. A charged point represents a small region with specific characteristics/values creating relations of attraction/repulsion with the others (two by two), proportional to the charges and inversely proportional to their distance. Finally, a real case about sectorization and vehicle routing in solid waste collection will be mentioned.