none c{=“newline,}=[; ]
“newline,} =,};=
“newline,;=[ ]“space

# Parallel Programming for FPGAs

Ryan Kastner, Janarbek Matai, and Stephen Neuendorffer

Copyright 2011-2024.

This work is licensed under the Creative Commons Attribution 4.0 International
License.

To view a copy of this license, visit
http://creativecommons.org/licenses/by/3.0/.

The newest version of this book can be found at http://hlsbook.ucsd.edu. The
authors welcome your feedback and suggestions.

###### Contents

  1. Preface
  2. Acknowledgements
  3. 1 Introduction
    1. 1.1 High-level Synthesis (HLS)
    2. 1.2 FPGA Architecture
    3. 1.3 FPGA Design Process
    4. 1.4 Design Optimization
      1. 1.4.1 Performance Characterization
      2. 1.4.2 Area/Throughput Tradeoffs
      3. 1.4.3 Restrictions on Processing Rate
      4. 1.4.4 Coding Style
    5. 1.5 Restructured Code
    6. 1.6 Book Organization
  4. 2 Finite Impulse Response (FIR) Filters
    1. 2.1 Overview
    2. 2.2 Background
    3. 2.3 Base FIR Architecture
    4. 2.4 Calculating Performance
    5. 2.5 Operation Chaining
    6. 2.6 Code Hoisting
    7. 2.7 Loop Fission
    8. 2.8 Loop Unrolling
    9. 2.9 Loop Pipelining
    10. 2.10 Bitwidth Optimization
    11. 2.11 Complex FIR Filter
    12. 2.12 Conclusion
  5. 3 CORDIC
    1. 3.1 Overview
    2. 3.2 Background
    3. 3.3 Calculating Sine and Cosine
    4. 3.4 Cartesian to Polar Conversion
    5. 3.5 Number Representation
      1. 3.5.1 Binary and Hexadecimal Numbers
      2. 3.5.2 Negative numbers
      3. 3.5.3 Overflow, Underflow, and Rounding
      4. 3.5.4 Binary arithmetic
      5. 3.5.5 Representing Arbitrary Precision Integers in C and C++
      6. 3.5.6 Floating Point
    6. 3.6 Further Optimizations
    7. 3.7 Conclusion
  6. 4 Discrete Fourier Transform
    1. 4.1 Fourier Series
    2. 4.2 DFT Background
    3. 4.3 Matrix-Vector Multiplication Optimizations
    4. 4.4 Pipelining and Parallelism
    5. 4.5 Storage Tradeoffs and Array Partitioning
    6. 4.6 Baseline Implementation
    7. 4.7 DFT optimization
    8. 4.8 Conclusion
  7. 5 Fast Fourier Transform
    1. 5.1 Background
    2. 5.2 Baseline Implementation
    3. 5.3 Bit Reversal
    4. 5.4 Task Pipelining
    5. 5.5 Conclusion
  8. 6 Sparse Matrix Vector Multiplication
    1. 6.1 Background
    2. 6.2 Baseline Implementation
    3. 6.3 Testbench
    4. 6.4 Specifying Loop Properties
    5. 6.5 C/RTL Cosimulation
    6. 6.6 Loop Optimizations and Array Partitioning
    7. 6.7 Conclusion
  9. 7 Matrix Multiplication
    1. 7.1 Background
    2. 7.2 Complete Matrix Multiplication
    3. 7.3 Block Matrix Multiplication
    4. 7.4 Conclusion
  10. 8 Prefix Sum and Histogram
    1. 8.1 Prefix Sum
    2. 8.2 Histogram
    3. 8.3 Histogram Optimization and False Dependencies
    4. 8.4 Increasing Histogram Performance
    5. 8.5 Conclusion
  11. 9 Video Systems
    1. 9.1 Background
      1. 9.1.1 Representing Video Pixels
      2. 9.1.2 Digital Video Formats
      3. 9.1.3 Video Processing System Architectures
    2. 9.2 Implementation
      1. 9.2.1 Line Buffers and Frame Buffers
      2. 9.2.2 Causal Filters
      3. 9.2.3 Boundary Conditions
    3. 9.3 Conclusion
  12. 10 Sorting Algorithms
    1. 10.1 Introduction
    2. 10.2 Insertion Sort
      1. 10.2.1 Basic Insertion Sort Implementation
      2. 10.2.2 Parallelising Insertion Sort
      3. 10.2.3 Explicit Systolic Array For Insertion Sort
    3. 10.3 Merge Sort
      1. 10.3.1 Basic Merge Sort
      2. 10.3.2 Restructured Merge Sort
    4. 10.4 Conclusion
  13. 11 Huffman Encoding
    1. 11.1 Background
    2. 11.2 Implementation
      1. 11.2.1 Filter
      2. 11.2.2 Sort
      3. 11.2.3 Create Tree
      4. 11.2.4 Compute Bit Length
      5. 11.2.5 Truncate Tree
      6. 11.2.6 Canonize Tree
      7. 11.2.7 Create Codeword
      8. 11.2.8 Testbench
    3. 11.3 Conclusion

## Preface

“When someone says, ’I want a programming language in which I need only say
what I wish done’, give him a lollipop.” -Alan Perlis

This book focuses on the use of algorithmic high-level synthesis (HLS) to
build application-specific FPGA systems. Our goal is to give the reader an
appreciation of the process of creating an optimized hardware design using
HLS. Although the details are, of necessity, different from parallel
programming for multicore processors or GPUs, many of the fundamental concepts
are similar. For example, designers must understand memory hierarchy and
bandwidth, spatial and temporal locality of reference, parallelism, and
tradeoffs between computation and storage.

This book is a practical guide for anyone interested in building FPGA systems.
In a university environment, it is appropriate for advanced undergraduate and
graduate courses. At the same time, it is also useful for practicing system
designers and embedded programmers. The book assumes the reader has a working
knowledge of C/C++ and includes a significant amount of sample code. In
addition, we assume familiarity with basic computer architecture concepts
(pipelining, speedup, Amdahl’s Law, etc.). A knowledge of the RTL-based FPGA
design flow is helpful, although not required.

The book includes several features that make it particularly valuable in a
classroom environment. It includes questions within each chapter that will
challenge the reader to solidify their understanding of the material. It
provides specific projects in the Appendix. These were developed and used in
the HLS class taught at UCSD (CSE 237C). We will make the files for these
projects available to instructors upon request. These projects teach concepts
in HLS using examples in the domain of digital signal processing with a focus
on developing wireless communication systems. Each project is more or less
associated with one chapter in the book. The projects have reference designs
targeting FPGA boards distributed through the Xilinx University Program
(http://www.xilinx.com/support/university.html). The FPGA boards are available
for commercial purchase. Any reader of the book is encouraged to request an
evaluation license of Vivado® HLS at http://www.xilinx.com.

This book is not primarily about HLS algorithms. There are many excellent
resources that provide details about the HLS process including algorithms for
scheduling, resource allocation, and binding [51, 29, 18, 26]. This book is
valuable in a course that focuses on these concepts as supplementary material,
giving students an idea of how the algorithms fit together in a coherent form,
and providing concrete use cases of applications developed in a HLS language.
This book is also not primarily about the intricacies of FPGA architectures or
RTL design techniques. However, again it may be valuable as supplementary
material for those looking to understand more about the system-level context.

This book focuses on using Xilinx tools for implementing designs, in
particular Vivado® HLS to perform the translation from C-like code to RTL. C
programming examples are given that are specific to the syntax used in Vivado®
HLS. In general, the book explains not only Vivado® HLS specifics, but also
the underlying generic HLS concepts that are often found in other tools. We
encourage readers with access to other tools to understand how these concepts
are interpreted in any HLS tool they may be using.

Good luck and happy programming!

## Acknowledgements

Many people have contributed to making this book happen. Probably first and
foremost are the many people who have done research in the area of High-Level
Synthesis. Underlying each of the applications in this book are many
individual synthesis and mapping technologies which combine to result in high-
quality implementations.

Many people have worked directly on the Vivado® HLS tool over the years. From
the beginning in Jason Cong’s research group at UCLA as the AutoPilot tool, to
making a commercial product at AutoESL Inc., to widespread adoption at Xilinx,
it’s taken many hours of engineering to build an effective tool. To Zhiru
Zhang, Yiping Fan, Bin Liu, Guoling Han, Kecheng Hao, Peichen Pan, Devadas
Varma, Chuck Song, and many others: your efforts are greatly appreciated.

The idea for this book originally arose out of a hallway conversation with
Salil Raje shortly after Xilinx acquired the AutoESL technology. Much thanks
to Salil for his early encouragement and financial support. Ivo Bolsens and
Kees Vissers also had the trust that we could make something worth the effort.
Thanks to you all for having the patience to wait for good things to emerge.

This book would not have been possible without substantial support from the
UCSD Wireless Embedded Systems Program. This book grew out of the need to make
a hardware design class that could be broadly applicable to students coming
from a mix of software and hardware backgrounds. The program provided
substantial resources in terms of lab instructors, teaching assistants, and
supplies that were invaluable as we developed (and re-developed) the
curriculum that eventually morphed into this book. Thanks to all the UCSD 237C
students over the years for providing feedback on what made sense, what
didn’t, and generally acting as guinea pigs over many revisions of the class
and this book. Your suggestions and feedback were extremely helpful. A special
thanks to the TAs for these classes, notable Alireza Khodamoradi, Pingfan
Meng, Dajung Lee, Quentin Gautier, and Armaiti Ardeshiricham; they certainly
felt the growing pains a lot more than the instructor.

Various colleagues have been subjected to early drafts of the book, including
Zhiru Zhang, Mike Wirthlin, Jonathan Corbett. We appreciate your feedback.

##  Chapter 1 Introduction

###  1.1 High-level Synthesis (HLS)

The hardware design process has evolved significantly over the years. When the
circuits were small, hardware designers could more easily specify every
transistor, how they were wired together, and their physical layout.
Everything was done manually. As our ability to manufacture more transistors
increased, hardware designers began to rely on automated design tools to help
them in the process of creating the circuits. These tools gradually become
more and more sophisticated and allowed hardware designers to work at higher
levels of abstraction and thus become more efficient. Rather than specify the
layout of every transistor, a hardware designer could instead specify digital
circuits and have electronic design automation (EDA) tools automatically
translate these more abstract specifications into a physical layout.

The Mead and Conway approach [50] of using a programming language (e.g.,
Verilog or VHDL) that compiles a design into physical chips took hold in the
1980s. Since that time, the hardware complexity has continued to increase at
an exponential rate, which forced hardware designers to move to even more
abstract hardware programming languages. register-transfer level (RTL) was one
step in abstraction, enabling a designer to simply specify the registers and
the operations performed on those registers, without considering how the
registers and operations are eventually implementation. EDA tools can
translate RTL specifications into a digital circuit model and then
subsequently into the detailed specification for a device that implements the
digital circuit. This specification might be the files necessary to
manufacture a custom device or might be the files necessary to program an off-
the-shelf device, such as an field-programmable gate array (FPGA). Ultimately,
the combination of these abstractions enables designers to build
extraordinarily complex systems without getting lost in the details of how
they are implemented. A non-technical perspective on the value of these
abstractions can be found in [42].

high-level synthesis (HLS) is yet another step in abstraction that enables a
designer to focus on larger architectural questions rather than individual
registers and cycle-to-cycle operations. Instead a designer captures behavior
in a program that does not include specific registers or cycles and an HLS
tool creates the detailed RTL micro-architecture. One of the first tools to
implement such a flow was based on behavioral Verilog and generated an RTL-
level architecture also captured in Verilog[35]. Many commercial tools now use
C/C++ as the input language. For the most part the language is unimportant,
assuming that you have a tool that accepts the program you want to synthesize!

Fundamentally, algorithmic HLS does several things automatically that an RTL
designer does manually:

  * •

HLS analyzes and exploits the concurrency in an algorithm.

  * •

HLS inserts registers as necessary to limit critical paths and achieve a
desired clock frequency.

  * •

HLS generates control logic that directs the data path.

  * •

HLS implements interfaces to connect to the rest of the system.

  * •

HLS maps data onto storage elements to balance resource usage and bandwidth.

  * •

HLS maps computation onto logic elements performing user specified and
automatic optimizations to achieve the most efficient implementation.

Generally, the goal of HLS is to make these decisions automatically based upon
user-provided input specification and design constraints. However, HLS tools
greatly differ in their ability to do this effectively. Fortunately, there
exist many mature HLS tools (e.g., Xilinx Vivado® HLS, LegUp [13], and Mentor
Catapult HLS) that can make these decisions automatically for a wide range of
applications. We will use Vivado® HLS as an exemplar for this book; however,
the general techniques are broadly applicable to most HLS tools though likely
with some changes in input language syntax/semantics.

In general, the designer is expected to supply the HLS tool a functional
specification, describe the interface, provide a target computational device,
and give optimization directives. More specifically, Vivado® HLS requires the
following inputs:

  * •

A function specified in C, C++, or SystemC

  * •

A design testbench that calls the function and verifies its correctness by
checking the results.

  * •

A target FPGA device

  * •

The desired clock period

  * •

Directives guiding the implementation process

In general, HLS tools can not handle any arbitrary software code. Many
concepts that are common in software programming are difficult to implement in
hardware. Yet, a hardware description offers much more flexibility in terms of
how to implement the computation. It typically requires additional information
to be added by the designers (suggestions or #pragmas) that provide hints to
the tool about how to create the most efficient design. Thus, HLS tools
simultaneously limit and enhance the expressiveness of the input language. For
example, it is common to not be able to handle dynamic memory allocation.
There is often limited support for standard libraries. System calls are
typically avoided in hardware to reduce complexity. The ability to perform
recursion is often limited. On the other hand, HLS tools can deal with a
variety of different interfaces (direct memory access, streaming, on-chip
memories). And these tools can perform advanced optimizations (pipelining,
memory partitioning, bitwidth optimization) to create an efficient hardware
implementation.

We make the following assumptions about the input function specification,
which generally adheres to the guidelines of the Vivado® HLS tool:

  * •

No dynamic memory allocation (no operators like malloc(), free(), new, and
delete())

  * •

Limited use of pointers-to-pointers (e.g., may not appear at the interface)

  * •

System calls are not supported (e.g., abort(), exit(), printf(), etc. They can
be used in the code, e.g., in the testbench, but they are ignored (removed)
during synthesis.

  * •

Limited use of other standard libraries (e.g., common math.h functions are
supported, but uncommon ones are not)

  * •

Limited use of function pointers and virtual functions in C++ classes
(function calls must be compile-time determined by the compiler).

  * •

No recursive function calls.

  * •

The interface must be precisely defined.

The primary output of an HLS tool is a RTL hardware design that is capable of
being synthesized through the rest of the hardware design flow. Additionally,
the tool may output testbenches to aid in the verification process. Finally,
the tool will provide some estimates on resource usage and performance.
Vivado® HLS generates the following outputs:

  * •

Synthesizable Verilog and VHDL

  * •

RTL simulations based on the design testbench

  * •

Static analysis of performance and resource usage

  * •

Metadata at the boundaries of a design, making it easier to integrate into a
system.

Once an RTL-level design is available, other tools are usually used in a
standard RTL design flow. In the Xilinx Vivado®Design Suite, logic synthesis
is performed, translating the RTL-level design into a netlist of primitive
FPGA logical elements. The netlist (consisting of logical elements and the
connections between them) is then associated with specific resources in a
target device, a process called place and route (PAR). The resulting
configuration of the FPGA resources is captured in a bitstream, which can be
loaded onto the FPGA to program its functionality. The bitstream contains a
binary representation of the configuration of each FPGA resource, including
logic elements, wire connections, and on-chip memories. A large Xilinx
UltraScale FPGAs will have over 1 billion configuration bits and even the
“smaller” devices have hundreds of millions of bits [64].

###  1.2 FPGA Architecture

It is important to understand the modern FPGA architectures since many of the
HLS optimizations specifically target these features. Over the decades, FPGAs
have gone from small arrays of programmable logic and interconnect to massive
arrays of programmable logic and interconnect with on-chip memories, custom
data paths, high speed I/O, and microprocessor cores all co-located on the
same chip. In this section, we discuss the architectural features that are
relevant to HLS. It is not our intention (nor do we think it is necessary) to
provide substantial details of the FPGA architecture. Rather we aim to give
the reader enough information to understand the HLS reports and successfully
use and leverage the HLS directives, many of which very specifically target
modern FPGA architectural features.

FPGAs are an array of programmable logic blocks and memory elements that are
connected together using programmable interconnect. Typically these logic
blocks are implemented as a lookup table (LUT)– a memory where the address
signal are the inputs and the outputs are stored in the memory entries. An
$n$-bit LUT can be programmed to compute any $n$-input Boolean function by
using the function’s truth table as the values of the LUT memory.

Figure 1.1 a) shows a 2 input LUT. It has $2^{2}=4$ configuration bits. These
bits are the ones that are programmed to determine the functionality of the
LUT. Figure 1.1 b) shows the truth table for a 2 input AND gate. By using the
four values in the “out” column for configuration bits 0-3, we can program
this 2 input LUT to be a 2 input AND gate. The functionality is easily changed
by reprogramming the configuration bits. This is a flexible and fairly
efficient method for encoding smaller Boolean logic functions. Most FPGAs use
a LUTs with 4-6 input bits as their base element for computation. Larger FPGAs
can have millions of these programmable logic elements.

Figure 1.1: Part a) shows a 2 input LUT, i.e., a 2-LUT. Each of the four
configuration bits can be programmed to change the function of the 2-LUT
making it a fully programmable 2 input logic gate. Part b) provides a sample
programming to implement an AND gate. The values in the “out” column from top
to bottom correspond directly to configuration bits 0 through 3. Part c) shows
a simple slice that contains a slightly more complex 3-LUT with the
possibility of storing the output into a FF. Note that there are nine
configuration bits: eight to program the 3-LUT and one to decide whether the
output should be direct from the 3-LUT or the one stored in the FF. More
generally, a slice is defined as a small number of LUTs and FFs combined with
routing logic (multiplexers) to move inputs, outputs, and internal values
between the LUTs and FFs.

