EFFICIENT PARALLEL COMPUTATION OF HIERCHICAL STRUCTURE ALGORITHMS ON NON-UNIFORM ACCESS MULTICOMPUTERS

摘要

In this paper a partitioning strategy comprising two alternating phases-a coarse grain level and a fine grain level-is suggested resulting in the construction of a hybrid quadtree-octtree algorithm structure. An efficient embedding procedure is proposed for the mapping of the hybrid tree guest graph on the host graph of a hypercube multicomputer with non-uniform access. The performance characteristics have been estimated via simulation implementing the latency hiding model of parallel bucket sort.