FPGA–based Implementation of Signal Processing Systems

An important working resource for engineers and researchers involved in the design, development, and implementation of signal processing systems

The last decade has seen a rapid expansion of the use of field programmable gate arrays (FPGAs) for a wide range of applications beyond traditional digital signal processing (DSP) systems. Written by a team of experts working at the leading edge of FPGA research and development, this second edition of FPGA–based Implementation of Signal Processing Systems has been extensively updated and revised to reflect the latest iterations of FPGA theory, applications, and technology. Written from a system–level perspective, it features expert discussions of contemporary methods and tools used in the design, optimization and implementation of DSP systems using programmable FPGA hardware. And it provides a wealth of practical insights along with illustrative case studies and timely real–world examples of critical concern to engineers working in the design and development of DSP systems for radio, telecommunications, audio–visual, and security applications, as well as bioinformatics, Big Data applications, and more. Inside you will find up–to–date coverage of:

FPGA solutions for Big Data Applications, especially as they apply to huge data sets The use of ARM processors in FPGAs and the transfer of FPGAs towards heterogeneous computing platforms The evolution of High Level Synthesis tools including new sections on Xilinx′s HLS Vivado tool flow and Altera′s OpenCL approach Developments in Graphical Processing Units (GPUs), which are rapidly replacing more traditional DSP systems

FPGA–based Implementation of Signal Processing Systems, 2nd Edition is an indispensable guide for engineers and researchers involved in the design and development of both traditional and cutting–edge data and signal processing systems. Senior–level electrical and computer engineering graduates studying signal processing or digital signal processing also will find this volume of great interest.

List of abbreviations 11

Preface 17

1 Introduction to Field Programmable Gate Arrays 1

1.1 Introduction 1

1.2 Field Programmable Gate Arrays 2

1.2.1 Rise of Heterogeneous Computing Platforms 4

1.2.2 Programmability and DSP 4

1.3 Influence of Programmability 6

1.4 Challenges of FPGAs 8

Bibliography 10

2 DSP Basics 11

2.1 Introduction 11

2.2 Definition of DSP Systems 12

2.2.1 Sampling 14

2.2.2 Sampling Rate 15

2.3 DSP Transformations 16

2.3.1 Discrete Fourier Transform 16

2.3.2 Fast Fourier Transform 17

2.3.3 Discrete Cosine Transform 19

2.3.4 Wavelet Transform 20

2.4 Filters 20

2.4.1 Finite Impulse Response Filter 21

2.4.2 Infinite Impulse Response filter 23

2.4.3 Wave Digital Filters 26

2.5 Adaptive Filtering 31

2.5.1 Applications of Adaptive Filters 32

2.5.2 Adaptive Algorithms 33

2.5.3 LMS Algorithm 33

2.5.4 RLS Algorithm 35

2.5.5 Squared Givens Rotations 40

2.6 Final Comments 41

Bibliography 42

3 Arithmetic Basics 45

3.1 Introduction 45

3.2 Number Representations 46

3.2.1 Signed Magnitude 47

3.2.2 One s Complement 48

3.2.3 Two s Complement 48

3.2.4 Binary Coded Decimal 48

3.2.5 Fixed–point Representation 48

3.2.6 Floating–point Representation 50

3.3 Arithmetic Operations 51

3.3.1 Adders 51

3.3.2 Adders and Subtracters 53

3.3.3 Adder Final Remarks 55

3.3.4 Multipliers 55

3.4 Alternative Number Representations 60

3.4.1 Signed Digit Number Representation 60

3.4.2 Logarithmic Number Systems 62

3.4.3 Residue Number Systems 62

3.4.4 CORDIC 63

3.5 Division 64

3.5.1 Recurrence Division 64

3.5.2 Division by Functional Iteration 65

3.6 Square Root 65

3.6.1 Digit Recurrence Square Root 65

3.6.2 Square Root by Functional Iteration 67

3.6.3 Initial Approximation Techniques 68

3.7 Fixed–point versus Floating–point 70

3.7.1 Floating–point on FPGA 71

3.8 Conclusions 72

Bibliography 72

4 Technology Review 75

4.1 Introduction 75

4.2 Implications of Technology Scaling 76

4.3 Architecture and Programmability 77

