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

Elias Vicari - One of the best experts on this subject based on the ideXlab platform.

  • optimal sparse matrix dense vector multiplication in the i o model
    ACM Symposium on Parallel Algorithms and Architectures, 2007
    Co-Authors: Michael A Bender, Riko Jacob, Gerth Stolting Brodal, Rolf Fagerberg, Elias Vicari
    Abstract:

    We analyze the problem of sparse-matrix dense-vector multiplication (SpMV) in the I/O-model. The task of SpMV is to compute y := Ax, where A is a sparse N x N matrix and x and y are vectors. Here, sparsity is expressed by the parameter k that states that A has a total of at most kN nonzeros, i.e., an average number of k nonzeros per column. The extreme choices for parameter k are well studied special cases, namely for k=1 permuting and for k=N dense matrix-vector multiplication. We study the worst-case complexity of this computational task, i.e., what is the best possible upper bound on the number of I/Os depending on k and N only. We determine this complexity up to a constant factor for large ranges of the parameters. By our arguments, we find that most matrices with kN nonzeros require this number of I/Os, even if the program may depend on the structure of the matrix. The model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung. We study two variants of the problem, depending on the Memory Layout of A. If A is stored in column major Layout, SpMV has I/O complexity Θ(min{kN B(1+logM/BN max{M,k}), kN}) for k ≤ N1-e and any constant 1> e > 0. If the algorithm can choose the Memory Layout, the I/O complexity of SpMV is Θ(min{kN B(1+logM/BN kM), kN]) for k ≤ 3√N. In the cache oblivious setting with tall cache assumption M ≥ B1+e, the I/O complexity is Ο(kN B(1+logM/B N k)) for A in column major Layout.

  • optimal sparse matrix dense vector multiplication in the i o model
    Technical report Swiss Federal Institute of Technology Zurich Department of Computer Science, 2006
    Co-Authors: Michael A Bender, Riko Jacob, Gerth Stolting Brodal, Rolf Fagerberg, Elias Vicari
    Abstract:

    We study the problem of sparse-matrix dense-vector multiplication (SpMV) in external Memory. The task of SpMV is to compute y:=Ax, where A is a sparse N×N matrix and x is a vector. We express sparsity by a parameter k, and for each choice of k consider the class of matrices where the number of nonzero entries is kN, i.e., where the average number of nonzero entries per column is k. We investigate what is the external worst-case complexity, i.e., the best possible upper bound on the number of I/Os, as a function of k, N and the parameters M (Memory size) and B (track size) of the I/O-model. We determine this complexity up to a constant factor for all meaningful choices of these parameters, as long as k≤N 1−e , where e depends on the problem variant. Our model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung. We study variants of the problem, differing in the Memory Layout of A. If A is stored in column major Layout, we prove that SpMV has I/O complexity $\Theta(\min\{\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{\max\{k,M\}}\},\,kN\})$for k≤N 1−e and any constant 0Memory Layout, the I/O complexity reduces to $\Theta ({\min\{\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{kM}\},kN\}})$for $k\leq\sqrt[3]{N}$. In contrast, if the algorithm must be able to handle an arbitrary Layout of the matrix, the I/O complexity is $\Theta ({\min\{\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{M}\},kN\}})$for k≤N/2. In the cache oblivious setting we prove that with tall cache assumption M≥B 1+e , the I/O complexity is $\mathcal {O}({\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{\max\{k,M\}}\}})$for A in column major Layout.

