Patent Description:
In some electronic devices, items can be removed from queues for handling out of order. In other words, in such electronic devices, items are not required to be removed in strictly in first-in-first-out (FIFO) or age order and instead can be removed, to at least some extent, in any convenient order. For example, a queue in a network device may store older transactions (or packets, messages, etc.) destined for a first downstream network device and newer transactions destined for a second downstream network device. If strictly age-order removal was required, the transactions destined for the first downstream network device would be required to be removed (and handled) first. In contrast, when out of order removal is permitted, the transactions destined for the second downstream network device can be removed first, despite being younger. This can be useful because the network device can make progress in removing the transactions from the queue when the second downstream network device is available, despite the first downstream network device being busy.

Although permitting the out of order removal of items from queues can be beneficial, electronic devices that support out of order removal must also include mechanisms for managing the vacancies in the queues caused by the out of order removal of items. Some electronic devices handle such vacancies by simply shifting the remaining items in the queue so that the vacancy is filled and a vacancy is opened at a "tail" of the queue for the next item to be added to the queue. This technique is straightforward and maintains age order among the items in a queue, but results in a large number of shift operations (especially in larger queues), because the removal of any item from the queue involves shifting as many as all of the remaining items in the queue. Electronic devices that use this technique for handling items in queues therefore consume relatively large amounts of electrical power for operating queues. Other electronic devices use metadata such as pointers, age information, or lists associated with items or entries in queues in order to keep track of the relative ages of items in queues. Although using metadata for keeping track of relative ages of items in queue can enable items to be stored in any location and age order in queues, the metadata must be stored in the queue or elsewhere and lookups must be performed in order to determine relative ages and/or locations of items in the queue. The overhead in terms of circuitry and lookup complexity for the metadata increases with larger queues. For queues above a certain size, the metadata circuitry can consume prohibitive amounts of circuit area and/or the lookup process can consume undesirably high levels of electrical power.

Throughout the figures and the description, like reference numerals refer to the same figure elements.

The following description is presented to enable any person skilled in the art to make and use the described embodiments and is provided in the context of a particular application and its requirements. Various modifications to the described embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications. Thus, the described embodiments are not limited to the embodiments shown, but are to be accorded the widest scope consistent with the principles and features disclosed herein.

In the following description, various terms are used for describing embodiments. The following is a simplified and general description of one of these terms. Note that this term may have significant additional aspects that are not recited herein for clarity and brevity and thus the description is not intended to limit this term.

Functional block: functional block refers to a group, collection, and/or set of one or more interrelated circuit elements such as integrated circuitry, discrete circuitry, etc. The circuit elements are "interrelated" in that circuit elements share at least one property. For example, the interrelated circuit elements may be included in, fabricated on, or otherwise coupled to a particular integrated circuit chip, substrate, circuit board, or portion thereof, may be involved in the performance of given functions (computational or processing functions, memory functions, etc.), may be controlled by a common control element and/or a common clock, etc. A functional block can include any number of circuit elements, from a single circuit element (e.g., a single integrated circuit logic gate or discrete circuit element) to millions or billions of circuit elements (e.g., an integrated circuit memory).

In the described embodiments, an electronic device includes a queue for storing items that are to be handled in the electronic device. For example, in some embodiments, a networking subsystem in the electronic device includes a network transaction queue that is used for storing network transactions (e.g., packets, requests, etc.) that are awaiting handling (e.g., forwarding, processing, etc.). As another example, in some embodiments, a processing subsystem in the electronic device includes a queue that stores work items (e.g., instructions, threads, interrupts, etc.) that are awaiting handling (e.g., scheduling, processing, etc.). The queue includes a set of multiple separate sub-queues, each sub-queue including a different subset of a set of entries for the queue. For example, the queue may include N entries (where N is <NUM>, <NUM>, or another number) that are divided among M sub-queues (where M is <NUM>, <NUM>, or another number). The sub-queues are included in a logical hierarchy in which the sub-queues are organized from a lowest sub-queue to a highest sub-queue.

In some embodiments, as items are stored in the queue, items are first stored in the lowest sub-queue in the hierarchy until the lowest sub-queue is full and then items are stored in successively higher sub-queues in the hierarchy as each successively higher sub-queue becomes full. In other words, as each sub-queue becomes full of stored items, subsequent incoming items are stored in a next higher sub-queue in the hierarchy. In some embodiments, as items are stored in the individual sub-queues, the items can be stored in any available entry in that sub-queue, so that items are not necessarily stored in a particular order in the entries in that sub-queue.

In some embodiments, a separate age matrix is used for keeping track of the relative ages of items that are stored in each of the sub-queues. Each age matrix includes a number of elements arranged in rows and columns, with each row and each column being associated with a different one of the entries in the corresponding sub-queue. Each row and column includes information about the relative ages of items that are stored in an associated entry in the sub-queue in comparison to items that are stored in some or all of the other entries in the sub-queue. More specifically, each element in an age matrix is used for storing a value that indicates whether the entry in the corresponding sub-queue associated with the row is older than the entry in the corresponding sub-queue associated with the column - or vice versa. In some embodiments, the value is stored in each element in age matrices using a single bit. In some of these embodiments, when the bit in an element in a column of an age matrix is set to <NUM>, the item in the entry associated with the column of the age matrix is older (i.e., less recently added to the entry) than the item in the entry associated with the row. The opposite is true when the bit in an element in a row of an age matrix is set to <NUM>. In some embodiments, the columns and/or rows in an age matrix include or are associated with validity information (e.g., one or more valid bits, etc.). In these embodiments, when an entry in the corresponding sub-queue does not presently store an item, the validity information is set to indicate that the column and/or row is invalid and should not be used for relative age determinations. In some embodiments, the validity information is included in metadata in the entry itself, but is used for handling information in the age matrix.

In some embodiments, as items are stored in entries in a sub-queue, the associated age matrix is updated to reflect the new relative ages of items stored in the sub-queue. For the updating operation, specified elements in columns and/or rows are set or updated. For example, in some embodiments, elements in a column in the age matrix that is associated with the entry in the sub-queue are set to a value such as <NUM> and elements in a row in the age matrix that is associated with the entry in the sub-queue are set to a value such as <NUM>.

In some embodiments, items that were previously stored in the queue are removed from the queue by being removed from the lowest-sub-queue in the hierarchy - and only from the lowest sub-queue. In some embodiments, any item that is ready for removal can be removed from the lowest sub-queue, including items for which there are one or more older items in the lowest sub-queue. In other words, items can be removed from the lowest sub-queue out of order with regard to other items in the sub-queue as the items are ready for removal. For example, when the queue is a network transaction queue, an item (e.g., a transaction such as a packet or request) destined for a first downstream device can be removed from the queue and forwarded to the first downstream device when the first downstream device is available, despite one or more older items destined for a second downstream device awaiting forwarding in the queue when the second downstream device is busy.