4.4 DSP Functionality Characteristics 79

4.4.1 Computational Complexity 79

4.4.2 Parallelism 80

4.4.3 Data Independency 81

4.4.4 Arithmetic Requirements 81

4.4.5 Processor Classification 82

4.5 Microprocessors 82

4.5.1 ARM Microprocessor Architecture Family 84

4.5.2 Parallella Computer 85

4.6 DSP Processors 87

4.6.1 Evolutions in DSP Microprocessors 89

4.6.2 TMS 320C6678 Multicore DSP 90

4.7 Graphical Processing Units 92

4.7.1 GPU Architecture 93

4.8 System–on–Chip Solutions 94

4.8.1 Systolic Arrays 95

4.9 Heterogeneous Computing Platforms 97

4.10 Conclusions 97

Bibliography 98

5 Current FPGA Technologies 99

5.1 Introduction 99

5.2 Toward FPGAs 100

5.2.1 Early FPGA Architectures 102

5.3 Altera Stratix® V and 10 FPGA family 104

5.3.1 ALMs 105

5.3.2 Memory Organization 106

5.3.3 DSP Processing Blocks 108

5.3.4 Clocks and Interconnect 109

5.3.5 Stratix® 10 innovations 109

5.4 Xilinx UltrascaleTM/Virtex–7 FPGA families 110

5.4.1 Configurable Logic Block 110

5.4.2 Memory 111

5.4.3 Digital Signal Processing 112

5.5 Xilinx Zynq FPGA Family 113

5.6 Lattice iCE40isp FPGA Family 114

5.6.1 Programmable Logic Blocks 116

5.6.2 Memory 116

5.6.3 Digital Signal Processing 117

5.7 MicroSemi RTG4 FPGA Family 117

5.7.1 Programmable Logic Blocks 118

5.7.2 Memory 118

5.7.3 Mathblocks for DSP 119

5.8 Design Stratregies for FPGA–based DSP Systems 119

5.8.1 DSP Processing Elements 119

5.8.2 Memory Organization 119

5.8.3 Other FPGA–based Design Guidelines 120

5.9 Conclusions 121

Bibliography 121

6 Detailed FPGA Implementation Techniques 123

6.1 Introduction 123

6.2 FPGA Functionality 124

6.2.1 LUT Functionality 125

6.2.2 DSP Processing Elements 127

6.2.3 Memory Availability 128

6.3 Mapping to LUT–based FPGA Technology 130

6.3.1 Reductions in Inputs/Outputs 130

6.3.2 Controller Design 133

6.4 Fixed Coefficient DSP 133

6.4.1 Fixed Coefficient FIR Filtering 133

6.4.2 DSP Transforms 134

6.4.3 Fixed Coefficient FPGA Techniques 137

6.5 Distributed Arithmetic 138

6.5.1 DA Expansion 138

6.5.2 DA Applied to FPGA 141

6.6 Reduced Coefficient Multiplier 142

6.6.1 DCT Example 142

6.6.2 RCM Design Procedure 142

6.6.3 FPGA Multiplier Summary 145

6.7 Final Statements 146

Bibliography 146

7 Synthesis Tools for FPGAs 149

7.1 Introduction 149

7.2 High Level Synthesis 150

7.2.1 HLS from C–based Languages 152

7.3 Xilinx Vivado 153

7.4 Control Logic Extraction Phase Example 154

7.5 Altera SDK for OpenCL 155

7.6 Other HLS Tools 157

7.6.1 Catapult 157

7.6.2 Impulse–C 157

7.6.3 GAUT 158

7.6.4 CAL 158

7.6.5 LegUp 160

7.7 Conclusions 160

Bibliography 160

8 Architecture Derivation for FPGA–based DSP Systems 163

8.1 Introduction 163

8.2 DSP Algorithm Characteristics 164

8.2.1 Further Characterization 166

8.3 DSP Algorithm Representations 169

8.3.1 SFG Descriptions 169

8.3.2 DFG Descriptions 170

8.4 Pipelining DSP Systems 171

8.4.1 Retiming 171

8.4.2 Cut–set Theorem 176

8.4.3 Application of Delay Scaling 179

8.4.4 Calculation of Pipelining Period 180

8.4.5 Longest Path Matrix Algorithm 181

