STUDIES ON THE PERFORMANCE OF A PARALLEL ITERATIVE ALGORITHM ON TRANSPUTER ARRAYS

作     者：S. SRINIVAS A. BASU K.G. KUMAR A. PAULRAJ L M PATNAIK 

作者机构：Centre for Development of Advanced Computing (C-DAC) 2/1 Brunton Road Bangalore 560025 India Department of Computer Science and Automation and Microprocessor Applications Laboratory Indian Institute of Science Bangalore 560012 India 

出 版 物：《International Journal of High Speed Computing》 

年 卷 期：1990年第2卷第3期

页      面：265-287页

主　　题：Convergence check distributed memory multiprocessors iterative methods message passing performance analysis performance estimation transputer arrays 

摘      要：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, k c . The method of determining an optimal value of k c is given. Further, the time taken for convergence detection is estimated for the best case, worst case, and average case situations.