Software queue-based algorithms for pipelined synchronization on multiprocessors

Synchronization either ensures mutual exclusion on shared data or forces a processor to wait until a set of variables becomes a specific state; the latter is called conditional synchronization. We have improved the performance of mutual exclusion on multiprocessors by allowing processors to concurre...

Full description

Saved in:
Bibliographic Details
Main Author: Takesue, M.
Format: Conference Proceeding
Language:English
Subjects:
Computational modeling
Concurrent computing
Data structures
Delay
Hardware
Parallel processing
Permission
Pipeline processing
Software algorithms
Testing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Synchronization either ensures mutual exclusion on shared data or forces a processor to wait until a set of variables becomes a specific state; the latter is called conditional synchronization. We have improved the performance of mutual exclusion on multiprocessors by allowing processors to concurrently access different parts of shared data in a pipelined manner (Takesue, 2002). A special software tree of queue-tail pointers is the key scheme for the pipelining, but it requires other hardware schemes such as the queue distributed in the caches. This paper proposes software queue-based algorithms for pipelined synchronization only with the Fetch&Inc. as hardware support. We pipeline mutual exclusion by exploiting the software tree. Conditional synchronization is pipelined by declaring the semaphore as a data structure, and by simulating the P and V operations so that the V can be eagerly performed before accessing shared data. Evaluation results with an RTL (register transfer level) simulator show that as compared with hardware queue-based non-pipelined synchronization, the speedup of our pipelining reaches up to over 2.0 for large data in heavily contentious cases.
ISSN:1530-2016
2375-530X
DOI:10.1109/ICPPW.2003.1240361