Optimized queue based communication in VLSI using a weakly ordered binary heap
Stefan Scholze, Stephan Henker, Johannes Partzsch, Christian Mayr, René Schüffny · International Conference Mixed Design of Integrated Circuits and Systems · 2010
For event based routing using global timestamps a sorting and buffering component is required. This work describes the implementation of a priority queue algorithm applying a binary heap structure, which efficiently combines the data storage and the reordering according to the data timestamp. For operation only two main functionalities are required, which insert and retrieve elements while assuring the heap property. The developed algorithmic enhancements offer significant optimisation of the runtime behaviour compared to standard heap algorithms and allow the usage of SRAM as storage memory, which provides substantial reduction of silicon area. The algorithms are implemented in UMC 180nm technology and integrated into a large-scale VLSI routing system.