Date: Wednesday, 20-Nov-96 20:04:46 GMT
Server: NCSA/1.3
MIME-version: 1.0
Content-type: text/html
Last-modified: Friday, 11-Oct-96 15:30:22 GMT
Content-length: 6317
High-Performance Synchronization
NSF grant CCR-9319445
High-Performance Synchronization for Shared-Memory Parallel Programs
Computer Science Department
University of Rochester
Rochester, NY 14627-0226
4-1-94 through 9-30-97
With increases in the size and availability of parallel processors with
shared-memory programming models, high-performance synchronization is
becoming increasingly important.
Several groups, including ours, have demonstrated in recent years that
software synchronization algorithms can scale well to very large
numbers of processors, and that they can avoid certain negative
interactions with high-performance scheduling algorithms.
We are continuing this research in several directions, including
(1) mechanisms for cooperative synchronization and scheduling,
which minimize unnecessary spinning, maximize processor locality, and
avoid contention for both lock and non-lock data;
(2) comparative evaluation of alternative mechanisms for atomic update of
shared data structures, including locks, non-blocking synchronization,
and function shipping;
(3) implementation of atomic hardware primitives on scalable
architectures;
(4) evaluation of the interaction of synchronization with coherence; and
(5) new synchronization algorithms.
Principal Investigator
Michael L. Scott
Associate Professor and Department Chair
scott@cs.rochester.edu
716-275-7745
Recent Graduates
Graduate Students
Publications
Pseudocode
-
Scalable spinlocks and barriers.
Includes test-and-set and ticket locks; queue locks; and
centralized, tree-based, and fft-style (``butterfly'') barriers.
From the 1991 TOCS paper.
-
Scalable busy-wait reader-writer locks.
Includes reader-preference, writer-preference, and fair locks.
From the 1991 PPoPP paper.
-
Scalable adaptive combining tree barriers.
Combine local-only spinning, logarithmic critical paths, amortization of
overhead for skewed arrival, and ``fuzziness''.
From the 1994 IJPP paper.
-
Variations on Lamport's fast mutual exclusion lock. Use no atomic
instructions other than read and write.
From UR TR 460 (submitted for publication).
-
Preemption-safe and scheduler-conscious synchronization algorithms.
Includes two queue-based mutual exclusion locks; test-and-set and ticket
locks; a fair, scalable, queue-based reader-writer lock; competitive and
optimal-time small-scale barriers; and a scalable barrier.
All algorithms avoid busy-waiting for action by preempted processes,
including those waiting in line for a FIFO queue or ticket lock. Most
employ a widened kernel-user interface.
Revised from UR TR 550; to appear in ACM TOCS.
-
A highly-concurrent multi-lock concurrent priority queue.
Uses bottom-up insertions and ``bit-reversal'' choice among fringe nodes.
-
Fast concurrent queue algorithms.
We believe these algorithms to be the best concurrent queues available,
for almost any application.
Executable Code
Last Change: 23 August 1996 /
scott@cs.rochester.edu