Sequential Searching in Multidimensional Monotone Arrays
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 sever congestion in the network. We propose a class of adaptive backoff 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 of 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1989
- Accession Number
- ADA211938
Entities
People
- Alok Aggarwal
- James K. Park
Organizations
- Massachusetts Institute of Technology