The Experts below are selected from a list of 4413 Experts worldwide ranked by ideXlab platform

Jurgen Gotze - One of the best experts on this subject based on the ideXlab platform.

  • PPAM (1) - Inexact sparse Matrix Vector multiplication in Krylov Subspace Methods: An Application-Oriented Reduction Method
    Parallel Processing and Applied Mathematics, 2014
    Co-Authors: Ahmad Mansour, Jurgen Gotze
    Abstract:

    Iterative solvers based on Krylov subspace method proved to be robust in the presence of well monitored inexact matrix vector products. In this paper, we show that the iterative solver performs well while gradually reducing the number of nonzero elements of the matrix throughout the iterations. We benefit from this robustness in reducing the computational effort and the communication volume when implementing sparse matrix vector multiplication (SMVM) on a Network-on-Chip (NoC).

  • PDCAT - sparse matrix-vector multiplication: A Data Mapping-Based Architecture
    2014 15th International Conference on Parallel and Distributed Computing Applications and Technologies, 2014
    Co-Authors: Ahmad Mansour, Jurgen Gotze, Wei-chun Hsu, Shanq-jang Ruan
    Abstract:

    The performance of the sparse matrix-vector multiplication (SMVM) on a parallel system is strongly affected by the distribution of data among its components. Two costs arise as a result of the used data mapping method: arithmetic and communication. The communication cost often dominates the arithmetic cost, and the gap between these costs tends to increase. Therefore, finding a mapping method that reduces the communication cost is of high importance. On the other hand, the load distribution among the processing units must not be sacrificed. In this paper, a data mapping method is proposed for SMVM on Network-on-Chip which achieves balanced working load and reduces the communication cost. Afterwards, an FPGA-based architecture is introduced which is designed to fit with the proposed data mapping method.

  • ICCS - Utilizing Robustness of Krylov Subspace Methods in Reducing the Effort of sparse Matrix Vector multiplication
    Procedia Computer Science, 2013
    Co-Authors: Ahmad Mansour, Jurgen Gotze
    Abstract:

    Abstract Iterative solvers based on Krylov subspace method proved to be robust in the presence of inexact matrix vector products. In this paper, the inexactness is induced by reducing the number of nonzero elements of the matrix while maintaining the convergence of the iterative solver. We benefit from this property by reducing the computational effort and the communication volume when implementing sparse matrix vector multiplication (SMVM) on Network-on-Chip (NoC).

  • PAAP - sparse matrix-vector multiplication Based on Network-on-Chip: On Data Mapping
    2012 Fifth International Symposium on Parallel Architectures Algorithms and Programming, 2012
    Co-Authors: Ahmad Mansour, Jurgen Gotze
    Abstract:

    sparse matrix-vector multiplication (SMVM) on parallel hardware is a very sophisticated problem because of the irregular data communication requirements. The communication volume in the parallel hardware is determined by how data is distributed among the processing elements. In this paper we introduce two methods of data mapping for SMVM based on Network-on-Chip (NoC) in order to spread the load among its components. Later, we introduce the effect of reordering of the sparse matrix on those mapping methods. Simulations are performed using an OMNeT++ based NoC simulator.

  • sparse matrix-vector multiplication on network-on-chip
    Advances in Radio Science, 2010
    Co-Authors: C.-c. Sun, Jurgen Gotze, H.-y. Jheng, Shanq-jang Ruan
    Abstract:

    Abstract. In this paper, we present an idea for performing matrix-vector multiplication by using Network-on-Chip (NoC) architecture. In traditional IC design on-chip communications have been designed with dedicated point-to-point interconnections. Therefore, regular local data transfer is the major concept of many parallel implementations. However, when dealing with the parallel implementation of sparse matrix-vector multiplication (SMVM), which is the main step of all iterative algorithms for solving systems of linear equation, the required data transfers depend on the sparsity structure of the matrix and can be extremely irregular. Using the NoC architecture makes it possible to deal with arbitrary structure of the data transfers; i.e. with the irregular structure of the sparse matrices. So far, we have already implemented the proposed SMVM-NoC architecture with the size 4×4 and 5×5 in IEEE 754 single float point precision using FPGA.

