A análise em tempo real de pares de imagens estereoscópicas para extração de características dimensionais da cena tem apresentado crescente interesse, possibilitando robusta navegação robótica e identificação de objetos em cenários dinâmicos. A presente dissertação propõe um método que emprega a análise pixel a pixel e observação de janelas, em pares de imagens estereoscópicas, para extração de denso mapa de disparidades. A arquitetura de processamento proposta é única em sua constituição, misturando elementos de processamento concorrente e seqüencial. O algoritmo estrutura-se em processamento pipeline, permitindo sua implementação em dispositivos de lógica programável e obtenção de resultados em tempo real. / Real-time analysis of stereo images for extraction of dimensional features has been focus of great interest, providing means for autonomous robot navigation and identification of objects in dynamic environments. This work describes a method based in pixel-to-pixel and windows based matching analysis, in stereo images, for constructing dense disparity maps. The proposed processing structure is unique, mixing concurrent and sequential elements. Pipelines structure is employed, targeting implementation in FPGA devices and enabling real-time results.

A análise em tempo real de pares de imagens estereoscópicas para extração de características dimensionais da cena tem apresentado crescente interesse, possibilitando robusta navegação robótica e identificação de objetos em cenários dinâmicos. A presente dissertação propõe um método que emprega a análise pixel a pixel e observação de janelas, em pares de imagens estereoscópicas, para extração de denso mapa de disparidades. A arquitetura de processamento proposta é única em sua constituição, misturando elementos de processamento concorrente e seqüencial. O algoritmo estrutura-se em processamento pipeline, permitindo sua implementação em dispositivos de lógica programável e obtenção de resultados em tempo real. / Real-time analysis of stereo images for extraction of dimensional features has been focus of great interest, providing means for autonomous robot navigation and identification of objects in dynamic environments. This work describes a method based in pixel-to-pixel and windows based matching analysis, in stereo images, for constructing dense disparity maps. The proposed processing structure is unique, mixing concurrent and sequential elements. Pipelines structure is employed, targeting implementation in FPGA devices and enabling real-time results.

No description available.

