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.

On the numerical computation of the Mittag-Leffler function

Recently simple limiting functions establishing upper and lower bounds on the Mittag-Leffler function were found. This paper follows those expressions to design an efficient algorithm for the approximate calculation of expressions usual in fractional-order control systems. The numerical experiments demonstrate the superior efficiency of the proposed method.

Geo-localization System for People with Cognitive Disabilities

Technology is present in almost every simple aspect of the people’s daily life. As an instance, let us refer to the smartphone. This device is usually equipped with a GPS modulewhich may be used as an orientation system, if it carries the right functionalities. The problem is that these applications may be complex to operate and may not be within the bounds of everybody. Therefore, the main goal here is to develop an orientation system that may help people with cognitive disabilities in their day-to-day journeys, when the caregivers are absent. On the other hand, to keep paid helpers aware of the current location of the disable people, it will be also considered a localization system. Knowing their current locations, caregiversmay engage in others activities without neglecting their prime work, and, at the same time, turning people with cognitive disabilities more independent.

Estudo do óxido de cálcio como catalisador para a transesterificação de óleos alimentares usados

O instável mas tendencialmente crescente preço dos combustíveis associado a preocupações ambientais cada vez mais enraizadas nas sociedades, têm vindo a despoletar uma maior atenção à procura de combustíveis alternativos. Por outro lado, várias projecções indicam um aumento muito acentuado do consumo energético global no curto prazo, fruto do aumento da população e do nível de industrialização das sociedades. Neste contexto, o biodiesel (ésteres de ácidos gordos) obtido através da transesterificação de triglicerídeos de origem vegetal ou animal, surge como a alternativa “verde” mais viável para utilização em equipamentos de combustão. A reacção de transesterificação é catalisada, por norma com recurso a catalisadores homogéneos alcalinos (NaOH ou KOH). Este tipo de processo, o único actualmente com expressão a nível industrial, apresenta algumas desvantagens que, para além de aumentarem o custo do produto final, contribuem para reduzir a benignidade do mesmo: a impossibilidade de reutilização do catalisador, o aumento do número e complexidade das etapas de separação e a produção de efluentes resultantes das referidas etapas. Com o intuito de minimizar ou eliminar estes problemas, vários catalisadores heterogéneos têm vindo a ser estudados para esta reacção. Apesar de muitos apresentarem resultados promissores, a grande maioria não tem viabilidade para aplicação industrial seja devido ao seu próprio custo, seja devido aos pré-tratamentos necessários à sua utilização. Entre estes catalisadores, o óxido de cálcio é talvez o que apresenta resultados mais promissores. O crescente número de estudos envolvendo este catalisador em detrimento de outros, é por si mesmo prova do potencial do CaO. A realização deste trabalho pretendia atingir os seguintes objectivos principais: • Avaliar a elegibilidade do óxido de cálcio enquanto catalisador da reacção de transesterificação de óleos alimentares usados com metanol; • Avaliar qual a sua influência nas características dos produtos finais; • Avaliar as diferenças de performance entre o óxido de cálcio activado em atmosfera inerte (N2) e em ar, enquanto catalisadores da reacção de transesterificação de óleos alimentares usados com metanol; • Optimizar as condições da reacção com recurso às ferramentas matemáticas disponibilizadas pelo planeamento factorial, através da variação de quatro factores chave de influência: temperatura, tempo, relação metanol / óleo e massa de catalisador utilizado. O CaO utlizado foi obtido a partir de carbonato de cálcio calcinado numa mufla a 750 °C durante 3 h. Foi posteriormente activado a 900 °C durante 2h, em atmosferas diferentes: azoto (CaO-N2) e ar (CaO-Ar). Avaliaram-se algumas propriedades dos catalisadores assim preparados, força básica, concentração de centros activos e áreas específicas, tendo-se obtido uma força básica situada entre 12 e 14 para ambos os catalisadores, uma concentração de centros activos de 0,0698 mmol/g e 0,0629 mmol/g e áreas específicas de 10 m2/g e 11 m2/g respectivamente para o CaO-N2 e CaO-Ar. Efectuou-se a transesterificação, com catálise homogénea, da mistura de óleos usados utilizada neste trabalho com o objectivo de determinar os limites para o teor de FAME’s (abreviatura do Inglês de Fatty Acid Methyl Esters’) que se poderiam obter. Foi este o parâmetro avaliado em cada uma das amostras obtidas por catálise heterogénea. Os planos factoriais realizados tiveram como objectivo maximizar a sua quantidade recorrendo à relação ideal entre tempo de reacção, temperatura, massa de catalisador e quantidade de metanol. Verificou-se que o valor máximo de FAME’s obtidos a partir deste óleo estava situado ligeiramente acima dos 95 % (m/m). Realizaram-se três planos factoriais com cada um dos catalisadores de CaO até à obtenção das condições óptimas para a reacção. Não se verificou influência significativa da relação entre a quantidade de metanol e a massa de óleo na gama de valores estudada, pelo que se fixou o valor deste factor em 35 ml de metanol / 85g de óleo (relação molar aproximada de 8:1). Verificou-se a elegibilidade do CaO enquanto catalisador para a reacção estudada, não se tendo observado diferenças significativas entre a performance do CaO-N2 e do CaO-Ar. Identificaram-se as condições óptimas para a reacção como sendo os valores de 59 °C para a temperatura, 3h para o tempo e 1,4 % de massa de catalisador relativamente à massa de óleo. Nas referidas condições, obtiveram-se produtos com um teor de FAME’s de 95,7 % na catálise com CaO-N2 e 95,3 % na catálise com CaO-Ar. Alguns autores de estudos consultados no desenvolvimento do presente trabalho, referiam como principal problema da utilização do CaO, a lixiviação de cálcio para os produtos obtidos. Este facto foi confirmado no presente trabalho e na tentativa de o contornar, tentou-se promover a carbonatação do cálcio com a passagem de ar comprimido através dos produtos e subsequente filtração. Após a realização deste tratamento, não mais se observaram alterações nas suas propriedades (aparecimento de turvação ou precipitados), no entanto, nos produtos obtidos nas condições óptimas, a concentração de cálcio determinada foi de 527 mg/kg no produto da reacção catalisada com CaO-N2 e 475 mg/kg com CaO-A. O óxido de cálcio apresentou-se como um excelente catalisador na transesterificação da mistura de óleos alimentares usados utilizada no presente trabalho, apresentando uma performance ao nível da obtida por catálise homogénea básica. Não se observaram diferenças significativas de performance entre o CaO-N2 e o CaO-Ar, sendo possível obter nas mesmas condições reaccionais produtos com teores de FAME’s superiores a 95 % utilizando qualquer um deles como catalisador. O elevado teor de cálcio lixiviado observado nos produtos, apresenta-se como o principal obstáculo à aplicação a nível industrial do óxido de cálcio como catalisador para a transesterificação de óleos.

