HopliteBuf Analytical Bounds Tool

We provide Python, MATLAB/Octave, and shell scripts that help system engineers certify communicating applications running on the HopliteBuf NoC. The scripts can also regenerate plots from the HopliteBuf FPGA 2019 paper.

Public-release scope: this repository contains analytical software and published simulation data only. Hoplite router RTL is not included and is not licensed for public release.

Tushar Garg, Saud Wasly, Rodolfo Pellizzoni, and Nachiket Kapre

"HopliteBuf: FPGA NoCs with Provably Stall-Free FIFOs",

International Symposium on Field-Programmable Gate Arrays, Feb 2019

How to use the tool:

Installation dependencies

On macOS:

brew install octave parallel
python3 -m pip install -r requirements.txt

On Linux, install Python 3 and GNU Octave through your package manager, then run the same pip command. GNU Parallel is only required for the sweep scripts.

Generating a Network Specification:

To compute buffer and latency bounds, supply a specification of the communication workload. This simple plaintext format captures source-destination pairs, flow rates, and burst properties.

For a 2x2 NoC with 4 flows, the flow.dat file will look as shown below:

sX, sY, dX, dY, B,  R
0,  0,  0,  1,  1,      0.250000
0,  1,  1,  1,  1,      0.050000
1,  0,  1,  1,  1,      0.150000
1,  1,  0,  0,  1,      0.200000

In this file, we have a set of four flows with source address sx,sy and destination address dx,dy on a 2D torus. For each flow, we need to know flow properties such as Burst and Rate which are the next two entries in the row. It is possible to have multiple flows originating at the same source sx,sy with different destinations dx1,dy1, dx2, dy2, ... but that requires a careful analysis of regulator implementations (per flow, or unified). For simplicity of this tutorial, we currently assume a single flow from a given source.

For generating the plots in the paper, we synthetically generate various flow sets. That requires a different script gennoc.py as explained below. To understand how it works type: ./gennoc.py -h which produces the text message as shown below.

./gennoc.py -h
usage: gennoc.py [-h] [-o output] [-p Rate] [-t TrafficType] [-f flows]
                 [-b bursts]
                 Width Height

NoC Traffic Generator

positional arguments:
  Width           the Width of the NoC
  Height           the Height of the NoC

optional arguments:
  -h, --help      show this help message and exit
  -o output       the map file
  -p Rate         override the rate of all the flows, default = random (1/m^2,
                  0.5)
  -t TrafficType  set the traffic type => {random, all2one, all2row,
                  all2column}: default = random
  -f flows        the maximum number of different flows per node
  -b bursts       the maximum number of burstiness per flow

Running The Analysis:

After capturing the network flow properties, run the analysis to compute buffer and latency bounds.

The file analyze.py handles the HopliteBuf: W->S architecture. It processes flow.dat for the supplied system size and identifies the flows that interfere at each switch in a HopliteBuf 2D torus using dimension-ordered routing.

$ ./analyze.py -h
usage: analyze.py [-h] -N NxN [-f flowset file] [-B burst info] [-R rate info]

NoC Traffic Analyzer

optional arguments:
  -h, --help       show this help message and exit
  -N NxN           the size of the NoC
  -f flowset file  a file containing a list of flows
  -B burst info    burst, by default reads from input file
  -R rate info     rate, by default reads from input file

In a similar way, the file analyze_dualbuffer.py is used for HopliteBuf: W->S+N architecture and it will process your flow.dat for a supplied system size to compute which set of flows will interfere at each switch in the network.

$ ./analyze_dualbuffer.py -h
usage: analyze_dualbuffer.py [-h] -N NxN [-f flowset file] [-B burst info] [-R rate info]

NoC Traffic Analyzer

optional arguments:
  -h, --help       show this help message and exit
  -N NxN           the size of the NoC
  -f flowset file  a file containing a list of flows
  -B burst info    burst, by default reads from input file
  -R rate info     rate, by default reads from input file

For both these files, the switch -N for size of the NoC is a required parameter to run this script. The remaining parameters are optional. The optional Burst -B and Rate -R arguments override the values in flow.dat. When supplied, each flow uses the same override values.

The script will generate a set of burst and rate information for each switch in the network and generate files w_rm_*.csv, w_bm_*.csv, pe_rm_*.csv,pe_bm_*.csv These files are read by the core MATLAB/Octave analysis routines in top_extract_all.m. The Python analysis script invokes this Octave stage automatically.