8.5 Parallel Operation 184

8.5.1 Unfolding 187

8.5.2 Folding 190

8.6 Conclusions 194

Bibliography 195

9 Complex DSP Core Design for FPGA 197

9.1 Introduction 197

9.2 Motivation for Design for Reuse 198

9.3 Intellectual Property Cores 199

9.4 Evolution of IP cores 202

9.4.1 Arithmetic Libraries 203

9.4.2 Complex DSP Functions 204

9.4.3 Future of IP Cores 205

9.5 Parameterizable (Soft) IP Cores 205

9.5.1 Identifying Design Components Suitable for Development as IP 207

9.5.2 Identifying Parameters for IP Cores 208

9.5.3 Development of Parameterizable Features 212

9.5.4 Parameterizable Control Circuitry 213

9.5.5 Application to Simple FIR Filter 213

9.6 IP Core Integration 214

9.6.1 Design Issues 214

9.7 Current FPGA–based IP cores 216

9.8 Watermarking IP 217

9.9 Summary 217

Bibliography 218

10 Advanced Model–Based FPGA Accelerator Design 221

10.1 Introduction 221

10.2 Dataflow Modeling of DSP Systems 222

10.2.1 Process Networks 222

10.2.2 Synchronous Dataflow 223

10.2.3 Cyclo–static Dataflow 224

10.2.4 Multidimensional Synchronous Dataflow 225

10.3 Architectural Synthesis of Custom Circuit Accelerators from DFGs 226

10.4 Model–Based Development of Multi–Channel Dataflow Accelerators 227

10.4.1 Multidimensional Arrayed Dataflow 229

10.4.2 Block and Interleaved Processing in MADF 230

10.4.3 MADF Accelerators 232

10.4.4 Pipelined FE Derivation for MADF Accelerators 233

10.4.5 WBC Configuration 235

10.4.6 Design Example: Normalized Lattice Filter 236

10.4.7 Design Example: Fixed Beamformer System 239

10.5 Model–Based Development for Memory–Intensive Accelerators 242

10.5.1 Synchronous Dataflow Representation of FSME 242

10.5.2 Cyclo–Static Representation of FSME 244

10.6 Summary 247

Bibliography 247

11 Adaptive beamformer example 249

11.1 Introduction to adaptive beamforming 250

11.2 Generic design process 251

11.2.1 Adaptive Beamforming Specification 253

11.2.2 Algorithm development 254

11.3 Algorithm to architecture 255

11.3.1 Dependence graph 256

11.3.2 Signal Flow Graph 257

11.4 Efficient Architecture Design 258

11.4.1 Scheduling the QR operations 263

11.5 Generic QR architecture 266

11.5.1 Processor Array 266

11.6 Retiming the generic architecture 271

11.6.1 Retiming QR architectures 278

11.7 Parameterizable QR architecture 282

11.7.1 Choice of architecture 282

11.7.2 Parameterizable control 283

11.7.3 Linear architecture 284

11.7.4 Sparse linear architecture 284

11.7.5 Rectangular architecture 289

11.7.6 Sparse rectangular architecture 290

11.7.7 Generic QR cells 292

11.8 Generic control 292

11.8.1 Generic input control for linear and the sparse linear arrays 293

11.8.2 Generic input control for rectangular and the sparse rectangular arrays 294

11.8.3 Effect of latency on the control seeds 295

11.9 Beamformer design example 297

11.10Chapter summary 298

Bibliography 299

12 FPGA solutions for Big Data applications 301

12.1 Introduction 301

12.2 Big Data 302

12.3 Big Data analytics 303

12.3.1 Inductive learning 304

12.3.2 Data Mining algorithms 305

12.3.3 Classification 306

12.3.4 Regression 307

12.3.5 Clustering 308

12.3.6 The right approach 308

12.4 Acceleration 309

12.4.1 Scaling up or scaling out 309

12.4.2 FPGA–based system developments 309

12.4.3 FPGA implementations 310

12.4.4 Heston Model acceleration using FPGA 311

12.5 k–means clustering FPGA implementation 313

12.5.1 Computational Complexity analysis of k–means algorithm 314

12.6 FPGA–based soft processors 315

12.6.1 IPPro FPGA–based processor 316