Riko Jacob - One of the best experts on this subject based on the ideXlab platform.

  • efficient regular sparse grid hierarchization by a dynamic Memory Layout
    2014
    Co-Authors: Riko Jacob
    Abstract:

    We consider a new hierarchization algorithm for sparse grids of high dimension and low level. The algorithm is inspired by the theory of Memory efficient algorithms. It is based on a cache-friendly Layout of a compact data storage, and the idea of rearranging the data for the different phases of the algorithm. The core steps of the algorithm can be phrased as multiplying the input vector with two sparse matrices. A generalized counting makes it possible to create (or apply) the matrices in constant time per row. The algorithm is implemented as a proof of concept and first experiments show that it performs well in comparison with the previous implementation SG++, in particular for the case of high dimensions and low level.

  • optimal sparse matrix dense vector multiplication in the i o model
    ACM Symposium on Parallel Algorithms and Architectures, 2007
    Co-Authors: Michael A Bender, Riko Jacob, Gerth Stolting Brodal, Rolf Fagerberg, Elias Vicari
    Abstract:

    We analyze the problem of sparse-matrix dense-vector multiplication (SpMV) in the I/O-model. The task of SpMV is to compute y := Ax, where A is a sparse N x N matrix and x and y are vectors. Here, sparsity is expressed by the parameter k that states that A has a total of at most kN nonzeros, i.e., an average number of k nonzeros per column. The extreme choices for parameter k are well studied special cases, namely for k=1 permuting and for k=N dense matrix-vector multiplication. We study the worst-case complexity of this computational task, i.e., what is the best possible upper bound on the number of I/Os depending on k and N only. We determine this complexity up to a constant factor for large ranges of the parameters. By our arguments, we find that most matrices with kN nonzeros require this number of I/Os, even if the program may depend on the structure of the matrix. The model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung. We study two variants of the problem, depending on the Memory Layout of A. If A is stored in column major Layout, SpMV has I/O complexity Θ(min{kN B(1+logM/BN max{M,k}), kN}) for k ≤ N1-e and any constant 1> e > 0. If the algorithm can choose the Memory Layout, the I/O complexity of SpMV is Θ(min{kN B(1+logM/BN kM), kN]) for k ≤ 3√N. In the cache oblivious setting with tall cache assumption M ≥ B1+e, the I/O complexity is Ο(kN B(1+logM/B N k)) for A in column major Layout.

  • optimal sparse matrix dense vector multiplication in the i o model
    Technical report Swiss Federal Institute of Technology Zurich Department of Computer Science, 2006
    Co-Authors: Michael A Bender, Riko Jacob, Gerth Stolting Brodal, Rolf Fagerberg, Elias Vicari
    Abstract:

    We study the problem of sparse-matrix dense-vector multiplication (SpMV) in external Memory. The task of SpMV is to compute y:=Ax, where A is a sparse N×N matrix and x is a vector. We express sparsity by a parameter k, and for each choice of k consider the class of matrices where the number of nonzero entries is kN, i.e., where the average number of nonzero entries per column is k. We investigate what is the external worst-case complexity, i.e., the best possible upper bound on the number of I/Os, as a function of k, N and the parameters M (Memory size) and B (track size) of the I/O-model. We determine this complexity up to a constant factor for all meaningful choices of these parameters, as long as k≤N 1−e , where e depends on the problem variant. Our model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung. We study variants of the problem, differing in the Memory Layout of A. If A is stored in column major Layout, we prove that SpMV has I/O complexity $\Theta(\min\{\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{\max\{k,M\}}\},\,kN\})$for k≤N 1−e and any constant 0Memory Layout, the I/O complexity reduces to $\Theta ({\min\{\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{kM}\},kN\}})$for $k\leq\sqrt[3]{N}$. In contrast, if the algorithm must be able to handle an arbitrary Layout of the matrix, the I/O complexity is $\Theta ({\min\{\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{M}\},kN\}})$for k≤N/2. In the cache oblivious setting we prove that with tall cache assumption M≥B 1+e , the I/O complexity is $\mathcal {O}({\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{\max\{k,M\}}\}})$for A in column major Layout.

