CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Reactive Concurrent Data Structures and Algorithms for Synchronization

Phuong Ha (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers))
Göteborg : Chalmers University of Technology, 2006. ISBN: 91-7291-780-6.- 169 pages s.

Parallelism plays a significant role in high-performance computing systems, from large clusters of computers to chip-multithreading (CMT) processors. Performance of the parallel systems comes not only from concurrently running more processing hardware but also from utilizing the hardware efficiently. The hardware utilization is strongly influenced by how processors/processes are synchronized in the system to maximize parallelism. Synchronization between concurrent processes usually relies on shared data structures. The data structures that enhance parallelism by allowing processes to access them concurrently are known as "concurrent data structures". The thesis aims at developing efficient concurrent data structures and algorithms for synchronization in asynchronous shared-memory multiprocessors. Generally speaking, simple data structures perform well in the absence of contention but perform poorly in high-contention situations. Contrarily, sophisticated data structures that can scale and perform well in the presence of high contention usually suffer unnecessary high latency when there is no contention. Efficient concurrent data structures should be able to adapt their algorithmic complexity to varying contention. This has motivated us to develop fundamental concurrent data structures like trees, multi-word compare-and-swap and locks into reactive ones that timely adapt their size or algorithmic behavior to the contention level in execution environments. While the contention is varying rapidly, the reactive data structures must keep the cost of reaction below its benefit, avoiding unnecessary reaction due to the contention oscillation. This is quite challenging since the information of how the contention will vary in the future is usually not available in multiprogramming multiprocessor environments. To deal with the uncertainty, we have successfully synthesized non-blocking synchronization techniques and advanced on-line algorithmic techniques, in the context of reactive concurrent data structures. On the other hand, we have developed a new optimal on-line algorithm for one-way trading with time-varying exchange-rate bounds. The algorithm extends the set of practical problems that can be transformed to the one-way trading so as to find an optimal solution. In this thesis, the new algorithm demonstrates its applicability by solving the freshness problem in the context of concurrent data structures.

Nyckelord: synchronization, reactive, non-blocking, concurrent data structures, distributed data structures, multi-word atomic primitives, spin-locks, shared memory, online algorithms, online financial problems, randomization

Since some of the papers included in this thesis have been published, the copyright has been transferred to the respective publishing houses. The following is ACM's copyright notice. The other publishers have similar ones. Copyright © XXXX by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.

Denna post skapades 2006-08-25. Senast ändrad 2013-09-25.
CPL Pubid: 20006


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers) (2005-2007)



Chalmers infrastruktur

Relaterade publikationer

Inkluderade delarbeten:

Reactive multi-word synchronization for multiprocessors

Reactive multi-word synchronization for multiprocessors

Self-tuning Reactive Distributed Trees for Counting and Balancing

Efficient Multi-Word Locking Using Randomization

One-Way Trading with Time-Varying Exchange Rate Bounds

Competitive Freshness Algorithms for Wait-free Data Objects

Reactive Spin-locks: A Self-tuning Approach


Datum: 2006-06-02
Tid: 10.00
Lokal: 10.00 Hall EA, Rännvägen 6B, Chalmers
Opponent: Prof. Michael L. Scott, University of Rochester, USA.

Ingår i serie

Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie 2462

Technical report D - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University 17D