CSC/ECE 506 Spring 2011/ch5 LL: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
=Supplement to Chapter 5: | =Supplement to Chapter 5: Parallel Programming For Linked Data Structures= | ||
==Introduction== | ==Introduction== | ||
Chapter 5 of [[#References | Solihin (2008)]] discusses parallel algorithms for operating on Linked data structures. The focus is primarily on thread-safe accesses based on locks. The semantics of locks imply that a single thread can access the data structure at any given time. The chapter discusses optimizations such as finer grained locks and read-write locks to enable more parallelization. All these approaches are fundamentally blocking in nature since the building block is a lock which has blocking semantics. This supplements discusses non-blocking algorithms to access linked data structures and the related issues. | |||
=Non blocking algorithms= | =Non blocking algorithms= | ||
| Line 16: | Line 17: | ||
==Linked list example of use of barrier instructions== | ==Linked list example of use of barrier instructions== | ||
=Skip lists= | =Skip lists= | ||
=References= | =References= | ||
* Yan Solihin, ''Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems'', Solihin Books, August 2009. | |||
=Appendix= | =Appendix= | ||
// Sequential code, from [[#References|Solihin (2008), p. 25.]] | |||
for (i = 0; i < 8; i++) | |||
a[i] = b[i] + c[i]; | |||
sum = 0; | |||
for (i = 0; i < 8; i++) | |||
if (a[i] > 0) | |||
sum = sum + a[i]; | |||
Print sum; | |||
Revision as of 16:04, 27 February 2011
Supplement to Chapter 5: Parallel Programming For Linked Data Structures
Introduction
Chapter 5 of Solihin (2008) discusses parallel algorithms for operating on Linked data structures. The focus is primarily on thread-safe accesses based on locks. The semantics of locks imply that a single thread can access the data structure at any given time. The chapter discusses optimizations such as finer grained locks and read-write locks to enable more parallelization. All these approaches are fundamentally blocking in nature since the building block is a lock which has blocking semantics. This supplements discusses non-blocking algorithms to access linked data structures and the related issues.
Non blocking algorithms
Motivation
categories
building blocks
Lock-free linked list implementation
Pop-only case
Push-Pop case aka the ABA problem
Tag-based solution
DCAS based solutions
Memory model and barrier instructions
The X86 memory model
Barrier instructions
Linked list example of use of barrier instructions
Skip lists
References
- Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.
Appendix
// Sequential code, from Solihin (2008), p. 25.
for (i = 0; i < 8; i++)
a[i] = b[i] + c[i];
sum = 0;
for (i = 0; i < 8; i++)
if (a[i] > 0)
sum = sum + a[i];
Print sum;