Η παρούσα ειδική ερευνητική εργασία εκπονήθηκε στα πλαίσια του Διατμηματικού Προγράμματος Μεταπτυχιακών Σπουδών στην “Ηλεκτρονική και Επεξεργασία της Πληροφορίας”, στο Τμήμα Φυσικής του Πανεπιστημίου Πατρών. Αντικείμενο της παρούσας εργασίας είναι η “Υλοποίηση σε FPGA του περιγραφέα HOG για ανίχνευση ανθρώπων σε εικόνες και βίντεο”. Το πρώτο κεφάλαιο αποτελεί μια εισαγωγή στις βασικότερες έννοιες που χρησιμοποιούνται στην παρούσα εργασία. Περιγράφεται επίσης η αναπτυξιακή πλακέτα που χρησιμοποιήθηκε καθώς και τα επί μέρους στοιχεία που τη συνθέτουν. Τέλος γίνεται μια συνοπτική αναφορά σε εργασίες με παρόμοιο αντικείμενο, οι οποίες με επηρέασαν στο σχεδιασμό και την υλοποίηση του συστήματός μου. Στο δεύτερο κεφάλαιο αναλύεται ο περιγραφέας Ιστογραμμάτων Προσανατολισμού της Βάθμωσης ή όπως είναι ευρύτερα γνωστός Histograms of Oriented Gradient Descriptor. Παρουσιάζονται τα βήματα όπως περιγράφονται στην εργασία των Dalal&Triggs[4] και οι βέλτιστες τιμές των παραμέτρων του περιγραφέα. Στο τρίτο κεφάλαιο ακολουθώντας τα βήματα του δευτέρου κεφαλαίου, παρουσιάζεται η διαδικασία υλοποίησης του περιγραφέα στο Matlab. Εκτός της υλοποίησης έγινε και μια προεργασία για τη μεταφορά του σε γλώσσα περιγραφής υλικού. Η προεργασία αυτή περιλαμβάνει απλοποιήσεις και τροποποιήσεις με σκοπό να μειωθεί το υπολογιστικό κόστος. Τέλος παρουσιάζονται τα αποτελέσματα δοκιμών της απόδοσης του περιγραφέα για τις διάφορες απλοποιήσεις. Στο τέταρτο κεφάλαιο γίνεται μια μικρή αναφορά στους ταξινομητές. Περιγράφονται οι ταξινομητές που δοκιμάστηκαν στην παρούσα εργασία ως προς συγκεκριμένα χαρακτηριστικά τους καθώς και την υπολογιστική τους πολυπλοκότητα για την συγκεκριμένη εφαρμογή. Το πέμπτο και τελευταίο κεφάλαιο περιλαμβάνει την περιγραφή της υλοποίησης σε VHDL. Αναλύονται τα επί μέρους κυκλώματα και όπου κρίθηκε αναγκαίο χρησιμοποιήθηκαν σχήματα ή πίνακες. Σε κάποιες περιπτώσεις δίνονται και οι κυματομορφές των κυκλωμάτων. / This thesis took place within the frame work of the Interdeparmental Master’s Program in “Electronics and Information Processing”, at the Department of Physics of University of Patras. The objective of this work is the implementation in FPGA of the HOG descriptor for the detection of people, images and videos. The first chapter is an introduction about the basic concepts, which are used across the manuscript. (Additional descriptions concern the development board which was used as well as the individual parts that compose it.) In the end, there is a brief reference to past projects focusing on similar objectives, which influenced the design and the implementation of my system. The second chapter concerns the presentation and discussion of the Histograms of Oriented Gradient descriptor. The steps of the procedure and the best parameter values of the descriptor are presented in a similar way as they are described in the paper of Dalal and Triggs. In the third chapter, following the steps of the previous one, the focus shifts to the descriptor’s implementation procedure in Matlab. Besides the implementation, there is a preparation for the transference of the descriptor in a Hardware Description Language. This preparation includes simplifications and modifications aiming at the reduction of the computational cost. Finally, we see the tests’ results of the descriptor’s performance concerning the various simplifications. The fourth chapter is a partial reference to the classifiers. The description is about the classifiers that were used in the present work with respect to their features and their computational complexity of this particular application. The fifth and final chapter refers to the description of the implementation in VHDL. There is an analysis of the partial circuits and, when necessary, shapes and tables were used. In some cases, the waveforms of the circuits are being presented.

A presente dissertação examina um método de determinação da conectividade cerebral cujo uso vem se tornando popular nos últimos anos, o partial direct coherence (PDC), que se destaca dentre outros métodos por possibilitar a verificação das relações imediatas de sinais multivariados. Este método representa a conectividade cerebral no domínio da frequência e tem íntima relação com a noção de \"causalidade\" de Granger (GRANGER, 1969), que possibilita quantificar a influência mútua entre séries temporais observadas. De um ponto de vista computacional, o referido método faz uso de modelos de séries temporais que hoje têm implementação bastante eficiente em termos de algoritmos off-line, mas cujo sucesso depende da presunção de estacionariedade dos dados, fato que é somente verdadeiro em trechos relativamente curtos de sinais de origem cerebral, como no caso do EEG (Eletroencefalograma). O objetivo deste trabalho é criar um sistema que calcule o PDC, continuamente, em tempo real e que possua a mesma precisão do método off-line, além de ser uma plataforma de estudos para implementações e testes de métodos de determinação da conectividade neural em tempo real. A plataforma desenvolvida é modular, incentivando futuros trabalhos na mesma, e mostrouse eficaz quanto a precisão numérica dos resultados do cálculo do PDC. As características de tempo real foram atingidas com algumas restrições, que dependem da configuração do usuário e do número de canais que um sinal possui. / This thesis examines a method of determination of brain connectivity whose use becomes popular in recent years, the partial direct coherence (PDC) that stands out in comparison with other methods for making possible the verification of immediate relations of multivariate signal. This method represents the brain connectivity in the frequency domain and has a close relationship with the notion of Granger causality (GRANGER, 1969) that makes it possible to quantify the mutual influence between observed time series. From a computational perspective, the above method makes use of time series models, which today has very efficient implementation in terms of off-line algorithm, but whose success depends on presume that the data is stationary, a fact that is only true in relatively short stretches of cerebral signals, especially in the case of EEG. The objective of this thesis is to create a system that calculates the PDC continuously and in real time maintaining the same precision of the off-line method. Furthermore being a research platform for implementations and tests of new methods for determining neural connectivity in real time. The developed platform is modular encouraging future work on it, and was effective in the numerical accuracy of the PDC calculation results. The real time characteristics were achieved with some restrictions that depend of the user configuration and the number of channels that the signal has.

