BBQ

The Bitmapped Bucket Queue (or BBQ for short) is a highly scalable and performant priority queue architecture for hardware packet scheduling. Underlying BBQ is an Integer Priority Queueing (IPQ) scheme that circumvents the complexity barrier imposed by comparison-based sorting, allowing it to scale to a large number of queue elements without increasing the runtime complexity of operations. Refer to the NSDI '24 paper for details about BBQ's design and how it makes it feasible, for the first time, to implement programmable packet scheduling on modern line-rate switches and SmartNICs.

Contents

This repository contains synthesizable SystemVerilog code for BBQ, as well as a number of existing hardware priority queue designs we compare against: PIFO (SIGCOMM '16), PIEO (SIGCOMM '19), and BMW-Tree (SIGCOMM '23). In addition, we provide scripts to synthesize these designs to hardware (targeting FPGAs and ASICs), and a simulation testbench for BBQ (consisting of a number of unit- and regression-tests).

Getting Started

This code was tested on Ubuntu 22.04 LTS. The workflow and minimum system requirements depend on how you intend to use this research artifact.

0. Browsing Code: You can find the source code for BBQ as well as the baseline designs in the hardware subdirectory. For instance, PIFO's priority queue implementation can be found in hardware/pifo/src/pifo.sv. In the case of BBQ, the source code is auto-generated by a Python wrapper that stitches together modular blocks of hand-written SystemVerilog code; to run this script, you will need Python 3.10 or newer. The instructions for this can be found in the hardware/bbq subdirectory.

1. FPGA Simulation: If you simply want to run and test these designs in simulation, you will need Modelsim (for Intel FPGAs). The BBQ source code is known to work with Modelsim Standard Edition v20.1.1. We recommend using the Starter Edition (included with all of Intel's Modelsim distributions), which is free to use and works seamlessly for designs with fewer than 10K LoC. As a starting point for simulation, we provide a testbench for bbq in the hardware/bbq/tb subdirectory.

2. FPGA Synthesis: If you want to synthesize these designs to an FPGA target, you will need Intel Quartus Prime. All designs contained herein are known to work with Quartus Prime Pro Edition v19.3. Note: Most of the included designs use a small set of Intel IPs (BRAM and SCFIFO); if you intend to use a different synthesis toolchain (e.g., Xilinx Vivado), you will need to modify the designs to use the equivalent IPs from the corresponding vendor. To get started with FPGA synthesis, refer to the README in the hardware subdirectory.

3. ASIC Synthesis: The PIFO and BBQ designs can also be synthesized to ASIC targets using the Synopsys Design Compiler. The ASIC synthesis flow is known to work with Synopsys S-2021.06 (Version 5.3) using a 7 nm Standard Cell Library based on the ASAP7 PDK. To get started with ASIC synthesis, refer to the README in the evaluation subdirectory (in progress, please check back shortly).