Parallel Lagrange interpolation on k-ary n-cubes with maximum channel utilization

Aminollah Mahabadi | Hamid Sarbazi | Ebraham Khodaei | keyvan Navi

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=1215
Date :  2008/03/01
Publish in :    The Journal of Supercomputing


Keywords :Parallel, interpolation, utilization

Abstract :

---

This paper proposes an efficient parallel algorithm for computing Lagrange interpolation on k-ary n-cube networks. This is done using the fact that a k-ary n-cube can be decomposed into n link-disjoint Hamiltonian cycles. Using these n link-disjoint cycles, we interpolate Lagrange polynomial using full bandwidth of the employed network. Communication in the main phase of the algorithm is based on an all-to-all broadcast algorithm on the n link-disjoint Hamiltonian cycles exploiting all network channels, and thus, resulting in high-efficiency in using network resources. A performance evaluation of the proposed algorithm reveals an optimum speedup for a typical range of system parameters used in current state-of-the-art implementations.