Nectarios Koziris - One of the best experts on this subject based on the ideXlab platform.

  • PPoPP - BASMAT: bottleneck-aware sparse matrix-vector multiplication auto-tuning on GPGPUs
    Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming, 2019
    Co-Authors: Athena Elafrou, Georgios Goumas, Nectarios Koziris
    Abstract:

    In this work, we present a bottleneck-aware sparse matrix-vector multiplication auto-tuner (BASMAT) for general purpose graphics processing units (GPGPUs) that targets both fast execution and low preprocessing overheads.

  • A lightweight optimization selection method for sparse matrix-vector multiplication.
    arXiv: Performance, 2015
    Co-Authors: Athena Elafrou, Georgios Goumas, Nectarios Koziris
    Abstract:

    In this paper, we propose an optimization selection methodology for the ubiquitous sparse matrix-vector multiplication (SpMV) kernel. We propose two models that attempt to identify the major performance bottleneck of the kernel for every instance of the problem and then select an appropriate optimization to tackle it. Our first model requires online profiling of the input matrix in order to detect its most prevailing performance issue, while our second model only uses comprehensive structural features of the sparse matrix. Our method delivers high performance stability for SpMV across different platforms and sparse matrices, due to its application and architecture awareness. Our experimental results demonstrate that a) our approach is able to distinguish and appropriately optimize special matrices in multicore platforms that fall out of the standard class of memory bandwidth bound matrices, and b) lead to a significant performance gain of 29% in a manycore platform compared to an architecture-centric optimization, as a result of the successful selection of the appropriate optimization for the great majority of the matrices. With a runtime overhead equivalent to a couple dozen SpMV operations, our approach is practical for use in iterative numerical solvers of real-life applications.

  • Performance evaluation of the sparse matrix-vector multiplication on modern architectures
    The Journal of Supercomputing, 2009
    Co-Authors: Georgios Goumas, Kornilios Kourtis, Nikos Anastopoulos, Vasileios Karakasis, Nectarios Koziris
    Abstract:

    In this paper, we revisit the performance issues of the widely used sparse matrix-vector multiplication (SpMxV) kernel on modern microarchitectures. Previous scientific work reports a number of different factors that may significantly reduce performance. However, the interaction of these factors with the underlying architectural characteristics is not clearly understood, a fact that may lead to misguided, and thus unsuccessful attempts for optimization. In order to gain an insight into the details of SpMxV performance, we conduct a suite of experiments on a rich set of matrices for three different commodity hardware platforms. In addition, we investigate the parallel version of the kernel and report on the corresponding performance results and their relation to each architecture’s specific multithreaded configuration. Based on our experiments, we extract useful conclusions that can serve as guidelines for the optimization process of both single and multithreaded versions of the kernel.

  • ICPP - Perfomance Models for Blocked sparse matrix-vector multiplication Kernels
    2009 International Conference on Parallel Processing, 2009
    Co-Authors: Vasileios Karakasis, Georgios Goumas, Nectarios Koziris
    Abstract:

    sparse matrix-vector multiplication (SpMV) is a very challenging computational kernel, since its performance depends greatly on both the input matrix and the underlying architecture. The main problem of SpMV is its high demands on memory bandwidth, which cannot yet be abudantly offered from modern commodity architectures. One of the most promising optimization techniques for SpMV is blocking, which can reduce the indexing structures for storing a sparse matrix, and therefore alleviate the pressure to the memory subsystem. However, blocking methods can severely degrade performance if not used properly. In this paper, we study and evaluate a number of representative blocking storage formats and present a performance model that can accurately select the most suitable blocking storage format and the corresponding block shape and size for a specific sparse matrix. Our model considers both the memory and computational part of the kernel, which can be non-negligible when applying blocking, and also assumes an overlapping of memory accesses and computations that modern commodity architectures can offer through hardware prefetching mechanisms.

  • understanding the performance of sparse matrix vector multiplication
    Parallel Distributed and Network-Based Processing, 2008
    Co-Authors: Georgios Goumas, Kornilios Kourtis, Nikos Anastopoulos, Vasileios Karakasis, Nectarios Koziris
    Abstract:

    In this paper we revisit the performance issues of the widely used sparse matrix-vector multiplication (SpMxV) kernel on modern microarchitectures. Previous scientific work reports a number of different factors that may significantly reduce performance. However, the interaction of these factors with the underlying architectural characteristics is not clearly understood, a fact that may lead to misguided and thus unsuccessful attempts for optimization. In order to gain an insight on the details of SpMxV performance, we conduct a suite of experiments on a rich set of matrices for three different commodity hardware platforms. Based on our experiments we extract useful conclusions that can serve as guidelines for the subsequent optimization process of the kernel.

