this storage essentially requires one more bit to represent in the array. As a
result, the left[] and right[] arrays are one bit larger than you might
expect.

For a large dataset ($n>256$), what is the approximate latency, in terms of
$n$, of the code in Figure 11.8? What portions of the code dominate the number
of cycles?

####  11.2.4 Compute Bit Length

The compute_bit_length function determines the depth in the tree for each
symbol. The depth is important because it determines the number of bits used
to encode each symbol. Computing the depth of each node in the tree is done
using the recurrence:

$\begin{array}[]{rrcl}&\mathrm{depth}(\mathrm{root})&=&0\\\ \forall
n!=\mathrm{root},&\mathrm{depth}(n)&=&\mathrm{depth}(\mathrm{parent}(n)+1)\\\
\forall n,&\mathrm{child\\_depth}(n)&=&\mathrm{depth}(n)+1\end{array}$ (11.1)

This recurrence can be computed by traversing the tree starting at the root
node and exploring each internal node in order. As we traverse each internal
node, we can compute the depth of the node and the corresponding depth
(incremented by one) of any child nodes. It turns out that we don’t actually
care about the depth of the internal nodes, only about the depth of the child
nodes. As a result, the code actually computes the recurrence:

$\begin{array}[]{rrcl}&\mathrm{child\\_depth}(\mathrm{root})&=&1\\\ \forall
n!=\mathrm{root},&\mathrm{child\\_depth}(n)&=&\mathrm{child\\_depth}(\mathrm{parent}(n)+1)\end{array}$
(11.2)

The code for this function is shown in Figure 11.9. The input arguments to the
function represent a Huffman tree in parent[], left[], and right[].
num_symbols contains the number of input symbols, which is one more than the
number of intermediate nodes in the tree. The output length_histogram[]. Each
element of that array stores the number of symbols with the given depth. Thus,
if there are five symbols with depth three, then length_histogram[3] = 5.

⬇

#include ”huffman.h”

#include ”assert.h”

void compute_bit_length (

/* input */ ap_uint<SYMBOL_BITS> parent[INPUT_SYMBOL_SIZE-1],

/* input */ ap_uint<SYMBOL_BITS> left[INPUT_SYMBOL_SIZE-1],

/* input */ ap_uint<SYMBOL_BITS> right[INPUT_SYMBOL_SIZE-1],

/* input */ int num_symbols,

/* output */ ap_uint<SYMBOL_BITS> length_histogram[TREE_DEPTH]) {

assert(num_symbols > 0);

assert(num_symbols <= INPUT_SYMBOL_SIZE);

ap_uint<TREE_DEPTH_BITS> child_depth[INPUT_SYMBOL_SIZE-1];

ap_uint<SYMBOL_BITS> internal_length_histogram[TREE_DEPTH];

init_histogram:

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

#pragma HLS pipeline II=1

internal_length_histogram[i] = 0;

}

child_depth[num_symbols-2] = 1; // Depth of the root node is 1.

traverse_tree:

for(int i = num_symbols-3; i >= 0; i–) {

#pragma HLS pipeline II=3

ap_uint<TREE_DEPTH_BITS> length = child_depth[parent[i]] + 1;

child_depth[i] = length;

if(left[i] != INTERNAL_NODE || right[i] != INTERNAL_NODE){

int children;

if(left[i] != INTERNAL_NODE && right[i] != INTERNAL_NODE) {

// Both the children of the original node were symbols

children = 2;

} else {

// One child of the original node was a symbol

children = 1;

}

ap_uint<SYMBOL_BITS> count = internal_length_histogram[length];

count += children;

internal_length_histogram[length] = count;

length_histogram[length] = count;

}

}

}

Figure 11.9: The complete code for determining the number of symbols at each
bit length.

child_depth[] stores the depth of each internal node while the tree is being
traversed. After the depth of each internal node is determined in the
traverse_tree loop, length_histogram[] is updated. internal_length_histogram[]
is used to ensure that our function adheres the requirements for the dataflow
directive, where the output array length_histogram[] is never read. The
init_histogram loop initializes these two arrays.

The init_histogram loop has a pipeline directive with II = 1. Is it possible
to meet this II? What happens if we increase the II to something larger? What
happens if we do not apply this directive?

Internal nodes in the tree are traversed from the root node, which has the
largest index, down to index zero. Since the array of nodes were created in
bottom-up order, this reverse order results in a top-down traversal of the
tree enabling the computation of the recurrence for each node in a single pass
through the nodes. For each node, we determine the depth of its children. Then
if the node actually does have any children which are symbols, we figure out
how many children and update the histogram accordingly. Child nodes which are
internal nodes are represented by the special value INTERNAL_NODE.

For a large dataset ($n>256$), what is the approximate latency, in terms of
$n$, of the code in Figure 11.9? What portions of the code dominate the number
of cycles?

This code has several recurrences. For example, one recurrence occurs because
of the histogram computation. In this case, the loop is synthesized with an II
of 3. What happens if you target a lower II in the pipeline directive? Can you
rewrite the code to eliminate the recurrences and achieve a lower II?

####  11.2.5 Truncate Tree

The next part of the Huffman encoding process reorganizes nodes with a depth
that is larger than that specified in MAX_CODEWORD_LENGTH. This is done by
finding any symbols with a greater depth, and moving them to a level that is
smaller than that specified target. Interestingly, this can be done entirely
by manipulating the histogram of symbol depths, as long as the histogram is
modified in a way that is consistent with the same modifications on the
original tree.

The input histogram is contained in input_length_histogram, which was derived
by the compute_bit_length() function described in the previous section. There
are two identical output arrays truncated_length_histogram1 and
truncated_length_histogram2. These arrays are passed to two separate functions
later in the process (canonize_tree and create_codewords), and thus we must
have two arrays to adhere to the single producer, single consumer constraint
of the dataflow directive.

⬇

#include ”huffman.h”

#include ”assert.h”

