TY  - JOUR
T1  - Improved implementations of binary universal operations.
JF  - Journal of the ACM
A1  - Attiya, Hagit
LA  - English
UL  - https://tuklas.up.edu.ph/Record/UP-99796217608727484
AB  - We present an algorithm for implementing binary operations (of any type) from unary load-linked (LL) and store-conditional (SC) operations. The performance of the algorithm is evaluated according to its sensitivity, measuring the distance between operations in the graph induced by conflicts, which guarantees that they do not influence the step complexity of each other. The sensitivity of our implementation is O(log* n), where n is the number of processors in the system. That is, operations that are Ω(log* n) apart in the graph induced by conflicts do not delay each other. Constant sensitivity is achieved for operations used to implement heaps and array-based linked lists.We also prove that there is a problem which can be solved in O(1) steps using binary LL/SC operations, but requires O(log log* n) operations if only unary LL/SC operations are used. This indicates a non-constant gap between unary and binary, LL/SC operations.
KW  - Computer systems organization.
KW  - Computer communication networks.
KW  - Distributed systems.
KW  - Performance of systems.
KW  - Software.
KW  - Programming techniques.
KW  - Concurrent programming.
KW  - Software engineering.
KW  - Interoperability.
KW  - Distributed objects.
KW  - Operating systems.
KW  - Process management.
KW  - Synchronization.
KW  - Theory of computation.
KW  - Computation by abstract devices.
KW  - Modes of computation.
KW  - Parallelism and concurrency.
KW  - Algorithms.
KW  - Performance.
KW  - Reliability.
KW  - Theory.
ER  -