A lock-free cache-friendly software queue buffer for decoupled software pipelining

Wen Ren Chen, Wuu Yang, Wei Chung Hsu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations


Multicore has become a trend on server and client computers in recent years. Parallelization is one way to fully utilize the computing power provided by multicore architectures. Most applications of interest have complex data and control dependency, which make traditional parallelization techniques, such as DOALL and DOACROSS, inapplicable. Decoupled Software Pipelining (DSWP), a new parallelization technique, shows its potential on parallelizing general applications. However, its success relies on fast inter-core synchronization and communication. On commodity multicore platforms, the performance of current DSWP disappoints us since the overhead involving lock-based, cache dishonored software approach offsets the benefit from DSWP. We present a lock-free, cache-friendly software queue designed for DSWP. A lock-free, cache-friendly solution need take two different aspects of memory system, memory coherence and memory consistency, into consideration.We show how inattention to these two aspects leads to incorrect or inefficient solutions. We also present our approach to providing a correct and efficient solution with detailed explanation. Due to the nondeterministic nature of parallel programs, traditional testing techniques cannot be used to fully verify the correctness of the implementation. We also discuss the correctness of our implementation both in informal and formal ways.

Original languageEnglish
Title of host publicationICS 2010 - International Computer Symposium
Number of pages10
StatePublished - 1 Dec 2010
Event2010 International Computer Symposium, ICS 2010 - Tainan, Taiwan
Duration: 16 Dec 201018 Dec 2010

Publication series

NameICS 2010 - International Computer Symposium


Conference2010 International Computer Symposium, ICS 2010


Dive into the research topics of 'A lock-free cache-friendly software queue buffer for decoupled software pipelining'. Together they form a unique fingerprint.

Cite this