How would you program the 2-LUT from Figure 1.1 to implement an XOR gate? An
OR gate? How many programming bits does an $n$ input ($n$-LUT) require?

How many unique functions can a 2-LUT be programmed to implement? How many
unique functions can a $n$ input ($n$-LUT) implement?

The FF is the basic memory element for the FPGA. They are typically co-located
with a LUTs. LUT s can be replicated and combined with FFs and other
specialized functions (e.g., a full adder) to create a more complex logic
element called a configurable logic block (CLB), logic array block (LAB), or
slice depending on the vendor or design tool. We use the term slice since it
is the resource reported by the Vivado® HLS tool. A slice is a small number of
LUTs, FFs and multiplexers combined to make a more powerful programmable logic
element. The exact number and combination of LUTs, FFs and multiplexers varies
by architecture, but generally a slice has only few of each of these elements.
Figure 1.1 c) shows a very simple slice with one 3-LUT and one FF. A slice may
also use some more complex logic functions. For example, it is common to
embedded a full adder into a slice. This is an example of “hardening” the
FPGA; this full adder is not programmable logic – it can only be used as a
full adder, but it is common to use full adders (to make addition operations)
and it is more efficient to use the custom full adder as opposed to
implementing a full adder on the programmable logic (which is also an option).
And thus, overall it is beneficial to have a hard full adder in the slice.

Programmable interconnect is the other key element of an FPGA. It provides a
flexible network of wires to create connections between the slices. The inputs
and outputs of the slice are connected to a routing channel. The routing
channel contains a set configuration bits can be programmed to connect or
disconnect the inputs/outputs of the slice to the programmable interconnect.
Routing channels are connected to switchboxes. A switchbox is a collection of
switches that are implemented as pass transistors. These provide the ability
to connect the routing tracks from one routing channels to another.

Figure 1.2 provides an example of how a slice, routing channel, and switchbox
are connected. Each input/output to the slice can be connected to one of many
routing tracks that exist in a routing channel. You can think of routing
tracks as single bit wires. The physical connections between the slice and the
routing tracks in the routing channel are configured using a pass transistor
that is programmed to perform a connect or disconnect from the input/output of
the slice and the programmable interconnect.

Figure 1.2:  A slice contains a small number of LUTs and FF. We show a very
simple slice with one LUT and one FF though generally these have two or more
of each. Slices are connected to one another using a routing channel and
switchbox. These two provide a programmable interconnect that provide the data
movement between the programmable logic elements (slices). The switchbox has
many switches (typically implemented as pass transistors) that allow for
arbitrary wiring configurations between the different routing tracks in the
routing tracks adjacent to the switchbox.

The switchboxes provides a connection matrix between routing tracks in
adjacent routing channels. Typically, an FPGA has a logical 2D representation.
That is, the FPGA is designed in a manner that provides a 2D abstraction for
computation. This is often called an “island-style” architecture where the
slices represent “logic islands” that are connected using the routing channels
and switchboxes. Here the switchbox connects to four routing channels to the
north, east, south, and west directions. The exact programming of the switches
in the routing channels and switchboxes determines how the inputs and outputs
of the programmable logic blocks are connected. The number of channels, the
connectivity of the switchboxes, the structure of the slice, and other logic
and circuit level FPGA architectural techniques are very well studied; we
refer the interested reader to the following books and surveys on this topic
for more information [12, 10, 30]. Generally, it is not necessary to
understand all of the nitty-gritty details of the FPGA architecture in order
to successfully use the HLS tools, rather it is more important to have a
general understanding of the various FPGA resources and how the HLS
optimizations effect the resource usage.

Figure 1.3:  The two-dimensional structure of an FPGA showing an island style
architecture. The logic and memory resources in the slices are interconnected
using routing channels and switchboxes. The input/output (I/O) blocks provide
an external interface, e.g., to a memory, microprocessor, sensor, and/or
actuator. On some FPGAs, the I/O directly connects to the chip pins. Other
FPGAs use the I/O to connect the programmable logic fabric to on-chip
resources (e.g., a microprocessor bus or cache).

Figure 1.3 provides an even more abstract depiction of an FPGA programmable
logic and interconnect. This provides a larger view of the 2D dimensional
layout of the programmable logic (e.g., slices), routing channels, and
switchboxes. The FPGA programmable logic uses I/O blocks to communicate with
an external device. This may be a microcontroller (e.g., an on-chip ARM
processor using an AXI interface), memory (e.g., an on-chip cache or an off-
chip DRAM memory controller), a sensor (e.g., an antenna through an A/D
interface), or a actuator (e.g., a motor through an D/A interface). More
recently, FPGAs have integrated custom on-chip I/O handlers, e.g., memory
controllers, transceivers, or analog-to-digital (and vice versa) controllers
directly into the fabric in order to increase performance.

As the number of transistors on the FPGA has continued to increase, FPGA
architectures have begun to incorporate more and more “hard” resources. These
are custom resources designed specifically to perform a task. For example,
many applications make heavy use of addition and multiplication operations.
Thus, the FPGA fabric added custom resources targeted at these operations. An
example of this is the DSP48 custom datapaths, which efficiently implement a
series of arithmetic operations including multiplication, addition, multiply-
accumulate, and word level logical operations. These DSP48 blocks have some
programmability, but are not as flexible as the programmable logic. Yet,
implementing a multiply or MAC operation on these DSP48s is much more
efficient than performing the same operation on the programmable logic. Thus,
there is a fundamental tradeoff of efficiency versus flexibility. Modern FPGAs
will have hundreds to thousands of these DSP48 distributed throughout the
logic fabric as shown in Figure 1.4.

Compare the performance of a multiply accumulate operation using the
programmable logic versus the DSP48s. What is the maximum frequency that one
can obtain in both cases? How does the FPGA resource usage change?

Figure 1.4:  Modern FPGAs are becoming more heterogenous with a mix of
programmable logic elements and “hardened” architectural elements like
register files, custom datapaths, and high speed interconnect. The FPGA is
often paired with one or more microprocessors, e.g., ARM or x86 cores, that
coordinates the control of the system.

A block RAM (BRAM) is another example of a hardened resource. BRAMs are
configurable random access memory modules that support different memory
layouts and interfaces. For example, they can be changed to have byte, half-
word, word, and double word transfers and connected to a variety of different
interfaces including local on-chip buses (for talking to the programmable
fabric) and processor buses (to communicate with on-chip processors).
Generally, these are used to transfer data between on-chip resources (e.g.,
the FPGA fabric and microprocessor) and store large data sets on chip. We
could choose to store the data set in the slices (using the FFs) but this
would incur overheads in performance and resource usage.

A typical BRAM has around 32 Kbit of memory storage which can be configured as
32K x 1 bit, 16K x 2 bits, 8K x 4 bits, etc. They can be cascaded together to
create larger memories. All of this configuration is done by the Vivado tools;
this is a major advantage of Vivado® HLS: the designer does not need to worry
about these low level details. The BRAMs are typically co-located next to the
DSP48. For HLS, it may be beneficial to think of the BRAMs as configurable
register files. These BRAMs can directly feed the custom datapaths (DSP48s),
talk to on-chip microprocessors, and transfer data to custom datapaths
implemented on the programmable logic.

Implement a design that stores a large (e.g., thousand item) array in BRAMs
and programmable logic. How does the performance change? What about the
resource usage?

Figure 1.5 provides a comparison between different on-chip and off-chip memory
resources. There are millions of FFs on-chip and these provide hundreds of
Kbytes of bit level storage. These can be read to and written to on every
cycle and thus provide a tremendous amount of total bandwidth. Unfortunately,
they do not provide the most efficient storage capacity. BRAMs provide a bit
more storage density at the cost of limited total bandwidth. Only one or two
entries of the BRAMs can be accessed during every cycle which is the major
limiting factor for the bandwidth. Going even further in this direction, we
can use very high density off-chip external memory, but the bandwidth is even
further reduced. The decision about where to place your application’s data is
crucial and one that we will consider extensively throughout this book. The
Vivado® HLS tool has many options that allow the designer to specify exactly
where and how to store data.

