Martin Kumm Multiple Constant Multi- plication Optimizations for Field Programmable Gate Arrays Multiple Constant Multiplication Optimizations for Field Programmable Gate Arrays Martin Kumm Multiple Constant Multiplication Optimizations for Field Programmable Gate Arrays With a preface by Prof. Dr.-Ing. Peter Zipf Martin Kumm Kassel, Germany Dissertation of Martin Kumm in the Department of Electrical Engineering and Computer Science at the University of Kassel. Date of Disputation: October 30th, 2015 ISBN 978-3-658-13322-1 ISBN 978-3-658-13323-8 (eBook) DOI 10.1007/978-3-658-13323-8 Library of Congress Control Number: 2016935387 Springer Vieweg © Springer Fachmedien Wiesbaden 2016 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part 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 or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. 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, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. Printed on acid-free paper This Springer Vieweg imprint is published by Springer Nature The registered company is Springer Fachmedien Wiesbaden GmbH Preface As silicon technology advances, field programmable gate arrays appear to gaingroundagainstthetraditionalASICprojectstarts,reachingouttoform the mainstream implementation basis. Their predefined structures result in an essential inefficiency, or performance gap at all relevant axes, i.e. clock frequency, power and area. Thus, highly optimised system realisations be- come more and more important to use this technology at its best. Microar- chitectures and their adaptation to the FPGA hardware, combined with an optimal matching of model structures and FPGA structures, are two points ofactionwhereengineerscantrytogetoptimallybalancedsolutionsfortheir designs, thus fighting the performance gap towards the ASIC reference. While microarchitecture design based on the knowledge of FPGA struc- turesislocatedinthedomainoftraditionalhardwareengineering, themap- ping and matching is based on EDA algorithms and thus strongly related to computer science. Algorithms and the related sophisticated tools are permanently in short supply for leading edge optimisation needs. Martin’s dissertation deals with the algorithmic optimisation of circuits for the multiplication of a variable with constants in different flavours. As this type of operations is elementary in all areas of digital signal processing and also usually on the critical path, his approaches and results are of high relevancenotonlybythemselvesbutalsoasadirectionforfurtherresearch. His direct contributions are the advancement of algorithmic treatment of pipeline-based multiplier circuits using heuristics and exact optimisation al- gorithms, the adaptation of several algorithms to the specific conditions of field programmable gate arrays, specifically lookup-table based multipliers, ternary adders and embedded multipliers with fixed word length, and the transferofhisfindingstoafloating-pointmultiplierarchitectureformultiple constants. Along with all the accompanying details, this is a large range of topics Martin presents here. It is an impressive and comprehensive achievement, convincing by its depth of discussion as well as its contributions in each of the areas. VI Preface MartinwasoneofmyfirstPhDcandidates. Thrownintotheculturalcon- flict between computer science and electrical engineering he soon developed a sense for the symbiosis of both disciplines. The approach and results are symptomatical for this developing interdisciplinary area, where systems and their optimisation algorithms are developed corporately. IfoundMartin’stextexcitingtoread,asitisacomprehensiveworkwithin the ongoing discussion of algorithmic hardware optimisation. His work is supportedbyalonglistofsuccessfulpublications. Itissurelyacontribution worth reading. Kassel, 22. of April, 2016 Prof. Dr.-Ing. Peter Zipf Abstract Digital signal processing (DSP) plays a major role in nearly any modern electronic system used in mobile communication, automotive control units, biomedical applications and high energy physics, just to name a few. A very frequent but resource intensive operation in DSP related systems is the multiplication of a variable by several constants, commonly denoted as multiple constant multiplication (MCM). It is needed, e.g., in digital filters and discrete transforms. While high performance DSP systems were tradi- tionally realized as application specific integrated circuits (ASICs), there is an ongoing and increasing trend to use generic programmable logic ICs like fieldprogrammablegatearrays(FPGAs). However,onlylittleattentionhas been paid on the optimization of MCM circuits for FPGAs. In this thesis, FPGA-specific optimizations of MCM circuits for low re- source usage but high performance are considered. Due to the large FPGA- specificroutingdelays,onekeyforhighperformanceispipelining. Theopti- mizationofpipelinedMCMcircuitsisconsideredinthefirstpartofthethe- sis. First,amethodthatoptimallypipelinesagiven(notnecessaryoptimal) MCM circuit using integer linear programming (ILP) is proposed. Then, it is shown that the direct optimization of a pipelined MCM circuit, formally defined as the pipelined MCM (PMCM) problem, is beneficial. This is done by presenting novel heuristic and optimal ILP-based methods to solve the PMCM problem. Besides this, extensions to the MCM problem with adder depth (AD) constraints and an extension for optimizing a related problem – the pipelined multiplication of a constant matrix with a vector – are given. While these methods are independent of the target device and reduce the number of arithmetic and storage components, i.e., adders, subtracters and pipeline registers, FPGA-specific optimizations are considered in the second part of the thesis. These optimizations comprise the inclusion of look-up table(LUT)-basedconstantmultipliers,embeddedmultipliersandtheuseof ternary(3-input)adderswhichcanbeefficientlymappedtomodernFPGAs. In addition, an efficient architecture to perform MCM operations in floating point arithmetic is given. Acknowledgements First of all, I would like to thank my supervisor, Prof. Dr.-Ing. Peter Zipf, who gave me the opportunity to do my PhD under his supervision. He provided an excellent guidance and was always open-minded to new and ex- ceptional ideas, leading to creative and fruitful discussions. I also thank my colleagues at the digital technology group of the University of Kassel. In special, Michael Kunz, who had many ideas how to prepare the course ma- terial and Konrad M¨oller, who started as student with his project work and master’s thesis and is now a highly-valued colleague. Our mathematicians, Diana Fangh¨anel, Do¨rthe Janssen and Evelyn Lerche, were always open to help with math related questions. The deep understanding in discrete opti- mization and ILP (and more) of Diana Fangh¨anel helped a lot in obtaining some of the results in this work. I am grateful to all the students that con- tributedtopartsofthisthesiswiththeirbachelorormaster’sthesis,project workorstudentjob: MartinHardieck,whodidagreatjobintheC++imple- mentation of RPAG extensions for ternary adders and the constant matrix multiplication (and the combination of both) during his project work, his diploma thesis and his student job; Katharina Liebisch, for implementing MCM floating point units for reference; Jens Willkomm, who realized the ternary adder at primitive level for Xilinx FPGAs during his project work; andMarcoKleinlein,whoimplementedflexibleVHDLcodegeneratorsbased on the Floating Point Core Generator (FloPoCo) library [1]. I would also liketothankourexternalPhDcandidatesEugenBayerandCharles-Frederic Mu¨ller for interesting discussions and collaborative work. I also appreciate the financial support of the German research council which allowed me to stay in a post-doc position in Kassel. DuringthePhD,IstartedcooperationswithChipHongChangandMath- ias Faust from the Nanyang Technological University, Singapore, Oscar Gustafsson and Mario Garrido from the University of Linko¨ping, Sweden, and Uwe Meyer-Baese from the Florida State University, USA. Especially, I am very grateful to Oscar Gustafsson to invite me as guest researcher in his group. Exchanging ideas with people from the same field expanded my horizon enormously. Thanks to the ERASMUS program, two visits in X Acknowledgements Linko¨ping were possible and further visits are planned. Another big help was the friendly support of other researchers. Levent Aksoy was always fast in answering questions, providing filter benchmark data or even the source code of their algorithms. My thanks also go to Florent de Dinechin and all the contributors of the FloPoCo library [1] for providing their implementa- tions as open-source [2]. Open-source in research simplifies the comparison with other work which inspired me to publish the presented algorithms as open-source, too. Last but not least, I want to kindly thank my wife Nadine and my son Jonathan. Their love and support gave me the energy to create this thesis. Contents Preface V Abstract VII Acknowledgements IX Contents XI List of Figures XIX List of Tables XXIII Abbreviations XXVII Nomenclature XXX Author’s Publications XXXI 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Goal and Contributions of the Thesis . . . . . . . . . . . . . . 2 1.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . 3 1.4 Applications of Multiple Constant Multiplication . . . . . . . 5 2 Background 9 2.1 Single Constant Multiplication . . . . . . . . . . . . . . . . . 9 2.1.1 Binary Multiplication . . . . . . . . . . . . . . . . . . 9