In some embodiments, when an item is removed from the lowest sub-queue, a vacancy is created in the lowest sub-queue - i.e., the entry in the sub-queue that stored the item is freed for storing another item. Items from the higher sub-queues in the hierarchy (assuming such items exist) are then shifted to fill the vacancy in the lowest sub-queue. For this operation, starting from the lowest sub-queue and proceeding through sub-queues in the hierarchy, for each sub-queue, when a next higher sub-queue in the hierarchy exists and stores at least one item, a controller in the electronic device determines, using the age matrix associated with the next higher sub-queue, an entry in which an oldest item in the next higher sub-queue is stored. For example, in some embodiments, the controller finds a column in the age matrix associated with the next higher sub-queue that best meets a criteria for the values in the column, such as the column in which the elements store the smallest number of <NUM> or the most <NUM>. The controller then identifies, based on the particular column in the age matrix, the entry in the next higher sub-queue in which the oldest item is stored - i.e., matches the column to the associated entry in the next higher sub-queue. The controller then moves the oldest item from the entry in the next higher sub-queue into the sub-queue. In this way, the controller moves/shifts the oldest item from each higher sub-queue down to the next lower sub-queue in sequence to fill the vacancy in each sub-queue.

In some embodiments, multiple items that are ready for removal can be removed from the lowest sub-queue in a single removal operation, including multiple items for which there are one or more older items in the lowest sub-queue. In other words, in these embodiments, two or more items can be removed at a time and out of order from the lowest sub-queue when the items are ready for removal. As with removing a single item from the lowest sub-queue, a corresponding number of items from the higher sub-queues in the hierarchy (assuming such items exist) are shifted to fill the vacancy in the lowest sub-queue.

By using the hierarchy of sub-queues and using age matrices to manage items in the sub-queues, the described embodiments are able to implement larger queues without the shortcomings of other queue implementations. More specifically, by using the hierarchy of sub-queues, the described embodiments are able to avoid the large number of shift operations that are performed in queues that order entries by age using shift operations and are able to avoid the complex and power hungry age metadata circuitry used for larger out-of-order queues. The electronic devices in the described embodiments therefore more efficiently use electrical power and computational resources, which leads to higher user satisfaction with the electronic devices.

<FIG> presents a block diagram illustrating electronic device <NUM> in accordance with some embodiments. As can be seen in <FIG>, electronic device <NUM> includes processing subsystem <NUM>, graphics processing subsystem <NUM>, memory subsystem <NUM>, and networking subsystem <NUM>. Generally, processing subsystem <NUM>, graphics processing subsystem <NUM>, memory subsystem <NUM>, and networking subsystem <NUM> are functional blocks that are implemented in hardware, i.e., using various circuitry, circuit elements, and devices. For example, processing subsystem <NUM>, graphics processing subsystem <NUM>, memory subsystem <NUM>, and networking subsystem <NUM> can be entirely fabricated on one or more semiconductor chips, including on one or more separate semiconductor chips, can be fashioned from semiconductor chips in combination with discrete circuit elements, can be fabricated from discrete circuit elements alone, etc. As described herein, some or all of processing subsystem <NUM>, graphics processing subsystem <NUM>, memory subsystem <NUM>, and networking subsystem <NUM> can perform operations for managing items in queues that include separate sub-queues using respective age matrices.

Processing subsystem <NUM> is a functional block that performs computational and other operations (e.g., control operations, configuration operations, etc.) in electronic device <NUM>. For example, processing subsystem <NUM> can be or include one or more microprocessors, central processing unit (CPU) cores, and/or other processing mechanisms. In some embodiments, processing subsystem <NUM> includes a queue having a number of sub-queues in which items such as threads, instructions, etc. can be stored and managed using age matrices as described herein.

Graphics processing subsystem <NUM> is a functional block that performs computational and other operations (e.g., control operations, configuration operations, etc.) associated with graphics processing (e.g., rendering, etc.) and/or general purpose computational operations in electronic device <NUM>. For example, processing subsystem <NUM> can be or include one or more general purpose graphics processing unit (GPGPU) cores, and/or other graphics processing mechanisms. In some embodiments, graphics processing subsystem <NUM> includes a queue having a number of sub-queues in which items such as threads, instructions, etc. can be stored and managed using age matrices as described herein.

Memory subsystem <NUM> is functional block that performs operations of a memory (e.g., a "main" memory). Memory subsystem <NUM> includes volatile and/or non-volatile memory circuits such as fourth-generation double data rate synchronous DRAM (DDR4 SDRAM) and/or other types of memory circuits for storing data and instructions for use by other functional blocks in electronic device <NUM> and control circuits for handling accesses of the data and instructions that are stored in the memory circuits and for performing other control or configuration operations. In some embodiments, memory subsystem <NUM> includes a queue having a number of sub-queues in which items such as memory access requests can be stored and managed using age matrices as described herein.

Networking subsystem <NUM> is a functional block that performs operations for searching for, connecting to, configuring, and communicating on a wired and/or wireless electronic communications network. Networking subsystem <NUM> includes transceivers, controllers, processors, and/or other circuitry for communicating on the wired and/or wireless network. In some embodiments, networking subsystem <NUM> includes a queue having a number of sub-queues in which items such as network transactions (e.g., packets, requests, messages, etc.) can be stored and managed using age matrices as described herein.

Electronic device <NUM> is simplified for illustrative purposes. In some embodiments, however, electronic device <NUM> includes additional or different functional blocks, subsystems, elements, and/or communication paths. For example, electronic device <NUM> may include input-output (I/O) subsystems, display subsystems, human interface subsystems, etc. Electronic device <NUM> generally includes sufficient functional blocks to perform the operations herein described.

Electronic device <NUM> can be, or can be included in, any device that performs the operations described herein. For example, electronic device <NUM> can be, or can be included in, a desktop computer, a laptop computer, a wearable computing device, a tablet computer, a piece of virtual or augmented reality equipment, a smart phone, an artificial intelligence (AI) or machine learning device, a server, a network appliance, a toy, a piece of audio-visual equipment, a home appliance, a vehicle, etc., and/or combinations thereof.