The analysis will generate the following files:

1. buffer.csv with FIFO sizes for each x,y position in the NoC,
2. stable.csv that tells us whether each flow is stable or now. Flows are unstable if they cause any traversal link to require >100% bandwidth utilization. If you have a system with a fixed-size FIFO in each switch, you can filter this further by checking buffer.csv and identifying if any entry >FIFOSIZE and eliminate those flows.
3. inflight.csv and total.csv latency files for each column in the torus that capture per-flow latency information.

Analysis Instructions for W->S buffer design

To run the analysis, you have to run the following set of steps:

1. To run the default example just type the following on the terminal

$ ./analyze.py -N 2 -f flow.dat
Calling Octave script to run analysis
Stable=1, Max FIFO=1, WC Latency=16

2. You can override the rate and burst specification in flow.dat by using the -b and -r parameters. In this example, we are using a 2x2 NoC and a rate of 0.08 and burst of 2.

$ ./analyze.py -N 2 -f flow.dat -R 0.08 -B 2
Calling Octave script to run analysis
Stable=1, Max FIFO=2, WC Latency=20

First, we note that the analysis is stable -> no links are overutilized. Second, note that the buffer size has now increased to 2 due to a flow burst of length 2. If you know that you have a budget of certain maximum number of FIFO slots, you can use the "Max FIFO size" field to filter out cases that are not supported by your NoC configuration.

3. The tool also reports the per-router buffer size in a file buffer.csv

$ cat buffer.csv
0,0
2,2

For our synthetic example, it is clear that we have buffer size of 2 in the first row of the NoC and none are needed in the upper row. We can configure out FPGA in a fully customized manner to support just as many buffer locations that are needed per router.

Analysis Instructions for W->S+N buffer design

To run the analysis, you have to run the following set of steps:

1. To run the default example just type the following on the terminal

$ ./analyze_dualbuffer.py -N 2 -f flow.dat
Calling Octave script to run analysis
Stable=1, Max FIFO=1, WC Latency=16

2. You can override the rate and burst specification in flow.dat by using the -b and -r parameters. In this example, we are using a 2x2 NoC and a rate of 0.08 and burst of 2.

$ ./analyze.py -N 2 -f flow.dat -R 0.08 -B 2
Calling Octave script to run analysis
Stable=1, Max FIFO=2, WC Latency=19

First, we note that the analysis is stable -> no links are overutilized. Second, note that the buffer size has now increased to 2 due to a flow burst of length 2. If you know that you have a budget of certain maximum number of FIFO slots, you can use the "Max FIFO size" field to filter out cases that are not supported by your NoC configuration.

3. The tool also reports the per-router buffer size in a file buffer.csv

$ cat buffer.csv
1,0
0,0
0,0
0,2

buffer.csv has twice as many rows as the system size because each switch has two buffers. From the midpoint, the upper entries describe the W->N FIFO and the lower entries describe the W->S FIFO.

Reproducing data from the paper

To reproduce analysis results from the FPGA 2019 paper, please run the following scripts:

$ cd scripts
$ ./sweep_outer_analysis_random_hoprt.sh
$ ./sweep_outer_analysis_random_ws.sh
$ ./sweep_outer_analysis_random_wsn.sh
$ ./sweep_outer_analysis_random_wsbkp.sh

Hoplite router Verilog RTL is not part of this public release. Published simulation data is supplied as CSV files here:

$ cd sim-data
$ ls *.csv
sweep_random_srcq.csv       sweep_random_srcq_wsbkp.csv sweep_srcq.csv              sweep_srcq_wsbkp.csv

Here:

1. sweep_random_srcq.csv contains simulation data for various router combinations (except backpressure) under RANDOM traffic.
2. sweep_srcq.csv contains simulation data for various router combinations (except backpressure) under ALL->* traffic.
3. sweep_random_srcq_wsbkp.csv contains simulation data for backpressure router under RANDOM traffic.
4. sweep_srcq_wsbkp.csv contains simulation data for backpressure router under ALL->* traffic.

License

This tool is distributed under MIT license.

Copyright (c) 2019 Tushar Garg, Saud Wasly, Rodolfo Pellizzoni, Nachiket Kapre

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.