<p>Event-triggered real-time systems are desirable to use in environments where the arrival of events are hard to predict. The semantics of an event-triggered system is well mapped to the behaviour of an active database management system (ADBMS), specified using event-condition-action (ECA) rules. The benefits of using an active database, such as persistent data storage, concurrency control, timely response to event occurrences etc. highlights the need for a development method for event-triggered real-time systems using active databases.</p><p>However, there are problems left to be solved before an ADBMS can be used with confidence in real-time environments. The behaviour of a real-time system must be predictable, which implies a thorough analysed specification with e.g. specified worst case execution times. The predictability requirement is an obstacle for specifying real-time systems as ECA rules, since the rules may affect each other in many intricate ways which makes them hard to analyse. The interaction between the rules implies that it is not enough to verify the correctness of single rules; an analysis must consider the behaviour of the entire rule set.</p><p>In this dissertation, an approach for developing active applications is presented. A method is examined which starts with an analysed high-level timed automaton specification and transforms the specified behaviour into an implicitly analysed rule set. For this method to be useful, the transformation from timed automata to rules must preserve the exact behaviour of the high level specification. Hence, the aim of this dissertation is to verify transformations between timed automaton specifications and ECA rules.</p><p>The contribution of this project is a structured set of general transformations between timed automata specifications and ECA rules. The transformations include both transformations of small timed automata constructs for deterministic environments and formally verified timed automata patterns specifying the behaviour of composite events in recent and chronicle context.</p>

Multi-Processor System on Chip (MPSoC) consisting of multiple processing cores connected via a Network on Chip (NoC) has gained prominence over the last decade. Most common way of mapping applications to MPSoCs is by dividing the application into small tasks and representing them in the form of a task graph where the edges connecting the tasks represent the inter task communication. Task scheduling involves mapping task to processor cores so as to meet a specified deadline for the application/task graph. With increase in system complexity and application parallelism, task communication times are tending towards task execution times. Hence the NoC which forms the communication backbone for the cores plays a critical role in meeting the deadlines. In this thesis we present an approach to synthesize a minimal network connecting a set of cores in a MPSoC in the presence of deadlines. Given a task graph and a corresponding task to processor schedule, we have developed a partitioning methodology to generate an efficient interconnection network for the cores. We adopt a 2-phase design flow where we synthesize the network in first phase and in second phase we perform statistical analysis of the network thus generated. We compare our model with a simulated annealing based scheme, a static graph based greedy scheme and the standard mesh topology. The proposed solution offers significant area and performance benefits over the alternate solutions compared in this work.

Event-triggered real-time systems are desirable to use in environments where the arrival of events are hard to predict. The semantics of an event-triggered system is well mapped to the behaviour of an active database management system (ADBMS), specified using event-condition-action (ECA) rules. The benefits of using an active database, such as persistent data storage, concurrency control, timely response to event occurrences etc. highlights the need for a development method for event-triggered real-time systems using active databases. However, there are problems left to be solved before an ADBMS can be used with confidence in real-time environments. The behaviour of a real-time system must be predictable, which implies a thorough analysed specification with e.g. specified worst case execution times. The predictability requirement is an obstacle for specifying real-time systems as ECA rules, since the rules may affect each other in many intricate ways which makes them hard to analyse. The interaction between the rules implies that it is not enough to verify the correctness of single rules; an analysis must consider the behaviour of the entire rule set. In this dissertation, an approach for developing active applications is presented. A method is examined which starts with an analysed high-level timed automaton specification and transforms the specified behaviour into an implicitly analysed rule set. For this method to be useful, the transformation from timed automata to rules must preserve the exact behaviour of the high level specification. Hence, the aim of this dissertation is to verify transformations between timed automaton specifications and ECA rules. The contribution of this project is a structured set of general transformations between timed automata specifications and ECA rules. The transformations include both transformations of small timed automata constructs for deterministic environments and formally verified timed automata patterns specifying the behaviour of composite events in recent and chronicle context.

