Accession Number : ADA211940


Title :   Adaptive Backoff Synchronization Techniques


Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE


Personal Author(s) : Agarwal, Anant ; Cherian, Mathews


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a211940.pdf


Report Date : Jul 1989


Pagination or Media Count : 23


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.


Descriptors :   *NETWORKS , *SYNCHRONIZATION(ELECTRONICS) , *MULTIPROCESSORS , *SHARING , *MEMORY DEVICES , VARIABLES , COSTS , CONGESTION , PARALLEL ORIENTATION , HIGH RATE , REDUCTION , INTENSITY , TRAFFIC , TRADE OFF ANALYSIS , BARRIERS


Subject Categories : Computer Hardware
      Test Facilities, Equipment and Methods
      Command, Control and Communications Systems


Distribution Statement : APPROVED FOR PUBLIC RELEASE