Fast parallel algorithms for forecasting

This paper presents two parallel algorithms for forecasting implemented on a linear array and a tree model. Both the algorithms are based on the weighted moving average technique. Given that m and n are the numbers of the input observed data values and the numbers of weights, respectively, the algorithm on a linear array of n processors requires m+1 steps and that on a tree model with (2n–1) processors (n being a power of 2), needs (m–n+2)+log2n steps. It has also been shown how the corresponding algorithms can be extended to the case when the number of available processors is less than n (for a linear array) or 2n–1 (for a tree model). The corresponding algorithms mapped on an ST-array (Store and Trigger array with p processors, p≤n) and an ST-tree (Store and Trigger tree with 2p–1 processors, p≤n, p being a power of 2) requiren/p(m–n+1)+p–1 and n/p[(m–n+2)+log2p] steps, respectively.