Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

PARALLEL COMPUTATION ON 2-3 TREES

IP.com Disclosure Number: IPCOM000128216D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 36K

Publishing Venue

Software Patent Institute

Related People

W. Paul: AUTHOR [+5]

Abstract

Our model of computation is a parallel computer with k synchronized processors P1,...,Pk sharing a common random access storage, where simultaneous access to the same storage location by two or more processors is not allowed. Suppose a 2-3 tree T with n leaves is implemented in the storage, suppose al,...,ak are data that may or may not be stored in the leaves, and for all i, 1 < i 4 k, processor Pi knows ai. We show how tosearch for al,...,ak in the tree T, insert these data into the tree, delete them from the tree, split the tree with respect to these elements and perform the union of k+1 range-disjoint 2-3 trees in [Equation ommitted] steps.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

PARALLEL COMPUTATION ON 2-3 TREES

BY

W. Paul, U. Vishkin and H. Wagener

Technical Report -~ #70 Ultracomputer Note #52

April 1983 New York University Department of Computer Science Courant Institute of Mathematical Sciences 251 Mercer Street New York, N. Y. PARALLEL. COMPUTATION ON 2- 3 TREES

W. Paul** IBM Research Laboratory San Jose, California 95193

U. Vishkin Courant Institute of Mathematical Sciences New York University, 251 Mercer Street New York, New York 10012

and

H. Wagener Technische Universitaet Berlin Institut fuer Software and Theoretische Informatik Strasse des 17. Juni 135, D-1000 Berlin 10, West Germany .

ABSTRACT

Our model of computation is a parallel computer with k synchronized processors P1,...,Pk sharing a common random access storage, where simultaneous access to the same storage location by two or more processors is not allowed. Suppose a 2-3 tree T with n leaves is implemented in the storage, suppose al,...,ak are data that may or may not be stored in the leaves, and for all i, 1 < i 4 k, processor Pi knows ai. We show how tosearch for al,...,ak in the tree T, insert these data into the tree, delete them from the tree, split the tree with respect to these elements and perform the union of k+1 range-disjoint 2-3 trees in

(Equation Omitted)

steps.

1. Introduction '

Technology will make it possible to build computers with a large number of cooperating processors in the near future. However, building such computers will only be worthwhile if the increased computing power can be used to reduce considerably the execution time of sufficiently many basic computational problems. In particular, one would like to have datastructures, where k processors can solve many problems about k times faster than a single processor. 2-3 trees are one such datastructure as "A preliminary version of this paper will be presented at the Tenth ICALP, Barcelona, July 1983. '~'~part of this research was done while the first author was visiting the Institut de Programmation of the Universite Paris will be demonstrated here. Protocols that avoid read or write conflicts, if several processors are

New York University Page 1 Dec 31, 1983

Page 2 of 12

PARALLEL COMPUTATION ON 2-3 TREES

working simultaneously on the same balanced tree, have been studied previously [BS], [S], but apparently no attempt was made to design fast algorithms and to analyze their running time. In the sequel, we say very little about how to avoid read or write conflicts: In the situations where they are possible, there are easy ways to avoid them. We will, however, have to sap. some words about storage allocation.

2. 2-3 Trees

A 2-3 tree T is a tree in which all leaves have the same depth and each interior mode v has two or three sons: the left son (v), the right son r(v), and in case there are three sons, the middle son m(v). Data from a totally ordered domain are stored in the leaves with smaller data to...