In the described embodiments, a queue is used for storing items. For example, in some embodiments, the queue is a network queue in networking subsystem <NUM> in which network transactions (i.e., the "items") are temporarily buffered before being removed and processed, forwarded, or otherwise handled by networking subsystem <NUM>. As another example, in some embodiments, the queue is a processing queue in processing subsystem <NUM> in which processing tasks or threads (i.e., the "items") are temporarily stored before being removed and processed or otherwise handled by processing subsystem <NUM>. <FIG> presents a block diagram illustrating queue <NUM> in accordance with some embodiments. As can be seen in <FIG>, queue <NUM> includes a set of <NUM> entries <NUM>. Each entry <NUM> includes memory circuitry (e.g., flip flops, latches, SRAM memory circuitry, etc.) useable for storing items. For example, in some embodiments, each entry includes memory circuitry for storing a set of bits for items that are up to T bytes in length (e.g., <NUM>, <NUM>, or another number of bytes). In some embodiments, each entry <NUM> also includes memory circuitry for storing metadata such as validity information, etc. that is used for handling or identifying information (or the lack thereof) in that entry <NUM>. For example, in some embodiments, the validity information is used for controlling when corresponding rows or columns are used for determining the age of items stored in entries <NUM> as described herein.

Entries <NUM> in queue <NUM> are allocated among a logical hierarchy of sub-queues <NUM> that includes, in order from a highest sub-queue to a lowest sub-queue in the hierarchy, highest sub-queue <NUM>, intermediate sub-queue <NUM>, and lowest sub-queue <NUM> (collectively, "the sub-queues"). Each of the sub-queues therefore includes a different subset of entries <NUM> - which is shown in <FIG> as each of the sub-queues including a different set of <NUM> of the <NUM> entries <NUM>. As used herein, "logical hierarchy" indicates that the sub-queues are regarded as part of a hierarchy by controller <NUM> (and possibly other functional blocks in electronic device <NUM>) for operations such as storing of items in and removal of items from the queue, shifting items among the sub-queues, etc. For example, in some embodiments, items are only removed from lowest sub-queue <NUM> in queue <NUM> (and not others of the sub-queues), items are shifted in a downward direction through the hierarchy of sub-queues until being removed from lowest sub-queue <NUM>, items are stored in queue <NUM> in a lowest sub-queue in which a vacant entry <NUM> is presently available, etc..

Queue <NUM> also includes controller <NUM>. Controller <NUM> is a functional block that performs operations for handling items in queue <NUM>. Controller <NUM> includes logic <NUM>, which is a functional block having circuitry for performing the operations for handling items in queue <NUM>. For example, in some embodiments, logic <NUM> performs operations for storing items in queue <NUM> (i.e., in the sub-queues), removing items from queue <NUM>, receiving items from other functional blocks in electronic device <NUM> (e.g., processing subsystem <NUM>, etc.), communicating items to other functional blocks in electronic device <NUM>, etc. When storing items in queue <NUM>, logic <NUM> receives an item, determines a lowest sub-queue in the hierarchy in which an entry is available for storing the item, and stores the item in an available entry in the determined sub-queue. When removing items from queue <NUM>, logic <NUM> determines that an item is ready for removal in lowest sub-queue <NUM>, acquires the item from an entry in lowest sub-queue <NUM>, and provides the item to a receiving functional block in electronic device <NUM> (or another entity). After removing an item from lowest sub-queue <NUM>, logic <NUM> shifts items downward in the hierarchy of sub-queues (assuming such items exist) to fill the vacancy in lowest sub-queue <NUM>. The operations performed by controller <NUM>/logic <NUM> for handling items in queue <NUM> are described in more detail below.

Controller <NUM> includes age matrices <NUM>-<NUM>. Each of age matrices <NUM>-<NUM> is a functional block that includes memory circuitry (e.g., flip flops, latches, SRAM memory circuitry, etc.) for storing an age matrix for a corresponding one of the sub-queues. Generally, each age matrix includes an arrangement of data (e.g., an array or a portion thereof, a table, a list, etc.) useable for identifying relative ages of items stored in entries in an associated sub-queue. <FIG> presents a block diagram illustrating an age matrix <NUM> in accordance with some embodiments. As can be seen in <FIG>, age matrix <NUM> includes a number of elements <NUM> arranged in rows <NUM> and columns <NUM>. The elements <NUM> in each row <NUM> and column <NUM> are associated with a different entry in a corresponding sub-queue and are used for storing age information for the associated entry (i.e., for an item stored in the associated entry). For example, the bottommost row <NUM> and leftmost column <NUM> in age matrix <NUM> are associated with entry _0 in sub-queue <NUM>. The bottommost row <NUM> and leftmost column <NUM> in age matrix <NUM> therefore store age information relating to an item stored in entry _0. Note that in age matrix <NUM> the diagonal row, which would hold values that represent the relative ages of items stored in the same entries in an associated sub-queue is shown in black - as such values are of little use and are not kept in some embodiments (and are only presented in <FIG> for clarity).

In some embodiments, the age information is stored in each element <NUM> using a specified number of bits. For example, in some embodiments, age information is stored in each element <NUM> in age matrix <NUM> using a single bit. In these embodiments, what the values of the bit in each element <NUM> indicate/represent in terms of the relative ages of items stored in entries in the associated sub-queue is determined and set in advance. For example, in some embodiments, <NUM> represent younger items and <NUM> represent older items. As another example, in some embodiments, <NUM> represent younger items and <NUM> represent older items. For the example in <FIG>, Ms and Ks are used as placeholders for illustrative purposes, but have no specific meaning. The values of bits and interpretation of relative age information in age matrix <NUM> is described in more detail below.

Age matrix <NUM> as shown in <FIG> is an example of a particular arrangement of data for an age matrix, but age matrices <NUM>-<NUM> may store data in one or more different arrangements, including arrangements that are not easily readable (e.g., a list, a table, etc.) but that otherwise represent what is shown in <FIG>. For example, <FIG> presents a block diagram illustrating a reduced form of age matrix <NUM> in accordance with some embodiments. As with age matrix <NUM>, age matrix <NUM> includes elements <NUM> arranged in rows <NUM> and columns <NUM>. Unlike age matrix <NUM>, however, age matrix <NUM> lacks elements <NUM> in rows <NUM> and columns <NUM> above reflection (REF) line <NUM>. This is because the values that would be stored in such elements <NUM> of age matrix <NUM> can be determined by reflecting and swapping the values in the elements <NUM> that are present in matrix <NUM> (for this example, M is the swap of K and vise versa). This is shown in <FIG> using dotted lines and italicized letters (which are similar in value to those in the corresponding elements <NUM> of age matrix <NUM>). In other words, given the information in elements <NUM> on one side of reflecting line <NUM>, the values that would be stored in elements <NUM> on the other side of the reflecting line can be computed. For this reason, in some embodiments, the reduced age matrix <NUM> is used instead of age matrix <NUM>.