| External |  |
---|---|---|---
| Memory | BRAM | FFs
count | 1-4 | thousands | millions
size | GBytes | KBytes | Bits
total size | GBytes | MBytes | 100s of KBytes
width | 8-64 | 1-16 | 1
total bandwidth | GBytes/sec | TBytes/sec | 100s of TBytes/sec
Figure 1.5: A comparison of three different on- and off-chip memory storage
options. External memory provides the most density but has limited total
bandwidth. Moving on-chip there are two options: FFs and BRAMs. FFs have the
best total bandwidth but only a limited amount of total data storage
capability. BRAMs provide an intermediate value between external memory and
FFs.

As on-chip transistors have become more plentiful, we have the ability to
consider integrating even more complex hardened resources. On-chip
microprocessors are a prime example of this. High-end modern FPGAs can include
four or more on-chip microprocessors (e.g., ARM cores). While only the largest
FPGAs include four microprocessors, it is very common to see one
microprocessor included in even the smaller FPGA devices. This provides the
ability to run an operating system (e.g., Linux) and quickly leverage all of
its facilities, e.g., to communicate with devices through drivers, run larger
software packages like OpenCV, and use more common high level programming
languages like Python to get the system up and running quickly. The
microprocessor is often the controller for the system. It orchestrates data
movement between off-chip memories, sensors, and actuators to on-chip
resources like the BRAMs. And the microprocessor can coordinate between the
custom IP cores developed with the HLS tools, third party IP cores, and the
board level resources.

###  1.3 FPGA Design Process

Given the complexity and size of modern FPGA devices, designers have looked to
impose a higher-level structure on building designs. As a result, FPGA designs
are often composed of components or IP cores, structured something like Figure
1.6. At the periphery of the design, close to the I/O pins, is a relatively
small amount of logic that implements timing-critical I/O functions or
protocols, such as a memory controller block, video interface core or analog-
to-digital converter. This logic, which we will refer to as an I/O interface
core, is typically implemented as structural RTL, often with additional timing
constraints that describe the timing relationships between signals and the
variability of these signals. These constraints must also take into account
interference of signals propagating through traces in a circuit board and
connectors outside of the FPGA. In order to implement high speed interfaces,
these cores typically make use of dedicated logic in the FPGA architecture
that is close to the I/O pins for serializing and deserializing data,
recovering and distributing clock signals, and delaying signals with
picosecond accuracy in order to repeatably capture data in a register. The
implementation of I/O interface cores is often highly customized for a
particular FPGA architecture and hence are typically provided by FPGA vendors
as reference designs or off-the-shelf components, so for the purposes of this
book, we can ignore the detailed implementation of these blocks.

Figure 1.6: A block diagram showing a hypothetical embedded FPGA design,
consisting of I/O interface cores (shown in blue), standard cores (shown in
green), and application specific accelerator cores (shown in purple). Note
that accelerator cores might have streaming interfaces (Accelerator 2),
memory-mapped interfaces (Accelerator 3), or both (Accelerator 1).

Away from I/O pins, FPGA designs often contain standard cores, such as
processor cores, on-chip memories, and interconnect switches. Other standard
cores include generic, fixed-function processing components, such as filters,
FFTs, and codecs. Although instances of these cores are often parameterized
and assembled in a wide variety of ways in a different designs, they are not
typically the differentiating element in a customers design. Instead, they
represent commodity, horizontal technology that can be leveraged in designs in
many different application areas. As a result, they are often provided by an
FPGA vendor or component provider and only rarely implemented by a system
designer. Unlike interface I/O cores, standard cores are primarily synchronous
circuits that require few constraints other than basic timing constraints
specifying the clock period. As a result, such cores are typically portable
between FPGA families, although their circuit structure may still be highly
optimized.

Lastly, FPGA designs typically contain customized, application-specific
accelerator cores. As with standard cores, accelerator cores are primarily
synchronous circuits that can be characterized by a clock period timing
constraint. In contrast, however, they are almost inevitably constructed for a
specific application by a system designer. These are often the “secret sauce”
and used to differentiate your system from others. Ideally a designer can
quickly and easily generate high-performance custom cores, perform a design
space exploration about feasible designs, and integrate these into their
systems in a short timeframe. This book will focus on the development of
custom cores using HLS in a fast, efficient and high performance manner.

When integrating a design as in Figure 1.6, there are two common design
methodologies. One methodology is to treat HLS-generated accelerator cores
just like any other cores. After creating the appropriate accelerator cores
using HLS, the cores are composed together (for instance, in a tool such as
Vivado®IP Integrator) along with I/O interface cores and standard cores to
form a complete design. This core-based design methodology is similar to the
way that FPGA designs are developed without the use of HLS. A newer
methodology focuses on standard design templates or platforms, which combine a
stable, verified composition of standard cores and I/O interface cores
targeting a particular board. This platform-based design methodology enables a
high-level programmer to quickly integrate different algorithms or roles
within the interfaces provided by a single platform or shell. It can also make
it easier to port an accelerator from one platform to another as long as the
shells support the same standardized interfaces.

###  1.4 Design Optimization

####  1.4.1 Performance Characterization

Before we can talk about optimizing a design, we need to discuss the key
criterion that are used to characterize a design. The computation time is a
particularly important metric for design quality. When describing synchronous
circuits, one often will use the number of clock cycles as a measure of
performance. However, this is not appropriate when comparing designs that have
different clock rates, which is typically the case in HLS. For example, the
clock frequency is specified as an input constraint to the Vivado® HLS, and it
is feasible to generate different architectures for the same exact code by
simply changing the target clock frequency. Thus, it is most appropriate to
use seconds, which allows an apples-to-apples comparison between any HLS
architecture. The Vivado® HLS tool reports the number of cycles and the clock
frequency. These can be used to calculate the exact amount of time that some
piece of code requires to compute.

It is possible to optimize the design by changing the clock frequency. The
Vivado® HLS tool takes as input a target clock frequency, and changing this
frequency target will likely result in the tool generating different
implementations. We discuss this throughout the book. For example, Chapter 2.4
describes the constraints the are imposed on the Vivado® HLS tool depending on
the clock period. Chapter 2.5 discusses how increasing the clock period can
increase the throughput by employing operation chaining.

We use the term task to mean a fundamental atomic unit of behavior; this
corresponds to a function invocation in Vivado® HLS. The task latency is the
time between when a task starts and when it finishes. The task interval is the
time between when one task starts and the next starts or the difference
between the start times of two consecutive tasks. All task input, output, and
computation is bounded by the task latency, but the start of a task may not
coincide with the reading of inputs and the end of a task may not coincide
with writing of outputs, particularly if the task has state that is passed
from one task to the next. In many designs, data rate is a key design goal,
and depends on both the task interval and the size of the arguments to the
function.

Figure 1.7: The task interval and task latency for two different designs. The
left design is pipelined while the right one uses a more sequential
implementation.

Figure 1.7 shows two different designs of some hypothetical application. The
horizontal axis represents time (increasing to the right) and the vertical
axis represents different functional units in the design. Input operations are
shaded red and and output operations are shaded orange. Active operators are
represented in dark blue and inactive operators are represented in light blue.
Each incoming arrow represents the start of a task and each outgoing arrow
represents the completion of a task. The diagram on the left represents four
executions of an architecture that starts a new task every cycle. This
corresponds to a ‘fully-pipelined’ implementation. On the right, there is task
with a very different architecture, reading a block of four pieces of input
data, processing it, and then producing a block of four output samples after
some time. This architecture has the same latency and interval (13 cycles) and
can only process one task at a time. This behavior is in contrast to the
behavior of the pipelined design on the left, which has multiple tasks
executing at any given instant of time. Pipelining in HLS is very similar to
the concept of instruction pipelines in a microprocessor. However, instead of
using a simple 5-stage pipeline where the results of an operation are usually
written back to the register file before being executed on again, the Vivado®
HLS tool constructs a circuit that is customized to run a particular program
on a particular FPGA device. The tool optimizes the number of pipeline stages,
the initiation interval (the time between successive data provided to the
pipeline – similar to the task interval), the number and types of functional
units and their interconnection based on a particular program and the device
that is being targeted.

The Vivado® HLS tool counts cycles by determining the maximum number of
registers between any input and output of a task. Thus, it is possible for a
design to have a task latency of zero cycles, corresponding to a combinational
circuit which has no registers in any path from input to output. Another
convention is to count the input and/or output as a register and then find the
maximum registers on any path. This would result in a larger number of cycles.
We use the Vivado® HLS convention throughout this book.

Note that many tools report the task interval as “throughput”. This
terminology is somewhat counterintuitive since a longer task interval almost
inevitably results in fewer tasks being completed in a given time and thus
lower data rates at the interfaces. Similarly, many tools use “latency” to
describe a relationship between reading inputs and writing outputs.
Unfortunately, in designs with complex behavior and multiple interfaces, it is
hard to characterize tasks solely in terms of inputs and outputs, e.g., a task
may require multiple reads or writes from a memory interface.

####  1.4.2 Area/Throughput Tradeoffs

In order to better discuss some of the challenges that one faces when using an
HLS tool, let’s consider a simple yet common hardware function – the finite
impulse response (FIR) filter. An FIR performs a convolution on an input
sequence with a fixed set of coefficients. An FIR is quite general – it can be
used to perform different types of filter (high pass filter, low pass, band
pass, etc.). Perhaps the most simple example of an FIR is a moving average
filter. We will talk more background on FIR in Chapter 2 and describe many
specific optimizations that can be done using HLS. But in the meantime just
consider its implementation at a high level.

The C code in Figure 1.8 provides a functional or task description for HLS;
this can be directly used as input to the Vivado® HLS tool, which will analyze
it and produce a functionally equivalent RTL circuit. This is a complex
process, and we will not get into much detail about this now, but think of it
as a compiler like gcc. Yet instead of outputting assembly code, the HLS
“compiler” creates an RTL hardware description. In both cases, it is not
necessary to understand exactly how the compiler works. This is exactly why we
have the compiler in the first place – to automate the design process and
allow the programmer/designer to work at a higher level of abstraction. Yet at
the same time, someone that knows more about how the compiler works will often
be able to write more efficient code. This is particularly important for
writing HLS code since there are many options for synthesizing the design that
are not typically obvious to one that only knows the “software” flow. For
example, ideas like custom memory layout, pipelining, and different I/O
interfaces are important for HLS, but not for a “software compiler”. These are
the concepts that we focus on in this book.

A key question to understand is: “What circuit is generated from this code?”.
Depending on your assumptions and the capabilities of a particular HLS tool,
the answer can vary widely. There are multiple ways that this could be
synthesized by an HLS tool.

⬇

#define NUM_TAPS 4

void fir(int input, int *output, int taps[NUM_TAPS])

{

static int delay_line[NUM_TAPS] = {};

int result = 0;

for (int i = NUM_TAPS - 1; i > 0; i–) {

delay_line[i] = delay_line[i - 1];

}

delay_line[0] = input;

for (int i = 0; i < NUM_TAPS; i++) {

result += delay_line[i] * taps[i];

}

*output = result;

}

Figure 1.8: Code for a four tap FIR filter.

⬇ fir: .frame r1,0,r15 # vars= 0, regs= 0, args= 0 .mask 0x00000000 addik
r3,r0,delay_line.1450 lwi r4,r3,8 # Unrolled loop to shift the delay line swi
r4,r3,12 lwi r4,r3,4 swi r4,r3,8 lwi r4,r3,0 swi r4,r3,4 swi r5,r3,0 # Store
the new input sample into the delay line addik r5,r0,4 # Initialize the loop
counter addk r8,r0,r0 # Initialize accumulator to zero addk r4,r8,r0 #
Initialize index expression to zero $L2: muli r3,r4,4 # Compute a byte offset
into the delay_line array addik r9,r3,delay_line.1450 lw r3,r3,r7 # Load
filter tap lwi r9,r9,0 # Load value from delay line mul r3,r3,r9 # Filter
Multiply addk r8,r8,r3 # Filter Accumulate addik r5,r5,-1 # update the loop
counter bneid r5,$L2 addik r4,r4,1 # branch delay slot, update index
expression rtsd r15, 8 swi r8,r6,0 # branch delay slot, store the output .end
fir

Figure 1.9: RISC-style assembly generated from the C code in Figure 1.8,
targetting the Xilinx Microblaze processor. This code is generated using
microblazeel-xilinx-linux-gnu-gcc -O1 -mno-xl-soft-mul -S fir.c

One possible circuit would execute the code sequentially, as would a simple
RISC microprocessor. Figure 1.9 shows assembly code for the Xilinx Microblaze
processor which implements the C code in Figure 1.8. Although this code has
been optimized, many instructions must still be executed to compute array
index expressions and loop control operations. If we assume that a new
instruction can be issued each clock cycle, then this code will take
approximately 49 clock cycles to compute one output sample of the filter.
Without going into the details of how the code works, we can see that one
important barrier to performance in this code is how many instructions can be
executed in each clock cycle. Many improvements in computer architecture are
fundamentally attempts to execute more complex instructions that do more
useful work more often. One characteristic of HLS is that architectural
tradeoffs can be made without needing to fit in the constraints of an
instruction set architecture. It is common in HLS designs to generate
architectures that issue hundreds or thousands of RISC-equivalent instructions
per clock with pipelines that are hundreds of cycles deep.