void truncate_tree(

/* input */ ap_uint<SYMBOL_BITS> input_length_histogram[TREE_DEPTH],

/* output */ ap_uint<SYMBOL_BITS> output_length_histogram1[TREE_DEPTH],

/* output */ ap_uint<SYMBOL_BITS> output_length_histogram2[TREE_DEPTH]

) {

// Copy into temporary storage to maintain dataflow properties

copy_input:

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

output_length_histogram1[i] = input_length_histogram[i];

}

ap_uint<SYMBOL_BITS> j = MAX_CODEWORD_LENGTH;

move_nodes:

for(int i = TREE_DEPTH - 1; i > MAX_CODEWORD_LENGTH; i–) {

// Look to see if there is any nodes at lengths greater than target depth

reorder:

while(output_length_histogram1[i] != 0) {

#pragma HLS LOOP_TRIPCOUNT min=3 max=3 avg=3

if (j == MAX_CODEWORD_LENGTH) {

// Find deepest leaf with codeword length < target depth

do {

#pragma HLS LOOP_TRIPCOUNT min=1 max=1 avg=1

j–;

} while(output_length_histogram1[j] == 0);

}

// Move leaf with depth i to depth j+1.

output_length_histogram1[j] -= 1; // The node at level j is no longer a leaf.

output_length_histogram1[j+1] += 2; // Two new leaf nodes are attached at
level j+1.

output_length_histogram1[i-1] += 1; // The leaf node at level i+1 gets
attached here.

output_length_histogram1[i] -= 2; // Two leaf nodes have been lost from level
i.

// now deepest leaf with codeword length < target length

// is at level (j+1) unless j+1 == target length

j++;

}

}

⬇

// Copy the output to meet dataflow requirements and check the validity

unsigned int limit = 1;

copy_output:

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

output_length_histogram2[i] = output_length_histogram1[i];

assert(output_length_histogram1[i] >= 0);

assert(output_length_histogram1[i] <= limit);

limit *= 2;

}

}

Figure 11.10: The complete code for rearranging the Huffman tree such that the
depth of any node is under the target specified by the parameter
MAX_CODEWORD_LENGTH.

The code is shown in Figure 11.10. The copy_input loop copies the data from
the input array input_length_histogram. The move_nodes loop contains the bulk
of the processing to modify the histogram. Lastly, the input_length_histogram
function copies the internal result to other output at the end of the
function.

The copy_in for loop is not optimized. What happens to the latency and
initiation interval of the truncate_tree function if we use a pipeline or
unroll directive on this loop. What happens to the overall latency and
initiation interval of the design (i.e., the huffman_encoding function)?

The function continues in the second move_nodes for loop, which performs the
bulk of the computation. This for loop starts by iterating through the
truncated_length_histogram array from the largest index (TREE_DEPTH \- the
specified maximum depth for a tree). This continues down through the array
until there is a non-zero element or i reaches the MAX_CODEWORD_LENGTH. If we
do not find a non-zero element, that means the initial input Huffman tree does
not have any nodes with a depth larger than the target depth. In other words,
we can exit this function without performing any truncation. If there is a
value larger than the target depth, then the function continues by
reorganizing the tree so that all of the nodes have depth smaller than the
target depth. This is done by the operations in the reorder while loop. When
there are nodes to move, the move_nodes for loop goes through them from those
with the largest depth, and continues to smaller depths until all nodes are
rearranged with a depth smaller than the target. Each iteration of this
move_nodes for loops works on moving nodes from one depth at a time.

The reorder while loop moves one node in each iteration. The first if
statement is used to find the leaf node with the largest depth. We will then
alter this node by making it an intermediate node, and adding it and the leaf
node with a depth larger than than target as children. This if clause has a
do/while loop that iterates downward from the target looking for a non-zero
entry in the truncated_length_histogram array. It works in a similar manner as
the beginning of the move_nodes for loop. When it has found the deepest leaf
node less than the target depth, it stops. The depth of this node is stored in
j.

Now we have a node with a depth i larger than the target, and a node with a
depth smaller than the target stored in j. We move the node from depth i and a
node from j into child nodes at depth j + 1. Therefore, we add two symbols to
truncated_length_histogram[j+1]. We are making a new intermediate node a depth
j thus, we subtract a symbol from that level. We move the other leaf node from
depth i to depth i - 1. And we subtract two from truncated_length_histogram[i]
since one of the nodes went to level j + 1 and the other when to level i - 1.
These operations are performed in the four statements on the array
truncated_length_histogram. Since we added a symbol to level j + 1, we update
j, which holds the highest level under the target level, and then we repeat
the procedure. This is done until there are no additional symbols with a depth
larger than the target.

The function completes by creating an additional copy of the new bit lengths.
This is done by storing the updated bit lengths in the array
truncated_length_histogram1 into the array truncated_length_histogram2. We
will pass these two arrays to the final two functions in the huffman_encoding
top function; we need two arrays to insure that the constraints of the
dataflow directive are met.

####  11.2.6 Canonize Tree

The next step in the encoding process is to determine the number of bits for
each of the symbols. We do this in the canonize_tree function shown in Figure
11.11. The function takes as input an array of symbols in sorted order, the
total number of symbols (num_symbols), and a histogram of lengths describing
the Huffman tree. The output symbol_bits[] contains the number of encoded bits
used for each symbol. Thus, if the symbol with value 0x0A is encoded in 4
bits, then symbol_bits[10] = 4.

⬇

#include ”huffman.h”

#include ”assert.h”

void canonize_tree(

/* input */ Symbol sorted[INPUT_SYMBOL_SIZE],

/* input */ ap_uint<SYMBOL_BITS> num_symbols,

/* input */ ap_uint<SYMBOL_BITS> codeword_length_histogram[TREE_DEPTH],

/* output */ CodewordLength symbol_bits[INPUT_SYMBOL_SIZE] ) {

assert(num_symbols <= INPUT_SYMBOL_SIZE);

init_bits:

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

symbol_bits[i] = 0;

}