Note that, although queue <NUM> is presented with a specific number of entries and an arrangement of sub-queues, in some embodiments, queue <NUM> includes a different number of entries and/or arrangement of sub-queues. For example, in some embodiments, queue <NUM> includes a different number of entries in some or all of highest sub-queue <NUM>, intermediate sub-queue <NUM>, and lowest sub-queue <NUM>. In other words, in these embodiments some or all of the sub-queues have a different number of entries than one or more others of the sub-queues. As another example, in some embodiments, queue <NUM> includes four or more sub-queues. Generally, in the described embodiments, queue <NUM> includes sufficient sub-queues and entries therein (and other circuitry) to perform the operations described herein.

In the described embodiments, age matrices are used for keeping track of the relative ages of items stored in entries in sub-queues in an electronic device. <FIG> presents a block diagram illustrating a process for using an age matrix for keeping track of the relative ages of items in a sub-queue in accordance with some embodiments. Note that the operations shown in <FIG> are presented as a general example of operations performed by some embodiments. The operations performed by other embodiments include different operations, operations that are performed in a different order, and/or operations that are performed by different functional blocks. In addition, in some embodiments, the sub-queue has a different number of entries and the age matrix has a different number and/or arrangement of elements.

In <FIG>, states of a sub-queue are shown on the left side, corresponding states of an age matrix are shown in the center, and an arrow indicating a progression of time is shown on the right side. Generally, in <FIG>, at five separate times, i.e., times <NUM>-<NUM>, four items (i.e., items_0-item_3) are stored in the sub-queue and one item is removed (i.e., item_2), with the illustrated changes being made in the age matrix. In addition, in <FIG>, elements of the age matrix that are written due to an item having been stored in an entry of the sub-queue are shown using a diagonal hatched background, elements that are updated due to an item having been stored in an entry of the sub-queue or removed from an entry of the sub-queue are shown with stippled/dotted background, and unchanged elements are shown with a white background. (Recall that the elements on the central diagonal in the age matrix are shown in black as those elements are not used in some embodiments. ) Also, for the sake of illustration, a "new" (N) and "old" (O) pointer are shown in <FIG> to illustrate the column of the age matrix that identifies the entries that store the newest and oldest items in the sub-queue, although the new and old pointers may not exist/be used in some embodiments.

For the example in <FIG>, times <NUM>-<NUM> are illustrated. Individually, these times can be any absolute or relative time. With regard to the overall flow of time, times <NUM>-<NUM> and their placement in <FIG> are not intended to indicate any relationship between the times and are not drawn to a particular scale. Times <NUM>-<NUM> could therefore occur over several milliseconds, seconds, etc. with different numbers of milliseconds, seconds, etc. occurring between each of times <NUM>-<NUM>.

In some embodiments, when no item is presently stored in an entry in an associated sub-queue, a validity flag/register associated with a column in the age matrix (which may be or include validity information in metadata in the entry itself) (not shown) is set to indicate that the respective column in the age matrix is invalid and therefore should not be used in age-determining operations. This is shown in <FIG> using Xs in the elements in such columns, although in some embodiments, the elements in such columns may store other values, including <NUM> or <NUM> - and the validity flag/register value controls whether or not a controller (e.g., controller <NUM>) uses the values in the elements. For the example in <FIG>, although not shown for clarity, it is assumed that the sub-queue is initially empty and thus age matrix has the validity flag/register value set to indicate that all of the columns are invalid - and thus the elements in all of the columns would initially be shown with Xs (as can be seen, three of the columns remain invalid at time <NUM>).

For the operations in <FIG>, a particular pattern of <NUM> and <NUM> in columns of the age matrix is used for determining an entry in a sub-queue in which an oldest element among the elements in the sub-queue is stored. More specifically, the entry in the sub-queue that includes the oldest item is determined based on the column that includes no <NUM> (and possibly all <NUM>). Generally, for this pattern, the column in the age matrix that is associated with the entry in the sub-queue in which the oldest item is stored includes no <NUM> (and thus only <NUM>). Although this pattern is used for the example in <FIG>, in some embodiments, a different pattern is used. For example, the properties associated with <NUM> and <NUM> may be reversed, so that the column with the most <NUM> is used for determining an entry in a sub-queue in which an oldest element is stored. As another example, values in rows of elements in the age matrix may be used instead of columns - with the updating of the age matrix as described below adjusted accordingly. In addition, although an age matrix with a particular arrangement of rows and columns is used for the example in <FIG>, in some embodiments, an age matrix with a different arrangement of rows and/or columns is used. For example, the reduced age matrix shown in <FIG> or some representation thereof can be used in some embodiments. Generally, in the described embodiments, any arrangement of values can be stored in an age matrix having a respective set of rows and columns (or the equivalent) and used to determine the relative ages of entries in the sub-queue.

Turning now to <FIG>, at time <NUM>, the controller receives item_0, determines that item_0 is to be stored in entry <NUM> in the sub-queue (as incoming items are permitted to be stored in any available entry in the sub-queue), and stores item_0 into entry <NUM> in the sub-queue. The controller also updates the age matrix to indicate that a newest item in the sub-queue is stored in entry <NUM> of the sub-queue. For the updating, the controller sets the elements in the column associated with entry <NUM> equal to <NUM>. This can be seen in the age matrix because the elements of column <NUM> have the diagonal hatched background - and are set to <NUM>. Because the other columns in the age matrix are invalid at time <NUM> (and therefore contain the X invalidity value), no changes are made to the rows. In some embodiments, however, the elements in row <NUM> would be set to <NUM> despite the columns being invalid.

Because only the column of the age matrix associated with entry <NUM> has valid values at time <NUM>, the new and old pointers both indicate the column associated with entry <NUM>. If the controller used the age matrix to determine the entry in the sub-queue that stored the oldest element at time <NUM>, the controller would identify entry <NUM> of the sub-queue based on the values in elements of the age matrix. For example, in some embodiments, while disregarding values in elements in invalid rows (i.e., rows for which the associated entry in the sub-queue do not presently store an item), the controller finds the valid column that includes no <NUM>. In other words, while masking rows using corresponding validity information (e.g., a valid bit in metadata for the associated entry in the sub-queue), the controller determines the valid column in the age matrix that has no <NUM>. Because the three rows of <NUM> in column <NUM> are disregarded - and column <NUM> is the only valid column - the controller identifies column <NUM> as including no <NUM>. The controller also determines that entry <NUM> of the sub-queue, which is associated with column <NUM>, stores the oldest item.

