Port de l'aplicació de bioinformàtica FTDock a la plataforma heterogènia ZYNQ

PORT DE L'APLICACIÓ DE BIOINFORMÀTICA FTDOCK A LA PLATAFORMA HETEROGÈNIA ZYNQ Autor: Marc Josep i Fabregó Grau en Enginyeria Informàtica Especialitat en Enginyeria de Computadors Gener de 2016 Director: Daniel Jiménez González Codirector: Carlos Álvarez Martínez Facultat d’Informàtica de Barcelona Universidad Politécnica de Catalunya – Barcelona Tech Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 2 Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 3 Resum En aquest treball es mostra el port de l’aplicació en bioinformàtica FTDock a una plataforma heterogènia formada per un multiprocessador i una FPGA, utilitzant els avantatges que ofereix l’ús d’acceleradors hardware en aquelles regions més crítiques del codi com són les transformades de Fourier. En primera instància s’exposen els objectius plantejats, informació relacionada amb el projecte per oferir uns coneixements bàsics referents al treball, un breu estat de l’art i la metodologia que s’emprarà. S’acompanya amb una previsió de recursos que s’utilitzaran al llarg del projecte, a nivell econòmic i temporal. A continuació es descriu els passos que s’han seguit per tal d’arribar al disseny final, i les modificacions aplicades a FTDock perquè pugui fer ús d’aquest disseny. Finalment s’exposen i analitzen els resultats derivats del projecte, juntament amb una mostra de possibles extensions que planteja el projecte com a treball futur. Resumen En este trabajo se muestra el puerto de la aplicación en bioinformática FTDock a una plataforma heterogenia formada por un multiprocesador y una FPGA, utilizando las ventajas que ofrece el uso de aceleradores hardware en aquellas regiones más críticas del código como son las transformadas de Fourier. En primera instancia se exponen los objetivos planteados, información relacionada con el proyecto para ofrecer unos conocimientos básicos referentes al trabajo, un breve estado del arte y la metodología que se emprará. Se acompaña con una previsión de recursos que se utilizarán a lo largo del proyecto, a nivel económico y temporal. A continuación se descrive los pasos que se han seguido para llegar al diseño final, y las modificaciones aplicadas a FTDock para que pueda utilizar dicho diseño. Finalmente se exponen y analizan los resultados derivados del proyecto, junto a una muestra de posibles extensiones que plantea el proyecto como trabajo futuro. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 4 Abstract On this work we show the port from the application in bioinformatics FTDock to an heterogeneous platform which features a multiprocessor and an FPGA, taking advantage of hardware accelerators on critical code regions such as Fourier transforms. At the first place we expose our goals, some information related to the project in order to offer some basic knowledge related to our work, a brief state of the art and the methodology we are going to use. It will be followed by a prediction of the resource usage along the project, both in an economic and temporal level. We will describe all the steps we have followed in order to achieve the final hardware design, and the modifications we have applied to FTDock so it cans use this design. Finally we expose and analyse the results obtained from the project, along with a som possible additions that the project raises as future work. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 5 Índex 1. Introducció .................................................................................................................... 8 1.1 Objectiu i motivació ............................................................................................... 8 1.2 Abast ....................................................................................................................... 8 1.3 Termes i conceptes .................................................................................................. 8 1.4 Actors implicats ...................................................................................................... 9 1.5 Estat de l’art .......................................................................................................... 10 1.6 Plec de condicions ................................................................................................. 11 1.7 Eines de treball ...................................................................................................... 11 1.8 Obstacles i riscos .................................................................................................. 12 1.9 Metodologia i rigor ............................................................................................... 13 2. Planificació temporal .................................................................................................. 15 2.1 Planificació del projecte ....................................................................................... 15 2.2 Cost temporal final ............................................................................................... 18 3. Pressupost ................................................................................................................... 22 3.1 Control de gestió ................................................................................................... 22 3.2 Estimació de costos en recursos humans .............................................................. 22 3.3 Estimació de costos en amortitzacions ................................................................. 22 3.4 Estimació de costos indirectes .............................................................................. 22 3.4 Estimació de costos finals .................................................................................... 22 4. Sostenibilitat i compromís social ................................................................................ 28 5. FTDock ....................................................................................................................... 29 5.1 Acoblament molecular .......................................................................................... 29 5.2 Algoritme .............................................................................................................. 29 Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 6 5.2 Descripció de l’algoritme ..................................................................................... 29 6. Descripció de una FPGA i la màquina Zynq .............................................................. 31 6.1 FPGA .................................................................................................................... 31 6.2 Zynq-7000 ............................................................................................................ 31 6.3 Entorn de treball amb Zynq .................................................................................. 33 7. Porting de FTDock a la Zynq ..................................................................................... 37 7.1 Anàlisi de FTDock ................................................................................................ 37 7.2 DFT, FFT i FFTW ................................................................................................ 39 7.3 FFT en 3D utilitzant FFTs en 1D .......................................................................... 40 7.4 Disseny del hardware accelerador ........................................................................ 43 7.5 Paral·lelització del codi ........................................................................................ 44 8. Implementació de FTDock ........................................................................................ 46 8.1 Implementacions hardware ................................................................................... 46 8.2 Implementació software ....................................................................................... 52 9. Entorn de treball ......................................................................................................... 54 9.1 Desenvolupament software................................................................................... 54 9.1.1 Creació i edició de codi ..................................................................................... 54 9.2 Desenvolupament hardware ................................................................................. 55 10. Resultats obtinguts .................................................................................................... 56 10.1 Fast Fourier Transform 1D ................................................................................. 56 10.2 Fast Fourier Transform 3D ................................................................................. 59 10.3 FTDock ............................................................................................................... 61 10.4 Estimació de temps d’execució total .................................................................. 63 11. Possibles extensions del projecte .............................................................................. 66 Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 7 11.1 Ús d’acceleradors hardware en altres regions crítiques ...................................... 66 11.2 Millora de l’assignació de memòria per a DMA ................................................ 66 11.3 Exportació a altres programes i plataformes ...................................................... 67 12. Conclusions .............................................................................................................. 68 13. Bibliografia ............................................................................................................... 69 Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 8 1. Introducció 1.1 Objectiu i motivació L'algoritme de bioinformàtica FTDock forma part d’un conjunt de programes, anomenat 3D-Dock, que permeten prediccions d’acoblament entre molècules. L'execució d'aquest algoritme consumeix una gran quantitat de temps. L'objectiu d'aquest projecte és la reducció del temps d'execució de l'algoritme, mitjançant un port a una plataforma heterogènia, com és Zynq, desenvolupada per l'empresa Xilinx. Aquesta plataforma consta d'un multiprocessador simètric (SMP) i una FPGA (Field Programmable Gate Array), que podrem utilitzar com a accelerador hardware. 1.2 Abast Per tal de poder millorar el rendiment en l'execució de FTDock i realitzar-ne el port a la plataforma Zynq, modificarem i distribuirem el programa original per tal d'aprofitar al màxim possible el multiprocessador i la FPGA que ofereix la placa. L'enfocament inicial que es vol donar al projecte consisteix en l'execució de les transformades de Fourier que requereix l'algoritme en la FPGA, i que consumeixen una important part del temps, i la resta del programa serà executat en el multiprocessador. A més, la part de codi executada en el multiprocessador explotarà el paral·lelisme en aquelles parts on sigui possible mitjançant l'ús de pthreads. No obstant això, si altres fragments del codi es creu oportú que la seva execució mitjançant acceleradors hardware pot ser favorable, s’estudiarà la possibilitat d’incorporar-li. Un altre objectiu que ens plantegem és estudiar i treballar amb la connexió que tenim entre el multiprocessador i la FPGA. 1.3 Termes i conceptes 1.3.1 FTDock Algoritme bioinformàtic que permet el càlcul dels millors acoblaments possibles entre dues molècules, oferint unes ponderacions en funció de diferents factors de cada molècula. 1.3.2 Acoblament proteïna-proteïna Computació de l’acoblament entres dues proteïnes, intentant simular amb la màxima precisió possible respecte com es donaria aquest procés en un organisme viu. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 9 1.3.3 Zedboard Placa de Xilinx a on farem port del codi de FTDock. Disposa de un multiprocessador i de una FPGA, a part de xarxes de comunicació, dispositius de configuració, eines d’entrada/sortida entre d’altres. 1.3.4 Field Programable Gate Array (FPGA) Circuit integrat que permet a l’usuari la seva configuració hardware, des de portes lògiques simples (com AND o OR), fins a blocs funcionals complexos, juntament amb elements de memòria. La seva configuració es pot especificar mitjançant llenguatges de descripció de hardware. 1.3.5 Multiprocessador Un multiprocessador o processador multi-core és un sol processador que disposa de dues o més unitats de processament, és a dir, varis cores o CPUs (Central Processing Unit). Disposar de múltiples cores permet l’execució simultània de múltiples instruccions i obtenint així el que coneixem com a computació paral·lela. Això permet una execució en menys temps i un consum més reduït d’energia, però alhora implica unes necessitat de comunicació entre cores. 1.3.6 Transformada de Fourier Transformada matemàtica que permet la descomposició d’un conjunt de mostres d’una funció en components amb diferents freqüències. Sovint abreviada com a DFT. 1.4 Actors implicats 1.4.1 Desenvolupador Seré l’únic desenvolupador del projecte, amb la tasca de generar tota la documentació (prèvia i posterior) del projecte, així com tota la feina d’optimització i port de l’aplicació. 1.4.2 Director i codirector Encarregats de supervisar i encaminar el projecte, i de guiar al desenvolupador per tal d’ajudar a garantir la finalització correcta del projecte. Aquests rols són assumits per Daniel Jiménez González i Carlos Álvarez Martínez respectivament. 1.4.3 Desenvolupadors del codi original Els desenvolupadors del codi original poden veure’s interessats per aquest projecte per tal de generar una nova versió millorada. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 16 Hores estimades Hores reals 70 70 Aquesta fase del projecte no ha vist modificada la seva planificació inicial. La presència de terminis molt clars i tenir uns objectius a assolir amb molt poc marge de variació i sense marge d’error, fa d’aquesta una etapa on les desviacions eren difícils d’esperar. 2.1.2 Familiarització amb el programa i anàlisi L’objectiu d’aquesta etapa és conèixer el contingut i estructura del programa amb el qual treballarem, i analitzar-lo per tal d’obtenir informació valuosa per a les següents etapes. Inclou la instal·lació i comprensió del programa, així com dels paràmetres que accepta. Actualització de llibreries i anàlisi detallat. Gràcies a aquest anàlisi, podrem identificar quines són les regions crítiques del codi, per tal de poder tenir millores més significatives. Hores estimades Hores reals 50 50 Aquesta etapa s’ha aconseguit acomplir amb el marge de temps estimat inicialment, malgrat que la seva data d’inici fou més tard que la prevista. Com la fase anterior tenia uns objectius marcats amb poc marge de variació i d’error. 2.1.3 Optimització del programa Optimització del codi a executar en el multicore A partir de la informació obtinguda en l’etapa anterior, millorar el rendiment del programa per a executar en un sistema multicore. Aplicarem optimitzacions apreses a l’assignatura de Programació Conscient de l’Arquitectura (PCA), i també modificarem el codi amb crides la llibreria pthreads, per tal d’habilitar l’execució paral·lela tal com hem après a les assignatures de Paral·lelisme (PAR) i Programació d’Arquitectures Paral·leles (PAP). Per tal d’aplicar aquestes millores i per tal de garantir al màxim possible l’absència d’errors i bugs¸ emprarem la metodologia descrita anteriorment. Aquestes millores no s’aplicaran a la part de l’algoritme que inclou les transformades de Fourier. Hores estimades Hores reals 70 30 Aquesta etapa ha vist reduït el seu temps real respecte l’estimació inicial. Això és degut als resultats obtinguts en l’anàlisi, que apuntaven a una necessitat en donar més èmfasi en les etapes posteriors. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 17 Adaptació del codi a executar en la FPGA Adaptació del codi que inclou el càlcul de transformades de Fourier per tal de que es pugui executar en una FPGA. Això implica el disseny d’un hardware que permeti l’execució de transformades de Fourier. També s’explorarà la possibilitat de disposar de múltiples instàncies d’aquest hardware per poder-los executar simultàniament i obtenir així un millor rendiment. Es tracta d’una etapa complexa, en la qual la detecció d’errors és molt més complicada degut a la tipologia de la programació i el disseny hardware. Serà l’etapa central del projecte. Hores estimades Hores reals 240 850 Aquesta fase, eix central del projecte, ha suposat una de les desviacions més importants en el projecte i la causa més destacada de l’endarreriment del termini. S’han realitzat moltes modificacions respecte al plantejament inicial, suposant un cost temporal molt elevat per a cada proposta, a part de constar de moltes sub-etapes addicionals no previstes inicialment. 2.1.4 Integració entre el codi de multicore i de FPGA En aquesta etapa establirem la comunicació entre el multicore i la FPGA. Integrarem les dues subetapes anteriors per tal que el programa pugui utilitzar l’accelerador hardware generat en l’etapa anterior per executar les transformades de Fourier. Comprovarem el funcionament correcte del conjunt i analitzarem les millores en rendiment obtingudes. Hores estimades Hores reals 70 500 Una altra de les etapes que ha suposat un cost temporal addicional en l’assoliment del termini. Com l’etapa anterior, ha implicat moltes més tasques que les que es van augurar en el primer plantejament. Per altra banda, s’ha pogut solapar amb l’etapa anterior malgrat que inicialment no es contemplava aquesta possibilitat. Addicionalment, la quantitat de tests que s’ha realitzat ha estat molt major a l’esperat inicialment, degut a la gran quantitat de passos intermedis fins a l’assoliment del resultat final, que també s’han volgut avaluar independentment per poder veure el seu impacte. 2.1.5 Finalització del projecte Darrera etapa del projecte, en la qual redactarem l’informe definitiu, exposant els resultats obtinguts, i prepararem l’exposició final del projecte. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 18 Hores estimades Hores reals 50 100 A diferència de com ho havíem plantejat inicialment, hem pogut solapar aquesta etapa en les anteriors, i així tenir una càrrega menor sobre aquest punt en els darrers dies del projecte. Podríem considerar que de les 100 hores reals que hi hem dedicat, aproximadament la meitat s’ha donat durant el transcurs del projecte, mentre que l’altra meitat s’ha donat en l’etapa final. 2.2 Cost temporal final A la taula 2.1 podem veure el cost temporal del conjunt del projecte i de les seves subetapes, distingint les hores estimades inicialment i les hores que s’hi ha destinat finalment. A la figura 2.1 podem veure el diagrama de Gantt que mostra la planificació inicial, mentre que les figures 2.2.1 i 2.2.2 mostren el diagrama de Gantt de la planificació final. Etapa Hores estimades Hores reals Definició i planificació del projecte (GEP) 70 70 Familiarització amb el programa i anàlisi 50 50 Optimització del programa 310 880 Optimització del codi a executar en el multicore 70/310 30/880 Adaptació del codi a executar en la FPGA 240/310 850/880 Comunicació entre multicore i FPGA 70 500 Finalització del projecte 50 100 Total 550 hores 1.600 hores Taula 2.1: Duració del projecte Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 19 Figura 2.1: Diagrama de Gantt de la planificació inicial Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 20 Figura 2.2.1: Diagrama de Gantt de la planificació final -1 Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 21 Figura 2.2.2: Diagrama de Gantt de la planificació final - 2 Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 22 3. Pressupost 3.1 Control de gestió Per tal de fer una bona gestió del pressupost disponible, s’ha revisant a cada etapa que ens hi ajustem. Aquestes revisions principalment consten del nombre d’hores dedicades per etapa, ja que com veurem és el cost més significatiu que tenim al projecte. Els costs d’adquisicions i amortitzacions serà molt reduït degut a donacions o a la utilització de programes d’ús gratuït. Tenint en compte que el principal cost que teníem en el pressupost era la quantitat d’hores de dedicació, i veient que aquesta quantitat s’ha vist incrementada substancialment respecte la primera previsió, trobem una important desviació respecte el pressupost inicial. 3.2 Estimació de costos en recursos humans Malgrat que el projecte sigui desenvolupat per una sola persona, aquesta persona assumirà diferents rols en el projecte, i per tant haurem de distingir aquest rols entre les hores dedicades i el seu cost per hora. D’aquesta manera, el preu per hora treballada serà diferent en funció del rol que assumim. La taula 3.1 mostra els costos destinats en recursos humans. 3.3 Estimació de costos en amortitzacions Tindrem la necessitat d’alguns components hardware i software, i el seu cost es calcularà en funció de la seva amortització. La taula 3.2.1 i 3.2.2 mostra els costos destinats a aquestes amortitzacions. La placa Zedboard i el conjunt de software Vivado Design Suite són donatius de Xilinx sota el Xilinx University Program. És per això que no repercuteixen en el cost de les amortitzacions. 3.4 Estimació de costos indirectes Per al càlcul dels costos indirectes únicament tindrem en compte la despesa de la llum per alimentar els ordinadors i la placa que utilitzarem. La taula 3.3 mostra els costos indirectes derivats del projecte. 3.4 Estimació de costos finals La taula 3.4 mostra el cost final del projecte, tenint en compte una contingència del 15%. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 23 Etapa Rol Preu per hora Hores estimades Hores reals Cost estimat Cost real Desviació Definició i planificació del projecte Cap de projecte 25€/h 70h 70h 1.750€ 1.750€ 0€ Total - 70h 70h 1.750€ 1.750€ 0€ Familiarització amb el programa i anàlisi Analista 22,5€/h 50h 50h 1.125€ 1.125€ 0€ Total - 50h 50h 1.125€ 1.125€ 0€ Optimització del programa Cap de projecte 25€/h 10h 30h 250€ 750€ 500€ Desenvolupador 18,5€/h 250h 600h 4.625€ 11.100€ 6.475€ Tester 19€/h 50h 200h 950€ 3.800€ 2.850€ Total - 310h 830h 5.825€ 15.650 9.825 Comunicació entre multicore i FPGA Cap de projecte 25€/h 5h 20h 125€ 500€ 375€ Desenvolupador 18,5€/h 50h 410h 925€ 7.585€ 6.660€ Tester 19€/h 15h 70h 285€ 1.330€ 1.045€ Total - 70h 500h 1.335€ 9.415€ 8.080€ Finalització del projecte Cap de projecte 25€/h 50h 100h 1.250€ 2.500€ 1.250€ Total 50h 100h 1.250€ 2.500€ 1.250€ TOTAL RECURSOS HUMANS - - 550 hores 1.600 hores 11.285€ 30.440€ 19.155€ Taula 3.1: Estimació de costos en recursos humans Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 24 Etapa Producte Preu unitat Vida útil Període estimat Període real Cost estimat Cost real Desviació Definició i planificació del projecte Ordinador de sobretaula 926,81 4 anys 1 mes 1 mes 19,31 € 19,31 € 0 € Ordinador portàtil 950 € 5 anys 1 mes 1 mes 15,83 € 15,83 € 0 € Microsoft Office 2010 79 € 3 anys 1 mes 1 mes 2,19 € 2,19 € 0 € Open Office 0 € - - - 0 € 0 € 0 € Windows 8.1 Professional 279 € 3 anys 1 mes 1 mes 7,75 € 7,75 € 0 € Ubuntu 14 0 € - - - 0 € 0 € 0 € Total - - - - 45,08 € 45,08 € 0 € Familiarització amb el programa i anàlisi Ordinador portàtil 950 € 5 anys 1 mes 1 mes 15,83 € 15,83 € 0 € Ubuntu 14 0 € - - - 0 € 0 € 0 € FTDock 0 € - - - 0 € 0 € 0 € FFTW 0 € - - - 0 € 0 € 0 € Total - - - - 15,83 € 15,83 € 0 € Optimització del programa Ordinador portàtil 950 € 5 anys 1 mes 8 mesos 15,83 € 126,67€ 110,84 € Ubuntu 14 0 € - - - - - 0 € FTDock 0 € - - - - - 0 € Vivado Design Suite 2.675,80 € 2 anys 2 mesos 8 mesos 0 € 0 € 0 € Zedboard 305 € 4 anys 2 mesos 8 mesos 0 € 0 € 0 € Total - - - - 15,83 € 126,67€ 110,84 € Taula 3.2.1: Estimació de costos en amortitzacions-1 Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 25 Taula 3.2.1: Estimació de costos en amortitzacions-2 Etapa Producte Preu unitat Vida útil Període estimat Període real Cost estimat Cost real Desviació Comunicació entre multicore i FPGA Ordinador portàtil 950 € 5 anys 1 mes 4 mesos 15,83 € 63,33 € 47,50 € Ubuntu 14 0 € - - - - - 0 € FTDock 0 € - - - - - 0 € Vivado Design Suite 2.675,80 € 2 anys 1 mes 4 mesos 0 € 0 € 0 € Zedboard 305 € 4 anys 1 mes 4 mesos 0 € 0 € 0 € Total 3.626 € - - - 15,83 € 63,33 € 47,50 € Finalització del projecte Ordinador de sobretaula 926,81 4 anys 15 dies 1 mes 9,65 € 19,31 € 9,66 € Ordinador portàtil 950 € 5 anys 15 dies 1 mes 7,91 € 15,83 € 7,92 € Microsoft Office 2010 79 € 3 anys 15 dies 1 mes 1,09 € 2,19 € 1,1 € Open Office 0 € - - - 0 € 0 € 0 € Windows 8.1 Professional 279 € 3 anys 15 dies 1 mes 3,87 € 7,75 € 3,88 € Ubuntu 14 0 € - - - 0 € 0 € 0 € Total - - - - 22,52 € 45,08 € 22,56 € TOTAL AMORTITZACIONS - - - - - 115,09 € 295,99 € 180,9 € Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 32 6.2.1 CPU El processador que utilitza és un Dual ARM Cortex-A9 MPCore with CoreSight, format per dos microprocessadors d’arquitectura ARM. El multiprocessador pot funcionar com a un únic processador, processador simètric dual o processador asimètric dual. Suporta NEON, que permet l’execució d’instruccions SIMD (Single Instruction, Multiple Data) en ARM, i operacions amb coma flotant simple i doble amb capacitat de fins a 2.0 MFLOPS/MHz per a cada core. Disposa de 256KB de memòria on-chip, accessible des de la CPU i la lògica programable, i interfícies de 16 i 32 bits per a DDR3, DDR3L, DDR2 i LPDDR2. Té interfícies d’entrada i sortida de tipus Ethernet MAC, USB 2.0, CAN 2.0B, SD/SDIO, SPI, UART, I2C i GPIO. Suporta interrupcions i temporitzadors (timers). 6.2.2 FPGA La FPGA que utilitza és una Artix-7 FPGA, amb 85.000 cèl·lules de lògica programable, 53.200 taules de cerca (Look-Up Tables) i 106.400 Flip-flops. Accés a 36Kb de memòria RAM a través de dos ports. 6.2.3 Interfície PS-PL Es disposa de una interfície ACP (Accelerator Coherency Port) que permet una connexió ràpida entre PS (Processing System) i PL (Programmable Logic). Aquesta interfície ens permetrà a l’accés de la memòria del processador des del PL a través de DMAs (Direct Memory Access), que en pot suportar fins a 4. A la figura 6.1 es mostra l’arquitectura del xip Zynq-7000. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 33 Figura 6.1: Arquitectura del xip Zynq-7000 6.3 Entorn de treball amb Zynq A l’hora de treballar amb Zynq es plantegen dues possibilitats: una execució standalone o una execució amb sistema operatiu. Un sistema standalone o bare-metal és aquell que no utilitza un sistema operatiu al complet. Utilitza els recursos mínims d’un sistema per tal de carregar el programa i executar-lo en el processador. Evita les petites quantitats de throughput que pot consumir un sistema operatiu, tot i que aquest overhead avui en dia es pot considerar negligible. Simplifica el sistema, però té més limitacions. L’altra opció és la utilització de un sistema operatiu. Ha de ser un sistema operatiu Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 34 lleuger i pensat per a les limitacions del microprocessador. L’ús de sistema operatiu afegeix una petita sobrecàrrega en el sistema, però pot agilitzar i simplificar moltes tasques. Ens decantarem per la opció del sistema operatiu. Per una banda, podrem treballar des d’un entorn més familiar, que ens facilitarà operacions com la compilació mitjançant l’ús de llibreries, o l’execució de programes amb els paràmetres i arxius d’entrada desitjats. També ens permetrà una gestió de la paral·lelització del codi i accés a les dades de la targeta SD. Per altra banda, hem d’utilitzar drivers de suport de DMA, compiladors creuats (cross-compilers) i crear un sistema específic per cada hardware. 6.3.1 PetaLinux Utilitzarem una distribució de Linux denominada PetaLinux, creada per Xilinx especialment per als seus productes. Mitjançant PetaLinux Tools, proveït de manera gratuïta per Xilinx, permet la configuració i creació d'una imatge del sistema operatiu. Aquí especificarem la placa destí i el hardware que la FPGA utilitzarà. Generarem aquest PetaLinux de manera que es pugui instal·lar a la targeta SD que disposa la placa, i la configurarem de manera que arranqui a partir de la SD. Utilitzarem el port sèrie UART de la placa per tal de monitoritzar i interactuar amb el sistema operatiu, a través d'un emulador de terminal (com Minicom, PuTTY o TeraTerm). 6.3.2 Generació de PetaLinux Generarem un PetaLinux específic per a cada hardware. Malgrat que es pot modificar el hardware que utilitza el sistema operatiu en temps d’execució, algunes característiques no es veuen modificades i és per això que preferim aquesta opció. Per tal de generar el PetaLinux, primer necessitem el BSP (Board Support Package) específic de la placa que tenim. Aquest paquet inclou tot el software referent al hardware necessari per al sistema operatiu. A partir d’aquí generarem un projecte especificant l’arquitectura del nostre xip (Zynq en el nostre cas). A continuació exportarem la descripció del hardware que hem dissenyat a Vivado i configurarem el sistema operatiu. Nosaltres hem utilitzat sempre la configuració per defecte. Un cop configurat i amb el hardware exportat, podem procedir a la generació del PetaLinux. És aquí on es crea la imatge del sistema operatiu i el device tree. El device tree és una estructura de dades que conté la descripció del hardware, i la informació que llegirà el sistema operatiu per tal de ser conscient de quin hardware disposa. L’últim component necessari per al PetaLinux és el BOOT.bin. Aquest arxiu conté el gestor d’arrancada (bootloader) del sistema operatiu i el bitstream. Tots aquests components s’han de copiar a la targeta SD que inserirem a la seva ranura Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 35 de la placa i modificarem els jumpers per tal que el sistema arranqui des de la targeta, tal com mostrem a la figura 6.2.1. Per altra banda, per tal que funcioni en mode standalone, s’haurà de configurar com la figura 6.2.2. Figura 6.2.1: configuració per a S. O. Un cop arranquem la placa amb la informació del sistema operatiu a la targeta SD, ens hi connectarem mitjançant un emulador de terminal (Minicom en el nostre cas), i ens trobarem amb el prompt de U-boot. Haurem de configurar el bootloader perquè carregui el sistema des de la targeta i finalment podrem accedir al sistema operatiu. Si un cop en el sistema operatiu volem accedir a la informació de la targeta, haurem de muntar el dispositius mitjançant la comanda mount. 6.3.3 Driver de DMA Utilitzarem uns drivers per controlar les DMAs que ens permetran fer la transmissió de dades entre el PS i el PL i viceversa. Xilinx no ofereix suport per a aquest tipus d’operació des de PetaLinux, i és per això que fem servir una llibreria externa externs, disponible a GitHub gràcies a l'usuari “Berin Martini” 1 . Utilitzarem la darrera versió disponible a novembre de 2015 (commit de l'autor el febrer de 2015), que disposa de funcions per assignar memòria a les dades que transmetre a través de DMA, determinar el número de DMA que tenim o realitzar transaccions amb el DMA, entre d’altres. Per a la instal·lació dels drivers cal compilar la llibreria utilitzant un cross-compiler per a ARM. Cal copiar la llibreria en la targeta SD que fem servir a la placa, i carregar el mòdul en el kernel amb el Linux corrent per tal de poder-ne fer ús. Principalment farem ús de tres funcions d’aquesta llibreria: una funció d’inicialització, que detecta i inicialitza els dispositius DMA que tenim en el hardware a partir del device tree i mapeja l’àrea de memòria a la qual accedirem des del DMA; una funció 1 https://github.com/bmartini/zynq-xdma Figura 6.2.2: Configuració per a standalone Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 36 d’assignació de memòria en aquesta regió; i finalment una funció per tal de realitzar les transaccions amb el dispositiu DMA. Aquesta darrera funció ens permet especificar a quin dispositiu DMA accedim i si la comunicació és unilateral o bilateral. L’ús d’aquesta funció especial d’assignació de memòria, assigna una regió de memòria que té un cost d’accés molt més elevat que si utilitzéssim memòria assignada mitjançant malloc. Aquesta assignació de memòria, però, és necessària per poder accedir a les dades a través DMA. Tot i aquest cost addicional, també la utilitzarem per a les dades que no requereixen enviament a DMA (com és el cas de les execucions de FFTW) per tal d’obtenir una comparació de temps sota les mateixes condicions. Tindrem en compte aquesta darrera consideració a l’hora d’avaluar els resultats, ja que pot donar lloc avaluacions distorsionades. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 37 7. Porting de FTDock a la Zynq 7.1 Anàlisi de FTDock Després de veure l’estructura que té FTDock, hem fet un anàlisi del temps que ocupen les diferents regions de codi, per tal de poder veure quin són els punts crítics del programa. D’entrada, ja podem preveure que la part més costosa del programa serà el bucle de rotacions de la molècula B. Fent un anàlisi en una execució amb únicament 50 rotacions en el nostre PC mitjançant gprof obtenim el resultat mostrat a la figura 7.1. Figura 7.1: Anàlisi de FTDock mitjançant gprof Aquí podem veure que les funcions que consumeixen més temps són les relacionades amb la llibreria FFTW i l’execució de FFT. A més, podem veure que les dues que consumeixen més temps són les de les FFT forward i backward, que trobem a dins del bucle. Els següents anàlisis han estat realitzats ja a la placa Zedboard utilitzant FFTW, i les funcions gettimeoday de la llibreria de sistema time per obtenir-ne els temps. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 38 Figura 7.2: Temps de bucle de FTDock A la figura 7.2 mostrem el temps que representa el bucle de FTDock respecte el conjunt del programa. Notis que l’eix que representa el temps comença a 350 micro-segons, per tal de poder veure la presència del temps d’inicialització i finalització. Aquesta prova s’ha realitzat per a un total de 50 rotacions, i en aquest cas el bucle ja representa un 98,7% del total del programa. En una execució completa del programa (més de 9.000 rotacions), el temps de inicialització i finalització seria totalment negligible, i per tant només el de bucle seria representatiu. Figura 7.3: Temps d’una rotació de FTDock A la figura 7.3 podem veure el pes que tenen les diferents funcions dintre de cada rotació del bucle de FTDock (veure la figura 5.1 per recordar l’estructura del bucle). Podem adonar-nos que el conjunt de les dues FFT, una directa i una altra inversa, 350 370 390 410 430 450 Temps en microsegons Temps de FTDock Inicialització + finalització Bucle 0 2000000 4000000 6000000 8000000 10000000 Temps en microsegons Temps d'una rotació del bucle de FTDock Rotació + Convolució + Avaluació FFT C2R FFT R2C Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 39 suposen més de la meitat del temps d’execució, vora un 66%, mentre que el conjunt d’operacions restants consumeixen el 34% restant del temps. És per això que centrarem el nostre objectiu en accelerar les FFT, que en una execució completa representarien vora el 66% del temps d’execució del programa. També veiem que el següent punt rellevant és el conjunt de les operacions de rotació, convolució i avaluació, que analitzaríem per separat i en més profunditat en el cas d’un treball futur en aquest sentit. 7.2 DFT, FFT i FFTW Per als càlculs de complementarietat de les superfícies, l’algoritme utilitza transformades de Fourier (DFT) per tal d'agilitzar el procés, a través de la llibreria de subrutines FFTW. La transformada ràpida de Fourier (FFT o Fast Fourier Transform) és l’algoritme que utilitza la llibreria FFTW (Fastest Fourier Transform in the West) per tal de calcular les DFT. Per tant, convé distingir els termes i sigles:  Transformada discreta de Fourier o transformada de Fourier (DFT): transformada matemàtica que permet la descomposició d’un conjunt de mostres d’una funció en components amb diferents freqüències. Podem distingir entre DFT directa (forward) i inversa (backward).  Transformada ràpida de Fourier (FFT): algoritme que computa una DFT. Degut a la similitud amb el concepte anterior, sovint els utilitzarem indistintament.  Fastest Fourier Transform in the West (FFTW): llibreria que utilitza FTDock per al càlcul de les FFT. A més, dintre de les FFT, farem algunes distincions:  FFT de reals a complexes (R2C FFT): FFT directa que pren per entrada valors reals i que retorna valors complexos, formats per una part real i una imaginària.  FFT de complexes a reals (C2R FFT): FFT inversa que pren per entrada valors complexos i que retorna valors reals.  FFT de complexes a complexes (C2C FFT): FFT que tant la seva entrada com la seva sortida pren valors complexes. Pot ser tant directa com inversa.  FFT en una dimensió (1D FFT): FFT que opera amb valors al llarg de una única dimensió.  FFT en tres dimensions (3D FFT): FFT que opera amb valors al llarg de tres dimensions. Més endavant veurem el funcionament que té aquest tipus de FFT. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 40 El tipus de les dades d’entrada i sortida a la FFT és independent de les dimensions amb les que opera. A cada iteració s’aplica una FFT de reals a complexes a la molècula mòbil, i es realitza una convolució entre els valors complexes de la molècula estàtica i la molècula mòbil. Això consisteix en el producte de matrius entre el conjugat complex de la molècula A i la molècula B. A els valors complexes resultants s’hi aplica una FFT de complexes a reals, i del resultat se n’extreuen un conjunts de valors que suposaran la puntuació de la rotació. Per tant, per a cada iteració tindrem una FFT R2C, una FFT C2R, una convolució entre complexes i l’obtenció de puntuacions. 7.3 FFT en 3D utilitzant FFTs en 1D FTDock opera amb dades estructurades en dos arrays, cada un està distribuït en tres dimensions. Les dades amb les que operen ambdues arrays són nombres reals, representats utilitzant coma flotant de precisió simple, és a dir, floats. Una d'aquestes arrays és estàtica, mentre que l'altre és mòbil. A l'array estàtica executarem una única FFT en 3 dimensions, on obtindrem nombres complexes a partir de l'entrada real. A l'array mòbil executarem una FFT en 3 dimensions, també amb entrada real i sortida complexa, però en aquest cas l'executarem un cop per a cada iteració. Del resultat d'aquesta FFT, juntament amb el resultat de la que ja haurem realitzat per a l'array estàtica, en realitzarem una convolució, que FTDock utilitza per assignar una puntuació a la rotació. Al final de cada iteració, a l'array de complexes que hem obtingut de l'array mòbil, realitzarem una FFT inversa, també en 3 dimensions, però en aquest cas amb entrada de complexes i sortida de reals. Ara bé, les transformades que podem executar en hardware són únicament en una dimensió, i utilitzen únicament entrada i sortida de nombres complexes. Per poder utilitzar el hardware, s'ha modificat el codi de FTDock per tal que utilitzi transformades en una dimensió. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 41 Una FFT en tres dimensions equival a realitzar FFT en una dimensió per a tota l'array, al llarg de cada un dels eixos. És a dir, per cada pla Nx x Ny, Ny FFT al llarg de la dimensió x; per cada pla Ny x Nz, Nz FFT al llarg de l'eix y; i finalment per a cada pla Nz x Nx, Nx FFT al llarg de l'eix z. Veure figura 7.4. Per tal de passar a l'IP core un stream de dades que sigui continu, després de realitzar una FFT al llarg d'un eix, realitzarem una transposició dels plans per tal que sempre treballem amb l'eix x. Per tant, l'algoritme que utilitzem serà el següent per a FFT directa en tres dimensions de reals a complexes serà el següent [9]:  Per cada pla Nx x Ny, Ny FFT 1D de reals a complexes, al llarg de l'eix x.  Transposició de cada pla Nx x Ny.  Per cada pla Nx x Ny, Ny FFT 1D de complexes a complexes, al llarg de l'actual eix x (original eix y).  Transposició de cada pla Nx x Nz.  Per cada pla Nx x Ny, Ny FFT 1D de complexes a complexes, al llarg de l'actual eix x (original eix z).  Transposició de cada pla Nx x Nz (opcional).  Transposició de cada pla Nx x Ny (opcional). De manera similar, l'algoritme que utilitzem per a FFT inversa en tres dimensions, de complexes a reals serà el següent:  Transposició de cada pla Nx x Ny (opcional).  Transposició de cada pla Nx x Nz (opcional).  Per cada pla Nx x Ny, Ny IFFT 1D de complexes a complexes, al llarg l'actual eix x (original eix z). Figura 7.4: Eixos i plans de referència Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 48 Figura 8.2.2: Configuració de l’FFT IP Core-2 En la segona pestanya, configurem l’accelerador perquè rebi complexos formats per dos floats, un per representar la part real i un per representar la part imaginària del nombre. Per tant, utilitzem precisió simple (single-precission) per al càlcul de les FFT. El resultat s'obté a través del canal de sortida, que retorna la transformada resultant en el mateix format que el que hem descrit per a les dades d'entrada. És per això que especifiquem que volem les dades de sortida en ordre natural. 8.1.2 AXI DMA Per tal de realitzar la transmissió de dades entre la memòria del processador ARM i accelerador de les FFT, necessitem un altre IP core denominat AXI DMA (Direct Memory Access). Aquest mòdul ens permetrà que les dades provinents del processador Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 49 arribin a l’accelerador; a més, també permetrà la comunicació en sentit invers, retornant a la memòria del processador les dades obtingudes. Per a cada instància de l’accelerador encarregat dels càlculs de FFT utilitzarem un DMA que gestionarà la comunicació d'aquell accelerador amb el processador. La figura 8.3 mostra aquest IP. Addicionalment, per a la transmissió de les dades de configuració de les transformades (com hem comentat, per tal d'especificar la direcció de la FFT), utilitzarem un DMA addicional, que transmetrà aquesta informació a tots els mòduls FFT. Degut a les característiques de FTDock, no necessitarem configuracions independents entre els diferents cores de FFT, i per tant un únic DMA de configuració serà necessari en el disseny. Aquest DMA actuarà en única direcció, de la memòria del processador cap al mòdul FFT. Per tal de distingir els DMAs de dades de FFT del DMA de configuració a l'hora d’enviar les dades, hem assignat el valor N, essent N el nombre de cores FFT, al DMA de configuració. Per altra banda, els DMAs encarregats de la transmissió de dades prendran els valors entre 0 i N-1. Figura 8.3: AXI DMA Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 50 Figura 8.4: Configuració de l’AXI DMA A la figura 8.4 mostrem la configuració que hem aplicat per als DMA encarregats de la transmissió de dades. Hem habilitat tant el canal d’escriptura com de lectura, per rebre les dades provinents de la CPU i poder-ne retornar els resultats. Hem assignat 64 bits a l’amplada dels canals de dades, per suportar les duples de floats que representaran els nombres complexos amb els que operarà l’accelerador. Per al DMA de configuració, únicament hem habilitat el canal de lectura, ja que no retornarà dades al processador. A més, l’amplada de les dades serà de 32 bits, suficient per incloure la informació de configuració. 8.1.3 Processing System 7 Processador del xip, que definim en el disseny per tal de realitzar-hi totes la connexions necessàries. Serà des del processador on executarem la majoria del programa, i des d’on sol·licitarem als DMAs la transferència de dades cap i des de l’accelerador. Podem veure el processador en la imatge de la figura 8.5. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 51 En el processador, definit al disseny com a Zynq7 Processing System, s'ha configurat per tal de tenir un port de sortida mestre, el que utilitzarem per a l'enviament de les dades de la FFT a la PL, i també la informació per configurar els acceleradors. Per a la recepció de les dades que retornaran del mòdul FFT, s'han configurat múltiples ports esclaus per rebre aquestes dades. A més a més, s'ha habilitat un port per a la detecció de les interrupcions que generaran els DMAs al comunicar-se amb el controlador de memòria. 8.1.4 AXI Interconnect Les connexions entre el PSi la i viceversa es realitzen a través de la IP AXI Interconnect. Aquest mòdul permet la connexió entre varis ports esclaus i mestres per a la transmissió de dades de la memòria cap a streaming (MM2S) i viceversa (S2MM). A la figura 8.6 podem veure aquest connector. Un d'aquests mòduls l'utilitzarem per controlar des del processador els diferents DMA que tenim en el disseny, tant els que s'encarregaran de subministrar les dades de la FFT als DMAs com el que destinarem a la configuració de les FFT. Aquest AXI Interconnect tindrà un únic port esclau (que vindrà directament del processador) i N+1 ports esclaus, essent N el nombre de cores FFT, N que es connectaran als DMAs de dades i un darrer port que es connectarà al DMA de configuració. També utilitzarem un AXI Interconnect per a cada DMA que es connectarà a ports esclaus del processador. Aquests serviran per retornar les dades obtingudes en els mòduls FFT al processador. Cada un d'aquests Interconnects tindran 3 entrades: una provinent del port SG (Scatter-Gather), i dues dels ports MM2S i S2MM. El primer s'encarrega de les transferències de dades de múltiples regions de memòria en una sola transacció del DMA, mentre que els altres dos de la comunicació entre el DMA i el controlador de la memòria. Identifiquem aquests mòduls amb el 6. Opcionalment podríem agregar tots aquests mòduls en un únic Interconnect amb un major nombre de ports esclaus provinents dels diferents DMAs i un sol port mestre, connectat al processador. Figura 8.5: Zynq7 Processing System Figura 8.6: AXI Interconnect Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 52 8.1.5 AXI4-Stream Interconnect De manera similar als AXI Interconnect, disposem d'un mòdul AXI4-Stream Interconnect, que permet la connexió de múltiples ports esclaus i mestres, en aquest cas tots en streaming. Aquest core s'alimentarà de les dades del DMA de configuració i les subministrarà directament a tots els cores FFT de manera simultània. D'aquesta manera tots els mòduls de càlcul de FFT quedaran configurats alhora amb la mateixa configuració. 8.1.6 Processor System Reset Module Per generar una senyal de reset síncrona al rellotge, és necessari el mòdul Processor System Reset, que generarà aquesta senyal per a tots els mòduls FFT, DMA i Interconnects. 8.1.7 Concat Finalment, utilitzarem la IP Concat per tal d'enviar al processador totes les senyals d'interrupció dels DMAs quan aquests es comuniqui amb la memòria. 8.2 Implementació software Per la utilització els diferents acceleradors hardware, i que aquests funcioni de manera paral·lela i seguint l’estratègia descrita anteriorment, hem modificat la nostra implementació de les execucions de transformades en tres dimensions. Per això hem fet servir els drivers per a DMA anteriorment esmentats i la llibreria pthreads. La nostra implementació de la FFT 3D R2C segueix la següent estructura: 1. Inicialització threads: s’assigna a cada thread un identificador i la quantitat de iteracions que haurà de realitzar. La quantitat d’iteracions serà la quantitat de plans Nx x Ny amb que treballarà. 2. Creació de threads: es creen els threads, on cada un executarà Ny FFT R2C 1D al llarg de l’eix x per a tots els plans Nx x Ny que té assignats. Aquestes execucions es realitzaran mitjançant la llibreria FFTW, per els motius descrits anteriorment. 3. Unió de threads: s’espera el final d’execució de cada un dels threads. 4. Creació de threads: es creen novament els threads per a la transposició dels plans Nx x Ny. Es segueix la mateix estructura que per a l’execució de les FFT R2C 1D, cada thread tindrà un conjunt de plans Nx x Ny assignats als quals executarà la transposició. 5. Unió de threads. 6. Creació de threads: es repeteix el segon pas, però aquest cop executant FFT C2C, que en aquest cas sí que faran ús de l’accelerador hardware. Per això utilitzaran la funció de la llibreria de DMA xdma_perform_transaction. Aquesta Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 53 funció permet especificar amb quin accelerador hardware es comunicarà, on cada thread es comunicarà amb l’accelerador que té el mateix identificador que ell. Per això hem tingut cura en la inicialització que cada thread tingui un identificar menor al nombre total d’acceleradors que tenim. També especificarem les dades d’entrada, que seran els plans que hem assignat per a cada thread, i les de sortida, que coincidiran amb les posicions d’entrada. 7. Unió de threads. 8. Creació de threads: aquest cop cada thread realitzarà les transposicions en els plans Nx x Nz, i en aquest cas seran plans Nx x Nz els que tindran assignats. 9. Unió de threads. 10. Creació de threads: ídem al punt 6. 11. Unió de threads. En el cas de la FFT 3D C2R podem extrapolar la mateixa estructura al curs d’execució lleugerament diferent que hem descrit anteriorment. Figura 8.7: Eixos i plans de referència Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 54 9. Entorn de treball Aquí veurem les eines software que hem utilitzat per a la implementació de FTDock. 9.1 Desenvolupament software 9.1.1 Creació i edició de codi Per tal de crear i modificar tot el codi hem utilitzat principalment els programes d’edició de text vim i gedit, ambdós disponibles en el sistema operatiu Ubuntu 14 que tenim instal·lat en el nostre PC portàtil. Vim (Vi Improved) és un editor que basa la seva interfície en la línia de comandes i no en una interfície gràfica; és per això que el farem servir principalment per edicions reduïdes de codi. Per altra banda disposa de una interfície gràfica, que en molts casos serà més propera a l’usuari, i en aquest cas l’utilitzarem per l’edició de grans quantitats de codi. 9.1.2 Compilació Realitzarem les compilacions a través de Makefiles que generarem per tal de facilitar d’agilitzar el procés. El compilador que utilitzarem és arm-xilinx-linux-gnueabi-gcc, compilador creuat basat en gcc distribuït per Xilinx que ens permetrà la generació d’executables que podrem executar sota l’arquitectura ARM de la placa des de la nostra màquina. Utilitzarem els mateixos flags de compilació que utilitza FTDock per defecte Per a les execucions locals hem utilitzat el compilador gcc, fent ús del mateix conjunt de flags de compilació. Addicionalment, a l’hora de realitzar anàlisi de codi mitjançant gprof, hem afegit el flag –pg. 9.1.3 Llibreries Com hem comentat fem ús principalment de les llibreries externes FFTW i el driver de DMA. Per a FFTW utilitzarem l’actualització 3.2.2, ja que disposa de versió per a ARM, i no n’hem pogut trobar per a aquesta arquitectura en la darrera versió 3.3.4. Per al driver de DMA utilitzem la darrera versió disponible a GitHub a data de gener de 2016. Altres llibreries estàndard que utilitza FTDock són stdio (standard input output), string, math, stdlib, time i unistd. També utilitzem la llibreria pthread per a la paral·lelització del codi. 9.1.4 Anàlisi i mesura de temps Per tal de realitzar un anàlisi de FTDock hem utilitzat gprof. Un dels motius per la tria d’aquest instrument de profiling és que no hem de modificar el codi, únicament cal afegir un flag de compilació. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 55 Per a les mesures de temps hem fet servir la funció gettimeofday, que retorna la quantitat de segons i micro-segons des de l’instant Epoch (00:00 1 de gener de 1970). Afegint diferents marques de temps al llarg del codi i calculant-ne la diferència permet acotar el temps d’execució de diferents regions de codi. 9.2 Desenvolupament hardware 9.2.1 Vivado Design Suite Per al disseny i la generació del hardware hem utilitzat Vivado Design Suite en la versió 2014.4, la darrera versió en l’inici del projecte. 9.2.2 PetaLinux Tools Conjunt d’eines de Xilinx per a la creació del sistema operatiu PetaLinux. Malgrat que en el moment que el vàrem utilitzar per primer cop ja hi havia noves versions, hem utilitzat la mateixa versió que la que utilitzàvem per a Vivado, la 2014.4. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 56 10. Resultats obtinguts Aquí detallarem i analitzarem els resultats que hem obtingut a l’hora de posar a prova el disseny que hem realitzat a la Zedboard. 10.1 Fast Fourier Transform 1D Primer avaluarem els resultats que obtenim en l’execució de transformades de Fourier en una única dimensió. D’aquesta manera, ens centrarem en el rendiment obtingut utilitzant l’accelerador i les causes d’aquests resultats, i de moment ignorarem altres factors que tindran impacte en FTDock. Les figures 10.1 i 10.2 mostren els temps d’execució de 1.000 FFT en una direcció, directa i inversa respectivament. Mostrem els resultats per a diferents llargades potències de dos de la FFT, i per a execucions mitjançant FFTW, un accelerador o dos acceleradors. D’entrada, podem que els resultats no són favorables per a mides petites d’entrada de dades. Les execucions de FFT mitjançant la llibreria FFTW ofereixen un millor respecte a l’execució utilitzant els acceleradors hardware per a mides de 32 i 64 nombres complexos. És a partir de FFTs de llargada 128 que trobem una millora en l’ús d’acceleradors hardware: utilitzant un únic accelerador obtenim un millor temps que FFTW, però el marge que guanyem és poc significatiu; per altra banda, quan utilitzem dos acceleradors de manera paral·lela, comencem a veure un rendiment clarament favorable. Amb mides superiors, cada cop obtenim millors resultats fent ús dels acceleradors hardware. Podem veure també que en tots els casos, la diferència en temps d’execució entre transformades directes i inverses és negligible; és per això que analitzarem únicament per a FFT directes, les proves realitzades demostren que també són aplicables per a la seva inversa. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 57 Figura 10.1: Temps d’execució de FFT directa per a diferents versions Figura 10.2: Temps d’execució de FFT inversa per a diferents versions Un fet remarcable que podem veure a les figures 10.1 i 10.2 és la poca variació que mostra l’ús d’acceleradors en funció de la llargada de la FFT, en comparació amb l’increment que tenim en la utilització de la llibreria. Això és degut als alts temps de transferència de dades respecte al temps d’execució de la FFT. Les figura 10.3 i 10.4 mostren quina part del temps es destina a l’execució de FFTs respecte a la que es destina a la transmissió de dades (en el cas dels acceleradors) o al seu accés (en el cas de FFTW). 0 50000 100000 150000 200000 250000 300000 350000 400000 450000 32 64 128 256 512 Temps en mircosegons Llargada FFT FFT Directa FFTW 1 Accel. FFT 2 Accel. FFT 0 100000 200000 300000 400000 500000 32 64 128 256 512 Temps en microsegons Llargada FFT FFT inversa FFTW 1 Accel. FFT 2 Accel. FFT Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 64 fórmula: 𝑇 = 𝑇𝑖 +𝑇𝑓 +𝑇𝑟 ·𝑁𝑟 On 𝑇𝑖 és el temps d’inicialització, 𝑇𝑓 és el temps de finalització, 𝑇𝑟 és el temps de cada rotació i 𝑁𝑟 és el nombre de rotacions. Per als dos jocs de proves que hem utilitzat, 𝑁𝑟 = 9.240. La taula 10.1 mostra els valors que prenen 𝑇𝑖 +𝑇𝑓 per als jocs de proves i versions de FTDock esmentats. 𝑻𝒊 +𝑻𝒇 (segons) FFTWF Accelerador 5pti.parsed / 5pti.parsed 5,7366 4,0286 1PPE.lig / 1PPE.rec 4,9488 3,3406 Taula 10.1: Temps de 𝑻𝒊 +𝑻𝒇 Ja únicament ens falta trobar els valors de 𝑇𝑟. Aquests valors els obtindrem a partir de: 𝑇𝑟 =𝑇𝑏 𝑁𝑟 On Tb és el temps d’execució del bucle. En aquest cas, les execucions que hem realitzat executaven 100 rotacions del bucle, per tant 𝑁𝑟 =100. A la taula 10.2 mostrem el càlcul de 𝑇𝑟. 𝑻𝒓 (segons) FFTWF Accelerador 5pti.parsed / 5pti.parsed 𝑇𝑟 =867,0682 100 𝑇𝑟 =669,3896 100 1PPE.lig / 1PPE.rec 𝑇𝑟 =918,541 100 𝑇𝑟 =717,058 100 Taula 10.2: Temps de 𝑻𝒓 Finalment, ja podem calcular quin serà el temps d’una execució completa de FTDock. Mostrem a la taula 10.3 el resultat del càlcul mitjançant la fórmula descrita anteriorment. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 65 Temps de FTDock FFTWF Accelerador 5pti.parsed / 5pti.parsed 𝑇 = 22,26 hores 𝑇 = 17,18 hores 1PPE.lig / 1PPE.rec 𝑇 = 23,58 hores 𝑇 = 18,41 hores Taula 10.3 Temps d’execució completa de FTDock Aquí podem veure la necessitat de realitzar les proves de FTDock amb execucions amb una quantitat de rotacions limitades. A la figura 10.9 podem veure el temps resultant que obtindríem a partir d’aquestes estimacions. Figura 10.9: Temps teòric d’execució completa de FTDock 0 5 10 15 20 25 FFTW Accelerador Temps en hores Temps d'execució completa de FTDock 5pti.parsed / 5pti.parsed 1PPE.lig / 1PPE.rec Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 66 11. Possibles extensions del projecte Al llarg del projecte han aparegut moltes qüestions relacionades amb el projecte no estipulades inicialment, però que veiem que podrien tenir un impacte molt favorable en el projecte. Exposarem punts claus que podrien desembocar en futurs objectius a plantejar-se en una suposada continuació del projecte. 11.1 Ús d’acceleradors hardware en altres regions crítiques Hem pogut comprovar les grans avantatges, i també les dificultats, que suposa l’ús d’acceleradors hardware per tal d’agilitzar les regions més crítiques de FTDock. Per tant, podem extrapolar l’ús d’acceleradors a altres regions de codi. Centrant-nos en la transformada en tres dimensions, podem veure que malgrat reduir i paral·lelitzar les transposicions, aquestes encara tenen un pes rellevant. Un nou enfocament que es podria plantejar és realitzar aquestes transposicions a través d’un nou hardware especialitzat. No ens consta de que Xilinx disposi de cap IP core que acompleixi aquesta funció, però dintre del conjunt de programari que ofereix trobem Vivado HLS (High-Level Synthesis) que permet la implementació de components hardware a partir de descripcions algorítmiques en alt nivell. Es podria utilitzar aquesta eina per tal de generar components hardware que s’encarreguin de calcular els diferents tipus de transposicions que tenim, i afegir aquests nous components en el disseny que tenim, mitjançant l’ús de DMAs. De manera similar, també es podria estudiar la possibilitat de generar i afegir en el disseny components hardware que s’encarreguin de realitzar la convolució o l’algoritme d’assignació de puntuació a les rotacions. Per altra banda, no tindria massa sentit utilitzar components hardware per accelerar funcionalitats que es troben fora del bucle, ja que el seu impacte seria molt discret i estaríem ocupant una quantitat de components de FPGA molt valuosa que podríem destinar a millorar el bucle. Una altra millora que aparentment aportarà resultats a un cost de disseny molt reduït seria l’ampliació de la quantitat d’acceleradors a utilitzar. Únicament hem comprovat els avantatges que ofereix l’ús de dos acceleradors, i tot apunta que si incrementem aquesta quantitat els resultats seran millors. L’adaptació del codi de FTDock que s’ha fet és independent del nombre d’acceleradors que utilitza, de manera que tant sols s’hauria de modificar el hardware. D’aquesta manera aprofitaríem de manera més exhaustiva els recursos que ofereix la FPGA. 11.2 Millora de l’assignació de memòria per a DMA Com hem pogut veure, en l’execució de FFTs a través dels acceleradors hardware el gran coll d’ampolla que tenim és la transmissió de les dades. Addicionalment, Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 67 l’assignació de memòria per a ser utilitzada per DMA no només repercuteix quan operem amb aquestes dades en la FPGA, sinó també quan operem amb aquestes dades des del processador. Una primera solució que hem explorat però que no ha quedat reflectida en els resultats del treball, és treballar amb estructures de dades en memòria assignada mitjançant malloc. A l’hora d’enviar dades a través de DMA, realitzarem una còpia d’aquestes a una regió de memòria assignada que permeti la transmissió, efectuarem la transacció de DMA i copiarem el resultat obtingut. D’aquesta manera, no carregarem operacions que realitzem en el processador amb accessos a memòria més costosos i podrem assignar regions de memòria majors que permetran l’execució de FTDock amb un conjunt més ampli de molècules que ara no suportàvem. De totes maneres, aquesta solució no ataca el problema real que és l’elevat temps de transmissió a través de DMA, i per tant en cert grau entraria en conflicte amb la secció anterior. Una aproximació més complexa però que podria aportar millors resultats seria analitzar en profunditat quina és la causa dels elevats temps de transmissió a DMA i treballar per reduir-lo. D’aquesta manera estaríem atacant el principal coll d’ampolla que tenim en el programa, i alhora ens permetria obtenir millors resultats en la utilització d’acceleradors hardware per a altres regions del programa. 11.3 Exportació a altres programes i plataformes Les transformades de Fourier és un recurs àmpliament utilitzat en diferents camps. Podem trobar gran quantitat de programes que utilitzen FFT, ja sigui a través de FFTW o d’altres llibreries amb característiques similars, i que podrien veure’s beneficiats de l’ús de l’accelerador hardware que s’ha utilitzat en aquest projecte. També es pot exportar el hardware dissenyat a plataformes heterogènies de característiques similars però de majors prestacions, o inclús a sistemes formats per múltiples FPGA que permetrien una major acceleració del projecte. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 68 12. Conclusions Hem assolit amb èxit els objectius plantejats inicialment, realitzant un port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq, més concretament a la placa Zedboard, mitjançant l’ús d’acceleradors hardware. Addicionalment, hem arribat a l’objectiu de utilitzar múltiples instàncies d’aquest acceleradors de manera paral·lela. Hem obtingut una millora significativa de rendiment del programa, tot i ser inferior als resultats esperats. De totes maneres, podem preveure una obtenció de millors resultats a l’hora d’aplicar el conjunt de propostes de treball futur descrites anteriorment. S’ha pogut demostrar el gran potencial que representen la utilització conjunta de multiprocessadors i FPGA en l’acceleració de programes. Els fruits del projecte a nivell personal han estat molt enriquidors: han permès conèixer en profunditat i de primera mà les grans complexitats que suposa treballar en un projecte a una escala superior a els projectes plantejats durant el grau, a part de la gran quantitat de coneixements que han aportat que poden ser molt útils en el meu futur acadèmic i professional. També ha mostrat una cara menys amable, haver d’assumir les conseqüències de no poder arribar als objectius plantejats en els terminis que s’havien plantejat, però que alhora ha servit per aprendre a treballar per tal de superar aquests obstacles i tirar endavant amb el projecte, fent autocrítica i analitzant els diferents motius que han portat a aquesta situació. Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 69 13. Bibliografia [1] Varis autors. Docking (molecular). [En línia] <http://en.wikipedia.org/wiki/Docking_(molecular)> [Consulta: 2 oct 2014] [2] Inbal Halperin, Buyong Ma, Haim Wolfson, Ruth Nussinov. Principles of docking: An overview of search algorithms and a guide to scoring functions en Proteins: Structure, Function, and Bioinformatics, vol. 47, no. 4, pp. 409–443 (2002). [3] Irwin D. Kuntz, Jeffrey M. Blaney, Stuart J. Oatley, Robert Langridge, Thomas E. Ferrin. A geometric approach to macromolecule-ligand interactions en Journal of Molecular Biology, vol. 161, no. 2, pp. 269-288 (1982). [4] Imre Pechan, Béla Fehér, Attila Bérces. FPGA-Based Acceleration of the AutoDock Molecular Docking Software en Conference on Ph.D. Research in Microelectronics and Electronics, Berlin (18-21 jul. 2010). [5] Henry A. Gabb, Richard M. Jackson, Michael J. E. Sternberg. Modelling Protein Docking using Shape Complementarity, Electrostatics and Biochemical Information en J. Mol. Biol., vol. 272, pp. 106-120 (1997). [6] Matteo Frigo, Steven G. Johnson. The Design and Implementation of FFTW3 en Proc. IEEE, vol. 93, no. 2, pp. 216–231 (2005). [7] Gidon Moont, Henry A. Gabb, Michael J.E. Sternberg. Use of Pair Potentials Across Protein Interfaces in Screening Predicted Docked Complexes en PROTEINS: Structure, Function, and Genetics, vol. 35, no. 3, pp. 364–373 (1999). [8] “Cutie”. Implementation of Fast Fourier Transform (FFT) using VHDL (2011). [En línia] <https://www.scribd.com/doc/74682090/Implementation-Of-Fast-FourierTransform-FFT-Using-VHDL> [Consulta: 3 oct. 2014] [9] Harald Servat, Cecilia González-Álvarez2, Xavier Aguilar1,Daniel Cabrera-Benítez, Daniel Jiménez-González. Drug Design Issues on the Cell BE en Lecture Notes in Computer Science, vol. 4.917, pp. 176-190 (2008) [10] Varis autors. Field-programmable gate array. [En línia] <https://en.wikipedia.org/wiki/Field-programmable_gate_array> [Consulta: 15 gen 2016] [11] Autor desconegut. History of FPGAs. [En línia] <https://web.archive.org/web/20070412183416/http:/filebox.vt.edu/users/tmagin/history .htm> [Consulta: 15 gen 2016] Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 70 Port de l’aplicació en bioinformàtica FTDock a la plataforma heterogènia Zynq 71 Annex Annex 1: Diagrama del disseny final de Vivado Design Suite