Accession Number:

ADA211940

Title:

Adaptive Backoff Synchronization Techniques

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1989-07-01

Pagination or Media Count:

23.0

Abstract:

Shared-memory multiprocessors commonly use shared variables for synchronization. Our simulations of real parallel applications show that large- scale cache-coherent multiprocessors suffer significant amounts of invalidation traffic due to synchronization. Large multiprocessors that do not cache synchronization variables are often more severely impacted. If this synchronization traffic is not reduced or managed adequately, synchronization references can cause severe congestion in the network. We propose a class of adaptive backkoff methods that do not use any extra hardware and can significantly reduce the memory traffic to synchronization variables. These methods use synchronization state to reduce polling of synchronization variables. Our simulations show that when the number of processors participating in a barrier synchronization is small compared to the time of arrival of the processors, reductions fo 20 percent to over 95 percent in synchronization traffic can be achieved at no extra cost. In other situations adaptive backoff techniques result in a tradeoff between reduced network accesses and increased processor idle time.

Subject Categories:

  • Computer Hardware
  • Test Facilities, Equipment and Methods
  • Command, Control and Communications Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE