Priority queue sorting system and method with deterministic and bounded latency

Abstract

A priority queue sorting system including a priority queue and a message storage. The priority queue includes multiple priority blocks that are cascaded in order from a lowest priority block to a highest priority block. Each priority block includes a register block storing an address and an identifier, compare circuitry that compares a new identifier with the stored identifier for determining relative priority, and select circuitry that determines whether to keep or shift and replace the stored address and identifier within the priority queue based on the relative priority. The message storage stores message payloads, each pointed to by a corresponding stored address of a corresponding priority block. Each priority block contains its own compare and select circuitry and determines a keep, shift, or store operation. Thus, sorting is independent of the length of the priority queue thereby achieving deterministic sorting latency that is independent of the queue length.