Browse Prior Art Database

Low-Cost Combining Switch That Implements a Multiprocessor Join

IP.com Disclosure Number: IPCOM000036166D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 5 page(s) / 45K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

This article describes a low-cost interconnection structure that prioritizes transactions produced by a collection of processors. It can perform the functions of the networks described in [1], [2] but uses a token-ring structure in lieu of a tree structure to achieve low-cost, possibly at a lower level of performance.

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

Page 1 of 5

Low-Cost Combining Switch That Implements a Multiprocessor Join

This article describes a low-cost interconnection structure that prioritizes transactions produced by a collection of processors. It can perform the functions of the networks described in [1], [2] but uses a token-ring structure in lieu of a tree structure to achieve low-cost, possibly at a lower level of performance.

Described in 1,2 is a multiprocessor data processing system based on an interconnection structure whose topology is a tree structure. The interconnection mechanism is capable of performing prioritization operations and other similar operations required to synchronize concurrently executing transactions. The idea presented here is similar in function but dramatically different in structure. The former structure uses a logic network whose structure supports high- performance, but whose cost and complexity can be rather substantial. The implementation described here is based on token-ring technology, which provides a very low-cost connection per node, but whose performance may be less than the performance of the network described in [1, 2]. The difference in performance is that the longest delay in the [1, 2,] network is proportional to the logarithm of the number of nodes, whereas the longest delay in the present invention is linearly proportional to the number of nodes. The excess delay of the new invention is not a serious defect for networks composed of a small number of nodes, and the lower cost of implementation may be a great advantage.

Fig. 1 shows the tree-structured network described in 1, 2. To prioritize requests, the requests are submitted at the leaf nodes shown at the bottom of the network. The basic idea is that an internal node receives requests from each of the nodes below it, and selects the request with the greater priority to pass to the node at the next higher level of the tree. In this manner, the request that eventually reaches the root node of the tree is the highest priority of all input requests. The network essentially turns around such a request and repeats the request to the two nodes immediately below the root, then to four of the nodes immediately below those nodes, etc., until the request reaches all leaf nodes. In this way, the network selects one request from among N Messages, and broadcasts that transaction to all processors. In the tree in Fig. 1, the nodes in the tree are marked with a digit indicating the priority of the request. The numbers in the node indicate how the highest priority request reaches the root node, prior to the pass from top to bottom in which that request is broadcast to all nodes.

This discussion demonstrates the ability to select and broadcast. How results from queries can be summarized within the network is shown in [2]. Suppose, for example, that some request has just been broadcast to all leaf nodes in the network. The objective is to return to the requester a summary of the responses. One poss...