A CORRECTNESS CONDITION FOR HIGH-PERFORMANCE MULTIPROCESSORS

Citation
H. Attiya et R. Friedman, A CORRECTNESS CONDITION FOR HIGH-PERFORMANCE MULTIPROCESSORS, SIAM journal on computing, 27(6), 1998, pp. 1637-1670
Citations number
63
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
ISSN journal
0097-5397
Volume
27
Issue
6
Year of publication
1998
Pages
1637 - 1670
Database
ISI
SICI code
0097-5397(1998)27:6<1637:ACCFHM>2.0.ZU;2-J
Abstract
Hybrid consistency, a consistency condition for shared memory multipro cessors, attempts to capture the guarantees provided by contemporary h igh-performance architectures. It combines the expressiveness of stron g consistency conditions (e.g., sequential consistency, linearizabilit y) and the efficiency of weak consistency conditions (e.g., pipelined RAM, causal memory). Memory access operations are classified as either strong or weak. A global ordering of strong operations at different p rocesses is guaranteed, but there is very little guarantee on the orde ring of weak operations at different processes, except for what is imp lied by their interleaving with the strong operations. A formal and pr ecise definition of this condition is given and an algorithm for provi ding hybrid consistency on distributed memory machines is presented. T he response time of the algorithm is proved to be within a constant mu ltiplicative factor of the (theoretical) optimal time bounds.