[pt] Clusters (ou concentrações) de objetos móveis, como veículos e seres humanos, é um padrão de mobilidade relevante para muitas aplicações. Uma detecção rápida deste padrão e de sua evolução, por exemplo, se o cluster está encolhendo ou crescendo, é útil em vários cenários, como detectar a formação de engarrafamentos ou detectar uma rápida dispersão de pessoas em um show de música. A detecção on-line deste padrão é uma tarefa desafiadora porque requer algoritmos que sejam capazes de processar de forma contínua e eficiente o alto volume de dados enviados pelos objetos móveis em tempo hábil. Atualmente, a maioria das abordagens para a detecção destes clusters operam em lote. As localizações dos objetos móveis são armazenadas durante um determinado período e depois processadas em lote por uma rotina externa, atrasando o resultado da detecção do cluster até o final do período ou do próximo lote. Além disso, essas abordagem utilizam extensivamente estruturas de dados e operadores espaciais, o que pode ser problemático em cenários de grande fluxos de dados. Com intuito de abordar estes problemas, propomos nesta tese o DG2CEP, um algoritmo que combina o conhecido algoritmo de aglomeração por densidade (DBSCAN) com o paradigma de processamento de fluxos de dados (Complex Event Processing) para a detecção contínua e rápida dos aglomerados. Nossos experimentos com dados reais indicam que o DG2CEP é capaz de detectar a formação e dispersão de clusters rapidamente, em menos de alguns segundos, para milhares de objetos móveis. Além disso, os resultados obtidos indicam que o DG2CEP possui maior similaridade com DBSCAN do que abordagens baseadas em lote. / [en] Spatial concentrations (or spatial clusters) of moving objects, such as vehicles and humans, is a mobility pattern that is relevant to many applications. A fast detection of this pattern and its evolution, e.g., if the cluster is shrinking or growing, is useful in numerous scenarios, such as detecting the formation of traffic jams or detecting a fast dispersion of people in a music concert. An on-line detection of this pattern is a challenging task because it requires algorithms that are capable of continuously and efficiently processing the high volume of position updates in a timely manner. Currently, the majority of approaches for spatial cluster detection operate in batch mode, where moving objects location updates are recorded during time periods of certain length and then batch-processed by an external routine, thus delaying the result of the cluster detection until the end of the time period. Further, they extensively use spatial data structures and operators, which can be troublesome to maintain or parallelize in on-line scenarios. To address these issues, in this thesis we propose DG2CEP, an algorithm that combines the well-known density-based clustering algorithm DBSCAN with the data stream processing paradigm Complex Event Processing (CEP) to achieve continuous and timely detection of spatial clusters. Our experiments with real world data streams indicate that DG2CEP is able to detect the formation and dispersion of clusters with small latency while having a higher similarity to DBSCAN than batch-based approaches.

A growing search for alternative architectures and softwares have been noted in the last years. This search happens due to the advance of hardware technology and such advances must be complemented by innovations on design methodologies, test and verification techniques in order to use technology effectively. Alternative architectures and softwares, in general, explores the parallelism of applications, differently to Von Neumann model. Among high performance alternative architectures, there is the Dataflow Architecture. In this kind of architecture, the process of program execution is determined by data availability, thus the parallelism is intrinsic in these systems. The dataflow architectures become again a highlighted search area due to hardware advances, in particular, the advances of Reconfigurable Computing and Field Programmable Gate Arrays (FPGAs). ChipCflow projet is a tool for execution of algorithms using dynamic dataflow graph in FPGA. In this thesis, the development of a code conversion tool to generate aplications in a static dataflow architecture, is described. Also the ChipCflow project where the code conversion tool is part, is presented. The specification of algorithm to be converted is made in C language and converted to a hadware description language, respecting the proposed by ChipCflow project. The results are the proof of concept of converting a high-level language code for dataflow architecture to be used into a FPGA. / Existe uma crescente busca por softwares e arquiteturas alternativas. Essa busca acontece pois houveram avanços na tecnologia do hardware, e estes avanços devem ser complementados por inovações nas metodologias de projetos, testes e verificação para que haja um uso eficaz da tecnologia. Os software e arquiteturas alternativas, geralmente são modelos que exploram o paralelismo das aplicações, ao contrário do modelo de Von Neumann. Dentre as arquiteturas alternativas de alto desempenho, tem-se a arquitetura a fluxo de dados. Nesse tipo de arquitetura, o processo de execução de programas é determinado pela disponibilidade dos dados, logo o paralelismo está embutido na própria natureza do sistema. O modelo a fluxo de dados possui a vantagem de expressar o paralelismo de maneira intrínseca, eliminando a necessidade do programador explicitar em seu código os trechos onde deve haver paralelismo. As arquiteturas a fluxo de dados voltaram a ser uma área de pesquisa devido aos avanços do hardware, em particular, os avanços da Computação Reconfigurável e dos Field Programmable Gate Arrays (FPGAs).Nesta tese é descrita uma ferramenta de conversão de código que visa a geração de aplicações utilizando uma arquitetura a fluxo de dados estática. Também é descrito o projeto ChipCflow, cuja ferramenta de conversão de código, descrita nesta tese, é parte integrante. A especificação do algoritmo a ser convertido é feita em linguagem C e convertida para uma linguagem de descrição de hardware, respeitando o modelo proposto pelo ChipCflow. Os resultados alcançados visam a prova de conceito da conversão de código de uma linguagem de alto nível para uma arquitetura a fluxo de dados a ser configurada em FPGA.

