Task Assignment Algorithms for Heterogeneous Multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising a constant number (denoted by t) of distinct types of processors—such a platform is referred to as a t-type platform. We present two algorithms, LPGIM and LPGNM, each providing the following guarantee. For a given t-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet their deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then: (i) LPGIM succeeds in finding such an assignment where the same restriction on task migration applies (intra-migrative) but given a platform in which only one processor of each type is 1 + α × t-1/t times faster and (ii) LPGNM succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which every processor is 1 + α times faster. The parameter α is a property of the task set; it is the maximum of all the task utilizations that are no greater than one. To the best of our knowledge, for t-type heterogeneous multiprocessors: (i) for the problem of intra-migrative task assignment, no previous algorithm exists with a proven bound and hence our algorithm, LPGIM, is the first of its kind and (ii) for the problem of non-migrative task assignment, our algorithm, LPGNM, has superior performance compared to state-of-the-art.

Race-to-halt energy saving strategies

Energy consumption is one of the major issues for modern embedded systems. Early, power saving approaches mainly focused on dynamic power dissipation, while neglecting the static (leakage) energy consumption. However, technology improvements resulted in a case where static power dissipation increasingly dominates. Addressing this issue, hardware vendors have equipped modern processors with several sleep states. We propose a set of leakage-aware energy management approaches that reduce the energy consumption of embedded real-time systems while respecting the real-time constraints. Our algorithms are based on the race-to-halt strategy that tends to run the system at top speed with an aim to create long idle intervals, which are used to deploy a sleep state. The effectiveness of our algorithms is illustrated with an extensive set of simulations that show an improvement of up to 8% reduction in energy consumption over existing work at high utilization. The complexity of our algorithms is smaller when compared to state-of-the-art algorithms. We also eliminate assumptions made in the related work that restrict the practical application of the respective algorithms. Moreover, a novel study about the relation between the use of sleep intervals and the number of pre-emptions is also presented utilizing a large set of simulation results, where our algorithms reduce the experienced number of pre-emptions in all cases. Our results show that sleep states in general can save up to 30% of the overall number of pre-emptions when compared to the sleep-agnostic earliest-deadline-first algorithm.

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.

NoC contention analysis using a branch-and-prune algorithm

“Many-core” systems based on a Network-on-Chip (NoC) architecture offer various opportunities in terms of performance and computing capabilities, but at the same time they pose many challenges for the deployment of real-time systems, which must fulfill specific timing requirements at runtime. It is therefore essential to identify, at design time, the parameters that have an impact on the execution time of the tasks deployed on these systems and the upper bounds on the other key parameters. The focus of this work is to determine an upper bound on the traversal time of a packet when it is transmitted over the NoC infrastructure. Towards this aim, we first identify and explore some limitations in the existing recursive-calculus-based approaches to compute the Worst-Case Traversal Time (WCTT) of a packet. Then, we extend the existing model by integrating the characteristics of the tasks that generate the packets. For this extended model, we propose an algorithm called “Branch and Prune” (BP). Our proposed method provides tighter and safe estimates than the existing recursive-calculus-based approaches. Finally, we introduce a more general approach, namely “Branch, Prune and Collapse” (BPC) which offers a configurable parameter that provides a flexible trade-off between the computational complexity and the tightness of the computed estimate. The recursive-calculus methods and BP present two special cases of BPC when a trade-off parameter is 1 or ∞, respectively. Through simulations, we analyze this trade-off, reason about the implications of certain choices, and also provide some case studies to observe the impact of task parameters on the WCTT estimates.

P53 and Cancer-Associated Sialylated Glycans Are Surrogate Markers of Cancerization of the Bladder Associated with Schistosoma haematobium Infection

