International Journal of High Speed Computing

Many concurrent dictionary data structures have been proposed, but usually in the context of shared memory multiprocessors. In this paper, we present an algorithm for a concurrent distributed B-tree that can be implemented on message passing computer systems. Our distributed B-tree (the dB-tree) replicates the interior nodes in order to improve parallelism and reduce message passing. The dB-tree stores some redundant information in its nodes to permit the use of lazy updates to maintain replica coherency. We show how the dB-tree algorithm can be used to build an efficient implementation of a highly parallel, data-balanced distributed dictionary, the dE-tree.

Assume that a black/white n×n image is stored one pixel per element of a vector of length n². We consider determining some characteristics of such images using the scan model of parallel computation. The scan model was introduced by G.E. Blelloch and is a single instruction multiple data (SIMD) vector model of computation. The primitive operations of the model work on vectors (one dimensional arrays) of values, with three types of primitive operations: Elementwise arithmetic and logical operations, permutation operations, and scan operations, a type of prefix computation (a scan operation takes a binary associative operator ⊗ and a vector [a₁,…, a_n] and returns the vector [a₁, a₁⊗a₂,…, a₁⊗a₂⊗…⊗a_n]). We show that many important characteristics of binary images can be determined in constant time on the scan model of parallel computation. These include the convex hull construction, diameter, width, smallest enclosing box, perimeter, area, detecting digital convexity, parallel and point visibility (determining for each pixel of the image the portion that is visible, i.e., not obstructed by any black pixel, in a given direction from infinity or from a given point, respectively) of an image, smallest, largest and Hausdorff distances between two images, linear separability of two images, and the recognition of digital lines, rectangles and arcs.

Software distributed shared memory (DSM) provides a convenient and effective solution for programming parallel applications on distributed systems. However, the performance of current implementations suffers from large overhead in enforcing memory coherence. Coherence faults are the sources of massive network traffic. Various memory consistency models have been proposed in order to eliminate the effects of network traffic and memory latency. In this paper, we present a novel approach that combines relaxed memory consistency models and a compiler strategy to solve memory coherence problems for DSM. This approach produces fewer coherence faults. Experimental results also show this hybrid approach is effective for reducing the memory coherence overhead of DSM.

In a distributed memory multicomputer that has no global clock, global processor synchronization can only be achieved through software. Global synchronization is used in many applications, including tridiagonal systems solvers, CFD codes, and sequence comparison algorithms. For the Intel iPSC/860 in particular, global synchronization can also be used to ensure the most effective use of the communication network. Two global synchronization algorithms are considered for the iPSC/860: The gsync primitive provided by Intel and the RDS algorithm. Based on the communication model presented here, it is shown that gsync sometimes leaves the processors more poorly synchronized than they were to begin with. It is also shown that interrupts from the node operating system can cause gsync to contend for communication ports with the application code. The RDS algorithm does not have these shortcomings and costs only slightly more than the other algorithms. Measurements of the cost of message shift operations preceded by global synchronization confirm that the RDS algorithm always synchronizes the nodes more precisely than gsync.

In this paper, we propose a new fault tolerant multistage interconnection network (MIN) and a new adaptive self-routing scheme for the network. It can provide more multiple paths than the related previous networks between an input/output pair of a network by adding extra links between switching elements in the same stage and modifying the self-routing scheme of the banyan network. Our routing scheme is as simple as that of the banyan network, which is based on the topological relationships among the switching elements (SE’s) that render a packet to the same destination with the regular self-routing, which are discovered in this paper. We present an algebraic proof to show the correctness of this scheme, and an analytic reliability analysis to provide quantitative comparisons with other networks, which shows that the new network is more cost effective than the banyan network and other augmented MIN’s in terms of the reliability.