By default, the Vivado® HLS tool will generate an optimized, but largely
sequential architecture. In a sequential architecture, loops and branches are
transformed into control logic that enables the registers, functional units,
and the rest of the data path. Conceptually, this is similar to the execution
of a RISC processor, except that the program to be executed is converted into
a finite state machine in the generated RTL rather than being fetched from the
program memory. A sequential architecture tends to limit the number of
functional units in a design with a focus on resource sharing over massive
parallelism. Since such an implementation can be generated from most programs
with minimal optimization or transformation, this makes it easy for users to
get started with HLS. One disadvantage of a sequential architecture is that
analyzing and understanding data rates is often difficult since the control
logic can be complex. The control logic dictates the number of cycles for the
task interval and task latencies. The control logic can be quite complex,
making it difficult to analyze. In addition, the behavior of the control logic
may also depend on the data being processed, resulting in performance that is
data-dependent.

Figure 1.10: A “one tap per clock” architecture for an FIR filter. This
architecture can be implemented from the code in Figure 1.8.

Figure 1.11: A “one sample per clock” architecture for an FIR filter. This
architecture can be implemented from the code in Figure 1.8 using function
pipeline.

However, the Vivado® HLS tool can also generate higher performance pipelined
and parallel architectures. One important class of architectures is called a
function pipeline. A function pipeline architecture is derived by considering
the code within the function to be entirely part of a computational data path,
with little control logic. Loops and branches in the code are converted into
unconditional constructs. As a result, such architectures are relatively
simple to characterize, analyze, and understand and are often used for simple,
high data rate designs where data is processed continuously. Function pipeline
architectures are beneficial as components in a larger design since their
simple behavior allows them to be resource shared like primitive functional
units. One disadvantage of a function pipeline architecture is that not all
code can be effectively parallelized.

The Vivado® HLS tool can be directed to generate a function pipeline by
placing the #pragma HLS pipeline directive in the body of a function. This
directive takes a parameter that can be used to specify the initiation
interval of the the pipeline, which is the same as a task interval for a
function pipeline. Figure 1.10 shows one potential design – a “one tap per
clock” architecture, consisting of a single multiplier and single adder to
compute the filter. This implementation has a task interval of 4 and a task
latency of 4. This architecture can take a new sample to filter once every 4
cycles and will generate a new output 4 cycles after the input is consumed.
The implementation in Figure 1.11 shows a “one sample per clock” architecture,
consisting of 4 multipliers and 3 adders. This implementation has a task
interval of 1 and a task latency of 1, which in this case means that the
implementation accept a new input value every cycle. Other implementations are
also possible, such as architectures with “two taps per clock” or “two samples
per clock”, which might be more appropriate for a particular application. We
discuss more ways to optimize the FIR function in depth in Chapter 2.

In practice, complex designs often include complicated tradeoffs between
sequential architectures and parallel architectures, in order to achieve the
best overall design. In Vivado® HLS, these tradeoffs are largely controlled by
the user, through various tool options and code annotations, such as #pragma
directive.

What would the task interval of a “two taps per clock” architecture for a 4
tap filter be? What about for a “two samples per clock” architecture?

####  1.4.3 Restrictions on Processing Rate

As we have seen, the task interval of a design can be changed by selecting
different kinds of architectures, often resulting in a corresponding increase
in the processing rate. However, it is important to realize that the task
interval of any processing architecture is fundamentally limited in several
ways. The most important limit arises from recurrences or feedback loops in a
design. The other key limitation arises from resource limits.

A recurrence is any case where a computation by a component depends on a
previous computation by the same component. A key concept is that recurrences
fundamentally limit the throughput of a design, even in the presence of
pipelining [56, 43]. As a result, analyzing recurrences in algorithms and
generating hardware that is guaranteed to be correct is a key function of an
HLS tool. Similarly, understanding algorithms and selecting those without
tight recurrences is a important part of using HLS (and, in fact, parallel
programming in general).

Recurrences can arrive in different coding constructs, such as static
variables (Figure 1.8), sequential loops (Figure 1.10). Recurrences can also
appear in a sequential architecture and disappear when pipelining is applied
(as in Figures 1.10 and 1.11). In other cases, recurrences can exist without
limiting the throughput of a sequential architecture, but can become
problematic when the design is pipelined.

Another key factor that can limit processing rate are resource limitations.
One form of resource limitation is associated with the wires at the boundary
of a design, since a synchronous circuit can only capture or transmit one bit
per wire per clock cycle. As a result, if a function with the signature
int32_t f(int32_t x); is implemented as a single block at 100 MHz with a task
interval of 1, then the most data that it can process is 3.2 Gbits/sec.
Another form of resource limitation arises from memories since most memories
only support a limited number of accesses per clock cycle. Yet another form of
resource limitation comes from user constraints. If a designer limits the
number of operators that can instantiated during synthesis, then this places a
limit on the processing rate of the resulting design.

####  1.4.4 Coding Style

Another key question you should ask yourself is, “Is this code the best way to
capture the algorithm?”. In many cases, the goal is not only the highest
quality of results, but maintainable and modifiable code. Although this is
somewhat a stylistic preference, coding style can sometimes limit the
architectures that a HLS tool can generate from a particular piece of code.

For instance, while a tool might be able to generate either architecture in
Figure 1.11 or 1.10 from the code in Figure 1.8, additing additional
directives as shown in Figure 1.12 would result in a specific architecture. In
this case the delay line is explicitly unrolled, and the multiply-accumulate
for loop is stated to be implemented in a pipelined manner. This would direct
the HLS tool to produce an architecture that looks more like the pipelined one
in Figure 1.11.

⬇

#define NUM_TAPS 4

void block_fir(int input[256], int output[256], int taps[NUM_TAPS],

int delay_line[NUM_TAPS]) {

int i, j;

for (j = 0; j < 256; j++) {

int result = 0;

for (i = NUM_TAPS - 1; i > 0; i–) {

#pragma HLS unroll

delay_line[i] = delay_line[i - 1];

}

delay_line[0] = input;

for (i = 0; i < NUM_TAPS; i++) {

#pragma HLS pipeline

result += delay_line[i] * taps[i];

}

output[j] = result;

}

}

Figure 1.12: Alternative code implementing an FIR filter.

The chapter described how to build filters with a range of different
processing rates, up to one sample per clock cycle. However, many designs may
require processing data at a higher rate, perhaps several samples per clock
cycle. How would you code such a design? Implement a 4 samples per clock cycle
FIR filter. How many resources does this architecture require (e.g., number of
multipliers and adders)? Which do you think will use more FPGA resources: the
4 samples per clock or the 1 sample per clock cycle design?

We look further into the optimization of an FIR function in more detail in
Chapter 2. We discuss how to employ different optimizations (pipelining,
unrolling, bitwidth optimization, etc.), and describe their effects on the
performance and resource utilization of the resulting generated architectures.

###  1.5 Restructured Code

Writing highly optimized synthesizable HLS code is often not a straightforward
process. It involves a deep understanding of the application at hand, the
ability to change the code such that the Vivado® HLS tool creates optimized
hardware structures and utilizes the directives in an effective manner.

Throughout the rest of the book, we walk through the synthesis of a number of
different application domains – including digital signal processing, sorting,
compression, matrix operations, and video processing. In order to get the most
efficient architecture, it is important to have a deep understanding of the
algorithm. This enables optimizations that require rewriting the code rather
than just adding synthesis directives – a processing that we call code
restructuring.

Restructured code maps well into hardware, and often represents the
eccentricities of the tool chain, which requires deep understanding of micro-
architectural constructs in addition to the algorithmic functionality.
Standard, off-the-shelf code typically yields very poor quality of results
that are orders of magnitude slower than CPU designs, even when using HLS
directives such as pipelining, unrolling, and data partitioning. Thus, it is
important to understand how to write code that the Vivado® HLS will synthesize
in an optimal manner.

Restructured code typically differs substantially from a software
implementation – even one that is highly optimized. A number of studies
suggest that restructuring code is an essential step to generate an efficient
FPGA design [46, 47, 15, 14, 39]. Thus, in order to get an efficient hardware
design, the user must write restructured code with the underlying hardware
architecture in mind. Writing restructured code requires significant hardware
design expertise and domain specific knowledge.

Throughout the rest of this book, we go through a number of different
applications, and show how to restructure the code for a more efficient
hardware design. We present applications such as finite impulse response
(FIR), discrete Fourier transform (DFT), fast Fourier transform (FFT), sparse
matrix vector multiply (SpMV), matrix multiplication, sorting, and Huffman
encoding. We discuss the impact of restructured code on the final hardware
generated from high-level synthesis. And we propose a restructuring techniques
based on best practices. In each chapter, we aim to:

  1. 1.

Highlight the importance of restructuring code to obtain FPGA designs with
good quality of result, i.e., a design that has high performance and low area
usage;

  2. 2.

Provide restructured code for common applications;

  3. 3.

Discuss the impact of the restructuring on the underlying hardware; and

  4. 4.

Perform the necessary HLS directives to achieve the best design

Throughout the book, we use example applications to show how to move from a
baseline implementation and restructure the code to provide more efficient
hardware design. We believe that the optimization process is best understood
through example. Each chapter performs a different set of optimization
directives including pipelining, dataflow, array partitioning, loop
optimizations, and bitwidth optimization. Additionally, we provide insight on
the skills and knowledge necessary to perform the code restructuring process.

###  1.6 Book Organization

We organized this book to teach by example. Each chapter presents an
application (or application domain) and walks through its implementation using
different HLS optimizations. Generally, each chapter focuses on a limited
subset of optimization techniques. And the application complexity generally
increases in the later chapters. We start with a relatively simple to
understand finite impulse response (FIR) filter in Chapter 2 and move on to
implement complete video processing systems in Chapter 9.

There are of course benefits and drawbacks to this approach. The benefits are:
1) the reader can see how the optimizations are directly applicable to an
application, 2) each application provides an exemplar of how to write HLS
code, and 3) while simple to explain, toy examples can be hard to generalize
and thus do not always make the best examples.

The drawbacks to the teach by example approach are: 1) most applications
requires some background to give the reader a better understanding of the
computation being performed. Truly understanding the computation often
necessitates an extensive discussion on the mathematical background on the
application. For example, implementing the best architecture for the fast
Fourier transform (FFT) requires that the designer have deep understanding of
the mathematical concepts behind a discrete Fourier transform (DFT) and FFT.
Thus, some chapters, e.g., Chapter 4 (DFT) and Chapter 5 (FFT), start with a
non-trivial amount of mathematical discussion. This may be off-putting to a
reader simply looking to understand the basics of HLS, but we believe that
such a deep understanding is necessary to understand the code restructuring
that is necessary to achieve the best design. 2) some times a concept could be
better explained by a toy example that abstracts away some of the non-
important application details.

The organization for each chapter follows the same general pattern. A chapter
begins by providing a background on the application(s) under consideration. In
many cases, this is straightforward, e.g., it is not too difficult to explain
matrix multiplication (as in Chapter 7) while the DFT requires a substantial
amount of discussion (Chapter 4). Then, we provide a _baseline implementation_
– a functionally correct but unoptimized implementation of the application
using Vivado® HLS. After that, we perform a number of different optimizations.
Some of the chapters focus on a small number of optimizations (e.g., Chapter 3
emphasizes bitwidth optimizations) while others look at a broad range of
optimizations (e.g., Chapter 2 on FIR filters). The key optimizations and
design methods are typically introduced in-depth in one chapter and then used
repeatedly in the subsequent chapters.

The book is made to be read sequentially. For example, Chapter 2 introduces
most of the optimizations and the later chapters provide more depth on using
these optimizations. The applications generally get more complex throughout
the book. However, each chapter is relatively self-contained. Thus, a more
advanced HLS user can read an individual chapter if she only cares to
understand a particular application domain. For example, a reader interested
in generating a hardware accelerated sorting engine can look at Chapter 10
without necessarily have to read all of the previous chapters. This is another
benefit of our teach by example approach.

Table 1.1: A map describing the types of HLS optimizations and the chapters that discuss the concepts beyond them. Chapter |  FIR |  CORDIC |  DFT |  FFT |  SPMV |  MatMul |  Histogram |  Video |  Sorting |  Huffman
---|---|---|---|---|---|---|---|---|---|---
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
Loop Unrolling | X |  | X | X | X |  | X |  | X |
Loop Pipelining | X |  | X | X | X |  | X | X | X | X
Bitwidth Optimization | X | X |  |  |  |  |  |  |  | X
Function Inlining | X |  |  |  |  |  |  |  |  | X
Hierarchy | X |  |  | X |  |  | X | X | X | X
Array Optimizations |  |  | X | X | X | X | X | X | X | X
Task Pipelining |  |  |  | X |  |  | X | X | X | X
Testbench |  |  |  |  | X | X |  |  | X | X
Co-simulation |  |  |  |  | X |  |  |  |  |
Streaming |  |  |  |  |  | X |  | X | X |
Interfacing |  |  |  |  |  |  |  | X |  |

Table 1.1 provides an overview of the types of optimization and the chapters
where they are covered in at least some level of detail. Chapter 2 provides a
gentle introduction the HLS design process. It overviews several different
optimizations, and shows how they can be used in the optimization of a FIR
filter. The later chapters go into much more detail on the benefits and usage
of these optimizations.

