Advanced Micro Devices, Inc.
Using age matrices for managing entries in sub-queues of a queue

Abstract:

An electronic device includes a queue with multiple sub-queues arranged in a logical hierarchy from a lowest sub-queue to a highest sub-queue, each sub-queue including a separate subset of a set of entries of the queue, and a separate age matrix for each sub-queue. The electronic device also includes a controller that stores items in entries in the lowest sub-queue until the lowest sub-queue is full and then stores items in successively next higher sub-queues in the hierarchy. The controller also removes an item that is ready for removal from an entry in the lowest sub-queue. The controller then shifts items in sub-queues in the hierarchy to fill the vacancy in the lowest sub-queue. For the shifting, the controller uses an age matrix associated with each sub-queue to determine an oldest item in that sub-queue and then moves the oldest item to a next lower sub-queue in the hierarchy.