AN IMPROVED MAPPING OF CYCLIC ELIMINATION ONTO HYPERCUBES USING DATA REPLICATION

In this paper, we propose a new mapping of the Cyclic Elimination (CE) algorithm for the solution of block tridiagonal linear system of equa tions onto hypercube multiprocessors. Unlike the previous mapping sche mes, in our mapping of the CE algorithm all communications are restric ted to physically adjacent processors, using the concept of data repli cation. The effectiveness of our mapping is demonstrated by comparing it with the existing mapping of the Cyclic Reduction algorithm onto hy percubes using both analytical and simulation methods.