ap_uint<SYMBOL_BITS> length = TREE_DEPTH;

ap_uint<SYMBOL_BITS> count = 0;

// Iterate across the symbols from lowest frequency to highest

// Assign them largest bit length to smallest

process_symbols:

for(int k = 0; k < num_symbols; k++) {

if (count == 0) {

//find the next non-zero bit length

do {

#pragma HLS LOOP_TRIPCOUNT min=1 avg=1 max=2

length–;

// n is the number of symbols with encoded length i

count = codeword_length_histogram[length];

}

while (count == 0);

}

symbol_bits[sorted[k].value] = length; //assign symbol k to have length bits

count–; //keep assigning i bits until we have counted off n symbols

}

}

Figure 11.11:  The complete code for canonizing the Huffman tree, which
determins the number of bits for each symbol.

The canonization process consists of two loops, labeled init_bits and
process_symbols. The init_bits loop executes first, initializing symbol_bits[]
array to 0. The process_symbols loop then processes the symbols in sorted
order from smallest frequency to largest frequency. Naturally, the least
frequent symbols are assigned the longest codes while the most frequent
symbols are assigned the shortest code. Each time through the process_symbols
loop, we assign the length of one symbol. The length of the symbol is
determined by the the inner do/while loop, which steps through the histogram
of lengths. This loop finds the largest bit length that has not yet had
codewords assigned and stores the number of codewords in that length in count.
Each time through the outer loop, count is decremented until we run out of
codewords. When count becomes zero, the inner do/while loop executes again to
find a length with codewords to assign.

⬇

int k = 0;

process_symbols:

for(length = TREE_DEPTH; length >= 0; length–) {

count = codeword_length_histogram[length];

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

#pragma HLS pipeline II=1

symbol_bits[sorted[k++].value] = length;

}

}

Figure 11.12:  Alternate loop structure for the process_symbols loop in Figure
11.11.

Note that the process_symbols loop cannot be pipelined because the inner
do/while loop cannot be unrolled. This is somewhat awkward as the inner loop
will usually execute exactly once, stepping to the next length in the
histogram. Only in somewhat rare cases will the inner loop need to execute
more than once if we happen to get to a length which does not have any
codewords assigned. In this case, there’s not too much of a loss since all the
operations in the loop are simple operations that are unlikely to be
pipelined, with the exception of the memory operations. There are other ways
to structure this loop, however, which can be pipelined. One possibility is to
use an outer for loop to iterate over codeword_length_histogram[] and an inner
loop to count each symbol, as shown in Figure 11.12.

Implement the code in Figure 11.11 and the alternate code structure in Figure
11.12. Which results in higher performance? Which coding style is more natural
to you?

####  11.2.7 Create Codeword

The final step in the encoding process is to create the codeword for each
symbol. This process simply assigns each symbol in order according to the
properties of a Canonical Huffman code. The first property is that longer
length codes have a higher numeric value than the same length prefix of
shorter codes. The second property is that codes with the same length increase
by one as the symbol value increases. In order to achieve these properties
while keeping the code simple, it is useful to determine the first codeword of
each length. If we know the number of codewords of each length given by
$\mathrm{codeword\\_length\\_histogram}$, then this can be found using the
following recurrence:

$\begin{array}[]{rrcl}&\mathrm{first\\_codeword}(1)&=&0\\\ \forall
i>1,&\mathrm{first\\_codeword}(i)&=&(\mathrm{first\\_codeword}(i-1)+\mathrm{codeword\\_length\\_histogram}(i-1))<<1\end{array}$
(11.3)

Essentially, rather than actually assigning the codewords one after another,
this recurrence allocates all the codewords first. This allows us to actually
assign the codewords in order of symbol value without being concerned about
also ordering them by length or frequency.

In addition to assigning codewords to symbols, we also need to format the
codewords so that they can be easily used for encoding and decoding. Systems
that use Huffman encoding often store codewords in bit-reversed order. This
can make the decoding process easier since the bits are stored in the same
order that the tree is traversed during decoding, from root node to leaf node.

The code implementing the create_codewords function is shown in Figure 11.13.
symbol_bits[] contains the length of the codeword for each symbol and
codeword_length_histogram[] contains the number of codewords with each length.
The output encoding[] represents the encoding for each symbol. Each element
consists of the actual codeword and the length of each codeword packed
together. The maximum length of a codeword is given by the MAX_CODEWORD_LENGTH
parameter. In turn, this determines the number of bits required to hold the
codeword, which is given by CODEWORD_LENGTH_BITS. The CODEWORD_LENGTH_BITS
least significant bits of each element in the encoding array contains the same
value received from the input array symbol_bits. The high order
MAX_CODEWORD_LENGTH bits of each encoding element contains the actual
codeword. Using 27 bits for MAX_CODEWORD_LENGTH resulting in
CODEWORD_LENGTH_BITS of 5 is a particularly useful combination, since each
element of encoding[] fits in a single 32-bit word.

The code consists primarily of two loops, labeled first_codewords and
assign_codewords. The first_codewords loop finds the first codeword with each
length, implementing the recurrence in Equation 11.3. The assign_codewords
loop finally associates each symbol with a codeword. The codeword is found
using the length of each codeword and indexing into the correct element of
first_codeword[]. The main complexity of this code is in the bit reversal
process, which is based on the bit_reverse32 function. We have talked about
this function previously in the FFT chapter (see Chapter 5.3), so we will not
discuss it here again. After reversing the bits in the codeword, the next
statement removes the least significant ’0’ bits leaving only the bit-reversed
codeword. The bit-reversed codeword is then packed in the high-order bits
together with the length of the symbol in the low-order bits and stored in
encoding[]. Lastly, the value in first_codeword[] is incremented.

⬇

#include ”huffman.h”

#include ”assert.h”

#include <iostream>