The next set of chapters (Chapters 3 through 5) build digital signal
processing blocks (CORDIC, DFT, and FFT). Each of these chapters generally
focuses on one optimization: bitwidth optimization (Chapter 3), array
optimizations (Chapter 4, and task pipelining (Chapter 5). For example,
Chapter 3 gives an in-depth discussion on how to perform bitwidth
optimizations on the CORDIC application. Chapter 4 provides an introduction to
array optimizations, in particular, how to perform array partitioning in order
to increase the on-chip memory bandwidth. This chapter also talks about loop
unrolling and pipelining, and the need to perform these three optimizations in
concert. Chapter 5 describes the optimizations of the FFT, which itself is a
major code restructuring of the DFT. Thus, the chapter gives a background on
how the FFT works. The FFT is a staged algorithm, and thus highly amenable to
task pipelining. The final optimized FFT code requires a number of other
optimizations including loop pipelining, unrolling, and array optimizations.
Each of these chapters is paired with a project from the Appendix. These
projects lead the design and optimization of the blocks, and the integration
of these blocks into wireless communications systems.

Chapters 6 through 11 provide a discussion on the optimization of more
applications. Chapter 6 describes how to use a testbench and how to perform
RTL co-simulation. It also describes array and loop optimizations; these
optimizations are common and thus are used in the optimization of many
applications. Chapter 7 introduces the streaming optimization for data flow
between tasks. Chapter 8 presents two applications (prefix sum and histogram)
that are relatively simple, but requires careful code restructuring in order
to create the optimal architecture. Chapter 9 talks extensively about how to
perform different types interfacing, e.g., with a video stream using different
bus and memory interfaces. As the name implies, the video streaming requires
the use of the stream primitive, and extensive usage of loop and array
optimizations. Chapter 10 goes through a couple of sorting algorithms. These
require a large number of different optimizations. The final chapter creates a
complex data compression architecture. It has a large number of complex blocks
that work on a more complex data structure (trees).

##  Chapter 2 Finite Impulse Response (FIR) Filters

###  2.1 Overview

Finite Impulse Response (FIR) filters are commonplace in digital signal
processing (DSP) applications – they are perhaps the most widely used
operation in this domain. They are well suited for hardware implementation
since they can be implemented as a highly optimized architecture. A key
property is that they are a linear transform on contiguous elements of a
signal. This maps well to a data structures (e.g., FIFOs or tap delay lines)
that can be implemented efficiently in hardware. In general, streaming
applications tend to map well to FPGAs, e.g., most of the examples that we
present throughout the book have some sort of streaming behavior.

Two fundamental uses for a filter are signal restoration and signal
separation. Signal separation is perhaps the more common use case: here one
tries to isolate the input signal into different parts. Typically, we think of
these as different frequency ranges, e.g., we may want perform a low pass
filter in order remove high frequencies that are not of interest. Or we may
wish to perform a band pass filter to determine the presence of a particular
frequency in order to demodulate it, e.g., for isolating tones during
frequency shift keying demodulation. Signal restoration relates to removing
noise and other common distortion artifacts that may have been introduced into
the signal, e.g., as data is being transmitted across the wireless channel.
This includes smoothing the signal and removing the DC component.

Digital FIR filters often deal with a discrete signal generated by sampling a
continuous signal. The most familiar sampling is performed in time, i.e., the
values from a signal are taken at discrete instances. These are most often
sampled at regular intervals. For instance, we might sample the voltage across
an antenna at a regular interval with an analog-to-digital converter.
Alternatively we might sample the current created by a photo-diode to
determine the light intensity. Alternatively, samples may be taken in space.
For instance, we might sample the value of different locations in an image
sensor consisting of an array of photo-diodes to create a digital image. More
in-depth descriptions of signals and sampling can be found in [41].

The format of the data in a sample changes depending upon the application.
Digital communications often uses complex numbers (in-phase and quadrature or
I/Q values) to represent a sample. Later in this chapter we will describe how
to design a complex FIR filter to handle such data. In image processing we
often think of a pixel as a sample. A pixel can have multiple fields, e.g.,
red, green, and blue (RGB) color channels. We may wish to filter each of these
channels in a different way again depending upon the application.

The goal of this chapter is to provide a basic understanding of the process of
taking an algorithm and creating a good hardware design using high-level
synthesis. The first step in this process is always to have a deep
understanding of the algorithm itself. This allows us to make design
optimizations like code restructuring much more easily. The next section
provides an understanding of the FIR filter theory and computation. The
remainder of the chapter introduces various HLS optimizations on the FIR
filter. These are meant to provide an overview of these optimizations. Each of
them will described in more depth in subsequent chapters.

###  2.2 Background

The output signal of a filter given an impulse input signal is its impulse
response. The impulse response of a linear, time invariant filter contains the
complete information about the filter. As the name implies, the impulse
response of an FIR filter (a restricted type of linear, time invariant filter)
is finite, i.e., it is always zero far away from zero. Given the impulse
response of an FIR filter, we can compute the output signal for any input
signal through the process of convolution. This process combines samples of
the impulse response (also called coefficients or taps) with samples of the
input signal to compute samples of the output signal. The output of filter can
be computed in other ways (for instance, in the frequency domain), but for the
purposes of this chapter we will focus on computing in the time domain.

The convolution of an N-tap FIR filter with coefficients $h[]$ with an input
signal $x[]$ is described by the general difference equation:

$y[i]=\displaystyle\sum\limits_{j=0}^{N-1}h[j]\cdot x[i-j]$ (2.1)

Note that to compute a single value of the output of an N-tap filter requires
N multiplies and N-1 additions.

Moving average filters are a simple form of lowpass FIR filter where all the
coefficients are identical and sum to one. For instance in the case of the
three point moving filter, the coefficients are
$h=[\frac{1}{3},\frac{1}{3},\frac{1}{3}]$. It is also called a box car filter
due to the shape of its convolution kernel. Alternatively, you can think of a
moving average filter as taking the average of several adjacent samples of the
input signal and averaging them together. We can see that this equivalence by
substituting $1/N$ for $h[j]$ in the convolution equation above and
rearranging to arrive at the familiar equation for an average of $N$ elements:

$y[i]=\frac{1}{N}\displaystyle\sum\limits_{j=0}^{N}x[i-j]$ (2.2)

Each sample in the output signal can be computer by the above equation using
$N-1$ additions and one final multiplication by $1/N$. Even the final
multiplication can often be regrouped and merged with other operations. As a
result, moving average filters are simpler to compute than a general FIR
filter. Specifically, when $N=3$ we perform this operation to calculate
$y[12]$:

$y[12]=\frac{1}{3}\cdot(x[12]+x[11]+x[10])$ (2.3)

This filter is causal, meaning that the output is a function of no future
values of the input. It is possible and common to change this, for example, so
that the average is centered on the current sample, i.e.,
$y[12]=\frac{1}{3}\cdot(x[11]+x[12]+x[13])$. While fundamentally causality is
an important property for system analysis, it is less important for a hardware
implementation as a finite non-causal filter can be made causal with buffering
and/or reindexing of the data.

Moving average filters can be used to smooth out a signal, for example to
remove random (mostly high frequency) noise. As the number of taps $N$ gets
larger, we average over a larger number of samples, and we correspondingly
must perform more computations. For a moving average filter, larger values of
$N$ correspond to reducing the bandwidth of the output signal. In essence, it
is acting like a low pass filter (though not a very optimal one). Intuitively,
this should make sense. As we average over larger and larger number of
samples, we are eliminating higher frequency variations in the input signal.
That is, “smoothing” is equivalent to reducing higher frequencies. The moving
average filter is optimal for reducing white noise while keeping the sharpest
step response, i.e., it creates the lowest noise for a given edge sharpness.

Note that in general, filter coefficients can be crafted to create many
different kinds of filters: low pass, high pass, band pass, etc.. In general,
a larger value of number of taps provides more degrees of freedom when
designing a filter, generally resulting in filters with better
characteristics. There is substantial amount of literature devoted to
generating filter coefficients with particular characteristics for a given
application. When implementing a filter, the actual values of these
coefficients are largely irrelevant and we can ignore how the coefficients
themselves were arrived at. However, as we saw with the moving average filter,
the structure of the filter, or the particular coefficients can have a large
impact on the number of operations that need to be performed. For instance,
symmetric filters have multiple taps with exactly the same value which can be
grouped to reduce the number of multiplications. In other cases, it is
possible to convert the multiplication by a known constant filter coefficient
into shift and add operations [34]. In that case, the values of the
coefficients can drastically change the performance and area of the filter
implementation [52]. But we will ignore that for the time being, and focus on
generating architectures that have constant coefficients, but do not take
advantage of the values of the constants.

###  2.3 Base FIR Architecture

Consider the code for an 11 tap FIR filter in Figure 2.1. The function takes
two arguments, an input sample x, and the output sample y. This function must
be called multiple times to compute an entire output signal, since each time
that we execute the function we provide one input sample and receive one
output sample. This code is convenient for modeling a streaming architecture,
since we can call it as many times as needed as more data becomes available.

⬇

#define N 11

#include ”ap_int.h”

typedef int coef_t;

typedef int data_t;

typedef int acc_t;

void fir(data_t *y, data_t x) {

coef_t c[N] = {53, 0, -91, 0, 313, 500, 313, 0, -91, 0, 53};

static data_t shift_reg[N];

acc_t acc;

int i;

acc = 0;

Shift_Accum_Loop:

for (i = N - 1; i >= 0; i–) {

if (i == 0) {

acc += x * c[0];

shift_reg[0] = x;

} else {

shift_reg[i] = shift_reg[i - 1];

acc += shift_reg[i] * c[i];

}

}

*y = acc;

}

Figure 2.1: A functionally correct, but highly unoptimized, implementation of
an 11 tap FIR filter.

The coefficients for the filter are stored in the c[] array declared inside of
the function. These are statically defined constants. Note that the
coefficients are symmetric. i.e., they are mirrored around the center value
c[5] = 500. Many FIR filter have this type of symmetry. We could take
advantage of it in order to reduce the amount of storage that is required for
the c[] array.

The code uses typedef for the different variables. While this is not
necessary, it is convenient for changing the types of data. As we discuss
later, bit width optimization – specifically setting the number of integer and
fraction bits for each variable – can provide significant benefits in terms of
performance and area.

Rewrite the code so that it takes advantage of the symmetry found in the
coefficients. That is, change c[] so that it has six elements (c[0] through
c[5]). What changes are necessary in the rest of the code? How does this
effect the number of resources? How does it change the performance?

The code is written as a streaming function. It receives one sample at a time,
and therefore it must store the previous samples. Since this is an 11 tap
filter, we must keep the previous 10 samples. This is the purpose of the
shift_reg[] array. This array is declared static since the data must be
persistent across multiple calls to the function.

The for loop is doing two fundamental tasks in each iteration. First, it
performs the multiply and accumulate operation on the input samples (the
current input sample x and the previous input samples stored in shift_reg[]).
Each iteration of the loop performs a multiplication of one of the constants
with one of the sample, and stores the running sum in the variable acc. The
loop is also shifting values through shift_array, which works as a FIFO. It
stores the input sample x into shift_array[0], and moves the previous elements
“up” through the shift_array:

shift_array[10] = shift_array[9]
shift_array[9] = shift_array[8]
shift_array[8] = shift_array[7]
$\cdots$
shift_array[2] = shift_array[1]
shift_array[1] = shift_array[0]
shift_array[0] = x

The label Shift_Accum_Loop: is not necessary. However it can be useful for
debugging. The Vivado® HLS tool adds these labels into the views of the code.

After the for loop completes, the acc variable has the complete result of the
convolution of the input samples with the FIR coefficient array. The final
result is written into the function argument y which acts as the output port
from this fir function. This completes the streaming process for computing one
output value of an FIR.

This function does not provide an efficient implementation of a FIR filter. It
is largely sequential, and employs a significant amount of unnecessary control
logic. The following sections describe a number of different optimizations
that improve its performance.

###  2.4 Calculating Performance

Before we get into the optimizations, it is necessary to define precise
metrics. When deriving the performance of a design, it is important to
carefully state the metric. For instance, there are many different ways of
specifying how “fast” your design runs. For example, you could say that it
operates at $X$ bits/second. Or that it can perform $Y$ operations/sec. Other
common performance metrics specifically for FIR filters talk about the number
of filter operations/second. Yet another metric is multiply accumulate
operations: MACs/second. Each of these are related to one another, in some
manner, but when comparing different implementations it is important to
compare apples to apples. For example, directly comparing one design using
bits/second to another using filter operations/second can be misleading; fully
understanding the relative benefits of the designs requires that we compare
them using the same metric. And this may require additional information, e.g.,
going from filter operations/second to bits/second requires information about
the size of the input and output data.

All of the aforementioned metrics use seconds. High-level synthesis tools talk
about the designs in terms of number of cycles, and the frequency of the
clock. The frequency is inversely proportional to the time it takes to
complete one clock cycle. Using them both gives us the amount of time in
seconds to perform some operation. The number of cycles and the clock
frequency are both important: a design that takes one cycle, but with a very
low frequency is not necessary better than another design that takes 10 clock
cycles but operates at a much higher frequency.

The clock frequency is a complicated function that the Vivado® HLS tool
attempts to optimize alongside the number of cycles. Note that it is possible
to specify a target frequency to the Vivado® HLS tool. This is done using the
create_clock tcl command. For example, the command create_clock -period 5
directs the tool to target a clock period of 5 ns and equivalently a clock
frequency of 200 MHz. Note that this is only a target clock frequency only and
primarily affects how much operation chaining is performed by the tool. After
generating RTL, the Vivado® HLS tool provides an initial timing estimate
relative to this clock target. However, some uncertainty in the performance of
the circuit remains which is only resolved once the design is fully place and
routed.

While achieving higher frequencies are often critical for reaching higher
performance, increasing the target clock frequency is not necessarily optimal
in terms of an overall system. Lower frequencies give more leeway for the tool
to combine multiple dependent operations in a single cycle, a process called
operation chaining. This can sometimes allow higher performance by enabling
improved logic synthesis optimizations and increasing the amount of code that
can fit in a device. Improved operation chaining can also improve (i.e.,
lower) the initiation interval of pipelines with recurrences. In general
providing a constrained, but not over constrained target clock latency is a
good option. Something in the range of $5-10$ ns is typically a good starting
option. Once you optimize your design, you can vary the clock period and
observe the results. We will describe operation chaining in more detail in the
next section.

Because Vivado® HLS deals with clock frequency estimates, it does include some
margin to account for the fact that there is some error in the estimate. The
goal of this margin is to ensure enough timing slack in the design that the
generated RTL can be successfully placed and routed. This margin can be
directly controlled using the set_clock_uncertainty TCL command. Note that
this command only affects the HLS generated RTL and is different from the
concept of clock uncertainty in RTL-level timing constraints. Timing
constraints generated by Vivado® HLS for the RTL implementation flow are
solely based on the target clock period.

It is also necessary to put the task that you are performing in context with
the performance metric that you are calculating. In our example, each
execution of the fir function results in one output sample. But we are
performing $N=11$ multiply accumulate operations for each execution of fir.
Therefore, if your metric of interest is MACs/second, you should calculate the
task latency for fir in terms of seconds, and then divide this by $11$ to get
the time that it takes to perform the equivalent of one MAC operation.

Calculating performance becomes even more complicated as we perform pipelining
and other optimizations. In this case, it is important to understand the
difference between task interval and task latency. It is a good time to
refresh your understanding of these two metrics of performance. This was
discussed in Chapter 1.4. And we will continue to discuss how different
optimizations effect different performance metrics.

###  2.5 Operation Chaining

Operation chaining is an important optimization that the Vivado® HLS performs
in order to optimize the final design. It is not something that a designer has
much control over, but it is important that the designer understands how this
works especially with respect to performance. Consider the multiply accumulate
operation that is done in a FIR filter tap. Assume that the add operation
takes 2 ns to complete, and a multiply operation takes 3 ns. If we set the
clock period to 1 ns (or equivalently a clock frequency of 1 GHz), then it
would take 5 cycles for the MAC operation to complete. This is depicted in
Figure 2.2 a). The multiply operation is executed over 3 cycles, and the add
operation is executed across 2 cycles. The total time for the MAC operation is
5 cycles $\times$ 1 ns per cycle $=$ 5 ns. Thus we can perform 1/5 ns $=$ 200
million MACs/second.

