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

Jeanpierre David - One of the best experts on this subject based on the ideXlab platform.

  • intermediate level synthesis of a gauss jordan Elimination linear solver
    International Parallel and Distributed Processing Symposium, 2015
    Co-Authors: Marcandre Daigneault, Jeanpierre David
    Abstract:

    As the world of computing goes more and more parallel, reconfigurable computing can enable interesting compromises in terms of processing speed and power consumption between CPUs and GPUs. Yet, from a developer's perspective, programming Field-Programmable Gate Arrays to implement application specific processors still represents a significant challenge. In this paper, we present the application of an Intermediate-Level Synthesis methodology to the design of a Gauss-Jordan Elimination linear solver on FPGA. The ILS methodology takes for input a language offering an Algorithmic-State Machine programming model. Each ASM handles blocking and non-blocking connections between data-synchronized channels having streaming interfaces with implicit ready-to-send/receive signals. Using our compiler, a scalable linear solver design reaching as much as 46.2 GFLOPS was designed and tested in a matter of days, showing how the ILS methodology can enable an interesting design time/performance compromise between RTL and HLS methodologies.

  • IPDPS Workshops - Intermediate-Level Synthesis of a Gauss-Jordan Elimination Linear Solver
    2015 IEEE International Parallel and Distributed Processing Symposium Workshop, 2015
    Co-Authors: Marcandre Daigneault, Jeanpierre David
    Abstract:

    As the world of computing goes more and more parallel, reconfigurable computing can enable interesting compromises in terms of processing speed and power consumption between CPUs and GPUs. Yet, from a developer's perspective, programming Field-Programmable Gate Arrays to implement application specific processors still represents a significant challenge. In this paper, we present the application of an Intermediate-Level Synthesis methodology to the design of a Gauss-Jordan Elimination linear solver on FPGA. The ILS methodology takes for input a language offering an Algorithmic-State Machine programming model. Each ASM handles blocking and non-blocking connections between data-synchronized channels having streaming interfaces with implicit ready-to-send/receive signals. Using our compiler, a scalable linear solver design reaching as much as 46.2 GFLOPS was designed and tested in a matter of days, showing how the ILS methodology can enable an interesting design time/performance compromise between RTL and HLS methodologies.