void create_codeword(

/* input */ CodewordLength symbol_bits[INPUT_SYMBOL_SIZE],

/* input */ ap_uint<SYMBOL_BITS> codeword_length_histogram[TREE_DEPTH],

/* output */ PackedCodewordAndLength encoding[INPUT_SYMBOL_SIZE]

) {

Codeword first_codeword[MAX_CODEWORD_LENGTH];

// Computes the initial codeword value for a symbol with bit length i

first_codeword[0] = 0;

first_codewords:

for(int i = 1; i < MAX_CODEWORD_LENGTH; i++) {

#pragma HLS PIPELINE II=1

first_codeword[i] = (first_codeword[i-1] + codeword_length_histogram[i-1]) <<
1;

Codeword c = first_codeword[i];

// std::cout << c.to_string(2) << ” with length ” << i << ”\n”;

}

assign_codewords:

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

#pragma HLS PIPELINE II=5

CodewordLength length = symbol_bits[i];

//if symbol has 0 bits, it doesn’t need to be encoded

make_codeword:

if(length != 0) {

// std::cout << first_codeword[length].to_string(2) << ”\n”;

Codeword out_reversed = first_codeword[length];

out_reversed.reverse();

out_reversed = out_reversed >> (MAX_CODEWORD_LENGTH - length);

// std::cout << out_reversed.to_string(2) << ”\n”;

encoding[i] = (out_reversed << CODEWORD_LENGTH_BITS) + length;

first_codeword[length]++;

} else {

encoding[i] = 0;

}

}

}

Figure 11.13:  The complete code for generating the canonical Huffman
codewords for each of the symbols. The codewords can be computed with
knowledge of number of bits that each symbol uses (stored in the input array
symbol_bits[]). Additionally, we have another input array
codeword_length_histogram[] which stores at each entry the number of symbols
with codewords at that bit length. The output is the code word for each symbol
stored in the encoding[] array.

In the code in Figure 11.13, the inputs actually contain some redundant
information. In particular, we could compute the number of symbols for each
bit length stored in codeword_length_histogram[] from the length of each
codeword symbol_bits[] using a histogram computation. Instead, in this code
we’ve chosen to reuse the histogram originally computed in the truncate_tree()
function. Instead we could save the storage by recomputing the histogram. Do
you think this is a good tradeoff? How many resources are required to compute
the histogram in this function? How many resources are required to communicate
the histogram through the pipeline?

Estimate the latency of the code in Figure 11.13

Let us now go through our running example and show how this is used to derive
the initial codewords. In the example, the symbols A, D, and E have two bits
for their encoding; symbol C has three bits; and symbols B and F have four
bits. Thus, we have:

$\begin{array}[]{lcl}\mathrm{bit\\_length}(1)&=&0\\\
\mathrm{bit\\_length}(2)&=&3\\\ \mathrm{bit\\_length}(3)&=&1\\\
\mathrm{bit\\_length}(4)&=&2\\\ \end{array}$ (11.4)

Using Equation 11.3 to calculate the values of first_codeword, we determine:

$\begin{array}[]{lllll}\mathrm{first\\_codeword}(1)&=&0&=&\mathrm{0b0}\\\
\mathrm{first\\_codeword}(2)&=&(0+0)<<1&=&\mathrm{0b00}\\\
\mathrm{first\\_codeword}(3)&=&(0+3)<<1&=&6=\mathrm{0b110}\\\
\mathrm{first\\_codeword}(4)&=&(6+1)<<1&=&14=\mathrm{0b1110}\\\ \end{array}$
(11.5)

Once we have determined these values, then consider each symbol in order from
smallest to largest. For each symbol, we determine the length of its codeword
and assign the next codeword of the appropriate length. In the running
example, we consider symbols A, B, C, D, E, and F in alphabetical order. The
symbol A has two bits for its encoding. We perform a lookup into
first_codeword[2] = 0. Thus we assign the codeword for A to 0b00. We increment
the value at first_codeword[2] to $1$. The symbol B has four bits. Since
first_codeword[4] = 14 = 0b1110, it gets assigned the codeword 0b1110. Symbol
C has three bits. The value of first_codeword[3] = 6 = 0b110, thus it gets the
codeword 110. Symbol D has two bits so it gets first_codeword[2] = 1 = 0b01;
remember that we incremented this value after we assigned the codeword to
symbol A. Symbol E has two bits so it gets the codeword 0b01 + 1 = 0b10. And F
has four bits so it gets the codeword 0b1110 + 1 = 0b1111.

The final codewords for all of the symbols are:

$\begin{array}[]{lll}\texttt{A}&\rightarrow&00\\\
\texttt{B}&\rightarrow&1110\\\ \texttt{C}&\rightarrow&110\\\
\texttt{D}&\rightarrow&01\\\ \texttt{E}&\rightarrow&10\\\
\texttt{F}&\rightarrow&1111\\\ \end{array}$ (11.6)

####  11.2.8 Testbench

The final part of the code is the testbench. This is shown in Figure 11.14.
The general structure is to read the input frequency values from a file,
process them using the huffman_encoding function, and compare the resulting
codewords with an existing golden reference that is stored in a file.

⬇

#include ”huffman.h”

#include <stdio.h>

#include <stdlib.h>

void file_to_array(const char *filename, ap_uint<16> *&array, int
array_length) {

printf(”Start␣reading␣file␣[%s]\n”, filename);

FILE *file = fopen(filename, ”r”);

if(file == NULL) {

printf(”Cannot␣find␣the␣input␣file\n”);

exit(1);

}

int file_value = 0;

int count = 0;

array = (ap_uint<16> *) malloc(array_length*sizeof(ap_uint<16>));

while(1) {

int eof_check = fscanf(file, ”%x”, &file_value);

if(eof_check == EOF) break;

else {

array[count++] = (ap_uint<16>) file_value ;

}

}

fclose(file);

if(count != array_length) exit(1);

}

