Máquinas de aprendizagem, como Redes Neuronais Artificiais (ANNs), Redes Bayesianas, Máquinas de Vetores de Suporte (SVMs) e outras, são aplicadas em problemas de classificação de padrões. Devido ao baixo erro de teste, a SVM possui uma grande quantidade de aplicações, como no reconhecimento de imagens, seleção de genes, classificação de textos, robótica, reconhecimento de escrita a mão e outras. Dos algoritmos desenvolvidos para o treinamento da SVM, o Sequential Minimal Optimization (SMO) é um dos mais rápidos e o mais fácil de implementar em software. Devido a sua importância, várias otimizações para diminuir ainda mais o seu tempo de execução têm sido reportadas. A maioria das implementações do treinamento da SVM foram realizadas em software. Não obstante, a implementação em hardware é necessária em algumas aplicações com restrições: de área, e/ou de energia e/ou de tempo de treinamento, por exemplo, em algumas aplicações portáveis ou móveis. Nas implementações em hardware anteriores a este trabalho, o treinamento da SVM foi realizado com um conjunto de exemplos cuja quantidade é da ordem de somente dezenas, e unicamente uma delas usou o algoritmo SMO. Neste trabalho é apresentada uma modificação do algoritmo SMO, que denominamos algoritmo SMO de Múltiplos Pares (MP-SMO), para a aceleração do treinamento da SVM. A diminuição do tempo de treinamento é obtida realizando a otimização de um ou mais pares de coeficientes, chamados Multiplicadores de Lagrange, em cada iteração. De modo diferente, o algoritmo SMO original otimiza somente um par. O algoritmo MP-SMO apresenta as seguintes características: 1) a otimização de cada par de coeficientes é mantida simples usando a solução analítica do algoritmo SMO original. 2) as heurísticas para a seleção dos múltiplos pares a otimizar são adaptações das soluções anteriores para a seleção de um par por iteração. Testou-se o algoritmo otimizando até dois, três e quatro pares de coeficientes por iteração, e melhores resultados foram obtidos quando comparados com os do algoritmo SMO. Nos testes realizados com sete benchmarks, o tempo de treinamento diminuiu entre 22,5% e 42,8%. A diminuição do tempo de execução do algoritmo SMO em hardware é também abordada nesta dissertação. Os algoritmos SMO e MP-SMO foram completamente implementados em hardware dedicado para o benchmark Tic-tac-toe endgame. Este benchmark é composto por 958 exemplos, uma quantidade superior às usadas nas implementações anteriores. Com o algoritmo MP-SMO pretendeu-se reduzir o número de iterações, como na implementação em software, e poder incluir paralelismo na implementação em hardware. Para diminuir o tempo de execução de cada iteração, arquiteturas dos tipos pipeline e paralela foram usadas. Foram implementadas e testadas em um dispositivo do tipo FPGA (Field Programmable Gate Array) dezesseis diferentes arquiteturas no total, combinando ou não o algoritmo SMO ou o MP-SMO com pipelining e/ou paralelismo. O tempo de treinamento diminuiu no melhor caso para 1,8% do obtido com o algoritmo SMO implementado sem pipelining nem paralelismo, ou seja, diminuiu em mais de 50 vezes. Esta dissertação apresenta também a análise do custo em área e potência decorrente do aumento da velocidade de treinamento. / Learning Machines, like Artificial Neural Networks (ANNs), Bayesian Networks, Support Vector Machines (SVMs) and others are applied in pattern classification problems. As the test error in SVM is small, it has several applications, such as image recognition, gene selection, text classification, robotics, handwritten recognition and others. Among the developed algorithms for the SVM training, the Sequential Minimal Optimization (SMO) is one of the fastest and the simplest to implement in software. Due to its importance, many improvements have been proposed in order to obtain even faster solutions than the original algorithm. Most of the SVM training implementations are in software. However, in some applications with restrictions of: area, and/or power and/or training time, a hardware implementation is necessary, for example, in some mobile or portable applications. In related previous works, the SVMs were trained in hardware using sets of only tens of examples, and in only one implementation the SMO algorithm was employed. In this work, a modified version of the SMO algorithm, named here the Multiple Pairs SMO (MP-SMO) algorithm, for the SVM training acceleration is presented. The training time reduction is obtained optimizing per iteration one or more pairs of coefficients known as Lagrange Multipliers, instead of only one pair as in the original SMO algorithm. The MP-SMO algorithm has the following features: 1) the optimization of each pair is as simple as in the original SMO algorithm because of the use of the same analytical method. 2) the solution for the pairs of coefficients selection can be chosen between two adapted heuristics for the SMO algorithm. The algorithm was tested optimizing up to two, three and four pairs of coefficients per iteration, and the training time was improved, when compared against the SMO algorithm. The tests for seven benchmarks showed an improvement that ranged from 22.5% to 42.8%. The reduction of the training time of the SMO algorithm executed in hardware is also treated in this dissertation. The algorithms SMO and MP-SMO were completely implemented in dedicated hardware for the Tic-tac-toe endgame benchmark. This benchmark is composed of 958 examples, a number greater than the used in the previous hardware implementations. The implementation of the MP-SMO algorithm is intended to reduce the number of iterations, as in the software implementation, and to include parallelism in the hardware implementation. In order to reduce the iteration execution time, the pipeline and parallel architectures were realized. Sixteen different architectures were implemented and tested on a Field Programmable Gate Array (FPGA) device, combining or not the SMO or MP-SMO algorithm with pipelining and/or parallelism. The training time was reduced to 1.8% of that obtained with the SMO algorithm without neither pipelining nor parallelism, that is, more than 50 times. This dissertation also presents an analysis of the area and power cost of the training speed increase.