Muitos pesquisadores têm se interessado em explorar o vasto poder computacional das recentes unidades de processamento gráfico (GPUs) em aplicações fora do domínio gráfico. Essa tendência ao desenvolvimento de propósitos gerais com a GPU (GPGPU) foi intensificada com a produção de APIs não-gráficas, tais como a Compute Unified Device Architecture (CUDA), da NVIDIA. Com elas, estudou-se a solução na GPU de muitos problemas de processamento de sinal 2D e 3D envolvendo álgebra linear e equações diferenciais parciais, mas pouca atenção tem sido dada ao processamento de sinais 1D, que também podem exigir recursos computacionais significativos. Já havia sido demonstrado que a GPU pode ser usada para processamento de sinais em tempo-real, mas alguns processos não se adequavam bem à arquitetura da GPU. Neste trabalho, apresento uma nova técnica para implementar um filtro digital linear recursivo usando a GPU. Até onde eu sei, a solução aqui apresentada é a primeira na literatura. Uma comparação entre esta abordagem e uma implementação equivalente baseada na CPU demonstra que, quando usada em um sistema de processamento de áudio em temporeal, esta técnica permite o processamento de duas a quatro vezes mais coeficientes do que era possível anteriormente. A técnica também elimina a necessidade de processar o filtro na CPU - evitando transferências de memória adicionais entre CPU e GPU - quando se deseja usar o filtro junto a outros processos, tais como síntese de som. A recursividade estabelecida pela equação do filtro torna difícil obter uma implementação eficiente em uma arquitetura paralela como a da GPU. Já que cada amostra de saída é computada em paralelo, os valores necessários de amostras de saída anteriores não estão disponíveis no momento do cômputo. Poder-se-ia forçar a GPU a executar o filtro sequencialmente usando sincronização, mas isso seria um uso ineficiente da GPU. Este problema foi resolvido desdobrando-se a equação e "trocando-se" as dependências de amostras próximas à saída atual por outras precedentes, assim exigindo apenas o armazenamento de um certo número de amostras de saída. A equação resultante contém convoluções que então são eficientemente computadas usando a FFT. A implementação da técnica é geral e funciona para qualquer filtro recursivo linear invariante no tempo. Para demonstrar sua relevância, construímos um filtro LPC para sintetizar em tempo-real sons realísticos de colisões de objetos feitos de diferentes materiais, tais como vidro, plástico e madeira. Os sons podem ser parametrizados por material dos objetos, velocidade e ângulo das colisões. Apesar de flexível, esta abordagem usa pouca memória, exigindo apenas alguns coeficientes para representar a resposta ao impulso do filtro para cada material. Isso torna esta abordagem uma alternativa atraente frente às técnicas tradicionais baseadas em CPU que apenas realizam a reprodução de sons gravados. / Many researchers have been interested in exploring the vast computational power of recent graphics processing units (GPUs) in applications outside the graphics domain. This trend towards General-Purpose GPU (GPGPU) development has been intensified with the release of non-graphics APIs for GPU programming, such as NVIDIA's Compute Unified Device Architecture (CUDA). With them, the GPU has been widely studied for solving many 2D and 3D signal processing problems involving linear algebra and partial differential equations, but little attention has been given to 1D signal processing, which may demand significant computational resources likewise. It has been previously demonstrated that the GPU can be used for real-time signal processing, but several processes did not fit the GPU architecture well. In this work, a new technique for implementing a digital recursive linear filter using the GPU is presented. To the best of my knowledge, the solution presented here is the first in the literature. A comparison between this approach and an equivalent CPU-based implementation demonstrates that, when used in a real-time audio processing system, this technique supports processing of two to four times more coefficients than it was possible previously. The technique also eliminates the necessity of processing the filter on the CPU - avoiding additional memory transfers between CPU and GPU - when one wishes to use the filter in conjunction with other processes, such as sound synthesis. The recursivity established by the filter equation makes it difficult to obtain an efficient implementation on a parallel architecture like the GPU. Since every output sample is computed in parallel, the necessary values of previous output samples are unavailable at the time the computation takes place. One could force the GPU to execute the filter sequentially using synchronization, but this would be a very inefficient use of GPU resources. This problem is solved by unrolling the equation and "trading" dependences on samples close to the current output by other preceding ones, thus requiring only the storage of a limited number of previous output samples. The resulting equation contains convolutions which are then efficiently computed using the FFT. The proposed technique's implementation is general and works for any time-invariant recursive linear filter. To demonstrate its relevance, an LPC filter is designed to synthesize in real-time realistic sounds of collisions between objects made of different materials, such as glass, plastic, and wood. The synthesized sounds can be parameterized by the objects' materials, velocities and collision angles. Despite its flexibility, this approach uses very little memory, requiring only a few coefficients to represent the impulse response for the filter of each material. This turns this approach into an attractive alternative to traditional CPU-based techniques that use playback of pre-recorded sounds.

