Lecture Notes in Electrical Engineering 566 Iouliia Skliarova Valery Sklyarov FPGA-BASED Hardware Accelerators Lecture Notes in Electrical Engineering Volume 566 Series Editors LeopoldoAngrisani,DepartmentofElectricalandInformationTechnologiesEngineering,UniversityofNapoli FedericoII,Naples,Italy MarcoArteaga,DepartamentdeControlyRobótica,UniversidadNacionalAutónomadeMéxico,Coyoacán, Mexico BijayaKetanPanigrahi,ElectricalEngineering,IndianInstituteofTechnologyDelhi,NewDelhi,Delhi,India SamarjitChakraborty,FakultätfürElektrotechnikundInformationstechnik,TUMünchen,Munich,Germany JimingChen,ZhejiangUniversity,Hangzhou,Zhejiang,China ShanbenChen,MaterialsScience&Engineering,ShanghaiJiaoTongUniversity,Shanghai,China TanKayChen,DepartmentofElectricalandComputerEngineering,NationalUniversityofSingapore, Singapore,Singapore RüdigerDillmann,HumanoidsandIntelligentSystemsLab,KarlsruheInstituteforTechnology,Karlsruhe, Baden-Württemberg,Germany HaibinDuan,BeijingUniversityofAeronauticsandAstronautics,Beijing,China GianluigiFerrari,UniversitàdiParma,Parma,Italy ManuelFerre,CentreforAutomationandRoboticsCAR(UPM-CSIC),UniversidadPolitécnicadeMadrid, Madrid,Spain SandraHirche,DepartmentofElectricalEngineeringandInformationScience,TechnischeUniversität München,Munich,Germany FaryarJabbari,DepartmentofMechanicalandAerospaceEngineering,UniversityofCalifornia,Irvine,CA, USA LiminJia,StateKeyLaboratoryofRailTrafficControlandSafety,BeijingJiaotongUniversity,Beijing,China JanuszKacprzyk,SystemsResearchInstitute,PolishAcademyofSciences,Warsaw,Poland AlaaKhamis,GermanUniversityinEgyptElTagamoaElKhames,NewCairoCity,Egypt TorstenKroeger,StanfordUniversity,Stanford,CA,USA QilianLiang,DepartmentofElectricalEngineering,UniversityofTexasatArlington,Arlington,TX,USA FerranMartin,Departamentd’EnginyeriaElectrònica,UniversitatAutònomadeBarcelona,Bellaterra, Barcelona,Spain TanCherMing,CollegeofEngineering,NanyangTechnologicalUniversity,Singapore,Singapore WolfgangMinker,InstituteofInformationTechnology,UniversityofUlm,Ulm,Germany PradeepMisra,DepartmentofElectricalEngineering,WrightStateUniversity,Dayton,OH,USA SebastianMöller,QualityandUsabilityLab,TUBerlin,Berlin,Germany SubhasMukhopadhyay,SchoolofEngineering&AdvancedTechnology,MasseyUniversity, PalmerstonNorth,Manawatu-Wanganui,NewZealand Cun-ZhengNing,ElectricalEngineering,ArizonaStateUniversity,Tempe,AZ,USA ToyoakiNishida,GraduateSchoolofInformatics,KyotoUniversity,Kyoto,Japan FedericaPascucci,DipartimentodiIngegneria,UniversitàdegliStudi“RomaTre”,Rome,Italy YongQin,StateKeyLaboratoryofRailTrafficControlandSafety,BeijingJiaotongUniversity,Beijing,China GanWoonSeng,SchoolofElectrical&ElectronicEngineering,NanyangTechnologicalUniversity, Singapore,Singapore JoachimSpeidel,InstituteofTelecommunications,UniversitätStuttgart,Stuttgart,Baden-Württemberg, Germany GermanoVeiga,CampusdaFEUP,INESCPorto,Porto,Portugal HaitaoWu,AcademyofOpto-electronics,ChineseAcademyofSciences,Beijing,China JunjieJamesZhang,Charlotte,NC,USA ThebookseriesLectureNotesinElectricalEngineering(LNEE)publishesthelatestdevelopments in Electrical Engineering—quickly, informally and in high quality. While original research reported in proceedings and monographs has traditionally formed the core of LNEE, we also encourage authors to submit books devoted to supporting student education and professional training in the various fields and applications areas of electrical engineering. The series cover classicalandemergingtopicsconcerning: (cid:129) CommunicationEngineering,InformationTheoryandNetworks (cid:129) ElectronicsEngineeringandMicroelectronics (cid:129) Signal,ImageandSpeechProcessing (cid:129) WirelessandMobileCommunication (cid:129) CircuitsandSystems (cid:129) EnergySystems,PowerElectronicsandElectricalMachines (cid:129) Electro-opticalEngineering (cid:129) InstrumentationEngineering (cid:129) AvionicsEngineering (cid:129) ControlSystems (cid:129) Internet-of-ThingsandCybersecurity (cid:129) BiomedicalDevices,MEMSandNEMS Forgeneralinformationaboutthisbookseries,commentsorsuggestions,pleasecontactleontina. [email protected]. To submit a proposal or request further information, please contact the Publishing Editor in yourcountry: China JasmineDou,AssociateEditor([email protected]) India SwatiMeherishi,ExecutiveEditor([email protected]) AnindaBose,SeniorEditor([email protected]) Japan TakeyukiYonezawa,EditorialDirector([email protected]) SouthKorea Smith(Ahram)Chae,Editor([email protected]) SoutheastAsia RameshNathPremnath,Editor([email protected]) USA,Canada: MichaelLuby,SeniorEditor([email protected]) AllotherCountries: LeontinaDiCecco,SeniorEditor([email protected]) ChristophBaumann,ExecutiveEditor([email protected]) ** Indexing: The books of this series are submitted to ISI Proceedings, EI-Compendex, SCOPUS,MetaPress,WebofScienceandSpringerlink** Moreinformationaboutthisseriesathttp://www.springer.com/series/7818 Iouliia Skliarova Valery Sklyarov (cid:129) FPGA-BASED Hardware Accelerators 123 Iouliia Skliarova Valery Sklyarov Department ofElectronics Department ofElectronics Telecommunications and Informatics Telecommunications and Informatics University of Aveiro University of Aveiro Aveiro, Portugal Aveiro, Portugal ISSN 1876-1100 ISSN 1876-1119 (electronic) Lecture Notesin Electrical Engineering ISBN978-3-030-20720-5 ISBN978-3-030-20721-2 (eBook) https://doi.org/10.1007/978-3-030-20721-2 ©SpringerNatureSwitzerlandAG2019 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission orinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfrom therelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained hereinorforanyerrorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregard tojurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface Field-programmable gate arrays (FPGAs) were invented by Xilinx in 1985, i.e., about 35 years ago. Currently, they are part of heterogeneous computer platforms that combine different types of processing systems with new generations of pro- grammable logic. The influence of FPGAs on many directions in engineering is growingcontinuouslyandrapidly.ForecastssuggestthattheimpactofFPGAswill continue to expand, and the range of applications will increase considerably in future. Recent field-configurable microchips incorporate scalar and vector multi-coreprocessingelementsandreconfigurablelogicappendedwithanumberof frequently used devices. FPGA-based systems can be specified, simulated, syn- thesized, and implemented in general-purpose computers by using dedicated inte- grated design environments. Experiments and explorations of such systems are commonly based on prototyping boards that are linked to the design environment. It is widely known that FPGAs can be applied efficiently in a vast variety of engineering applications. One reason for this is that growing system complexity makesitverydifficulttoshipdesignswithouterrors.Hence,ithasbecomeessential tobeabletofixerrorsafterfabrication,andcustomizabledevices,suchasFPGAs, make this much easier. The complexity of contemporary chips is increasing exponentially with time, and the number of available transistors is growing faster than the ability to design meaningfully with them. This situation is a well-known design productivity gap, which is increasing continuously. The extensive involvement of FPGAs in new designs of circuits and systems and the need for better design productivity undoubtedly require huge engineering resources, which are the major output of technical universities. This book is intended to provide substantial assistance for courses relating to the design and development of systems using FPGAs. Several steps in the design process are discussed, including system modeling in software, the retrieval of basic software functions, and the automatic mapping of these functions to highly optimized hardware specifications. Finally, the synthesis and implementationofcircuitsandsystemsisdoneinindustrialcomputer-aideddesign environments. v vi Preface FPGAs still operate at lower clock frequencies than general-purpose computers and application-specific integrated circuits. The cost of the most advanced FPGA devicesishigh,andcheaperFPGAssupportclockfrequenciesthataremuchlower than those in inexpensive computers that are used widely. One of the most importantapplications ofFPGAs isimprovingperformance.Obviously,toachieve accelerationwith devicesthataregenerallyslower,parallelismneeds tobeapplied extensivelyandexplaininghowthiscanbeachievedisthemaintargetofthisbook. Several types of hardware accelerators are studied and discussed in the context of the following areas: (1) searching networks and their varieties, (2) sorting net- works and a number of derived architectures, (3) counting networks, and (4) net- worksfromlookuptablesfocusingontherationaldecompositionofcombinational circuits. The benefits of the proposed methods and architectures are demonstrated through examples from data processing and data mining, combinatorial searching, encoding, as well as a number of other frequently required computations. The following features set this book apart from others in the field: 1. The methodology discussed shows in detail how design ideas can be advanced fromroughmodelinginsoftwarethroughtosynthesizablehardwaredescription language specifications. Basic functions are retrieved from software and auto- matically transformed to core operational blocks in decompositions of the developed circuits that are suggested. 2. Traditional highly parallel searching and sorting networks are combined with othertypesofnetworkstoallowcomplexcombinationalandsequentialcircuits tobedecomposedwithinregularreusablestructures.Notethatcorecomponents of the network may be different from commonly used comparators/swappers. 3. Regular and easily scalable designs are described using a variety of networks based on iterative hardware implementations. Relatively large highly parallel segments of the developed circuit are reused iteratively, which allows the number of core elements to be reduced dramatically, thus maximizing the potential throughput with given hardware. 4. A number of synthesizable hardware description language specifications (in VHDL) are provided that are ready to be tested and incorporated into practical engineering designs. This can be an extremely valuable reference base for both undergraduateandpostgraduateuniversitystudents.ManysynthesizableVHDL specifications are available online at http://sweet.ua.pt/skl/Springer2019. The chapters in the book contain the following material: Chapter 1 provides an introduction to reconfigurable devices (i.e., field- programmable gate arrays and hardware programmable systems-on-chip), design languages,methods,andtoolsthatwillbeusedinthebook.Thecorereconfigurable elementsandthemostcommonembeddedblocksarebrieflydescribed, addressing only those features that are needed in subsequent chapters. A number of simple examples are given that are ready to be tested in FPGA-based prototyping boards, twoofwhicharebrieflyoverviewed.Finally,thevarioustypesofnetworksthatare studied in the rest of the book are characterized in outline. Preface vii Chapter2underlinesthattocompetewiththeexistingalternativesolutions(both in hardware and in software), wide-level parallelism must be implemented in FPGA-based circuits with small propagation delays. Several useful techniques are discussed and analyzed, one example being the ratio between combinational and sequentialcomputationsatdifferentlevels.Communication-timedataprocessingis introduced. Many supplementary components that are needed for hardware accel- erators are described, implemented, and tested. Finally, different aspects of design are discussed, and a range of useful examples are given. Chapter 3 is dedicated to searching networks. These allow extreme values in a data set to be found, or items in a set that satisfy some predefined conditions or limitations, indicated by given thresholds, to be identified. The simplest task dis- cussedisretrievingthemaximumand/ortheminimumvaluesorsubsetsfromadata set. More complicated procedures are described that permit the most frequently occurring value/item to be found, or the retrieval of a set of the most frequent values/items above a given threshold, or satisfying some other constraint. These tasks can be solved for entire data sets, for intervals of data sets, or for specially organized structures. Chapter 4 studies sorting networks, with the emphasis on regular and easily scalable structures that permit data to be sorted and a number of supplementary (derived) problems to be solved. Two core architectures are discussed: (1) an iterative approach that is based on a highly parallel combinational sorting network with minimal propagation delay, and (2) a communication-time architecture that allows data to be processed as soon as a new item is received, thus minimizing communicationoverhead.Severalnewproblemsareaddressed,namelytheretrieval maximumand/orminimumsortedsubsets,filtering,processingnon-repeateditems, applyingaddress-basedtechniques,andtraditionalpipeliningtogetherwiththering pipeline that is introduced. Many examples are given and analyzed with complete details. Chapter 5 identifies several computational problems that can be solved effi- ciently in FPGA-based hardware accelerators. Many of these involve the compu- tation and comparison of Hamming weights. Three core methods are presented: counting networks, low-level designs from elementary logic cells viewed as spe- cially organized networks, and designs using arithmetical units involving FPGA digital signal processing slices. Mixed solutions based on combining different methods are also discussed. Many practical examples with synthesizable VHDL code are given. Finally, the applicability of the proposed methods is demonstrated using problems in combinatorial search, and data and information processing. Chapter6concludesthatforproblemsthatallowahighlevelofparallelismtobe applied, hardware implementations are generally faster than software running in general-purpose and application-specific computers. However, software is more flexible and easily adaptable to potentially changing conditions and requirements. Besides, on-chip hardware circuits introduce a number of constraints, primarily on resources that limit the possible complexity of designs that can be implemented. Thus, it makes sense to combine the flexibility, maintainability, and portability of softwarewiththespeedandothercapabilitiesofhardware,andthiscanbeachieved viii Preface inhardware/softwareco-design.Chapter6isdedicatedtoexploringthesetopicsin depth and discusses hardware/software partitioning, dedicated helpful blocks (namely, priority buffers), hardware/software interaction, and some useful tech- niques that allow communication overhead to be reduced. A number of examples are discussed. The book can be used as the supporting material for university courses that involve FPGA-based design, such as “Digital design,” “Computer architecture,” “Embeddedsystems,”“Reconfigurablecomputing,”and“FPGA-basedsystems.”It will also be helpful in engineering practice and research activity in areas where FPGA-based circuits and systems are explored. Aveiro, Portugal Iouliia Skliarova Valery Sklyarov Conventions 1. VHDL/Java keywords are shown in bold font 2. VHDL/Java comments are shown in the following font:—this is a comment 3. VHDL is not a case-sensitive language, and thus, UPPERCASE and lowercase letters may be used interchangeably. 4. WhenareferencetoaJavaprogramisdone,thenthenameoftherelevantclass ispointedout.WhenareferencetoaVHDLspecificationisdone,thenthename of the relevant entity is indicated. 5. Java programs have been prepared as compact as possible. That is why many required verifications (such as that are needed for files) have not been applied. Besides, many input variables are declared as final constant values. 6. Xilinx Vivado 2018.3 has been used as the main design environment, but the proposed specifications have been kept as platform-independent as possible. Xilinx®, Artix®, Vivado®, and Zynq® are registered trademarks of Xilinx Inc. Nexys-4 and ZyBo are trademarks of Digilent, Inc. Other product and company names mentioned may be trademarks of their respective owners. The research results reported in this book were supported by Portuguese National Funds through the FCT—Foundation for Science and Technology, in the context of the project UID/CEC/00127/2019. ix