56 %
44 %
Information about LCR02

Published on February 15, 2008

Author: Sigfrid


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:  Systems Multi-processor systems: cache-coherent shared memory UMA NUMA Desktop computers Synchronization:  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:  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:  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 Slide10:  Schedule Goals Design Examples Experiments Status Conclusions and Future work NOBLE: Brings Non-blocking closer to Practice Goals:  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:  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:  Examples To change the synchronization mechanism, only one line of code has to be changed! Experiment:  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:  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

Add a comment

Related presentations

Related pages

LCR 02 -

Hier sollte eine Beschreibung angezeigt werden, diese Seite lässt dies jedoch nicht zu.
Read more

Gourmet Berner Cremecafe Likör, 17%vol., 0,2 -

LCR02: Lieferumfang 1x Cremecafe Likör, 17%vol., 0,2 Lebensmittel Information. Lebensmittelbezeichnung: Likör Crème Caf ...
Read more

faq lcr-02-36M -

9453 9287-10. Title: faq_lcr-02-36M Author: HIOKI Created Date: 6/11/2013 6:03:26 PM
Read more

ProgRama LCR02 Range Rover Lowering Module

LCR02 Range Rover Lowering Module ... Data included as a reference only. ProgRama Inc. is not responsible for any exclusion or incorrect data as result of ...
Read more

Dexter the Bear - Funky Kits

Dexter the Bear [LCR02] £4.95 In Stock: Based on the adorable "Little Cotton Rabbits" by Julie . Untrimmed Grey Rubber . Acrylic Block required - either ...
Read more

PW Rate Skilled LCR02-2015fbLoc24(Day) Page

Prevailing Wage Rate Skilled Crafts ... Change # : LCR02-2015fbLoc24(Day) Craft : Sheet Metal Worker Effective Date : 07/01/2015 Last Posted : 07/01/2015. BHR.
Read more

PW Rate Skilled LCR02-2015fbLoc246VDV Page

Prevailing Wage Rate Skilled Crafts Name of Union: Electrical Local 246 Voice Data Video
Read more

[RPIF-Bestandsverzeichnis: Mond - Bildmaterial 1: Mond ...

LCr02 Nordöstlicher Kraterrand des Kraters King (Apollo-Aufnahme: AS16-1579M) LCr03 Krater King (Apollo-Aufnahme: AS16-19580H) LCr04 Krater im Hochland ...
Read more

ProgRama LCR02 zRange Rover Lowering Module

LCR02 zRange Rover Lowering Module ... Range Rover LM: 2007-2011: Range Rover LM 4.2: 2006: Range Rover RL3: 2005-2009: Range Rover Sport
Read more