Esta dissertação aborda um ramo da computação que se encontra em crescente desenvolvimento: a computação em tempo real. Os sistemas de computação tempo real surgiram a partir da necessidade de substituição do controle humano, que muitas vezes é falho, em situações complexas ou críticas, onde máxima confiabilidade e disponibilidade são exigidas para garantir a segurança do sistema. A área de aplicação diferencia-se de outras convencionais por possuir diferentes tipos de restrições de tempo e operar em ambientes não-determinísticos. Entretanto, atualmente tais sistemas estão tornando-se grandes, complexos, distribuídos, adaptativos e cada vez mais presentes nas aplicações do dia-a-dia,o que tende a exigir soluções mais simples e generalizadas. Pelo fato de tais sistemas normalmente atuarem sobre aplicações críticas, importante salientar que, em algumas situações, pequenos erros no sistema podem levar a grandes catástrofes. Mesmo atrasos mínimos no tempo de resposta são problemáticos, podendo ocasionar degradações ou ações erradas no mundo físico controlado pelo sistema tempo real. Como nestes casos máxima confiabilidade e disponibilidade são exigidas para garantir a sua segurança, tornou-se importante a construção de sistemas tempo real tolerantes a falhas. Dessa forma, é visivelmente crescente a necessidade de utilização de mecanismos capazes de abordar os requisitos de tempo real e tolerância a falhas de forma integrada durante o desenvolvimento do sistema. Assim, o processo de desenvolvimento de sistemas tempo real confiáveis torna-se mais simples e mais eficiente. A necessidade de maior conhecimento do uso de tolerância a falhas para obter segurança no funcionamento de aplicações tempo real levou ao desenvolvimento deste trabalho, onde buscou-se um caminho de solução para a adequação das técnicas de tolerância a falhas a estas aplicações. Sabe-se que para produzir software confiável e, desta forma de maior qualidade, além do emprego de boas técnicas de engenharia de software, é necessário compreender os principais conceitos e técnicas de tolerância a falhas. Por outro lado, é importante ter-se conhecimento dos mecanismos oferecidos pelas diversas camadas de software de um sistema - protocolo de comunicação, sistema operacional e linguagem de programação - para apoiar estas atividades de tolerância a falhas. Este trabalho busca analisar os mecanismos e técnicas usados na implementação de software tolerante a falhas frente às situações mencionadas, uma vez que nem todas as técnicas conhecidas podem ser indistintamente aplicáveis a estas situações. Os resultados desta análise são organizados na forma de uma taxonomia, visando assim auxiliar projetistas de desenvolvimento de software a tomarem decisões importantes na construção de sistemas tempo real tolerantes a falhas. Os mecanismos são agrupados de acordo com o nível de implementação: sistemas operacionais, linguagens de programação e protocolos de comunicação, destacando suas características e aplicabilidade. Por fim uso da classificação é demonstrado com a análise de três casos-exemplo. / This dissertation is about a, computer science field which is in growing development, that is, real-time computation. Real-time computing systems have emerged from the necessity of substituting. human control which is sometimes failed in complex or critical situations. In these ones maximum availability and reliability are requested in order to guarantee the system dependability. The application area differs from the conventional ones because it has particular time constraints and operates in nondeterministic environments. Nevertheless, nowadays such systems are becoming large, complex, distributed and adaptive but tend to demand simpler and generalized solutions as they are more present in daily applications. Since such systems normally act on critical applications it is important to reinforce, that in some situations, subtle systems errors may generate big catastrophes. Even slight delays in response time are troublesome and they may cause degradation or wrong acts in physical world controlled by real-time systems. In these cases maximum reliability and availability are requested in order to guarantee system dependability. Thereby, the requirement of including mechanisms capable of achieving real-time and fault tolerance in an integrated way during the system design has been increased. Thus, the developing process of reliable real-time systems becomes simpler and more effective. The necessity of improving designers knowledge on using fault tolerance in order to obtain dependability on real-time applications has motivated this study. Our main goal has been to find an adequate way of using fault tolerance techniques to these applications. It is known that the development of reliable software not only requires appropriate software engineering techniques but also demands understanding of main politics and mechanisms used to implement fault tolerance techniques in these situations. Otherwise, it is very important to know the related support that is offered by the different software levels of a system - communication protocol, operating system and programming language. This study has as purpose analyzing the mechanisms and techniques used in implementation of fault-tolerant software applied to the previously mentioned situations. The basic supposition is that not all the known techniques may be applied indistinctly to these situations. The properties of the software are organized according to a taxonomy, where the mechanisms are bracketed in groups according to implementation level: operating systems, programming languages and communication protocols. In this presentation, the characteristics and applicability of the software tools are stood out in order to help developing-software designers to decide what is important to build faulttolerant software. Finally, the use of the classification is demonstrated by analyzing three case-examples.

