Primitives for asynchronous list compression |
| |
Authors: | R J Anderson |
| |
Affiliation: | (1) University of Washington, 98195 Seattle, WA, USA |
| |
Abstract: | In this paper we study the problem of asynchronous processors traversing a list with path compression. We show that if an atomic splice operation is available, the worst-case work forp processors traversing a list of length h is (np
1/2). The splice operation can be generalized to removek elements from the list. For thek-splice operation the worst-case work is (np
1/
k+1).This research was supported by an NSF Presidential Young Investigator Award CCR-8657562, Digital Equipment Corporation, NSF CER Grant CCR-861966, and NSF/Darpa Grant CCR-8907960. A preliminary version of this paper was presented at the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|