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

Reactive multi-word synchronization for multiprocessors

Phuong Ha (Institutionen för datavetenskap, Datakommunikation och Distribuerade System) ; Philippas Tsigas (Institutionen för datavetenskap, Datakommunikation och Distribuerade System)
The Journal of Instruction-Level Parallelism Vol. 6 (2004), Special issue, p. Web archives.
[Artikel, refereegranskad vetenskaplig]

Shared memory multiprocessor systems typically provide a set of hardware primitives in order to support synchronization. Generally, they provide "single-word" read-modify-write hardware primitives such as compare-and-swap, load-linked/store-conditional and fetch-and-op, from which the higher-level synchronization operations are then implemented in software. Although the "single-word" hardware primitives are conceptually powerful enough to support higher-level synchronization, from the programmer's point of view they are not as useful as their generalizations to the "multi-word" objects. This paper presents two fast and reactive lock-free "multi-word" compare-and-swap algorithms. The algorithms dynamically measure the level of contention as well as the memory conflicts of the "multi-word" compare-and-swap operations, and in response, they react accordingly in order to guarantee good performance in a wide range of system conditions. The algorithms are non-blocking (lock-free), allowing in this way fast dynamical behavior. Experiments on thirty processors of an SGI Origin2000 multiprocessor show that both our algorithms react quickly according to the contention variations and outperform the best known alternatives in almost all contention conditions.

Nyckelord: non-blocking, lock-free, reactive synchronization, online algorithms, practical

(c)2004 AI Access Foundation and Morgan Kaufmann Publishers

Denna post skapades 2006-08-25.
CPL Pubid: 1580


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, Datakommunikation och Distribuerade System (2002-2004)


Information Technology

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:

Reactive Shared Objects for Interprocess Synchronization

Reactive Concurrent Data Structures and Algorithms for Synchronization