Proposta de Arquitetura em Hardware para FPGA da Técnica Q-learning de … · Proposta de Arquitetura em Hardware para FPGA da Técnica Q-learning de Aprendizagem por Reforço Lucileide

UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE

CENTRO DE TECNOLOGIA

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E

DE COMPUTAÇÃO

Proposta de Arquitetura em Hardware paraFPGA da Técnica Q-learning de Aprendizagem

por Reforço

Lucileide Medeiros Dantas da Silva

Orientador: Prof. Dr. Marcelo Augusto Costa Fernandes

Dissertação de Mestrado apresentado aoPrograma de Pós-Graduação em EngenhariaElétrica e de Computação (PPgEE/UFRN)(área de concentração: Engenharia de Com-putação) como parte dos requisitos para ob-tenção do título Mestre em Ciências

.

Número de ordem PPgEE: M473Novembro 2016, Natal, Brasil

Catalogação da Publicação na Fonte

Universidade Federal do Rio Grande do Norte - Sistema de Bibliotecas Biblioteca Central Zila Mamede / Setor de Informação e Referência

Silva, Lucileide Medeiros Dantas da. Proposta de Arquitetura em Hardware para FPGA da Técnica Q-learning de Aprendizagem por Reforço / Lucileide Medeiros Dantas da Silva. - 2017.

73 f. : il. Dissertação (mestrado) - Universidade Federal do Rio Grande do

Norte, Centro de Tecnologia, Programa de Pós-Graduação em Engenharia Elétrica e de Computação. Natal, RN, 2017.

Orientador: Prof. Dr. Marcelo Augusto Costa Fernandes. 1. FPGA (Field Programmable Gate Array) - Dissertação. 2. Q-

learning - Dissertação. 3. Aprendizagem por reforço - Dissertação. 4. Hardware - Dissertação. I. Fernandes, Marcelo Augusto Costa. II. Título.

RN/UF/BCZM CDU 621: 004.41

Proposta de Arquitetura em Hardware paraFPGA da Técnica Q-learning de Aprendizagem

por Reforço

Lucileide Medeiros Dantas da Silva

Dissertação de Mestrado aprovada em 18 de novembro de 2016 pela banca examinadoracomposta pelos seguintes membros:

Prof. Dr. Marcelo Augusto Costa Fernandes (orientador) . . . . . . . . DCA/UFRN

Prof. Dr. Alisson Vasconcelos de Brito . . . . . . . . . . . . . . . . . . . . . . . . . . . CI/UFPB

Prof. Dr. Adrião Duarte Dória Neto . . . . . . . . . . . . . . . . . . . . . . . . . . . DCA/UFRN

Prof. Dr. José Alberto Nicolau De Oliveira . . . . . . . . . . . . . . . . . . . . . DEE/UFRN

Prof. Dr. Jorge Dantas de Melo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DCA/UFRN

Ao meu amor e companheiro, Walter.

Agradecimentos

Ao meu orientador, professor Dr. Marcelo Augusto Costa Fernandes por acreditar no meutrabalho, pela dedicação durante todo o processo de orientação e pelo apoio oferecidodurante a realização deste trabalho.

Aos colegas Matheus, Sérgio e Alysson que dedicaram um pouco do seu tempo para meajudar a descobrir novas ferramentas e estavam sempre dispostos a ajudar com valiosassugestões para implementação do trabalho.

Aos demais colegas da base de pesquisa, pelo companheirismo e pelos momentos com-partilhados.

À Universidade Federal do Rio Grande do Norte - UFRN, que me acolheu nos últimosdois anos durante a realização de meu mestrado acadêmico.

Ao Instituto Federal de Educação Ciência e Tecnologia do Rio Grande do Norte - IFRN,pelo apoio financeiro.

Aos meus pais, Rosa Neide e José Renato, que sempre me incentivaram a estudar cadadia um pouco mais.

Aos meus irmãos e sobrinhos, as melhores companhias e alegria dos meus dias duranteas muitas idas a Natal.

Ao meu esposo e companheiro, Walter Gadelha, que sempre me ajudou a melhorar e quefoi sempre compreensivo e carinhoso, me dando força durante os momento mais difíceis.

À todos estes, o meu muito obrigada!

Resumo

O Q-learning é uma técnica de aprendizagem por reforço off-policy que tem comoprincipal vantagem a possibilidade de obter uma política ótima interagindo com o ambi-ente sem que o modelo deste ambiente necessite ser conhecido. Este trabalho descreveuma proposta de arquitetura paralela em ponto fixo da técnica usando hardware reconfi-gurável do FPGA (Field Programmable Gates Arrays). O objetivo de desenvolver essatécnica em hardware é otimizar o tempo de processamento do sistema. São apresentadosresultados de convergência do algoritmo, área de ocupação e frequência de amostragem.Também são apresentados detalhes de implementação da arquitetura. O projeto foi de-senvolvido utilizando a plataforma de desenvolvimento System Generator da Xilinx sendoprojetado para o FPGA Virtex 6 xc6vcx240t-1ff1156.

Palavras-chave: FPGA, Q-learning, Aprendizagem por Reforço, Hardware

Abstract

Q-learning is a off-policy reinforcement learning technique which has as main ad-vantage the possibility of obtaining an optimal policy interacting with an unknown modelenvironment. This work proposes a parallel fixed-point Q-learning algorithm architecture,implemented in FPGA. Fundamental to this approach is optimize system processing time.Convergence results are presented. The processing time and occupied area were analy-zed for diferentes scenarios and various fixed point formats. Architecture implementationdetails were featured. The entire project was developed using the System Generator plat-form (Xilinx), with a Virtex-6 xc6vcx240t-1ff1156 as the target FPGA.

Keywords: FPGA, Q-learning, Reinforcement Learning, Hardware

Sumário

Sumário i

Lista de Figuras iii

Lista de Tabelas v

Lista de Algoritmos vii

1 Introdução 11.1 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Principais Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Artigos Publicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4 Organização da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Computação Reconfigurável 72.1 Introdução à Computação Reconfigurável . . . . . . . . . . . . . . . . . 72.2 Field Programmable Gate Arrays - FPGA . . . . . . . . . . . . . . . . . 8

2.2.1 Arquitetura do FPGA . . . . . . . . . . . . . . . . . . . . . . . . 112.2.2 Consumo de Potência . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Técnica Q-Learning de Aprendizagem por Reforço 153.1 Aprendizagem por Reforço . . . . . . . . . . . . . . . . . . . . . . . . . 153.2 Q-Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Arquitetura em Hardware da Técnica Q-learning 214.1 Visão Geral da Arquitetura . . . . . . . . . . . . . . . . . . . . . . . . . 214.2 GA - Sorteio das Ações . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.3 EN - Módulo de Atualização . . . . . . . . . . . . . . . . . . . . . . . . 244.4 RS - Função Recompensa . . . . . . . . . . . . . . . . . . . . . . . . . . 254.5 S - Cálculo da Função Valor . . . . . . . . . . . . . . . . . . . . . . . . 26

4.5.1 Qn - Cálculo da Função Valor . . . . . . . . . . . . . . . . . . . 27

i

4.5.2 SFn Estado Futuro . . . . . . . . . . . . . . . . . . . . . . . . . 274.6 SEL - Seleção do Estado Futuro . . . . . . . . . . . . . . . . . . . . . . 29

5 Resultados 315.1 Resultados de Simulação . . . . . . . . . . . . . . . . . . . . . . . . . . 315.2 Resultado de Síntese . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.2.1 Análise dos Resultados de Ocupação . . . . . . . . . . . . . . . 365.2.2 Análise dos Resultados de Amostragem . . . . . . . . . . . . . . 40

6 Considerações Finais 476.1 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.2 Perspectivas Futuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

6.2.1 Regras de Seleção da Ação . . . . . . . . . . . . . . . . . . . . . 486.2.2 Exploração e Explotação . . . . . . . . . . . . . . . . . . . . . . 496.2.3 Multi-Agente . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Referências bibliográficas 51

Lista de Figuras

2.1 Visão abstrata do FPGA [Woehrle & Kirchner 2015]. . . . . . . . . . . . 92.2 Fluxo de mapeamento do FPGA [Woehrle & Kirchner 2015]. . . . . . . . 102.3 Arquitetura de uma LUT [Woehrle & Kirchner 2015]. . . . . . . . . . . . 122.4 Bloco lógico de uma LUT [Woehrle & Kirchner 2015]. . . . . . . . . . . 13

3.1 Interação agente-ambiente na Aprendizagem por Reforço [Camponogara& Serra 2005]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.1 Visão geral da arquitetura proposta. . . . . . . . . . . . . . . . . . . . . 224.2 Arquitetura do gerador de números aleatórios. . . . . . . . . . . . . . . . 234.3 Gerador de Número Aleatório implementado em Hardware . . . . . . . . 244.4 Arquitetura do módulo Sn . . . . . . . . . . . . . . . . . . . . . . . . . 264.5 Arquitetura do módulo Qn - Cálculo da função valor. . . . . . . . . . . . 284.6 Arquitetura do módulo SFn - Escolha do estado futuro. . . . . . . . . . . 284.7 Arquitetura do módulo SEL. . . . . . . . . . . . . . . . . . . . . . . . . 29

5.1 Exemplo utilizado para simulação e validação da implementação em Hard-ware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.2 Matriz de Cores para Função Valor Obtida em Ponto Flutuante. . . . . . . 345.3 Matrizes de Cores para Funções Valor Obtidas em Ponto Fixo. . . . . . . 355.4 Área ocupada em multiplicadores para diferentes cenários . . . . . . . . 415.5 Área ocupada em registradores para diferentes cenários . . . . . . . . . . 425.6 Área ocupada em LUTs para diferentes cenários . . . . . . . . . . . . . . 435.7 Frequência de amostragem para diferentes cenários com [24.14] bits . . . 45

iii

Lista de Tabelas

2.1 Comparação FPGA - Microprocessador - ASIC . . . . . . . . . . . . . . 8

5.1 Função Valor Para Diferentes Representações Binárias . . . . . . . . . . 345.2 Cenários Simulados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.3 Parâmetros de Síntese . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.4 Síntese de Hardware - Cénario I - (N = 6, Z = 4). . . . . . . . . . . . . . 375.5 Síntese de Hardware - Cénario II - (N = 12, Z = 4). . . . . . . . . . . . . 375.6 Síntese de Hardware - Cénario III - (N = 12, Z = 8). . . . . . . . . . . . . 375.7 Síntese de Hardware - Cénario IV - (N = 20, Z = 4). . . . . . . . . . . . . 375.8 Síntese de Hardware - Cénario V - (N = 20, Z = 8). . . . . . . . . . . . . 385.9 Síntese de Hardware - Cénario VI - (N = 30, Z = 4). . . . . . . . . . . . . 385.10 Síntese de Hardware - Cénario VII - (N = 30, Z = 8). . . . . . . . . . . . 385.11 Síntese de Hardware - Cénario VIII - (N = 56, Z = 4). . . . . . . . . . . . 385.12 Síntese de Hardware - Cénario IX - (N = 56, Z = 8). . . . . . . . . . . . . 395.13 Síntese de Hardware - Cénario X - (N = 132, Z = 4). . . . . . . . . . . . . 395.14 Tempo de Convergência e Frequência de Amostragem de Aplicações da

literatura Utilizando a Arquitetura em Hardware do Q-learning. . . . . . 46

v

Lista de Algoritmos

1 Q-learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

vii

Capítulo 1

Introdução

A Aprendizagem por Reforço (AR) , é um formalismo da inteligência artificial quepermite a um agente aprender a partir da interação com o ambiente onde ele está inse-rido [Sutton & Barto 2012]. Esta abordagem é indicada para situações em que não hámuita informação sobre o comportamento que o agente deve tomar para alcançar o ob-jetivo, ou seja, o agente sem conhecimentos prévios aprende através da interação com oambiente, recebendo recompensas por suas ações e descobrindo assim, a politica ótima[de Almeida 2015]. Dentre os algoritmos de AR, o Q-learning é tido como o mais popu-lar, possuindo aplicações nas mais diversas áreas de conhecimento, tais como engenhariade reservatórios [de Oliveira 2010], técnicas de otimização [de Lima Júnior 2009], co-municação móvel [Nie & Haykin 1999], gerenciamento de potência [Tan et al. 2009],robótica [Park et al. 2001], entre outras.

O desenvolvimento da técnica de aprendizagem por reforço Q-learning em hardwarepermite tornar sistemas mais rápidos que seus equivalentes em software, abrindo assimpossibilidades de utilização em situações onde a problemática de restrição de tempo e/ouprocessamento de grande volume de dados seja necessária. É possível ainda reduzir oconsumo de energia, através da redução dos ciclos de clock, em aplicações onde veloci-dade de processamento não seja relevante ou seja menos limitante que a necessidade debaixo consumo de potência.

