Hardware Priority Queue Architecture Library

🎯 This library serves as a comprehensive resource for hardware researchers and developers exploring hardware priority queues for high-performance computing applications.

🏗️ Project Structure

• hwpq/ - Contains RTL implementations of different priority queue architectures, along with pre-collected key metrics logs.

• py-scripts/ - Python scripts for data analysis and visualization.

• vivado-runtime/ - Contains shell scripts that run Vivado in Tcl mode to sweep through parameters of each architecture in parallel.

  • It is suggested that users execute any Tcl or Bash scripts inside this directory. Since Vivado generates log and journal files automatically, keeping them in this specific directory facilitates later access and debugging.

• vivado-synthesis_tcl/ - Tcl scripts for Vivado synthesis.

❗ Prerequisites

Before running the synthesis and analysis, ensure you have the following installed:

• Xilinx Vivado: 2024.2 preferred

  • Download here: https://www.xilinx.com/support/download.html

• Python 3: verison>=3.8 preferred

⌨️ Running Synthesis and Analysis

Re-running synthesis is not necessary as all data is already available within each architecture's directory. If you're interested in analyzing the existing results, please proceed directly to the Analysis section below. Only re-run synthesis if you've modified an architecture or wish to test with different parameters.

Synthesis

1. Clone the repository.

2. Navigate to the hwpq directory:

   cd hwpq/vivado-runtime

3. Execute the parameter sweep Bash script, this script would find sweep through all possible combinations of enqueue swtich (if supported), queue_size (you can change the range inside of the script) with data width set to 16 bits (change also be changed inside of the script):

   ./run_param_sweep_parallel.sh <architecture>

   • Aviable architectures:

     • register_tree
     • register_tree_pipelined
     • register_array
     • register_array_pipelined
     • systolic_array
     • bram_tree
     • bram_tree_pipelined
     • hybrid_tree

4. Alternatively, if you just want to synthesize an architecture under a specific configurations, you could also run the tcl scipt instead:

   vivado -mode batch -source ../vivado-synthesis_tcl/synth_design_param_sweep_parallel.tcl -tclargs <architecture_name> <enqueue_on/off> <data_width> <queue_size>

   • <architecture_name>:

     • register_tree
     • register_tree_pipelined
     • register_array
     • register_array_pipelined
     • systolic_array
     • bram_tree
     • bram_tree_pipelined
     • hybrid_tree

   • <enqueue_on/off>: 1 (on) or 0 (off)

   • <data_width>: e.g., 8, 16, 32, 64 (integer)

   • <queue_size>: architecture and application-dependent (integer)

Analysis

1. Navigate to the hwpq directory:

   cd hwpq/vivado-runtime

2. Install the required Python packages:

   pip install -r ../py-scripts/requirements.txt

3. Process and visualize the results using the Python plotting script:

   python ../py-scripts/analysis_py/src/plotter

📐 Current Support Priority Queue Architectures

Register Based

• Register Tree

• Register Tree Pipelined

• Register Array

• Register Array Pipelined

• Systolic Array

BRAM Based

• BRAM Tree

• BRAM Tree Pipelined

• Hybrid Tree

Citing This Work

If you use this library in your work, please include a reference to the following citation:

@inproceedings{wu2025hwpq,
  author = {Wu, Charlie and Rovinski, Austin},
  title = {Revisiting Hardware Priority Queue Architectures},
  booktitle = {Fourth Workshop on Open-Source Computer Architecture Research (OSCAR)}
  year = {2025},
  month = {June}
}

📝 References

The architectures in this library are primarily dervied from the following references:

@article{moon2000,
  author = {Sung-Whan Moon and Rexford, J. and Shin, K.G.},
  journal = {IEEE Transactions on Computers},
  title = {Scalable hardware priority queue architectures for high-speed packet switches},
  year = {2000},
  volume = {49},
  number = {11},
  pages = {1215-1227},
  keywords = {Packet switching;Switches;Shift registers;Systolic arrays;Hardware design languages;Quality of service;Buildings;Binary trees;Clocks;Silicon compiler},
  doi = {10.1109/12.895938},
}

@inproceedings{huang2014,
  author = {Huang, Muhuan and Lim, Kevin and Cong, Jason},
  booktitle = {2014 24th International Conference on Field Programmable Logic and Applications (FPL) },
  title = {A scalable, high-performance customized priority queue},
  year = {2014},
  volume = {},
  number = {},
  pages = {1-4},
  keywords = {Throughput;Field programmable gate arrays;Arrays;Registers;Clocks;Software;Database systems},
  doi = {10.1109/FPL.2014.6927413},
}

@article{zhou2020,
  author = {Zhou, Yuzhi and Jin, Xi and Wang, Tianqi and Boluda, Jose A.},
  title = {FPGA Implementation of A Star Algorithm for Real-Time Path Planning},
  year = {2020},
  issue_date = {2020},
  publisher = {Hindawi Limited},
  address = {London, GBR},
  volume = {2020},
  issn = {1687-7195},
  url = {https://doi.org/10.1155/2020/8896386},
  doi = {10.1155/2020/8896386},
  journal = {Int. J. Reconfig. Comput.},
  month = jan,
  numpages = {11},
}