Complete Binary Search Mesh: A Concurrent Data Structure for Distributed Memory Parallel Computers

Complete Binary Search Mesh: A Concurrent Data Structure for Distributed Memory Parallel Computers

Abstract

A dictionary machine is a database of (key, record) pairs with a given set of operators. Typical operators include insert, delete, delete record with minimum key, delete record with maximum key, record with minimum key, record with maximum key, nearest record, predecessor, successor, rank, and count. The different implementations of dictionary machines for districuted memory multiprocessor computers are reported in the literature. The stored chain, balanced cube, banyan heap are some examples. Binary search mesh is a concurrent data structure for dictionary machine for implementation of dictionary machines on the distributed memory multiprocessor computers with mesh or hypercube topologies. The implementation of binary search mesh which is given in [24] has some problems: hole is created in the insert operation, properties of the binary search mesh are not preserved in delete operation, mesh is not balanced, and data structure has low throughput. In [4] the balanced binary search mesh has proposed which doesn't create hole in the insert operator and preserve the binary search mesh in the delete operator. In this paper, we propose the complete binary search mesh, which solves problems in binary search mesh and balanced binary search mesh. In this data structure, the levels of mesh are filled in the increasing order, which improves the throughput of data structure. For implementation of this data structure on the mesh or hypercube, the machine logically consists of two different non-disjoint networks: broadcasting network for sending operators and sending network for sending the responses, which reduce the overall traffic of the network. Comparison of complete binary search mesh with other dictionary machines implemented on the distributed memory multiprocessor computers with mesh topology shows that the complete binary search mesh has higher throughput.

References