Aplicações em tempo real podem apresentar restrições de tempo mais ou menos ri-gorosas. Dentre as aplicações com maiores restrições pode-se listar: sistemas de monito-ramento de sinais vitais em unidades de saúde, controle de sistemas industriais, sistemasde comunicação digitais, em robôs e até em carros e aeronaves. Os mecanismos e mé-todos tradicionais nem sempre conseguem vencer as barreiras impostas pelas restriçõesde tempo mais rigorosas. A pesquisa e o desenvolvimento de algoritmos de aprendiza-gem de máquinas em hardware para aplicações em tempo real tem crescido significativa-mente nos últimos anos. Isso se dá devido a seu potencial de performance com relação

2 CAPÍTULO 1. INTRODUÇÃO

ao tempo de amostragem dos sistemas ([Reyneri 2003], [de Souza & Fernandes 2013],[Barron et al. 2009], [Leiner et al. 2008]), [Noronha & Fernandes 2016], [Torquato &Fernandes 2016], [Silva & Fernandes 2016]. Uma das motivações da implementação datécnica Q-learning em hardware é justamente acelerar o funcionamento e a obtenção dapolítica ótima para que possa ser utilizado em aplicações desse gênero.

Uma outra motivação ao desenvolvimento do trabalho é a possibilidade de aceleraraplicações com grande fluxo de dados. Por exemplo, processamento no contexto de BigData. Uma outra aplicação onde também existe a problemática do tratamento de gran-des quantidades de dados é a Bioinformática que precisa tratar uma grande quantidadede dados de sequenciamento genômico [Saldanha 2012]. Também é possível a utili-zação em DataMine, ou Mineração de Dados, que consiste em descobrir informaçõesrelevantes, que por casualidade estejam mascarados em uma quantidade grande de dados[de Carvalho 2005].

Diferentemente dos processadores que tem sempre seu clock na frequência máxima,no FPGA o clock depende do que esta sendo executado nele. Utilizar um clock menorque a frequência de operação teórica máxima, faz com que a potência dinâmica dimi-nua. Quanto menor o clock, menor o consumo [Shang et al. 2002], sendo possível suautilização em sistemas de baixo consumo.

A escolha do FPGA se deu porque este apresenta alta performance com uma frequên-cia operacional baixa através da exploração do paralelismo [Asano et al. 2009]. OsFPGAs mais modernos podem proporcionar uma performance e densidade semelhante aoASIC com as vantagens de redução do tempo de desenvolvimento, facilidade e rapidez dereprogramação e construção de uma arquitetura flexível [Kuon & Rose 2006].

Assim, este trabalho apresenta uma proposta de arquitetura modular e paralela paraimplementação da técnica Q-learning de aprendizagem por reforço em hardware reconfi-gurável do tipo FPGA com o intuito de diminuir o tempo de processamento possibilitandoa utilização do algoritmo em sistemas de alta dinâmica e/ou grande fluxo de dados oubaixo consumo de potência.

O desenvolvimento deste trabalho, assim como todas as simulações e resultados, foirealizado a partir da plataforma de desenvolvimento Xilinx - System Generator [Xilinx-Inc n.d.] configurada para trabalhar com um FPGA Virtex 6 xc6vcx240t 1ff1156.

1.1 Trabalhos Relacionados

Aprendizado de máquina, inteligência artificial e processamento de sinais são ampla-mente utilizados em aplicações atuais. É importante observar duas importantes novas

1.1. TRABALHOS RELACIONADOS 3

características para estes tipos de aplicações: a quantidade de dados que precisa ser pro-cessada está crescendo constantemente enquanto sistemas móveis e robóticos se tornamcada vez mais importantes [Woehrle & Kirchner 2015]. Várias implementações de arqui-teturas em hardware de algoritmos de aprendizagem de máquina e inteligência artificialsão encontrados na literatura.

Em Reyneri (2003) é feita uma visão geral das implementações de hardware de redesneurais artificiais e sistemas fuzzy salientando as principais limitações, vantagens e des-vantagens de várias técnicas de aplicação. O autor também realiza uma análise de váriosparâmetros de desempenho de hardware, gargalos e o custo-benefício intrínseco à váriasmetodologias de implementação. Já em Leiner et al. (2008) a implementação de umaarquitetura de hardware em FPGA para uma rede neural de memória associativa aplicadaa sistemas de reconhecimento de padrão de imagens é descrita, onde é feito um estudodetalhado de performance da rede, incluindo dados como: taxa de ocupação, velocidadede processamento e consumo do sistema em hardware. Contudo, pouco ainda se encon-tra sobre implementação em hardware de arquitetura programável e/ou fixa da técnica deaprendizagem por reforço Q-Learning. No trabalho de Liu & Elhany (2007) foi descritauma arquitetura em pipeline em hardware do mecanismo de seleção da melhor ação noestado do Q-learning. Segundo o autor, o atraso do algoritmo aumenta com o número deações, sendo o gargalo do sistema, e é possível reduzir este atraso com a implementaçãode uma arquitetura pipeline para a seleção da melhor ação no estado, também foi provado,através de uma consistente fundamentação matemática, que a função valor converge paraa politica ótima, apesar da implementação da arquitetura em pipeline. Entretanto, nãoforam apresentadas soluções de hardware para os demais mecanismos inerentes ao algo-ritmo Q-learning de aprendizagem por reforço, tão-pouco foram apresentados detalhes deimplementação, análise de ocupação ou ferramenta utilizada para o projeto de hardwaredesse mecanismo do sistema. Em [Prabha & Monie 2007] uma arquitetura em hardwaredo algoritmo SARSA (ou On-line Q-learning) de aprendizagem por reforço é desenvol-vida para a aplicação em gerenciamento dinâmico de potência. A principal diferença en-tre o SARSA e o Q-learning é que o SARSA é on-policy, ou seja, aprende valores de açãorelativos à política que ele segue, enquanto o Q-learning é off-police, não dependendoassim da política que está sendo utilizada. O autor converteu o algoritmo SARSA emseu hardware equivalente modelando a arquitetura em VHDL (modelsim). A arquiteturaimplementa um gerenciamento de potência que é capaz de trocar de política de acordocom sua carga de trabalho. A proposta foi simulada e sintetizado no Xilinx Spartan 2E.

Determinadas aplicações em processamento de sinais e aprendizado de máquina im-põem limitações técnicas ao hardware. Além disso a quantidade de dados que precisam


ser processados está em constante crescimento [Woehrle & Kirchner 2015]. Uma alter-nativa prática para o projeto de arquiteturas de hardware é a utilização de ferramentasreconfiguráveis como o FPGA que é uma ferramenta com a capacidade de proporcionaruma performance de densidade semelhante a um ASIC (Application Specific IntegratedCircuit) com a vantagem de utilização de prototipagem rápida e flexibilidade [de Souza &Fernandes 2013]. Devido à sua natureza reconfigurável, novas funções podem ser sempreadicionadas e a atualização do sistema pode ser realizada, conforme necessário [Kuon &Rose 2006]. Outra vantagem pertinente para a utilização de FPGA neste tipo de projetoé a possibilidade de projetar módulos de hardware que trabalhem em paralelo aumen-tando a capacidade de processamento do sistema [Faraji & Naji 2013], permitindo quediferentes partes do algoritmo sejam executadas simultaneamente de maneira a diminuiro tempo de processamento total, resultando em uma alternativa interessante e de melhorperformance que os microprocessadores convencionais como CPUs ou GPUs, sobretudopara aplicações onde há restrições severas de tempo.

São encontrados na literatura alguns trabalhos que apontam o projeto de algoritmosparalelos para o aumento de sua capacidade de processamento. Em Barron et al. (2009) éapresentado uma técnica de decomposição para o Processo de Decisão Markoviano (MDP- Markov Decision Process) em subproblemas, apresentando uma estrutura para a parale-lização de técnicas de aprendizagem por reforço. Esta técnica, segundo o trabalho, é capazde diminuir o tempo de processamento em até dez vezes. Já em [Printista et al. 2002], éproposta uma implementação do algoritmo Q-Learning em uma máquina massivamenteparalela utilizando uma biblioteca de paradigma de troca de mensagem PVM (ParallelVirtual Machine) com um esquema de comunicação baseado na memória cache. Estetrabalho apresenta resultados significativos de convergência do método paralelizado e au-mento de velocidade deste, apontando a paralelização como uma alternativa interessantepara a diminuição do tempo de treinamento para o aprendizado da política.

Outros trabalhos fundamentam a escolha do FPGA, apresentando algumas vantagenscom relação a outras plataformas para aplicações com restrições de tempo. Em Asanoet al. (2009) é feito um estudo comparativo de desempenho de FPGA, GPU e CPU emproblemas de processamento de imagem. Apesar da possibilidade de utilização de para-lelismo em micro-processadores através de multi-cores, que melhora a performance paraum grande número de aplicações, os núcleos são todos agrupados, e a transferência dedados entre eles é muito limitada. Somente para problemas muitos simples (ex.: naive al-gorithms) a GPU é capaz de obter performance parecida ao FPGA. Para algoritmos maissofisticados (ex.: shared arrays), GPUs não demonstram a mesma performance pois temlimitações de acesso de memória causada pela arquitetura.

1.2. PRINCIPAIS CONTRIBUIÇÕES 5

FPGAs oferecem plataformas de hardware adequadas para a implantação de algorit-mos de software [Faraji & Naji 2013]. A partir da fundamentação teórica apresentada, épossível concluir que que o baixo tempo de execução do FPGA em comparação com seushomólogos em software é a principal razão para o seu uso como plataforma de desenvol-vimento da Técnica Q-learning de Aprendizagem por Reforço.

1.2 Principais Contribuições

Esta dissertação de mestrado apresenta como contribuição uma arquitetura paralelaem Hardware para FPGA da técnica Q-learning de aprendizagem por reforço. A ideiaprincipal está fundamentada em desenvolver uma arquitetura modular e paralela para vi-abilizar o aumento da velocidade de execução do algoritmo ou menor consumo atravésda diminuição da frequência do clock. As propriedades intrínsecas do FPGA, tais como:flexibilidade e processamento paralelo foram fundamentais para que esse objetivo sejaalcançado. O baixo tempo de execução do FPGA e a paralelização do fluxo de dadospermite que a técnica Q-learning seja utilizada em aplicações onde haja um grande fluxode dados e restrições rigorosas do tempo de processamento, onde seria inviável o uso deprocessadores genéricos, como: CPUs ou até mesmo GPUs. Uma outra possibilidade deaplicação da arquitetura é em sistemas de baixo consumo, onde o clock do sistema podeser reduzido de maneira a reduzir o consumo de potência.

1.3 Artigos Publicados

1. Lucileide M. D. da Silva, Matheus F. Torquato e Marcelo A. C. Fernandes. "Pro-posta de Arquitetura em Hardware para FPGA da Técnica Q-learning de Aprendi-zagem por Reforço". In: XIII Encontro Nacional de Inteligência Artificial e Com-putacional (ENIAC 2016 - Recife-PE).

2. Lucileide M. D. da Silva e Marcelo A. C. Fernandes. "Arquitetura Paralela doAlgoritmos de Aprendizagem por Reforço Q-learning para FPGA". In: 9a ediçãoda Escola Potiguar de Computação e suas Aplicações (EPOCA 2016 - Natal-RN).

1.4 Organização da Dissertação

A presente dissertação está organizada conforme evidenciado nos parágrafos a seguir.


Neste primeiro capítulo foi apresentada uma breve introdução ao trabalho, em que oproblema é contextualizado. Foi feito também uma revisão bibliográfica e de estado daarte e apresentados os principais objetivos a serem alcançados.

No capítulo 2 será apresentada uma fundamentação teórica sobre computação reconfi-gurável, onde são apresentados detalhes da arquitetura do FPGA, hardware utilizado paraa implementação da arquitetura proposta.

No capítulo 3 será apresentada uma fundamentação teórica sobre aprendizagem porreforço, explorando as principais características e vantagens do algoritmo que foi imple-mentado em Hardware, o Q-learning.

No capítulo 4 será feita uma descrição detalhada do desenvolvimento e da implemen-tação da arquitetura, descrevendo os diversos módulos utilizados para a construção doalgoritmo em hardware.

No capítulo 5 será feita a validação do sistema a partir da simulação de problemassimples na arquitetura apresentada neste trabalho, fazendo a comparação com os resulta-dos obtidos através da simulação do mesmo problema em software. A análise de síntesede hardware do sistema para diferentes cenários de implementação também foram rea-lizadas, onde, serão analisados parâmetros como a área de ocupação e a frequência deamostragem.

E no capítulo 6 serão apresentadas as considerações finais e perspectivas de trabalhosfuturos.

Capítulo 2

Computação Reconfigurável