Hartwig Anzt - One of the best experts on this subject based on the ideXlab platform.

  • variable size batched gauss jordan Elimination for block jacobi preconditioning on graphics processors
    Parallel Computing, 2018
    Co-Authors: Hartwig Anzt, Goran Flegar, Enrique S Quintanaorti
    Abstract:

    Abstract In this work, we address the efficient realization of block-Jacobi preconditioning on graphics processing units (GPUs). This task requires the solution of a collection of small and independent linear systems. To fully realize this implementation, we develop a variable-size batched matrix inversion kernel that uses Gauss-Jordan Elimination (GJE) along with a variable-size batched matrix–vector multiplication kernel that transforms the linear systems’ right-hand sides into the solution vectors. Our kernels make heavy use of the increased register count and the warp-local communication associated with newer GPU architectures. Moreover, in the matrix inversion, we employ an implicit pivoting strategy that migrates the workload (i.e., operations) to the place where the data resides instead of moving the data to the executing cores. We complement the matrix inversion with extraction and insertion strategies that allow the block-Jacobi preconditioner to be set up rapidly. The experiments on NVIDIA’s K40 and P100 architectures reveal that our variable-size batched matrix inversion routine outperforms the CUDA basic linear algebra subroutine (cuBLAS) library functions that provide the same (or even less) functionality. We also show that the preconditioner setup and preconditioner application cost can be somewhat offset by the faster convergence of the iterative solver.

  • batched gauss jordan Elimination for block jacobi preconditioner generation on gpus
    Programming Models and Applications for Multicores and Manycores, 2017
    Co-Authors: Hartwig Anzt, Goran Flegar, Jack Dongarra, Enrique S Quintanaorti
    Abstract:

    In this paper, we design and evaluate a routine for the efficient generation of block-Jacobi preconditioners on graphics processing units (GPUs). Concretely, to exploit the architecture of the graphics accelerator, we develop a batched Gauss-Jordan Elimination CUDA kernel for matrix inversion that embeds an implicit pivoting technique and handles the entire inversion process in the GPU registers. In addition, we integrate extraction and insertion CUDA kernels to rapidly set up the block-Jacobi preconditioner. Our experiments compare the performance of our implementation against a sequence of batched routines from the MAGMA library realizing the inversion via the LU factorization with partial pivoting. Furthermore, we evaluate the costs of different strategies for the block-Jacobi extraction and insertion steps, using a variety of sparse matrices from the SuiteSparse matrix collection. Finally, we assess the efficiency of the complete block-Jacobi preconditioner generation in the context of an iterative solver applied to a set of computational science problems, and quantify its benefits over a scalar Jacobi preconditioner.

  • PMAM@PPoPP - Batched Gauss-Jordan Elimination for Block-Jacobi Preconditioner Generation on GPUs
    Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, 2017
    Co-Authors: Hartwig Anzt, Goran Flegar, Jack Dongarra, Enrique S. Quintana-ortí
    Abstract:

    In this paper, we design and evaluate a routine for the efficient generation of block-Jacobi preconditioners on graphics processing units (GPUs). Concretely, to exploit the architecture of the graphics accelerator, we develop a batched Gauss-Jordan Elimination CUDA kernel for matrix inversion that embeds an implicit pivoting technique and handles the entire inversion process in the GPU registers. In addition, we integrate extraction and insertion CUDA kernels to rapidly set up the block-Jacobi preconditioner. Our experiments compare the performance of our implementation against a sequence of batched routines from the MAGMA library realizing the inversion via the LU factorization with partial pivoting. Furthermore, we evaluate the costs of different strategies for the block-Jacobi extraction and insertion steps, using a variety of sparse matrices from the SuiteSparse matrix collection. Finally, we assess the efficiency of the complete block-Jacobi preconditioner generation in the context of an iterative solver applied to a set of computational science problems, and quantify its benefits over a scalar Jacobi preconditioner.

Do Hoang Giang - One of the best experts on this subject based on the ideXlab platform.

  • application of quantum gauss jordan Elimination code to quantum secret sharing code
    International Journal of Theoretical Physics, 2018
    Co-Authors: Do Ngoc Diep, Do Hoang Giang
    Abstract:

    The QSS codes associated with a MSP code are based on finding an invertible matrix V, solving the system $\mathbf {v}_{A}^{T}M_{B} \left (\begin {array}{c} \mathbf {s}\\ \mathbf {a} \end {array}\right )=\mathbf {s}$ . We propose a quantum Gauss-Jordan Elimination Procedure to produce such a pivotal matrix V by using the Grover search code. The complexity of solving is of square-root order of the cardinal number of the unauthorized set $\sqrt {2^{|B|}}$ .

  • quantum gauss jordan Elimination and simulation of accounting principles on quantum computers
    International Journal of Theoretical Physics, 2017
    Co-Authors: Do Ngoc Diep, Do Hoang Giang, Nguyen Van Minh
    Abstract:

    The paper is devoted to a version of Quantum Gauss-Jordan Elimination and its applications. In the first part, we construct the Quantum Gauss-Jordan Elimination (QGJE) Algorithm and estimate the complexity of computation of Reduced Row Echelon Form (RREF) of N × N matrices. The main result asserts that QGJE has computation time is of order 2N/2. The second part is devoted to a new idea of simulation of accounting by quantum computing. We first expose the actual accounting principles in a pure mathematics language. Then, we simulate the accounting principles on quantum computers. We show that, all accounting actions are exhousted by the described basic actions. The main problems of accounting are reduced to some system of linear equations in the economic model of Leontief. In this simulation, we use our constructed Quantum Gauss-Jordan Elimination to solve the problems and the complexity of quantum computing is a square root order faster than the complexity in classical computing.

  • quantum gauss jordan Elimination
    arXiv: Quantum Physics, 2005
    Co-Authors: Do Ngoc Diep, Do Hoang Giang
    Abstract:

    In this paper we construct the Quantum Gau\ss Jordan Elimination (QGJE) Algorithm and estimate the complexity time of computation of Reduced Row Echelon Form (RREF) of an $N\times N$ matrix using QGJE procedure. The main theorem asserts that QGJE has computation time of order $2^{N/2}$.