Este trabalho descreve a prova de conceito de uma abordagem que utiliza o modelo de computação a fluxo de dados, inerentemente paralelo, associado ao modelo de computação reconfigurável parcial e dinamicamente, visando à obtenção de sistemas computacionais de alto desempenho. Mais especificamente, trata da obtenção de um modelo para o particionamento dos grafos a fluxo de dados dinâmicos e de um protocolo de comunicação entre suas partes, a fim de permitir a sua implementação em arquiteturas dinamicamente reconfiguráveis, em especial em FGPAs Virtex da Xilinx. Enquadra-se no contexto do projeto ChipCFlow, de escopo mais amplo, que pretende obter uma ferramenta para geração automática de descrição de hardware sintetizável, a partir de código em alto nível, escrito em linguagem C, fazendo uso da abordagem a fluxo de dados para extrair o paralelismo implícito nas aplicações originais. O modelo proposto é aplicado em um grafo a fluxo de dados dinâmico, e através de simulações sua viabilidade é discutida / This work describes the concept of an approach that uses data ow computational model, inherently parallel, associated with de reconfigurable computing model, partial and dynamic, in order to obtain high performance computational systems. More specifically, it is about a model to the partitioning and communication between partitioned sectors of a CDFG (Control Data Flow Graph) in order to map these graphs on a partial reconfiguration FPGA fabric, in special Virtex II/II-Pro from Xilinx. It is part of the ChipCFlow project, that has a bigger scope, and that aims to automatically obtain syntetisable hardware descriptions, from high level code written in C and, by using a data flow approach to extract implicit parallelism in original applications. The model obtained is extensively explained and applied to an example of CDFG, where by means of simulations its feasibility is discussed

