DocumentCode :
3415267
Title :
O(log log n) time algorithms for Hamiltonian-suffix and min-max-pair heap operations on hypercube multicomputers
Author :
Das, Sajal K. ; Pinotti, M. Cristina
Author_Institution :
Dept. of Comput. Sci., North Texas Univ., Denton, TX, USA
fYear :
1997
fDate :
1-5 Apr 1997
Firstpage :
507
Lastpage :
511
Abstract :
We present an efficient mapping of a min-max-pair heap of size N on a hypercube multicomputer of p processors in such a way the load on each processor´s local memory is balanced and no additional communication overhead is incurred for implementation of the single insertion, deletemin and deletemax operations. Our novel approach is based on an optimal mapping of the paths of a binary heap into a hypercube such that in O(log N/p+log p) time we can compute the Hamiltonian-suffix, which is defined as a pipelined suffix-minima computation on an O(log N)length heap path embedded into the Hamiltonian path of the hypercube according to the binary reflected Gray codes. However the binary tree underlying the heap data structure is not altered by the mapping process
Keywords :
Gray codes; data structures; hypercube networks; parallel algorithms; O(log log n) time algorithms; binary reflected Gray codes; binary tree; deletemax; deletemin; heap data structure; hypercube multicomputers; mapping; min-max-pair heap; optimal mapping; pipelined suffix-minima computation; Algorithm design and analysis; Binary trees; Costs; Data structures; Embedded computing; Hypercubes; Magnetic heads; Phase change random access memory; Reflective binary codes; Tree data structures;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing Symposium, 1997. Proceedings., 11th International
Conference_Location :
Genva
ISSN :
1063-7133
Print_ISBN :
0-8186-7793-7
Type :
conf
DOI :
10.1109/IPPS.1997.580947
Filename :
580947
Link To Document :
بازگشت