Brief Announcement: An Efficient Long-Lived Adaptive Collect Algorithm ⋆

Abstract. We present a new long-lived, efficient, adaptive collect algorithm. Namely, our algorithm adapts to K-contention- it has the property that if during an operation the interval contention k exceeds a predetermined constant K the step complexity is O(N). If, it falls below K, the processors executions will eventually have adaptive step complexity of O(k 3). Moreover, for K such that K 3 ≤ N our algorithm requires only O(N 2) shared memory registers.