A Random Access Protocol incorporating Multi-Packet Reception, Retransmission Diversity and Successive Interference Cancellation

8th International Workshop on Multiple Access Communications (MACOM2015), Helsinki, Finland.

Generalized Extraction of Real-Time Parameters for Homogeneous Synchronous Dataflow Graphs

23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP 2015). 4 to 6, Mar, 2015. Turku, Finland.

Task partitioning and priority assignment for distributed hard real-time systems

In this paper, we propose the Distributed using Optimal Priority Assignment (DOPA) heuristic that finds a feasible partitioning and priority assignment for distributed applications based on the linear transactional model. DOPA partitions the tasks and messages in the distributed system, and makes use of the Optimal Priority Assignment (OPA) algorithm known as Audsley’s algorithm, to find the priorities for that partition. The experimental results show how the use of the OPA algorithm increases in average the number of schedulable tasks and messages in a distributed system when compared to the use of Deadline Monotonic (DM) usually favoured in other works. Afterwards, we extend these results to the assignment of Parallel/Distributed applications and present a second heuristic named Parallel-DOPA (P-DOPA). In that case, we show how the partitioning process can be simplified by using the Distributed Stretch Transformation (DST), a parallel transaction transformation algorithm introduced in [1].

Improved Numerical Simulation for a Novel Adaptive Control Using Fractional Order Derivatives

A novel control technique is investigated in the adaptive control of a typical paradigm, an approximately and partially modeled cart plus double pendulum system. In contrast to the traditional approaches that try to build up ”complete” and ”permanent” system models it develops ”temporal” and ”partial” ones that are valid only in the actual dynamic environment of the system, that is only within some ”spatio-temporal vicinity” of the actual observations. This technique was investigated for various physical systems via ”preliminary” simulations integrating by the simplest 1st order finite element approach for the time domain. In 2004 INRIA issued its SCILAB 3.0 and its improved numerical simulation tool ”Scicos” making it possible to generate ”professional”, ”convenient”, and accurate simulations. The basic principles of the adaptive control, the typical tools available in Scicos, and others developed by the authors, as well as the improved simulation results and conclusions are presented in the contribution.

A Real-Time Optimization for 2R Manipulators

This work proposes a real-time algorithm to generate a trajectory for a 2 link planar robotic manipulator. The objective is to minimize the space/time ripple and the energy requirements or the time duration in the robot trajectories. The proposed method uses an off line genetic algorithm to calculate every possible trajectory between all cells of the workspace grid. The resultant trajectories are saved in several trees. Then any trajectory requested is constructed in real-time, from these trees. The article presents the results for several experiments.

Real-Time Visual Ground-Truth System for Indoor Robotic Applications

The robotics community is concerned with the ability to infer and compare the results from researchers in areas such as vision perception and multi-robot cooperative behavior. To accomplish that task, this paper proposes a real-time indoor visual ground truth system capable of providing accuracy with at least more magnitude than the precision of the algorithm to be evaluated. A multi-camera architecture is proposed under the ROS (Robot Operating System) framework to estimate the 3D position of objects and the implementation and results were contextualized to the Robocup Middle Size League scenario.

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.

Non-preemptive and SRP-based fullypreemptive scheduling of real-time Software Transactional Memory

Recent embedded processor architectures containing multiple heterogeneous cores and non-coherent caches renewed attention to the use of Software Transactional Memory (STM) as a building block for developing parallel applications. STM promises to ease concurrent and parallel software development, but relies on the possibility of abort conflicting transactions to maintain data consistency, which in turns affects the execution time of tasks carrying transactions. Because of this fact the timing behaviour of the task set may not be predictable, thus it is crucial to limit the execution time overheads resulting from aborts. In this paper we formalise a FIFO-based algorithm to order the sequence of commits of concurrent transactions. Then, we propose and evaluate two non-preemptive and one SRP-based fully-preemptive scheduling strategies, in order to avoid transaction starvation.

Adaptive modeling and high quality spectral estimation for speech enhancement

In this work an adaptive modeling and spectral estimation scheme based on a dual Discrete Kalman Filtering (DKF) is proposed for speech enhancement. Both speech and noise signals are modeled by an autoregressive structure which provides an underlying time frame dependency and improves time-frequency resolution. The model parameters are arranged to obtain a combined state-space model and are also used to calculate instantaneous power spectral density estimates. The speech enhancement is performed by a dual discrete Kalman filter that simultaneously gives estimates for the models and the signals. This approach is particularly useful as a pre-processing module for parametric based speech recognition systems that rely on spectral time dependent models. The system performance has been evaluated by a set of human listeners and by spectral distances. In both cases the use of this pre-processing module has led to improved results.

Adaptive filtering for high quality HMM based speech synthesis

In this work an adaptive filtering scheme based on a dual Discrete Kalman Filtering (DKF) is proposed for Hidden Markov Model (HMM) based speech synthesis quality enhancement. The objective is to improve signal smoothness across HMMs and their related states and to reduce artifacts due to acoustic model's limitations. Both speech and artifacts are modelled by an autoregressive structure which provides an underlying time frame dependency and improves time-frequency resolution. Themodel parameters are arranged to obtain a combined state-space model and are also used to calculate instantaneous power spectral density estimates. The quality enhancement is performed by a dual discrete Kalman filter that simultaneously gives estimates for the models and the signals. The system's performance has been evaluated using mean opinion score tests and the proposed technique has led to improved results.

Algorithm for the Parkinson’s disease behavioural models characterization using a biosensor

