Browse Prior Art Database

HARDWARE RETRY MECHANISM for MULTISTAGE INTERCONNECTION NETWORKS for PARALLEL COMPUTERS

IP.com Disclosure Number: IPCOM000039542D
Original Publication Date: 1987-Jun-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 6 page(s) / 84K

Publishing Venue

IBM

Related People

George, DA: AUTHOR [+5]

Abstract

Multistage Interconnection Networks (MINs) used in parallel computers transmit one word at a time between stages of switches. The size of these words depends on the implementation of the network. In order to implement data retry across long links in a network, the transmitting logic of the switch, attached to this link, should be able to buffer more than one word that has been transmitted across the link. The length (i.e., number of words) of this buffer depends on: the maximum number of bits that can be carried by a wire of the link at any point in time, the delay in the receiving logic to detect an error, and the delay in the transmitting logic to detect that retry is requested. Let "k" be the maximum number of bits a wire of the long link can carry at any point in time.

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

Page 1 of 6

HARDWARE RETRY MECHANISM for MULTISTAGE INTERCONNECTION NETWORKS for PARALLEL COMPUTERS

Multistage Interconnection Networks (MINs) used in parallel computers transmit one word at a time between stages of switches. The size of these words depends on the implementation of the network. In order to implement data retry across long links in a network, the transmitting logic of the switch, attached to this link, should be able to buffer more than one word that has been transmitted across the link. The length (i.e., number of words) of this buffer depends on: the maximum number of bits that can be carried by a wire of the link at any point in time, the delay in the receiving logic to detect an error, and the delay in the transmitting logic to detect that retry is requested. Let "k" be the maximum number of bits a wire of the long link can carry at any point in time. Let the receiving logic have an "r" bit delay to detect an error, and let the transmitting logic have a "t" bit delay to recognize that retry is required. Then the length of this buffer is given by the following equation: Buffer length L = 2k + r + t words In this buffer "k" words are needed to account for cable delay during the transmission of the word. The "r" and "t" words account for the delay in the receiving and transmitting switches to detect an error and retry, respectively.

The rest of "k" words are needed due to the cable delay incurred by the error (i.e., retry signal) indicating the signal from the receiving switch to the transmitting switch. For most switch designs the "r" and "t" parameters will be either 0 or 1. A O-bit delay is incurred when error detection is done in the cycle in which data is received and retry is requested in the following cycle. A 1-bit delay is seen when error detection is done in the cycle following data reception and retry is requested in the following cycle. In this latter case, if retry is signalled in the same cycle as error detection, then a O-bit delay is observed. A similar explanation can be given for the delay in recognizing retry. In order to minimize costs, MINs are constructed using only one switch design for all its switches. Due to this reason and because links between other stages can have different lengths, it is cost-effective to design this buffer to have a selectable length. That is, the length of this buffer should be configurable, as required. This can be done by designing a buffer of length "L" and selecting an appropriate subset of this length, at network initialization or construction time. This length "L" should be calculated as given above, for the longest link stage of the network. This disclosure assumes that such buffers can be used, if needed. For ease of explanation of the invention, it is assumed that "r" and "t" are zero. Figs. 1 and 2 reflect this assumption. If these assumptions do not hold for some MIN's switch design, then the logic of Figs. 1 and 2 can be easily modified, as required. It is also assu...