AXI Stream Compressor

Inspired by a project I did for a job interview. I've deliberately obscured the code to protect their privacy.

Purpose

The purpose of this module is to take in streaming data, compress it, and feed the results to a streaming output. Each streaming data element consits of:

A floating width field, up to FLOATING_FIELD_MAX width delimited by FLOATING_FIELD_DELIMITER.
A fixed width field, which can have multiple fields within it but must always be the same number of bytes.

For example, a baseball statistic stream element might have a name, Batting Average, At-Bats, Hits, Walks, Doubles, Triples and Home Runs. The name is floating width because players will of course have different length names. The rest of the statistics are static widths.

Name	Avg	AB	H	BB	2B	3B	HR	K	SB
Char[16]	16-bits	16-bits	16-bits	16-bits	8-bits	8-bits	8-bits	16-bits	8-bits
Don Mattingly	0.332	512	170	41	30	7	7	75	12
Ken Griffey	0.300	512	154	12	23	4	8	75	12
Chipper Jones	0.281	512	144	77	21	2	18	75	13
Dave Winfield	0.304	500	154	6	4	19	40	75	13

An entry might be represented as:

Name													Delim	AVG		AB		H		BB		3B
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
'D'	'o'	'n'	' '	'M'	'a'	't'	't'	'i'	'n'	'g'	'l'	'y'	0x2c	0x1	0x4c	0x00	0xaa	0x0	0x2C	0x0	0x1E	0x0	0x28	0x1F	0	0x4b	0xC

Data was passed in an 8-bit bus, packed and unaligned. This means that the first entry might start on byte 0 but if it were, say, 22 bytes long, the second entry would start on byte 22 (or byte 6 of the fourth bus cycle). So some level of multiplexing was necessary to get the bits into the compressor.

Discussion

There are some obvious points where we could optimize to reduce size of the message:

Assuming the names are Alphanumerics and spaces (and not part of an extended character space), there are 53 characters (capital and lowercase letters and spaces) we have to be concerned with.
Assuming each and only the first letter of every name is capitalized, we can reduce our space to 27 characters which fits into one 5-bit character.
Batting average can be collapsed since we can recompute that from H/AB.

The challenges here are:

The data is not coming in aligned on any boundary. The Name, Avg, or floating field delimiter could come at any of the input bytes. Bytes will likely need to be shifted before being input to a compression mechanism.
The data is an indefinite length.

Approach

My original approach was to implement two 64-deep fifos- one for input and one for output- and attempt to process the data "in flight". This approach to several issues:

To find the delimiter byte I needed comparators in each of my FIFO bytes. This made the logic (and the routing) much more difficult.
Since I had to do byte packing and the bytes I needed to pack could be at FIFO element 1 or FIFO element 62, I either needed:
- A lot of multiplexing to move data into my compression logic from any of 64 FIFO elements -OR-
- Redundant compression logic.

Throughout the exercise I assumed I had to processes the data at the input clock rate; (i.e. I couldn't have a clock running at a higher rate to "subprocess" the data).
For my second attept I decided to make a design with a multi-element receiver. Each Stream element holds one entry from above. A token is passed from each stream element to the next as the element's data arrives.
For Design Verification I rely on Verilator, which in my experience has faster compile and simulation performance than xsim/xelab.

For example, upon reset, Stream Element 0 holds the token. Suppose there are three stream entries coming in:

First Entry: A 25 byte element: Variable field is bytes 0-6, the delimiter at byte 7, and bytes 8-24 being the fixed data.
Second Entry: A 27 byte element: Variable field is bytes 0-8, the delimiter at byte 9, and bytes 10-26 being the flxed data.
Third Entry: A 19 byte element: Variable field is byte 0, the delimiter at byte 1, and bytes 2-18 being the fixed length data.

The rough sequence of events is (starting with Stream element 0 holding the token):

Cycle 1: DataIn contains First Entry [7:0] captured by Stream Element 0 Bank 0 and Stream Element 1 Bank 0.
Cycle 2: DataIn contains First Entry [15:8] captured by Stream Element 0 Bank 1. Delimiter discovered at Byte 7. Stream Element 1 Bank 0 also captures that data.
Cycle 3: DataIn contains First Entry [23:16] captured by Stream Element 0 Bank 2. Stream element 1 Bank 0 also captures that data..
Cycle 4: DataIn contains First Entry [24] (byte 0) and Second Entry[6:0] (bytes 7-1). Captured by Stream Element 0 Bank 3. Stream element 1 Bank 0 also captures that data. Token and Starting Byte (1) passed from Stream Element 0 to Stream Element 1
Cycle 5: DataIn contains Second Entry[14:7]. Stream Element 1 Bank 1 captures dataIn. Stream Element 0 indicates to compressor that it has data.
Cycle 6: DataIn contains Second Entry[22:15]. Stream Element 1 Bank 2 captures dataIn. Delimiter discovered at Byte 7. Compressor acknowledges Stream Element 0's data. Stream Element 0 returns to idle.
Cycle 7: DataIn contains Second Entry[26:23](bytes 3:0) and Third Entry[3:0] (bytes7:4). Stream Element 1 Bank 3 captures dataIn as does Stream Element 2 Bank 0. Token passed from Stream Element 1 to Stream Element 2 along with Start Byte (4).
Cycle 8... Since Stream Element 1 received its data offset by 1 byte it needs to shift down by 1. It will then present its data to the compressor. Stream Element 2 will capture the data for the third entry and shift down by 4 once it completes.

Once data is compressed, it is routed to a return FIFO which outputs the data.

Source

Github Source

Compilation Parameters

DATA_BYTE_WIDTH	Maximum byte width taken in the streaming interface at once
ALGORITHM_SELECTED	Algorithm to be ifdef-compied in.
VARIABLE_FIELD_DELIMITER	ASCII Value of Delimiter to detect end of floating field.
VARIABLE_FIELD_MAX_BYTES	Maximum VARIABLE_FIELD length (not including delimiter)
FIXED_FIELD_MAX_BYTES	Byte Width of Fixed Field

Design Verification Plan

Obviously since this is a hobby/demo project I did not do a full-scale DV effort. Such an effort would involve adding the following points:

Verifying across multiple data-widths and Fixed-field widths.
Verifying all algorithms.
Integration of Verilator model with interfacing system software so that it may be tested before being synthesized.

This would become part of a Jenkins/Kubernetes environment which would run nightly as part of CI/CD.

Timing and Logic Levels

So far the best results I've been able to achieve are about 9 ns. This is with the ZYNQ processor which has a slower process.

Next Steps

Generify input interface to be AXI rather than a continuous stream. This would involve adding FRAME ends.