Testing and debugging are key tasks during the development cycle. However, they are among the most expensive activities during the development process. To improve the productivity of developers during the debugging process various fault localization techniques have been proposed, being Spectrum-based Fault Localization (SFL), or Coverage-based Fault Localization (CBFL), one of the most promising. SFL techniques pinpoints program elements (e.g., statements, branches, and definition-use associations), sorting them by their suspiciousness. Heuristics are used to rank the most suspicious program elements which are then mapped into lines to be inspected by developers. Although data-flow spectra (definition-use associations) has been shown to perform better than control-flow spectra (statements and branches) to locate the bug site, the high overhead to collect data-flow spectra has prevented their use on industry-level code. A data-flow coverage tool was recently implemented presenting on average 38% run-time overhead for large programs. Such a fairly modest overhead motivates the study of SFL techniques using data-flow information in programs similar to those developed in the industry. To achieve such a goal, we implemented Jaguar (JAva coveraGe faUlt locAlization Ranking), a tool that employ control-flow and data-flow coverage on SFL techniques. The effectiveness and efficiency of both coverages are compared using 173 faulty versions with sizes varying from 10 to 96 KLOC. Ten known SFL heuristics to rank the most suspicious lines are utilized. The results show that the behavior of the heuristics are similar both to control- and data-flow coverage: Kulczynski2 and Mccon perform better for small number of lines investigated (from 5 to 30 lines) while Ochiai performs better when more lines are inspected (30 to 100 lines). The comparison between control- and data-flow coverages shows that data-flow locates more defects in the range of 10 to 50 inspected lines, being up to 22% more effective. Moreover, in the range of 20 and 100 lines, data-flow ranks the bug better than control-flow with statistical significance. However, data-flow is still more expensive than control-flow: it takes from 23% to 245% longer to obtain the most suspicious lines; on average data-flow is 129% more costly. Therefore, our results suggest that data-flow is more effective in locating faults because it tracks more relationships during the program execution. On the other hand, SFL techniques supported by data-flow coverage needs to be improved for practical use at industrial settings / Teste e depuração são tarefas importantes durante o ciclo de desenvolvimento de programas, no entanto, estão entre as atividades mais caras do processo de desenvolvimento. Diversas técnicas de localização de defeitos têm sido propostas a fim de melhorar a produtividade dos desenvolvedores durante o processo de depuração, sendo a localização de defeitos baseados em cobertura de código (Spectrum-based Fault Localization (SFL) uma das mais promissoras. A técnica SFL aponta os elementos de programas (e.g., comandos, ramos e associações definição-uso), ordenando-os por valor de suspeição. Heursticas são usadas para ordenar os elementos mais suspeitos de um programa, que então são mapeados em linhas de código a serem inspecionadas pelos desenvolvedores. Embora informações de fluxo de dados (associações definição-uso) tenham mostrado desempenho melhor do que informações de fluxo de controle (comandos e ramos) para localizar defeitos, o alto custo para coletar cobertura de fluxo de dados tem impedido a sua utilização na prática. Uma ferramenta de cobertura de fluxo de dados foi recentemente implementada apresentando, em média, 38% de sobrecarga em tempo de execução em programas similares aos desenvolvidos na indústria. Tal sobrecarga, bastante modesta, motiva o estudo de SFL usando informações de fluxo de dados. Para atingir esse objetivo, Jaguar (Java coveraGe faUlt locAlization Ranking), uma ferramenta que usa técnicas SFL com cobertura de fluxo de controle e de dados, foi implementada. A eficiência e eficácia de ambos os tipos de coberturas foram comparados usando 173 versões com defeitos de programas com tamanhos variando de 10 a 96 KLOC. Foram usadas dez heursticas conhecidas para ordenar as linhas mais suspeitas. Os resultados mostram que o comportamento das heursticas são similares para fluxo de controle e de dados: Kulczyski2 e Mccon obtêm melhores resultados para números menores de linhas investigadas (de 5 a 30), enquanto Ochiai é melhor quando mais linhas são inspecionadas (de 30 a 100). A comparação entre os dois tipos de cobertura mostra que fluxo de dados localiza mais defeitos em uma variação de 10 a 50 linhas inspecionadas, sendo até 22% mais eficaz. Além disso, na faixa entre 20 e 100 linhas, fluxo de dados classifica com significância estatstica melhor os defeitos. No entanto, fluxo de dados é mais caro do que fluxo de controle: leva de 23% a 245% mais tempo para obter os resultados; fluxo de dados é em média 129% mais custoso. Portanto, os resultados indicam que fluxo de dados é mais eficaz para localizar os defeitos pois rastreia mais relacionamentos durante a execução do programa. Por outro lado, técnicas SFL apoiadas por cobertura de fluxo de dados precisam ser mais eficientes para utilização prática na indústria

Diversas aplicações são responsáveis por gerar dados ao longo do tempo de maneira contínua, ordenada e ininterrupta em um ambiente dinâmico, denominados fluxo de dados. Entre possíveis tarefas que podem ser realizadas com estes dados, classificação é uma das mais proeminentes. Devido à natureza não estacionária do ambiente responsável por gerar os dados, as características que descrevem os conceitos das classes do problema de classificação podem se alterar ao longo do tempo. Por isso, classificadores de fluxo de dados requerem constantes atualizações em seus modelos para que a taxa de acerto se mantenha estável ao longo do tempo. Na etapa de atualização a maior parte das abordagens considera que, após a predição de cada exemplo, o seu rótulo correto é imediatamente disponibilizado sem qualquer atraso de tempo (latência nula). Devido aos altos custos do processo de rotulação, os rótulos corretos nem sempre podem ser obtidos para a maior parte dos dados ou são obtidos após um considerável atraso de tempo. No caso mais desafiador, encontram-se as aplicações em que após a etapa de classificação dos exemplos, os seus respectivos rótulos corretos nunca sã disponibilizados para o algoritmo, caso chamado de latência extrema. Neste cenário, não é possível o uso de abordagens tradicionais, sendo necessário o desenvolvimento de novos métodos que sejam capazes de manter um modelo de classificação atualizado mesmo na ausência de dados rotulados. Nesta tese, além de discutir o problema de latência na tarefa de classificação de fluxo de dados não estacionários, negligenciado por boa parte da literatura, também sã propostos dois algoritmos denominados SCARGC e MClassification para o cenário de latência extrema. Ambas as propostas se baseiam no uso de técnicas de agrupamento para a adaptação à mudanças de maneira não supervisionada. Os algoritmos propostos são intuitivos, simples e apresentam resultados superiores ou equivalentes a outros algoritmos da literatura em avaliações com dados sintéticos e reais, tanto em termos de acurácia de classificação como em tempo computacional. Aléem de buscar o avanço no estado-da-arte na área de aprendizado em fluxo de dados, este trabalho também apresenta contribuições para uma importante aplicação tecnológica com impacto social e na saúde pública. Especificamente, explorou-se um sensor óptico para a identificação automática de espécies de insetos a partir da análise de informações provenientes do batimento de asas dos insetos. Para a descrição dos dados, foi verificado que os coeficientes Mel-cepstrais apresentaram os melhores resultados entre as diferentes técnicas de processamento digital de sinais avaliadas. Este sensor é um exemplo concreto de aplicação responsável por gerar um fluxo de dados em que é necessário realizar classificações em tempo real. Durante a etapa de classificação, este sensor exige a adaptação a possíveis variações em condições ambientais, responsáveis por alterar o comportamento dos insetos ao longo do tempo. Para lidar com este problema, é proposto um Sistema com Múltiplos Classificadores que realiza a seleção dinâmica do classificador mais adequado de acordo com características de cada exemplo de teste. Em avaliações com mudanças pouco significativas nas condições ambientais, foi possível obter uma acurácia de classificação próxima de 90%, no cenário com múltiplas classes e, cerca de 95% para a identificação da espécie Aedes aegypti, considerando o treinamento com uma única classe. No cenário com mudanças significativas nos dados, foi possível obter 91% de acurácia em um problema com 5 classes e 96% para a classificação de insetos vetores de importantes doenças como dengue e zika vírus. / Many applications are able to generate data continuously over t ime in an ordered and uninterrupted way in a dynamic environment , called data streams. Among possible tasks that can be performed with these data, classification is one of the most prominent . Due to non-stationarity of the environment that generates the data, the features that describe the concepts of the classes can change over time. Thus, the classifiers that deal with data streams require constants updates in their classification models to maintain a stable accuracy over time. In the update phase, most of the approaches assume that after the classification of each example from the stream, their actual class label is available without any t ime delay (zero latency). Given the high label costs, it is more reasonable to consider that this delay could vary for the most portion of the data. In the more challenging case, there are applications with extreme latency, where in after the classification of the examples, heir actual class labels are never available to the algorithm. In this scenario, it is not possible to use traditional approaches. Thus, there is the need of new methods that are able to maintain a classification model updated in the absence of labeled data. In this thesis, besides to discuss the problem of latency to obtain actual labels in data stream classification problems, neglected by most of the works, we also propose two new algorithms to deal with extreme latency, called SCARGC and MClassification. Both algorithms are based on the use of clustering approaches to adapt to changes in an unsupervised way. The proposed algorithms are intuitive, simpleand showed superior or equivalent results in terms of accuracy and computation time compared to other approaches from literature in an evaluation on synthetic and real data. In addition to the advance in the state-of-the-art in the stream learning area, this thesis also presents contributions to an important technological application with social and public health impacts. Specifically, it was studied an optical sensor to automatically identify insect species by the means of the analysis of information coming from wing beat of insects. To describe the data, we conclude that the Mel-cepst ral coefficients guide to the best results among different evaluated digital signal processing techniques. This sensor is a concrete example of an applicat ion that generates a data st ream for which it is necessary to perform real-time classification. During the classification phase, this sensor must adapt their classification model to possible variat ions in environmental conditions, responsible for changing the behavior of insects. To address this problem, we propose a System with Multiple Classifiers that dynamically selects the most adequate classifier according to characteristics of each test example. In evaluations with minor changes in the environmental conditions, we achieved a classification accuracy close to 90% in a scenario with multiple classes and 95% when identifying Aedes aegypti species considering the training phase with only the positive class. In the scenario with considerable changes in the environmental conditions, we achieved 91% of accuracy considering 5 species and 96% to classify vector mosquitoes of important diseases as dengue and zika virus.

Nos últimos anos, percebeu-se uma crescente busca por softwares e arquiteturas alternativas. Essa busca acontece porque houve avanços na tecnologia do hardware e estes avanços devem ser complementados por inovações nas metodologias de projetos, testes e verificação para que haja um uso eficaz da tecnologia. Muitos dos softwares e arquiteturas alternativas, geralmente partem para modelos que exploram o paralelismo das aplicações, ao contrário do modelo de von Neumann. Dentre as arquiteturas alternativas de alto desempenho, tem-se a arquitetura a fluxo de dados. Nesse tipo de arquitetura, o processo de execução de programas é determinado pela disponibilidade dos dados. Logo, o paralelismo está embutido na própria natureza do sistema. O modelo a fluxo de dados possui a vantagem de expressar o paralelismo de maneira intrínseca, eliminando a necessidade de o programador explicitar em seu código os trechos onde deve haver paralelismo. As arquiteturas a fluxo de dados voltaram a ser um tema de pesquisa devido aos avanços do hardware, em particular, os avanços da Computação Reconfigurável e os FPGAs (Field-Programmable Gate Arrays). O projeto ChipCflow é uma ferramenta para execução de algoritmos usando o modelo a fluxo de dados dinâmico em FPGA. Este trabalho apresenta o formato para os tagged-tokens do ChipCflow, os operadores de manipulação das tags dos tokens e suas implementações a fim de que se tenha a PROVA-DE-CONCEITOS para tais operadores na arquitetura ChipCflow / The alternative architectures and softwares researches have been growing in the last years. These researches are happening due to the advance of hardware technology and such advances must be complemented by improvements on design methodologies, test and verification techniques in order to use technology effectively. Many of the alternative architectures and softwares, in general, explore the parallelism of applications, differently to von Neumann model. Among high performance alternative architectures, there is the Dataflow Architecture. In this kind of architecture, the execution of programs is determined by data availability, thus the parallelism is intrinsic in these systems. The dataflow architectures become again a highlighted research area due to hardware advances, in particular, the advances of Reconfigurable Computing and FPGAs (Field-Programmable Gate Arrays). ChipCflow project is a tool for execution of algorithms using dynamic dataflow graph in FPGA. The main goal in this module of the ChipCflow project is to define the tagged-token format, the iterative operators that will manipulate the tags of tokens and to implement them

Os processadores de arquitetura orientada ao fluxo de dados, denominados Data Flow, são estruturas voltadas a implementação em VLSI em função do grande número de Unidades de Processamento e da vasta rede de interconexão entre os mesmos. Este trabalho visa propor o diagrama de um processador Data Flow e discutir sua implementação em VLSI, bem como avaliar seu funcionamento e desempenho através da proposição de um modelo de simulação utilizando-se programação concorrente.

O objetivo deste trabalho é mostrar os resultados obtidos com a simulação do Processador de Imagem em Pipeline, NEC UPD 7281, em termos de desempenho. O processador simulado é uma máquina de computação a fluxo de dados. Entretanto, este não pode ser considerado uma máquina a fluxo de dados clássica, pois possui algumas diferenças com relação ao modelo clássico. Para mostrar isto, o texto introduzo modelo de computação a fluxo de dados, dando enfoque para o módulo em si, para as arquiteturas e para as linguagens de programação a fluxo de dados. A arquitetura do Processador de Imagem em Pipeline é mostrada com detalhes aonde os módulos de processador são descritos. São mostradas as diferenças básicas entre a arquitetura do processador NEC UPD 7281 e o modelo de computação a fluxo de dados clássico. Para medida de desempenho do processador, foram executados, pelo simulador, programas de aplicação com algumas possibilidades de testes. Os programas foram rodados em multiprocessadores em anel de diversos tamanhos, em número de processadores. Para cada número de processadores, os programas foram testados para executar apenas um conjunto de dados e para processar listas de dados. As primeiras medidas foram referentes ao latência do sistema, isto é, o tempo para que o primeiro resultado saia, e a segunda medida é a qualidade de resultados que o anel produz a cada 100 ciclos. Estas medidas fornecem subsídios para buscar a melhor maneira de programar o processador simulado.

O algoritmo que resolve o método de advecção proposto por Walcek tem como principais características a conservação dos valores de picos, tanto de máximo quanto de mínimo, e a baixa difusão numérica. Entretanto este algoritmo possui também uma característica intrínseca que limita a implementação de paralelismo por cooperação de tarefas: exige dependências de fluxo no cálculo das células do domínio. O presente trabalho propõe a mudança no paradigma de programação do algoritmo original para torná-lo aderente ao processamento a fluxo de dados. Nesse tipo de processamento a computação ocorre em forma de tarefas que são definidas de acordo com os valores/estado dos dados de entrada. Essas tarefas podem ou não conter dependências e permitem ainda uma organização não sequencial do processamento. Quando tarefas independentes surgem, a obtenção de paralelismo passa a ser trivial. Experimentos realizados sobre domínios unidimensionais mostram que a abordagem a fluxo de dados expõe situações propícias ao processamento paralelo outrora desconhecidas, além de obter um tempo total de processamento inferior ao algoritmo original. Quando considerando domínios multidimensionais, a nova abordagem consegue um desempenho paralelo equivalente e um tempo total de processamento até 2,5 mais rápido do que a abordagem original.

Made available in DSpace on 2015-02-04T21:38:38Z (GMT). No. of bitstreams: 1 Antonino Cecilio.pdf: 2793291 bytes, checksum: b0720ce07be10a11c533bf1e6cfc6ad9 (MD5) Previous issue date: 2008-02-29 / Esta pesquisa exploratória objetiva estudar como se dá o fluxo de dados, informações e conhecimentos do produto automóvel, pelo seu devido gerenciamento durante o ciclo de vida do produto (Product Lifecycle Management - PLM) e que encontra eco no contexto da indústria automobilística, por se tratar de um segmento em que não existem fronteiras para desenvolver, manufaturar ou vender produtos, e ainda possibilita às organizações tratarem do gerenciamento do ciclo de vida do produto. Este ciclo, que se inicia com o planejamento, passa por todo o desenvolvimento e pela produção, ultrapassa a disponibilização do bem ao consumidor e o suporte necessário, acompanhando-o até seu devido descarte. Para o alcance do objetivo, realizou-se, inicialmente, uma ampla revisão da recente literatura relacionada ao tema PLM; e com isso, evidenciou-se a grande complexidade e abrangência desta prática, além de uma percepção inicial dos fluxos de dados, informações e conhecimentos que ocorrem entre suas sete etapas. A partir destas informações da primeira fase da pesquisa levantamento do estado-da-arte da prática de PLM no contexto da indústria automobilística - desenvolveram-se diagramas e matrizes de associação objetivando descrever as integrações entre dados, informações e conhecimentos existentes entre as sete etapas do PLM. Estes resultados iniciais foram analisados e complementados por uma pesquisa de campo que envolveu outras duas fases: a) comparação com a realidade de uma empresa montadora. Para isso, realizou-se a análise da prática da gestão do ciclo de vida do produto automóvel no contexto da organização Volkswagen do Brasil (VWB) e, posteriormente, b) discussão das percepções junto a especialistas no assunto, tanto acadêmicos quanto praticantes. Para a primeira fase da pesquisa de campo, utilizou-se o método de estudo de caso único; para a segunda, aplicou-se a metodologia Delphi. Os resultados indicam que a aplicação efetiva da abordagem PLM, passa a ser condição sine qua non em ambientes organizacionais, especialmente para o ambiente automobilístico em que criar, utilizar, armazenar e até descartar adequadamente os dados, informações e conhecimentos pertinentes ao produto automóvel, poderá gerar valor competitivo para estas empresas, por possibilitar um amplo entendimento e controle do produto que se está desenvolvendo o Automóvel - e assim tomar as decisões mais acertivas possíveis.