STUDIES ON THE PERFORMANCE OF A PARALLEL ITERATIVE ALGORITHM ON TRANSPUTER ARRAYS
S. SRINIVAS, A. BASU, K.G. Kumar, Arogyaswami J. Paulraj, Lalit Mohan Patnaik · International Journal of High Speed Computing · 1990
This paper discusses studies on the performance of a parallel iterative algorithm implemented on an array of transputers connected in a mesh configuration. The iterative algorithm under consideration is the finite difference method for the solution of partial differential equations. Analytical expressions for the execution times of the various steps of the algorithm are derived by studying its computation and communication characteristics. These expressions are validated by comparing the theoretical results of the performance with the experimental values obtained on a transputer array. Then the analytical model is used to estimate the performance of the algorithm for varying number of transputers in the array and for varying grid sizes. An important objective of this paper is to study the influence of the convergence detection overhead on the performance of the algorithm. We present an approach to minimize the overhead. Convergence detection is one of the dominant factors that affects the performance of the algorithm, since it involves a substantial amount of computation and communication. In order to reduce this overhead, the proposed algorithm checks convergence once in every certain number of iterations, kc. The method of determining an optimal value of kc is given. Further, the time taken for convergence detection is estimated for the best case, worst case, and average case situations.