La quête de performance a été une constante à travers l’histoire des systèmes informatiques. Il y a plus d’une décennie maintenant, le modèle de traitement séquentiel montrait ses premiers signes d’épuisement pour satisfaire les exigences de performance. Les barrières du calcul séquentiel ont poussé à un changement de paradigme et ont établi le traitement parallèle comme standard dans les systèmes informatiques modernes. Avec l’adoption généralisée d’ordinateurs parallèles, de nombreux algorithmes et applications ont été développés pour s’adapter à ces nouvelles architectures. Cependant, dans des applications non conventionnelles, avec des exigences d’interactivité et de temps réel, la parallélisation efficace est encore un défi majeur. L’exigence de performance en temps réel apparaît, par exemple, dans les simulations interactives où le système doit prendre en compte l’entrée de l’utilisateur dans une itération de calcul de la boucle de simulation. Le même type de contrainte apparaît dans les applications d’analyse de données en continu. Par exemple, lorsque des donnes issues de capteurs de trafic ou de messages de réseaux sociaux sont produites en flux continu, le système d’analyse doit être capable de traiter ces données à la volée rapidement sur ce flux tout en conservant un budget de mémoire contrôlé La caractéristique dynamique des données soulève plusieurs problèmes de performance tel que la décomposition du problème pour le traitement en parallèle et la maintenance de la localité mémoire pour une utilisation efficace du cache. Les optimisations classiques qui reposent sur des modèles pré-calculés ou sur l’indexation statique des données ne conduisent pas aux performances souhaitées. Dans cette thèse, nous abordons les problèmes dépendants de données sur deux applications différentes : la première dans le domaine de la simulation physique interactive et la seconde sur l’analyse des données en continu. Pour le problème de simulation, nous présentons un algorithme GPU parallèle pour calculer les multiples plus courts chemins et des diagrammes de Voronoi sur un graphe en forme de grille. Pour le problème d’analyse de données en continu, nous présentons une structure de données parallélisable, basée sur des Packed Memory Arrays, pour indexer des données dynamiques géo-référencées tout en conservant une bonne localité de mémoire. / A busca por desempenho tem sido uma constante na história dos sistemas computacionais. Ha mais de uma década, o modelo de processamento sequencial já mostrava seus primeiro sinais de exaustão pare suprir a crescente exigência por performance. Houveram "barreiras"para a computação sequencial que levaram a uma mudança de paradigma e estabeleceram o processamento paralelo como padrão nos sistemas computacionais modernos. Com a adoção generalizada de computadores paralelos, novos algoritmos foram desenvolvidos e aplicações reprojetadas para se adequar às características dessas novas arquiteturas. No entanto, em aplicações menos convencionais, com características de interatividade e tempo real, alcançar paralelizações eficientes ainda representa um grande desafio. O requisito por desempenho de tempo real apresenta-se, por exemplo, em simulações interativas onde o sistema deve ser capaz de reagir às entradas do usuário dentro do tempo de uma iteração da simulação. O mesmo tipo de exigência aparece em aplicações de monitoramento de fluxos contínuos de dados (streams). Por exemplo, quando dados provenientes de sensores de tráfego ou postagens em redes sociais são produzidos em fluxo contínuo, o sistema de análise on-line deve ser capaz de processar essas informações em tempo real e ao mesmo tempo manter um consumo de memória controlada A natureza dinâmica desses dados traz diversos problemas de performance, tais como a decomposição do problema para processamento em paralelo e a manutenção da localidade de dados para uma utilização eficiente da memória cache. As estratégias de otimização tradicionais, que dependem de modelos pré-computados ou de índices estáticos sobre os dados, não atendem às exigências de performance necessárias nesses cenários. Nesta tese, abordamos os problemas dependentes de dados em dois contextos diferentes: um na área de simulações baseada em física e outro em análise de dados em fluxo contínuo. Para o problema de simulação, apresentamos um algoritmo paralelo, em GPU, para computar múltiplos caminhos mínimos e diagramas de Voronoi em um grafo com topologia de grade. Para o problema de análise de fluxos de dados, apresentamos uma estrutura de dados paralelizável, baseada em Packed Memory Arrays, para indexar dados dinâmicos geo-localizados ao passo que mantém uma boa localidade de memória. / The quest for performance has been a constant through the history of computing systems. It has been more than a decade now since the sequential processing model had shown its first signs of exhaustion to keep performance improvements. Walls to the sequential computation pushed a paradigm shift and established the parallel processing as the standard in modern computing systems. With the widespread adoption of parallel computers, many algorithms and applications have been ported to fit these new architectures. However, in unconventional applications, with interactivity and real-time requirements, achieving efficient parallelizations is still a major challenge. Real-time performance requirement shows up, for instance, in user-interactive simulations where the system must be able to react to the user’s input within a computation time-step of the simulation loop. The same kind of constraint appears in streaming data monitoring applications. For instance, when an external source of data, such as traffic sensors or social media posts, provides a continuous flow of information to be consumed by an online analysis system. The consumer system has to keep a controlled memory budget and deliver a fast processed information about the stream Common optimizations relying on pre-computed models or static index of data are not possible in these highly dynamic scenarios. The dynamic nature of the data brings up several performance issues originated from the problem decomposition for parallel processing and from the data locality maintenance for efficient cache utilization. In this thesis we address data-dependent problems on two different applications: one on physically based simulations and another on streaming data analysis. To deal with the simulation problem, we present a parallel GPU algorithm for computing multiple shortest paths and Voronoi diagrams on a grid-like graph. Our contribution to the streaming data analysis problem is a parallelizable data structure, based on packed memory arrays, for indexing dynamic geo-located data while keeping good memory locality.