Michael A Bender - One of the best experts on this subject based on the ideXlab platform.

  • optimal sparse matrix dense vector multiplication in the i o model
    ACM Symposium on Parallel Algorithms and Architectures, 2007
    Co-Authors: Michael A Bender, Riko Jacob, Gerth Stolting Brodal, Rolf Fagerberg, Elias Vicari
    Abstract:

    We analyze the problem of sparse-matrix dense-vector multiplication (SpMV) in the I/O-model. The task of SpMV is to compute y := Ax, where A is a sparse N x N matrix and x and y are vectors. Here, sparsity is expressed by the parameter k that states that A has a total of at most kN nonzeros, i.e., an average number of k nonzeros per column. The extreme choices for parameter k are well studied special cases, namely for k=1 permuting and for k=N dense matrix-vector multiplication. We study the worst-case complexity of this computational task, i.e., what is the best possible upper bound on the number of I/Os depending on k and N only. We determine this complexity up to a constant factor for large ranges of the parameters. By our arguments, we find that most matrices with kN nonzeros require this number of I/Os, even if the program may depend on the structure of the matrix. The model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung. We study two variants of the problem, depending on the Memory Layout of A. If A is stored in column major Layout, SpMV has I/O complexity Θ(min{kN B(1+logM/BN max{M,k}), kN}) for k ≤ N1-e and any constant 1> e > 0. If the algorithm can choose the Memory Layout, the I/O complexity of SpMV is Θ(min{kN B(1+logM/BN kM), kN]) for k ≤ 3√N. In the cache oblivious setting with tall cache assumption M ≥ B1+e, the I/O complexity is Ο(kN B(1+logM/B N k)) for A in column major Layout.

  • optimal sparse matrix dense vector multiplication in the i o model
    Technical report Swiss Federal Institute of Technology Zurich Department of Computer Science, 2006
    Co-Authors: Michael A Bender, Riko Jacob, Gerth Stolting Brodal, Rolf Fagerberg, Elias Vicari
    Abstract:

    We study the problem of sparse-matrix dense-vector multiplication (SpMV) in external Memory. The task of SpMV is to compute y:=Ax, where A is a sparse N×N matrix and x is a vector. We express sparsity by a parameter k, and for each choice of k consider the class of matrices where the number of nonzero entries is kN, i.e., where the average number of nonzero entries per column is k. We investigate what is the external worst-case complexity, i.e., the best possible upper bound on the number of I/Os, as a function of k, N and the parameters M (Memory size) and B (track size) of the I/O-model. We determine this complexity up to a constant factor for all meaningful choices of these parameters, as long as k≤N 1−e , where e depends on the problem variant. Our model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung. We study variants of the problem, differing in the Memory Layout of A. If A is stored in column major Layout, we prove that SpMV has I/O complexity $\Theta(\min\{\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{\max\{k,M\}}\},\,kN\})$for k≤N 1−e and any constant 0Memory Layout, the I/O complexity reduces to $\Theta ({\min\{\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{kM}\},kN\}})$for $k\leq\sqrt[3]{N}$. In contrast, if the algorithm must be able to handle an arbitrary Layout of the matrix, the I/O complexity is $\Theta ({\min\{\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{M}\},kN\}})$for k≤N/2. In the cache oblivious setting we prove that with tall cache assumption M≥B 1+e , the I/O complexity is $\mathcal {O}({\frac{kN}{B}\max\{1,\log_{M/B}\frac{N}{\max\{k,M\}}\}})$for A in column major Layout.

