L12 & L13 Flashcards
How can we build concurrent data structure without locks?
Lock-free data structures
Which language is good for lock-free data structues?
Java because it has automated memory management
How can lock-free data structures result in an inconsistent state for enqueue?
CAS cannot perform 2 write accesses but enqueue needs to update tail.next and tail atomically
What does
if local_tail.next.compareAndSet(null, n)
do?
It keeps spinning until state is consistent.
True of false?
The lock-free approach is similar to the approach taken by load-linked/store-conditional.
True
What are the 2 main ideas for a lock-free approach? (what is done by the program)
1) a method saves the state of the lock-free data structure upon entry
2) the method responds appropriately depending on whether the state has changed or not
Why is implementing a lock-free data structure difficult in C/C++?
You never know when a dequeued node can be freed as another thread may still have a reference to it.
Which scales better: lock-free algorithms or lock-based algorithms?
Lock-free, but the code is harder to write
What are two standard parallel programming frameworks?
OpenMP (Open MultiProcessing)
MPI (Message Passing Interface)
What is MPI?
It is a set of basic functions used to create portable parallel applications, that relies on message passing for communication.
Can MPI be easily integrated into an exsiting application?
No, the application needs to be redesigned with MPI in mind to be ported.
What are ‘messages’ in the MPI framework?
rank of sending/receiving processes + tag for type
What functions are used to send and receive messages between processes?
MPI_Send and MPI_Recv functions
What are some collective operations in the MPI standard?
MPI_Barrier: barrier synchronisation
MPI_Bcast: broadcast
MPI_Scatter: broadcast parts of data to different processes
MPI_Gather: inverse of scatter
MPI_Reduce: a reduction operation
In MPI, the _______ operation is used to broadcast parts of data to different processes.
MPI_Scatter
