Category: Education

Presentation Description

No description available.


Presentation Transcript

NOBLE: A Non-Blocking Inter-Process Communication Library: 

NOBLE: A Non-Blocking Inter-Process Communication Library Håkan Sundell Philippas Tsigas Computing Science Chalmers University of Technology


Systems Multi-processor systems: cache-coherent shared memory UMA NUMA Desktop computers


Synchronization A significant part of the work performed by today’s parallel applications is spent on synchronization Mutual exclusion (Locks) Blocking Convoy effects Deadlocks

Convoy effects: 

Convoy effects The slowdown of one process may cause the whole system to slowdown


Research Non-blocking synchronization has been researched since the 70’s Lock-free Wait-free Non-blocking are based on usage of atomic synchronization primitives shared memory

Non-blocking Synchronization: 

Non-blocking Synchronization Lock-Free Synchronization Retries until not interfered by other operations Usually detecting interference by using some kind of shared variable indicating busy-state or similar. Guarantees live-ness but not starvation-free. Change flag to unique value, or remember current state ... do the operation while preserving the active structure ... Check for same value or state and then validate changes , otherwise retry

Non-blocking Synchronization: 

Non-blocking Synchronization Wait-free synchronization All concurrent operations can proceed independently of the others. Every process always finishes the protocol in a bounded number of steps, regardless of interleaving No starvation


Practice Non-blocking synchronization is still not used in many practical applications Non-blocking solutions are often complex having non-standard or un-clear interfaces non-practical Many results show that non-blocking improves the performance of parallel applications significantly… ? ?

Non-blocking Synchronization – Practice: 

Non-blocking Synchronization – Practice P. Tsigas, Y. Zhang “Evaluating the Performance of Non-Blocking Synchronization on Modern Shared Memory Multiprocessors”, ACM Sigmetrics 2001


Schedule Goals Design Examples Experiments Status Conclusions and Future work NOBLE: Brings Non-blocking closer to Practice


Goals Create a non-blocking inter-process communication interface that have these properties: Attractive functionality Programmer friendly Easy to adapt existing solutions Efficient Portable Adaptable for different programming languages

Design: Attractive functionality: 

Design: Attractive functionality Data structures for multi-threaded usage Queues. Stacks. Singly linked lists. Snapshots. Data structures for multi-process usage Shared Register. Clear specifications enqueue and dequeue push and pop first, next, insert, delete and read update and scan read and write

Design: Programmer friendly: 

Design: Programmer friendly Hide the complexity as much as possible! Just one include file Simple naming convention: Every function is beginning with the NBL characters #include <Noble.h> NBLQueueEnqueue() NBLQueueDequeue() …

Design: Easy to adapt solutions: 

Design: Easy to adapt solutions Support lock-based as well as non-blocking solutions. Several different create functions Unified functions for the operations, independent of the synchronization method  NBLQueue *NBLQueueCreateLF(); NBLQueue *NBLQueueCreateLB(); NBLQueueFree(handle); NBLQueueEnqueue(handle,item); NBLQueueDequeue(handle);

Design: Efficient: 

Design: Efficient To minimize overhead, usage of function pointers In-line redirection typedef struct NBLQueue { void *data; void (*free)(void *data); void (*enqueue)(void *data,void *item); void *(*dequeue)(void *data); } NBLQueue; #define NBLQueueFree(handle) (handle->free(handle->data)) #define NBLQueueEnqueue(handle,item) (handle-> enqueue(handle->data,item)) #define NBLQueueDequeue(handle) (handle->dequeue(handle->data))

Design: Portable: 

Design: Portable CAS, TAS, Spin-Locks … SunHardware.asm CAS, TAS, Spin-Locks ... IntelHardware.asm . . . . . . Platform dependent Platform in-dependent Exported definitions Identical on all platforms

Design: Adaptable for different programming languages: 

Design: Adaptable for different programming languages Implemented in C, all compiled into a library file. C++ compatible include files and easy to make C++ wrappers class NOBLEQueue { private: NBLQueue* queue; public: NOBLEQueue(int type) {if(type==NBL_LOCKFREE) queue=NBLQueueCreateLF(); else … } ~NOBLEQueue() {NBLQueueFree(queue);} inline void Enqueue(void *item) {NBLQueueEnqueue(queue,item);} ...


Examples When the data structure is not in use anymore: First create a global variable handling the shared data object, for example a stack: Create the stack with the appropriate implementation: When some thread wants to do some operation:


Examples To change the synchronization mechanism, only one line of code has to be changed!


Experiment Set of 50000 random operations performed multithreaded on each data structure, with either low or high contention Comparing the different synchronization mechanisms and implementations available Varying number of threads from 1 – 30 Performed on multiprocessors: Sun Enterprise 10000 with 64 CPUs, Solaris Compaq PC with 2 CPUs, Win32

Experiments: Linked List: 

Experiments: Linked List Lock-Free nr.1 – J. Valois “Lock-Free Data Structures” Ph.D-thesis 1995. Lock-Free nr.2 - T. Harris “A Pragmatic Implementation of Non-Blocking Linked Lists.” 2001 Symposium on Distributed Computing. Lock-Based – Spin-locks (Test-And-Set).

Experiments: Linked List (high): 

Experiments: Linked List (high)

Experiments: Linked List (low): 

Experiments: Linked List (low)

Experiments: Linked List (high) - Threads: 

Experiments: Linked List (high) - Threads

Experiments: Queues: 

Experiments: Queues Lock-Free nr.1 – J. Valois “Lock-Free Data Structures” Ph.D-thesis 1995. Lock-Free nr.2 - P. Tsigas, Y. Zhang “A Simple, Fast and Scalable Non-Blocking Concurrent FIFO queue for Shared Memory Multiprocessor Systems”, ACM SPAA’01, 2001. Lock-Based – Spin-locks (Test-And-Set).

Experiments: Queues (high): 

Experiments: Queues (high)

Experiments: Queues (low): 

Experiments: Queues (low)

Experiments: Queues (high) - Threads: 

Experiments: Queues (high) - Threads


Status Multiprocessor support Sun Solaris (Sparc) Win32 (Intel x86) SGI (Mips) – Testing phase Linux (Intel x86) – Testing phase Extensive Manual Web site up and running,

Conclusions and Future work: 

Conclusions and Future work NOBLE: Easy to use, efficient and portable Non-blocking protocols always performs better than or similar to lock-based, especially on multi-processor systems. To do: Use in real parallel applications Extend with more shared data object implementations Extend to other platforms, especially suitable for real-time systems

authorStream Live Help