AnTiQ: A Hardware-Accelerated Priority Queue Design with Constant Time Arbitrary Element Removal

Abstract

The recent trend towards open architectures and open source hardware enables agile development of domain specific architectures. In this paper, we explore and propose the design and implementation of AnTiQ, a hardware-accelerated priority queue tailored to the needs of timer queue implementations and other cases where removal of arbitrary elements, a feature we found lacking in related work, is desirable. The key novelty of AnTiQ is the arbitrary remove or DROP operation, which along with PUSH, POP and PEEK is performed in constant time. The design was conceived by reviewing existing implementations of hardware priority queues and analysing the fundamental characteristics of three queue architectures: the shift register queue, the systolic array queue and the binary heap queue. The systolic array architecture was chosen for our design due to its pipelined structure and ability to provide constant time responses to queue operations regardless of the queue depth. The architecture and implementation of our RTL prototype is presented and relevant behavioural corner cases in the design are identified. The implementation of our design achieved a clock frequency of 350 MHz on a Xilinx VCU 118 FPGA. The scalability of the design is evaluated through FPGA synthesis for 32, 64, 128 and 256 depth configurations and compared to the related work. We elaborate on directions for further development and future work towards monotonic timer implementations for the RTIC framework, a domain specific Rust language extension for concurrent programming targeting bare metal microcontrollers.