Este trabalho propõe um controlador PID (Proporcional, Integrador, Derivativo), implementado em hardware reconfigurável, para controle de ganho de uma câmera com sensor CMOS. O conceito utilizado é o de sistemas SoC (System-on-a-Chip). As principais funções realizadas pelo sistema são: Aquisição da imagem, montagem do histograma, análise do histograma, controle de ganho baseado na análise do histograma. O sistema proposto tem como objetivo conter algumas funções básicas de controle de ganho que possam servir de base para construção de sistemas de visão computacional que possibilitem a otimização do tempo gasto na construção de novos sistemas, deixando o projetista concentrado na parte mais específica do sistema. O algoritmo de controle de ganho através da análise de histograma demonstrou ser além de funcional, altamente flexível, pois pode ser aplicado a qualquer câmera, independente do tipo do sensor. Este algoritmo pode ser aplicado a tipos diferentes de sensores, com diferentes taxas de aquisição e transmissão de imagens. Este ambiente baseado em computação reconfigurável proporciona alta performance e flexibilidade no modo de implementação, possibilitando que o hardware seja configurado para satisfazer situações que exigem alto desempenho, que pode ser obtido através do paralelismo de operações. Esta arquitetura ainda possibilita a configuração de processadores que executam operações em software em conjunto com operações executadas em hardware. O sistema final controla a câmera CMOS de maneira adequada às aplicações robóticas de tempo real / This paper proposes a PID controller (Proportional, Integrator, Derivative), implemented in reconfigurable hardware to control a CMOS sensor camera gain. The concept used is the system SoC (System-on-a-Chip). The main functions performed by the system are: image acquisition, assembly of the histogram, histogram analysis, gain control based analysis of the histogram. The proposed system aims to contain some basic gain control functions. These functions may serve as a basis for future construction of computer vision systems. This work will optimize the time spent in building new systems, leaving the designer free to concentrate on more specific development. The gain control algorithm through the analysis of histogram proved be functional, highly exible, and it can be applied to any camera, regardless of the type of sensor. This algorithm can be applied to different types of image sensors with different acquisition and transmission rates. This environment-based reconfigurable computing provides high performance and exibility in implementation, enabling the hardware to be confiogured to meet situations that require high performance, which can be obtained through parallelism of operations. This architecture also enables the configuration of processors that perform software operations in conjunction with hardware operations. The final system controls the CMOS camera accordingly to real-time robotic applications

