Efficient Implementation of Concurrent Data Structures on Multi-core and Many-core Architectures

↓ Direkt till sidans innehåll
↓ Direkt till sidans sekundära innehåll (sidomenyn)

Search: id:"swepub:oai:research.chalmers.se:fcfc6c71-1785-4482-a5d7-5210f30174a2" > Efficient Implement...

1 of 1
Previous record
Next record
To hitlist

Details
MARC

Chatterjee, Bapi,1982Chalmers tekniska högskola,Chalmers University of Technology (author)

Efficient Implementation of Concurrent Data Structures on Multi-core and Many-core Architectures

BookEnglish2015

Publisher, publication year, extent ...

Gothenburg,2015
electronicrdacarrier

Numbers

LIBRIS-ID:oai:research.chalmers.se:fcfc6c71-1785-4482-a5d7-5210f30174a2
https://research.chalmers.se/publication/213279URI

Supplementary language notes

Language:English
Summary in:English

Part of subdatabase

SwePubSwePub

Classification

Subject category:lic swepub-publicationtype
Subject category:vet swepub-contenttype

Notes

Synchronization of concurrent threads is the central problem in order to design efficient concurrent data-structures. The compute systems widely available in market are increasingly becoming heterogeneous involving multi-core Central Processing Units (CPUs) and many-core Graphics Processing Units (GPUs). This thesis contributes to the research of efficient synchronization in concurrent data-structures in more than one way. It is divided into two parts. In the first part, a novel design of a Set Abstract Data Type (ADT) based on an efficient lock-free Binary Search Tree (BST) with improved amortized bounds of the time complexity of set operations - Add, Remove and Contains, is presented. In the second part, a comprehensive evaluation of concurrent Queue implementations on multi-core CPUs as well as many-core GPUs are presented. Efficient Lock-free BST -To the best of our knowledge, the lock-free BST presented in this thesis is the first to achieve an amortized complexity of O(H(n)+c) for all Set operations where H(n) is the height of a BST on n nodes and c is the contention measure. Also, the presented lock-free algorithm of BST comes with an improved disjoint-access-parallelism compared to the previously existing concurrent BST algorithms. This algorithm uses single-word compare-and-swap (CAS) primitives. The presented algorithm is linearizable. We implemented the algorithm in Java and it shows good scalability. Evaluation of concurrent data-structures - We have evaluated the performance of a number of concurrent FIFO Queue algorithms on multi-core CPUs and many-core GPUs. We studied the portability of existing design of concurrent Queues from CPUs to GPUs which are inherently designed for SIMD programs. We observed that in general concurrent queues offer them to efficient implementation on GPUs with faster cache memory and better performance support for atomic synchronization primitives such as CAS. To the best of our knowledge, this is the first attempt to evaluate a concurrent data-structure on GPUs.

Subject headings and genre

NATURVETENSKAP Data- och informationsvetenskap Datorteknik hsv//swe
NATURAL SCIENCES Computer and Information Sciences Computer Engineering hsv//eng
NATURVETENSKAP Data- och informationsvetenskap Programvaruteknik hsv//swe
NATURAL SCIENCES Computer and Information Sciences Software Engineering hsv//eng
NATURVETENSKAP Data- och informationsvetenskap Systemvetenskap, informationssystem och informatik hsv//swe
NATURAL SCIENCES Computer and Information Sciences Information Systems hsv//eng
NATURVETENSKAP Data- och informationsvetenskap Datavetenskap hsv//swe
NATURAL SCIENCES Computer and Information Sciences Computer Sciences hsv//eng
TEKNIK OCH TEKNOLOGIER Elektroteknik och elektronik Datorsystem hsv//swe
ENGINEERING AND TECHNOLOGY Electrical Engineering, Electronic Engineering, Information Engineering Computer Systems hsv//eng
Lock-free
Lock-free Binary search tree
Synchronization Primitives
Concurrent Data Structures

Added entries (persons, corporate bodies, meetings, titles ...)

Chalmers tekniska högskola (creator_code:org_t)

Internet link

Find in a library

Efficient Implementation of Concurrent Data Structures on Multi-core and Many-co... (Search the publication in LIBRIS)

To the university's database

1 of 1
Previous record
Next record
To hitlist

Find more in SwePub

By the author/editor: Chatterjee, Bapi ...

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Computer and Inf ...; and Computer Enginee ...

NATURAL SCIENCES: NATURAL SCIENCES; and Computer and Inf ...; and Software Enginee ...

NATURAL SCIENCES: NATURAL SCIENCES; and Computer and Inf ...; and Information Syst ...

NATURAL SCIENCES: NATURAL SCIENCES; and Computer and Inf ...; and Computer Science ...

ENGINEERING AND TECHNOLOGY: ENGINEERING AND ...; and Electrical Engin ...; and Computer Systems

By the university: Chalmers University of Technology

Search outside SwePub

Extend your search to:: Google; Google Book Search; Google Scholar

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

LIBRIS.kb.se