At time <NUM>, the controller receives item_1, determines that item_1 is to be stored in entry <NUM> in the sub-queue, and stores item_1 into entry <NUM> in the sub-queue. The controller also updates the age matrix to indicate that a newest item in the sub-queue is stored in entry <NUM> of the sub-queue. For the updating, the controller sets the elements in the column associated with entry <NUM> equal to <NUM>. This can be seen in the age matrix because the elements of column <NUM> have the diagonal hatched background - and are set to <NUM>. The controller also sets all the valid elements in the row associated with entry <NUM> equal to <NUM>. This can be seen in the age matrix because the elements of row <NUM> have the stippled/dotted background - and are set to <NUM>. Note that only the element in column <NUM> of row <NUM> is set to <NUM> - because the other columns in the age matrix are invalid at time <NUM>, no changes are made to these elements in row <NUM>.

At time <NUM>, two columns of the age matrix include age information. Generally, for the embodiment shown in <FIG>, entries storing newer items include more <NUM> in the column (the columns are set this way, as described above). Because the column associated with entry <NUM> has more <NUM> at time <NUM> (i.e., three <NUM>), therefore, the new pointer indicates the column associated with entry <NUM>. On the other hand, the column associated with entry <NUM>, due to the setting of the <NUM> in row <NUM>, has less <NUM> at time <NUM> (i.e., two <NUM>), and thus the old pointer remains indicating the column associated with entry <NUM> - the entry storing the oldest item in the sub-queue. If the controller used the age matrix to determine the entry in the sub-queue that stored the oldest element at time <NUM>, the controller would identify entry <NUM> of the sub-queue based on the relative number of <NUM> stored in columns of the age matrix. For example, in some embodiments, while disregarding values in elements in invalid rows (i.e., rows for which the associated entry in the sub-queue do not presently store an item), the controller finds the valid column that includes no <NUM>. In other words, while masking rows using corresponding validity information, the controller determines the valid column in the age matrix that has no <NUM>. Because rows <NUM> and <NUM> are both valid (while rows <NUM> and <NUM> are invalid), the controller considers only the values in elements in the center four-element square of the age matrix. The controller therefore identifies column <NUM> as being the column that includes no <NUM>. The controller also determines that entry <NUM> of the sub-queue, which is associated with column <NUM>, stores the oldest item. For example, in some embodiments, the controller includes an arrangement of logic gates (e.g., NAND, NOR, etc. logic gates) that the controller uses for determining which column has the most <NUM> (or <NUM>).

At time <NUM>, the controller receives item_2, determines that item_2 is to be stored in entry <NUM> in the sub-queue, and stores item_2 into entry <NUM> in the sub-queue. The controller also updates the age matrix to indicate that a newest item in the sub-queue is stored in entry <NUM> of the sub-queue. For the updating, the controller sets the elements in the column associated with entry <NUM> equal to <NUM>. This can be seen in the age matrix because the elements of column <NUM> have the diagonal hatched background - and are set to <NUM>. The controller also sets all the valid elements in the row associated with entry <NUM> equal to <NUM>. This can be seen in the age matrix because the elements of row <NUM> have the stippled/dotted background - and are set to <NUM>. The elements in columns <NUM> and <NUM> of row <NUM> are set to <NUM> - because column <NUM> is invalid at time <NUM>, no changes are made to this element in row <NUM>.

At time <NUM>, three columns of the age matrix include age information. Because the column associated with entry <NUM> has the most <NUM> at time <NUM> (i.e., three <NUM>), the new pointer indicates the column associated with entry <NUM>. On the other hand, the columns associated with each of entries <NUM> and <NUM>, due to the setting of the <NUM> in row <NUM>, have less <NUM> at time <NUM>. The column with the most <NUM> is the column associated with entry <NUM>, and thus the old pointer remains indicating the column associated with entry <NUM> - which remains the entry storing the oldest item in the sub-queue. If the controller used the age matrix to determine the entry in the sub-queue that stored the oldest element at time <NUM>, the controller would identify entry <NUM> of the sub-queue based on the relative number of <NUM> stored in columns of the age matrix. For example, in some embodiments, while disregarding values in elements in invalid rows (i.e., rows for which the associated entry in the sub-queue do not presently store an item), the controller finds the valid column that includes no <NUM>. In other words, while masking rows using corresponding validity information, the controller determines the valid column in the age matrix that has no <NUM>. Because rows <NUM>, <NUM>, and <NUM> are all valid (while row <NUM> is invalid), the controller considers only the values in elements in the lower left nine-element block within the age matrix. The controller therefore identifies column <NUM> as being the column that includes no <NUM>. The controller also determines that entry <NUM> of the sub-queue, which is associated with column <NUM>, stores the oldest item.

At time <NUM>, the controller receives item_3, determines that item_3 is to be stored in entry <NUM> in the sub-queue, and stores item_3 into entry <NUM> in the sub-queue. The controller also updates the age matrix to indicate that a newest item in the sub-queue is stored in entry <NUM> of the sub-queue. For the updating, the controller sets the elements in the column associated with entry <NUM> equal to <NUM>. This can be seen in the age matrix because the elements of column <NUM> have the diagonal hatched background - and are set to <NUM>. The controller also sets all the valid elements in the row associated with entry <NUM> equal to <NUM>. This can be seen in the age matrix because the elements of row <NUM> have the stippled/dotted background - and are set to <NUM>.

At time <NUM>, all four columns of the age matrix include age information. Because the column associated with entry <NUM> has the most <NUM> at time <NUM> (i.e., three <NUM>), the new pointer indicates the column associated with entry <NUM>. On the other hand, the columns associated with each of entries <NUM>, <NUM>, and <NUM>, due to the setting of the <NUM> in row <NUM>, have less <NUM> at time <NUM>. The column with the most <NUM> is the column associated with entry <NUM>, and thus the old pointer remains indicating the column associated with entry <NUM> - which remains the entry storing the oldest item in the sub-queue. If the controller used the age matrix to determine the entry in the sub-queue that stored the oldest element at time <NUM>, the controller would identify entry <NUM> of the sub-queue based on the relative number of <NUM> stored in columns of the age matrix. For example, in some embodiments, while disregarding values in elements in invalid rows (i.e., rows for which the associated entry in the sub-queue do not presently store an item), the controller finds the valid column that includes no <NUM>. Because all of the rows of the age matrix are valid, the controller considers the values in all of the elements in the age matrix. The controller therefore identifies column <NUM> as being the column that includes no <NUM>. The controller also determines that entry <NUM> of the sub-queue, which is associated with column <NUM>, stores the oldest item.

At time <NUM>, the controller removes item_2 from entry <NUM> in the sub-queue. This removal is out of order with respect to the ages of items in the sub-queue. In some embodiments, this is permitted when newer items are "ready" to be removed before older items in the sub-queue. For example, when the items are processing tasks in processing subsystem <NUM>, item_2 may require a different and available first processing resource (e.g., execution unit, interrupt processor, etc.) than item_0 and item _1, which are waiting for a busy second processing resource. The controller also updates the age matrix to indicate that item_2 was removed from the sub-queue. For the updating, the controller sets the validity flag/register value for column associated with entry <NUM> to indicate that the column is invalid. As described above, this can be seen in the age matrix because the elements of column <NUM> have the stippled/dotted background - and are set to X.