int main() {

printf(”Starting␣canonical␣Huffman␣encoding␣testbench\n”);

FILE *output_file;

int return_val = 0;

ap_uint<16> *frequencies = NULL;

file_to_array(”huffman.random256.txt”, frequencies, INPUT_SYMBOL_SIZE);

Symbol in[INPUT_SYMBOL_SIZE];

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

in[i].frequency = frequencies[i];

in[i].value = i;

}

int num_nonzero_symbols;

⬇

PackedCodewordAndLength encoding[INPUT_SYMBOL_SIZE];

huffman_encoding(in, encoding, &num_nonzero_symbols);

output_file = fopen(”huffman.random256.out”, ”w”);

for(int i = 0; i < INPUT_SYMBOL_SIZE; i++)

fprintf(output_file, ”%d,␣%x\n”, i, (unsigned int) encoding[i]);

fclose(output_file);

printf (”\n***************Comparing␣against␣output␣data***************␣\n\n”);

if (system(”diff␣huffman.random256.out␣huffman.random256.golden”)) {

fprintf(stdout, ”*******************************************\n”);

fprintf(stdout, ”FAIL:␣Output␣DOES␣NOT␣match␣the␣golden␣output\n”);

fprintf(stdout, ”*******************************************\n”);

return_val = 1;

} else {

fprintf(stdout, ”*******************************************\n”);

fprintf(stdout, ”␣PASS:␣The␣output␣matches␣the␣golden␣output\n”);

fprintf(stdout, ”*******************************************\n”);

return_val = 0;

}

printf(”Ending␣canonical␣Huffman␣encoding␣testbench\n”);

return return_val;

}

Figure 11.14:  The complete code for the canonical Huffman encoding testbench.
The code initializes the in array with data from an input file. It passes that
into the top huffman_encoding function. Then it stores the resulting codewords
into a file, and compares that with another golden reference file. It prints
out the results of the comparison, and returns the appropriate value.

The main() function starts by setting up the variables required to read the
frequencies from a file (in this case the file is huffman.random256.txt) and
puts them into in[]. This is done in the file_to_array function, which takes
as input the filename for the input data and the length of the data
(array_length), and stores the entries in that file into array[] variable.
This file contains the frequency of each symbol. Frequency values are stored
in symbol order, thus the first value of the file represents the frequency of
symbol ’0’, and so on.

The main() function continues by initializing in[] using the frequencies from
the file. It then calls the top huffman_encoding function. The function
returns the encoded symbol values in encoding[]. Since the result of
processing should be a prefix code, we check that the properties of a prefix
code are actually satisfied. The result is then compared to the codewords
stored in a golden reference, which is stored in the file
huffman.random256.gold. We do this by writing the result to a file named
random256.out and performing a file comparison using the diff tool. The diff
tool returns ’0’ if the files are identical and non-zero if the files are
different. Thus, the if condition occurs when the files are different, and the
else condition is executed when the files are the same. In both cases, we
print out a message and set the return_val to the appropriate value. This
return value is used by the Vivado® HLS tool during cosimulation to check the
correctness of results. The return value should be ’0’ if it passes, and non-
zero if it does not pass.

###  11.3 Conclusion

Huffman Coding is a common type of data compression used in many applications.
While encoding and decoding using a Huffman code are relatively simple
operations, generating the Huffman code itself can be a computationally
challenging problem. In many systems it is advantageous to have relatively
small blocks of data, implying that new Huffman codes must be created often,
making it worthwhile to accelerate.

Compared to other algorithms we’ve studied in this book, creating a Huffman
code contains a number of steps with radically different code structures. Some
are relatively easy to parallelize, while others are more challenging. Some
portions of the algorithm naturally have higher $\mathcal{O}(n)$ complexity,
meaning that they must be more heavily parallelized to achieve a balanced
pipeline. However, using the dataflow directive in Vivado® HLS, these
different code structures can be linked together relatively easily