Timing of ordering of inventory items is of very great importance in Materials Requirement Planning. Uncertainties in timing can have an adverse effect on the system performance. Most often the lead time variation contribute to timing uncertainties; and their effects are reflected in added costs. Lead time error effects are investigated in this thesis. The study attempts to estimate the effects through some relevant costs, and their variations across the lot sizing rules. The hypotheses for this study are 1) Between any two lot sizing rules, there will be a significant difference in error coats due to combined effect of purchased lead time error and manufacturing lead time errors; 2) Relative cost performance of lot sizing rules in MRP is influenced by the lead time errors; 3) There will be a difference in error cost between lot for l o t rule and least total cost rule even with single source of lead time variation. To carry out the study a MRP programme was developed, in FORTRAN 77 with provisions to include the lot sizing rules while exploding the structure. The lot sizing rules used in the study are Lot for Lot, Silver and Meal heuristics, Wagner-Whitin algorithm, Least total cost, Least unit cost and Part Period balancing. A simulation model is developed using GPSS/PC, to test the hypotheses. An hypothetical production situation with three end items, each with a different product structure is designed. In addition, a master production schedule and a job shop are also structured. Appropriate distributions are assumed for both manufacturing lead times and purchase lead times. These provide the stochastic variables in the simulation experiments. A series of experiments were carried out with the model to investigate into the variations of costs amongst lot sizing rules. Results of the simulation experiments prove that there are costs associated with lead time errors in MRP. These error costs vary significantly with different lot sizing rules. It is also found that the resultant error costs vary significantly even with a single source of lead time variation. Least unit cost rule gives the beat performance having least error costs. Lot for Lot rule has shown the worst performance amongst the lot sizing rules considered. Other interesting results have emerged out of the study.

