NDLI: Parallel Sparse Matrix Multiplication for Preconditioning and SSTA on a Many-Core Architecture

Content Provider	IEEE Xplore Digital Library
Author	Keliang Zhang Baifeng Wu
Copyright Year	2012
Abstract	Operations related to Sparse matrix multiplication are frequently used in scientific computing area, and these operations usually become a performance bottleneck because of their high operational complexity. For example, sparse matrix multiplying diagonal matrix (CS) is a key sub-procedure in preconditioning, and sparse matrix multiplying one-dimension block diagonal matrix (BCS) is a key sub-procedure for statistical static timing analysis (SSTA) without slope propagation based on sparse matrix framework. Although ELLH format along with its variant is suited to many-core architecture for spare matrix multiplying vector (SpMV) operation, for CS operation it leads to large amount of memory access due to accessing the column index matrix, for BCS operation it not only leads to larger amount of memory access, but also brings high computational complexity during parallel programming due to the complex data denpendencies among matrix elements. This paper presents a new sparse format (named ELLV format). For CS operation, the number of memory access can be reduced by half because of no requirement of accessing the matrix for column index. Experiment result shows that with our ELLV format the performance of CS operation can be improved by 15\% versus with ELLH format. For BCS operation, due to consistency of column index between the logical matrices and the physical matrices, not only the number of memory access can be reduced more remarkably, but also bring efficient and straightforward parallel programming on a many-core architecture.
Starting Page	59
Ending Page	68
File Size	977415
Page Count	10
File Format	PDF
ISBN	9781467318891
e-ISBN	9780769547220
DOI	10.1109/NAS.2012.11
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-06-28
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Linear systems sparse matrix multiplying one-dimension block diagonal matrix sparse matrix multiplying diagonal matrix Parallel programming Memory management Vectors statistical static timing analysis Sparse matrices Indexes Preconditioning Delay
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Sparse Matrix Multiplication on a Reconfigurable Many-Core Architecture

A geometric approach to matrix ordering.

Parallel commutation of sparse linear systems on many core processor

Research on parallel model for sparse matrix-vector iterative multiplication

Parallel block-diagonal-bordered sparse linear solvers for power systems applications (1994).

Optimizing Sparse Matrix Vector Multiplication Using Diagonal Storage Matrix Format

High-Level Strategies for Parallel Shared-Memory Sparse Matrix-Vector Multiplication

Parallel multilevel block ILU preconditioning techniques for large sparse linear systems (2003)

Permuting Sparse Rectangular Matrices into Block-Diagonal Form

Parallel Sparse Matrix Multiplication for Preconditioning and SSTA on a Many-Core Architecture

Similar Documents

Sparse Matrix Multiplication on a Reconfigurable Many-Core Architecture

A geometric approach to matrix ordering.

Parallel commutation of sparse linear systems on many core processor

Research on parallel model for sparse matrix-vector iterative multiplication

Parallel block-diagonal-bordered sparse linear solvers for power systems applications (1994).

Optimizing Sparse Matrix Vector Multiplication Using Diagonal Storage Matrix Format

High-Level Strategies for Parallel Shared-Memory Sparse Matrix-Vector Multiplication

Parallel multilevel block ILU preconditioning techniques for large sparse linear systems (2003)

Permuting Sparse Rectangular Matrices into Block-Diagonal Form

Parallel Sparse Matrix Multiplication for Preconditioning and SSTA on a Many-Core Architecture