Muitos pesquisadores têm se interessado em explorar o vasto poder computacional das recentes unidades de processamento gráfico (GPUs) em aplicações fora do domínio gráfico. Essa tendência ao desenvolvimento de propósitos gerais com a GPU (GPGPU) foi intensificada com a produção de APIs não-gráficas, tais como a Compute Unified Device Architecture (CUDA), da NVIDIA. Com elas, estudou-se a solução na GPU de muitos problemas de processamento de sinal 2D e 3D envolvendo álgebra linear e equações diferenciais parciais, mas pouca atenção tem sido dada ao processamento de sinais 1D, que também podem exigir recursos computacionais significativos. Já havia sido demonstrado que a GPU pode ser usada para processamento de sinais em tempo-real, mas alguns processos não se adequavam bem à arquitetura da GPU. Neste trabalho, apresento uma nova técnica para implementar um filtro digital linear recursivo usando a GPU. Até onde eu sei, a solução aqui apresentada é a primeira na literatura. Uma comparação entre esta abordagem e uma implementação equivalente baseada na CPU demonstra que, quando usada em um sistema de processamento de áudio em temporeal, esta técnica permite o processamento de duas a quatro vezes mais coeficientes do que era possível anteriormente. A técnica também elimina a necessidade de processar o filtro na CPU - evitando transferências de memória adicionais entre CPU e GPU - quando se deseja usar o filtro junto a outros processos, tais como síntese de som. A recursividade estabelecida pela equação do filtro torna difícil obter uma implementação eficiente em uma arquitetura paralela como a da GPU. Já que cada amostra de saída é computada em paralelo, os valores necessários de amostras de saída anteriores não estão disponíveis no momento do cômputo. Poder-se-ia forçar a GPU a executar o filtro sequencialmente usando sincronização, mas isso seria um uso ineficiente da GPU. Este problema foi resolvido desdobrando-se a equação e "trocando-se" as dependências de amostras próximas à saída atual por outras precedentes, assim exigindo apenas o armazenamento de um certo número de amostras de saída. A equação resultante contém convoluções que então são eficientemente computadas usando a FFT. A implementação da técnica é geral e funciona para qualquer filtro recursivo linear invariante no tempo. Para demonstrar sua relevância, construímos um filtro LPC para sintetizar em tempo-real sons realísticos de colisões de objetos feitos de diferentes materiais, tais como vidro, plástico e madeira. Os sons podem ser parametrizados por material dos objetos, velocidade e ângulo das colisões. Apesar de flexível, esta abordagem usa pouca memória, exigindo apenas alguns coeficientes para representar a resposta ao impulso do filtro para cada material. Isso torna esta abordagem uma alternativa atraente frente às técnicas tradicionais baseadas em CPU que apenas realizam a reprodução de sons gravados. / Many researchers have been interested in exploring the vast computational power of recent graphics processing units (GPUs) in applications outside the graphics domain. This trend towards General-Purpose GPU (GPGPU) development has been intensified with the release of non-graphics APIs for GPU programming, such as NVIDIA's Compute Unified Device Architecture (CUDA). With them, the GPU has been widely studied for solving many 2D and 3D signal processing problems involving linear algebra and partial differential equations, but little attention has been given to 1D signal processing, which may demand significant computational resources likewise. It has been previously demonstrated that the GPU can be used for real-time signal processing, but several processes did not fit the GPU architecture well. In this work, a new technique for implementing a digital recursive linear filter using the GPU is presented. To the best of my knowledge, the solution presented here is the first in the literature. A comparison between this approach and an equivalent CPU-based implementation demonstrates that, when used in a real-time audio processing system, this technique supports processing of two to four times more coefficients than it was possible previously. The technique also eliminates the necessity of processing the filter on the CPU - avoiding additional memory transfers between CPU and GPU - when one wishes to use the filter in conjunction with other processes, such as sound synthesis. The recursivity established by the filter equation makes it difficult to obtain an efficient implementation on a parallel architecture like the GPU. Since every output sample is computed in parallel, the necessary values of previous output samples are unavailable at the time the computation takes place. One could force the GPU to execute the filter sequentially using synchronization, but this would be a very inefficient use of GPU resources. This problem is solved by unrolling the equation and "trading" dependences on samples close to the current output by other preceding ones, thus requiring only the storage of a limited number of previous output samples. The resulting equation contains convolutions which are then efficiently computed using the FFT. The proposed technique's implementation is general and works for any time-invariant recursive linear filter. To demonstrate its relevance, an LPC filter is designed to synthesize in real-time realistic sounds of collisions between objects made of different materials, such as glass, plastic, and wood. The synthesized sounds can be parameterized by the objects' materials, velocities and collision angles. Despite its flexibility, this approach uses very little memory, requiring only a few coefficients to represent the impulse response for the filter of each material. This turns this approach into an attractive alternative to traditional CPU-based techniques that use playback of pre-recorded sounds.