Daisuke Takahashi - One of the best experts on this subject based on the ideXlab platform.

  • ICCSA (2) - Parallel sparse matrix-vector multiplication Using Accelerators
    Computational Science and Its Applications – ICCSA 2016, 2016
    Co-Authors: Hiroshi Maeda, Daisuke Takahashi
    Abstract:

    sparse matrix-vector multiplication (SpMV) is an essential computational kernel for many applications such as scientific computing. Recently, the number of computing systems equipped with NVIDIA’s GPU and Intel’s Xeon Phi coprocessor based on the MIC architecture has been increasing. Therefore, the importance of effective algorithms for SpMV in these systems is increasing. To the best of our knowledge, while previous studies have reported CPU and GPU implementations of SpMV for a cluster and MIC implementations for a single node, implementations of SpMV for the MIC cluster have not yet been reported. In this paper, we implemented and evaluated parallel SpMV on a GPU cluster and a MIC cluster. As shown by the results, the implementation for MIC achieved relatively high performance in some matrices with a single process, but it could not achieve higher performance than other implementations with 64 MPI processes. Therefore, we implemented and evaluated the single SpMV kernel to improve the performance of parallel SpMV.

  • CANDAR - Performance Evaluation of sparse matrix-vector multiplication Using GPU/MIC Cluster
    2015 Third International Symposium on Computing and Networking (CANDAR), 2015
    Co-Authors: Hiroshi Maeda, Daisuke Takahashi
    Abstract:

    sparse matrix-vector multiplication (SpMV) is an important computational kernel for many applications such as scientific computing. To the best of our knowledge, while previous studies have reported CPU and GPU implementations of SpMV for a cluster and MIC implementations for a single node, implementations of SpMV for the MIC cluster have not yet been reported. In this paper, we implement and evaluate parallel SpMV on a GPU cluster and a MIC cluster.

  • optimization of sparse matrix vector multiplication by auto selecting storage schemes on gpu
    International Conference on Computational Science and Its Applications, 2011
    Co-Authors: Yuji Kubota, Daisuke Takahashi
    Abstract:

    sparse matrix vector multiplication is one of the most often used functions in scientific and engineering computing. Though, various storage schemes for sparse matrices have been proposed, the optimal storage scheme is dependent upon the matrix being stored. In this paper, we will propose an autoselecting algorithm for sparse matrix vector multiplication on GPUs that automatically selects the optimal storage scheme. We evaluated our algorithm using a solver for systems of linear equations. As a result, we found that our algorithm was effective for many sparse matrices.

  • ICCSA (2) - Optimization of sparse matrix-vector multiplication by auto selecting storage schemes on GPU
    Computational Science and Its Applications - ICCSA 2011, 2011
    Co-Authors: Yuji Kubota, Daisuke Takahashi
    Abstract:

    sparse matrix vector multiplication is one of the most often used functions in scientific and engineering computing. Though, various storage schemes for sparse matrices have been proposed, the optimal storage scheme is dependent upon the matrix being stored. In this paper, we will propose an autoselecting algorithm for sparse matrix vector multiplication on GPUs that automatically selects the optimal storage scheme. We evaluated our algorithm using a solver for systems of linear equations. As a result, we found that our algorithm was effective for many sparse matrices.

Rob H Bisseling - One of the best experts on this subject based on the ideXlab platform.

  • Cache-Oblivious sparse matrix-vector multiplication by Using sparse Matrix Partitioning Methods
    SIAM Journal on Scientific Computing, 2009
    Co-Authors: A. N. Yzelman, Rob H Bisseling
    Abstract:

    In this article, we introduce a cache-oblivious method for sparse matrix-vector multiplication. Our method attempts to permute the rows and columns of the input matrix using a recursive hypergraph-based sparse matrix partitioning scheme so that the resulting matrix induces cache-friendly behavior during sparse matrix-vector multiplication. Matrices are assumed to be stored in row-major format, by means of the compressed row storage (CRS) or its variants incremental CRS and zig-zag CRS. The zig-zag CRS data structure is shown to fit well with the hypergraph metric used in partitioning sparse matrices for the purpose of parallel computation. The separated block-diagonal (SBD) form is shown to be the appropriate matrix structure for cache enhancement. We have implemented a run-time cache simulation library enabling us to analyze cache behavior for arbitrary matrices and arbitrary cache properties during matrix-vector multiplication within a $k$-way set-associative idealized cache model. The results of these simulations are then verified by actual experiments run on various cache architectures. In all these experiments, we use the Mondriaan sparse matrix partitioner in one-dimensional mode. The savings in computation time achieved by our matrix reorderings reach up to 50 percent, in the case of a large link matrix.

  • a two dimensional data distribution method for parallel sparse matrix vector multiplication
    Siam Review, 2005
    Co-Authors: Brendan Vastenhouw, Rob H Bisseling
    Abstract:

    A new method is presented for distributing data in sparse matrix-vector multiplication. The method is two-dimensional, tries to minimize the true communication volume, and also tries to spread the computation and communication work evenly over the processors. The method starts with a recursive bipartitioning of the sparse matrix, each time splitting a rectangular matrix into two parts with a nearly equal number of nonzeros. The communication volume caused by the split is minimized. After the matrix partitioning, the input and output vectors are partitioned with the objective of minimizing the maximum communication volume per processor. Experimental results of our implementation, Mondriaan, for a set of sparse test matrices show a reduction in communication volume compared to one-dimensional methods, and in general a good balance in the communication work. Experimental timings of an actual parallel sparse matrix-vector multiplication on an SGI Origin 3800 computer show that a sufficiently large reduction in communication volume leads to savings in execution time.

Ahmad Mansour - One of the best experts on this subject based on the ideXlab platform.