## References

  * Abdelhadi and Lemieux [2014] Ameer M.S. Abdelhadi and Guy G.F. Lemieux.  Modular multi-ported SRAM-based memories.  In _Proceedings of the International Symposium on Field Programmable Gate Arrays (FPGA)_ , pages 35–44. ACM, 2014.  ISBN 978-1-4503-2671-1.  doi: 10.1145/2554688.2554773.  URL http://doi.acm.org/10.1145/2554688.2554773.
  * Acc [2017] _SystemC_.  Accellera, 2.3.2 edition, October 2017.  URL http://www.accellera.org/downloads/standards/systemc.
  * Ahmed et al. [1982] Hassan M. Ahmed, Jean-Marc Delosme, and Martin Morf.  Highly concurrent computing structures for matrix arithmetic and signal processing.  _IEEE Computer_ , 15(1):65–82, 1982.
  * Andraka [1996] Raymond J. Andraka.  Building a high performance bit-serial processor in an FPGA.  In _Proceedings of Design SuperCon_ , volume 96, pages 1–5, 1996\.
  * Arcas-Abella et al. [2014] Oriol Arcas-Abella et al.  An empirical evaluation of high-level synthesis languages and tools for database acceleration.  In _Proceedings of the International Field Programmable Logic and Applications Conference (FPL)_ , pages 1–8. IEEE, 2014.
  * ARM [2013] _AMBA AXI and ACE Protocol Specification_.  ARM Limited, v1.0 edition, 2013.  URL http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ihi0022e/index.html.  ARM IHI 0022E.
  * Bayer [1976] Bryce E. Bayer.  Color imaging array, July 1976.  US 3971065.
  * Bayliss and Constantinides [2012] Samuel Bayliss and George A. Constantinides.  Optimizing SDRAM bandwidth for custom FPGA loop accelerators.  In _Proceedings of the International Symposium on Field Programmable Gate Arrays (FPGA)_ , pages 195–204. ACM, February 2012.
  * Bednara et al. [2000] Marcus Bednara et al.  Tradeoff analysis and architecture design of a hybrid hardware/software sorter.  In _Proceedings of the International Conference on Application-specific Systems, Architectures and Processors (ASAP)_ , pages 299–308. IEEE, 2000.
  * Betz and Rose [1997] Vaughn Betz and Jonathan Rose.  VPR: A new packing, placement and routing tool for FPGA research.  In _Proceedings of the International Field Programmable Logic and Applications Conference (FPL)_ , pages 213–222. Springer, 1997.
  * Blelloch [1990] Guy E. Blelloch.  Prefix sums and their applications.  Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University, November 1990.
  * Brown and Rose [1996] Stephen Brown and Jonathan Rose.  FPGA and CPLD architectures: A tutorial.  _IEEE Design and Test of Computers_ , 13(2):42–57, 1996.
  * Canis et al. [2011] Andrew Canis, Jongsok Choi, Mark Aldham, Victor Zhang, Ahmed Kammoona, Jason H Anderson, Stephen Brown, and Tomasz Czajkowski.  LegUp: high-level synthesis for FPGA-based processor/accelerator systems.  In _Proceedings of the International Symposium on Field Programmable Gate Arrays (FPGA)_ , pages 33–36. ACM, 2011.
  * Chen et al. [2012] Jianwen Chen, Jason Cong, Ming Yan, and Yi Zou.  FPGA-accelerated 3D reconstruction using compressive sensing.  In _Proceedings of the International Symposium on Field Programmable Gate Arrays (FPGA)_ , pages 163–166. ACM, 2012.
  * Cong et al. [2011] Jason Cong, Bin Liu, Stephen Neuendorffer, Juanjo Noguera, Kees Vissers, and Zhiru Zhang.  High-level synthesis for fpgas: From prototyping to deployment.  _IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems (TCAD)_ , 30(4):473–491, 2011.
  * Cooley and Tukey [1965] James W. Cooley and John W. Tukey.  An algorithm for the machine calculation of complex fourier series.  _Mathematics of Computation_ , 19(90):297–301, 1965.  ISSN 00255718.  URL http://www.jstor.org/stable/2003354.
  * Cormen et al. [2009] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  _Introduction to Algorithms, Third Edition_.  MIT Press, 3rd edition, 2009.  ISBN 0262033844, 9780262033848.
  * Coussy and Morawiec [2010] Philippe Coussy and Adam Morawiec.  _High-level synthesis_ , volume 1.  Springer, 2010.
  * Dai et al. [2017] Steve Dai, Ritchie Zhao, Gai Liu, Shreesha Srinath, Udit Gupta, Christopher Batten, and Zhiru Zhang.  Dynamic hazard resolution for pipelining irregular loops in high-level synthesis.  In _Proceedings of the International Symposium on Field Programmable Gate Arrays (FPGA)_ , pages 189–194, 2017.  ISBN 978-1-4503-4354-1.  doi: 10.1145/3020078.3021754.  URL http://doi.acm.org/10.1145/3020078.3021754.
  * Dean and Ghemawat [2008] Jeffrey Dean and Sanjay Ghemawat.  MapReduce: Simplified data processing on large clusters.  _Communications of the ACM_ , 51(1):107–113, January 2008.  ISSN 0001-0782.  doi: 10.1145/1327452.1327492.  URL http://doi.acm.org/10.1145/1327452.1327492.
  * Despain [1974] Alvin M. Despain.  Fourier transform computers using CORDIC iterations.  _IEEE Transactions on Computers_ , 100(10):993–1001, 1974.
  * Detrey and de Dinechin [2007] J. Detrey and F. de Dinechin.  Floating-point trigonometric functions for FPGAs.  In _Proceedings of the International Field Programmable Logic and Applications Conference (FPL)_ , pages 29–34, August 2007.  doi: 10.1109/FPL.2007.4380621.
  * Deutsch [1996] L Peter Deutsch.  DEFLATE compressed data format specification version 1.3.  1996\.
  * Duprat and Muller [1993] Jean Duprat and Jean-Michel Muller.  The CORDIC algorithm: new results for fast VLSI implementation.  _IEEE Transactions on Computers_ , 42(2):168–178, 1993.
  * Flannery et al. [1992] Brian P. Flannery, William H. Press, Saul A. Teukolsky, and William Vetterling.  _Numerical recipes in C_.  Press Syndicate of the University of Cambridge, New York, 1992.
  * Gajski et al. [2012] Daniel D. Gajski, Nikil D. Dutt, Allen C.H. Wu, and Steve Y.L. Lin.  _High-Level Synthesis: Introduction to Chip and System Design_.  Springer Science & Business Media, 2012.
  * Gentleman and Sande [1966] W Morven Gentleman and Gordon Sande.  Fast fourier transforms: for fun and profit.  In _Proceedings of the November 7-10, 1966, fall joint computer conference_ , pages 563–578. ACM, 1966.
  * George et al. [2014] Nivia George, HyoukJoong Lee, David Novo, Tiark Rompf, Kevin J. Brown, Arvind K. Sujeeth, Martin Odersky, Kunle Olukotun, and Paolo Ienne.  Hardware system synthesis from domain-specific languages.  In _Proceedings of the International Field Programmable Logic and Applications Conference (FPL)_ , pages 1–8. IEEE, 2014.
  * Gupta et al. [2004] Sumit Gupta, Rajesh Gupta, Nikil Dutt, and Alexandru Nicolau.  _SPARK: A Parallelizing Approach to the High-level Synthesis of Digital Circuits_.  Kluwer, 2004.  ISBN 1-4020-7837-4.
  * Hauck and DeHon [2010] Scott Hauck and Andre DeHon.  _Reconfigurable computing: the theory and practice of FPGA-based computation_ , volume 1.  Morgan Kaufmann, 2010.
  * Hegarty et al. [2016] James Hegarty, Ross Daly, Zachary DeVito, Jonathan Ragan-Kelley, Mark Horowitz, and Pat Hanrahan.  Rigel: Flexible multi-rate image processing hardware.  _ACM Trans. Graph._ , 35(4):85:1–85:11, July 2016\.  ISSN 0730-0301.  doi: 10.1145/2897824.2925892.  URL http://doi.acm.org/10.1145/2897824.2925892.
  * Heideman et al. [1984] M. Heideman, D. Johnson, and C. Burrus.  Gauss and the history of the fast fourier transform.  _ASSP Magazine, IEEE_ , 1(4):14–21, October 1984\.  ISSN 0740-7467.  doi: 10.1109/MASSP.1984.1162257.
  * Huffman [1952] David A. Huffman.  A method for the construction of minimum-redundancy codes.  _Proceedings of the IRE_ , 40(9):1098–1101, 1952\.
  * Kastner et al. [2010] Ryan Kastner, Anup Hosangadi, and Farzan Fallah.  _Arithmetic optimization techniques for hardware and software design_.  Cambridge University Press, 2010.
  * Knapp [1996] David Knapp.  _Behavioral Synthesis: Digital System Design using the Synopsys Behavioral Compiler_.  Prentice-Hall, 1996.  ISBN 0-13-569252-0.
  * Knuth [1998] Donald Ervin Knuth.  _The art of computer programming: sorting and searching_ , volume 3.  Pearson Education, 1998.
  * Laforest et al. [2014] Charles Eric Laforest, Zimo Li, Tristan O’rourke, Ming G. Liu, and J. Gregory Steffan.  Composing multi-ported memories on FPGAs.  _ACM Transactions on Reconfigurable Technology and Systems (TRETS)_ , 7(3):16:1–16:23, September 2014.  ISSN 1936-7406.  doi: 10.1145/2629629.  URL http://doi.acm.org/10.1145/2629629.
  * Langdon Jr et al. [1990] Glen G. Langdon Jr, Joan L. Mitchell, William B. Pennebaker, and Jorma J. Rissanen.  Arithmetic coding encoder and decoder system, February 27 1990.  US Patent 4,905,297.
  * Lee et al. [2014] Dajung Lee, Janarbek Matai, Brad Weals, and Ryan Kastner.  High throughput channel tracking for JTRS wireless channel emulation.  In _Proceedings of the International Field Programmable Logic and Applications Conference (FPL)_. IEEE, 2014.
  * Lee and Messerschmitt [1987] Edward A. Lee and David G. Messerschmitt.  Pipeline interleaved programmable DSPs: Architecture.  _IEEE Transactions on Acoustics, Speech, and Signal Processing (TASSP)_ , 35(9):1320–1333, September 1987.
  * Lee and Varaiya [2011] Edward A. Lee and Pravin Varaiya.  _Structure and Interpretation of Signals and Systems, Second Edition_.  2011\.  ISBN 0578077191.  URL LeeVaraiya.org.
  * Lee [2017] Edward Ashford Lee.  _Plato and the Nerd: The Creative Partnership of Humans and Technology_.  MIT Press, 2017.  ISBN 978-0262036481.
  * Leiserson et al. [1993] C. Leiserson, F. Rose, and J. Saxe.  Optimizing synchronous circuitry by retiming.  In _Third Caltech Conference On VLSI_ , 1993.
  * Liu et al. [2017] G. Liu, M. Tan, S. Dai, R. Zhao, and Z. Zhang.  Architecture and synthesis for area-efficient pipelining of irregular loop nests.  _IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems (TCAD)_ , 36(11):1817–1830, November 2017\.  ISSN 0278-0070.  doi: 10.1109/TCAD.2017.2664067.
  * Marcelino et al. [2008] Rui Marcelino et al.  Sorting units for FPGA-based embedded systems.  In _Distributed Embedded Systems: Design, Middleware and Resources_ , pages 11–22. Springer, 2008.
  * Matai et al. [2012] Janarbek Matai, Pingfan Meng, Lingjuan Wu, Brad T Weals, and Ryan Kastner.  Designing a hardware in the loop wireless digital channel emulator for software defined radio.  In _Proceedings of the International Conference on Field-Programmable Technology (FPT)_. IEEE, 2012.
  * Matai et al. [2014a] Janarbek Matai, Joo-Young Kim, and Ryan Kastner.  Energy efficient canonical huffman encoding.  In _Proceedings of the International Conference on Application-specific Systems, Architectures and Processors (ASAP)_. IEEE, 2014a.
  * Matai et al. [2014b] Janarbek Matai, Dustin Richmond, Dajung Lee, and Ryan Kastner.  Enabling FPGAs for the masses.  _arXiv preprint arXiv:1408.5870_ , 2014b.
  * Matai et al. [2016] Janarbek Matai, Dustin Richmond, Dajung Lee, Zac Blair, Qiongzhi Wu, Amin Abazari, and Ryan Kastner.  Resolve: Generation of high-performance sorting architectures from high-level synthesis.  In _Proceedings of the International Symposium on Field Programmable Gate Arrays (FPGA)_ , pages 195–204. ACM, 2016.  ISBN 978-1-4503-3856-1.  doi: 10.1145/2847263.2847268.  URL http://doi.acm.org/10.1145/2847263.2847268.
  * Mead and Conway [1980] Carver Mead and Lynn Conway.  _Introduction to VLSI systems_ , volume 1080.  Addison-Wesley Reading, MA, 1980.
  * Micheli [1994] Giovanni De Micheli.  _Synthesis and optimization of digital circuits_.  McGraw-Hill Higher Education, 1994.
  * Mirzaei et al. [2007] Shahnam Mirzaei, Anup Hosangadi, and Ryan Kastner.  FPGA implementation of high speed fir filters using add and shift method.  In _Computer Design, 2006. ICCD 2006. International Conference on_ , pages 308–313. IEEE, 2007.
  * MISRA [2013] MISRA.  _Guidelines for the Use of the C Language in Critical Systems_.  March 2013.  ISBN 978-1-906400-10-1.  URL https://www.misra.org.uk.
  * Mueller et al. [2012] Rene Mueller et al.  Sorting networks on FPGAs.  _The VLDB Journal—The International Journal on Very Large Data Bases_ , 21(1):1–23, 2012.
  * Ortiz et al. [2011] Jorge Ortiz et al.  A streaming high-throughput linear sorter system with contention buffering.  _International Journal of Reconfigurable Computing_ , 2011.
  * Papaefthymiou [1991] Marios C. Papaefthymiou.  Understanding retiming through maximum average-weight cycles.  In _SPAA ’91: Proceedings of the third annual ACM symposium on Parallel algorithms and architectures_ , pages 338–348, 1991.
  * Pennebaker [1992] William B. Pennebaker.  _JPEG: Still image data compression standard_.  Springer, 1992.
  * Sedgewick [2001] Robert Sedgewick.  _Algorithms in C_.  Addison-Wesley, 2001.  ISBN 978-0201756081.
  * Sherigar and Ramanujan [2004] Bhaskar Sherigar and Valmiki K. Ramanujan.  Huffman decoder used for decoding both advanced audio coding (AAC) and MP3 audio, June 29 2004.  US Patent App. 10/880,695.
  * Winterstein et al. [2013] F. Winterstein, S. Bayliss, and G. A. Constantinides.  High-level synthesis of dynamic data structures: A case study using Vivado HLS.  In _Proceedings of the International Symposium on Field Programmable Gate Arrays (FPGA)_ , pages 362–365, December 2013.  doi: 10.1109/FPT.2013.6718388.
  * Witten et al. [1987] Ian H. Witten, Radford M. Neal, and John G. Cleary.  Arithmetic coding for data compression.  _Communications of the ACM_ , 30(6):520–540, 1987\.
  * Xil [2017a] _UltraScale Architecture Configurable Logic Block (UG574)_.  Xilinx, v1.5 edition, February 2017a.  URL https://www.xilinx.com/support/documentation/user_guides/ug574-ultrascale-clb.pdf.
  * Xil [2017b] _Vivado Design Suite User Guide: High-Level Synthesis (UG902)_.  Xilinx, v2017.1 edition, April 2017b.  URL https://www.xilinx.com/support/documentation/sw_manuals/xilinx2017_1/ug902-vivado-high-level-synthesis.pdf.
  * Xil [2017c] _UltraScale Architecture Configuration (UG570)_.  Xilinx, v1.7 edition, March 2017c.  URL https://www.xilinx.com/support/documentation/user_guides/ug570-ultrascale-configuration.pdf.