At time <NUM>, three columns of the age matrix include valid age information. Because the column associated with entry <NUM> has the most <NUM> at time <NUM> (i.e., three <NUM>), the new pointer indicates the column associated with entry <NUM>. On the other hand, the columns associated with each of entries <NUM> and <NUM> have less <NUM> at time <NUM>. The column with the most <NUM> is the column associated with entry <NUM>, and thus the old pointer remains indicating the column associated with entry <NUM> - which remains the entry storing the oldest item in the sub-queue. If the controller used the age matrix to determine the entry in the sub-queue that stored the oldest element at time <NUM>, the controller would identify entry <NUM> of the sub-queue based on the relative number of <NUM> stored in columns of the age matrix. For example, in some embodiments, while disregarding values in elements in invalid rows (i.e., rows for which the associated entry in the sub-queue do not presently store an item), the controller finds the valid column that includes no <NUM>. In other words, while masking rows using corresponding validity information, the controller determines the valid column in the age matrix that has no <NUM>. Because rows <NUM>, <NUM>, and <NUM> are all valid (while row <NUM> is invalid), the controller considers only the values in elements in the upper right nine-element block within the age matrix. The controller therefore identifies column <NUM> as being the column that includes no <NUM>. The controller also determines that entry <NUM> of the sub-queue, which is associated with column <NUM>, stores the oldest item.

If the operations shown in <FIG> were to continue at an additional time following time <NUM> with the removal of the item in entry <NUM> of the sub-queue (not shown), the controller would set the validity flag/register value for the column associated with entry <NUM> to indicate that the column is invalid. At this point, using the age matrix to determine the oldest item present in the sub-queue would return column <NUM>, which would have no <NUM> in the upper right four-square box of elements in the age matrix that is used for the determining. On the other hand, if a new item were to be stored in the vacant entry <NUM>, the controller would again write <NUM> in the corresponding column and <NUM> in the corresponding row in the age matrix - an operation similar to what is described above.

In the described embodiments, as items are removed from a lowest sub-queue in a hierarchy of two or more sub-queues, a vacancy is created in the lowest sub-queue. A controller shifts items downward from higher sub-queues in the hierarchy - when such items exist - to fill the vacancy in the lowest sub-queue. <FIG> presents a block diagram illustrating the removal of an item from a lowest sub-queue in a hierarchy of sub-queues and the subsequent shifting of items from the higher sub-queues in the hierarchy to fill the vacancy in the lowest sub-queue in accordance with some embodiments. Note that the operations shown in <FIG> are presented as a general example of operations performed by some embodiments. The operations performed by other embodiments include different operations, operations that are performed in a different order, and/or operations that are performed by different functional blocks. In addition, in some embodiments, a different number of sub-queues are used and/or some or all of the sub-queues have different numbers of entries.

For the example in <FIG>, queue <NUM> includes three sub-queues <NUM>-<NUM>, each of which has capacity for storing four items. In the original state, which is shown on the left side of <FIG>, a controller has stored items in all the entries in all three of sub-queues <NUM>-<NUM>. Although age matrices are not shown in <FIG> for clarity, a separate age matrix is assumed to exist for each of sub-queues <NUM>-<NUM>. Each of the age matrices is further assumed to have been updated (e.g., as described above for <FIG>), and thus to hold current relative age information for the associated sub-queue.

As described above, for the operations in <FIG>, sub-queues <NUM>-<NUM> originally each hold four items. The controller then removes item_2 from sub-queue <NUM> (i.e., the lowest sub-queue in the hierarchy of sub-queues). For this operation, the controller determines that item_2 is ready for removal, reads item_2 from sub-queue <NUM> (and may provide item_2 to another functional block), and invalidates and/or clears the entry in sub-queue <NUM>. The controller also updates the age matrix for sub-queue <NUM> to reflect the change in the items stored in sub-queue <NUM>. Recall that, in some embodiments, items are permitted to be removed in any order from the lowest sub-queue in the hierarchy of sub-queues, based on which items are ready for removal. It may be true, therefore, that one or more items younger than item_2 (e.g., item_0, etc.) remain stored in the lowest sub-queue - which will be reflected, after the update, in the relative age information in the age matrix associated with sub-queue <NUM>.

After removing item_2 from sub-queue <NUM>, the controller shifts an item from the next higher sub-queue, i.e., sub-queue <NUM>, to fill the vacancy in sub-queue <NUM>. For this operation, the controller determines an oldest item in sub-queue <NUM> by determining a particular column (or row) in the age matrix associated with sub-queue <NUM> that best meets a specified criteria for values in the column (e.g., includes the most <NUM>). The controller then identifies, based on the particular column in the age matrix, the entry in sub-queue <NUM> in which the oldest item is stored. For the example in <FIG>, it is assumed that the oldest item in sub-queue <NUM> is item_4, and thus the controller identifies the entry in which item_4 is stored based on the values in elements in a corresponding column in the age matrix for sub-queue <NUM>. The controller then reads item_4 from sub-queue <NUM>, invalidates and/or clears the entry in sub-queue <NUM>, and stores item_4 in the vacant entry in sub-queue <NUM>. The controller also updates the respective age matrices for both sub-queues <NUM> and <NUM> to reflect the change in the items stored in sub-queues <NUM> and <NUM>. Alternatively, the controller may not update the age matrices for each of the sub-queues until all the movements of data affecting a given sub-queue have occurred - and thus may leave the age matrix associated with sub-queue <NUM> unchanged until the final shift occurs.

After shifting item_4 from sub-queue <NUM> to sub-queue <NUM>, the controller shifts an item from the next higher sub-queue, i.e., sub-queue <NUM>, to fill the vacancy in sub-queue <NUM>. For this operation, the controller determines an oldest item in sub-queue <NUM> using the associated age matrix (similarly to what was described above for sub-queue <NUM>). For the example in <FIG>, it is assumed that the oldest item in sub-queue <NUM> is item_8, and thus the controller identifies the entry in which item_8 is stored based on the values in elements in a corresponding column in the age matrix for sub-queue <NUM>. The controller then reads item_8 from sub-queue <NUM>, invalidates and/or clears the entry in sub-queue <NUM>, and stores item_8 in the vacant entry in sub-queue <NUM>. The controller also updates the respective age matrices for both sub-queues <NUM> and <NUM> to reflect the change in the items stored in sub-queues <NUM> and <NUM>.

