Parallel Numerical Interpolation on Necklace Hypercubes

The necklace hypercube has been recently proposed as an attractive topology for multicomputers and was shown to have many desirable properties such as well-scalability and suitability for VLSI implementation. This paper introduces a parallel algorithm for computing an N-point Lagrange interpolation on a necklace hypercube multiprocessor. This algorithm consists of 3 phases: initialization, main and final. There is no computation in the initialization phase. The main phase consists of lceilE/2rceil steps (with E being the number of edges of the network), each consisting of 4 multiplications and 4 subtractions, and an additional step including 1 division and 1 multiplication. Communication in the main phase is based on an all-to-all broadcast algorithm using some Eulerian rings embedded in the host necklace hypercube. The final phase is carried out in three sub-phases. There are lceilk/2rceil steps in the first sub-phase where k is the size of necklace. Each of sub-phases two and three contains n steps. Our study reveals that when implementation cost in taken into account, there is no speedup difference between low-dimensional and high-dimensional necklace networks