Browse Prior Art Database

Enhanced Means for Parallel Synchronization in Crossbar Switching Networks

IP.com Disclosure Number: IPCOM000035188D
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 3 page(s) / 47K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR [+2]

Abstract

This article describes a means for combining requests in parallel in crossbar switching networks. A technique for parallel synchronization based on the use of an instruction called Fetch-and-Add coupled with a network of switches of a type known as a combining switch is presented in [*]. Although this proposal has the potential of removing a class of synchronization bottlenecks that appear in multiprocessor networks, it has two disadvantages - high cost and many levels of logic delay.

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

Page 1 of 3

Enhanced Means for Parallel Synchronization in Crossbar Switching Networks

This article describes a means for combining requests in parallel in crossbar switching networks. A technique for parallel synchronization based on the use of an instruction called Fetch-and-Add coupled with a network of switches of a type known as a combining switch is presented in [*]. Although this proposal has the potential of removing a class of synchronization bottlenecks that appear in multiprocessor networks, it has two disadvantages - high cost and many levels of logic delay.

Other methods are known that overcome some of the disadvantages of the proposal in [*] by implementing some of the actions of the Fetch- and-Add in software rather than in hardware. Other work shows: 1. a hardware method for synchronization coupled with a software technique for combining, 2. an adaptation of the synchronization method suitable for crossbar switches, and 3. a different adaptation of the idea for multilevel switching networks.

This article describes an enhancement of the above technique for crossbar switches. The enhancement extends crossbar synchronization from synchronizing two requests to synchronizing multiple requests. The enhancement should reduce network overhead for little additional network cost.

A synchronizer is shown in the figure, and the interconnection network is a crossbar network that routes requests from the N processors to the N synchronizer modules. Each synchronizer returns one of three responses to synchronization requests that it receives. 1. No Synch. No other processor is attempting to synchronize at the same synch address in the current cycle. 2. Synch Wait. Another processor is attempting to synchronize at the same synch address. Suspend this processor's activity immediately, and wait for the other processor to release this processor before proceeding. 3. Synch Continue. Another processor is attempting to synchronize at the same synch address. That processor has suspended its activity and is waiting for this processor to release it.

In the original formulation, exactly one response is returned and it is one of the three. The new invention produces a sequence of re sponses. The responses are: 1. No Synch 2. Synch Wait 3. Synch Continue which are the same messages as before with the same mea...