Browse Prior Art Database

Synchronization Costs on Multiprocessors

IP.com Disclosure Number: IPCOM000128245D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 10 page(s) / 35K

Publishing Venue

Software Patent Institute

Related People

Anne Greenbaum: AUTHOR [+3]

Abstract

Various types of processor synchronization are introduced and analyzed with regard to execution time and waiting time. It is shown that while barrier synchronization requires a large execution time on systems with many processors, other less restrictive forms of synchronization do not have this drawback. It is also , shown that for most reasonable distributions of processor times, a relatively small amount of time is spent waiting at synchronization points. The conclusion is that if barriers can be replaced by the less restrictive synchronization forms, then, for problems with appropriate size granularity, the synchronization costs on most multiprocessors will be small.

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

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Synchronization Costs on Multiprocessors

by Anne Greenbaum

Ultracomputer Note #98 April, 1986 This work was supported in part by the Applied Mathematical Sciences Program of the US Department of Energy under contract DE-AC02- 76ER03077 and in part by contract number W-7405-ENG-4.8.

ABSTRACT

Various types of processor synchronization are introduced and analyzed with regard to execution time and waiting time. It is shown that while barrier synchronization requires a large execution time on systems with many processors, other less restrictive forms of synchronization do not have this drawback. It is also , shown that for most reasonable distributions of processor times, a relatively small amount of time is spent waiting at synchronization points. The conclusion is that if barriers can be replaced by the less restrictive synchronization forms, then, for problems with appropriate size granularity, the synchronization costs on most multiprocessors will be small.

1. Introduction

Considerable attention has been given to the problem of synchronizing multiprocessors. In particular, barrier synchronization has been analyzed [1] and shown to require significant execution time on systems with large numbers of processors. To avoid the extra cost of synchronizing processors, asynchronous algorithms have been developed [2,3]. In this paper we consider several forms of synchronization and estimate the time required in execution and in waiting at the synchronization points. The goal is to determine what the costs are for the various forms of synchronization and thereby to determine which form is best (when several different forms could be used) and under what circumstances it is worthwhile to pursue asynchronous algorithms. When an algorithm is implemented on several processors, there are usually points in the algorithm at which some processor must wait for data to be computed by other processors, before it can proceed with its own work. At such points, some type of processor synchronization is required. The processors computing the needed data must "announce" that it is ready, and the processor that needs this data must "check" to see if it is ready and wait until the check is affirmative before proceeding. Often barrier synchronization is used. A barrier is a point in a program at which all processors must arrive before any can proceed. While barrier synchronization is sometimes necessary, it can often be replaced by other less restrictive forms of synchronization. Consider, for example, the type of synchronization required in various iterative methods for solving sparse linear systems. If the linear system is denoted by Ax = b, then most iterative methods can be expressed in two stages:. Given an initial guess x0, compute r0 -b - Axe, and for m = 1,2,~, (1) Generate an approximate solution x'.

(2) Compute a residual

(Equation Omitted)

New York University Page 1 Dec 31, 1986

Page 2...