PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
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


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional