Browse Prior Art Database

Multiway Input Comparator for a Low-Cost Combining Switch

IP.com Disclosure Number: IPCOM000100912D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 3 page(s) / 93K

Publishing Venue

IBM

Related People

Pfister, G: AUTHOR [+2]

Abstract

We describe an improvement to a serial combining switch based on a ring geometry as, for example, in Lipovski (1). The improvement provides for a multiplicity of requests to be treated concurrently at each node instead of limiting the action at each node to a single request. Prior art for combining switches is due to Gottlieb et al. (2) who proposed an implementation of the Fetch-and-Add instruction as well as other instructions that take the general form Fetch-and-Op. The effect of this instruction when executed concurrently by N processors that attempt to update a single shared variable is to combine the updating information in the switching network so that only a single access to physical memory is necessary to effect the N updates.

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

Multiway Input Comparator for a Low-Cost Combining Switch

       We describe an improvement to a serial combining switch
based on a ring geometry as, for example, in Lipovski (1). The
improvement provides for a multiplicity of requests to be treated
concurrently at each node instead of limiting the action at each node
to a single request.  Prior art for combining switches is due to
Gottlieb et al.  (2) who proposed an implementation of the
Fetch-and-Add instruction as well as other instructions that take the
general form Fetch-and-Op.  The effect of this instruction when
executed concurrently by N processors that attempt to update a single
shared variable is to combine the updating information in the
switching network so that only a single access to physical memory is
necessary to effect the N updates.  A second effect of the
instruction is that each of the N processors is returned a result
that would have been observed for some serial ordering of the
updates. Therefore, the combining switch simulates the serial
updating of the shared variable while actually performing the update
in a parallel manner.

      We propose a means for doing combining at each node in ring
network whose nodes are connected to processors that randomly issue
Fetch-and-Add requests.  The objective is to combine from a
multiplicity of pending requests rather than to combine from a single
candidate request.  Each candidate can be initiated from a separate
processor tied to a node on the ring or can be initiated from one
processor provided that they are permitted to be executed out of
sequence.

      When combining is done by serial transmission of data, for
example, as outlined in Lipovski (1), a combining message is composed
of an identification tag, other control information, and the data to
be combined.  The implementation shown in Fig. 1 illustrates how
several requestors place requests to a combining node in a ring
network.  The combining network nodule shown in the figure oper...