Universal operations
Hagit Attiya, Eyal Dagan · 1996
An algorithm for implementing binary operations (of any type) from unary load-linked (LL) and storeconditional (SC) operations is presented.The performance of the algorithm is measured by its sensitivity, i.e., how far (in terms of distances in the graph induced by the contention among overlapping operations) should operations be in order not to influence the step complexity of each other.The sensitivity of this implemental ion is at most O (log* n), where n is the number of the processors in the system.That is, operations that are at least O(log* n) apart in the contention graph do not delay each other.In some cases, where the data sets of the operations are restricted, e.g., in operations used to implement linked lists and heaps, the sensitivity is 0(1).We also prove a negative result.We show that there is a problem which can be solved in 0(1) steps using binary LL/SC operations, but requires O(log log* n) operations if only unary LL/SC operations are used.