## Glossary

array partitioning

    Dividing a single logical array into multiple physical memories.
bitstream

    The configuration data used to program the functionality of an FPGA
IP core

    An RTL-level component with well-defined interfaces enabling it to be incorporated into a larger design. Often used as a way of hiding the ‘intellectual property’ from another company, hence the name.
C/RTL cosimulation

    The process of verifying an design generated by HLS using testvectors captured from the C testbench.
data rate

    The frequency at which a task can process the input data. This is often expressed in bits/second and thus also depends on the size of the input data
finite impulse response

    A common digital signal processing task that performs a convolution on the input signal with a fixed signal that is defined by its coefficients. The FIR is often performed in hardware and can be efficiently implemented
I/O block

    An I/O block provides the interface between the FPGA fabric and the remainder of the system. I/O blocks can talk to memories (e.g., on-chip caches and off-chip DRAM, microprocessors (using AXI or other protocols), sensors, actuators, etc..
loop interchange

    A code transformation that changes the order of loop operations. This transformation is often a useful approach to addressing recurrences in code.
loop pipelining

    Enabling multiple iterations of a loop to run concurrently sharing the same functional units.
netlist

    An intermediate design artifact consisting of device-level primitive elements and the connections between them. In FPGA designs, the primitive elements include ,, and .
partial loop unrolling

    A transformation where the body of a loop is replicated multiple times. This is often used in processor systems to reduce loop condition overhead or to provide opportunities for vectorization. In HLS, it can have a similar effect, enabling more operations from the same loop nest to be considered in scheduling. This can improve the performance of a design.
process

    An individual component in a dataflow architecture
recurrence

    A code structure that results in a feedback loop when implemented in a circuit. Recurrences limit the throughput of the circuit.
routing channel

    A routing channel provides a flexible set of connections between the FPGA programmable logic elements.
slice

    A (typically small) set of , and multiplexors. These are often reported in resource utilization reports.
sorting cell

    An simple stateful component that forms part of a larger sorting network or algorithm. Commonly a cell performs a compare-and-swap operation between two elements.
stable sort

    A sorting algorithm that keeps different elements with the same sorting key in their original sequence after sorting.
switchbox

    A switchbox connects routing channel s to provide a flesible routing structure for data routed between the programmable logic and .
logic synthesis

    The process of converting an glsrtl design into a netlist of device-level primitives.
systolic array

    An array of processing elements that coordinate to perform a more complex algorithm. Systolic arrays are usually designed so that each processing element encapsulates some local information and only communicates with its local neighbors. This often enables systolic arrays to easily scale to large problem sizes by increasing the size of the array.
task interval

    The time between when one task starts and the next starts or the difference between the start times of two consecutive tasks
task latency

    The time between when a task starts and when it finishes
task

    A fundamental atomic unit of behavior or high-level synthesis computation; this corresponds to a function invocation in high-level synthesis
task pipelining

    Being able to execute more than one task concurrently on the same accelerator in a pipelined fashion.

## Acronyms

BRAM

    block RAM
CRS

    compressed row storage
DFT

    Discrete Fourier Transform
EDA

    electronic design automation
FF

    flip-flop
FFT

    Fast Fourier Transform
FPGA

    field-programmable gate array
HLS

    high-level synthesis
LUT

    lookup table
PAR

    place and route
PE

    Processing Element
ROM

    Read-only Memory
RTL

    register-transfer level
SSA

    static single assigment