Esta dissertação aborda um ramo da computação que se encontra em crescente desenvolvimento: a computação em tempo real. Os sistemas de computação tempo real surgiram a partir da necessidade de substituição do controle humano, que muitas vezes é falho, em situações complexas ou críticas, onde máxima confiabilidade e disponibilidade são exigidas para garantir a segurança do sistema. A área de aplicação diferencia-se de outras convencionais por possuir diferentes tipos de restrições de tempo e operar em ambientes não-determinísticos. Entretanto, atualmente tais sistemas estão tornando-se grandes, complexos, distribuídos, adaptativos e cada vez mais presentes nas aplicações do dia-a-dia,o que tende a exigir soluções mais simples e generalizadas. Pelo fato de tais sistemas normalmente atuarem sobre aplicações críticas, importante salientar que, em algumas situações, pequenos erros no sistema podem levar a grandes catástrofes. Mesmo atrasos mínimos no tempo de resposta são problemáticos, podendo ocasionar degradações ou ações erradas no mundo físico controlado pelo sistema tempo real. Como nestes casos máxima confiabilidade e disponibilidade são exigidas para garantir a sua segurança, tornou-se importante a construção de sistemas tempo real tolerantes a falhas. Dessa forma, é visivelmente crescente a necessidade de utilização de mecanismos capazes de abordar os requisitos de tempo real e tolerância a falhas de forma integrada durante o desenvolvimento do sistema. Assim, o processo de desenvolvimento de sistemas tempo real confiáveis torna-se mais simples e mais eficiente. A necessidade de maior conhecimento do uso de tolerância a falhas para obter segurança no funcionamento de aplicações tempo real levou ao desenvolvimento deste trabalho, onde buscou-se um caminho de solução para a adequação das técnicas de tolerância a falhas a estas aplicações. Sabe-se que para produzir software confiável e, desta forma de maior qualidade, além do emprego de boas técnicas de engenharia de software, é necessário compreender os principais conceitos e técnicas de tolerância a falhas. Por outro lado, é importante ter-se conhecimento dos mecanismos oferecidos pelas diversas camadas de software de um sistema - protocolo de comunicação, sistema operacional e linguagem de programação - para apoiar estas atividades de tolerância a falhas. Este trabalho busca analisar os mecanismos e técnicas usados na implementação de software tolerante a falhas frente às situações mencionadas, uma vez que nem todas as técnicas conhecidas podem ser indistintamente aplicáveis a estas situações. Os resultados desta análise são organizados na forma de uma taxonomia, visando assim auxiliar projetistas de desenvolvimento de software a tomarem decisões importantes na construção de sistemas tempo real tolerantes a falhas. Os mecanismos são agrupados de acordo com o nível de implementação: sistemas operacionais, linguagens de programação e protocolos de comunicação, destacando suas características e aplicabilidade. Por fim uso da classificação é demonstrado com a análise de três casos-exemplo. / This dissertation is about a, computer science field which is in growing development, that is, real-time computation. Real-time computing systems have emerged from the necessity of substituting. human control which is sometimes failed in complex or critical situations. In these ones maximum availability and reliability are requested in order to guarantee the system dependability. The application area differs from the conventional ones because it has particular time constraints and operates in nondeterministic environments. Nevertheless, nowadays such systems are becoming large, complex, distributed and adaptive but tend to demand simpler and generalized solutions as they are more present in daily applications. Since such systems normally act on critical applications it is important to reinforce, that in some situations, subtle systems errors may generate big catastrophes. Even slight delays in response time are troublesome and they may cause degradation or wrong acts in physical world controlled by real-time systems. In these cases maximum reliability and availability are requested in order to guarantee system dependability. Thereby, the requirement of including mechanisms capable of achieving real-time and fault tolerance in an integrated way during the system design has been increased. Thus, the developing process of reliable real-time systems becomes simpler and more effective. The necessity of improving designers knowledge on using fault tolerance in order to obtain dependability on real-time applications has motivated this study. Our main goal has been to find an adequate way of using fault tolerance techniques to these applications. It is known that the development of reliable software not only requires appropriate software engineering techniques but also demands understanding of main politics and mechanisms used to implement fault tolerance techniques in these situations. Otherwise, it is very important to know the related support that is offered by the different software levels of a system - communication protocol, operating system and programming language. This study has as purpose analyzing the mechanisms and techniques used in implementation of fault-tolerant software applied to the previously mentioned situations. The basic supposition is that not all the known techniques may be applied indistinctly to these situations. The properties of the software are organized according to a taxonomy, where the mechanisms are bracketed in groups according to implementation level: operating systems, programming languages and communication protocols. In this presentation, the characteristics and applicability of the software tools are stood out in order to help developing-software designers to decide what is important to build faulttolerant software. Finally, the use of the classification is demonstrated by analyzing three case-examples.