A presente dissertação examina um método de determinação da conectividade cerebral cujo uso vem se tornando popular nos últimos anos, o partial direct coherence (PDC), que se destaca dentre outros métodos por possibilitar a verificação das relações imediatas de sinais multivariados. Este método representa a conectividade cerebral no domínio da frequência e tem íntima relação com a noção de \"causalidade\" de Granger (GRANGER, 1969), que possibilita quantificar a influência mútua entre séries temporais observadas. De um ponto de vista computacional, o referido método faz uso de modelos de séries temporais que hoje têm implementação bastante eficiente em termos de algoritmos off-line, mas cujo sucesso depende da presunção de estacionariedade dos dados, fato que é somente verdadeiro em trechos relativamente curtos de sinais de origem cerebral, como no caso do EEG (Eletroencefalograma). O objetivo deste trabalho é criar um sistema que calcule o PDC, continuamente, em tempo real e que possua a mesma precisão do método off-line, além de ser uma plataforma de estudos para implementações e testes de métodos de determinação da conectividade neural em tempo real. A plataforma desenvolvida é modular, incentivando futuros trabalhos na mesma, e mostrouse eficaz quanto a precisão numérica dos resultados do cálculo do PDC. As características de tempo real foram atingidas com algumas restrições, que dependem da configuração do usuário e do número de canais que um sinal possui. / This thesis examines a method of determination of brain connectivity whose use becomes popular in recent years, the partial direct coherence (PDC) that stands out in comparison with other methods for making possible the verification of immediate relations of multivariate signal. This method represents the brain connectivity in the frequency domain and has a close relationship with the notion of Granger causality (GRANGER, 1969) that makes it possible to quantify the mutual influence between observed time series. From a computational perspective, the above method makes use of time series models, which today has very efficient implementation in terms of off-line algorithm, but whose success depends on presume that the data is stationary, a fact that is only true in relatively short stretches of cerebral signals, especially in the case of EEG. The objective of this thesis is to create a system that calculates the PDC continuously and in real time maintaining the same precision of the off-line method. Furthermore being a research platform for implementations and tests of new methods for determining neural connectivity in real time. The developed platform is modular encouraging future work on it, and was effective in the numerical accuracy of the PDC calculation results. The real time characteristics were achieved with some restrictions that depend of the user configuration and the number of channels that the signal has.