Do Ngoc Diep - One of the best experts on this subject based on the ideXlab platform.

  • application of quantum gauss jordan Elimination code to quantum secret sharing code
    International Journal of Theoretical Physics, 2018
    Co-Authors: Do Ngoc Diep, Do Hoang Giang
    Abstract:

    The QSS codes associated with a MSP code are based on finding an invertible matrix V, solving the system $\mathbf {v}_{A}^{T}M_{B} \left (\begin {array}{c} \mathbf {s}\\ \mathbf {a} \end {array}\right )=\mathbf {s}$ . We propose a quantum Gauss-Jordan Elimination Procedure to produce such a pivotal matrix V by using the Grover search code. The complexity of solving is of square-root order of the cardinal number of the unauthorized set $\sqrt {2^{|B|}}$ .

  • quantum gauss jordan Elimination and simulation of accounting principles on quantum computers
    International Journal of Theoretical Physics, 2017
    Co-Authors: Do Ngoc Diep, Do Hoang Giang, Nguyen Van Minh
    Abstract:

    The paper is devoted to a version of Quantum Gauss-Jordan Elimination and its applications. In the first part, we construct the Quantum Gauss-Jordan Elimination (QGJE) Algorithm and estimate the complexity of computation of Reduced Row Echelon Form (RREF) of N × N matrices. The main result asserts that QGJE has computation time is of order 2N/2. The second part is devoted to a new idea of simulation of accounting by quantum computing. We first expose the actual accounting principles in a pure mathematics language. Then, we simulate the accounting principles on quantum computers. We show that, all accounting actions are exhousted by the described basic actions. The main problems of accounting are reduced to some system of linear equations in the economic model of Leontief. In this simulation, we use our constructed Quantum Gauss-Jordan Elimination to solve the problems and the complexity of quantum computing is a square root order faster than the complexity in classical computing.

  • quantum gauss jordan Elimination
    arXiv: Quantum Physics, 2005
    Co-Authors: Do Ngoc Diep, Do Hoang Giang
    Abstract:

    In this paper we construct the Quantum Gau\ss Jordan Elimination (QGJE) Algorithm and estimate the complexity time of computation of Reduced Row Echelon Form (RREF) of an $N\times N$ matrix using QGJE procedure. The main theorem asserts that QGJE has computation time of order $2^{N/2}$.