Este capítulo apresenta detalhes e conceitos sobre computação reconfigurável e FPGA.É exibida uma comparação de eficiência com dispositivos não reconfiguráveis como osASICS e os microprocessadores. É feita uma descrição dos elementos que compõem oFPGA apresentando uma visão abstrata e generalista de sua arquitetura e funcionamento,dando ênfase aos recursos básicos disponíveis como: blocos lógicos e blocos de interco-nexão. É feito também uma breve descrição sobre os tipos de consumo de potência noFPGA, identificando as principais fontes de consumo.

2.1 Introdução à Computação Reconfigurável

A computação reconfigurável combina o desempenho do hardware com a flexibili-dade do software. Através da computação reconfigurável é possível implementar circui-tos com os benefícios de desempenho do hardware, tais como: consumo potência, área,performance. A principal diferença entre os circuitos do tipo ASIC e os circuitos recon-figuráveis, como os FPGAs, é justamente a possibilidade de adaptar o hardware atravésda reprogramação, não sendo necessária a fabricação de um novo dispositivo a cada mu-dança na arquitetura do circuito integrado. A reprogramação de FPGAs, com um baixocusto, facilidade e rapidez, pode ser utilizada simplesmente para solucionar problemas ebugs do design ou até mesmo para agregar novas funcionalidades ao sistema para as maisdiversas aplicações, assim como é possivel fazer nos softwares. Essa flexibilidade e rapi-dez no desenvolvimento de circuitos reprogramáveis, vem com o ônus de ter transistorese recursos adicionais que são parcialmente utilizados [Shang et al. 2002]. Se comparadoscom microprocessadores tradicionais, nos FPGAs é possível desenvolver e embarcar umaarquitetura com a capacidade de fazer alterações no próprio fluxo de dados e no fluxo decontrole. Num FPGA, a implementação de milhões de operações com recursos distribuí-dos é realizável, fazendo com que sejam muito mais rápidos. A tabela 2.1 resume alguns

8 CAPÍTULO 2. COMPUTAÇÃO RECONFIGURÁVEL

Tabela 2.1: Comparação FPGA - Microprocessador - ASICRUIM REGULAR BOA EXCELENTE

Performance ⇤ �4

Flexibilidade de Recurso 4 � ⇤

Facilidade de Desenvolvimento 4 ⇤�

� - FPGA, ⇤ - microprocessador, 4 - ASIC

parâmetros das três tecnologias de fabricação citadas: FPGA (computação reconfigurá-vel), microprocessadores e ASICs. A partir destes parâmetros é possível a comparação dedesempenhos [Kuon & Rose 2006], [Asano et al. 2009]. É possível notar que o FPGAe o ASIC têm maior potencial de performance em detrimento dos microprocessadores.No entanto, o ASIC não apresenta capacidade de reutilização de recurso como o FPGA.Enquanto que a flexibilidade dos microprocessadores é superior ainda ao FPGA.

Os dispositivos reconfiguráveis são compostas de blocos lógicos e blocos de conexão.Os blocos lógicos podem ser reconfigurados em sua funcionalidade e/ou lógica. Já osblocos de interconexão, que também podem ser reconfigurados, são os responsáveis pelaligação entre os blocos lógicos. Como os blocos lógicos são alocados diretamente nohardware é possível implementar algoritmo de forma paralela, possibilitando que estesalgoritmos sejam executados mais rapidamente que se fossem implementados de formasequencial em processadores de hardware fixo.

2.2 Field Programmable Gate Arrays - FPGA

Um FPGA (ou Field Programmable Gate Array) é um circuito integrado desenhadopara ser configurado pelo usuário após a sua fabricação. A Figura 2.1 ilustra a estruturainterna do FPGA, que é constituído por um conjunto de blocos lógicos embarcados numaestrutura de roteamento flexível para fazer sua conexão e células de entrada e saída (pi-nos de I/O), usando ferramentas de CAD automatizadas, os projetistas podem programarblocos lógicos e suas interligações correspondentes de maneira a implementar a aplicaçãodesejada [Shang et al. 2002].

2.2. FIELD PROGRAMMABLE GATE ARRAYS - FPGA 9

!"#$#%"&'($#

)*+,-$#*,./#

01"2"3%4,%)56

Figura 2.1: Visão abstrata do FPGA [Woehrle & Kirchner 2015].

O FPGA é formado por elementos lógicos que podem ser configurados para formarcircuitos específicos e implementar algoritmos em hardware afim de alcançar melhorasexpressivas na performance [Woehrle & Kirchner 2015]. Ao contrário de CPUs e GPUs,um FPGA não tem um conjunto fixo de instruções ou pipeline, ao invés disso, pode serprogramado para funcionar como qualquer tipo de circuito lógico digital. O FPGA émajoritariamente composto por LABs (Logic Arrays Blocks) dispostos em matrizes co-nectadas por estruturas programáveis de roteamento (blocos de interconexão). Cada LABcontém vários LEs (Logic Element) que são blocos lógicos formados por LUTs (LookupTables) , Flip-Flops ou registradores, e alguns circuitos adicionais, como por exemplocarry logic, para prover uma maior funcionalidade ou flexibilidade. As LUTs são consti-tuídas por uma árvore de multiplexadores que tem como entrada uma matriz de elementosde memória. Dependendo do tipo de dado escrito no elemento de memória durante suaconfiguração, o elemento lógico pode realizar qualquer tipo de função lógica combinaci-onal desejada. Desde as mais complexas até a simples portas AND ou XOR. Já o regis-trador (ou Flip-Flop) permite que o elemento lógico realize funções lógicas sequenciais.As LUTs, blocos de interconexão, e todas as demais funções programáveis do FPGA sãocontroladas por bits de controle das SRAM. O FPGA precisa ser configurado antes deser utilizado. Significa dizer que os dados precisam ser escritos nas SRAM para que sejaprogramada sua funcionalidade. Como as SRAMs são regraváveis, os FPGAs podem ser


reprogramados para se adaptar a diferentes tipos de aplicação [Tang 2016].A criação de um circuito baseado em FPGA é um processo de criação de um fluxo de

dados em formato binário (bitstream) que será carregado no dispositivo (Figura 2.2).

!"#$%&'()&*+,

-$+'+.,/0

Figura 2.2: Fluxo de mapeamento do FPGA [Woehrle & Kirchner 2015].


Existem ferramentas para realizar tal configuração, desenvolvidas pelos fabricantesdos FPGAs, sendo a configuração do FPGA geralmente especificada por uma linguagemde descrição de hardware ( Hardware Description Language - HDL). A partir do HDLé feita a síntese lógica que converte um código comportamental de alto nível em portaslógicas. Em seguida a tecnologia de mapeamento separa as portas em grupos que melhorcorrespondem aos recursos lógicos do FPGA. O posicionamento (placement) atribui osagrupamentos lógicos para blocos lógicos específicos e o roteamento determina os recur-sos de interconexão que irão transportar os sinais. Finalmente com a geração do bitstream,um arquivo binário que define todos os pontos de programação do FPGA, os blocos lógi-cos e de roteamento são configurados apropriadamente [Hauck & Dehon 2008].

Historicamente, FPGAs precisavam de mais tempo de processamento, maior consumode potência, tinham um menor potencial de performance e conseguiam implementar me-nos funcionalidades que seus homólogos ASICs. Recentemente, FPGAs como a AlteraStratix 5 ou Xilinx Virtex-6 passaram a fazer frente às soluções correspondentes comASICs, fornecendo uma redução no consumo, uma maior velocidade de processamento,menor custo e maiores possibilidades de reconfiguração [Kuon & Rose 2006]. Apli-cações específicas de FPGAs incluem processamento digital de sinal, prototipagem deASICs, visão computacional, reconhecimento de voz, bioinformática, emulação de hard-ware de computador, detecção de metal, entre vários outras. Com a incorporação de mul-tiplicadores embarcados nos FPGAs, aplicações que anteriormente eram realizadas comDSPs passaram a ter como alternativa o FPGA. Uma outra tendência de uso de FPGAs éa aceleração de hardware, onde se pode usar o FPGA para acelerar certas partes de um al-goritmo e compartilhar o processamento com uma com uma plataforma microprocessada,implementada no próprio FPGA.

2.2.1 Arquitetura do FPGA

Em termos gerais, só há dois tipos de recursos disponíveis nos FPGAs: blocos lógicose blocos de interconexão. Nos blocos lógicos as funções lógicas são executadas. Enquantoque os blocos de interconexão fornecem os caminhos para que os dados possam ir de umnó computacional ao outro.

O bloco lógico básico da maioria dos FPGAs é o lookup table, ou LUT, que é um ele-mento de hardware capaz de implementar facilmente tabelas verdades. Toda e qualquerequação booleana pode ser expressa por sua tabela verdade, sendo possível assim a imple-mentação de algoritmos elaborados agregando várias LUTs. A arquitetura de uma LUTpode ser vista na Figura 2.3. Ela é formada por um multiplexador N:1 e uma memória de


!"#$%&'

!

!!!

!"#$%&'()(*&+,

Figura 2.3: Arquitetura de uma LUT [Woehrle & Kirchner 2015].

N-bits.

Somente com LUTs não seria possível implementar lógica sequencial ou manter oestado do circuito. Flip-flops são acrescentados a estrutura como elementos de armaze-namento para solução desse tipo de problema (Figura 2.4), formando os blocos lógicosbásicos dos FPGAs. A saída do multiplexador seleciona como resultado a saída da LUTou a saída armazenada no flip-flop [Hauck & Dehon 2008].

Os blocos lógicos estão cercados por uma arranjo de interconexão em duas dimensões,conforme é possível observar na Figura 2.1. Enquanto os blocos lógicos executam a com-putação aritmética e lógica, o arranjo de interconexão leva os resultados das operaçõesrealizadas nos blocos lógicos a saída e as roteiam como entradas de outros, através deuma série de interligações programáveis, permitindo cada bloco lógico de se comunicarcom os demais.

Para todos esses pontos programáveis, inclusive para os blocos lógicos, os FPGAsusam SRAMs para armazenar os valores das configurações definidas pelo usuário proje-tista.

Os FPGAs mais modernos dispõem de blocos adicionais para fornecer funcionalida-des que não são implementados de forma tão eficiente em seus blocos básicos. Dentreesses blocos podemos citar os carry chain que aceleram as operações de adição; os mul-tiplicadores embarcados que ocupam uma menor área e tem um menor consumo de po-


!"#

!"

!#

!$%

!$%

&

'

!