Dissertação para obtenção do Grau de Mestre em Engenharia Biomédica

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.

Adaptive Game Design Study of a fully adaptive framework

Adventure! The Paladin Order foi um projecto ambicioso que começou por ser desenvolvido como um video jogo completo. Tinha como objéctivo implementar uma ferramenta diferente que permitisse tornar o jogo completamente adaptativo às decisões do jogador tanto nas interacções e no diálogo com outras personagens, assim como no combate contra os variados inímigos do jogo. Devido à inexperiência do autor uma grande parte do tempo foi passado a estudar e a pesquisar várias possíveis soluções que permitissem criar um ambiente que fosse adaptativo de uma forma simples e interessante, não só para os programadores mas também para qualquer pessoa que fosse responsável por editar o diálogo e a história do jogo. Os resultados foram bastante interessantes, revelando um sistema que depende simultaneamente dos ficheiros de onde é retirado o diálogo, e de um sistema de personalidades que permite definir qual será o comportamento de qualquer objecto do jogo ou, pelo menos, como as outras personagens irão reagir. O produto final é uma ferramenta de bases sólidas que permite uma implementação relativamente simples de um sistema abrangente e adaptativo, com poucas falhas e apenas algumas questões de simplicidade de código.

Providing Adaptation for an Adaptive Hypermedia System

O ensino à distância cresceu consideravelmente nos últimos anos e a tendência é para que continue a crescer em anos vindouros. No entanto, enquanto que a maioria das plataformas de ensino à distância utilizam a mesma abordagem de ensino para todos os utilizadores, os estudantes que as usam são na realidade pessoas de diferentes culturas, locais, idades e géneros, e que possuem diferentes níveis de educação. Ao contrário do ensino à distância tradicional, os sistemas de hipermédia adaptativa educacional adaptam interface, apresentação de conteúdos e navegação, entre outros, às características, necessidades e interesses específicos de diferentes utilizadores. Apesar da investigação na área de sistemas de hipermédia adaptativa já estar bastante desenvolvida, é necessário efetuar mais desenvolvimento e experimentação de modo a determinar quais são os aspetos mais eficazes destes sistemas e avaliar o seu sucesso. A Plataforma de Aprendizagem Colaborativa da Matemática (PCMAT) é um sistema de hipermédia adaptativa educacional com uma abordagem construtivista, que foi desenvolvido com o objetivo de contribuir para a investigação na área de sistemas de hipermédia adaptativa. A plataforma avalia o conhecimento do utilizador e apresenta conteúdos e atividades adaptadas às características e estilo de aprendizagem dominante de estudantes de matemática do segundo ciclo. O desenvolvimento do PCMAT tem também o propósito de auxiliar os alunos Portugueses com a aprendizagem da matemática. De acordo com o estudo PISA 2012 da OCDE [OECD, 2014], o desempenho dos alunos Portugueses na área da matemática melhorou em relação à edição anterior do estudo, mas os resultados obtidos permanecem abaixo da média da OCDE. Por este motivo, uma das finalidades deste projeto é desenvolver um sistema de hipermédia adaptativa que, ao adequar o ensino da matemática às necessidades específicas de cada aluno, os assista com a aquisição de conhecimento. A adaptação é efetuada pelo sistema usando a informação constante no modelo do utilizador para definir um grafo de conceitos do domínio específico. Este grafo é adaptado do modelo do domínio e utilizado para dar resposta às necessidades particulares de cada aluno. Embora a trajetória inicial seja definida pelo professor, o percurso percorrido no grafo por cada aluno é determinado pela sua interação com o sistema, usando para o efeito a representação do conhecimento do aluno e outras características disponíveis no modelo do utilizador, assim como avaliação progressiva. A adaptação é conseguida através de alterações na apresentação de conteúdos e na estrutura e anotações das hiperligações. A apresentação de conteúdos é alterada mostrando ou ocultando cada um dos vários fragmentos que compõe as páginas dum curso. Estes fragmentos são compostos por diferentes objetos de aprendizagem, tais como exercícios, figuras, diagramas, etc. As mudanças efetuadas na estrutura e anotações das hiperligações têm o objetivo de guiar o estudante, apontando-o na direção do conhecimento mais relevante e mantendo-o afastado de informação inadequada. A escolha de objectos de aprendizagem adequados às características particulares de cada aluno é um aspecto essencial do modelo de adaptação do PCMAT. A plataforma inclui para esse propósito um módulo responsável pela recomendação de objectos de aprendizagem, e um módulo para a pesquisa e recuperação dos mesmos. O módulo de recomendação utiliza lógica Fuzzy para converter determinados atributos do aluno num conjunto de parâmetros que caracterizam o objecto de aprendizagem que idealmente deveria ser apresentado ao aluno. Uma vez que o objecto “ideal” poderá não existir no repositório de objectos de aprendizagem do sistema, esses parâmetros são utilizados pelo módulo de pesquisa e recuperação para procurar e devolver ao módulo de recomendação uma lista com os objectos que mais se assemelham ao objecto “ideal”. A pesquisa é feita numa árvore k-d usando o algoritmo k-vizinhos mais próximos. O modelo de recomendação utiliza a lista devolvida pelo módulo de pesquisa e recuperação para seleccionar o objecto de aprendizagem mais apropriado para o aluno e processa-o para inclusão numa das páginas Web do curso. O presente documento descreve o trabalho desenvolvido no âmbito do projeto PCMAT (PTDS/CED/108339/2008), dando relevância à adaptação de conteúdos.