Browse Prior Art Database

No-Op Commands for Re-Ordering Messages in a First In/First Out

IP.com Disclosure Number: IPCOM000114334D
Original Publication Date: 1994-Dec-01
Included in the Prior Art Database: 2005-Mar-28
Document File: 4 page(s) / 148K

Publishing Venue

IBM

Related People

Feeney, JW: AUTHOR [+2]

Abstract

Disclosed is a method for handling "stuck" messages in relation to asynchronous, multi-stage switching networks. Said networks interconnect a plurality of nodes, and messages are transmitted across the network from a sending device at one node to a receiving device at another node. The devices normally contains message buffers, usually a Send FIFO containing a plurality of messages to be sent to the network, and a Receive (RCV) FIFO containing a plurality of messages which have been received from the network. A problem that occurs in a system using a Send FIFO is that the first message in the Send FIFO can get "stuck" and block subsequent messages in the FIFO. A "stuck" condition can be caused by no network path being available in a blocking network, or the RCV FIFO on the other side of the network being full.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 38% of the total text.

No-Op Commands for Re-Ordering Messages in a First In/First Out

      Disclosed is a method for handling "stuck" messages in relation
to asynchronous, multi-stage switching networks.  Said networks
interconnect a plurality of nodes, and messages are transmitted
across the network from a sending device at one node to a receiving
device at another node.  The devices normally contains message
buffers, usually a Send FIFO containing a plurality of messages to be
sent to the network, and a Receive (RCV) FIFO containing a plurality
of messages which have been received from the network.  A problem
that occurs in a system using a Send FIFO is that the first message
in the Send FIFO can get "stuck" and block subsequent messages in the
FIFO.  A "stuck" condition can be caused by no network path being
available in a blocking network, or the RCV FIFO on the other side of
the network being full.

      The solution is to implement hardware for the Send FIFO which
permits a "stuck" message to be bypassed temporarily and retried
later.  The writing of a message to the FIFO is done by the node
processor entering a message starting at the tail of the FIFO.  The
reading of a message from the FIFO to the network starts at the head
of the FIFO.  The solution requires special purpose hardware,
including two read pointers, a FIFO Head Pointer and a FIFO Re-Order
Pointer, plus 1 FIFO read counter.  With system reset, the 2 read
pointers and counter are all initialized to all zeroes.  After the
Send FIFO is loaded with a message or messages, the first message is
read from the FIFO using the Read Counter (address = all zeroes
initially).  It is assumed each message begins with a message  header
of one or several words containing pertinent information about the
message, including network destination (dest), message count, and
status.  The processor sets the 2-bit message status field to "10"
initially to indicate that the message is to be sent to the network.
The disclosed hardware reads the message header stores it to the
header register, as well as sending it to the network.  The read
counter is incremented after every word is read from the FIFO; this
continues as the entire first message is read from the FIFO.  Note
that at this time, the message also remains in the FIFO; i.e., it is
not destroyed as it is read.

      The network has two responses it can make to a message from the
Send FIFO: ACCEPT or REJECT.  ACCEPT means that the message was
transmitted successfully by the network.  REJECT means that the
message could not be transmitted successfully by the network.  If the
network issues ACCEPT, both the FIFO Pointers are set equal to the
Read Counter, which has counted through the first message and is now
pointing to the first word (header) of the second message.  This
erases the first message from the FIFO by changing the FIFO Head
Pointer to point to the second message, and defines a new head of the
FIFO.  If the network issues...