Das S., Pinotti M. C. O(log log N) time algorithms for hamiltonian suffix and min-max-pair heap operations on the hypercube. In: Journal of Parallel and Distributed Computing, vol. 48 pp. 200 - 211. Academic Press, 1998. |

Abstract (English) |
This paper deals with a fast implementation of a heap data structure on a hypercube-connected, synchronous, distributed-memory multicomputer. In particular, we present a communication-efficient mapping of a min-max-pair heap on the hypercube architecture in which the load on each processor’s local memory is balanced and propose cost-optimal parallel algorithms which require O((log N)/p + log p) time to perform single insertion, deletemin, and deletemax operations on a min-max-pair heap of size N, where p is the number of processors. Our implementation is based on an embedding of complete binary trees in the hypercube and an efficient parallel solution to a special kind of suffix computation, that we call the Hamiltonian suffix, along a Hamiltonian path in the hypercube. The binary tree underlying the heap data structure is, however, not altered by the mapping process. | |

Subject | distributed-memory multicomputer E.1 Data Structures C.3 special purpose and application based systems |

1) Download Document PDF |

Open access Restricted Private