Global synchronization algorithms for the Intel iPSC/860

Seidel, Steven R.; Davis, Mark A.

In a distributed memory multicomputer that has no global clock, global processor synchronization can only be achieved through software. Global synchronization algorithms are used in tridiagonal systems solvers, CFD codes, sequence comparison algorithms, and sorting algorithms. They are also useful for event simulation, debugging, and for solving mutual exclusion problems. For the Intel iPSC/860 in particular, global synchronization can be used to ensure the most effective use of the communication network for operations such as the shift, where each processor in a one-dimensional array or ring concurrently sends a message to its right (or left) neighbor. Three global synchronization algorithms are considered for the iPSC/860: the gysnc() primitive provided by Intel, the PICL primitive sync0(), and a new recursive doubling synchronization (RDS) algorithm. The performance of these algorithms is compared to the performance predicted by communication models of both the long and forced message protocols. Measurements of the cost of shift operations preceded by global synchronization show that the RDS algorithm always synchronizes the nodes more precisely and costs only slightly more than the other two algorithms.

Document ID

19930023172

Acquisition Source

Legacy CDMS

Document Type

Contractor Report (CR)

Authors

Date Acquired

September 6, 2013

Publication Date

August 11, 1992

Subject Category

Report/Patent Number

Accession Number

93N32361

Funding Number(s)

Distribution Limits

Public

Work of the US Gov. Public Use Permitted.

Available Downloads

Name

Type

19930023172.pdf

STI

No Preview Available

NTRS

NTRS - NASA Technical Reports Server

Available Downloads

Related Records