At the end of the operations shown in <FIG>, sub-queue <NUM> has an entry that is available for storing an item, i.e., a vacancy. Although not shown in <FIG>, in a subsequent operation, a new item (e.g., received from another functional block) can be stored in the available entry in sub-queue <NUM>. As with other operations that change the items stored in entries in sub-queues, after storing the new item in sub-queue <NUM>, the controller would update the age matrix for sub-queue <NUM> to indicate the relative ages of items stored therein.

The described embodiments use age matrices for keeping track of the relative ages of items stored in sub-queues in a hierarchy of sub-queues. <FIG> presents a flowchart illustrating a process storing an item in a sub-queue and updating an age matrix for the sub-queue in accordance with some embodiments. For the process in <FIG>, it is assumed that a controller (e.g., controller <NUM>) in a networking subsystem (e.g., networking subsystem <NUM>) stores an item into an entry in a sub-queue (e.g., intermediate sub-queue <NUM>, lowest sub-queue <NUM>, etc.) from among a hierarchy of sub-queues in a queue (e.g., queue <NUM>) in the networking subsystem. It is also assumed that the sub-queue is associated with an age matrix (e.g., age matrix <NUM>) that is used for keeping track of the relative ages of items stored in entries in the sub-queue. Note that the operations shown in <FIG> are presented as a general example of operations performed by some embodiments. The operations performed by other embodiments include different operations, operations that are performed in a different order, and/or operations that are performed by different functional blocks.

The process in <FIG> starts when the controller receives an item to be stored in a queue that includes a number of sub-queues (step <NUM>). For this operation, the networking subsystem (or another functional block or entity) provides, to the controller, an item that identifies a network transaction such as a packet to be sent or forwarded to a downstream electronic device via a network, a control or configuration value to be transmitted to a downstream electronic device via a network, a message to be subsequently processed in the networking subsystem, etc. The item can include a number of bits or bytes organized into specified fields or portions that identify, characterize, and/or represent the network transaction.

The controller then determines a sub-queue in which the item is to be stored (step <NUM>). For this operation, the controller determines a lowest sub-queue in the hierarchy of sub-queues in which a vacant entry is available for storing the item. For example, the controller may maintain a pointer to the lowest queue in the hierarchy in which one or more entries are available, may keep a count of the items presently stored in all of the sub-queues, may query some or all of the sub-queues or entries therein regarding availability, etc., and may determine the lowest sub-queue based thereon. In this way, the controller stores items in the lowest sub-queue until the lowest sub-queue becomes full, and then stores items in successively next higher sub-queues in the hierarchy as each next higher sub-queue becomes full. As part of this operation, the controller also determines the particular entry in the sub-queue into which the item is to be stored. In some embodiments, items are permitted to be stored in entries in sub-queues in any order (i.e., are not restricted to being stored in the entries in an order such as first-in-first-out) and may be removed out of order, so the particular entry is determined by the controller each time that an item is stored to a sub-queue.

The controller next stores the item in the sub-queue (step <NUM>). For this operation, the controller writes, to the memory circuitry in the determined entry in the sub-queue, bits or bytes of the item or a representation thereof. Continuing the example above, this operation involves writing information about the network transaction to the entry in the sub-queue.

The controller then updates an age matrix associated with the sub-queue (step <NUM>). For this operation, the controller updates the age matrix to indicate that the entry in the sub-queue stores a youngest item from among the entries in the sub-queue. For example, assuming an embodiment in which the age matrix is updated as shown in <FIG>, the controller sets elements in a column in the age matrix associated with the entry in the sub-queue to <NUM> and sets elements in a row in the age matrix associated with the entry in the given sub-queue to <NUM>. After this operation, the column in the age matrix associated with the entry in the sub-queue stores all <NUM> and therefore indicates that the entry stores the youngest item in the sub-queue.

<FIG> presents a flowchart illustrating a process for shifting items in sub-queues in a hierarchy of sub-queues to fill a vacancy in a lowest sub-queue and updating age matrices for the sub-queues in accordance with some embodiments. For the process in <FIG>, it is assumed that a controller (e.g., controller <NUM>) in a networking subsystem (e.g., networking subsystem <NUM>) removes an item from an entry in a lowest sub-queue (e.g., lowest sub-queue <NUM>, etc.) from among a hierarchy of sub-queues in a queue (e.g., queue <NUM>) in the networking subsystem. It is further assumed that the sub-queues in the hierarchy of sub-queues are each associated with a separate age matrix (e.g., age matrix <NUM>) that is used for keeping track of the relative ages of items stored in entries in that sub-queue. Note that the operations shown in <FIG> are presented as a general example of operations performed by some embodiments. The operations performed by other embodiments include different operations, operations that are performed in a different order, and/or operations that are performed by different functional blocks.

The process in <FIG> starts when the controller removes an item that is ready for removal from an entry in the lowest sub-queue (step <NUM>). For this operation, the controller determines that an item is ready for removal from the lowest sub-queue based on the item itself or metadata for the entry in which the items is stored, operating states of functional blocks in the electronic device, busyness or idleness of downstream network devices or communication links in the network, etc. For example, the controller can determine that a communication link to be used for communicating a packet (i.e., the item) to a downstream network device is or has become available. The controller then removes the item from the entry in the lowest sub-queue and handles the item (e.g., forwards the packet to a downstream network device, etc.). Note that, as described above, the item that is ready for removal may be younger than other items in the sub-queue, but may still be removed from the sub-queue out of order with respect to older items in the sub-queue. In other words, the controller can remove the item from the lowest sub-queue regardless of an age of the item, so that an item that is younger than an oldest item in the lowest sub-queue is removed before the oldest item is removed from the lowest sub-queue.

After removing the item from the lowest sub-queue, the controller shifts items from higher sub-queues into lower sub-queues to fill the vacancy in the entry in the lowest sub-queue (step <NUM>). For this operation, the controller generally shifts items downward in the hierarchy of sub-queues as described for <FIG>. In other words, starting from the lowest sub-queue and proceeding through sub-queues in the hierarchy in order, for each sub-queue, the controller performs the following operations. When a next higher sub-queue in the hierarchy exists (i.e., the controller has not reached the top sub-queue in the hierarchy) and the next higher sub-queue stores at least one item (i.e., is not empty and thus has items to shift), the controller determines, using the age matrix associated with the next higher sub-queue, an entry in which an oldest item in the next higher sub-queue is stored. In some embodiments, for this operation, the controller determines a column (or row) in the age matrix associated with the next higher sub-queue that best meets a specified criteria for the values in the column (e.g., as described for <FIG>) and then uses the column to identify the entry in the next higher sub-queue in which the oldest item is stored. The controller next moves the oldest item from the entry in the next higher sub-queue into that sub-queue.

