251 |
FPGA prototyping of custom GPGPUsNigania, Nimit 08 January 2014 (has links)
Prototyping new systems on hardware is a time-consuming task with limited scope for architectural exploration. The aim of this work was to perform fast prototyping of general-purpose graphics processing units (GPGPUs) on field programmable gate arrays (FPGAs) using a novel tool chain. This hardware flow combined with the higher level simulation flow using the same source code allowed us to create a whole tool chain to study and build future architectures using new technologies. It also gave us enough flexibility at different granularities to make architectural decisions. We will also discuss some example systems that were built using this tool chain along with some results.
|
252 |
Parallélisation et optimisation d'un simulateur de morphogénèse d'organes. Application aux éléments du reinCaux, Jonathan 30 November 2012 (has links) (PDF)
Depuis plusieurs dizaines d'années, la modélisation du vivant est un enjeu majeur qui nécessite de plus en plus de travaux dans le domaine de la simulation. En effet, elle ouvre la porte à toute une palette d'applications : l'aide à la décision en environnement et en écologie, l'aide à l'enseignement, l'aide à la décision pour les médecins, l'aide à la recherche de nouveaux traitements pharmaceutiques et la biologie dite " prédictive ", etc. Avant de pouvoir aborder un problème, il est nécessaire de pouvoir modéliser de façon précise le système biologique concerné en précisant bien les questions auxquelles devra répondre le modèle. La manipulation et l'étude de systèmes complexes, les systèmes biologiques en étant l'archétype, pose, de façon générale, des problèmes de modélisation et de simulation. C'est dans ce contexte que la société Integrative BioComputing (IBC) développe depuis le début des années 2000 un prototype d'une Plateforme Générique de Modélisation et de Simulation (la PGMS) dont le but est de fournir un environnement pour modéliser et simuler plus simplement les processus et les fonctions biologiques d'un organisme complet avec les organes le composant. La PGMS étant une plateforme générique encore en phase de développement, elle ne possédait pas les performances nécessaires pour permettre de réaliser la modélisation et la simulation d'éléments importants dans des temps suffisamment courts. Il a donc été décidé, afin d'améliorer drastiquement les performances de la PGMS, de paralléliser et d'optimiser l'implémentation de celle-ci ; le but étant de permettre la modélisation et la simulation d'organes complets dans des temps acceptables. Le travail réalisé au cours de cette thèse a donc consisté à traiter différents aspects de la modélisation et de la simulation de systèmes biologiques afin d'accélérer les traitements de ceux-ci. Le traitement le plus gourmand en termes de temps de calcul lors de l'exécution de la PGMS, le calcul des champs physicochimiques, a ainsi fait l'objet d'une étude de faisabilité de sa parallélisation. Parmi les différentes architectures disponibles pour paralléliser une telle application, notre choix s'est porté sur l'utilisation de GPU (Graphical Processing Unit) à des fins de calculs généralistes aussi couramment appelé GPGPU (General-Purpose computation on Graphics Processing Units). Ce choix a été réalisé du fait, entre autres, du coût réduit du matériel et de sa très grande puissance de calcul brute qui en fait une des architectures de parallélisation les plus accessibles du marché. Les résultats de l'étude de faisabilité étant particulièrement concluant, la parallélisation du calcul des champs a ensuite été intégrée à la PGMS. En parallèle, nous avons également mené des travaux d'optimisations pour améliorer les performances séquentielles de la PGMS. Le résultat de ces travaux est une augmentation de la vitesse d'exécution d'un facteur 18,12x sur les simulations les plus longues (passant de 16 minutes pour la simulation non optimisée utilisant un seul cœur CPU à 53 secondes pour la version optimisée utilisant toujours un seul cœur CPU mais aussi un GPU GTX500). L'autre aspect majeur traité dans ces travaux a été d'améliorer les performances algorithmiques pour la simulation d'automates cellulaires en trois dimensions. En effet, ces derniers permettent aussi bien de simuler des comportements biologiques que d'implémenter des mécanismes de modélisation tels que les interactions multi-échelles. Le travail de recherche s'est essentiellement effectué sur des propositions algorithmiques originales afin d'améliorer les simulations réalisées par IBC sur la PGMS. L'accélération logicielle, à travers l'implémentation de l'algorithme Hash‑Life en trois dimensions, et la parallélisation à l'aide de GPGPU ont été étudiées de façon concomitante et ont abouti à des gains très significatifs en temps de calcul.
|
253 |
Parallel Sorting on the Heterogeneous AMD Fusion Accelerated Processing UnitDelorme, Michael Christopher 18 March 2013 (has links)
We explore efficient parallel radix sort for the AMD Fusion Accelerated Processing Unit (APU). Two challenges arise: efficiently partitioning data between the CPU and GPU and the allocation of data in memory regions. Our coarse-grained implementation utilizes both the GPU and CPU by sharing data at the begining and end of the sort. Our fine-grained implementation utilizes the APU’s integrated memory system to share data throughout the sort. Both these implementations outperform the current state of the art GPU radix sort from NVIDIA. We therefore demonstrate that the CPU can be efficiently used to speed up radix sort on the APU.
Our fine-grained implementation slightly outperforms our coarse-grained implementation. This demonstrates the benefit of the APU’s integrated architecture. This performance benefit is hindered by limitations in the APU’s architecture and programming model. We believe that the performance benefits will increase once these limitations are addressed in future generations of the APU.
|
254 |
An efficient GPU-based implementation of recursive linear filters and its application to realistic real-time re-synthesis for interactive virtual worlds / Uma implementação eficiente de filtros lineares recursivos e sua aplicação a re-síntese realistica em tempo real para mundos virtuais interativosTrebien, Fernando January 2009 (has links)
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.
|
255 |
Novos mapas simpléticos para integração de sistemas hamiltonianos com múltiplas escalas de tempo : enfoque em sistemas gravitacionais de N-corposFerrari, Guilherme Gonçalves January 2015 (has links)
Mapas simpléticos são bem conhecidos por preservarem o volume do espaço de fase em dinâmica Hamiltoniana e são particularmente apropriados para problemas que requerem longos tempos de integração. Nesta tese nós desenvolvemos abordagens baseadas em mapas simpléticos para o acoplamento de multi sub-sistemas/domínios astrofísicos/códigos de simulação, para integração eficiente de sistemas de N-corpos auto-gravitantes com grandes variações nas escalas de tempo características. Nós estabelecemos uma família de 48 novos mapas simpléticos baseados numa separação Hamiltoniana recursiva, que permite que o acoplamento ocorra de uma maneira hierárquica, contemplando assim todas as escalas de tempo das interações envolvidas. Nossa formulação é geral o suficiente para permitir que tal método seja utilizado como receita para combinar diferentes fenômenos físicos, que podem ser modelados independentemente por códigos especializados. Nós introduzimos também uma separação Hamiltoniana baseada em Hamiltonianos de Kepler, para resolver o problema gravitacional geral de N-corpos como uma composição de N2 problemas de 2-corpos. O método resultante é exato para cada problema de 2-corpos individual e produz resultados rápidos e precisos para sistemas de N-corpos quase- Keplerianos, como sistemas planetários ou um aglomerado de estrelas que orbita um buraco-negro supermassivo. O método é também apropriado para integração de sistemas de N-corpos com hierarquias intrínsecas, como um aglomerados de estrelas com binárias compactas. Nós apresentamos a implementação dos algoritmos mencionados e descrevemos o nosso código tupan, que está publicamente disponível na seguinte url: https://github.com/ggf84/tupan. / Symplectic maps are well know for preserving the phase space volume in Hamiltonian dynamics and are particularly suited for problems that require long integration times. In this thesis we develop approaches based on symplectic maps for the coupling of multi sub-systems/astrophysics domains/simulation codes for efficient integration of self-gravitating N-body systems with large variation in characteristic time-scales. We establish a family of 48 new symplectic maps based on a recursive Hamiltonian splitting, which allow the coupling to occur in a hierarchical manner, thus contemplating all time-scales of the involved interactions. Our formulation is general enough to allow that such method be used as a recipe to combine different physical phenomena which can be modeled independently by specialized simulation codes. We also introduce a Keplerian-based Hamiltonian splitting for solving the general gravitational Nbody problem as a composition of N2 2-body problems. The resulting method is precise for each individual 2-body solution and produces quick and accurate results for near-Keplerian N-body systems, like planetary systems or a cluster of stars that orbit a supermassive black-hole. The method is also suitable for integration of N-body systems with intrinsic hierarchies, like a star cluster with compact binaries. We present the implementation of the mentioned algorithms and describe our code tupan, which is publicly available on the following url: https://github.com/ggf84/tupan.
|
256 |
Balanceamento de carga dinâmico em aglomerados de GPUsSant'Ana, Luis Felipe January 2015 (has links)
Orientador: Prof. Dr. Márcio Katsumi Oikawa / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2015. / Este trabalho utiliza conceitos de Séries Históricas e Método dos Mínimos Quadrados
para realização de estudo evolutivo da Doença de Alzheimer. Com estas técnicas, foram
elaboradas a apresentação do panorama atual de um grupo de pacientes e, posteriormente,
a previsão de resultados a partir de dados históricos obtidos do exame neuropsicológico
denonimado Mini Exame do Estado Mental. Foram geradas trajetórias representadas pela
unidade tempo (em anos) de cada um dos pacientes contidos na base de dados. Os resultados sugerem que a modelagem por meio de Séries Históricas e Método dos Mínimos
Quadrados pode ser considerada adequada para o acompanhamento e previsão da progressão/estagnação da Doença de Alzheimer. / This study attempted of the concepts of Time Series and the Least Squares Method for
accomplishment of evolutive study of Alzheimer¿s disease. With these techniques were
development the presentation of the current situation of a group of patients and subsequently the prediction from historical data results of neuropsychological test called Mini Mental State Examination. For each of the patients in the database, it was generated
trajectories represented by unit time (in years). The findings suggests that the modeling
using Time Series associated with the Least Squares Method can be considered suitable
for monitoring and prediction of the progression/stagnation of the Alzheimer¿s disease.
|
257 |
An efficient GPU-based implementation of recursive linear filters and its application to realistic real-time re-synthesis for interactive virtual worlds / Uma implementação eficiente de filtros lineares recursivos e sua aplicação a re-síntese realistica em tempo real para mundos virtuais interativosTrebien, Fernando January 2009 (has links)
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.
|
258 |
Novos mapas simpléticos para integração de sistemas hamiltonianos com múltiplas escalas de tempo : enfoque em sistemas gravitacionais de N-corposFerrari, Guilherme Gonçalves January 2015 (has links)
Mapas simpléticos são bem conhecidos por preservarem o volume do espaço de fase em dinâmica Hamiltoniana e são particularmente apropriados para problemas que requerem longos tempos de integração. Nesta tese nós desenvolvemos abordagens baseadas em mapas simpléticos para o acoplamento de multi sub-sistemas/domínios astrofísicos/códigos de simulação, para integração eficiente de sistemas de N-corpos auto-gravitantes com grandes variações nas escalas de tempo características. Nós estabelecemos uma família de 48 novos mapas simpléticos baseados numa separação Hamiltoniana recursiva, que permite que o acoplamento ocorra de uma maneira hierárquica, contemplando assim todas as escalas de tempo das interações envolvidas. Nossa formulação é geral o suficiente para permitir que tal método seja utilizado como receita para combinar diferentes fenômenos físicos, que podem ser modelados independentemente por códigos especializados. Nós introduzimos também uma separação Hamiltoniana baseada em Hamiltonianos de Kepler, para resolver o problema gravitacional geral de N-corpos como uma composição de N2 problemas de 2-corpos. O método resultante é exato para cada problema de 2-corpos individual e produz resultados rápidos e precisos para sistemas de N-corpos quase- Keplerianos, como sistemas planetários ou um aglomerado de estrelas que orbita um buraco-negro supermassivo. O método é também apropriado para integração de sistemas de N-corpos com hierarquias intrínsecas, como um aglomerados de estrelas com binárias compactas. Nós apresentamos a implementação dos algoritmos mencionados e descrevemos o nosso código tupan, que está publicamente disponível na seguinte url: https://github.com/ggf84/tupan. / Symplectic maps are well know for preserving the phase space volume in Hamiltonian dynamics and are particularly suited for problems that require long integration times. In this thesis we develop approaches based on symplectic maps for the coupling of multi sub-systems/astrophysics domains/simulation codes for efficient integration of self-gravitating N-body systems with large variation in characteristic time-scales. We establish a family of 48 new symplectic maps based on a recursive Hamiltonian splitting, which allow the coupling to occur in a hierarchical manner, thus contemplating all time-scales of the involved interactions. Our formulation is general enough to allow that such method be used as a recipe to combine different physical phenomena which can be modeled independently by specialized simulation codes. We also introduce a Keplerian-based Hamiltonian splitting for solving the general gravitational Nbody problem as a composition of N2 2-body problems. The resulting method is precise for each individual 2-body solution and produces quick and accurate results for near-Keplerian N-body systems, like planetary systems or a cluster of stars that orbit a supermassive black-hole. The method is also suitable for integration of N-body systems with intrinsic hierarchies, like a star cluster with compact binaries. We present the implementation of the mentioned algorithms and describe our code tupan, which is publicly available on the following url: https://github.com/ggf84/tupan.
|
259 |
Novos mapas simpléticos para integração de sistemas hamiltonianos com múltiplas escalas de tempo : enfoque em sistemas gravitacionais de N-corposFerrari, Guilherme Gonçalves January 2015 (has links)
Mapas simpléticos são bem conhecidos por preservarem o volume do espaço de fase em dinâmica Hamiltoniana e são particularmente apropriados para problemas que requerem longos tempos de integração. Nesta tese nós desenvolvemos abordagens baseadas em mapas simpléticos para o acoplamento de multi sub-sistemas/domínios astrofísicos/códigos de simulação, para integração eficiente de sistemas de N-corpos auto-gravitantes com grandes variações nas escalas de tempo características. Nós estabelecemos uma família de 48 novos mapas simpléticos baseados numa separação Hamiltoniana recursiva, que permite que o acoplamento ocorra de uma maneira hierárquica, contemplando assim todas as escalas de tempo das interações envolvidas. Nossa formulação é geral o suficiente para permitir que tal método seja utilizado como receita para combinar diferentes fenômenos físicos, que podem ser modelados independentemente por códigos especializados. Nós introduzimos também uma separação Hamiltoniana baseada em Hamiltonianos de Kepler, para resolver o problema gravitacional geral de N-corpos como uma composição de N2 problemas de 2-corpos. O método resultante é exato para cada problema de 2-corpos individual e produz resultados rápidos e precisos para sistemas de N-corpos quase- Keplerianos, como sistemas planetários ou um aglomerado de estrelas que orbita um buraco-negro supermassivo. O método é também apropriado para integração de sistemas de N-corpos com hierarquias intrínsecas, como um aglomerados de estrelas com binárias compactas. Nós apresentamos a implementação dos algoritmos mencionados e descrevemos o nosso código tupan, que está publicamente disponível na seguinte url: https://github.com/ggf84/tupan. / Symplectic maps are well know for preserving the phase space volume in Hamiltonian dynamics and are particularly suited for problems that require long integration times. In this thesis we develop approaches based on symplectic maps for the coupling of multi sub-systems/astrophysics domains/simulation codes for efficient integration of self-gravitating N-body systems with large variation in characteristic time-scales. We establish a family of 48 new symplectic maps based on a recursive Hamiltonian splitting, which allow the coupling to occur in a hierarchical manner, thus contemplating all time-scales of the involved interactions. Our formulation is general enough to allow that such method be used as a recipe to combine different physical phenomena which can be modeled independently by specialized simulation codes. We also introduce a Keplerian-based Hamiltonian splitting for solving the general gravitational Nbody problem as a composition of N2 2-body problems. The resulting method is precise for each individual 2-body solution and produces quick and accurate results for near-Keplerian N-body systems, like planetary systems or a cluster of stars that orbit a supermassive black-hole. The method is also suitable for integration of N-body systems with intrinsic hierarchies, like a star cluster with compact binaries. We present the implementation of the mentioned algorithms and describe our code tupan, which is publicly available on the following url: https://github.com/ggf84/tupan.
|
260 |
An efficient GPU-based implementation of recursive linear filters and its application to realistic real-time re-synthesis for interactive virtual worlds / Uma implementação eficiente de filtros lineares recursivos e sua aplicação a re-síntese realistica em tempo real para mundos virtuais interativosTrebien, Fernando January 2009 (has links)
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.
|
Page generated in 0.0397 seconds