Browse Prior Art Database

Hardware Queueing Mechanism

IP.com Disclosure Number: IPCOM000045217D
Original Publication Date: 1983-Feb-01
Included in the Prior Art Database: 2005-Feb-06
Document File: 3 page(s) / 44K

Publishing Venue

IBM

Related People

Giaccone, LF: AUTHOR

Abstract

A hardware queueing mechanism (HQM) is a memory storing its elements in a "partial order" which facilitates the retrieval of the highest priority element in at log n accesses, where n is the count of the elements. It serves a priority queue or a sorting assist.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

Hardware Queueing Mechanism

A hardware queueing mechanism (HQM) is a memory storing its elements in a "partial order" which facilitates the retrieval of the highest priority element in at log n accesses, where n is the count of the elements. It serves a priority queue or a sorting assist.

In this discussion the definitions of the words cell, vertex and word coincide. They are used interchangeably when the context suits. For instance, trees have vertices, memories have words, and HQM has cells. HQM supports the tree structure which in RAM (random-access memory) would have the successor formula 2n+i, where n is the address of the current word and i is the associated bit of a path vector (Fig. 1). When i is a zero the left successor is chosen, and when i is a one, the right successor is chosen. Thus, a single bit string, of length log(2) n-1, is sufficient to traverse any path in the tree. HQM eliminates the need for the address n and the cost in time of calculating the successor vertex. This produces the effect of a memory having any number of words but having an address bus one bit wide.

HQM has the following elements (not shown): 1. The address line (I) upon which the path vector bit i is placed. 2. A Data Bus m bits wide (D). 3. Control Lines - Reset (R), Trigger (T), Strobe (S) and Read/Write (W). 4. Cell Address Elements (AE) 5. Cells (vertices, words) 6. Depth Counter (C).

Consider the cells of the HQM as sequentially numbered from 1 to x arranged according to the successor formula (Fig. 1), as previously mentioned.

Let n be the number of the cell currently accessed. After reset n is 1, when T is active and the memory is strobed (line S), HQM either places the contents of cell 1 on the data bus (D) if W=0 or latches the signals on D into cell 1 if W=1. Note that the device ignores the signal to I for the source vertex (this signal could be used as a chip select).

As was stated previously, subsequent accesses of HQM select successors to n by the formula 2n+i. The successor cell is selected by a cell address element (AE) associated with the current cell. The AE is the fundamental element of HQM. An AE is associa...