CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

A New Approach for Representation of Multi-dimensional Matrix Multiplication Operations

by Satya Prakash, Anil K. Ahlawat
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 29 - Number 8
Year of Publication: 2011
Authors: Satya Prakash, Anil K. Ahlawat
10.5120/4195-4968

Satya Prakash, Anil K. Ahlawat . A New Approach for Representation of Multi-dimensional Matrix Multiplication Operations. International Journal of Computer Applications. 29, 8 ( September 2011), 37-43. DOI=10.5120/4195-4968

@article{ 10.5120/4195-4968,
author = { Satya Prakash, Anil K. Ahlawat },
title = { A New Approach for Representation of Multi-dimensional Matrix Multiplication Operations },
journal = { International Journal of Computer Applications },
issue_date = { September 2011 },
volume = { 29 },
number = { 8 },
month = { September },
year = { 2011 },
issn = { 0975-8887 },
pages = { 37-43 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume29/number8/4195-4968/ },
doi = { 10.5120/4195-4968 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:15:18.835880+05:30
%A Satya Prakash
%A Anil K. Ahlawat
%T A New Approach for Representation of Multi-dimensional Matrix Multiplication Operations
%J International Journal of Computer Applications
%@ 0975-8887
%V 29
%N 8
%P 37-43
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. G.H. Golub and C.F.V. Loan, Matrix Computations, 2nd Edition, The John Hopkins University Press, Baltimore, Maryland 21218, 1989.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
Index Terms

Computer Science
Information Sciences

Keywords

Matrix Multiplication Algorithm EKMR TMR

Powered by PhDFocusTM