(

( )

"*+

Figura 2.4: Bloco lógico de uma LUT [Woehrle & Kirchner 2015].

tência que multiplicações implementadas em LUTs [Hauck & Dehon 2008]; e as RAMspara o armazenamento de dados, evitando a comunicação com memórias externas.

2.2.2 Consumo de Potência

Existem dois tipos de consumo de potência em FPGAs: potência estática e dinâmica.Na tecnologia CMOS, que inclui FPGAs baseados em SRAM, a corrente de fuga é a únicafonte de dissipação de energia estática. Devido a quantidade ínfima de corrente de fuga,a parcela de potência estática consumida é muito menor que a dinâmica.

Há três fontes principais de consumo de potência dinâmica: capacitância efetiva doscircuitos CMOS, transição dos sinas e utilização dos recursos do FPGA. O consumo depotência dinâmica é causado pela carga e descarga da capacitância dos circuitos CMOS epelas transições dos sinais no circuito. Quanto maior a frequência de operação mais tran-sições de sinal e portanto, aumento de dissipação de energia. Um outro fator importantea ser levado em consideração é a utilização dos recursos do FPGA. Em um design típico,a maioria dos recursos disponíveis não são utilizados após a configuração e portanto nãoirão consumir potência dinâmica [Shang et al. 2002].


Capítulo 3

Técnica Q-Learning de Aprendizagempor Reforço

Este capítulo visa discutir os conceitos e utilizações de aprendizagem por reforçodando ênfase na técnica utilizada neste trabalho, a Q-learning. Na sessão 3.1, é feitoum breve levantamento sobre as principais características de sistemas de aprendizagempor reforço. Na sessão 3.2 a técnica Q-learning de Aprendizagem por Reforço, baseadano método de diferença temporal, será apresentada. Também são apresentados detalhesde funcionamento do algoritmo, dando ênfase, principalmente, ao processo de escolha,seleção de alternativas e caminhos de ação ótima para a obtenção da função valor do sis-tema. Foram citados alguns problemas encontrados na literatura que utilizavam a TécnicaQ-learning para determinar a política ótima de funcionamento de seus sistemas. Apresen-tando a quantidade de iterações necessária de acordo com as dimensões desses problemas.

3.1 Aprendizagem por Reforço

Aprendizagem por reforço (AR), conforme descrito por Sutton & Barto (2012), éa maximização de recompensas numéricas através do mapeamento de acontecimentosdefinidas por estados e ações. O agente não recebe a informação de que ação deve tomar,como em outras formas de aprendizagem de máquina, ao invés disso, ele deve descobrirquais as ações que produzirão a melhor recompensa em cada estado a partir de interaçõescom o ambiente. Como descrito por Camponogara & Serra (2005), é um agente queinterage em um ambiente via ação e assimilação, ou seja, o agente determina uma ação aser executada a partir de situações encontradas no ambiente. A ação executada transformao ambiente de algum modo, e perturba o estado na investida de atingir o objetivo, e asmodificações são transmitidas ao agente através de uma recompensa e do próximo estado.

O problema de aprendizagem por reforço apresenta cinco partes fundamentais [Cam-

16 CAPÍTULO 3. TÉCNICA Q-LEARNING DE APRENDIZAGEM POR REFORÇO

ponogara & Serra 2005]:

1. O Ambiente: Todo sistema de AR aprende um mapeamento de situações em açõespor experimentos em um ambiente dinâmico.

2. A Política de Controle / Decisão: Representa o comportamento que o sistema ARsegue para alcançar o objetivo.

3. Reforço e Retorno: O reforço é um sinal devolvido pelo ambiente ao agente assimque uma ação tenha sido efetuada e uma transição de estado tenha ocorrido. Oagente deve maximizar a quantidade total de reforços recebidos chamado de retornoacumulado.

4. Função de Reforço: Existem pelo menos três classes de problemas usadas paracriar funções adequadas a cada tipo de problema:

• Reforço no estado final: As recompensas são todas zero exceto no estado final,em que o agente recebe uma recompensa (e. g., +1) ou uma penalidade (e.g.,-1).

• Tempo mínimo ao objetivo: O agente realiza ações que produzem o caminhoou trajetória mais curta para o estado objetivo.

• Minimizar reforços: Nem sempre o agente precisa ou deve tentar maximizara função reforço, podendo também aprender a minimizá-la.

5. Função Valor: É o mapeamento do estado ou par estado-ação em um valor queé obtido a partir do reforço atual e dos reforços futuros. A função valor que con-sidera somente o estado s é denotada por V (s) e denominada função valor-estado,enquanto que a função valor que considera o par estado-ação (s,a) é denotada porQ(s,a) e denominada função valor-ação.

Como os efeitos das ações não podem ser rigorosamente antecipados, o agente pre-cisa monitorar com frequência o ambiente para que possa reagir adequadamente e ir cons-truindo sua função valor. Em um sistema de AR, o ambiente é representado por [Cam-ponogara & Serra 2005]:

1. Um conjunto de variáveis de estado (S) percebidas pelo agente;

2. Um conjunto de ações (A) escolhidas pelo agente que influenciam o estado do am-biente;

3.2. Q-LEARNING 17

3. O valor das transições de estados, que é passado ao agente através de um sinal dereforço.

O objetivo é determinar uma sequência de ações que determine uma política ótima,definida como o mapeamento de estado em ações que maximizem a soma dos valores dereforço. A Figura 3.1 resume o processo de interação agente-ambiente descrito, onde:

• sk é uma representação do estado do ambiente, sendo st 2 S e S é o conjunto deestados possíveis;

• ak é uma representação de ação, sendo at 2 A e A é o conjunto de ações possíveisno estado sk;

• rk+1 é uma recompensa numérica, consequência da ação at tomada;• sk+1 é o novo estado.

AMBIENTE

AGENTE

AçãoReforçoEstadokaks kr

1+kr

1+ks

Figura 3.1: Interação agente-ambiente na Aprendizagem por Reforço [Camponogara &Serra 2005].

Como os algoritmos de aprendizagem por reforço são baseados na estimativa dafunção valor (V ou Q) que prevê o quão bom é para o agente estar em um determi-nado estado ou o quão bom é executar uma determinada ação em um determinado es-tado [de Oliveira 2010], um método de obtenção de valores (V ou Q) deve ser utilizadopara solucionar os problemas. Os três métodos largamente utilizados são: ProgramaçãoDinâmica, Método de Monte Carlo e Método da Diferença Temporal.

3.2 Q-Learning

O Q-learning [Watkins & Dayan 1992] é uma das técnicas de aprendizagem clas-sificadas como um método de diferença temporal off-policy, já que a convergência para


valores ótimos de Q não depende da política que está sendo utilizada. A função da recom-pensa futura no estado s ao executar uma ação a, denotada como Q(s,a), é assimilada porinterações com o ambiente. É tido como o mais popular algoritmo de AR e foi propostocomo uma maneira de aprender iterativamente uma política ótima quando o modelo dosistema não é conhecido.

A equação de atualização da função valor dos pares estado-ação Q(s,a) do algoritmoQ-learning fundamenta-se na função valor-ação expressa como

Qk+1(snk ,a

zk) = Qk(sn

k ,azk)+a[r(sn

k ,azk)+ gmax(Q(sn

k+1,azk+1))�Qk(sn

k ,azk)] (3.1)

onde:

• k é o instante de discretização, com período de amostragem Ts;• sn

k é o n-ésimo estado do ambiente na k-ésima iteração;• az

k é a z-ésima ação tomada no n-ésimo estado snk também na k-ésima iteração;

• Qk(snk ,a

zk) é o retorno acumulado pelo agente por ter escolhido a ação az

k no estadosn

k no instante k;• r(sn

k ,azk) é o reforço imediato recebido no estado sn

k por ter tomado a ação azk;

• snk+1 é o estado futuro;

• max(Q(snk+1,a

zk)) é o valor Q correspondente à máxima função valor no estado

futuro.• a e g são constantes positivas de valor menor que a unidade que representam o

coeficiente de aprendizagem e o fator de desconto respectivamente.

O coeficiente de aprendizagem determina até que ponto a informação nova substi-tuirá a informação anterior, enquanto que o fator de desconto mais próximo a um reduza influência das recompensas imediatas e considera a recompensa a longo prazo. A fun-ção recompensa (r) indica as ações promissoras imediatas e a função valor (Q) indica oganho total acumulado. Quando o agente muda de um estado para um estado futuro, oQ-learning atualiza a nova estimativa da função valor (Q) do novo estado para o estadoanterior.

Um aspecto relevante da técnica de aprendizagem por reforço Q-learning é que a esco-lha das ações que serão realizadas durante o processo de estimativa da função valor Q(s,a)pode ser realizada por qualquer método de exploração/explotação, até mesmo de formaaleatória. Como demonstrado por [Watkins & Dayan 1992], se cada par estado-ação forvisitado um número infinito de vezes a função valor (Q), convergirá com probabilidade1 para seu valor ótimo, usando um coeficiente de aprendizagem (a) suficientemente pe-queno.

3.2. Q-LEARNING 19

O Algoritmo 1 apresenta o pseudocódigo do Q-learning. Ele tem como entradas o co-eficiente de aprendizagem, a taxa de desconto temporal e a função recompensa. Começacom a inicialização da matriz de função de valores Q e do estado inicial s0. O algoritmoescolhe uma ação dentre as ações possíveis para o estado atual e observa o próximo estadoe a recompensa. O valor de Q é atualizado, o novo estado é definido e então o processose repete por um limite de passos, até retornar a matriz Q atualizada.

Algoritmo 1: Q-learningEntrada: a,g,rinício

Inicialize matriz Q;Inicialize s0;enquanto iteração k menor que limite de passos faça

Sortear uma ação azk para o estado sn

k ;Executar a ação az

k;Observar o estado sn

k+1 e atualizar Qk(snk ,a

zk) de acordo com:

Qk+1(snk ,a

zk) = Qk(sn

k ,azk)+a[r(sn

k ,azk)+ g.maxQ(sn

k+1,azk+1)�Qk(sn

k ,azk)];

sk sk+1;fimretorna matriz Q;

fim

Ainda que o critério de convergência do Q-learning demande que os pares estado-açãosejam visitados infinitas vezes, na prática ao executar um número de iterações suficiente-mente grande (considerando a tarefa a ser aprendida) é possível alcançar valores bastanterelevantes. Para um problema de 18 estados e 2 ações, como o descrito em de Almeida(2015), onde o Q-learning foi utilizado para determinar um politica ótima de seleção en-tre conformação de feixe e controle de potência de um arranjo adaptativo de antenas, aconvergência da matriz Q acontece após aproximadamente 2500 iterações. No trabalhode Das et al. (2014), o Q-learning foi utilizado para fazer o gerenciamento térmico adap-tativo de sistemas multicore, de modo a melhorar a confiabilidade e estender vida útildestes. Nesse segundo trabalho, o algoritmo de AR aprende a relação entre o mapea-mento dos threads para o núcleo (core), a frequência do core e sua temperatura, definindoos intervalos de stress térmico como estados e as trheads, tensões e frequências de ope-ração como ações. Para um intel quad-core o sistema foi modelado por 12 estado e 8ações, sendo necessário um total de 5500 iterações para a convergência da função valorQ. Já no trabalho apresentado em Diniz et al. (2010) o algoritmo Q-learning foi utilizadopara a determinação da política ótima de chaveamento entre três controladores aplicados


a um sistema de tanques de modo a aproveitar a característica positiva de cada um deles,aperfeiçoando assim, a saída do sistema, sendo o sinal de erro discretizado em 41 inter-valos, caracterizando os estados admissíveis, e a escolha entre um dos três controladoresas ações do problema. Um sistema de 41 estado e 3 ações, sorteando as ações de maneiraaleatória, converge para a política ótima em aproximadamente 8000 iterações.

Detalhes sobre a implementação em hardware do algoritmo proposto serão apresenta-dos no Capítulo 4.

Capítulo 4

Arquitetura em Hardware da TécnicaQ-learning

Neste capítulo os detalhes de implementação da arquitetura desenvolvida são descri-tos. Na Seção 4.1 é apresentada uma visão geral da arquitetura em Hardware para FPGAda técnica Q-learning, onde é definida a notação utilizada para a descrição da estrutura.Nas seções seguintes, particularidades de cada um dos módulos do sistema são discutidos,detalhando os mecanismos utilizados para a implementação do Algoritmo 1 em hardware.

4.1 Visão Geral da Arquitetura

Uma visão geral da arquitetura de hardware desenvolvida é apresentada na Figura4.1. Ela recebe o clock da FPGA como entrada e o valor do estado inicial, s0, deve ser,aleatoriamente, inicializado no registrador REG1. Todo o sistema é detalhado a partirdeste diagrama, onde serão explicados os principais mecanismos de escolha de ações,cálculos da função valor, atualização dos pares estado-ação e os mecanismos de seleçãodo estado futuro. O sistema foi projetado para operar com N estados e Z ações e portanto,uma combinação de N⇥Z pares estado-ação possíveis. A arquitetura foi desenvolvida demodo a tentar paralelizar ao máximo a execução do algoritmo de maneira a diminuir e/ouotimizar o tempo de processamento do Q-learning.

A notação utilizada nas figuras é descrita a seguir:

• k é o instante de discretização, com período de amostragem Ts, no qual pode-se me-dir a taxa de transferência, conhecida pelo termo throughput, definida como 1/Ts;

• snk é o n-ésimo estado do ambiente na k-ésima iteração;

• azk é a z-ésima ação tomada no n-ésimo estado sn

k também na k-ésima iteração;• un

k é um vetor de Z elementos que vai atuar habilitando, ou não, os registradores

22 CAPÍTULO 4. ARQUITETURA EM HARDWARE DA TÉCNICA Q-LEARNING

1maxQ

0maxQ

S2

SN

.

.

.

EN1

GA

1+kS

Qmax.γ

...

...Qmax.γ

RS1

EN2

...Qmax.γ

RS2

...ENN

RSN

.

.

.

snk

azk

...

Seleção estado futuro

&

Armazenamento da função valor

SEL

...

...Q

QD

REG1

S1

...

...α

α

α

.

.

.

sk0 1+

sk1 1+

sNk 11−

+

1max −NQ

uk

1

uk

0

uN

k

1−

r 0

r 1

r N 1−

Qk

0

QN

k

1−

Qk

1

.

.

.

snk

azk

azk

azk

Figura 4.1: Visão geral da arquitetura proposta.

que guardam o valor atribuído à função valor no n-ésimo estado;• rn é um vetor, de valor constante, com o reforço imediato para as Z ações do n-

ésimo estado;• sn

k+1 é o n-ésimo estado futuro ;• maxQn é o valor Q correspondente a ação com maior valor de reforço no estado,

atualizado a cada iteração;• Qn

k é um vetor com os elementos da função valor atribuídos as Z ações do n-ésimoestado;

• a e g são constantes positivas de valor menor que a unidade que representam ocoeficiente de aprendizagem e o fator de desconto respectivamente.

O sistema é composto por cinco tipos de módulos tidos como principais: O móduloGA, responsável pelo sorteio das ações do algoritmo; Os módulos EN, que determinamqual o par estado-ação deve ser atualizado; Os módulos RS, responsáveis por armazenaros valores da recompensa; Os módulos S, responsáveis pelo cálculo da função valor Q; Eo módulo SEL, onde é feita a seleção do estado futuro e o armazenamento da função valorQ. Cada um dos módulos do sistema é detalhado individualmente nas seções a seguir.

4.2. GA - SORTEIO DAS AÇÕES 23

4.2 GA - Sorteio das Ações

Como visto no pseudocódigo do Q-learning apresentado em Algoritmo 1 (Capitulo 3)é preciso fazer o sorteio da ação az

k para o estado snk . Para tanto, um gerador de números

pseudo-aleatórios (Pseudo Random Number Generator - PRNG) foi implementado. Ogerador sorteia dentre todas as ações possíveis (0 a Z-1) qual será a ação executada. Cadaz-ésima ação é formada por uma palavra de log2(Z) bits. O primeiro estado s0 é iniciali-zado aleatoriamente, dentre todos os estados possíveis (0 a N-1), no registrador REG1, etem um tamanho de log2(N) bits.

O gerador de números pseudo-aleatórios é o ponto de partida para a execução do al-goritmo. A partir da segunda iteração, os próximos estados passam a ser definido pelarealimentação, como consequência das ações do sistema, e as ações continuam a ser defi-nidas aleatoriamente.

Para que ocorra a convergência do algoritmo é necessário que todos os pares estado-ação sejam visitados um número suficientemente grande (idealmente infinito) de vezes.E para tanto utilizamos o gerador de números pseudo-aleatórios baseado na congruêncianumérica descrita em [Wu 1997]. A expressão utilizada para implementar o PRNG éapresentada como

azk = P1⇥az

k�1 +P2 (mod Z), (4.1)

onde os valores P1 e P2 são constantes, azk é um inteiro entre 0 e Z�1 e az

k�1 é o valor noinstante anterior da série de números pseudo-aleatórios. A arquitetura interna do geradorde números aleatórios está ilustrada na Figura 4.2.

+x

Q

Q D

P1 az

k

azk 1−

GA

Figura 4.2: Arquitetura do gerador de números aleatórios.

Para a implementação, a constante P2 foi adotada como zero. O módulo (mod Z) é


feito a partir de uma função de tratamento de estouro intrínseca do multiplicador, o wrap-around (i.e. valores que ultrapassam o número máximo de bits são contornados dentro dointervalo representável guardando somente os bits menos significativos [Abreu 2014]).

Contudo, podem acontecer problemas onde o número de ações possíveis não sejammúltiplo de dois. Para solucionar esta limitação, foi adotado o recurso ilustrado na Fi-gura 4.3. Um PRNG com número de combinações possíveis (Nomax) muito maior que onúmero de ações desejadas é executado. Em seguida, o intervalo contento todas as com-binações é dividido em Z intervalos iguais. Onde Z é o número de ações desejado. Casoo número sorteado seja 0 < x < C1 a ação az

k será a0k , no caso do número sorteados ser

C1 < x <C2 a ação a1k e assim sucessivamente até que x >CZ�1 quando a ação será aZ�1

k .Essa divisão é feita utilizando comparadores e lógica combinacional.

Figura 4.3: Gerador de Número Aleatório implementado em Hardware

Havendo determinado o par estado-ação em cada iteração, sabe-se qual dos elementosda matriz função valor Qk(sn

k ,szk) deve ser atualizado. Como as ações são escolhidas de

forma aleatória (pseudo-aleatória), a arquitetura realiza apenas a exploração (treinamento)do ambiente pelo agente para a obtenção da politica ótima, não se preocupando com aexplotação.

4.3 EN - Módulo de Atualização

Os módulos de atualização chamados de EN são os responsáveis por selecionar qualpar estado-ação (sn

k , azk) será atualizado. Cada n-ésimo módulo, ENn, é um bloco lógico

combinacional que possui como entradas o k-ésimo estado, snk , e ação, az

k, e sua saída é

4.4. RS - FUNÇÃO RECOMPENSA 25

um vetor de Z elementos, aqui denotado como unk e representado por

unk =

2

66664

un,0k

un,1k...

un,Z�1k

3

77775. (4.2)

onde un,zk é um bit que quando em nível logico alto representa que o elemento da matriz

da função valor Q referente ao n-ésimo estado e a z-ésima ação deve ser atualizado. Con-siderando as saídas de todos os N módulos, são N⇥Z saídas, o mesmo número de paresestado-ação. Contudo, somente uma saída de um desses módulos terá nível lógico altopor cada iteração. A operação lógica que determina un

k é expressa como

unk =

8><

>:

(1 >> azk)||A se sn

k = n

A(4.3)

onde >> é um operador lógico de deslocamento a direita e A é um vetor de Z zeros.Os valores referentes a cada par estado-ação da função valor Qk(sn

k ,szk) são armazena-

dos em N⇥Z registradores que têm suas entradas enable ligadas justamente às saídas dosmódulos EN. Portanto, a função valor só é atualizada quando um dos elementos de umdos n-ésimos vetores un

k estiver em nível lógico alto.

4.4 RS - Função Recompensa

Os valores dos reforços imediatos, ou recompensa, ficam armazenados nos N móduloschamados de RS. A função recompensa rn é um vetor de Z elementos, representado como

rn =

2

66664

rn,0

rn,1

...rn,Z�1

3

77775, (4.4)

que indica quais são as ações imediatas promissoras naquele estado. Cada n-ésimo mó-dulo RS possui Z constantes, rn,z, associadas a cada uma das Z ações do n-ésimo estado.Essas constantes expressam o objetivo que o agente quer alcançar. Cada z-ésima variávelrn,z é constituída por uma palavra de B bits. Ações que levam ao estado objetivo tem


um valor de reforço numérico rn,z positivo. Ações indesejadas no estado recebem um re-forço numérico rn,z negativo. Enquanto que ações que levam aos demais estados recebemrn,z = 0.

4.5 S - Cálculo da Função Valor

A arquitetura em hardware do Q-learning, conforme observado no diagrama principalapresentado na Figura 4.1, é paralelizada com relação aos seus estados (sn

k). O módulo don-ésimo estado, Sn, é subdividido em dois outros módulos de funções diferentes. A suaconfiguração está ilustrada na Figura 4.4.

Figura 4.4: Arquitetura do módulo Sn

No módulo SFn é determinado localmente o estado futuro, snk+1, a partir, somente da

informação da ação sorteada, azk. Já no módulo Qn é realizado o cálculo dos elementos do

vetor da função valor, Qnk , e determinado a função valor correspondente a ação com maior

valor, maxQn, para o n-ésimo estado.

4.5. S - CÁLCULO DA FUNÇÃO VALOR 27

4.5.1 Qn - Cálculo da Função Valor

Cada n-ésimo módulo Qn calcula o vetor

Qnk =

2

66664

Qn,0k

Qn,1k...

Qn,Z�1k

3

77775(4.5)

Qnk é um vetor de Z elementos, onde cada elemento Qn,z

k é formado por B bits. O conjuntodos N vetores, Qn

k , forma a matriz função valor Qk(snk ,a

zk) que pode ser expressa como

Qk(snk ,a

zk) =

hQ0

k Q1k ... QN�1

k

i=

2

66664

Q0,0k Q1,0

k ... QN�1,0k

Q0,1k Q1,1

k ... QN�1,1k

...... ...

...Q0,Z�1

k Q1,Z�1k ... QN�1,Z�1

k

3

77775. (4.6)

As entradas para este módulo são o vetor enable unk , a função recompensa rn, o coeficiente

de aprendizagem a e o valor Q correspondente à ação com maior valor de reforço futurono estado futuro descontado de g (g ·maxQ). Parte da arquitetura interna dos módulos Snestá ilustrada na Figura 4.5, também é uma arquitetura paralela, paralelizada em relação asações do sistema. A cada iteração a matriz Q é atualizada. Para tanto, são utilizados 2⇥Zsomadores (SOM1nz e SOM2nz), Z subtratores (SUBnz) e Z multiplicadores (MULTnZ)em cada um dos n-ésimos módulos Sn que implementam a Equação 3.1 que é a equaçãofundamental do Q-learning, e ainda Z registradores para o armazenamento de Qn

k .

Ademais de calcular a função valor, no módulo Sn é também calculado o valor de Qcorrespondente à ação com maior valor no n-ésimo estado. Esta variável está ilustrada naFigura 4.5 como maxQn e é obtida a partir da comparação (COMPn) de todos os z-ésimoselementos do vetor Qn

k no n-ésimo estado.

4.5.2 SFn Estado Futuro

Há ainda uma terceira funcionalidade implementada no módulo Sn. Nele é determi-nado qual seria o estado futuro Sn

k+1 para a ação ak sorteada pelo GA. A estrutura ilus-trada na Figura 4.6 representa a porção da arquitetura do módulo Sn, o modulo internoSFn, responsável pela execução dessa funcionalidade. Por se tratar de uma arquiteturaparalelizada, um estado futuro é determinado em cada um dos N módulos Sn tomando em


Q

Q

en

D

REGn1++SOM1n1

+-

SUBn1

+x

MULTn1

++SOM2n1

Qmax.0,n

kQ...

r n 0,

Q

Q

en

DREGn2++

SOM1n2

+-

SUBn2

+x

MULTn2

++SOM2n2

...

Q

Q

en

DREGnZ++

SOM1nZ

+-

SUBnZ

+x

MULTnZ

++SOM2nZ

...

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

COMPnr n 1,

r Zn 1, −

nQmax

1, −Znku

1,nku

0,nku

1,nkQ

1, −ZnkQ

Figura 4.5: Arquitetura do módulo Qn - Cálculo da função valor.

consideração somente a informação da ação ak sorteada. No módulo SEL será decididoqual o n-ésimo estado futuro Sn

k+1 seguirá adiante no algoritmo e se tornará o estado atualna seguinte iteração.

MUX1n

ka

.

.

.

0,1

nkS +

1,1

nkS +

1,1−

+Zn

kS

nkS 1+

Figura 4.6: Arquitetura do módulo SFn - Escolha do estado futuro.

Portanto, o bloco entrega três informações ao sistema: o vetor da função valor para asações do n-ésimo estado Qn

k , a função valor corresponde a ação com maior valor maxQn

4.6. SEL - SELEÇÃO DO ESTADO FUTURO 29

e o n-ésimo estado futuro snk+1(s) determinado a partir da ação tomada.

4.6 SEL - Seleção do Estado Futuro

O último módulo da aquitetura é o módulo SEL. Sua estrutura está apresentada naFigura 4.7. É o ponto de junção do algoritmo, onde as informações calculadas parale-lamente nos módulos anteriores são cruzadas. É neste módulo que é determinado qualserá o próximo estado a ser explorado pela arquitetura. É também onde determina-se aação com maior valor no estado futuro maxQ. E onde reúnem-se os N vetores Qn

k para aconstrução da matriz da função valor Qk(sn

k ,azk) do sistema.

Para determinar o estado futuro sk+1, todos os n-ésimos estados futuros snk+1, prove-

nientes dos N módulos Sn são colocados em um multiplexador MUX2, que tem comoseletor o estado atual sk. Esse valor de estado futuro é realimentado para o início daarquitetura e torna-se o estado atual na próxima iteração.

MUX3

MUX2

Qmax.

kS

.

.

.

.

.

.

.

.

.

1+kS

SEL

1kQ

0kQ

1NkQ

),( zk

nkk asQ

01+kS

11+kS

11+

NkS

0maxQ1maxQ

1max NQ

Figura 4.7: Arquitetura do módulo SEL.

Para determinar a ação com maior valor no estado futuro maxQ, o estado futuro sk+1

é usado como seletor do multiplexador MUX3 que tem como entrada as N ações com


maior valor dos N estados da arquitetura maxQn. O valor de maxQ será multiplicado pelofator de desconto temporal g e realimentado às entradas do módulos Sn para o cálculo dosvetores Qn

k que compõem função valor.Nesta capítulo foram apresentados detalhes de implementação da arquitetura proposta.

Uma arquitetura implementada para N estados e Z ações, com uma estrutura de imple-mentação completamente paralela, utilizada para a obtenção da politica ótima através daexploração do ambiente e dos reforços recebidos dele.

Capítulo 5

Resultados

Neste capítulo são apresentados os resultados de simulação e síntese de hardware daarquitetura proposta neste trabalho. Foram realizadas simulações e sínteses de diferentescenários, onde foram variados os números de estados e ações. Todos os cenários foramsimulados e sintetizados para diferentes resoluções em bits. A observação dos resultadosde simulação foi utilizada para validação da arquitetura em hardware e para a avaliação doerro de resolução a partir do número de bits. Enquanto que os resultados de síntese permi-tiram analisar o comportamento do sistema com relação aos parâmetros importantes parao projeto de arquiteturas em hardware, como: taxa de ocupação e tempo de amostragem.

Neste capítulo também é analisado a aplicabilidade da arquitetura proposta em pro-blemas reais. Aplicações encontradas na literatura, que utilizam o algoritmo Q-learningpara o treinamento do agente, foram sintetizadas no FPGA, de modo a obter a frequênciade amostragem e o tempo de convergência para a politica ótima.

5.1 Resultados de Simulação

Para simulação e validação da arquitetura do algoritmo Q-learning foi analisado umcenário caracterizado por um robô que se movimenta em uma arena, tendo como obje-tivo alcançar uma determinada região da arena. O número de estados neste problemarepresenta a granularidade da arena. Enquanto que as ações representam os possíveis mo-vimentos do robô. A arena foi divida em seis regiões (estados: s1,s2,s3,s4,s5 e s6). Eo robô tem quatro direções possíveis de movimento (ações: a1 - cima, a2 - baixo, a3 -esquerda, a4 - direita). O problema descrito está ilustrado na Figura 5.1 e foi simuladocom representação digital em ponto fixo para cinco diferentes resoluções. A notação uti-lizada é [n ·b] onde n é o número total de bits, onde b bits representam a parte fracionariae (n�b) bits representam a parte inteira.

É desejado que o agente consiga chegar na sala 6 (s6), independentemente da sala na

32 CAPÍTULO 5. RESULTADOS

Figura 5.1: Exemplo utilizado para simulação e validação da implementação em Hard-ware

qual ele esteja. Para definir a sala 6 como objetivo, é associado um reforço imediato rn,z =100 para as ações que levam diretamente a região desejada. Setas azuis foram utilizadasna Figura 5.1 para ilustrar estas ações. Se o agente executa uma ação que resulta emchoque com as bordas da arena recebe uma recompensa imediata negativa (rn,z =�500).Estas ações estão representadas por setas de cor vermelha. Em todas as demais transições,a recompensa recebida é nula (rn,z = 0), representadas pelas setas brancas. A matriz r

r =

2

6666666664

�500 0 �500 0�500 0 0 0�500 100 0 �500

0 �500 �500 00 �500 0 1000 �500 0 �500

3

7777777775

(5.1)

demonstra todas as recompensas para todos os pares estado-ação, onde os estados (s1, s2,s3, s4, s5, s6) estão representados nas linhas da matriz, enquanto que as ações (a1,a2,a3,a4),estão representadas pelas colunas. Cada elemento da matriz r é formado por uma palavrade [n ·b] bits.

Os resultados numéricos da função valor Qk(snk ,a

zk) após a simulação da arquitetura

5.1. RESULTADOS DE SIMULAÇÃO 33

desenvolvida foram comparados com resultados obtidos através de uma implementaçãorealizada em Matlab em ponto flutuante, padrão IEEE 754. Para simular o exemplo des-crito, foram utilizados como parâmetros um coeficiente de aprendizagem a=0,8 e umataxa de desconto g = 0,8. Estes parâmetros foram utilizados tanto na simulação em pontoflutuante no Matlab, quanto na simulação da arquitetura paralela em hardware realizadano System Generator.

A matriz da função valor obtida em ponto flutuante, padrão IEEE 754, está aprensen-tada a seguir.

Qk(snk ,a

zk) =

2

6666666664

�357,8 177,8 �357,8 177,8�322,2 222,2 142,2 222,2�277,8 277,8 177,8 �277,8142,2 �322,2 �322,2 222,2177,8 �277,8 177,8 277,8222,2 �322,2 222,2 �322,2

3

7777777775

(5.2)

Os resultados da simulação da arquitetura hardware estão ilustrados na Tabela 5.1. Aarquitetura em hardware foi simulada com representação digital em ponto fixo para cincocenários diferentes No primeiro cenário foram utilizados 24 bits sendo 14 bits de pontobinário (Tabela 5.1 - (a)). No segundo 20 bits sendo 10 de ponto binário (Tabela 5.1 - (b)).Já no terceiro foram utilizados 16 bits com 6 bits de ponto binário (Tabela 5.1 - (c)). E noúltimo cenário, 12 bits com 2 bits de ponto binário (Tabela 5.1 - (d)).

Após as simulações é possível observar, a partir dos resultados adquiridos para a po-lítica ótima, que conforme diminuímos o número de bits maior o erro de resolução (e)obtido com relação ao ponto flutuante. Todavia, é importante enfatizar que a resolução damatriz Q, não é tão significativa, desde que sua política ótima esteja bem definida. A Fi-gura 5.2 é a representação da função valor obtida na simulação em ponto flutuante a partirde uma matriz de cores onde os valores das ações são codificados em uma escala linearde -400 a 400. O menor valor da escala esta representado pelo tom de azul mais escuroenquanto o maior valor está representado no último tom do vermelho. Já a Figura 5.3 éa representação, em matrizes de cores, das funções valores obtidas a partir da simulaçãoda arquitetura em ponto fixo utilizando como referencia a mesma escala. A partir dela épossível observar que, apesar do erro de resolução associado a diminuição do número debits, a política está bem caracterizada. Mesmo no pior caso simulado, com apenas 12 bitsde resolução, onde obtivemos um erro associado maior que 30%, as melhores e pioresações, apesar de terem cores diferentes da matriz de referência, estão bem definidas, apre-


Tabela 5.1: Função Valor Para Diferentes Representações Binárias

Q =

2

6666664

�357,8 177,8 �357,8 177,8�322,2 222,2 142,2 222,2�277,8 277,8 177,8 �277,8

142,2 �322,2 �322,2 222,2177,8 �277,8 177,8 277,8222,2 �322,2 222,2 �322,2

3

7777775Q =

2

6666664

�358,0 177,5 �358,0 177,5�322,5 222,0 142,0 222,0�277,0 277,5 177,5 �278,0

142,0 �322,5 �322,5 222,2177,5 �278,0 177,5 277,5222,0 �322,5 222,0 �322,5

3

7777775

(a) [24.14] bits – e = 0,01% (b) [20.10] bits – e = 0,17%

Q =

2

6666664

�361,5 173,9 �361,5 173,9�326,1 218,2 138,5 218,2�281,8 273,9 173,9 �281,2

138,5 �326,1 �326,1 218,2173,9 �281,8 173,9 273,9218,2 �326,1 218,2 �326,1

3

7777775Q =

2

6666664

�405,0 127,2 �405,0 127,2�372,7 170,0 95,0 170,0�330,0 227,2 127,2 �330,0

95,0 �372,7 �372,7 170,0127,2 �330,0 127,2 227,2170,0 �372,7 170,0 �372,7

3

7777775

(c) [16.6] bits – e = 2,61% (d) [12.2] bits – e = 33,20%

sentando assim, a mesma politica se comparado com o ponto flutuante e com os demaiscasos simulados em diferentes resoluções.

Figura 5.2: Matriz de Cores para Função Valor Obtida em Ponto Flutuante.

5.2. RESULTADO DE SÍNTESE 35

(a) 24 bits (b) 20 bits

(c) 16 bits (d) 12 bits

Figura 5.3: Matrizes de Cores para Funções Valor Obtidas em Ponto Fixo.

O erro de resolução pode sempre ser melhorado com o aumento no número de bits.No entanto, conforme será detalhado nas seções a seguir, isso implica diretamente noaumento da área ocupada no FPGA e do tempo de processamento.

5.2 Resultado de Síntese

Para a análise de síntese de hardware da arquitetura, além do cenário apresentadona Figura 5.1, foram analisados outros nove cenários distintos, com diferentes númerosde estados e ações. Os cenários foram caracterizados usando também como problema orobô, descrito na Seção 5.1, que se movimenta em uma arena. Quão maior a granularidadeda arena maior o número de estados. Seis cenários foram caraterizados para quatro açõespossíveis: a1 - cima, a2 - baixo, a3 - esquerda, a4 - direita, onde o agente se movimenta deuma posição na direção indicada pela ação. Outros quatro cenários foram caracterizadospara oito ações possíveis: a1 - cima, a2 - baixo, a3 - esquerda, a4 - direita, a5 - cima2, a6


- baixo2, a7 - esquerda2, a8 - direita2. Onde o comportamento do agente é o mesmo doscenários anteriores para as quatro primeiras ações enquanto que nas demais ações ele semovimenta duas posições, também na direção indicada pela ação. A dimensão de todosos exemplos implementados e simulados estão apresentados na Tabela 5.2. Os parâmetrosutilizados nos testes destes 10 cenários são mostrados na Tabela 5.3. Todos os resultadosforam obtidos para o FPGA Xilinx Virtex-6 da [Xilinx-Inc n.d.].

Tabela 5.2: Cenários Simulados

Cenário I II III IV V VI VII VIII IX X

Estados (N) 6 12 12 20 20 30 30 56 56 132

Ações (Z) 4 4 8 4 8 4 8 4 8 4

Tabela 5.3: Parâmetros de SínteseParâmetros Valores

Número de Estados NNúmero de Ações Z

Coeficiente de Aprendizagem (a) 0,8Taxa de Desconto (g) 0,8Representação Digital Ponto Fixo

Número de Bits [n.b]

Todos os cenários foram sintetizados com todas as variáveis em ponto fixo. As Tabelas5.4 - 5.13 ilustram os resultados obtidos tanto em termos de taxa de ocupação quantode frequência de amostragem. Nas primeiras colunas é indicada a resolução em bitssintetizada para as variáveis rn e Qn

k , as demais variáveis tem fixa a sua resolução. Paraesta análise de síntese, foram implementadas quatro (4) representações diferentes.

5.2.1 Análise dos Resultados de Ocupação

Analisando os dados das Tabelas 5.4 - 5.13, na segunda coluna é exibido o númerode multiplicadores utilizados. Os multiplicadores são usados no PRNG (módulo GA),também nos módulos S onde é realizado o cálculo da função valor, mais especificamente


Tabela 5.4: Síntese de Hardware - Cénario I - (N = 6, Z = 4).No de bits[n ·b] Multiplicadores Registradores

(Flip-Flops)Células Lógicas

(LUTs)Amostragem

(MHz)

[24 ·14] 34 (4%) 788 (<1%) 2597 (2%) 23,02[20 ·10] 34 (4%) 669 (<1%) 2159 (1%) 21,80[16 ·6] 34 (4%) 548 (<1%) 1734 (1%) 23,54[10 ·0] 34 (4%) 367 (<1%) 1086 (<1%) 26,42

Tabela 5.5: Síntese de Hardware - Cénario II - (N = 12, Z = 4).No de bits[n ·b] Multiplicadores Registradores


(LUTs)Amostragem

(MHz)

[24 ·14] 106 (13%) 1509 (< 1%) 5070 (3%) 20,83[20 ·10] 58 (7%) 1270 (<1%) 4222 (3%) 22,23[16 ·6] 58 (7%) 1029 (< 1%) 3387 (2%) 22,27[10 ·0] 58 (7%) 668 (< 1%) 2133 (1%) 24,76

Tabela 5.6: Síntese de Hardware - Cénario III - (N = 12, Z = 8).No de bits[n ·b] Multiplicadores Registradores


(LUTs)Amostragem

(MHz)

[24 ·14] 202 (26%) 2661 (< 1%) 10379 (7%) 18,08[20 ·10] 106 (13%) 2230 (<1%) 8639 (5%) 20,71[16 ·6] 106 (13%) 1797 (< 1%) 6960 (4%) 20,67[10 ·0] 106 (13%) 1148 (< 1%) 4415 (3%) 23,45

Tabela 5.7: Síntese de Hardware - Cénario IV - (N = 20, Z = 4).No de bits[n ·b] Multiplicadores Registradores


(LUTs)Amostragem

(MHz)

[24 ·14] 170 (22%) 2470 (< 1%) 8349 (5%) 17,82[20 ·10] 90 (11%) 2071 (<1%) 6966 (4%) 19,87[16 ·6] 90 (11%) 1670 (< 1%) 5594 (3%) 20,16[10 ·0] 90 (11%) 1069 (< 1%) 3541 (2%) 21,23


Tabela 5.8: Síntese de Hardware - Cénario V - (N = 20, Z = 8).No de bits[n ·b] Multiplicadores Registradores


(LUTs)Amostragem

(MHz)

[24 ·14] 330 (42%) 4390 (1%) 17188 (11%) 16,74[20 ·10] 170 (22%) 3671 (1%) 14373 (9%) 15,96[16 ·6] 170 (22%) 2950 (< 1%) 11561 (7%) 17,66[10 ·0] 170 (22%) 1869 (< 1%) 7321 (4%) 19,79

Tabela 5.9: Síntese de Hardware - Cénario VI - (N = 30, Z = 4).No de bits[n ·b] Multiplicadores Registradores


(LUTs)Amostragem

(MHz)

[24 ·14] 250 (32%) 3670 (1%) 12379 (8%) 16,57[20 ·10] 130 (16%) 3071 (1%) 10299 (6%) 20,19[16 ·6] 130 (16%) 2470 (< 1%) 8272 (5%) 19,67[10 ·0] 130 (16%) 1569 (< 1%) 5206 (3%) 21,29

Tabela 5.10: Síntese de Hardware - Cénario VII - (N = 30, Z = 8).No de bits[n ·b] Multiplicadores Registradores


(LUTs)Amostragem

(MHz)

[24 ·14] 490 (63%) 6550 (2%) 25627 (17%) 15,53[20 ·10] 250 (32%) 5471 (2%) 21406 (14%) 16,48[16 ·6] 250 (32%) 4390 (1%) 17208 (11%) 16,45[10 ·0] 250 (%) 2769 (< 1%) 10915 (7%) 16,29

Tabela 5.11: Síntese de Hardware - Cénario VIII - (N = 56, Z = 4).No de bits[n ·b] Multiplicadores Registradores


(LUTs)Amostragem

(MHz)

[24 ·14] 458 (59%) 6792 (2%) 23117 (15%) 15,90[20 ·10] 234 (30%) 5673 (2%) 19252 (14%) 15,59[16 ·6] 234 (30%) 4552 (1%) 15526 (10%) 15,15[10 ·0] 234 (30%) 2875 (< 1%) 9808 (6%) 20,20


Tabela 5.12: Síntese de Hardware - Cénario IX - (N = 56, Z = 8).No de bits[n ·b] Multiplicadores Registradores


(LUTs)Amostragem

(MHz)

[24 ·14] 746 (97%) 12248 (4%) 90,917 (60%) 13,75[20 ·10] 378 (49%) 10153 (3%) 55573 (36%) 14,89[16 ·6] 378 (49%) 8136 (2%) 48536 (32%) 14,41[10 ·0] 378 (49%) 5115 (2%) 28849 (19%) 17,88

Tabela 5.13: Síntese de Hardware - Cénario X - (N = 132, Z = 4).No de bits[n ·b] Multiplicadores Registradores


(LUTs)Amostragem

(MHz)

[24 ·14] 730 (95%) 15958 (5%) 142778 (94%) 12,23[20 ·10] 370 (48%) 13175 (4%) 77574 (51%) 13,40[16 ·6] 370 (48%) 10533 (3%) 70311 (46%) 13,35[10 ·0] 370 (48%) 6626 (2%) 40764 (27%) 14,00

a multiplicação do coeficiente de aprendizagem (a) (MULTnz) e para a multiplicaçãodo fator de desconto (g) pela ação com maior valor de reforço futuro (maxQ) (móduloSEL). É observado um aumento no número de multiplicadores, em todos os cenários,para configurações maiores que 20 bits. Isso se dá devido ao tamanho dos multiplicado-res de hardware embutido do FPGA utilizado, que tem um tamanho de 48 bits. Portanto,operações aritméticas realizadas com um multiplicador, agora precisam de mais de um.Todas as multiplicações realizadas nos 8 primeiros cenários (I-VIII) foram implementa-das através de multiplicadores embarcados, no FPGA Virtex-6 eles são slices DSP48E1.Nos cenários IX e X, devido a maior complexidade desses sistemas, algumas operaçõesde multiplicação foram implementadas através de células lógicas (LUTs). Pois o FPGAescolhido não possui multiplicadores embarcados suficientes para implementar esses ce-nários quando sintetizados em maior resolução.

Na terceira coluna é indicado o número de registradores da implementação. A áreaocupada devido aos registradores se dá por conta do armazenamento da função valorQk(sn

k ,azk) (REGnz) que é calculada para cada um dos pares estado-ação. Registradores

também foram utilizados para armazenar o valor da função correspondente à ação commaior valor maxQn para cada um dos estados e para armazenar o estado futuro (sk+1)durante uma iteração, antes que ele seja realimentado ao início da arquitetura e se torne o


estado atual (sk)(REG1).

Na quarta coluna é apresentado o número de células logicas utilizadas. A ocupaçãodas células lógicas é relacionada as operações aritméticas implementadas nos N blocos Spara viabilizar o cálculo da função valor Q. Nos cenários de maior complexidade, IX eX, essa ocupação está diretamente relacionada com a utilização das LUTs para realizar asoperações de multiplicação em substituição aos multiplicadores embarcados.

As Figuras 5.4, 5.5 e 5.6 demonstram a ocupação em termos da variação de estados eações para os cenários já caracterizados. As Figuras 5.4(a), 5.5(a) e 5.6(a) ilustram a ocu-pação para a maior resolução sintetizada, [24.14] bits. Enquanto as Figuras 5.4(b), 5.5(b)e 5.6(b) foram construídas a partir dos dados da menor resolução, [10.0] bits. É possí-vel perceber que a área ocupada aumenta quase que linearmente com o número de paresestado-ação. As descontinuidades presentes nas Figuras 5.4 e 5.6 aparecem pois ao subs-tituir alguns multiplicadores embarcados por LUTs, nos cenários de maior complexidade,consequentemente aumentamos o número proporcional de LUTs e diminuímos a quan-tidade de multiplicadores. Ao comparar a área ocupada para o caso de maior resoluçãocom o caso de menor resolução, é possível observar que o comportamento é praticamenteo mesmo, com relação a área ocupada por multiplicadores (Figura 5.4) e por registra-dores (Figura 5.5). No entanto, é possível perceber que com relação as LUTs isso nãoacontece. O crescimento em LUTs é muito maior quando aumentamos o número de bitse usamos LUTs para as operações de multiplicação em substituição aos multiplicadoresembarcados.

É observado que área de ocupação é determinada tanto pelo número de bits quantopela complexidade do problema, ou seja, quão maior a resolução utilizada no problemae quantos mais pares estado-ação (n,z) maior o espaço ocupado no FPGA. Em situaçõesonde se faça necessário diminuir a ocupação do FPGA é possível modificar a resolução,pois como demonstrado na seção 5.1 (Figura 5.3), é possível obter a política ótima aindaque haja um erro de resolução associado.

5.2.2 Análise dos Resultados de Amostragem

Ainda nas Tabelas 5.4 - 5.13, na última coluna é observada a frequência de amostra-gem. Como o sistema foi desenvolvido de maneira a paralelizar ao máximo o fluxo dedados, a taxa de amostragem não varia expressivamente, mantendo uma frequência deamostragem bem alta, da ordem de 10 MHz.


020

4060

45

67

80

200

400

600

800

EstadosAções

Ocu

paçã

o M

ultip

licad

ores

(a) 24.14 bits

020

4060

45

67

80

100

200

300

400

EstadosAções

Ocu

paçã

o M

ultip

licad

ores

(b) 10.00 bits

Figura 5.4: Área ocupada em multiplicadores para diferentes cenários


020

4060

45

67

80

5000

10000

15000

EstadosAções

Ocu

paçã

o R

egis

trado

res

(a) 24.14 bits

020

4060

45

67

80

1000

2000

3000

4000

5000

6000

EstadosAções

Ocu

paçã

o R

egis

trado

res

(b) 10.00 bits

Figura 5.5: Área ocupada em registradores para diferentes cenários


020

4060

45

67

80

2

4

6

8

10

x 104

EstadosAções

Ocu

paçã

o LU

Ts

(a) 24.14 bits

020

4060

45

67

80

0.5

1

1.5

2

2.5

3

x 104

EstadosAções

Ocu

paçã

o LU

Ts

(b) 10.00 bits

Figura 5.6: Área ocupada em LUTs para diferentes cenários


A partir dos dados de amostragem, é observada uma diminuição na taxa de frequênciamáxima com o crescimento do número de estados do problema. Assim como também épossível notar que essa frequência diminui com o aumento do número de ações possíveispor estado. Isso é explicado pelo aumento da complexidade do problema o que acarretauma maior quantidade de dados a serem processados. A Figura 5.7 apresenta os dados deamostragem para diferentes números de estados e ações com [24.14] bits. Como o sistemafoi desenvolvido de maneira a paralelizar ao máximo o fluxo de dados, essa variação nãoé tão expressiva. Já que, mesmo aumentando o número de pares estado-ação, o caminhopercorrido durante o processamento da informação não é significativamente modificado.Uma pequena redução na frequência de amostragem ocorre pois aumentando o número deações por estado é preciso fazer a comparação (COMPn) da função valor Q(s,a) de todasas ações possíveis de modo a determinar a função valor máxima maxQ(st+1,a) para amelhor ação no n-ésimo estado. Em aumentado o número de estados, consequentementeo número de entradas dos multiplexadores que selecionam o próxima estado (MUX1n)nos módulos Sn também cresce. Assim como dos multiplexadores que selecionam opróximo estado (st+1) (MUX2), e a máxima função valor do estado futuro maxQ(st+1,a)(MUX3). Esses são os principais gargalos para a paralelização completa do sistema e ospontos que influenciam na diminuição da taxa de amostragem de acordo com o aumentoda complexidade do problema. Apesar dos gargalos, é observado que entre o pior (N =

132,Z = 4) e o melhor caso (N = 6,Z = 4) a variação do período de amostragem é inferiora 50ns.

0

20

40

60 45

67

8

12

14

16

18

20

22

24

AçõesEstados

Amos

rage

m (M

Hz)

Figura 5.7: Frequência de amostragem para diferentes cenários com [24.14] bits


Tabela 5.14: Tempo de Convergência e Frequência de Amostragem de Aplicações daliteratura Utilizando a Arquitetura em Hardware do Q-learning.

Referência No deEstados

No deAções

No deIterações

Freq. deAmostragem

Tempo deConvergência

[Diniz et al. 2010] N = 41 Z = 3 ⇠8000 ⇠15MHz ⇠0,5ms

[Das et al. 2014] N = 12 Z = 8 ⇠5500 ⇠23MHz ⇠0,2ms

[de Almeida 2015] N = 18 Z = 2 ⇠2500 ⇠25MHz ⇠0,1ms

De modo a ilustrar a aplicabilidade da arquitetura em hardware para Q-learning apre-sentada neste trabalho, foram sintetizados problemas nas mesmas dimensões destas apli-cações para verificar o tempo de convergência para a politica ótima. Na Tabela 5.14são ilustradas algumas aplicações praticas do Q-learning encontradas na literatura. Aprimeira coluna contém a referência do trabalho. Na segunda e terceira coluna são apre-sentadas as dimensões do problema (número de estados e ações). Na quarta coluna sãoapresentados a quantidade de iterações necessárias para que os problemas, de acordo comas dimensões deste, convirja para a função valor ótima se implementado na arquitetura emhardware do Q-learning proposta neste trabalho. Na coluna seguinte é apresentada a in-formação de frequência de amostragem que o problema poderia alcançar se o Q-learningfosse implementado na arquitetura proposta. Na última coluna, a partir do numero deiterações e da máxima frequência de amostragem, é feita uma estimativa de tempo deconvergência para a politica ótima do problemas citados. Em um problema como o apre-sentado em Diniz et al. (2010), que tem a mesma ordem de complexidade que o cená-rio VIII, é possível executar o Q-learning com uma amostragem de aproximadamente15MHz. Conforme visto em 3.2, são necessárias 8000 iterações para a convergência damatriz Q, o que significa que a política ótima estaria disponível ao sistema após 0,5ms.Já no problema apresentado em Das et al. (2014), que tem o mesmo número de estadose ações do cenário III a matriz função valor, que converge com 5500 iterações, precisariade 0,2ms. E no problema apresentado em de Almeida (2015), com 2500 iterações, seriamnecessário 0,1ms. Caso haja restrição de tempo para aquisição dos dados necessários aocálculo da política, é possível ainda, reduzir o clock do sistema para que, conforme de-monstrado em [Shang et al. 2002], reduza-se o consumo do sistema e adeque-se o tempode execução ao de aquisição dos dados.


Capítulo 6

Considerações Finais

Neste Capítulo são apresentadas as considerações finais do trabalho, fazendo algu-mas observações e expondo as principais conclusões relativas a cada uma das etapas derealização deste trabalho. São indicadas as principais perspectivas de trabalhos futuros,mostrando possíveis caminhos para a implementação de melhorias e/ou funcionalidadesa arquitetura proposta neste trabalho.

6.1 Conclusões

Este trabalho ilustrou uma proposta de arquitetura paralela em Hardware da técnicaQ-learning em FPGA. Foi apresentado o estado da arte de implementações de técnicasde aprendizado de máquina em hardware, dando enfase a técnicas de AR. Foram listadasaplicações que usam o Q-learning como técnica, ilustrando assim as principais motiva-ções ao desenvolvimento deste trabalho. A escolha do FPGA foi justificada devido suaalta performance, baixa frequência de operação e por possuir vários núcleos de processa-mento. Foram indicadas também, as contribuições desta dissertação de mestrado.

Seguindo a linha da dissertação foram mostrados alguns conceitos de inteligencia ar-tificial, enfatizando a técnica Q-learning que foi implementada em hardware reconfigurá-vel, FPGA, neste trabalho. O Q-learning é uma técnica de aprendizagem por reforço quetem como sua principal vantagem a possibilidade de obter uma política ótima interagindocom o ambiente sem que o modelo do sistema necessite ser conhecido. Desenvolver essatécnica em hardware permite diminuir o tempo de processamento do sistema. O FPGAfoi utilizada pela possibilidade de prototipagem rápida e flexibilidade, paralelismo e baixoconsumo de potência, algumas das principais vantagens da FPGA.

Detalhes da implementação da arquitetura em Hardware foram descritos, apresen-tando uma visão geral da estrutura. Também foram discutidos detalhes dos módulos in-dividuais do sistema e quais os mecanismos em hardware foram utilizados para a imple-

48 CAPÍTULO 6. CONSIDERAÇÕES FINAIS

mentação do algoritmo Q-learning. Foi proposta uma arquitetura genérica de N estadose Z ações que faz o processamento dos dados a partir de uma implementação paralela edistribuída para que seja otimizado o tempo de processamento do Q-learning.

Foi feita uma análise detalhada da implementação, além da análise de dados de simu-lação e síntese. A partir dos dados de simulação foi feita a validação da arquitetura. Foraminvestigados também os impactos do erro de resolução para a obtenção da politica ótimado problema. É possível observar que a obtenção da política ótima também pode aconte-cer mesmo para baixa resoluções em bits que implicam em uma menor área de ocupação.A análise dos dados de síntese permitiram verificar o comportamento do sistema com re-lação a parâmetros importantes, como: taxa de ocupação e tempo de amostragem. Pelaobservação dos dados das sínteses em FPGA realizadas neste trabalho foi observado quecom desenvolvimento deste algoritmo, diretamente em hardware, é possível alcançar altopotencial de performance da técnica, sobretudo em termos de tempo de processamentoe/ou baixo consumo de potência se comparado com seus homólogos em software. Es-sas caraterísticas permitem a sua utilização em situações práticas mais complexas e comos mais diversos tipos de aplicação, principalmente aplicações com restrições de tempocomo aplicações em tempo real, aplicações em telecomunicações onde o fluxo de dadosprecisa ser tratado muito rapidamente; ou em aplicações onde haja restrições com relaçãoa alimentação e se faça necessário um baixo consumo de potencia para estes dispositivos.

6.2 Perspectivas Futuras

Diversas modificações podem ser feitas para a melhoria das funcionalidades da ar-quitetura proposta. Nas seções 6.2.1, 6.2.2 e 6.2.3, foram listadas algumas de nossasimpressões com relação as perspectivas de trabalhos para esta implementação.

6.2.1 Regras de Seleção da Ação

Neste trabalho as escolhas das ações foram feitas através de um pseudo-gerador denúmeros aleatórios (Capítulo 4, Seção 4.2) que escolhe as ações, dentre todas as açõespossíveis no enésimo estado, de forma aleatória.

Como uma das perspectivas de trabalhos futuros, é possível substituir o bloco geradorde números pseudo-aleatórios por um outro método que, de alguma forma, leve em con-sideração o conhecimento atual para maximizar a recompensa imediata. Um alternativaé usar métodos como e-gulosa que considera a ação com melhor recompensa imediata namaior parte do tempo, mas em determinados instantes, com uma pequena probabilidade

6.2. PERSPECTIVAS FUTURAS 49

e, escolhe aleatoriamente entre todas as ações independentemente das estimativas da fun-ção valor daquela ação [Sutton & Barto 2012]. Como a arquitetura foi desenvolvida deforma modular, a substituição do Módulo de seleção das ações (GA) pode ser feita sem anecessidade de modificações nos demais mecanismos da arquitetura.

Vale destacar que a escolha do tipo de exploração, e portanto das regras de seleção daação, deve ser escolhida de acordo com o tipo de aplicação no qual o método é empregado.Sendo assim, sem uma aplicação pre-determinada, não é possível adotar o método deseleção da ação ideal.

6.2.2 Exploração e Explotação

Para maximizar a recompensa obtidas pelas interações com o ambiente. O agenteprecisar decidir entre a necessidade de explorar com a explotação. Ou seja, escolher entreusufruir de uma ação já explorada ou se testar novas opções. A exploração impossibilitaque o agente aja sempre de forma ótima. Pois, ele deve eventualmente escolher açõesaleatórias para aprender suas recompensas. Contudo, sem a exploração, o agente nãoconhecera nunca a política ótima. O compromisso entre exploração e explotação é um dospontos chaves para o desenvolvimento de soluções em aprendizagem por reforço [Sutton& Barto 2012].

A arquitetura apresentada neste trabalho, é utilizada para exploração (treinamento)do ambiente pelo agente para a obtenção da politica ótima, não se preocupando com aexplotação. Para trabalhos futuros, fica a perspectiva de implementar uma arquitetura paraa explotação, além do circuito de controle que determina quando o agente deve explorarou quando deve explotar o ambiente.

6.2.3 Multi-Agente

Foi apresentado neste trabalho, uma arquitetura monoagente para a técnica Q-learningde aprendizagem por reforço. Onde um único agente aprende a política de ação através deinterações com o ambiente. Em sistemas monoagentes toda e qualquer entidade diferentedo agente é considerada como ambiente. Sendo o agente capaz de aprender a tomardecisões de forma independente no ambiente.

Em problemas do tipo multiagente, vários agente precisam aprender a política ótima.Todos os agentes tem a capacidade de aprender. Existem variadas técnicas multiagentesque permitem a aceleração do processo de aprendizagem, compartilhamento de aprendi-zagem entre agentes, e robustez a falhas devido a multiplicidade de agentes [?].

50 CAPÍTULO 6. CONSIDERAÇÕES FINAIS

Expandir a arquitetura desenvolvida nesse trabalho para uma arquitetura em hardwaremultiagente é mais uma, dentre as possibilidade já apresentadas, perspectiva de continua-ção deste trabalho.

Referências Bibliográficas

Abreu, Renato Barbosa (2014), Avaliação de projetos de filtros digitais de ponto-fixousando teorias do módulo da satisfatibilidade, Dissertação de mestrado, Universi-dade Federal do Amazonas (UFAM).

Asano, Shuichi, Tsutomu Maruyama & Yoshiki Yamaguchi (2009), ‘Performance compa-rison of fpga, gpu and cpu in image processing’, International Conference on FieldProgrammable Logic and Applications .

Barron, Jonathan T., Dave S. Golland & Nicholas J. Hay (2009), Parallelizing Reinforce-ment Learning, Tese de doutorado, UC Berkeley.

Camponogara, Eduardo & Maurício Rangel Guimarães Serra (2005), ‘Aprendizagem porreforço: Uma primeira intridução’, Universidade Federal de Santa Catarina .

Das, Anup, Rishad A. Shafik & Geoff V. Merrett (2014), ‘Reinforcement learning-basedinter- and intra-application thermal optimization for lifetime improvement of multi-core systems’, Design Automation Conference (DAC) .

de Almeida, Náthalee Cavalcanti (2015), Técnicas de Conformação de Feixe em Arranjode Antenas utilizando Aprendizagem por Reforço, Tese de doutorado, UniversidadeFederal do Rio Grande do Norte (UFRN).

de Carvalho, Luís Alfredo Vidal (2005), Datamining: A Mineração de Dados no Marke-ting, Medicina, Economia, Engenheria, e Admistração, Ciência Moderna.

de Lima Júnior, Francisco Chagas (2009), Algoritimo Q-learning como Estratégia de Ex-ploração e/ou Explotação para as Mateheurísticas GRASP e Algorítimo Genético,Tese de doutorado, Universidade Federal do Rio Grande do Norte (UFRN).

de Oliveira, Amanda Gondim (2010), Uma aplicação da aprendizagem por reforço naotimização da produção em um campo de petróleo, Tese de doutorado, UniversidadeFederal do Rio Grande do Norte (UFRN).

51

52 REFERÊNCIAS BIBLIOGRÁFICAS

de Souza, Alisson C. D. & Marcelo A. C. Fernandes (2013), ‘Proposta de implementaçãoparalela em ponto fixo de uma rede de funçõees radiais de base para fpga’, CBIC .

Diniz, Anthony Andrey Ramalho, Armando José J. Lemos Filho, Paulo Robertoda Motta Pires, Sérgio Massao Kanazava, Jorge Dantas de Melo & Adrião Du-arte Dória Neto (2010), ‘Aplicação do q-learning para definição de política ótimade acionamento de controladores pid, neural e fuzzy em um processo de controle denível’, XVIII Congresso Brasileiro de Automática .

Faraji, Rasoul & Hamid Reza Naji (2013), ‘An efficient crossover architecture for hard-ware parallel implementation of genetic algorithm’, Neurocomputing .

Hauck, Scott & André Dehon (2008), Reconfigurable Computing: The Theory and Prac-tice of FPGA-Based Computation, first editiona edição, Morgab Kaufmann Pu-blishers.

Kuon, Ian & Jonatham Rose (2006), ‘Measuring the gap between fpgas and asics’, Pro-ceedings of the international symposium on Field programmable gate arrays –FPGA’06 .

Leiner, Barba J., Vargas Q. Lorena, Torres M. Cesar & Mattos V. Lorenzo (2008), ‘Hard-ware architecture for fpga implementation of a neural network and its application inimages processing’, Eletronics, Robotics and Automotive Mechanics Conference .

Liu, Zhenzehn & Itamar Elhany (2007), ‘Large-scale tabular-form hardware architecturefor q-learning’, Circuits and Systems .

Nie, Junho & Simin Haykin (1999), ‘A q-learning-based dynamic channel assignmenttechnique for mobile communication systems’, IEE Transactions On Vehicular Te-chnology .

Noronha, Daniel H. & Marcelo Augusto Costa Fernandes (2016), ‘Implementação emfpga de máquina de vetores de suporte (svm) para classificação e regressão’, Encon-tro Nacional de Inteligencia Artificial e Computacional .

Park, Kui-Hong, Yong-Jae Kim & Jong-Hwan Kim (2001), ‘Modular q-learning basedmulti-agent cooperation for robot soccer’, Robotics and Autonomus System .

Prabha, Viswanathan Lakshmi & Elwim Chandra Monie (2007), ‘Hardware architectureof reinforcement learning scheme for dynamic power management in embedded sys-tems’, EURASIP Journal on Embedded Systems .

REFERÊNCIAS BIBLIOGRÁFICAS 53

Printista, Alicia Marcela, Marcelo Luis Errecalde & Cecilia Inés Montoya (2002), ‘Aparallel implemetation of q-learning based on cammunication with cache’.

Reyneri, Leonardo MAria (2003), ‘implementation issues of neuro-fuzzy hardware:Going toward hw/sw codesingn’, IEE Transactions On Neural Networks 14(1).

Saldanha, Hugo Vasconcelos (2012), Bionimbus: Uma arquitetura de federação de nuvenscomputacionais híbridas para execução do workflows de bioinformática, Dissertaçãode mestrado, Universidade de Brasília (UnB).

Shang, Li, Alireza S. Kaviani & Kasuma Bathala (2002), ‘Dynamic power consumptionin virtex-ii fpga family’, FPGA ’02 Proceedings of the 2002 ACM/SIGDA tenthinternational symposium on Field-programmable gate arrays .

Silva, Sérgio N. & Marcelo Augusto Costa Fernandes (2016), ‘Real-time simulator fordynamic systems using a fpga platform’, XXI Congresso Brasileiro de Automática .

Sutton, Richard S. & Andrew G. Barto (2012), Reinforcement Learning: An Introduction,second editiona edição, The MIT Press.

Tan, Ying, Wei Liu & Qinru Qiu (2009), Adaptive power management using reinforce-ment learning, em ‘International Conference on Coputer-Aided Design’.

Tang, Qing Yun (2016), FPGA Based Acceleration of Matrix Decomposition and Cluste-ring Algorithm Using High Level Synthesis, Tese de doutorado, University of Wind-sor, Ontario, Canada.

Torquato, Matheus Fernandes & Marcelo Augusto Costa Fernandes (2016), ‘Proposta deimplementação paralela de algoritmo genético em fpga’, XXI Congresso Brasileirode Automática .

Watkins, Christopher J. C. H. & Peter Dayan (1992), ‘Technical note: Q-learning’, Ma-chine Learning .

Woehrle, Hendrik & Frank Kirchner (2015), Reconfigurable Hardware-Based Accelera-tion for Machine Learning and Signal Processing, 1sta edição, Springer FachmedienWiesbaden, Wiesbaden.

Wu, Pei-Chi (1997), ‘Multiplicative, congruential random-number generators’, ACMTransactions on Mathematical Software, Vol. 23, No. 2 .

Xilinx-Inc (n.d.), http://www.xilinx.com.

Documents

Proposta de Arquitetura em Hardware para FPGA da Técnica Q-learning de … · Proposta de Arquitetura em Hardware para FPGA da Técnica Q-learning de Aprendizagem por Reforço Lucileide