A parallel algorithm for embedding large pyramids into smaller hypercubes with load balancing
Y.W. Chen, Kuo‐Liang Chung · 2002
Consider a pyramid with n levels and a k-dimensional hypercube, 0/spl les/k/spl les/2n-2. The paper presents a parallel algorithm for embedding large pyramids into smaller hypercubes with load balancing. With dilation 4, congestion at most 2/sup n-k/2/+4, and load [2/sup 2n-k//3] when k is even, our algorithm embeds the pyramid into the hypercube, otherwise, with the same dilation and load, it has congestion 2/sup n-(k+1)///sup 2+1/+6 when k is odd. The algorithm can be performed in O(k)-bit time.