Abstract
We consider techniques for the large scale parallel execution of algorithms on trees. We show that there is much parallelism in these algorithms, and introduce efficient means to exploit this parallelism. In particular, arbitrary order operations on trees are considered. An execution of a set arbitrary order operations must be equivalent to some sequential execution of a permutation of these operations.
A new algorithm is introduced for efficiently performing these operations under the condition that an operation consists of a sequence of reads starting at the root of a tree down a path towards some leaf, followed by a partial retrace of that path in reverse during which writes can occur — this is the standard form for performing inserts, searches, and deletes on most forms of balanced and unbalanced binary trees. We show that this new algorithm, tree interference is correct and produces execution schedules which are at least as parallel as other techniques including locking and graph coloring based interference. We also show some estimate of the performance on a sample computation, AVL trees.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Ahuja, N. Carriero, and David Gelertner. Linda and friends. Computer, 19(8):26–34, August, 1986.
A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, Reading, Mass., 1975.
David R. Chase, Mark Wegman, and F. K. Zadek. Analysis of pointers and structures. In Programming Language Design and Implementation, pages 296–310. ACM, June 1990.
Allan Gottlieb, B. D. Lubachevsky, and Larry Rudolph. Basic techniques for the efficient coordination of very large numbers of cooperating sequential processes. ACM Transactions of Programming Languages, 5(2):164–189, April, 1983.
Robert H. Halstead. Multilisp: a language for concurrent symbolic computation. TOPLAS, 7(4):501–538, October 1985.
W. Ludwell Harrison. Generalized iteration space and the parallelization of symbolic languages. In Ian Foster and Evan Tick, editors, Workshop on Computation of Symbolic Languages for Parallel Computers. Argonne National Labs, October 1992.
Laurie J. Hendren, Joseph Hummel, and Alexandru Nicolau. Abstraction for recursive pointer data structures: Improving the analysis and transformation of imperative languages. In Programming Language Design and Implementation, pages 249–260. ACM, June 1992.
Morris J. Katz. Paratran: A transparent, transaction based runtime mechanism for the parallel execution of scheme. Master's thesis, MIT, June 1986. Masters Thesis.
James R. Larus and Paul N. Hilfinger. Detecting conflicts between structure accesses. In SIGPLAN'88 Conference on Programming Language Design and Implementation, June 1988.
Thomas J. LeBlanc and John M. Mellor-Crummey. Debugging parallel programs with instant replay. TOC, C-36(4):471–482, April 1987.
Jacob T. Schwartz, R. B. K. Dewar, E. Dubinsky, and E. Schonberg. Programming with sets: an introduction to SETL. Springer-Verlag, New York, New York, 1986. setl book.
Joel H. Saltz, Ravi Mirchandaney, and Kay Crowley. Run-time parallelization and scheduling of loops. IEEE Trans. on Computer, 40(5):603–612, May 1991.
Jon A. Solworth. Programming language constructs for highly parallel operations on lists. The Journal of Supercomputing, 2:331–347, 1988.
Jon A. Solworth. The PARSEQ project: An interim report. In Languages and Compilers for Parallel Computing, pages 490–510. Pittman/MIT, 1990.
Jon A. Solworth. On the performance of parallel lists. In Advances in Languages and Compilers for Parallel Computing, pages 152–171. Pittman/MIT, 1991.
Jon A. Solworth. Arbitrary order iterations over pointer-based data structures. In 5th Workshop on Programming Languages and Compilers, August 1992. to appear.
Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. JACM, pages 652–686, July 1985.
Michael Wolfe. Doany: Not just another parallel loop. In 5th Workshop on Programming Languages and Compilers, August 1992. to appear.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Solworth, J.A., Reagan, B.B. (1994). Arbitrary order operations on trees. In: Banerjee, U., Gelernter, D., Nicolau, A., Padua, D. (eds) Languages and Compilers for Parallel Computing. LCPC 1993. Lecture Notes in Computer Science, vol 768. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57659-2_2
Download citation
DOI: https://doi.org/10.1007/3-540-57659-2_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57659-4
Online ISBN: 978-3-540-48308-3
eBook Packages: Springer Book Archive