As Máquinas de Vetores de Suporte (SVMs) têm sido largamente empregadas em diversas aplicações, graças à sua baixa taxa de erros na fase de testes (boa capacidade de generalização) e o fato de não dependerem das condições iniciais. Dos algoritmos desenvolvidos para o treinamento da SVM, o Sequential Minimal Optimization (SMO) é um dos mais rápidos e eficientes para a execução desta tarefa. Importantes implementações da fase de treinamento da SVM têm sido feitas em FPGAs. A maioria destas implementações tem sérias restrições na quantidade de conjunto de amostras a serem treinadas, pelo fato de implementarem soluções numéricas. De observação na literatura técnica, apenas dois trabalhos implementaram o SMO para o treinamento SVM em hardware e apenas um destes possibilita o treinamento de uma quantidade importante de amostras, porém a aplicação é restrita a apenas um benchmark específico. Na última década, com a tecnologia baseada em RAM estática, os FPGAs apresentaram um novo aspecto de flexibilidade: a capacidade de reconfiguração dinâmica, que possibilita a alteração do sistema em tempo de execução trazendo redução de área. Adicionalmente, apesar de uma potencial penalidade no tempo de processamento, a velocidade de execução continua muito superior quando comparada com soluções em software. No presente trabalho, uma solução genérica é proposta para o treinamento SVM em hardware (i.e. uma arquitetura que possibilite o treinamento para diversos tipos de amostras de entrada), e, motivado pela natureza seqüencial do algoritmo SMO, uma arquitetura dinamicamente reconfigurável é desenvolvida. Um estudo da implementação genérica com codificação em ponto fixo é apresentada, assim como os efeitos de quantização. A arquitetura é implementada no dispositivo Xilinx Virtex-IV XC4VLX25. Dados de tempo e área são obtidos e detalhes da síntese são explorados. É feita uma simulação da reconfiguração dinâmica através de chaves de isolação para a validação do sistema sob reconfiguração dinâmica. A arquitetura foi testada para três diferentes benchmarks, com resultados indicando que o treinamento no hardware reconfigurável foi acelerado em até 30 vezes quando comparado com a solução em software e os estudos apontaram que uma economia de até 22,38% de área útil do FPGA pode ser obtida dependendo das metodologias de síntese e implementação adotadas. / Support Vector Machines have been largely used in different applications, due to their high classifying capability without errors (generalization capability) and the advantage of not depending on the initial conditions. Among the developed algorithms for the SVM training, the Sequential Minimal Optimization (SMO) is one of the fastest and the one of the most efficient algorithms for executing this task. Important dedicated hardware implementations of the training phase of the SVM have been proposed for digital FPGA. Most of them are very restricted about the quantity of input samples to be trained due to the fact that they implement numeric solutions. Only two works with implementation in the SMO algorithm for the SVM training in hardware have been reported recently, and just one is able to train an important quantity of input samples, however it is restricted for only one specific benchmark. In the last decade, with the technology based on static memory (SRAM), FPGAs has provided a unique aspect of flexibility: the capability of dynamic reconfiguration, which involves altering the programmed design at run-time and allows area\'s saving. In addition, although leading to some time penalty, the execution time is still faster when compared with purely software solutions. In this work we present a totally hardware general-purpose implementation of the SMO algorithm. In this general-purpose approach, training of examples with different number of samples and elements are possible, and, motivated by the sequential nature of some of the SMO tasks, a dynamically reconfigurable architecture is developed. A study of the general-purpose implementation with fixed-point codification is presented, as well as the quantization effects. The architecture is implemented in the Xilinx Virtex-IV XC4VLX25 device, and timing and area data are provided. Synthesis details are exploited. A simulation using dynamic circuit switching is carried out in order to validate the systems dynamic reconfiguration aspects. The architecture was tested in the training of three different benchmarks; the training on the reconfigurable hardware was accelerated up to 30 times when compared with software solution, and studies points to an area saving up to 22.38% depending on the synthesis and implementation methodologies adopted in the project.