Enrique S. Quintana-ortí - One of the best experts on this subject based on the ideXlab platform.

  • PMAM@PPoPP - Batched Gauss-Jordan Elimination for Block-Jacobi Preconditioner Generation on GPUs
    Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, 2017
    Co-Authors: Hartwig Anzt, Goran Flegar, Jack Dongarra, Enrique S. Quintana-ortí
    Abstract:

    In this paper, we design and evaluate a routine for the efficient generation of block-Jacobi preconditioners on graphics processing units (GPUs). Concretely, to exploit the architecture of the graphics accelerator, we develop a batched Gauss-Jordan Elimination CUDA kernel for matrix inversion that embeds an implicit pivoting technique and handles the entire inversion process in the GPU registers. In addition, we integrate extraction and insertion CUDA kernels to rapidly set up the block-Jacobi preconditioner. Our experiments compare the performance of our implementation against a sequence of batched routines from the MAGMA library realizing the inversion via the LU factorization with partial pivoting. Furthermore, we evaluate the costs of different strategies for the block-Jacobi extraction and insertion steps, using a variety of sparse matrices from the SuiteSparse matrix collection. Finally, we assess the efficiency of the complete block-Jacobi preconditioner generation in the context of an iterative solver applied to a set of computational science problems, and quantify its benefits over a scalar Jacobi preconditioner.

  • ICA3PP Workshops - Tuning the Blocksize for Dense Linear Algebra Factorization Routines with the Roofline Model
    Algorithms and Architectures for Parallel Processing, 2016
    Co-Authors: Peter Benner, Pablo Ezzatti, Enrique S. Quintana-ortí, Alfredo Remón, Juan Pablo Silva
    Abstract:

    The optimization of dense linear algebra operations is a fundamental task in the solution of many scientific computing applications. The Roofline Model is a tool that provides an estimation of the performance that a computational kernel can attain on a hardware platform. Therefore, the RM can be used to investigate whether a computational kernel can be further accelerated. We present an approach, based on the RM, to optimize the algorithmic parameters of dense linear algebra kernels. In particular, we perform a basic analysis to identify the optimal values for the kernel parameters. As a proof-of-concept, we apply this technique to optimize a blocked algorithm for matrix inversion via Gauss-Jordan Elimination. In addition, we extend this technique to multi-block computational kernels. An experimental evaluation validates the method and shows its convenience. We remark that the results obtained can be extended to other computational kernels similar to Gauss-Jordan Elimination such as, e.g., matrix factorizations and the solution of linear least squares problems.

  • Trading Off Performance for Energy in Linear Algebra Operations with Applications in Control Theory
    Clei Electronic Journal, 2014
    Co-Authors: Peter Benner, Pablo Ezzatti, Enrique S. Quintana-ortí, Alfredo Remón
    Abstract:

    We analyze the performance-power-energy balance of a conventional Intel Xeon multicore processor and two low-power architectures ‐an Intel Atom processor and a system with a quad-core ARM Cortex A9+NVIDIA Quadro 1000M‐ using a high performance implementation of Gauss-Jordan Elimination (GJE) for matrix inversion. The blocked version of this algorithm employed in the experimental evaluation mostly comprises matrix-matrix products, so that the results from the evaluation carry beyond the simple matrix inversion and are representative for a wide variety of dense linear algebra operations/codes.

  • ICA3PP (2) - On the Impact of Optimization on the Time-Power-Energy Balance of Dense Linear Algebra Factorizations
    Algorithms and Architectures for Parallel Processing, 2013
    Co-Authors: Peter Benner, Pablo Ezzatti, Enrique S. Quintana-ortí, Alfredo Remón
    Abstract:

    We investigate the effect that commonoptimization techniques for general-purpose multicore processors (either manual, compiler-driven, in the form of highly tuned libraries, or orchestrated by a runtime) exert on the performance-power-energy trade-off of dense linear algebra routines. The algorithm employed for this analysis is matrix inversion via Gauss-Jordan Elimination, but the results from the evaluation carry beyond this particular operation and are representative for a variety of dense linear algebra computations, especially, dense matrix factorizations.

  • HPCS - High performance matrix inversion of SPD matrices on graphics processors
    2011 International Conference on High Performance Computing & Simulation, 2011
    Co-Authors: Peter Benner, Pablo Ezzatti, Enrique S. Quintana-ortí, Alfredo Remón
    Abstract:

    We introduce high performance codes for the inversion of a symmetric positive definite matrix. Two alternativesare studied and evaluated, the traditional approach based onthe Cholesky factorization and the Gauss-Jordan Elimination algorithm. Several implementations of the two algorithms are developed on a hybrid architecture equipped with a general purpose multi-core processor and a graphics processor. Numerical experiments show the efficiency attained by the proposed implementations on the target architecture.