A framework for memory contention analysis in multi-core platforms

The last decade has witnessed a major shift towards the deployment of embedded applications on multi-core platforms. However, real-time applications have not been able to fully benefit from this transition, as the computational gains offered by multi-cores are often offset by performance degradation due to shared resources, such as main memory. To efficiently use multi-core platforms for real-time systems, it is hence essential to tightly bound the interference when accessing shared resources. Although there has been much recent work in this area, a remaining key problem is to address the diversity of memory arbiters in the analysis to make it applicable to a wide range of systems. This work handles diverse arbiters by proposing a general framework to compute the maximum interference caused by the shared memory bus and its impact on the execution time of the tasks running on the cores, considering different bus arbiters. Our novel approach clearly demarcates the arbiter-dependent and independent stages in the analysis of these upper bounds. The arbiter-dependent phase takes the arbiter and the task memory-traffic pattern as inputs and produces a model of the availability of the bus to a given task. Then, based on the availability of the bus, the arbiter-independent phase determines the worst-case request-release scenario that maximizes the interference experienced by the tasks due to the contention for the bus. We show that the framework addresses the diversity problem by applying it to a memory bus shared by a fixed-priority arbiter, a time-division multiplexing (TDM) arbiter, and an unspecified work-conserving arbiter using applications from the MediaBench test suite. We also experimentally evaluate the quality of the analysis by comparison with a state-of-the-art TDM analysis approach and consistently showing a considerable reduction in maximum interference.

On the numerical computation of the Mittag-Leffler function

Recently simple limiting functions establishing upper and lower bounds on the Mittag-Leffler function were found. This paper follows those expressions to design an efficient algorithm for the approximate calculation of expressions usual in fractional-order control systems. The numerical experiments demonstrate the superior efficiency of the proposed method.

Performance Analysis of IEEE 802.15.6 Contention-based MAC Protocol

IEEE International Conference on Communications (IEEE ICC 2015). 8 to 12, Jun, 2015, IEEE ICC 2015 - Communications QoS, Reliability and Modeling, London, United Kingdom.

A system model and stack for the parallelization of time-critical applications on many-core architectures

3rd Workshop on High-performance and Real-time Embedded Systems (HIRES 2015). 21, Jan, 2015. Amsterdam, Netherlands.

No encontro comigo e com os outros

