Difference: SPMV (1 vs. 17)

Revision 172011-02-10 - KorniliosKourtis

Line: 1 to 1
 
META TOPICPARENT name="ActivitiesProjects"
Added:
>
>		For our more recent work on the Sparse Matrix-Vector Multiplication check: CSX.
 

Sparse Matrix-Vector Multiplication

Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm, which is further aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented

Revision 162010-11-17 - KorniliosKourtis

Line: 1 to 1
 
META TOPICPARENT name="ActivitiesProjects"

Sparse Matrix-Vector Multiplication

Line: 11 to 11
 
Added:
>
>
 

Revision 152009-10-08 - VasileiosKarakasis

Line: 1 to 1
 
META TOPICPARENT name="ActivitiesProjects"

Sparse Matrix-Vector Multiplication

Line: 8 to 8
 Another important optimization that has been widely applied to SPMV is blocking. While such optimization was initially intended to increase register reuse and the locality of references to the input vector, the main advantage of blocking is that it can significantly reduce the working set of the algorithm, thus leading to less memory traffic, meaning better performance for the case of the memory-bound SPMV. After attacking the memory intensiveness of the algorithm, the computational part of the kernel becomes more significant as a result. This allows for computation optimizations, such as vectorization, which can add a further performance boost to the blocked kernel. However, preliminary experiments have shown that the performance among different block shapes, which lead to the same working set, can have significantly varying performance, especially in the case of vectorization, due to a number of architectural issues raised from modern commodity microprocessors. Considering the multitude of blocked storage formats available for sparse matrices and the fact that block shapes can heavily affect the performance of SPMV, a performance model that could accurately predict the performance of a blocked storage format and then guide through the proper selection of both the right method and the right block shape would be desirable. Towards this direction, we have developed a performance model that accounts for both the memory and computation times of the blocked kernels. Our model is capable to better approximate the real execution time and lead to a more fit selection of method and block shape than earlier models, which solely based their prediction to memory traffic.

Publications

Changed:
<
<
  • V. Karakasis, G. Goumas, and N. Koziris, "Performance models for blocked Sparse Matrix-Vector multiplication kernels," International Conference on Parallel Processing (ICPP), Vienna, Austria, September 22-25, 2009. (to appear).
  • V. Karakasis, G. Goumas, and N. Koziris, "A comparative study of blocking storage methods for sparse matrices on multicore architectures," IEEE International Conference on Computational Science and Engineering (CSE), Vancouver, BC, Canada, August 29-31, 2009. (to appear).
  • V. Karakasis, G. Goumas, and N. Koziris, "Exploring the effect of block shapes on the performance of sparse kernels," Proceedings of the 23rd International Parallel and Distributed Processing Symposium (IPDPS-PDSEC), Rome, Italy, May 25-29, 2009.
  • K. Kourtis, G. Goumas, and N. Koziris, "Optimizing Sparse Matrix-Vector Multiplication Using Index and Value Compression," Proceedings of the ACM International Conference on Computing Frontiers, Ischia, Italy, 4-6 May, 2008
  • G. Goumas, K. Kourtis, N. Anastopoulos, V. Karakasis and N. Koziris, "Understanding the Performance of Sparse Matrix-Vector Multiplication," Proceedings of the 16th Euromicro International Conference on Parallel, Distributed and network-based Processing (PDP2008), Toulouse, France, 13-15 February, 2008
>
>
 

Diploma Thesis

  • Implementation of the Sparse Matrix-Vector Multiplication computational kernel on massively threaded graphics processors (pdf).

Revision 142009-06-25 - VasileiosKarakasis

Line: 1 to 1
 
META TOPICPARENT name="ActivitiesProjects"

Sparse Matrix-Vector Multiplication

Line: 8 to 8
 Another important optimization that has been widely applied to SPMV is blocking. While such optimization was initially intended to increase register reuse and the locality of references to the input vector, the main advantage of blocking is that it can significantly reduce the working set of the algorithm, thus leading to less memory traffic, meaning better performance for the case of the memory-bound SPMV. After attacking the memory intensiveness of the algorithm, the computational part of the kernel becomes more significant as a result. This allows for computation optimizations, such as vectorization, which can add a further performance boost to the blocked kernel. However, preliminary experiments have shown that the performance among different block shapes, which lead to the same working set, can have significantly varying performance, especially in the case of vectorization, due to a number of architectural issues raised from modern commodity microprocessors. Considering the multitude of blocked storage formats available for sparse matrices and the fact that block shapes can heavily affect the performance of SPMV, a performance model that could accurately predict the performance of a blocked storage format and then guide through the proper selection of both the right method and the right block shape would be desirable. Towards this direction, we have developed a performance model that accounts for both the memory and computation times of the blocked kernels. Our model is capable to better approximate the real execution time and lead to a more fit selection of method and block shape than earlier models, which solely based their prediction to memory traffic.

Publications

Changed:
<
<
>
>
  • V. Karakasis, G. Goumas, and N. Koziris, "Performance models for blocked Sparse Matrix-Vector multiplication kernels," International Conference on Parallel Processing (ICPP), Vienna, Austria, September 22-25, 2009. (to appear).
  • V. Karakasis, G. Goumas, and N. Koziris, "A comparative study of blocking storage methods for sparse matrices on multicore architectures," IEEE International Conference on Computational Science and Engineering (CSE), Vancouver, BC, Canada, August 29-31, 2009. (to appear).
  • V. Karakasis, G. Goumas, and N. Koziris, "Exploring the effect of block shapes on the performance of sparse kernels," Proceedings of the 23rd International Parallel and Distributed Processing Symposium (IPDPS-PDSEC), Rome, Italy, May 25-29, 2009.
 