Le processus de développement des systèmes avioniques suit des réglementations de sûreté de fonctionnement très strictes, incluant l'analyse du déterminisme et de la prédictibilité temporelle des systèmes. L'approche est basée sur la séparation des étapes de conception et d'implémentation. Une des plus grandes difficultés dans l'approche actuelle se trouve dans la détermination du WCET, qui est nécessaire pour prouver la satisfaction des contraintes de temps-réel dur du système. Dans cette thèse, une méthodologie de relâchement de contraintes temps-réels pour les systèmes de commandes digital est proposé. L'objectif est de réduire le conservatisme des approches traditionnelles basés sur le pire temps d'exécution, tout en préservant la stabilité et les performances de commandes. L'approche a été appliqué au système de commande de tangage d'un avion, ce qui a permi de montrer que le relâchement des contraintes temps réels améliore l'utilisation de la puissance de calcul disponible tout en préservant la stabilité et la qualité de commande du système. / The development process of critical avionics products are done under strict safety regulations. These regulations include determinism and predictability of the systems' timing. The overall approach is based on a separation of concerns between control design and implementation. One of the toughest challenges in the current approach is the determination of the WCET, in order to correctly size the system. In this thesis, a weakened implementation scheme for real-time feedback controllers is proposed to reduce the conservatism due to traditional worst-case considerations, while preserving the stability and control performance. The methodology is tested to the pitch control of an aircraft, showing that weakening the real-time constraints allows for saving computing power while preserving the system's stability and quality of control.

