Abstract

In this paper, the extended Karnaugh Map representation (EKMR) scheme has been proposed as an alternative to the traditional matrix representation (TMR) which caused the multi-dimensional array operation to be inefficient when extended to dimensions higher than two. Multi-dimensional arrays are widely used in a lot of scientific studies but still some issues have been encountered regarding efficient operations of these multi-dimensional arrays. EKMR scheme has managed to successfully optimize the performance of the multi-dimensional array operations to the nth dimension of the array. The basic concept EKMR is to transform the multi-dimensional array in to a set of two-dimensional arrays. EKMR scheme implies Karnaugh Map which is a technique used to reduce a Boolean expression. It is commonly represented with the help of a rectangular map which holds all the possible values of the Boolean expression. Then the efficient data parallel algorithms for multi-dimensional matrix multiplication operation using EKMR are presented in this study which outperformed those data parallel algorithms for multi-dimensional matrix multiplication operation which used the TMR scheme. The study encourages designing data parallel algorithms for multi-dimensional dense and sparse multi-dimensional arrays for other operations as well using the EKMR scheme since this scheme produces the efficient performance for all dimensions and for all operations of the arrays.

References

• A.J.C. Bik and H.A.G. Wijshoff, “Compilation Techniques for Sparse Matrix Computations,” Proc. ACM Int.l Conf. Supercomputing, 1993, pp. 416-424.
• A.J.C. Bik, P.M.W. Knijnenburg, and H.A.G. Wijshoff, “Reshaping Access Patterns for Generating Sparse Codes,” Proc. Int.l Workshop Languages and Compilers for Parallel Computing, 1994, pp. 406-420.
• A.J.C. Bik and H.A.G Wijshoff, “Automatic Data Structure Selection and Transformation for Sparse Matrix Computations,” IEEE Transactions on Parallel and Distributed Systems, vol. 7, no. 2, Feb. 1996, pp. 109-126.
• G. Bandera, P.P. Trabado, and E.L. Zapata, “Local Enumeration Techniques for Sparse Algorithms,” Proc. IEEE Int.l Symp. Parallel Processing, 1998, pp.52-56.
• B.B. Fraguela, R. Doallo, E.L. Zapata, “Modeling Set Associative Caches Behaviour for Irregular Computations,” Proc. ACM Int.l Conf. Measurement and Modeling of Computer Systems, 1998, pp.192-201.
• B.B. Fraguela, R. Doallo, E.L. Zapata, “Cache Misses Prediction for High Performance Sparse Algorithms,” Proc. Int.l Euro-Par Conf., 1998, pp.224-233.
• B.B. Fraguela, R. Doallo, E.L. Zapata, “Cache Probabilistic Modeling for Basic Sparse Algebra Kernels Involving Matrices with a Non-Uniform Distribution,” Proc. IEEE Euromicro Conf., 1998, pp. 345-348.
• B.B. Fraguela, R. Doallo, E.L. Zapata, “Automatic Analytical Modeling for the Estimation of Cache Misses,” Proc. Int.l Conf. Parallel Architectures and Compilation Techniques, 1999, pp. 221-231.
• B. Kumar, C.H. Huang, R.W. Johnson, and P. Sadayappan, “A Tensor Product Formulation of Strassen's Matrix Multiplication Algorithm with Memory Reduction,” Proc. Int.l Symp. Parallel Processing, 1993, pp. 582-588.
• T.R. Chung, R.G. Chang, and J.K. Lee, “Sampling and Analytical Techniques for Data Distribution of Parallel Sparse Computation,” Pro. SIAM Conf. Parallel Processing for Scientific Computing, 1997.
• S. Chatterjee, A.R. Lebeck, P.K. Patnala, and M. Thottethodi, “Recursive Array Layouts and Fast Matrix Multiplication,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 11, Nov. 2002, pp.1105-1123.
• G.H. Golub and C.F.V. Loan, Matrix Computations, 2nd Edition, The John Hopkins University Press, Baltimore, Maryland 21218, 1989.
• J.B. White and P. Sadayappan, “On Improving the Performance of Sparse Matrix-Vector Multiplication,” Proc. Int.l Conf. High-Performance Computing, 1997, pp. 711-725.
• C.Y. Lin, J.S. Liu, and Y.C. Chung, “Efficient Representation Scheme for Multi-Dimensional Array Operations,” IEEE Transactions on Computers, vol. 51, no. 3, Mar. 2002, pp. 327-345.
• C.Y. Lin, Y.C. Chung, and J.S. Liu, “Efficient Data Parallel Algorithms for Multi-Dimensional Array Operations Based on the EKMR Scheme for Distributed Memory Multicomputers,” Accepted by IEEE Transactions on Parallel and Distributed Systems, 2003.
• M.F.P. O'Boyle and P.M.W. Knijnenburg, “Integrating Loop and Data Transformations for Global Optimization,” Proc. Int.l Conf. ParallelArchitectures and Compilation Techniques, 1998, pp. 12-19.