Efficient technique for partitioning and programming linear algebraalgorithms on concurrent VLSI architectures

摘要

An efficient technique for partitioning and programming linearnalgebra algorithms on concurrent architectures is described and appliednto 2-D wavefront arrays. The mapping of the computational elementsn(processes) to processors is based on the concept of folding. Thenmapping pattern on the 2-D full-size mesh of processes is composition ofnsymmetric tiles of size 2√(N)×2√(N), N being thennumber of processors. The algorithm can be partitioned according to anglobally sequential, locally parallel scheme. The code optimisation isnperformed by programming a few different types of tile, according to thenalgorithm. When the size of the problem is much larger than the size ofnthe mesh of processors, a linear speed-up is achieved independently ofnthe number of processors. Experimental results are presented for matrixnmultiplication, LU decomposition and the solution of triangular systemnequations on 2-D meshes of transputers programmed in Occam