La quête de performance a été une constante à travers l’histoire des systèmes informatiques. Il y a plus d’une décennie maintenant, le modèle de traitement séquentiel montrait ses premiers signes d’épuisement pour satisfaire les exigences de performance. Les barrières du calcul séquentiel ont poussé à un changement de paradigme et ont établi le traitement parallèle comme standard dans les systèmes informatiques modernes. Avec l’adoption généralisée d’ordinateurs parallèles, de nombreux algorithmes et applications ont été développés pour s’adapter à ces nouvelles architectures. Cependant, dans des applications non conventionnelles, avec des exigences d’interactivité et de temps réel, la parallélisation efficace est encore un défi majeur. L’exigence de performance en temps réel apparaît, par exemple, dans les simulations interactives où le système doit prendre en compte l’entrée de l’utilisateur dans une itération de calcul de la boucle de simulation. Le même type de contrainte apparaît dans les applications d’analyse de données en continu. Par exemple, lorsque des donnes issues de capteurs de trafic ou de messages de réseaux sociaux sont produites en flux continu, le système d’analyse doit être capable de traiter ces données à la volée rapidement sur ce flux tout en conservant un budget de mémoire contrôlé La caractéristique dynamique des données soulève plusieurs problèmes de performance tel que la décomposition du problème pour le traitement en parallèle et la maintenance de la localité mémoire pour une utilisation efficace du cache. Les optimisations classiques qui reposent sur des modèles pré-calculés ou sur l’indexation statique des données ne conduisent pas aux performances souhaitées. Dans cette thèse, nous abordons les problèmes dépendants de données sur deux applications différentes : la première dans le domaine de la simulation physique interactive et la seconde sur l’analyse des données en continu. Pour le problème de simulation, nous présentons un algorithme GPU parallèle pour calculer les multiples plus courts chemins et des diagrammes de Voronoi sur un graphe en forme de grille. Pour le problème d’analyse de données en continu, nous présentons une structure de données parallélisable, basée sur des Packed Memory Arrays, pour indexer des données dynamiques géo-référencées tout en conservant une bonne localité de mémoire. / A busca por desempenho tem sido uma constante na história dos sistemas computacionais. Ha mais de uma década, o modelo de processamento sequencial já mostrava seus primeiro sinais de exaustão pare suprir a crescente exigência por performance. Houveram "barreiras"para a computação sequencial que levaram a uma mudança de paradigma e estabeleceram o processamento paralelo como padrão nos sistemas computacionais modernos. Com a adoção generalizada de computadores paralelos, novos algoritmos foram desenvolvidos e aplicações reprojetadas para se adequar às características dessas novas arquiteturas. No entanto, em aplicações menos convencionais, com características de interatividade e tempo real, alcançar paralelizações eficientes ainda representa um grande desafio. O requisito por desempenho de tempo real apresenta-se, por exemplo, em simulações interativas onde o sistema deve ser capaz de reagir às entradas do usuário dentro do tempo de uma iteração da simulação. O mesmo tipo de exigência aparece em aplicações de monitoramento de fluxos contínuos de dados (streams). Por exemplo, quando dados provenientes de sensores de tráfego ou postagens em redes sociais são produzidos em fluxo contínuo, o sistema de análise on-line deve ser capaz de processar essas informações em tempo real e ao mesmo tempo manter um consumo de memória controlada A natureza dinâmica desses dados traz diversos problemas de performance, tais como a decomposição do problema para processamento em paralelo e a manutenção da localidade de dados para uma utilização eficiente da memória cache. As estratégias de otimização tradicionais, que dependem de modelos pré-computados ou de índices estáticos sobre os dados, não atendem às exigências de performance necessárias nesses cenários. Nesta tese, abordamos os problemas dependentes de dados em dois contextos diferentes: um na área de simulações baseada em física e outro em análise de dados em fluxo contínuo. Para o problema de simulação, apresentamos um algoritmo paralelo, em GPU, para computar múltiplos caminhos mínimos e diagramas de Voronoi em um grafo com topologia de grade. Para o problema de análise de fluxos de dados, apresentamos uma estrutura de dados paralelizável, baseada em Packed Memory Arrays, para indexar dados dinâmicos geo-localizados ao passo que mantém uma boa localidade de memória. / The quest for performance has been a constant through the history of computing systems. It has been more than a decade now since the sequential processing model had shown its first signs of exhaustion to keep performance improvements. Walls to the sequential computation pushed a paradigm shift and established the parallel processing as the standard in modern computing systems. With the widespread adoption of parallel computers, many algorithms and applications have been ported to fit these new architectures. However, in unconventional applications, with interactivity and real-time requirements, achieving efficient parallelizations is still a major challenge. Real-time performance requirement shows up, for instance, in user-interactive simulations where the system must be able to react to the user’s input within a computation time-step of the simulation loop. The same kind of constraint appears in streaming data monitoring applications. For instance, when an external source of data, such as traffic sensors or social media posts, provides a continuous flow of information to be consumed by an online analysis system. The consumer system has to keep a controlled memory budget and deliver a fast processed information about the stream Common optimizations relying on pre-computed models or static index of data are not possible in these highly dynamic scenarios. The dynamic nature of the data brings up several performance issues originated from the problem decomposition for parallel processing and from the data locality maintenance for efficient cache utilization. In this thesis we address data-dependent problems on two different applications: one on physically based simulations and another on streaming data analysis. To deal with the simulation problem, we present a parallel GPU algorithm for computing multiple shortest paths and Voronoi diagrams on a grid-like graph. Our contribution to the streaming data analysis problem is a parallelizable data structure, based on packed memory arrays, for indexing dynamic geo-located data while keeping good memory locality.