Figure 2.2: The performance of multiply accumulate operation changes depending
upon the target clock period. Assume the multiply operation takes 3 ns and add
operation takes 2 ns. Part a) has a clock period of 1 ns, and one MAC
operation takes 5 cycles. Thus the performance is 200 million MACs/sec. Part
b) has a clock period of 2 ns, and the MAC takes 3 cycles resulting in
approximately 167 million MACs/sec. Part c) has a clock period of 5 ns. By
using operation chaining, a MAC operation takes 1 cycle for a clock period of
200 million MACs/sec.

If we increase the clock period to 2 ns, the multiply operation now spans over
two cycles, and the add operation must wait until cycle 3 to start. It can
complete in one cycle. Thus the MAC operation requires 3 cycles, so 6 ns total
to complete. This allows us to perform approximately 167 million MACs/second.
This result is lower than the previous result with a clock period of 1 ns.
This can be explained by the “dead time” in cycle 2 where no operation is
being performed.

However, it is not always true that increasing the clock period results in
worse performance. For example, if we set the clock period to 5 ns, we can
perform both the multiply and add operation in the same cycle using operation
chaining. This is shown in Figure 2.2 c). Thus the MAC operation takes 1 cycle
where each cycle is 5 ns, so we can perform 200 million MACs/second. This is
the same performance as Figure 2.2 a) where the clock period is faster (1 ns).

So far we have performed chaining of only two operations in one cycle. It is
possible to chain multiple operations in one cycle. For example, if the clock
period is 10 ns, we could perform 5 add operations in a sequential manner. Or
we could do two sequential MAC operations.

It should start to become apparent that the clock period plays an important
role in how the Vivado® HLS tool optimizes the design. This becomes even more
complicated with all of the other optimizations that the Vivado® HLS tool
performs. It is not that important to fully understand the entire process of
the Vivado® HLS tool. This is especially true since the tool is constantly
being improved with each new release. However, it is important to have a good
idea about how the tool may work. This will allow you to better comprehend the
results, and even allow you to write more optimized code.

Although the Vivado® HLS can generate different different hardware for
different target clock periods, overall performance optimization and
determining the optimal target clock period still requires some creativity on
the part of the user. For the most part, we advocate sticking within a small
subset of clock periods. For example, in the projects we suggest that you set
the clock period to 10 ns and focus on understanding how other optimizations,
such as pipelining, can be used to create different architectures. This 100
MHz clock frequency is relatively easy to achieve, yet it is provides a good
first order result. It is certainly possible to create designs that run at a
faster clock rate. 200 MHz and faster designs are possible but often require
more careful balance between clock frequency targets and other optimization
goals. You can change the target clock period and observe the differences in
the performance. Unfortunately, there is no good rule to pick the optimal
frequency.

Vary the clock period for the base FIR architecture (Figure 2.1) from 10 ns to
1 ns in increments of 1 ns. Which clock period provides the best performance?
Which gives the best area? Why do you think this is the case? Do you see any
trends?

###  2.6 Code Hoisting

The if/else statement inside of the for loop is inefficient. For every control
structure in the code, the Vivado® HLS tool creates logical hardware that
checks if the condition is met, which is executed in every iteration of the
loop. Furthermore, this conditional structure limits the execution of the
statements in either the if or else branches; these statements can only be
executed after the if condition statement is resolved.

The if statement checks when x == 0, which happens only on the last iteration.
Therefore, the statements within the if branch can be “hoisted” out of the
loop. That is we can execute these statements after the loop ends, and then
remove the if/else control flow in the loop. Finally, we must change the loop
bounds from executing the “0th” iteration. This transform is shown in Figure
2.3. This shows just the changes that are required to the for loop.

⬇

Shift_Accum_Loop:

for (i = N - 1; i > 0; i–) {

shift_reg[i] = shift_reg[i - 1];

acc += shift_reg[i] * c[i];

}

acc += x * c[0];

shift_reg[0] = x;

Figure 2.3:  Removing the conditional statement from the for loop creates a
more efficient hardware implementation.

The end results is a much more compact implementation that is ripe for further
loop optimizations, e.g., unrolling and pipelining. We discuss those
optimizations later.

Compare the implementations before and after the removal of the if/else
condition done through loop hoisting. What is the difference in performance?
How do the number of resources change?

###  2.7 Loop Fission

We are doing two fundamental operations within the for loop. The first part
shifts the data through the shift_reg array. The second part performs the
multiply and accumulate operations in order to calculate the output sample.
Loop fission takes these two operations and implements each of them in their
own loop. While it may not intuitively seem like a good idea, it allows us to
perform optimizations separately on each loop. This can be advantageous
especially in cases when the resulting optimizations on the split loops are
different.

⬇

TDL:

for (i = N - 1; i > 0; i–) {

shift_reg[i] = shift_reg[i - 1];

}

shift_reg[0] = x;

acc = 0;

MAC:

for (i = N - 1; i >= 0; i–) {

acc += shift_reg[i] * c[i];

}

Figure 2.4:  A code snippet corresponding to splitting the for loop into two
separate loops.

The code in Figure 2.4 shows the result of manual loop fission optimization.
The code snippet splits the loop from Figure 2.3 into two loops. Note the
label names for the two loops. The first is TDL and the second is MAC. Tapped
delay line (TDL) is a common DSP term for the FIFO operation; MAC is short-
hand for “multiply accumulate”.

Compare the implementations before and after loop fission. What is the
difference in performance? How do the number of resources change?

Loop fission alone often does not provide a more efficient hardware
implementation. However, it allows each of the loops to be optimized
independently, which could lead to better results than optimizing the single,
original for loop. The reverse is also true; merging two (or more) for loops
into one for loop may yield the best results. This is highly dependent upon
the application, which is true for most optimizations. In general, there is
not a single ‘rule of thumb’ for how to optimize your code. There are many
tricks of the trade, and your mileage may vary. Thus, it is important to have
many tricks at your disposal, and even better, have a deep understanding of
how the optimizations work. Only then will you be able to create the best
hardware implementation. Let us continue to learn some additional tricks…

###  2.8 Loop Unrolling

By default, the Vivado® HLS tool synthesizes for loops in a sequential manner.
The tool creates a data path that implements one execution of the statements
in the body of the loop. The data path executes sequentially for each
iteration of the loop. This creates an area efficient architecture; however,
it limits the ability to exploit parallelism that may be present across loop
iterations.

Loop unrolling replicates the body of the loop by some number of times (called
the factor). And it reduces the number of iterations of the loop by the same
factor. In the best case, when none of the statements in the loop depend upon
any of the data generated in the previous iterations, this can substantially
increase the available parallelism, and thus enables an architecture that runs
much faster.

The first for loop (with the label TDL) in Figure 2.4 shifts the values up
through the shift_reg array. The loop iterates from largest value (N-1) to the
smallest value (i = 1). By unrolling this loop, we can create a data path that
executes a number of these shift operations in parallel.

⬇

TDL:

for (i = N - 1; i > 1; i = i - 2) {

shift_reg[i] = shift_reg[i - 1];

shift_reg[i - 1] = shift_reg[i - 2];

}

if (i == 1) {

shift_reg[1] = shift_reg[0];

}

shift_reg[0] = x;

Figure 2.5:  Manually unrolling the TDL loop in the fir11 function.

Figure 2.5 shows the result of unrolling the loop by a factor of two. This
code replicates the loop body twice. Each iteration of the loop now performs
two shift operations. Correspondingly, we must perform half of the number of
iterations.

Note that there is an additional if condition after the for loop. This is
required in the case when the loop does not have an even number of iterations.
In this case, we must perform the last “half” iteration by itself. The code in
the if statement performs this last “half” iteration, i.e., moving the data
from shift_reg[0] into shift_reg[1].

Also note the effect of the loop unrolling on the for loop header. The
decrement operation changes from i– to i=i-2. This is due to the fact that we
are doing two times the “work” in each iteration, thus we should decrement by
2 instead of 1.

Finally, the condition for terminating the for loop changes from i > 0 to i >
1. This is related to the fact that we should make sure that the “last”
iteration can fully complete without causing an error. If the last iteration
of the for loop executes when i = 1, then the second statement would try to
read from shift_reg[-1]. Rather than perform this illegal operation, we do the
final shift in the if statement after the for loop.

Write the code corresponding to manually unrolling this TDL for loop by a
factor of three. How does this change the loop body? What changes are
necessary to the loop header? Is the additional code in the if statement after
the for loop still necessary? If so, how is it different?

Loop unrolling can increase the overall performance provided that we have the
ability to execute some (or all) of the statements in parallel. In the
unrolled code, each iteration requires that we read two values from the
shift_reg array; and we write two values to the same array. Thus, if we wish
to execute both statements in parallel, we must be able to perform two read
operations and two write operations from the shift_reg array in the same
cycle.

Assume that we store the shift_reg array in one BRAM, and that BRAM has two
read ports and one write port. Thus we can perform two read operations in one
cycle. But we must sequentialize the write operations across two consecutive
cycles.

There are ways to execute these two statements in one cycle. For example, we
could store all of the values of the shift_reg array in separate registers. It
is possible to read and write to each individual register on every cycle. In
this case, we can perform both of the statements in this unrolled for loop in
one cycle. You can tell the Vivado® HLS tool to put all of the values in the
shift_reg array into registers using the directive #pragma HLS array_partition
variable=shift_reg complete. This is an important optimization, thus we
discuss the array_partition directive in more detail later.

A user can tell the Vivado® HLS tool to automatically unroll the loop using
the unroll directive. To automatically perform the unrolling done manually in
Figure 2.5, we should put the directive #pragma HLS unroll factor=2 into the
body of the code, right after the for loop header. While we can always
manually perform loop unrolling, it is much easier to allow the tool to do it
for us. It makes the code easier to read; and it will result in fewer coding
errors.

Unroll the TDL for loop automatically using the unroll directive. As you
increase the unroll factor, how does this change the number of resources (FFs,
LUTs, BRAMs, DSP48s, etc.)? How does it effect the throughput? What happens
when you use the array_partition directive in conjunction with the unroll
directive? What happens if you do not use the unroll directive?

Now, consider the second for loop (with the label MAC) in Figure 2.4. This
loop multiplies a value from the array c[] with a value from the array
shift_array[]. In each iteration it accesses the ith value from both arrays.
And then it adds the result of that multiplication into the acc variable.

