CSC/ECE 506 Spring 2011/ch5 LL

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.

References

• Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.
• David E. Culler, Jaswinder Pal Singh, and Anoop Gupta, Parallel Computer Architecture: A Hardware/Software Approach, Gulf Professional Publishing, August 1998.
• Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, "Thread scheduling for multiprogrammed multiprocessors (1998)" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.130.3853
• Wikipedia, NonBlocking http://en.wikipedia.org/wiki/Non-blocking_algorithm
• Wikipedia, ABA http://en.wikipedia.org/wiki/ABA_problem
• Wikipedia, Hazard http://en.wikipedia.org/wiki/Hazard_pointer
• Wikipedia, CAS http://en.wikipedia.org/wiki/Compare-And-Swap
• Wikipedia, LLSC http://en.wikipedia.org/wiki/Load-Link/Store-Conditional
• GCC, Atomic builtins http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html#Atomic-Builtins

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;