La quête de performance a été une constante à travers l'histoire des systèmes informatiques.Il y a plus d'une décennie maintenant, le modèle de traitement séquentiel montrait ses premiers signes d'épuisement pour satisfaire les exigences de performance.Les barrières du calcul séquentiel ont poussé à un changement de paradigme et ont établi le traitement parallèle comme standard dans les systèmes informatiques modernes.Avec l'adoption généralisée d'ordinateurs parallèles, de nombreux algorithmes et applications ont été développés pour s'adapter à ces nouvelles architectures.Cependant, dans des applications non conventionnelles, avec des exigences d'interactivité et de temps réel, la parallélisation efficace est encore un défi majeur.L'exigence de performance en temps réel apparaît, par exemple, dans les simulations interactives où le système doit prendre en compte l'entrée de l'utilisateur dans une itération de calcul de la boucle de simulation.Le même type de contrainte apparaît dans les applications d'analyse de données en continu.Par exemple, lorsque des donnes issues de capteurs de trafic ou de messages de réseaux sociaux sont produites en flux continu, le système d'analyse doit être capable de traiter ces données à la volée rapidement sur ce flux tout en conservant un budget de mémoire contrôlé.La caractéristique dynamique des données soulève plusieurs problèmes de performance tel que la décomposition du problème pour le traitement en parallèle et la maintenance de la localité mémoire pour une utilisation efficace du cache.Les optimisations classiques qui reposent sur des modèles pré-calculés ou sur l'indexation statique des données ne conduisent pas aux performances souhaitées.Dans cette thèse, nous abordons les problèmes dépendants de données sur deux applications différentes: la première dans le domaine de la simulation physique interactive et la seconde sur l'analyse des données en continu.Pour le problème de simulation, nous présentons un algorithme GPU parallèle pour calculer les multiples plus courts chemins et des diagrammes de Voronoi sur un graphe en forme de grille.Pour le problème d'analyse de données en continu, nous présentons une structure de données parallélisable, basée sur des Packed Memory Arrays, pour indexer des données dynamiques géo-référencées tout en conservant une bonne localité de mémoire. / The quest for performance has been a constant through the history of computing systems. It has been more than a decade now since the sequential processing model had shown its first signs of exhaustion to keep performance improvements.Walls to the sequential computation pushed a paradigm shift and established the parallel processing as the standard in modern computing systems. With the widespread adoption of parallel computers, many algorithms and applications have been ported to fit these new architectures. However, in unconventional applications, with interactivity and real-time requirements, achieving efficient parallelizations is still a major challenge.Real-time performance requirement shows-up, for instance, in user-interactive simulations where the system must be able to react to the user's input within a computation time-step of the simulation loop. The same kind of constraint appears in streaming data monitoring applications. For instance, when an external source of data, such as traffic sensors or social media posts, provides a continuous flow of information to be consumed by an on-line analysis system. The consumer system has to keep a controlled memory budget and delivery fast processed information about the stream.Common optimizations relying on pre-computed models or static index of data are not possible in these highly dynamic scenarios. The dynamic nature of the data brings up several performance issues originated from the problem decomposition for parallel processing and from the data locality maintenance for efficient cache utilization.In this thesis we address data-dependent problems on two different application: one in physics-based simulation and other on streaming data analysis. To the simulation problem, we present a parallel GPU algorithm for computing multiple shortest paths and Voronoi diagrams on a grid-like graph. To the streaming data analysis problem we present a parallelizable data structure, based on packed memory arrays, for indexing dynamic geo-located data while keeping good memory locality.