Efficient Fully Adaptive Snapshots using Incremental Calculation


Authors


Abstract

The step complexity of fully adaptive algorithms depends only on the contention during an operation, when counting both local computation and accesses to shared registers. This paper significantly improves the local and shared step complexity of atomic snapshot and immediate snapshot to $O(k^2)$ and $O(k^3)$, respectively, where $k$ is the point contention during the operation's execution interval. These implementation uses only read and write operations on the shared memory. The fully adaptive algorithms employ a generic Gather&f object, which returns the value of applying a function f on previously stored information. It has $O(k)$ local and shared step complexity for calculating $f$ and $O(k^2)$ for storing information. A simple implementation of a Collect&f object has $O(k^2)$ local and shared step complexity for storing information and for calculating f. For common applications, the paper presents an efficient ECollect&f implementation, where storing information takes a single step and calculating f has $O(k)$ local and shared step complexity.