Muitos pesquisadores têm se interessado em explorar o vasto poder computacional das recentes unidades de processamento gráfico (GPUs) em aplicações fora do domínio gráfico. Essa tendência ao desenvolvimento de propósitos gerais com a GPU (GPGPU) foi intensificada com a produção de APIs não-gráficas, tais como a Compute Unified Device Architecture (CUDA), da NVIDIA. Com elas, estudou-se a solução na GPU de muitos problemas de processamento de sinal 2D e 3D envolvendo álgebra linear e equações diferenciais parciais, mas pouca atenção tem sido dada ao processamento de sinais 1D, que também podem exigir recursos computacionais significativos. Já havia sido demonstrado que a GPU pode ser usada para processamento de sinais em tempo-real, mas alguns processos não se adequavam bem à arquitetura da GPU. Neste trabalho, apresento uma nova técnica para implementar um filtro digital linear recursivo usando a GPU. Até onde eu sei, a solução aqui apresentada é a primeira na literatura. Uma comparação entre esta abordagem e uma implementação equivalente baseada na CPU demonstra que, quando usada em um sistema de processamento de áudio em temporeal, esta técnica permite o processamento de duas a quatro vezes mais coeficientes do que era possível anteriormente. A técnica também elimina a necessidade de processar o filtro na CPU - evitando transferências de memória adicionais entre CPU e GPU - quando se deseja usar o filtro junto a outros processos, tais como síntese de som. A recursividade estabelecida pela equação do filtro torna difícil obter uma implementação eficiente em uma arquitetura paralela como a da GPU. Já que cada amostra de saída é computada em paralelo, os valores necessários de amostras de saída anteriores não estão disponíveis no momento do cômputo. Poder-se-ia forçar a GPU a executar o filtro sequencialmente usando sincronização, mas isso seria um uso ineficiente da GPU. Este problema foi resolvido desdobrando-se a equação e "trocando-se" as dependências de amostras próximas à saída atual por outras precedentes, assim exigindo apenas o armazenamento de um certo número de amostras de saída. A equação resultante contém convoluções que então são eficientemente computadas usando a FFT. A implementação da técnica é geral e funciona para qualquer filtro recursivo linear invariante no tempo. Para demonstrar sua relevância, construímos um filtro LPC para sintetizar em tempo-real sons realísticos de colisões de objetos feitos de diferentes materiais, tais como vidro, plástico e madeira. Os sons podem ser parametrizados por material dos objetos, velocidade e ângulo das colisões. Apesar de flexível, esta abordagem usa pouca memória, exigindo apenas alguns coeficientes para representar a resposta ao impulso do filtro para cada material. Isso torna esta abordagem uma alternativa atraente frente às técnicas tradicionais baseadas em CPU que apenas realizam a reprodução de sons gravados. / Many researchers have been interested in exploring the vast computational power of recent graphics processing units (GPUs) in applications outside the graphics domain. This trend towards General-Purpose GPU (GPGPU) development has been intensified with the release of non-graphics APIs for GPU programming, such as NVIDIA's Compute Unified Device Architecture (CUDA). With them, the GPU has been widely studied for solving many 2D and 3D signal processing problems involving linear algebra and partial differential equations, but little attention has been given to 1D signal processing, which may demand significant computational resources likewise. It has been previously demonstrated that the GPU can be used for real-time signal processing, but several processes did not fit the GPU architecture well. In this work, a new technique for implementing a digital recursive linear filter using the GPU is presented. To the best of my knowledge, the solution presented here is the first in the literature. A comparison between this approach and an equivalent CPU-based implementation demonstrates that, when used in a real-time audio processing system, this technique supports processing of two to four times more coefficients than it was possible previously. The technique also eliminates the necessity of processing the filter on the CPU - avoiding additional memory transfers between CPU and GPU - when one wishes to use the filter in conjunction with other processes, such as sound synthesis. The recursivity established by the filter equation makes it difficult to obtain an efficient implementation on a parallel architecture like the GPU. Since every output sample is computed in parallel, the necessary values of previous output samples are unavailable at the time the computation takes place. One could force the GPU to execute the filter sequentially using synchronization, but this would be a very inefficient use of GPU resources. This problem is solved by unrolling the equation and "trading" dependences on samples close to the current output by other preceding ones, thus requiring only the storage of a limited number of previous output samples. The resulting equation contains convolutions which are then efficiently computed using the FFT. The proposed technique's implementation is general and works for any time-invariant recursive linear filter. To demonstrate its relevance, an LPC filter is designed to synthesize in real-time realistic sounds of collisions between objects made of different materials, such as glass, plastic, and wood. The synthesized sounds can be parameterized by the objects' materials, velocities and collision angles. Despite its flexibility, this approach uses very little memory, requiring only a few coefficients to represent the impulse response for the filter of each material. This turns this approach into an attractive alternative to traditional CPU-based techniques that use playback of pre-recorded sounds.

