A hardware implementation of the MCAS synchronization primitive

Lock-based parallel programs are easy to write. However, they are inherently slow as the synchronization is blocking in nature. Non-blocking lock-free programs, which use atomic instructions such as compare-and-set (CAS), are significantly faster. However, lock-free programs are notoriously difficul...

Full description

Saved in:
Bibliographic Details
Main Authors: Patel, Srishty, Kalayappan, Rajshekar, Mahajan, Ishani, Sarangi, Smruti R.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Cathode ray tubes
Data structures
Hardware
Pipelines
Protocols
Synchronization
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Lock-based parallel programs are easy to write. However, they are inherently slow as the synchronization is blocking in nature. Non-blocking lock-free programs, which use atomic instructions such as compare-and-set (CAS), are significantly faster. However, lock-free programs are notoriously difficult to design and debug. This can be greatly eased if the primitives work on multiple memory locations instead of one. We propose MCAS, a hardware implementation of a multi-word compare-and-set primitive. Ease of programming aside, MCAS-based programs are 13.8X and 4X faster on an average than lock-based and traditional lock-free programs respectively. The area overhead, in a 32-core 400mm 2 chip, is a mere 0.046%.
ISSN:1558-1101
DOI:10.23919/DATE.2017.7927120