LCR02

Information about LCR02

Published on February 15, 2008

Author: Sigfrid

Source: authorstream.com

Content

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, http://www.cs.chalmers.se/~noble 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

Related presentations


Other presentations created by Sigfrid

Diabetes Mellitus
29. 02. 2008
0 views

Diabetes Mellitus

bus108 pp 08spr
08. 05. 2008
0 views

bus108 pp 08spr

Ch01
07. 05. 2008
0 views

Ch01

Steenburgh
02. 05. 2008
0 views

Steenburgh

107249 firstfileFILE
02. 05. 2008
0 views

107249 firstfileFILE

Regional Roadshows generic
30. 04. 2008
0 views

Regional Roadshows generic

PE3 U2 R
24. 04. 2008
0 views

PE3 U2 R

Hydrogen Workshop
22. 04. 2008
0 views

Hydrogen Workshop

GW052307MS3Rv3Final
21. 04. 2008
0 views

GW052307MS3Rv3Final

0329
18. 04. 2008
0 views

0329

3 Johnson BMGs
10. 01. 2008
0 views

3 Johnson BMGs

Packaging
10. 01. 2008
0 views

Packaging

HIV AIDS PM
12. 01. 2008
0 views

HIV AIDS PM

PM Insv01
12. 01. 2008
0 views

PM Insv01

ISECON 2006 Sharp
13. 01. 2008
0 views

ISECON 2006 Sharp

Asthma 10 02
14. 01. 2008
0 views

Asthma 10 02

Panda life
15. 01. 2008
0 views

Panda life

Extinction
15. 01. 2008
0 views

Extinction

Empirical Formula
16. 01. 2008
0 views

Empirical Formula

Earth Resources
16. 01. 2008
0 views

Earth Resources

religion 1
17. 01. 2008
0 views

religion 1

020607 AmbassadorBriefing
21. 01. 2008
0 views

020607 AmbassadorBriefing

Christmas Sing along
15. 01. 2008
0 views

Christmas Sing along

Courseintro
04. 02. 2008
0 views

Courseintro

FAQ Presentation
24. 01. 2008
0 views

FAQ Presentation

CMS update
12. 02. 2008
0 views

CMS update

Brian Steele
28. 01. 2008
0 views

Brian Steele

crypto f05 s2
29. 01. 2008
0 views

crypto f05 s2

writing varner
06. 02. 2008
0 views

writing varner

The Maya
07. 02. 2008
0 views

The Maya

Fichner Rathus CH12
12. 02. 2008
0 views

Fichner Rathus CH12

bristol
14. 02. 2008
0 views

bristol

pps 310
14. 02. 2008
0 views

pps 310

burton RESTEasy
21. 02. 2008
0 views

burton RESTEasy

Glaucoma
25. 02. 2008
0 views

Glaucoma

festival on a budget
27. 02. 2008
0 views

festival on a budget

Projection Systems Ortho and Iso
09. 01. 2008
0 views

Projection Systems Ortho and Iso

Slide Presentation
28. 02. 2008
0 views

Slide Presentation

Age Of Enlightenment
03. 03. 2008
0 views

Age Of Enlightenment

JobPostings
11. 03. 2008
0 views

JobPostings

ESCI101 26 Groundwater1
12. 03. 2008
0 views

ESCI101 26 Groundwater1

79 3843 6 1950s Powerpoint
19. 03. 2008
0 views

79 3843 6 1950s Powerpoint

Operating Systems ofthe Home
10. 01. 2008
0 views

Operating Systems ofthe Home

climate transport brazil
25. 03. 2008
0 views

climate transport brazil

garetiree
07. 02. 2008
0 views

garetiree

LUENTO3Embryo development
10. 03. 2008
0 views

LUENTO3Embryo development

Woolly Monkey Research
31. 03. 2008
0 views

Woolly Monkey Research

nixonforeignpolicy JoshR BenK
03. 04. 2008
0 views

nixonforeignpolicy JoshR BenK

bahai
07. 04. 2008
0 views

bahai

Chapter 13 Global Clim
27. 03. 2008
0 views

Chapter 13 Global Clim

nach31d fuzeon vortr
28. 03. 2008
0 views

nach31d fuzeon vortr

d04 vp matousek
15. 04. 2008
0 views

d04 vp matousek

red binder pages
14. 04. 2008
0 views

red binder pages

KULDA Training 0405
23. 01. 2008
0 views

KULDA Training 0405

3 eReturn to work
29. 01. 2008
0 views

3 eReturn to work

slides trouble with tanning beds
04. 02. 2008
0 views

slides trouble with tanning beds

faith based focus group
13. 01. 2008
0 views

faith based focus group

pogorelova
14. 02. 2008
0 views

pogorelova

2 Trevor
16. 01. 2008
0 views

2 Trevor

goldstein 6th c7 editedW06
14. 01. 2008
0 views

goldstein 6th c7 editedW06

scenarios candice
28. 01. 2008
0 views

scenarios candice

histrespr2007
28. 01. 2008
0 views

histrespr2007

MontrealEngineering5 5 03
25. 01. 2008
0 views

MontrealEngineering5 5 03

ithaca presentation
17. 01. 2008
0 views

ithaca presentation

rapport medarbetarenkat 06
07. 02. 2008
0 views

rapport medarbetarenkat 06

2hmr theme1
15. 01. 2008
0 views

2hmr theme1

almy ieee
11. 01. 2008
0 views

almy ieee

DAMM Presentation Businet
13. 01. 2008
0 views

DAMM Presentation Businet

odrecva
05. 02. 2008
0 views

odrecva

Lecture4metabolism
23. 01. 2008
0 views

Lecture4metabolism

20060608 NAT2006
20. 02. 2008
0 views

20060608 NAT2006

Amarger Hitachi
08. 04. 2008
0 views

Amarger Hitachi

ERMSAR COMET S2 5
16. 01. 2008
0 views

ERMSAR COMET S2 5

Tim Riedel
24. 01. 2008
0 views

Tim Riedel

jmajor022206
11. 02. 2008
0 views

jmajor022206