Each iteration of this loop performs one multiply and one add operation. Each
iteration performs one read operation from array shift_reg[] and array c[].
The result of the multiplication of these two values is accumulated into the
variable acc.

The load and multiplication operations are independent across all of the
iterations of the for loop. The addition operation, depending on how it is
implemented, may depend upon the values of the previous iterations. However,
it is possible to unroll this loop and remove this dependency.

⬇

acc = 0;

MAC:

for (i = N - 1; i >= 3; i -= 4) {

acc += shift_reg[i] * c[i] + shift_reg[i - 1] * c[i - 1] +

shift_reg[i - 2] * c[i - 2] + shift_reg[i - 3] * c[i - 3];

}

for (; i >= 0; i–) {

acc += shift_reg[i] * c[i];

}

Figure 2.6:  Manually unrolling the MAC loop in the fir11 function by a factor
of four.

Figure 2.6 shows the code corresponding to unrolling the MAC for loop by a
factor of four. The first for loop is the unrolled loop. The for loop header
is modified in a similar manner to when we unrolled the TDL loop. The bound is
changed to i>=3, and i is decremented by a factor of $4$ for each iteration of
the unrolled loop.

While there was loop carried dependency in the original, unrolled for, it is
no longer present in the unrolled loop. The loop carried dependency came due
to the acc variable; since the result of the multiply accumulate is written to
this variable ever iteration, and we read from this register in every
iteration (to perform the running sum), it creates a read-after-write (RAW)
dependency across iterations. Note that there is not a dependency on the acc
variable in the unrolled for loop due to the way this is written. Thus we are
free to parallelize the four individual MAC operations in the unrolled for
loop.

There is an additional for loop after the unrolled for loop. This is necessary
to perform any partial iterations. Just like we required the if statement in
the TDL, this performs any computations on a potential last iteration. This
occurs when the number of iterations in the original, unrolled for loop is not
an even multiple of $4$.

Once again, we can tell the Vivado® HLS tool to automatically unroll the loop
by a factor of $4$ by inserting the code #pragma HLS unroll factor=4 into the
MAC loop body.

By specifying the optional argument skip_exit_check in that directive, the
Vivado® HLS tool will not add the final for loop to check for partial
iterations. This is useful in the case when you know that the loop will never
require these final partial iterations. Or perhaps performing this last few
iterations does not have an (major) effect on the results, and thus it can be
skipped. By using this option, the Vivado® HLS tool does not have to create
that additional for loop. Thus the resulting hardware is simpler, and more
area efficient.

The for loop is completely unrolled when no factor argument is specified. This
is equivalent to unrolling by the maximum number of iterations; in this case a
complete unrolling and unrolling by a factor of $11$ is equivalent. In both
cases, the loop body is replicated 11 times. And the loop header is
unnecessary; there is no need to keep a counter or check if the loop exit
condition is met. In order to perform a complete unrolling, the bounds of the
loop must be statically determined, i.e., the Vivado® HLS tool must be able to
know the number of iterations for the for loop at compile time.

Complete loop unrolling exposes a maximal amount of parallelism at the cost of
creating an implementation that requires a significant amount of resources.
Thus, it ok to perform a complete loop unroll on “smaller” for loops. But
completely unrolling a loop with a large number of iterations (e.g., one that
iterates a million times) is typically infeasible. Often times, the Vivado®
HLS tool will run for a very long time (and many times fail to complete after
hours of synthesis) if the resulting loop unrolling creates code that is very
large.

If you design does not synthesize in under 15 minutes, you should carefully
consider the effect of your optimizations. It is certainly possible that large
designs can take a significant amount for the Vivado® HLS tool to synthesize
them. But as a beginning user, your designs should synthesize relatively
quickly. If they take a long time, that most likely means that you used some
directives that significantly expanded the code, perhaps in a way that you did
not intend.

Synthesize a number of designs by varying the unroll factor for the MAC loop.
How does the performance change? How does the unroll factor number affect the
number of resources? Compare these results with the trends that you found by
unrolling the TDL.

###  2.9 Loop Pipelining

By default, the Vivado® HLS tool synthesizes for loops in a sequential manner.
For example, the for loop in Figure 2.1 will perform each iteration of the
loop one after the other. That is, all of the statements in the second
iteration happen only when all of the statements from the first iteration are
complete; the same is true for the subsequent iterations. This happens even in
cases when it is possible to perform statements from the iterations in
parallel. In other cases, it is possible to start some of the statements in a
later iteration before all of the statements in a former iteration are
complete. This does not happen unless the designer specifically states that it
should. This motivates the idea of loop pipelining, which allows for multiple
iterations of the loop to execute concurrently.

Consider the MAC for loop from Figure 2.4. This performs one multiply
accumulate (MAC) operation per iteration. This MAC for loop has four
operations in the loop body:

  * •

Read c[]: Load the specified data from the C array.

  * •

Read shift_reg[]: Load the specified data from the shift_reg array.

  * •

*: Multiply the values from the arrays c[] and shift_reg[].

  * •

+: Accumulate this multiplied result into the acc variable.

A schedule corresponding to one iteration of the MAC for loop is shown in
Figure 2.7 a). The Read operations each require 2 cycles. This is due to the
fact that the first cycle provides the address to the memory, and the data
from the memory is delivered during the second cycle. These two Read
operations can be done in parallel since there are no dependencies between
them. The * operation can begin in Cycle 2; assume that it takes three cycles
to complete, i.e., it is finished is Cycle 4. The + operation is chained to
start and complete during Cycle 4. The entire body of the MAC for loop takes 4
cycles to complete.

Figure 2.7: Part a) shows a schedule for the body of the MAC for loop. Part b)
shows the schedule for three iterations of a pipelined version of the MAC for
loop.

There are a number of performance metrics associated with a for loop. The
iteration latency is the number of cycles that it takes to perform one
iteration of the loop body. The iteration latency for this MAC for loop is 4
cycles. The for loop latency is the number of cycles required to complete the
entire execution of the loop. This includes time to calculate the
initialization statement (e.g., i = 0), the condition statement (e.g., i >=
0), and the increment statement (e.g., i–). Assuming that these three header
statements can be done in parallel with the loop body execution, the Vivado®
HLS tool reports the latency of this MAC for loop as 44 cycles. This is the
number of iterations (11) multiplied by the iteration latency (4 cycles) plus
one additional cycle to determine that the loop should stop iterating. And
then you subtract one. Perhaps the only strange thing here is the “subtract
1”. We will get to that in a second. But first, there is one additional cycle
that is required at the beginning of the next iteration, which checks if the
condition statement is satisfied (it is not) and then exits the loop. Now the
“subtract 1”: Vivado® HLS determines the latency as the cycle in which the
output data is ready. In this case, the final data is ready during Cycle 43.
This would be written into a register at the end of Cycle 43 and
correspondingly the beginning of Cycle 44. Another way to think of this is
that the latency is equal to the maximum number of registers between the input
data and the output data.

Loop pipelining is an optimization that overlaps multiple iterations of a for
loop. Figure 2.7 b) provides an example of pipelining for the MAC for loop.
The figure shows three iterations of the for which are executed
simultaneously. The first iteration is equivalent the the non-pipelined
version as depicted in Figure 2.7 a). The difference is the start times of the
subsequent iterations. In the non-pipelined version, the second iteration
begins after the first iteration is completed, i.e., in Cycle 5. However, the
pipelined version can start the subsequent iteration before the previous
iterations complete. In the figure, Iteration 2 starts at Cycle 2, and
Iteration 3 starts at Cycle 3. The remaining iterations start every
consecutive cycle. Thus, the final iteration, Iteration 11, would start at
Cycle 11 and it would complete during Cycle 14. Thus, the loop latency is 14.

The loop initiation interval (II) is another important performance metric. It
is defined as the number of clock cycles until the next iteration of the loop
can start. In our example, the loop II is 1, which means that we start a new
iteration of the loop every cycle. This is graphically depicted in Figure 2.7
b). The II can be explicitly set using the directive. For example, the
directive #pragma HLS pipeline II=2 informs the Vivado® HLS tool to attempt to
set the II=2. Note that this may not always be possible due to resource
constraints and/or dependencies in the code. The output reports will tell you
exact what the Vivado® HLS tool was able to achieve.

Explicitly set the loop initiation interval starting at 1 and increasing in
increments of 1 cycle. How does increasing the II effect the loop latency?
What are the trends? At some point setting the II to a larger value does not
make sense. What is that value in this example? How do you describe that value
for a general for loop?

Any for loop can be pipelined, so let us now consider the TDL for loop. This
for loop as a similar header to the MAC for loop. The body of the loop
performs an element by element shift of data through the array as described in
Section 2.3. There are two operations: one Read and one Write to the shift_reg
array. The iteration latency of this loop is 2 cycles. The Read operation
takes two cycles, and the Write operation is performed at the end of Cycle 2.
The for loop latency for this non-pipelined loop is 20 cycles.

Figure 2.8: Part a) shows a schedule for two iterations of the body of the TDL
for loop. Part b) shows the schedule for three iterations of a pipelined
version of the TDL for loop with II=1.

We can pipeline this loop by inserting the directive #pragma HLS pipeline II=1
after the loop header. The result of the synthesis is a loop initiation
interval equal to 1 cycle. This means that we can start a loop iteration every
cycle.

By modifying the example slightly, we can demonstrate a scenario where the
resource constraints do not allow the Vivado® HLS tool to achieve an II=1. To
do this, we explicitly set the type of memory for the shift_reg array. By not
specifying the resource, we leave it up to the Vivado® HLS tool to decide. But
we can specify the memory using a directive, e.g., the directive #pragma HLS
resource variable=shift_reg core=RAM_1P forces the Vivado® HLS tool to use a
single port RAM. When using this directive in conjunction with the loop
pipelining objective, the Vivado® HLS tool will fail to pipeline this loop
with an II=1. This is due to the fact that a pipelined version of this code
requires both a Read and Write operation in the same cycle. This is not
possible using a single port RAM. This is evident in Figure 2.8 b). Looking at
Cycle 2, we require a Write operation to the array shift_reg in Iteration 1,
and a Read operation to the same array in Iteration 2. We can modify the
directive to allow HLS more scheduling freedom by removing the explicit
request for II=1, e.g. #pragma HLS pipeline. In this case, HLS will
automatically increase the initiation interval until it can find a feasible
schedule.

The RESOURCE directive allows the user to force the Vivado® HLS tool to map an
operation to a hardware core. This can be done on arrays (as shown above) and
also for variables. Consider the code a = b + c;. We can use the RESOURCE
directive #pragma HLS RESOURCE variable=a core=AddSub_DSP to tell the Vivado®
HLS tool that the add operation is implemented using a DSP48. There are a wide
variety of cores described in the Vivado® HLS documentation [63]. In general,
it is advised to let the Vivado® HLS decide the resources. If these are not
satisfactory, then the designer can use directives.

###  2.10 Bitwidth Optimization

The C language provides many different data types to describe different kinds
of behavior. Up until this point, we have focused on the int type, which
Vivado® HLS treats as a 32-bit signed integer. The C language also provides
floating point data types, such as float and double, and integer data types,
such as char, short, long, and long long. Integer datatypes may be unsigned.
All of these data types have a size which is a power of 2.

The actual number of bits for these C data types may vary depending upon the
processor architecture. For example, an int can be 16 bits on a micro
controller and 32 bits on a general purpose processor. The C standard dictates
minimum bit widths (e.g., an int is at least 16 bits) and relations between
the types (e.g., a long is not smaller than an int which is not smaller than a
short). The C99 language standard eliminated this ambiguity with types such as
int8_t, int16_t, int32_t, and int64_t.

The primary benefits of using these different data types in software revolve
around the amount of storage that the data type requires. For large arrays,
using 8 bit values instead of 16 bit values can cut memory usage in half. The
drawback is that the range of values that you can represent is reduced. An 8
bit signed value allows numbers in the range [-128,127] while the 16 bit
signed data type has a range of [-32,768, 32,767]. Smaller operations may also
require fewer clock cycles to execute, or may allow more instructions to be
executed in parallel.

The same benefits are seen in an FPGA implementation, but they are even more
pronounced. Since the Vivado® HLS tool generates a custom data path, it will
create an implementation matched to the specified data types. For example, the
statement a = b * c will have different latency and resource usage depending
upon the data type. If all of the variables are 32 bits wide, then more
primitive boolean operations need to be performed than if the variables are
only 8 bits wide. As a result, more FPGA resources (or more complex resources)
must be used. Additionally, more complex logic typically requires more
pipelining in order to achieve the same frequency. A 32-bit multiplication
might require 5 internal registers to meet the same frequency that an 8 bit
multiplication can achieve with only one internal register. As a result, the
latency of the operation will be larger (5 cycles instead of 1 cycle) and HLS
must take this into account.

Create a simple design that implements the code a = b * c. Change the data
type of the variables to char, short, int, long, and long long. How many
cycles does the multiply operation take in each case? How many resources are
used for the different data types?

What primitive boolean operations are needed to implement the multiplication
of 8-bit numbers? How does this change when implementing multiplication of
32-bit numbers? Hint: How many primitive decimal operations are needed to
implement multiplication of two 8 digit decimal numbers?

