MAPPING PIPELINED DIVIDED-DIFFERENCE COMPUTATIONS INTO HYPERCUBES

In numerical computations, the method of divided differences is a very important technique for polynomial approximations. Consider a pipelin ed divided-difference computation for approximating an nth degree poly nomial. This paper first presents a method to transform the computatio nal structure of divided differences into the pyramid tree with n(2)+3 n+2/2 nodes. Based on graph embedding technique, without any extra com munication delay, the pipelined divided-difference computation can be performed in a (2k + 1)-dimensional fault-free hypercube for n+1 = 2(k ) + t, k > 0, and 0 < t < 2(k); the pipelined divided-difference compu tation can be further performed in a (2k + 2)-dimensional faulty hyper cube to tolerate arbitrary (k - 1) faulty nodes/links. To the best of our knowledge, this is the first time such mapping methods are being p roposed in the literature.