No presente Relatório apresenta-se o Projeto “No Encontro Comigo e Com os Outros”, desenvolvido com um grupo de mães de pessoas com deficiência intelectual. Este Projeto propõe uma resposta de apoio e de partilha num grupo de mães, visando o estabelecimento de relações em grupo, para que se reflita de forma autónoma nos problemas comuns. Desta forma, este Projeto, para além de propor encontros de apoio emocional, aponta para o envolvimento das mães nas atividades institucionais da Associação que os filhos frequentam. Os desafios colocados às famílias com filhos com deficiência fundamentaram o desenvolvimento de um Projeto em Educação e Intervenção Social, enquanto promotor de reflexão e de autonomia. Neste sentido, todo o Projeto posicionou-se, metodologicamente, na Investigação Ação-Participativa, onde, com as pessoas, se recolheu e analisou toda a informação que conduzia aos problemas e necessidades evidenciados. A finalidade deste projeto, e todos os objetivos propostos, foram, assim, ao encontro dos problemas e necessidades priorizados pelos intervenientes, propondo-se, a partir de um conjunto de ações, alcançar uma nova realidade. Desta forma, os resultados obtidos com o Projeto foram satisfatórios, por ter contribuído para o estabelecimento de laços entre as mães, por ter fomentando a partilha e a reflexão acerca dos problemas vivenciados e por ter envolvido as mesmas nos processos institucionais. Deficiência, Família, Grupo de Apoio, Partilha, Relação.

Real-time Task-Splitting scheduling algorithms framework

Nos dias de hoje, os sistemas de tempo real crescem em importância e complexidade. Mediante a passagem do ambiente uniprocessador para multiprocessador, o trabalho realizado no primeiro não é completamente aplicável no segundo, dado que o nível de complexidade difere, principalmente devido à existência de múltiplos processadores no sistema. Cedo percebeu-se, que a complexidade do problema não cresce linearmente com a adição destes. Na verdade, esta complexidade apresenta-se como uma barreira ao avanço científico nesta área que, para já, se mantém desconhecida, e isto testemunha-se, essencialmente no caso de escalonamento de tarefas. A passagem para este novo ambiente, quer se trate de sistemas de tempo real ou não, promete gerar a oportunidade de realizar trabalho que no primeiro caso nunca seria possível, criando assim, novas garantias de desempenho, menos gastos monetários e menores consumos de energia. Este último fator, apresentou-se desde cedo, como, talvez, a maior barreira de desenvolvimento de novos processadores na área uniprocessador, dado que, à medida que novos eram lançados para o mercado, ao mesmo tempo que ofereciam maior performance, foram levando ao conhecimento de um limite de geração de calor que obrigou ao surgimento da área multiprocessador. No futuro, espera-se que o número de processadores num determinado chip venha a aumentar, e como é óbvio, novas técnicas de exploração das suas inerentes vantagens têm de ser desenvolvidas, e a área relacionada com os algoritmos de escalonamento não é exceção. Ao longo dos anos, diferentes categorias de algoritmos multiprocessador para dar resposta a este problema têm vindo a ser desenvolvidos, destacando-se principalmente estes: globais, particionados e semi-particionados. A perspectiva global, supõe a existência de uma fila global que é acessível por todos os processadores disponíveis. Este fato torna disponível a migração de tarefas, isto é, é possível parar a execução de uma tarefa e resumir a sua execução num processador distinto. Num dado instante, num grupo de tarefas, m, as tarefas de maior prioridade são selecionadas para execução. Este tipo promete limites de utilização altos, a custo elevado de preempções/migrações de tarefas. Em contraste, os algoritmos particionados, colocam as tarefas em partições, e estas, são atribuídas a um dos processadores disponíveis, isto é, para cada processador, é atribuída uma partição. Por essa razão, a migração de tarefas não é possível, acabando por fazer com que o limite de utilização não seja tão alto quando comparado com o caso anterior, mas o número de preempções de tarefas decresce significativamente. O esquema semi-particionado, é uma resposta de caráter hibrido entre os casos anteriores, pois existem tarefas que são particionadas, para serem executadas exclusivamente por um grupo de processadores, e outras que são atribuídas a apenas um processador. Com isto, resulta uma solução que é capaz de distribuir o trabalho a ser realizado de uma forma mais eficiente e balanceada. Infelizmente, para todos estes casos, existe uma discrepância entre a teoria e a prática, pois acaba-se por se assumir conceitos que não são aplicáveis na vida real. Para dar resposta a este problema, é necessário implementar estes algoritmos de escalonamento em sistemas operativos reais e averiguar a sua aplicabilidade, para caso isso não aconteça, as alterações necessárias sejam feitas, quer a nível teórico quer a nível prá