Máquinas de aprendizagem, como Redes Neuronais Artificiais (ANNs), Redes Bayesianas, Máquinas de Vetores de Suporte (SVMs) e outras, são aplicadas em problemas de classificação de padrões. Devido ao baixo erro de teste, a SVM possui uma grande quantidade de aplicações, como no reconhecimento de imagens, seleção de genes, classificação de textos, robótica, reconhecimento de escrita a mão e outras. Dos algoritmos desenvolvidos para o treinamento da SVM, o Sequential Minimal Optimization (SMO) é um dos mais rápidos e o mais fácil de implementar em software. Devido a sua importância, várias otimizações para diminuir ainda mais o seu tempo de execução têm sido reportadas. A maioria das implementações do treinamento da SVM foram realizadas em software. Não obstante, a implementação em hardware é necessária em algumas aplicações com restrições: de área, e/ou de energia e/ou de tempo de treinamento, por exemplo, em algumas aplicações portáveis ou móveis. Nas implementações em hardware anteriores a este trabalho, o treinamento da SVM foi realizado com um conjunto de exemplos cuja quantidade é da ordem de somente dezenas, e unicamente uma delas usou o algoritmo SMO. Neste trabalho é apresentada uma modificação do algoritmo SMO, que denominamos algoritmo SMO de Múltiplos Pares (MP-SMO), para a aceleração do treinamento da SVM. A diminuição do tempo de treinamento é obtida realizando a otimização de um ou mais pares de coeficientes, chamados Multiplicadores de Lagrange, em cada iteração. De modo diferente, o algoritmo SMO original otimiza somente um par. O algoritmo MP-SMO apresenta as seguintes características: 1) a otimização de cada par de coeficientes é mantida simples usando a solução analítica do algoritmo SMO original. 2) as heurísticas para a seleção dos múltiplos pares a otimizar são adaptações das soluções anteriores para a seleção de um par por iteração. Testou-se o algoritmo otimizando até dois, três e quatro pares de coeficientes por iteração, e melhores resultados foram obtidos quando comparados com os do algoritmo SMO. Nos testes realizados com sete benchmarks, o tempo de treinamento diminuiu entre 22,5% e 42,8%. A diminuição do tempo de execução do algoritmo SMO em hardware é também abordada nesta dissertação. Os algoritmos SMO e MP-SMO foram completamente implementados em hardware dedicado para o benchmark Tic-tac-toe endgame. Este benchmark é composto por 958 exemplos, uma quantidade superior às usadas nas implementações anteriores. Com o algoritmo MP-SMO pretendeu-se reduzir o número de iterações, como na implementação em software, e poder incluir paralelismo na implementação em hardware. Para diminuir o tempo de execução de cada iteração, arquiteturas dos tipos pipeline e paralela foram usadas. Foram implementadas e testadas em um dispositivo do tipo FPGA (Field Programmable Gate Array) dezesseis diferentes arquiteturas no total, combinando ou não o algoritmo SMO ou o MP-SMO com pipelining e/ou paralelismo. O tempo de treinamento diminuiu no melhor caso para 1,8% do obtido com o algoritmo SMO implementado sem pipelining nem paralelismo, ou seja, diminuiu em mais de 50 vezes. Esta dissertação apresenta também a análise do custo em área e potência decorrente do aumento da velocidade de treinamento. / Learning Machines, like Artificial Neural Networks (ANNs), Bayesian Networks, Support Vector Machines (SVMs) and others are applied in pattern classification problems. As the test error in SVM is small, it has several applications, such as image recognition, gene selection, text classification, robotics, handwritten recognition and others. Among the developed algorithms for the SVM training, the Sequential Minimal Optimization (SMO) is one of the fastest and the simplest to implement in software. Due to its importance, many improvements have been proposed in order to obtain even faster solutions than the original algorithm. Most of the SVM training implementations are in software. However, in some applications with restrictions of: area, and/or power and/or training time, a hardware implementation is necessary, for example, in some mobile or portable applications. In related previous works, the SVMs were trained in hardware using sets of only tens of examples, and in only one implementation the SMO algorithm was employed. In this work, a modified version of the SMO algorithm, named here the Multiple Pairs SMO (MP-SMO) algorithm, for the SVM training acceleration is presented. The training time reduction is obtained optimizing per iteration one or more pairs of coefficients known as Lagrange Multipliers, instead of only one pair as in the original SMO algorithm. The MP-SMO algorithm has the following features: 1) the optimization of each pair is as simple as in the original SMO algorithm because of the use of the same analytical method. 2) the solution for the pairs of coefficients selection can be chosen between two adapted heuristics for the SMO algorithm. The algorithm was tested optimizing up to two, three and four pairs of coefficients per iteration, and the training time was improved, when compared against the SMO algorithm. The tests for seven benchmarks showed an improvement that ranged from 22.5% to 42.8%. The reduction of the training time of the SMO algorithm executed in hardware is also treated in this dissertation. The algorithms SMO and MP-SMO were completely implemented in dedicated hardware for the Tic-tac-toe endgame benchmark. This benchmark is composed of 958 examples, a number greater than the used in the previous hardware implementations. The implementation of the MP-SMO algorithm is intended to reduce the number of iterations, as in the software implementation, and to include parallelism in the hardware implementation. In order to reduce the iteration execution time, the pipeline and parallel architectures were realized. Sixteen different architectures were implemented and tested on a Field Programmable Gate Array (FPGA) device, combining or not the SMO or MP-SMO algorithm with pipelining and/or parallelism. The training time was reduced to 1.8% of that obtained with the SMO algorithm without neither pipelining nor parallelism, that is, more than 50 times. This dissertation also presents an analysis of the area and power cost of the training speed increase.

