Enhanced hardware shifting priority queue architecture with reduced switching activity

摘要

Hardware priority queues are data structures employed to build efficient communication infrastructures or to significantly speed up certain classes of algorithms such as task scheduling. This paper proposes an enhanced hardware priority queue which inherits its base idea from the shift register model. The designed enhancement aims at avoiding the costly shift operation needed to enqueue or dequeue data. This is achieved by using a mechanism that operates on some of the top locations of the queue and selects the data to be read and postpones the shift operation. A similar approach is used to enhance the write operation by avoiding the data shift in some cases if the new data must be introduced in the area belonging the top of the queue data area. The basic structural element is a storage cell that can decide autonomously how to behave when performing an operation. We developed a configurable tool which generates different queue instances based on specific parameters. The generated queues are processed using FPGA (Field Programmable Gate Array) flows. Multiple simulations were carried out using simple and enhanced versions of the queue and a significant switching activity reduction is reported in the case of the enhanced version. The simulations use various distributions and parameters for enqueue and dequeue requests generation. Simulations prove the functional correctness and synthesis reports prove the power efficiency and the moderate resource overhead of the enhanced version compared to the baseline.