In many cases to implement optimized hardware, it is necessary to process data
where the bitwidth is not a power of two. For example, analog to digital
converters often output results in 10 bits, 12 bits, or 14 bits. We could map
these to 16 bit values, but this would likely reduce performance and increase
resource usage. To more accurately describe such values, Vivado® HLS provides
arbitrary precision data types which allow for signed and unsigned data types
of any bitwidth.

There are two separate classes for unsigned and signed data types:

  * •

Unsigned: ap_uint<width>

  * •

Signed: ap_int<width>

where the width variable is an integer between 1 and 10241111024 is the
default maximum value, and this can be changed if needed. See the Vivado® HLS
user manuals for more information on how to do this.. For example, ap_int<8>
is an 8 bit signed value (same as char), and ap_uint<32> is a 32 bit unsigned
value (same as unsigned int). This provides a more powerful data type since it
can do any bitwidth, e.g., ap_uint<4> or ap_int<537>. To use these data types
you must use C++ and include the file ap_int.h, i.e., add the code #include
”ap_int.h” in your project and use a filename ending in ‘.cpp’222Similar
capabilities are also available in C using the file ap_cint.h.

Consider coefficients array c[] from the fir filter code in Figure 2.1. It is
reprinted here for you convenience: coef_t c[N] = {53, 0, -91, 0, 313, 500,
313, 0, -91, 0, 53};. The data type coef_t is defined as an int meaning that
we have 32 bits of precision. This is unnecessary for these constants since
they range from -91 to 500. Thus we could use a smaller data type for this. We
will need a signed data type since we have positive and negative values. And
the maximum absolute value for any of these 11 entries is 500, which requires
$\lceil\log_{2}500\rceil=9$ bits. Since we need negative numbers, we add an
additional bit. Thus coef_t can be declared as ap_int<10>.

What is the appropriate data type for the variable i in the fir function (see
Figure 2.1)?

We can also more accurately define the data types for the other variables in
the fir function, e.g., acc and shift_reg. Consider the shift_reg array first.
This is storing the last 11 values of the input variable x. So we know that
the shift_reg values can safely have the same data type as x. By “safe”, we
mean that there will be no loss in precision, i.e., if shift_reg had a data
type with a smaller bitwidth, then some significant bits of x would need to be
eliminated to fit them into a value in shift_reg. For example, if x was
defined as 16 bits (ap_uint<16>) and shift_reg was defined as 12 bits
(ap_uint<12>), then we would cut off the 4 most significant bits of x when we
stored it into shift_reg.

Defining the appropriate data type for acc is a more difficult task. The acc
variable stores the multiply and accumulated sum over the shift_reg and the
coefficient array c[] i.e., the output value of the filter. If we wish to be
safe, then we calculate the largest possible value that could be stored in
acc, and set the bitwidth as that.

To accomplish this, we must understand how the bitwidth increases as we
perform arithmetic operations. Consider the operation a = b + c where
ap_uint<10> b and ap_uint<10> c. What is the data type for the variable a? We
can perform a worst case analysis here, and assume both a and b are the
largest possible value $2^{10}=1024$. Adding them together results in $a=2024$
which can be represented as an 11 bit unsigned number, i.e., ap_uint<11>. In
general we will need one more bit than the largest bitwidth of the two number
being added. That is, when ap_uint<x> b and ap_uint<y> c, the data type for a
is ap_uint<z> where $z=\max(x,y)+1$. This same is also true when adding signed
integers.

That handles one part of the question for assigning the appropriate data type
to acc, but we must also deal with the multiply operation. Using the same
terminology, we wish to determine the value the bitwidth $z$ given the
bitwidths $x$ and $y$ (i.e., ap_int<z> a, ap_int<x> b, ap_int<y> c) for the
operation a = b * c. While we will not go into the details, the formula is
$z=x+y$.

Given these two formulas, determine the bitwidth of acc such that it is safe.

Ultimately we are storing acc into the variable y which is an output port of
the function. Therefore, if the bitwidth of acc is larger than the bitwidth of
c, the value in acc will be truncated to be stored into y. Thus, is it even
important to insure that the bitwidth of acc is large enough so that it can
handle the full precision of the multiply and accumulate operations?

The answer to the question lies in the tolerance of the application. In many
digital signal processing applications, the data itself is noisy, meaning that
the lower several bits may not have any significance. In addition, in signal
processing applications, we often perform numerical approximations when
processing data which can introduce additional error. Thus, it may not be
important that we insure that the acc variable has enough precision to return
a completely precise result. On the other hand, it may be desirable to keep
more bits in the accumulation and then round the final answer again to reduce
the overall rounding error in the computation. Other applications, such as
scientific computing, more dynamic range is often required, which may lead to
the use of floating point numbers instead of integer or fixed-point
arithmetic. So what is the correct answer? Ultimately it is up to the
tolerance of the application designer.

###  2.11 Complex FIR Filter

To this point, we have solely looked at filtering real numbers. Many digital
wireless communication systems deal with complex numbers using in-phase (I)
and quadrature (Q) components (see Chapter LABEL:chap:Wireless for more
details). Fortunately, it is possible to create a complex FIR filter using
real FIR filter as we describe in the following.

To understand how to build a complex FIR filter from real FIR filters consider
Equation 2.4. Assume that $(I_{in},Q_{in})$ is one sample of the input data
that we wish to filter. And one of the complex FIR filter coefficients is
denoted as $(I_{fir},Q_{fir})$. There will be more than one input sample and
complex coefficient, but let us not worry about that for now.

$(I_{in}+jQ_{in})(I_{fir}+jQ_{fir})=(I_{in}I_{fir}-Q_{in}Q_{fir})+j(Q_{in}I_{fir}+I_{in}Q_{fir})$
(2.4)

Equation 2.4 shows the multiplication of the input complex number by one
coefficient of the complex FIR filter. The right side of the equation shows
that the real portion of the output of complex input filtered by a complex FIR
filter is $I_{in}I_{fir}-Q_{in}Q_{fir}$ and the imaginary output is
$Q_{in}I_{fir}+I_{in}Q_{fir}$. This implies that we can separate the complex
FIR filter operation into four real filters as shown in Figure 2.9.

Figure 2.9: A complex FIR filter built from four real FIR filters. The input I
and Q samples are feed into four different real FIR filters. The FIR filters
hold the in-phase (FIR I) and quadrature (FIR Q) complex coefficients.

A complex FIR filter takes as input a complex number $(I_{in},Q_{in})$ and
outputs a complex filtered value $(I_{out},Q_{out})$. Figure 2.9 provides a
block diagram of this complex filter using four real FIR filters (FIR I1, FIR
Q1, FIR I2, FIR Q2). The filters FIR I1 and FIR I2 are equivalent, i.e., they
have the exact same coefficients. FIR Q1 and FIR Q2 are also equivalent. The
output of each of these filters corresponds to a term from Equation 2.4. These
output are then added or subtracted to provide the final filtered complex
output $(I_{out},Q_{out})$.

We used a hierarchical structure to define this complex FIR filter. Vivado®
HLS implements hierarchy using functions. Taking the previous real FIR
function void fir (data_t *y, data_t x) we can create another function that
encapsulates four versions of this fir function to create the complex FIR
filter. This code is shown in Figure 2.10.

⬇

typedef int data_t;

void firI1(data_t *y, data_t x);

void firQ1(data_t *y, data_t x);

void firI2(data_t *y, data_t x);

void firQ2(data_t *y, data_t x);

void complexFIR(data_t Iin, data_t Qin, data_t *Iout, data_t *Qout) {

data_t IinIfir, QinQfir, QinIfir, IinQfir;

firI1(&IinIfir, Iin);

firQ1(&QinQfir, Qin);

firI2(&QinIfir, Qin);

firQ2(&IinQfir, Iin);

*Iout = IinIfir + QinQfir;

*Qout = QinIfir - IinQfir;

}

Figure 2.10: The Vivado® HLS code to hierarchically implement a complex FIR
filter using four real FIR filters.

The code defines four functions firI1, firQ1, firI2, and firQ2. Each of these
functions has the exact same code, e.g., that of the fir function from Figure
2.1. Typically, we would not need to replicate the function; we could simply
call the same function four times. However, this is not possible in this case
due to the static keyword used within the fir function for the shift_reg.

The function calls act as interfaces. The Vivado® HLS tool does not optimize
across function boundaries. That is, each fir function synthesized
independently, and treated more or less as a black box in the complexFIR
function. You can use the inline directive if you want the Vivado® HLS tool to
co-optimize a particular function within its parent function. This will add
the code from that function into the parent function and eliminate the
hierarchical structure. While this can increase the potential for benefits in
performance and area, it also creates a large amount of code that the tool
must synthesize. That may take a long time, even fail to synthesize, or may
result in a non-optimal design. Therefore, use the inline directive carefully.
Also note that the Vivado® HLS tool may choose to inline functions on its own.
These are typically functions with a small amount of code.

⬇

float mul(int x, int y) { return x * y; }

float top_function(float a, float b, float c, float d) {

return mul(a, b) + mul(c, d) + mul(b, c) + mul(a, d);

}

float inlined_top_function(float a, float b, float c, float d) {

return a * b + c * d + b * c + a * d;

}

Figure 2.11:  A simple and trivial example to demonstrate the inline
directive. The top_function has four function calls to the function mul. If we
placed an inline directive on the mul function, the result is similar to what
you see in the function inlined_top_function.

The inline directive removes function boundaries, which may enable additional
opportunities for the Vivado® HLS tool at the cost of increasing the
complexity of the synthesis problem, i.e., it will likely make the synthesis
time longer. It also eliminates any overhead associated with performing the
function call. It allows for different implementations while maintaining the
structure of the code, and making it hierarchical and more readable.

The code in Figure 2.11 provides an example of how the inline directive works.
The function inlined_top_function is the result of using the inline directive
on the mul function.

The Vivado® HLS tool will sometimes choose to inline functions automatically.
For example, it will very likely choose to inline the mul function from Figure
2.11 since it is small. You can force the tool to keep the function hierarchy
by placing an inline directive in the function with the off argument.

The inline directive also has a recursive argument that inlines all functions
called within the inlined function to also be inlined. That is, it will
recursively add the code into the parent functions from every child function.
This could create a substantial code base, so use this function carefully.

An inlined function will not have separate entries in the report since all of
the logic will be associated with the parent function.

###  2.12 Conclusion

This chapter describes the specification and optimization of a FIR filter
using the Vivado® HLS tool. The goal is to provide an overview of the HLS
process. The first step in this process is understanding the basic concepts
behind the computation of the FIR filter. This does not require a deep
mathematical understanding, but certainly enough knowledge to write it in a
manner that is synthesizable by the Vivado® HLS tool. This may require
translating the code from a different language (e.g., MATLAB, Java, C++,
Python, etc.). Many times it requires rewriting to use simpler data
structures, e.g., one that is explicitly implemented in an array. And it often
involves removing system calls and other code not supported by the HLS tool.

Creating an optimum architecture requires a basic understanding about how the
HLS tool performs its synthesis and optimization process to RTL code. It is
certainly not unnecessary to understand the exact HLS algorithms for schedule,
binding, resource allocation, etc. (and many times these are proprietary). But
having a general idea of the process does aid the designer in writing code
that maps well to hardware. Throughout the chapter, we talked about some of
the key features of the HLS synthesis process that are necessary to understand
when performing various optimizations. It is especially important to
understand the way that the HLS tool reports performance, which we describe in
Chapter 2.4.

Additionally, we presented some basic HLS optimizations (including loop and
bitwidth optimizations). We highlighted their benefits and potential drawbacks
using the FIR filter as an example. These are common optimizations that can be
applied across a wide range of applications. We provide more details about
these optimizations in subsequent chapters as we walk through the
implementation of other more complex applications.

Finally, there is an entire project devoted to further optimizing the FIR
filter. This is located in the Appendix in Chapter LABEL:chapter:FIR_Project.

##  Chapter 3 CORDIC

###  3.1 Overview

CORDIC (Coordinate Rotation DIgital Computer) is an efficient technique to
calculate trigonometric, hyperbolic, and other mathematical functions. It is a
digit-by-digit algorithm that produces one output digit per iteration. This
allows us to tune the accuracy of the algorithm to the application
requirements; additional iterations produce a more precise output result.
Accuracy is another common design evaluation metric alongside performance and
resource usage. CORDIC performs simple computations using only addition,
subtraction, bit shifting, and table lookups, which are efficient to implement
in FPGAs and more generally in hardware.

The CORDIC method was developed by Jack Volder in the 1950’s as a digital
solution to replace an analog resolver for real-time navigation on a B-58
bomber. A resolver measures degrees of rotation. At that time hardware
implementations of multiply operations were prohibitively expense and CPUs had
very limited amount of state. Thus the algorithm needed to have low complexity
and use simple operations. Over the years, it has been used in math co-
processors [24], linear systems [3], radar signal processing [4], Fourier
transforms [21], and many other digital signal processing algorithms. It is
now commonly used in FPGA designs. Vivado® HLS uses a CORDIC core for
calculating trigonometric functions and it is a common element of modern FPGA
IP core libraries.

The goal of this chapter is to demonstrate how to create an optimized CORDIC
core using high-level synthesis. We are gradually increasing the complexity of