Universidade de Aveiro Departamento de Electr(cid:19)onica, Telecomunicac(cid:24)~oes e Inform(cid:19)atica 2010 ~ Lu(cid:19)(cid:16)s Carlos IMPLEMENTAC(cid:24)AO EM FPGA DE ALGORITMOS Nobre de Almeida COMPUTACIONAIS PARALELOS Figueiredo Universidade de Aveiro Departamento de Electr(cid:19)onica, Telecomunicac(cid:24)~oes e Inform(cid:19)atica 2010 ~ Lu(cid:19)(cid:16)s Carlos IMPLEMENTAC(cid:24)AO EM FPGA DE ALGORITMOS Nobre de Almeida COMPUTACIONAIS PARALELOS Figueiredo Disserta(cid:24)c~ao apresentada (cid:18)a Universidade de Aveiro para cumprimento dos requesitos necess(cid:19)arios (cid:18)a obten(cid:24)c~ao do grau de Mestre em Engenharia Electr(cid:19)onica e Telecomunica(cid:24)c~oes, realizada sob a orientac(cid:24)~ao cient(cid:19)(cid:16)(cid:12)ca do ProfessorDoutorValeriSkliarov,ProfessorCatedr(cid:19)aticodoDepartamentode Electr(cid:19)onica, Telecomunica(cid:24)c~oes e Inform(cid:19)atica da Universidade de Aveiro,co- orientac(cid:24)~aocient(cid:19)(cid:16)(cid:12)cadaProfessoraDoutoraIouliiaSkliarova,Professoraaux- iliar do Departamento de Electr(cid:19)onica, Telecomunicac~oes e Inform(cid:19)atica da Universidade de Aveiro. o ju(cid:19)ri / the jury presidente / president Doutor Ant(cid:19)onio Manuel de Brito Ferrari Almeida Professor Catedr(cid:19)atico da Universidade de Aveiro vogais / examiners committee Doutor H(cid:19)elio Mendes de Sousa Mendon(cid:24)ca Professor Auxiliar da Faculdade de Engenharia da Universidade do Porto Doutor Valeri Skliarov Professor Catedr(cid:19)atico da Universidade de Aveiro (Orientador) Doutora Ioulia Skliarova Professora Auxiliar da Universidade de Aveiro (Co-Orientadora) agradecimentos / Queroagradeceraosmeusorientadores,Prof. ValerySkliaroveProf. Iouliia acknowledgements Skliarova, por me fornecerem a oportunidade e conhecimento, uma vez que sempre mostraram a disponibilidade necess(cid:19)aria para elaborac(cid:24)~ao desta tese. Quero agradecer aos meus pais, irm~aos e toda a fam(cid:19)(cid:16)lia que me acompan- hou e suportou a minha vida acad(cid:19)emica. Em u(cid:19)ltimo lugar, quero agradecer a todos os meus amigos que, de uma maneira ou de outra, me ajudaram neste percurso acad(cid:19)emico e essencial- mente pelos la(cid:24)cos de amizade que cri(cid:19)amos. Palavras-chave Field-Programmable Gate Array, m(cid:19)aquinas de estados (cid:12)nitos, multiplica(cid:24)c~ao de matrizes e vectores, s(cid:19)(cid:16)ntese de circuitos, simula(cid:24)c~ao visual. Resumo Nos u(cid:19)ltimos anos, tem-se assistido a um indiscut(cid:19)(cid:16)vel aumento da utiliza(cid:24)c~ao de sistemas recon(cid:12)gur(cid:19)aveis. Dentro destes sistemas, as FPGAs (Field- Programmable Gate Array) apresentam-se, assim, como um grande po- tencial, possibilitando a implementa(cid:24)c~ao de projectos de m(cid:19)edia/grande com- plexidade, tais como os algoritmos de manipula(cid:24)c~ao de dados. O tempo de execu(cid:24)c~ao e os recursos envolvidos s~ao, de longe, os factores mais impor- tantes a considerar. Nesta perspectiva, foi desenvolvida nesta tese uma im- plementa(cid:24)c~ao de um algoritmo de multiplica(cid:24)c~ao de matrizes e foi comparado o seu tempo de execu(cid:24)c~ao face (cid:18)a implementa(cid:24)c~ao em software. A imple- menta(cid:24)c~ao do algoritmo na FPGA, debru(cid:24)ca-se essencialmente em m(cid:19)aquinas deestados(cid:12)nitos, comointuitodeaproveitaroparalelismoquesepodeen- contrar neste tipo de dispositivos. Foi, tamb(cid:19)em, criada uma comunica(cid:24)c~ao entre um PC de uso geral com a placa FPGA por USB, de modo a ser poss(cid:19)(cid:16)vel a transmiss~ao de dados entre ambos. O sistema foi implementado e testado com ^exito, podendo-se observar os resultados da multiplica(cid:24)c~ao atrav(cid:19)es do monitor VGA, ou atrav(cid:19)es do PC. Keywords Field-Programmable Gate Array, (cid:12)nite state machine, multiplication of ma- trices and vectors, circuit synthesis, visual simulation. Abstract In the last few years, the rising use of recon(cid:12)gurable systems is indis- putable. ThesesystemsareusuallyconstructedonthebasisofFPGA(Field- Programmable Gate Array), which allow for the implementation of medium andhigh complexityalgorithms, such as data manipulation algorithms. The most important factors to consider are the execution time and the required resources. In this thesis, matrix multiplication algorithms were implemented in FPGA and the resulting execution time was compared with the respective imple- mentation in software. The implementation in FPGA aims at exploring parallelism as much as possible. Then a communication was established be- tween a host computer and an FPGA-based prototype board through USB system. The entire system was implemented and tested sucessfully. The multipli- cations results can either be seen an a VGA monitor or on the PC console application. Conteu(cid:19)do 1 Introdu(cid:24)c~ao 1 1.1 Enquadramento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivac(cid:24)~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Objectivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Organiza(cid:24)c~ao da Tese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Estado de arte 5 2.1 Implementa(cid:24)c~ao em FPGA de algoritmos computacionais paralelos . . . . . . 5 2.2 M(cid:19)aquinas de estados (cid:12)nitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.1 Introdu(cid:24)c~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.2 M(cid:19)aquinas de estados (cid:12)nitos hier(cid:19)arquicas . . . . . . . . . . . . . . . . . 7 2.2.3 M(cid:19)aquinas de estado (cid:12)nitos hier(cid:19)arquicas paralelas . . . . . . . . . . . . 8 2.3 Aplica(cid:24)co~es pr(cid:19)aticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Sistemas digitais recon(cid:12)gur(cid:19)aveis. . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.1 FPGA (Field Programmable Gate Array) . . . . . . . . . . . . . . . . 17 2.4.2 Aplica(cid:24)c~oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5 Fabricantes e placas de prototipagem . . . . . . . . . . . . . . . . . . . . . . . 19 2.6 Multiplica(cid:24)c~ao de matrizes e vectores . . . . . . . . . . . . . . . . . . . . . . . 22 2.6.1 De(cid:12)ni(cid:24)c~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.6.2 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.6.3 Implementac(cid:24)~oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.6.4 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.7 Multiplica(cid:24)c~ao de matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.7.1 De(cid:12)ni(cid:24)c~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.7.2 Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.7.3 Implementac(cid:24)~oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7.4 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.8 Conclus~oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3 Ferramentas de apoio 37 3.1 Linguagem de descri(cid:24)c~ao de Hardware (HDL) . . . . . . . . . . . . . . . . . . 37 3.2 VHDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 Descri(cid:24)c~ao estrutural . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.2 Descri(cid:24)c~ao comportamental . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.3 Xilinx Integrated Software Environment (ISE) WebPack . . . . . . . . . . . . 39 3.3.1 IP Cores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 i 3.4 ModelSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.5 Microsoft Visual Studio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.6 Digilent Adept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.7 Conclus~oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4 Arquitectura b(cid:19)asica do sistema implementado 45 4.1 Comunica(cid:24)c~ao entre FPGA e um computador de uso geral . . . . . . . . . . . 45 4.1.1 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.2 Arquitectura do sistema em hardware . . . . . . . . . . . . . . . . . . . . . . 49 4.3 Conclus~oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5 Implementac(cid:24)~ao dos algoritmos de multiplica(cid:24)c~ao de matrizes e vectores 59 5.1 Esquema geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2 Comunica(cid:24)c~ao USB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.3 Bloco controlador da RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.4 Bloco Multiplicador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.5 Bloco VGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.6 Conclus~oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6 Resultados 73 6.1 Arquitectura sequencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.2 Arquitectura paralela. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.3 Conclus~oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 7 Conclus~oes e trabalho futuro 81 A Lista de acr(cid:19)onimos 83 ii Lista de Tabelas 2.1 Recursos l(cid:19)ogicos da Spartan3E 1200. . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Macro-blocos na Spartan3E 1200. . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Avaliac(cid:24)a~o dos resultados feitos em [18]. . . . . . . . . . . . . . . . . . . . . . 34 2.4 Avaliac(cid:24)a~o dos resultados atingidos em [21] . . . . . . . . . . . . . . . . . . . 34 2.5 Desempenho do sistema utilizando o primeiro teorema [25]. . . . . . . . . . . 34 2.6 Desempenho do sistema utilizando o segundo teorema [25]. . . . . . . . . . . 35 2.7 Avaliac(cid:24)a~o dos resultados feitos em [33]. . . . . . . . . . . . . . . . . . . . . . 35 4.1 Sinais de controlo do interface USB. . . . . . . . . . . . . . . . . . . . . . . . 46 6.1 Tempo da multiplica(cid:24)c~ao matricial para uma arquitectura sequencial(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.2 Tempo da multiplica(cid:24)c~ao matricial para uma arquitectura paralela (primeira vers~ao) a 12,5 MHz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.3 Tempo da multiplica(cid:24)c~ao matricial para uma arquitectura paralela (segunda vers~ao) a 12,5 MHz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.4 Tempo da multiplica(cid:24)c~ao matricial para uma arquitectura paralela a (vers~ao (cid:12)nal) a 25 MHz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.5 Tempodamultiplica(cid:24)c~aomatricialparaumaarquitecturaparalela(vers~ao(cid:12)nal) a 25 MHz (para outras matrizes iniciais). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.6 Tempodamultiplica(cid:24)c~aomatricialparaumaarquitecturaparalela(vers~ao(cid:12)nal) a 30 MHz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.7 Tempodamultiplica(cid:24)c~aomatricialparaumaarquitecturaparalela(vers~ao(cid:12)nal) a 30 MHz (para outras matrizes iniciais). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 iii Lista de Figuras 1.1 Compara(cid:24)c~ao do pre(cid:24)co m(cid:19)edio de venda sobre o custos de volume [1]. . . . . . . 2 2.1 Aumento do nu(cid:19)mero de trans(cid:19)(cid:16)stores utilizados na FPGA ao longo do tempo [2]. 6 2.2 Ilustra(cid:24)c~ao de multitasking num sistema computacional. . . . . . . . . . . . . . 6 2.3 FSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 HFSM [29] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.5 PHFSM [29] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.6 Panorama industrial e o fosso para a tecnologia [3]. . . . . . . . . . . . . . . . 9 2.7 Acelera(cid:24)c~ao de algoritmos em FPGA [3]. . . . . . . . . . . . . . . . . . . . . . 9 2.8 Tempo de execu(cid:24)c~ao em ciclos de rel(cid:19)ogio, em software e hardware de opera(cid:24)c~oes de v(cid:19)(cid:16)rgula (cid:13)utuante na placa Nios [35]. . . . . . . . . . . . . . . . . . . . . . . 10 2.9 Tempo de execu(cid:24)c~ao de um processador para calcular a factoriza(cid:24)c~ao LU e os resultados pela substitui(cid:24)c~ao pela placa Nios [35]. . . . . . . . . . . . . . . . . 10 2.10 Dois CA-CFAR em paralelo em diferente ciclos de rel(cid:19)ogio [24]. . . . . . . . . 11 2.11 Estrutura de dos dois CA-CFAR em paralelo [24]. . . . . . . . . . . . . . . . 11 2.12 Resultados do desempenho usando uma FPGA ou apenas software no proces- samento de imagens m(cid:19)edicas [34]. . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.13 Formato dos dados de entrada [22]. . . . . . . . . . . . . . . . . . . . . . . . . 12 2.14 Esquema do algoritmo para ordena(cid:24)c~ao dos dados visto em [22]. . . . . . . . . 13 2.15 Sequ^encia do algoritmo paralelo da multiplica(cid:24)ca~o de matrizes [25]. . . . . . . 13 2.16 Estrutura dos elementos de processo segundo [25]. . . . . . . . . . . . . . . . 14 2.17 Imagem de uma PROM [4]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.18 Estrutura de uma PLA [5]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.19 Estrutura de um PAL [6]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.20 Exemplo de uma GAL [7]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.21 Estrutura de uma CPLD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.22 Arquitectura interna de uma FPGA [8]. . . . . . . . . . . . . . . . . . . . . . 18 2.23 Exemplos de aplica(cid:24)c~oes de utiliza(cid:24)c~ao das FPGAs [9]. . . . . . . . . . . . . . . 19 2.24 Compara(cid:24)c~ao das caracter(cid:19)(cid:16)sticas de FPGAs da Xilinx [10]. . . . . . . . . . . . 20 2.25 Diagrama de blocos da placa Nexis 2 [11]. . . . . . . . . . . . . . . . . . . . . 20 2.26 Nexis 2 [11]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.27 Esquema de um multiplicador embutido na FPGA [12]. . . . . . . . . . . . . 22 2.28 Diagrama do algoritmo da multiplicac(cid:24)~ao de uma matriz por um vector. . . . 24 2.29 Multiplica(cid:24)c~ao de uma Sparse matriz por um vector em pipeline [26]. . . . . . 25 2.30 Estrutura b(cid:19)asica do desenho para k = 4 [27]. . . . . . . . . . . . . . . . . . . 26 2.31 Desempenho em MFLOPS em fun(cid:24)c~ao da largura de banda da SDRAM [26]. . 27 2.32 Compara(cid:24)c~aododesempenhodoSMVMcomoutrossistemascomputacionais[26]. 27 v