Added:
>
>
 

Diploma Thesis

  • Implementation of the Sparse Matrix-Vector Multiplication computational kernel on massively threaded graphics processors (pdf).

Revision 132009-01-07 - VasileiosKarakasis

Line: 1 to 1
 
META TOPICPARENT name="ActivitiesProjects"

Sparse Matrix-Vector Multiplication

Line: 10 to 10
 

Publications

Added:
>
>

Diploma Thesis

  • Implementation of the Sparse Matrix-Vector Multiplication computational kernel on massively threaded graphics processors (pdf).
  • A comparative study of blocking storage methods for sparse matrices for the efficient implementation of the Sparse Matrix-Vector Multiplication kernel (pdf).

Revision 122008-10-15 - VasileiosKarakasis

Line: 1 to 1
 
META TOPICPARENT name="ActivitiesProjects"

Sparse Matrix-Vector Multiplication

Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm, which is further aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented in CF'08 (pdf)

Added:
>
>		Another important optimization that has been widely applied to SPMV is blocking. While such optimization was initially intended to increase register reuse and the locality of references to the input vector, the main advantage of blocking is that it can significantly reduce the working set of the algorithm, thus leading to less memory traffic, meaning better performance for the case of the memory-bound SPMV. After attacking the memory intensiveness of the algorithm, the computational part of the kernel becomes more significant as a result. This allows for computation optimizations, such as vectorization, which can add a further performance boost to the blocked kernel. However, preliminary experiments have shown that the performance among different block shapes, which lead to the same working set, can have significantly varying performance, especially in the case of vectorization, due to a number of architectural issues raised from modern commodity microprocessors. Considering the multitude of blocked storage formats available for sparse matrices and the fact that block shapes can heavily affect the performance of SPMV, a performance model that could accurately predict the performance of a blocked storage format and then guide through the proper selection of both the right method and the right block shape would be desirable. Towards this direction, we have developed a performance model that accounts for both the memory and computation times of the blocked kernels. Our model is capable to better approximate the real execution time and lead to a more fit selection of method and block shape than earlier models, which solely based their prediction to memory traffic.
 

Publications

Revision 112008-08-20 - KorniliosKourtis

Line: 1 to 1
 
META TOPICPARENT name="ActivitiesProjects"

Sparse Matrix-Vector Multiplication

Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm, which is further aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented

Changed:
<
<		 in CF'08 (pdf)
>
>		 in CF'08 (pdf)
 

Publications

Changed:
<
<
>
>

Revision 102008-04-07 - KorniliosKourtis

Line: 1 to 1
 
META TOPICPARENT name="ActivitiesProjects"

Sparse Matrix-Vector Multiplication

Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm, which is further aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented

Changed:
<
<		 in CF'08 (pdf)
>
>		 in CF'08 (pdf)
 

Publications

Deleted:
<
<
 \ No newline at end of file
Added:
>
>

Revision 92008-03-11 - NikosAnastopoulos

Line: 1 to 1
 
META TOPICPARENT name="ActivitiesProjects"

Sparse Matrix-Vector Multiplication

Revision 82008-03-11 - VangelisKoukis

Line: 1 to 1
Changed:
<
<
META TOPICPARENT name="Arch"
>
>
META TOPICPARENT name="ActivitiesProjects"
 

Sparse Matrix-Vector Multiplication

Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm, which is further aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented

Revision 72008-03-07 - GeorgiosGoumas

Line: 1 to 1
 
META TOPICPARENT name="Arch"

Sparse Matrix-Vector Multiplication

Revision 62008-03-07 - VasileiosKarakasis

Line: 1 to 1
 
META TOPICPARENT name="Arch"

Sparse Matrix-Vector Multiplication

Changed:
<
<		Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing poses various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm and aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented
>
>		Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm, which is further aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented
  in CF'08 (pdf)

Publications

Revision 52008-03-06 - KorniliosKourtis

Line: 1 to 1
 
META TOPICPARENT name="Arch"
Changed:
<
<

SPMV

>
>

Sparse Matrix-Vector Multiplication

 
Changed:
<
<		Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing poses various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm and aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented
>
>		Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing poses various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm and aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented
  in CF'08 (pdf)

Publications

Revision 42008-03-06 - ArisSotiropoulos

Line: 1 to 1
 
META TOPICPARENT name="Arch"

SPMV

Changed:
<
<		Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing poses various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" ( pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm and aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented in CF'08 ( pdf)
>
>		Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing poses various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm and aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented in CF'08 (pdf)
 

Publications

Changed:
<
<
>
>

Revision 32008-03-06 - KorniliosKourtis

Line: 1 to 1
 
META TOPICPARENT name="Arch"

SPMV

Changed:
<
<		Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing poses various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm and aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented in Computing Frontiers 2008.
>
>		Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing poses various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" ( pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm and aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented in CF'08 ( pdf)
 

Publications

Deleted:
<
<		 -- GeorgiosGoumas - 06 Mar 2008

Revision 22008-03-06 - GeorgiosGoumas

Line: 1 to 1
 
META TOPICPARENT name="Arch"
Changed:
<
<		Sparse Matrix-Vector Multiplication (SPMV)
>
>

SPMV

Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing poses various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm and aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented in Computing Frontiers 2008.

Publications

  -- GeorgiosGoumas - 06 Mar 2008

Revision 12008-03-06 - GeorgiosGoumas

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="Arch"
Sparse Matrix-Vector Multiplication (SPMV)

-- GeorgiosGoumas - 06 Mar 2008

View topic | History: r17 < r16 < r15 < r14 | More topic actions...
 
This site is powered by the TWiki collaboration platform Powered by Perl

No permission to view TWiki.WebBottomBar