Multicore Scheduling of Real-Time Irregular Parallel Algorithms in Linux

Face à estagnação da tecnologia uniprocessador registada na passada década, aos principais fabricantes de microprocessadores encontraram na tecnologia multi-core a resposta `as crescentes necessidades de processamento do mercado. Durante anos, os desenvolvedores de software viram as suas aplicações acompanhar os ganhos de performance conferidos por cada nova geração de processadores sequenciais, mas `a medida que a capacidade de processamento escala em função do número de processadores, a computação sequencial tem de ser decomposta em várias partes concorrentes que possam executar em paralelo, para que possam utilizar as unidades de processamento adicionais e completar mais rapidamente. A programação paralela implica um paradigma completamente distinto da programação sequencial. Ao contrário dos computadores sequenciais tipificados no modelo de Von Neumann, a heterogeneidade de arquiteturas paralelas requer modelos de programação paralela que abstraiam os programadores dos detalhes da arquitectura e simplifiquem o desenvolvimento de aplicações concorrentes. Os modelos de programação paralela mais populares incitam os programadores a identificar instruções concorrentes na sua lógica de programação, e a especificá-las sob a forma de tarefas que possam ser atribuídas a processadores distintos para executarem em simultâneo. Estas tarefas são tipicamente lançadas durante a execução, e atribuídas aos processadores pelo motor de execução subjacente. Como os requisitos de processamento costumam ser variáveis, e não são conhecidos a priori, o mapeamento de tarefas para processadores tem de ser determinado dinamicamente, em resposta a alterações imprevisíveis dos requisitos de execução. `A medida que o volume da computação cresce, torna-se cada vez menos viável garantir as suas restrições temporais em plataformas uniprocessador. Enquanto os sistemas de tempo real se começam a adaptar ao paradigma de computação paralela, há uma crescente aposta em integrar execuções de tempo real com aplicações interativas no mesmo hardware, num mundo em que a tecnologia se torna cada vez mais pequena, leve, ubíqua, e portável. Esta integração requer soluções de escalonamento que simultaneamente garantam os requisitos temporais das tarefas de tempo real e mantenham um nível aceitável de QoS para as restantes execuções. Para tal, torna-se imperativo que as aplicações de tempo real paralelizem, de forma a minimizar os seus tempos de resposta e maximizar a utilização dos recursos de processamento. Isto introduz uma nova dimensão ao problema do escalonamento, que tem de responder de forma correcta a novos requisitos de execução imprevisíveis e rapidamente conjeturar o mapeamento de tarefas que melhor beneficie os critérios de performance do sistema. A técnica de escalonamento baseado em servidores permite reservar uma fração da capacidade de processamento para a execução de tarefas de tempo real, e assegurar que os efeitos de latência na sua execução não afectam as reservas estipuladas para outras execuções. No caso de tarefas escalonadas pelo tempo de execução máximo, ou tarefas com tempos de execução variáveis, torna-se provável que a largura de banda estipulada não seja consumida por completo. Para melhorar a utilização do sistema, os algoritmos de partilha de largura de banda (capacity-sharing) doam a capacidade não utilizada para a execução de outras tarefas, mantendo as garantias de isolamento entre servidores. Com eficiência comprovada em termos de espaço, tempo, e comunicação, o mecanismo de work-stealing tem vindo a ganhar popularidade como metodologia para o escalonamento de tarefas com paralelismo dinâmico e irregular. O algoritmo p-CSWS combina escalonamento baseado em servidores com capacity-sharing e work-stealing para cobrir as necessidades de escalonamento dos sistemas abertos de tempo real. Enquanto o escalonamento em servidores permite partilhar os recursos de processamento sem interferências a nível dos atrasos, uma nova política de work-stealing que opera sobre o mecanismo de capacity-sharing aplica uma exploração de paralelismo que melhora os tempos de resposta das aplicações e melhora a utilização do sistema. Esta tese propõe uma implementação do algoritmo p-CSWS para o Linux. Em concordância com a estrutura modular do escalonador do Linux, ´e definida uma nova classe de escalonamento que visa avaliar a aplicabilidade da heurística p-CSWS em circunstâncias reais. Ultrapassados os obstáculos intrínsecos `a programação da kernel do Linux, os extensos testes experimentais provam que o p-CSWS ´e mais do que um conceito teórico atrativo, e que a exploração heurística de paralelismo proposta pelo algoritmo beneficia os tempos de resposta das aplicações de tempo real, bem como a performance e eficiência da plataforma multiprocessador.