BACKGROUND: Bladder cancer is a significant health problem in rural areas of Africa and the Middle East where Schistosoma haematobium is prevalent, supporting an association between malignant transformation and infection by this blood fluke. Nevertheless, the molecular mechanisms linking these events are poorly understood. Bladder cancers in infected populations are generally diagnosed at a late stage since there is a lack of non-invasive diagnostic tools, hence enforcing the need for early carcinogenesis markers. METHODOLOGY/PRINCIPAL FINDINGS: Forty-three formalin-fixed paraffin-embedded bladder biopsies of S. haematobium-infected patients, consisting of bladder tumours, tumour adjacent mucosa and pre-malignant/malignant urothelial lesions, were screened for bladder cancer biomarkers. These included the oncoprotein p53, the tumour proliferation rate (Ki-67>17%), cell-surface cancer-associated glycan sialyl-Tn (sTn) and sialyl-Lewisa/x (sLea/sLex), involved in immune escape and metastasis. Bladder tumours of non-S. haematobium etiology and normal urothelium were used as controls. S. haematobium-associated benign/pre-malignant lesions present alterations in p53 and sLex that were also found in bladder tumors. Similar results were observed in non-S. haematobium associated tumours, irrespectively of their histological nature, denoting some common molecular pathways. In addition, most benign/pre-malignant lesions also expressed sLea. However, proliferative phenotypes were more prevalent in lesions adjacent to bladder tumors while sLea was characteristic of sole benign/pre-malignant lesions, suggesting it may be a biomarker of early carcionogenesis associated with the parasite. A correlation was observed between the frequency of the biomarkers in the tumor and adjacent mucosa, with the exception of Ki-67. Most S. haematobium eggs embedded in the urothelium were also positive for sLea and sLex. Reinforcing the pathologic nature of the studied biomarkers, none was observed in the healthy urothelium. CONCLUSION/SIGNIFICANCE: This preliminary study suggests that p53 and sialylated glycans are surrogate biomarkers of bladder cancerization associated with S. haematobium, highlighting a missing link between infection and cancer development. Eggs of S. haematobium express sLea and sLex antigens in mimicry of human leukocytes glycosylation, which may play a role in the colonization and disease dissemination. These observations may help the early identification of infected patients at a higher risk of developing bladder cancer and guide the future development of non-invasive diagnostic tests.

A fractional perspective to financial indices

The application of mathematical methods and computer algorithms in the analysis of economic and financial data series aims to give empirical descriptions of the hidden relations between many complex or unknown variables and systems. This strategy overcomes the requirement for building models based on a set of ‘fundamental laws’, which is the paradigm for studying phenomena usual in physics and engineering. In spite of this shortcut, the fact is that financial series demonstrate to be hard to tackle, involving complex memory effects and a apparently chaotic behaviour. Several measures for describing these objects were adopted by market agents, but, due to their simplicity, they are not capable to cope with the diversity and complexity embedded in the data. Therefore, it is important to propose new measures that, on one hand, are highly interpretable by standard personal but, on the other hand, are capable of capturing a significant part of the dynamical effects.

Creating and optimizing client-server applications on mobile devices

Mobile devices are embedded systems with very limited capacities that need to be considered when developing a client-server application, mainly due to technical, ergonomic and economic implications to the mobile user. With the increasing popularity of mobile computing, many developers have faced problems due to low performance of devices. In this paper, we discuss how to optimize and create client-server applications for in wireless/mobile environments, presenting techniques to improve overall performance.

Reabilitação sustentável em edifícios habitacionais com valor histórico

Mestrado em Engenharia Civil – Ramo Construções

Development of a system to monitor surfer’s balance and plantar pressure and surfboard’s movement

O uso da tecnologia tem crescido nas últimas décadas nas mais diversas áreas, seja na indústria ou no dia-a-dia, e é cada vez mais evidente os benefícios que traz. No desporto não é diferente. Cada dia surgem novos desenvolvimentos objetivando a melhoria do desempenho dos praticantes de atividades físicas, possibilitando atingir resultados nunca antes pensados. Além disto, a utilização da tecnologia no desporto permite a obtenção de dados biomecânicos que podem ser utilizados tanto no treinamento quando na melhoria da qualidade de vida dos atletas auxiliando na prevenção de lesões, por exemplo. Deste modo, o presente projeto se aplica na área do desporto, nomeadamente, na modalidade do surfe, onde a ausência de trabalhos científicos ainda é elevada, aliando a tecnologia eletrônica ao desporto para quantificar informações até então desconhecidas. Três fatores básicos de desempenho foram levantados, sendo eles: equilíbrio, posicionamento dos pés e movimentação da prancha de surfe. Estes fatores levaram ao desenvolvimento de um sistema capaz de medi-los dinamicamente através da medição das forças plantares e da rotação da prancha de surfe. Além da medição dos fatores, o sistema é capaz de armazenar os dados adquiridos localmente através de um cartão de memória, para posterior análise; e também enviá-los através de uma comunicação sem fio, permitindo a visualização do centro de pressões plantares; dos ângulos de rotação da prancha de surfe; e da ativação dos sensores; em tempo real. O dispositivo consiste em um sistema eletrônico embarcado composto por um microcontrolador ATMEGA1280; um circuito de aquisição e condicionamento de sinal analógico; uma central inercial; um módulo de comunicação sem fio RN131; e um conjunto de sensores de força Flexiforce. O firmware embarcado foi desenvolvido em linguagem C. O software Matlab foi utilizado para receção de dados e visualização em tempo real. Os testes realizados demostraram que o funcionamento do sistema atende aos requisitos propostos, fornecendo informação acerca do equilíbrio, através do centro de pressões; do posicionamento dos pés, através da distribuição das pressões plantares; e do movimento da prancha nos eixos pitch e roll, através da central inercial. O erro médio de medição de força verificado foi de -0.0012 ± 0.0064 N, enquanto a mínima distância alcançada na transmissão sem fios foi de 100 m. A potência medida do sistema foi de 330 mW.

