FAST PARALLEL ALGORITHMS FOR FORECASTING

This paper presents two parallel algorithms for forecasting implemente d on a Linear array and a tree model [1]. Both the algorithms are base d on the weighted moving average technique [2,3]. Given that n and n a re the numbers of the input observed data values and the numbers of we ights, respectively, the algorithm on a linear array of n processors r equires m + 1 steps and that on a tree model with (2n - 1) processors (n being a power of 2), needs (m - n + 2) + log(2) n steps. It has als o been shown how the corresponding algorithms can be extended to the c ase when the number of available processors is less than n (for a line ar array) or 2n - 1 (for a tree model). The corresponding algorithms m apped on an ST-array (Store and Trigger array with p processors, p les s than or equal to n) [4] and an ST-tree (Store and Trigger tree with 2p - 1 processors, p less than or equal to n, p being a power of 2) re quire n/p(m - n + 1) + p - 1 and n/p[(m - n + 2) + log(2) p] steps, re spectively.