An Effective Structure for Algorithmic Design and a Parallel Prefix Algorithm on Metacube

Metacube is an attractive, hypercube-like interconnection network that can connect an extremely large number of nodes with a small node degree while keeping a relatively short diamemter. A Metacube MC(k,m) connects 2^{2 k m+k} nodes with only k+m links per node. Metacube can be used to build parallel computing systems of very large scale with a small number of links per node. In this paper, we propose a new presentation of Metacube for algorithmic design on Metacube. Based on the new presentation, we give an efficient algorithm for parallel prefix computation on Metacubes that runs in 2^km(k+1)+k communication steps and 2^k+1m+2k computation steps.