Fast parallel algorithms for forecasting

✍ Scribed by P.K. Jana; B.P. Sinha

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 540 KB
• Volume: 34
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(97)00187-9

✦ Synopsis

This paper presents two parallel algorithms for forecasting implemented on a linear array and a tree model [1]. Both the algorithms are based on the weighted moving average technique [2,3]. 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) + log 2 n 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) [4] and an ST-tree (Store and Trigger tree with 2p -1 processors, p _< n, p being a power of 2) require n/p(m -n + 1) +p -1 and n/p[(m -n + 2) + log2p ] steps, respectively.