Este trabalho propõe um controlador PID (Proporcional, Integrador, Derivativo), implementado em hardware reconfigurável, para controle de ganho de uma câmera com sensor CMOS. O conceito utilizado é o de sistemas SoC (System-on-a-Chip). As principais funções realizadas pelo sistema são: Aquisição da imagem, montagem do histograma, análise do histograma, controle de ganho baseado na análise do histograma. O sistema proposto tem como objetivo conter algumas funções básicas de controle de ganho que possam servir de base para construção de sistemas de visão computacional que possibilitem a otimização do tempo gasto na construção de novos sistemas, deixando o projetista concentrado na parte mais específica do sistema. O algoritmo de controle de ganho através da análise de histograma demonstrou ser além de funcional, altamente flexível, pois pode ser aplicado a qualquer câmera, independente do tipo do sensor. Este algoritmo pode ser aplicado a tipos diferentes de sensores, com diferentes taxas de aquisição e transmissão de imagens. Este ambiente baseado em computação reconfigurável proporciona alta performance e flexibilidade no modo de implementação, possibilitando que o hardware seja configurado para satisfazer situações que exigem alto desempenho, que pode ser obtido através do paralelismo de operações. Esta arquitetura ainda possibilita a configuração de processadores que executam operações em software em conjunto com operações executadas em hardware. O sistema final controla a câmera CMOS de maneira adequada às aplicações robóticas de tempo real / This paper proposes a PID controller (Proportional, Integrator, Derivative), implemented in reconfigurable hardware to control a CMOS sensor camera gain. The concept used is the system SoC (System-on-a-Chip). The main functions performed by the system are: image acquisition, assembly of the histogram, histogram analysis, gain control based analysis of the histogram. The proposed system aims to contain some basic gain control functions. These functions may serve as a basis for future construction of computer vision systems. This work will optimize the time spent in building new systems, leaving the designer free to concentrate on more specific development. The gain control algorithm through the analysis of histogram proved be functional, highly exible, and it can be applied to any camera, regardless of the type of sensor. This algorithm can be applied to different types of image sensors with different acquisition and transmission rates. This environment-based reconfigurable computing provides high performance and exibility in implementation, enabling the hardware to be confiogured to meet situations that require high performance, which can be obtained through parallelism of operations. This architecture also enables the configuration of processors that perform software operations in conjunction with hardware operations. The final system controls the CMOS camera accordingly to real-time robotic applications