12.7 System Hardware 320

12.7.1 Distance Calculation Block 321

12.7.2 Comparison Block 322

12.7.3 Averaging 322

12.7.4 Optimizations 322

12.8 Conclusions 322

Bibliography 323

13 Low power FPGA implementation 327

13.1 Introduction 327

13.2 Sources of power consumption 328

13.2.1 Dynamic power consumption 328

13.2.2 Static power consumption 330

13.3 FPGA power consumption 333

13.3.1 Clock tree isolation 334

13.4 Power consumption reduction techniques 334

13.5 Dynamic voltage scaling in FPGAs 335

13.6 Reduction in switched capacitance 337

13.6.1 Data re–ordering 337

13.6.2 Pipelining 338

13.6.3 Locality 343

13.6.4 Data mapping 345

13.7 Final Comments 349

Bibliography 350

14 Final Statements 353

14.1 Introduction 353

14.2 Evolution in FPGA design approaches 354

14.3 Big Data and shift towards computing 355

14.4 Programming flow for FPGAs 356

14.5 Support for floating–point arithmetic 356

14.6 Memory Architectures 357

Bibliography 357

Roger Woods is a full professor and Research Director for the Electronics and Computer Engineering Cluster at Queens University Belfast. His research interests include heterogeneous programmable systems and system–level tools for data, signal and image processing and telecommunications. He is on the Advisory Board for the IEEE Technical Advisory Group on the Design and Implementation of Signal Processing Systems, on the Editorial Board for the ACM Transactions on Reconfigurable Technology and Systems, Journal of VLSI Signal Processing Systems and IET Proceedings on Computer and Digital Techniques, and on the program committee of a number of IEEE FPGA–based conferences. He has co–founded a spin–off company, Analytics Engines Ltd., which looks to accelerate data analytics and acts as their Chief Scientist. He holds 4 patents and has published over 200 papers.

John McAllister is an academic at Queen s University Belfast. His research interest lies in domain–specific embedded computing for signal and data processing, including dataflow languages and system design, distributed signal processing and machine learning and compilation and system synthesis. This work spans a wide spectrum of applications, from biomedical through software defined radio, neuromorphic systems and large–scale analytics. He is an Associate Editor of IEEE Transactions on Signal Processing, a member of the Editorial Board of Journal of Signal Processing Systems, a member of the Advisory Board to the IEEE Technical Committee on Design and Implementation of Signal Processing Systems, founding Chief Editor of the IEEE Signal Processing Society Resource Center (http://rc.signalprocessingsociety.org/) and a co–founder of Analytics Engines Ltd.

Gaye Lightbody is a Lecturer within the School of Computing and Mathematics in Ulster University. She received an M.Eng. (1995) and a PhD (2000) in Electrical and Electronic Engineering from Queen s University Belfast. Her PhD, High Performance VLSI Architectures for Recursive Least Squares Adaptive Filtering, involved the research and development into a scalable efficient architecture for highly intensive adaptive beamforming applications. Gaye worked in industry from 2000 to 2005 for Amphion Semiconductor developing intellectual property cores for ASIC and FPGA solutions in the areas of audio, image and video processing. Since joining Ulster University, after Amphion, her research interests have included biomedical signal processing, Brain Computer Interfaces, FPGAs and high performance computing.

Ying Yi is currently a Senior Software Engineer at SN Systems, a wholly owned subsidiary of Sony Interactive Entertainment Inc. She has a PhD on DSP architectural Synthesis Tools for FPGAs from the School of Electrical and Electronic Engineering, Queen s University Belfast, 2003. She was a Research Fellow at Integrated Micro and Nano Systems (IMNS) Institute, University of Edinburgh from 2004 to 2009 and a Senior Software Engineer at Spiral Gateway Ltd. from 2007 to 2009. Her research interests include software tool flow for the reconfigurable architecture and the single–chip multi–core architectures, compiler optimisation and code generation. She holds 1 patent and has published more than 30 refereed research papers on Journal of VLSI Signal Processing, IEEE Transactions on Computer–Aided Design, IEEE Transactions on Very Larger Scale Integration (VLSI) Systems, and Scalable Computing: Practice and Experience, Scientific International Journal for Parallel and Distributed Computing, and various IEEE conferences.