13-Parallel Data Structures - III

1 .CSC2/458 Parallel and Distributed Systems Parallel Data Structures - III Sreepathi Pai March 1, 2018 URCS 

2 .Outline Some Non-Blocking Data Structures 

3 .Outline Some Non-Blocking Data Structures 

4 .The M&S Queue Handout: Pg 126 of MLS 

5 .Sequential semantics of a Queue • Enqueue • Prev tail node T → next points to new node N • Tail pointer points to node N • Dequeue (if queue is empty) • Returns empty • Dequeue (if queue is not empty) • Returns node H pointed to by head • New head points to node in H− > next 

6 .CAS names In enqueue: • CAS1: if CAS(&t.p->next) ... • CAS2: (void) CAS(&tail, t, <n.p, t.c+1>) • CAS3: (void) CAS(&tail, t, <w, t.c+1>) In dequeue • CAS4: (void) CAS(&tail, t, <n.p, t.c+1>) • CAS5: (void) if CAS(&head, h, <n.p, h.c+1>) • Which of these CASes enforce the semantics? • Which are the linearization points? 

7 .Memory Management in M&S Queue • new in enqueue • Why the fence(W||W)? • free for reuse in dequeue • What is this? • Could we not simply: rtn := n.p->val.load() if CAS(&head, h, <n.p, h.c+1>) fence(W||W) free(h.p) break 

8 .Memory Reclamation How do we prevent premature reclamation of allocated data? • while somebody is holding a reference to it? 

9 .Performance • No way to theoretically model the performance of these concurrent data structures yet. • in advance • Run microbenchmarks on concurrent data structures • measure throughput