Browse Prior Art Database

Device for Synchronizing Multiple Processors

IP.com Disclosure Number: IPCOM000037258D
Original Publication Date: 1989-Dec-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 4 page(s) / 19K

Publishing Venue

IBM

Related People

Heidelberger, P: AUTHOR [+2]

Abstract

A module capable of performing up to K synchronizing operations in a single request/response cycle, where K is smaller than N, the number of processors in a multiprocessor system, is described. The objective is to provide for parallel synchronization to the degree that it is expected to be useful, but not to the degree that supports fully parallel synchronization of all processors in a system, which is far more costly to implement.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 27% of the total text.

Page 1 of 4

Device for Synchronizing Multiple Processors

A module capable of performing up to K synchronizing operations in a single request/response cycle, where K is smaller than N, the number of processors in a multiprocessor system, is described. The objective is to provide for parallel synchronization to the degree that it is expected to be useful, but not to the degree that supports fully parallel synchronization of all processors in a system, which is far more costly to implement.

The synchronizing operation of interest is the Fetch-and-Add operation described by [1]. This operation is a rather general operation that adds a given increment to memory and returns the prior value of the addend. It is most likely to be used in the form Fetch-and-Increment, which adds 1 or subtracts 1 from an addend instead of adding a given operand to the addend. The restriction to the addition or subtraction of 1 simplifies the logic circuit and allows more processors to be treated concurrently at a given cost of logic or chip area.

The purpose of this device is to implement efficient synchronization of the following functions: 1. barrier synchronization, and

2. serialization (prioritization) of multiple requests

in parallel.

A barrier synchronization is a point in a program that all processes in a set of processes must reach before any process in the set can pass the barrier. A serialization operation is an operation that assigns a unique integer to each of multiple simultaneous requests. The integer assigned can be interpreted as the priority of the process or can be used to assign each process a unique set of system resources. The objective of serialization is to do this operation in parallel in constant time rather than in a time proportional to the number of requests received.

Other techniques exist for implementing the synchronization functions above. Gottlieb et al. 1 demonstrated how to do these operations with Fetch-and-Add. A cache-coherency protocol such as those described in 2 is also sufficiently powerful to implement these functions. However, for these cache-coherence protocols, the barrier synchronization will cause a potentially large number of memory references. A device for barrier sychronization of N processors is described in 3. The device described here advances the art taught by 3 by incorporating the ability to select K of N requests to update, and to provide for serialization of requests. Lipovski and Vaughn 4 describe an implementation of Fetch-and-Add that does essentially what the combining network of [1] does, but does the arithmetic operations serially by bit in order to reduce the cost of the network. The new device is an advance over this art in that it incorporates a broadcast bus for transmitting global information and in that it provides for parallel responses to just K of N processors. It reduces the number of interconnections required on a VLSI implementation of a synchronization device because of these factors. The All...