Browse Prior Art Database

Optimized algorithm for input bypass queue mechanism

IP.com Disclosure Number: IPCOM000014326D
Original Publication Date: 2002-Jan-20
Included in the Prior Art Database: 2003-Jun-19
Document File: 2 page(s) / 83K

Publishing Venue

IBM

Abstract

The Input Bypass Queuing mechanism described hereunder is composed of a FIFO memory which is used to enqueue and dequeue messages, a Write Pointer (WP) and a Read Pointer (RP). The memory width is N 1 where N is the number of bits of the messages. The additional bit called VALID_BIT is used to characterize the message in its memory position.

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 72% of the total text.

Page 1 of 2

Optimized algorithm for input bypass queue mechanism

   The Input Bypass Queuing mechanism described hereunder is composed of a FIFO memory which is used to enqueue and dequeue messages, a Write Pointer (WP) and a Read Pointer (RP). The memory width is N + 1 where N is the number of bits of the messages. The additional bit called VALID_BIT is used to characterize the message in its memory position.

VALID_BIT is

written at '1' during the write of the message

written at '0' when the message is processed (read)

So a VALID_BIT at '1' in a memory position indicates that this position contains a message and a VALID_BIT at '0' indicates that the memory position is empty.

Write Process

When a write request occurs, the message is written at the WP address, and the corresponding VALID_BIT is set to '1'. Then the Write Pointer is incremented to be ready for the next write.

Read Process

The read process is more complex, it permits to perform a read operation at an address which can be different of the one given by the Read Pointer. For example if the message contained at address RP cannot be processed, the mechanism tries at address RP+1, RP+2 and so on, until it finds a message that can be processed. This message is read and its corresponding VALID_BIT is reset, so that this message will not be read twice in a later read operation. After the read operation, the Read Pointer is either incremented (if the read message was the one indicated by the Read Pointer) or restored (refer...