CONCURRENT PROCESSING OF LINEARLY ORDERED DATA-STRUCTURES ON HYPERCUBE MULTICOMPUTERS

This paper presents a simple and effective method for the concurrent m anipulation of linearly ordered data structures on hypercube systems. The method is based on the existence of an augmented binomial search t ree, called the pruned binomial tree, rooted at any arbitrary processo r node of the hypercube such that 1) every edge of the tree correspond s to a direct link between a pair of hypercube nodes, and 2) the tree spans any arbitrary sequence of n consecutive nodes containing the roo t, using a fan-out of at most inverted right perpendicular log2 n inve rted left perpendicular and a depth of at most inverted right perpendi cular log2 n inverted left perpendicular + 1. Search trees spanning no noverlapping processor lists are formed using only local information, and can be used concurrently without contention problems. Thus, they c an be used for performing operations such as broadcast and merge simul taneously on sets with nonuniform sizes. Extensions of the tree to k-a ry n-cubes and faulty hypercubes are presented. Applications of this c oncurrent data structure to low- and intermediate-level image processi ng algorithms, and for dictionary operations involving multiple keys, are also outlined.