As Máquinas de Vetores de Suporte (SVMs) têm sido largamente empregadas em diversas aplicações, graças à sua baixa taxa de erros na fase de testes (boa capacidade de generalização) e o fato de não dependerem das condições iniciais. Dos algoritmos desenvolvidos para o treinamento da SVM, o Sequential Minimal Optimization (SMO) é um dos mais rápidos e eficientes para a execução desta tarefa. Importantes implementações da fase de treinamento da SVM têm sido feitas em FPGAs. A maioria destas implementações tem sérias restrições na quantidade de conjunto de amostras a serem treinadas, pelo fato de implementarem soluções numéricas. De observação na literatura técnica, apenas dois trabalhos implementaram o SMO para o treinamento SVM em hardware e apenas um destes possibilita o treinamento de uma quantidade importante de amostras, porém a aplicação é restrita a apenas um benchmark específico. Na última década, com a tecnologia baseada em RAM estática, os FPGAs apresentaram um novo aspecto de flexibilidade: a capacidade de reconfiguração dinâmica, que possibilita a alteração do sistema em tempo de execução trazendo redução de área. Adicionalmente, apesar de uma potencial penalidade no tempo de processamento, a velocidade de execução continua muito superior quando comparada com soluções em software. No presente trabalho, uma solução genérica é proposta para o treinamento SVM em hardware (i.e. uma arquitetura que possibilite o treinamento para diversos tipos de amostras de entrada), e, motivado pela natureza seqüencial do algoritmo SMO, uma arquitetura dinamicamente reconfigurável é desenvolvida. Um estudo da implementação genérica com codificação em ponto fixo é apresentada, assim como os efeitos de quantização. A arquitetura é implementada no dispositivo Xilinx Virtex-IV XC4VLX25. Dados de tempo e área são obtidos e detalhes da síntese são explorados. É feita uma simulação da reconfiguração dinâmica através de chaves de isolação para a validação do sistema sob reconfiguração dinâmica. A arquitetura foi testada para três diferentes benchmarks, com resultados indicando que o treinamento no hardware reconfigurável foi acelerado em até 30 vezes quando comparado com a solução em software e os estudos apontaram que uma economia de até 22,38% de área útil do FPGA pode ser obtida dependendo das metodologias de síntese e implementação adotadas. / Support Vector Machines have been largely used in different applications, due to their high classifying capability without errors (generalization capability) and the advantage of not depending on the initial conditions. Among the developed algorithms for the SVM training, the Sequential Minimal Optimization (SMO) is one of the fastest and the one of the most efficient algorithms for executing this task. Important dedicated hardware implementations of the training phase of the SVM have been proposed for digital FPGA. Most of them are very restricted about the quantity of input samples to be trained due to the fact that they implement numeric solutions. Only two works with implementation in the SMO algorithm for the SVM training in hardware have been reported recently, and just one is able to train an important quantity of input samples, however it is restricted for only one specific benchmark. In the last decade, with the technology based on static memory (SRAM), FPGAs has provided a unique aspect of flexibility: the capability of dynamic reconfiguration, which involves altering the programmed design at run-time and allows area\'s saving. In addition, although leading to some time penalty, the execution time is still faster when compared with purely software solutions. In this work we present a totally hardware general-purpose implementation of the SMO algorithm. In this general-purpose approach, training of examples with different number of samples and elements are possible, and, motivated by the sequential nature of some of the SMO tasks, a dynamically reconfigurable architecture is developed. A study of the general-purpose implementation with fixed-point codification is presented, as well as the quantization effects. The architecture is implemented in the Xilinx Virtex-IV XC4VLX25 device, and timing and area data are provided. Synthesis details are exploited. A simulation using dynamic circuit switching is carried out in order to validate the systems dynamic reconfiguration aspects. The architecture was tested in the training of three different benchmarks; the training on the reconfigurable hardware was accelerated up to 30 times when compared with software solution, and studies points to an area saving up to 22.38% depending on the synthesis and implementation methodologies adopted in the project.