Browse Prior Art Database

Class of Low-Cost Switching Structures

IP.com Disclosure Number: IPCOM000034434D
Original Publication Date: 1989-Feb-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 5 page(s) / 108K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

A basic switch structure can be used in a variety of structures that permit a designer to achieve a broad range of values of cost and performance to perform combining operations similar to those described in [1,2,3]. (Image Omitted) The basic form of the low-cost combining switch is shown in Fig. 1. This is a three-node token ring with two input nodes and one output node. The switch combines requests from the input nodes and produces a combined request at the output node. The functional combination of the requests produces a Fetch-and-Add Instruction as described in [1]. The switch also implements the multiprocessor join described [2, 3]. In the case in Fig. 1, the token ring is as small as possible in that it combines two inputs to produce one output. (Image Omitted) To produce a network as shown in Fig.

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 5

Class of Low-Cost Switching Structures

A basic switch structure can be used in a variety of structures that permit a designer to achieve a broad range of values of cost and performance to perform combining operations similar to those described in [1,2,3].

(Image Omitted)

The basic form of the low-cost combining switch is shown in Fig. 1. This is a three-node token ring with two input nodes and one output node. The switch combines requests from the input nodes and produces a combined request at the output node. The functional combination of the requests produces a Fetch-and-Add Instruction as described in [1].

The switch also implements the multiprocessor join described [2, 3].

In the case in Fig. 1, the token ring is as small as possible in that it combines two inputs to produce one output.

(Image Omitted)

To produce a network as shown in Fig. 2(a) that can combine N inputs to produce one output, there are two different ways that the network of Fig. 1 can be extended. It can be extended as shown in Fig. 2(b) by adding more nodes to the ring, to create a single ring with all N inputs, or it can be expanded as shown in Fig. 2(c) by creating a tree structure of 2-input, 1-output rings. The total number of inputs to the tree structure is 2L, where L is the number of levels in the network. By choosing L to be at least as large as log2N, the network is guaranteed to have at least N inputs. The disclosure is the observation that any size token ring can be used as an individual building block in creating a larger network. The advantage of building a network from rings that have a large number of nodes is that the number of gateways between rings in the network diminishes as the rings become longer. The difference in cost between the networks in Fig. 2(b) and 2(c) is essentially equal to the number of gateways that have been inserted in Fig. 2(c). On the other hand, the delay experienced by a message is greatest for a tree structure built from a single ring, so that the lowest-cost structure has the highest delay, and the network delay diminishes as the cost of th...