The controller then updates age matrices associated with the lowest sub-queue and sub-queues in the hierarchy from which items were shifted (step <NUM>). For this operation, the controller updates the age matrix for each sub-queue that experienced a change in the items stored therein, either by having a new item shifted in from a higher sub-queue or having an item shifted out to a lower sub-queue and not replaced (as with a highest sub-queue or an intermediate sub-queue with only empty higher sub-queues). For example, assuming an embodiment in which age matrices are updated as shown in <FIG>, the controller, when updating the age matrix for each sub-queue to which an item was shifted/stored, sets, to <NUM>, elements in a column in the age matrix associated with the shifted/newly added entry in that sub-queue and sets, to <NUM>, elements in a row in the age matrix associated with the shifted/newly added entry in that sub-queue. As another example, the controller, when updating the age matrix for a sub-queue from which an item was shifted out (vacating an entry) and another item was not shifted in, sets the invalid flag/register for a column in the age matrix that is associated with the vacated entry in that sub-queue.

In the examples above in this description, single items are removed from the lowest sub-queue and then single items shifted within the hierarchy of sub-queues to fill the vacancy in the lowest sub-queue. Removing only single items is, however, not a requirement. In some embodiments, two or more items that are ready for removal can be removed from the lowest sub-queue in a single removal operation (i.e., can be removed together/as a group), including multiple items for which there are one or more older items in the lowest sub-queue. In other words, in these embodiments, two or more items can be removed at a time and out of order from the lowest sub-queue when the items are ready for removal. As with removing a single item from the lowest sub-queue, a corresponding number of items from the higher sub-queues in the hierarchy (assuming such items exist) are shifted to fill the vacancies in the lowest sub-queue.

In some embodiments, at least one electronic device (e.g., electronic device <NUM>) uses code and/or data stored on a non-transitory computer-readable storage medium to perform some or all of the operations herein described. More specifically, the at least one electronic device reads code and/or data from the computer-readable storage medium and executes the code and/or uses the data when performing the described operations. A computer-readable storage medium can be any device, medium, or combination thereof that stores code and/or data for use by an electronic device. For example, the computer-readable storage medium can include, but is not limited to, volatile and/or non-volatile memory, including flash memory, random access memory (e.g., eDRAM, RAM, SRAM, DRAM, DDR4 SDRAM, etc.), non-volatile RAM (e.g., phase change memory, ferroelectric random access memory, spin-transfer torque random access memory, magnetoresistive random access memory, etc.), read-only memory (ROM), and/or magnetic or optical storage mediums (e.g., disk drives, magnetic tape, CDs, DVDs, etc.).

In some embodiments, one or more hardware modules perform the operations herein described. For example, the hardware modules can include, but are not limited to, one or more central processing units (CPUs)/CPU cores, graphics processing units (GPUs)/GPU cores, application-specific integrated circuit (ASIC) chips, field-programmable gate arrays (FPGAs), compressors or encoders, compute units, embedded processors, accelerated processing units (APUs), controllers, neural network processors, and/or other functional blocks. When circuitry (e.g., integrated circuit elements, discrete circuit elements, etc.) in such hardware modules is activated, the circuitry performs some or all of the operations. In some embodiments, the hardware modules include general purpose circuitry such as execution pipelines, compute or processing units, etc. that, upon executing instructions (program code, firmware, etc.), perform the operations. In some embodiments, the hardware modules include purpose-specific or dedicated circuitry that performs the operations, possibly including circuitry that performs some or all of the operations "in hardware" and without executing instructions.

In some embodiments, a data structure representative of some or all of the functional blocks and circuit elements described herein (e.g., electronic device <NUM> or some portion thereof) is stored on a non-transitory computer-readable storage medium that includes a database or other data structure which can be read by an electronic device and used, directly or indirectly, to fabricate hardware including the functional blocks and circuit elements. For example, the data structure may be a behavioral-level description or register-transfer level (RTL) description of the hardware functionality in a high-level design language (HDL) such as Verilog or VHDL. The description may be read by a synthesis tool which may synthesize the description to produce a netlist including a list of transistors/circuit elements from a synthesis library that represent the functionality of the hardware including the above-described functional blocks and circuit elements. The netlist may then be placed and routed to produce a data set describing geometric shapes to be applied to masks. The masks may then be used in various semiconductor fabrication steps to produce a semiconductor circuit or circuits (e.g., integrated circuits) corresponding to the above-described functional blocks and circuit elements. Alternatively, the database on the computer accessible storage medium may be the netlist (with or without the synthesis library) or the data set, as desired, or Graphic Data System (GDS) II data.

In this description, variables or unspecified values (i.e., general descriptions of values without particular instances of the values) are represented by letters such as N, M, and X. As used herein, despite possibly using similar letters in different locations in this description, the variables and unspecified values in each case are not necessarily the same, i.e., there may be different variable amounts and values intended for some or all of the general variables and unspecified values. In other words, particular instances of N and any other letters used to represent variables and unspecified values in this description are not necessarily related to one another.

The expression "et cetera" or "etc." as used herein is intended to present an and/or case, i.e., the equivalent of "at least one of" the elements in a list with which the etc. is associated. For example, in the statement "the electronic device performs a first operation, a second operation, etc.," the electronic device performs at least one of the first operation, the second operation, and other operations. In addition, the elements in a list associated with an etc. are merely examples from among a set of examples - and at least some of the examples may not appear in some embodiments.

Claim 1:
An electronic device, comprising:
a queue including two or more sub-queues, each of the two or more sub-queues including a separate subset of a set of entries for the queue, the sub-queues being arranged in a logical hierarchy from a lowest sub-queue to a highest sub-queue;
a memory associated with each sub-queue of the two or more sub-queues, each of the memories storing an age matrix for the associated sub-queue, each age matrix including only elements on a first side of a reflecting line for which values can be used to determine values for elements on a second side of the reflecting line, the values in the elements of each age matrix identifying relative ages of items stored in entries in the associated sub-queue; and
a controller configured to:
store items in the queue by storing items in the lowest sub-queue until the lowest sub-queue becomes full, and then storing items in successively next higher sub-queues in the hierarchy as each next higher sub-queue becomes full;
remove an item from the queue by removing an item that is ready for removal from an entry in the lowest sub-queue; and
shift items stored in sub-queues in the hierarchy to fill the entry in the lowest sub-queue by, starting from the lowest sub-queue and proceeding through sub-queues in the hierarchy, for each sub-queue:
when a next higher sub-queue in the hierarchy exists and stores at least one item, determining, using the age matrix associated with the next higher sub-queue, an entry in which an oldest item in the next higher sub-queue is stored; and
moving the oldest item from the entry in the next higher sub-queue into that sub-queue.