Projecto e implementação de osciloscópio digital baseado na norma IEEE1451.0

Os osciloscópios digitais são utilizados em diversas áreas do conhecimento, assumindo-se no âmbito da engenharia electrónica, como instrumentos indispensáveis. Graças ao advento das Field Programmable Gate Arrays (FPGAs), os instrumentos de medição reconfiguráveis, dadas as suas vantagens, i.e., altos desempenhos, baixos custos e elevada flexibilidade, são cada vez mais uma alternativa aos instrumentos tradicionalmente usados nos laboratórios. Tendo como objectivo a normalização no acesso e no controlo deste tipo de instrumentos, esta tese descreve o projecto e implementação de um osciloscópio digital reconfigurável baseado na norma IEEE 1451.0. Definido de acordo com uma arquitectura baseada nesta norma, as características do osciloscópio são descritas numa estrutura de dados denominada Transducer Electronic Data Sheet (TEDS), e o seu controlo é efectuado utilizando um conjunto de comandos normalizados. O osciloscópio implementa um conjunto de características e funcionalidades básicas, todas verificadas experimentalmente. Destas, destaca-se uma largura de banda de 575kHz, um intervalo de medição de 0.4V a 2.9V, a possibilidade de se definir um conjunto de escalas horizontais, o nível e declive de sincronismo e o modo de acoplamento com o circuito sob análise. Arquitecturalmente, o osciloscópio é constituído por um módulo especificado com a linguagem de descrição de hardware (HDL, Hardware Description Language) Verilog e por uma interface desenvolvida na linguagem de programação Java®. O módulo é embutido numa FPGA, definindo todo o processamento do osciloscópio. A interface permite o seu controlo e a representação do sinal medido. Durante o projecto foi utilizado um conversor Analógico/Digital (A/D) com uma frequência máxima de amostragem de 1.5MHz e 14 bits de resolução que, devido às suas limitações, obrigaram à implementação de um sistema de interpolação multi-estágio com filtros digitais.

Resistência ao fogo de alvenarias sem função estrutural

Um incêndio é algo difícil de prever, assim como a sua consequência nos elementos de construção. Dessa forma, ao longo das últimas décadas, os elementos de construção têm sido alvo de diversos estudos a fim de avaliar os seus comportamentos quando solicitados em situação de incêndio. O International Building Code (IBC) descreve um método de cálculo analítico para a determinação da resistência ao fogo dos elementos da construção de acordo com os procedimentos de teste estabelecidos na ASTM E119 (Standard Test Methods for Fire Tests of Building Construction and Materials). Nesta dissertação foi feita uma análise desse método, que se mostrou inadequado para estimar a resistência ao fogo das alvenarias, sem função estrutural, de blocos cerâmicos e blocos de betão, uma vez que despreza qualquer efeito do ar no interior das mesmas. No seguimento desta análise, é apresentado um desenvolvimento do método descrito tendo em conta o efeito do ar. Depois de uma análise aos vários tipos de blocos cerâmicos e de betão com diferentes dimensões e geometrias foi possível obter uma relação entre a espessura equivalente de ar existente num bloco e a sua respectiva resistência ao fogo, de modo a serem obtidos os valores descritos na normalização existente. O efeito do ar mostrou ter uma maior influência na resistência ao fogo nas alvenarias constituídas por blocos cerâmicos de furação vertical, já que a sua geometria caracterizada por um elevado número de pequenos alvéolos contribui para o aumento do isolamento térmico, e consequentemente da sua resistência ao fogo. Nas alvenarias rebocadas os valores da resistência ao fogo aumentam cerca de 50%, quando revestidos com argamassa de cimento, e 70% quando revestidos com gesso, logo, o emprego de revestimentos representam uma boa alternativa para aumentar a resistência ao fogo.