Esta dissertação aborda um ramo da computação que se encontra em crescente desenvolvimento: a computação em tempo real. Os sistemas de computação tempo real surgiram a partir da necessidade de substituição do controle humano, que muitas vezes é falho, em situações complexas ou críticas, onde máxima confiabilidade e disponibilidade são exigidas para garantir a segurança do sistema. A área de aplicação diferencia-se de outras convencionais por possuir diferentes tipos de restrições de tempo e operar em ambientes não-determinísticos. Entretanto, atualmente tais sistemas estão tornando-se grandes, complexos, distribuídos, adaptativos e cada vez mais presentes nas aplicações do dia-a-dia,o que tende a exigir soluções mais simples e generalizadas. Pelo fato de tais sistemas normalmente atuarem sobre aplicações críticas, importante salientar que, em algumas situações, pequenos erros no sistema podem levar a grandes catástrofes. Mesmo atrasos mínimos no tempo de resposta são problemáticos, podendo ocasionar degradações ou ações erradas no mundo físico controlado pelo sistema tempo real. Como nestes casos máxima confiabilidade e disponibilidade são exigidas para garantir a sua segurança, tornou-se importante a construção de sistemas tempo real tolerantes a falhas. Dessa forma, é visivelmente crescente a necessidade de utilização de mecanismos capazes de abordar os requisitos de tempo real e tolerância a falhas de forma integrada durante o desenvolvimento do sistema. Assim, o processo de desenvolvimento de sistemas tempo real confiáveis torna-se mais simples e mais eficiente. A necessidade de maior conhecimento do uso de tolerância a falhas para obter segurança no funcionamento de aplicações tempo real levou ao desenvolvimento deste trabalho, onde buscou-se um caminho de solução para a adequação das técnicas de tolerância a falhas a estas aplicações. Sabe-se que para produzir software confiável e, desta forma de maior qualidade, além do emprego de boas técnicas de engenharia de software, é necessário compreender os principais conceitos e técnicas de tolerância a falhas. Por outro lado, é importante ter-se conhecimento dos mecanismos oferecidos pelas diversas camadas de software de um sistema - protocolo de comunicação, sistema operacional e linguagem de programação - para apoiar estas atividades de tolerância a falhas. Este trabalho busca analisar os mecanismos e técnicas usados na implementação de software tolerante a falhas frente às situações mencionadas, uma vez que nem todas as técnicas conhecidas podem ser indistintamente aplicáveis a estas situações. Os resultados desta análise são organizados na forma de uma taxonomia, visando assim auxiliar projetistas de desenvolvimento de software a tomarem decisões importantes na construção de sistemas tempo real tolerantes a falhas. Os mecanismos são agrupados de acordo com o nível de implementação: sistemas operacionais, linguagens de programação e protocolos de comunicação, destacando suas características e aplicabilidade. Por fim uso da classificação é demonstrado com a análise de três casos-exemplo. / This dissertation is about a, computer science field which is in growing development, that is, real-time computation. Real-time computing systems have emerged from the necessity of substituting. human control which is sometimes failed in complex or critical situations. In these ones maximum availability and reliability are requested in order to guarantee the system dependability. The application area differs from the conventional ones because it has particular time constraints and operates in nondeterministic environments. Nevertheless, nowadays such systems are becoming large, complex, distributed and adaptive but tend to demand simpler and generalized solutions as they are more present in daily applications. Since such systems normally act on critical applications it is important to reinforce, that in some situations, subtle systems errors may generate big catastrophes. Even slight delays in response time are troublesome and they may cause degradation or wrong acts in physical world controlled by real-time systems. In these cases maximum reliability and availability are requested in order to guarantee system dependability. Thereby, the requirement of including mechanisms capable of achieving real-time and fault tolerance in an integrated way during the system design has been increased. Thus, the developing process of reliable real-time systems becomes simpler and more effective. The necessity of improving designers knowledge on using fault tolerance in order to obtain dependability on real-time applications has motivated this study. Our main goal has been to find an adequate way of using fault tolerance techniques to these applications. It is known that the development of reliable software not only requires appropriate software engineering techniques but also demands understanding of main politics and mechanisms used to implement fault tolerance techniques in these situations. Otherwise, it is very important to know the related support that is offered by the different software levels of a system - communication protocol, operating system and programming language. This study has as purpose analyzing the mechanisms and techniques used in implementation of fault-tolerant software applied to the previously mentioned situations. The basic supposition is that not all the known techniques may be applied indistinctly to these situations. The properties of the software are organized according to a taxonomy, where the mechanisms are bracketed in groups according to implementation level: operating systems, programming languages and communication protocols. In this presentation, the characteristics and applicability of the software tools are stood out in order to help developing-software designers to decide what is important to build faulttolerant software. Finally, the use of the classification is demonstrated by analyzing three case-examples.