Xianhe Sun - One of the best experts on this subject based on the ideXlab platform.

  • W.: Automatic Memory optimizations for improving MPI derived datatype performance
    Springer, 2006
    Co-Authors: Surendra Byna, Xianhe Sun, Rajeev Thakur
    Abstract:

    Abstract. MPI derived datatypes allow users to describe noncontiguous Memory Layout and communicate noncontiguous data with a single communication function. This powerful feature provides an MPI implementation with optimized transfer of noncontiguous data. In practice, however, many implementations of MPI derived datatypes perform poorly, which makes application developers avoid using this feature. In this paper, we present a technique to automatically select templates that are optimized for Memory performance based on the access pattern of derived datatypes. We implement this mechanism in the MPICH2 source code. The performance of our implementation is compared to well-written manual packing/unpacking routines and original MPICH2 implementation. We show that performance for various derived datatypes is significantly improved and comparable to that of optimized manual routines

  • Automatic Memory Optimizations for Improving MPI Derived Datatype Performance,” selected for publication
    2006
    Co-Authors: Surendra Byna, Xianhe Sun, Rajeev Thakur
    Abstract:

    Abstract. MPI derived datatypes allow users to describe noncontiguous Memory Layout and communicate noncontiguous data with a single communication function. This powerful feature enables an MPI implementation to optimize the transfer of noncontiguous data. In practice, however, many implementations of MPI derived datatypes perform poorly, which makes application developers avoid using this feature. In this paper, we present a technique to automatically select templates that are optimized for Memory performance based on the access pattern of derived datatypes. We implement this mechanism in the MPICH2 source code. The performance of our implementation is compared to well-written manual packing/unpacking routines and original MPICH2 implementation. We show that performance for various derived datatypes is significantly improved and comparable to that of optimized manual routines

  • Automatic Memory Optimizations for Improving MPI Derived Datatype Performance
    Springer-Verlag, 2006
    Co-Authors: Surendra Byna, Xianhe Sun, Rajeev Thakur
    Abstract:

    Abstract. MPI derived datatypes allow users to describe noncontiguous Memory Layout and communicate noncontiguous data with a single communication function. This powerful feature enables an MPI implementation to optimize the transfer of noncontiguous data. In practice, however, many implementations of MPI derived datatypes perform poorly, which makes application developers avoid using this feature. In this paper, we present a technique to automatically select templates that are optimized for Memory performance based on the access pattern of derived datatypes. We implement this mechanism in the MPICH2 source code. The performance of our implementation is compared to well-written manual packing/unpacking routines and original MPICH2 implementation. We show that performance for various derived datatypes is significantly improved and comparable to that of optimized manual routines

  • improving the performance of mpi derived datatypes by optimizing Memory access cost
    International Conference on Cluster Computing, 2003
    Co-Authors: Xianhe Sun
    Abstract:

    The MPI Standard supports derived datatypes, which allow users to describe noncontiguous Memory Layout and communicate noncontiguous data with a single communication function. This feature enables an MPI implementation to optimize the transfer of noncontiguous data. In practice, however, few MPI implementations implement derived datatypes in a way that performs better than what the user can achieve by manually packing data into a contiguous buffer and then calling an MPI function. In this paper, we present a technique for improving the performance of derived datatypes by automatically using packing algorithms that are optimized for Memory-access cost. The packing algorithms use Memory-optimization techniques that the user cannot apply easily without advanced knowledge of the Memory architecture. We present performance results for a matrix-transpose example that demonstrate that our implementation of derived datatypes significantly outperforms both manual packing by the user and the existing derived-datatype code in the MPI implementation (MPICH).

Eelco Visser - One of the best experts on this subject based on the ideXlab platform.

  • scopes describe frames a uniform model for Memory Layout in dynamic semantics
    European Conference on Object-Oriented Programming, 2016
    Co-Authors: Casper Bach Poulsen, Pierre Neron, Andrew Tolmach, Eelco Visser
    Abstract:

    Semantic specifications do not make a systematic connection between the names and scopes in the static structure of a program and Memory Layout, and access during its execution. In this paper, we introduce a systematic approach to the alignment of names in static semantics and Memory in dynamic semantics, building on the scope graph framework for name resolution. We develop a uniform Memory model consisting of frames that instantiate the scopes in the scope graph of a program. This provides a language-independent correspondence between static scopes and run-time Memory Layout, and between static resolution paths and run-time Memory access paths. The approach scales to a range of binding features, supports straightforward type soundness proofs, and provides the basis for a language-independent specification of sound reachability-based garbage collection.

  • scopes describe frames a uniform model for Memory Layout in dynamic semantics artifact
    European Conference on Object-Oriented Programming, 2016
    Co-Authors: Casper Bach Poulsen, Pierre Neron, Andrew Tolmach, Eelco Visser
    Abstract:

    Our paper introduces a systematic approach to the alignment of names in the static structure of a program, and Memory Layout and access during its execution. We develop a uniform Memory model consisting of frames that instantiate the scopes in the scope graph of a program. This provides a language-independent correspondence between static scopes and run-time Memory Layout, and between static resolution paths and run-time Memory access paths. The approach scales to a range of binding features, supports straightforward type soundness proofs, and provides the basis for a language-independent specification of sound reachability-based garbage collection. This Coq artifact showcases how our uniform model for Memory Layout in dynamic semantics provides structure to type soundness proofs. The artifact contains type soundness proofs mechanized in Coq for (supersets of) all languages in the paper. The type soundness proofs rely on a language-independent framework formalizing scope graphs and frame heaps.