Estudo de Caso: Processos de orçamentação de obras

O relatório inserido na Unidade Curricular de DIPRE do Mestrado em Engenharia Civil do ISEP e desenvolvido no âmbito do estágio curricular realizado na HESPOR – Construções Lda, tem como objetivo caraterizar o mercado nacional da construção civil, os procedimentos da orçamentação, analisando os seus processos no âmbito dos concursos públicos em Portugal. Deste modo, o relatório tem por base a importância da orçamentação na construção civil e a caraterização do mercado da construção na atual situação financeira que o País se depara. Em seguida foi realizado um estudo da arte sobre os temas de custos e orçamentos, e ainda uma abordagem aos custos associados à construção civil. Depois de analisada toda a metodologia inerente à orçamentação, são caraterizados os processos das empresas do grupo para o ato de orçamentação. Foi abordado um estudo de caso para demonstrar como é elaborado o ato de orçamentação e foi realizada uma análise em função das propostas apresentadas com o intuito de afinar o processo de orçamentação de forma a tornar a proposta competitiva mas salvaguardando sempre a viabilidade, que é a estratégia adotada pela empresa.

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.

Exigências funcionais em pavimentos de madeira

Durante séculos a madeira foi dos materiais mais privilegiados e usados na construção. Ainda hoje, existem construções antigas em madeira em bom estado de conservação e que, desempenham as suas funções adequadamente. Com o aparecimento do betão e do aço, os projetistas deixaram de usar este tipo de estruturas. Isto provocou um desinteresse na indústria da madeira, adiando a criação de regulamentos e normas relativamente às exigências funcionais deste tipo de estruturas. Com a necessidade da reabilitação do património edificado, verifica-se uma inversão desta tendência, devido às edificações no centro histórico serem constituídas por estruturas de madeira, essencialmente os pavimentos e coberturas. Na maioria das vezes estas estruturas apresentam um elevado nível de degradação e a solução mais rentável é demolir. Os pavimentos de madeira são então substituídos por lajes aligeiradas ou de betão armado provocando alterações estruturais inadequadas nas fachadas a manter. Pretende-se com esta dissertação mostrar as potencialidades dos pavimentos de madeira e assim incentivar ao seu uso, principalmente nas áreas a reabilitar. São analisados todos os regulamentos e normas aplicáveis às exigências estruturais, térmicas, acústicas e contra incêndio dos pavimentos de madeira. A análise da normalização aplicável vai ser sintetizada, ou seja, só vão ser referidos os aspetos a ter em conta para a verificação das exigências funcionais em pavimentos de madeira. A aplicação dos conceitos e das verificações necessárias são aplicadas a um pavimento de madeira a ser construído na parcela C4 do Quarteirão das Cardosas. Os resultados obtidos neste caso de estudo são encorajadores, e abrem uma perspetiva das potencialidades que este sistema construtivo apresenta.

Inovação e estratégia industrial: estudo de caso: aplicação dos 5S

As empresas necessitam de ver os seus desempenhos e resultados constantemente melhorados ao nível da qualidade e eficiência. Quando deparamos com a problemática industrial, parece não haver dúvidas de que a metodologia aplicada, a inovação e o capital de investimento a médio e a longo prazo, são decisivos para o crescimento de uma empresa. Das várias estratégias e metodologias que são aplicadas nas empresas, a filosofia Lean surge como uma poderosa metodologia de melhoria de processos. O objetivo deste trabalho assenta na seleção e aplicação de uma das ferramentas da metodologia Lean numa unidade industrial. Foi selecionada a ferramenta 5S para implementação numa empresa de transformação e comercialização de vidro plano. Com a implementação da ferramenta 5S atuou-se sobre os desperdícios, identificando e implementando diversas melhorias no processo. Face às evidentes melhorias observadas, pretende-se alargar o processo a todas as áreas da empresa com vista à melhoria contínua.