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

Ching-hsien Hsu - One of the best experts on this subject based on the ideXlab platform.

  • Processor Mapping Technique For Communication Free Data Redistribution on
    2004
    Co-Authors: Ching-hsien Hsu
    Abstract:

    In this paper, we present the processor mapping technique to eliminate amount of data exchange in runtime data redistribution on symmetric matrices. The main idea of the proposed technique is to develop mathematical functions for mapping destination processors to a new sequence of processor id. The realigned order of destination processors is then used to perform data redistribution in the receiving phase. Together with a local Matrix Transposition scheme, inter-processor communication can be totally eliminated in runtime redistribution. The other improvement of this approach is that one does not need to compute the complicated communication sets. The indexing cost is reduced largely. The theoretical analysis shows that (p−1)/p data transmission cost can be saved for a redistribution over p×p processors grid. Experimental result also shows that the processor mapping technique provides superior improvement for runtime data redistribution.

  • ISPAN - Processor mapping technique for communication free data redistribution on symmetrical Matrix
    7th International Symposium on Parallel Architectures Algorithms and Networks 2004. Proceedings., 2004
    Co-Authors: Ching-hsien Hsu
    Abstract:

    In this paper, we present the processor mapping technique to eliminate amount of data exchange in runtime data redistribution on symmetric matrices. The main idea of the proposed technique is to develop mathematical functions for mapping destination processors to a new sequence of processor id. The realigned order of destination processors is then used to perform data redistribution in the receiving phase. Together with a local Matrix Transposition scheme, interprocessor communication can be totally eliminated in runtime redistribution. The other improvement of this approach is that one does not need to compute the complicated communication sets. The indexing cost is reduced largely. The theoretical analysis shows that (p-1)/p data transmission cost can be saved for a redistribution over p/spl times/p processors grid. Experimental result also shows that the processor mapping technique provides superior improvement for runtime data redistribution.

Andrey Vladimirov - One of the best experts on this subject based on the ideXlab platform.

  • Profiling-Guided Optimization
    High Performance Parallelism Pearls, 2015
    Co-Authors: Andrey Vladimirov
    Abstract:

    The chapter focuses on a Matrix Transposition, a small and self-contained workload of great practical value. The optimization process applied to the code relies exclusively on programming in a high-level language plus utilization of the OpenMP framework. The result is a portable code that can run on both CPU (processor) and MIC (coprocessor) architectures, and can be recompiled for future generations of Intel architectures. The focus of the chapter is on the use of Intel® VTune™ Amplifier XE reports to understand where to apply optimization. Through VTune, the performance monitoring functionality of Intel Xeon Phi coprocessors is showcased not only to detect bottlenecks but also to point out overall performance issues and possible resolution methods. In short, this chapter demonstrates the familial relationship between Intel processors and coprocessors plus the Intel software development tools.

  • Multithreaded Transposition of Square Matrices with Common Code for Intel Xeon Processors and Intel Xeon Phi Coprocessors
    2013
    Co-Authors: Andrey Vladimirov
    Abstract:

    In-place Matrix Transposition, a standard operation in linear algebra, is a memory bandwidth-bound operation. The theoretical maximum performance of Transposition is the memory copy bandwidth. However, due to non-contiguous memory access in the Transposition operation, practical performance is usually lower. The ratio of the Transposition rate to the memory copy bandwidth is a measure of the Transposition algorithm efficiency. This paper demonstrates and discusses an efficient C language implementation of parallel in-place square Matrix Transposition. For large matrices, it achieves a Transposition rate of 49 GB/s (82% efficiency) on Intel Xeon CPUs and 113 GB/s (67% efficiency) on Intel Xeon Phi coprocessors. The code is tuned with pragma-based compiler hints and compiler arguments. Thread parallelism in the code is handled by OpenMP, and vectorization is automatically implemented by the Intel compiler. This approach allows to use the same C code for a CPU and for a MIC architecture executable, both demonstrating high efficiency. For benchmarks, an Intel Xeon Phi 7110P coprocessor is used.

  • Cache Traffic Optimization on Intel Xeon Phi Coprocessors for Parallel In-Place Square Matrix Transposition with Intel Cilk Plus and OpenMP
    2013
    Co-Authors: Andrey Vladimirov
    Abstract:

    Numerical algorithms sensitive to the performance of processor caches can be optimized by increasing the locality of data access. Loop tiling and recursive divide-and-conquer are common methods for cache traffic optimization. This paper studies the applicability of these optimization methods in the Intel Xeon Phi architecture for the in-place square Matrix Transposition operation. Optimized implementations in the Intel Cilk Plus and OpenMP frameworks are presented and benchmarked. Cache-oblivious nature of the recursive algorithm is compared to the tunable character of the tiled method. Results show that Intel Xeon Phi coprocessors transpose large matrices faster than the host system, however, smaller matrices are more efficiently transposed by the host. On the coprocessor, the Intel Cilk Plus framework excels for large Matrix sizes, but incurs a significant parallelization overhead for smaller sizes. Transposition of smaller matrices on the coprocessor is faster with OpenMP.

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

  • a decomposition for in place Matrix Transposition
    ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2014
    Co-Authors: Bryan Catanzaro, Alexander Keller, Michael Garland
    Abstract:

    We describe a decomposition for in-place Matrix Transposition, with applications to Array of Structures memory accesses on SIMD processors. Traditional approaches to in-place Matrix Transposition involve cycle following, which is difficult to parallelize, and on matrices of dimension m by n require O(mn log mn) work when limited to less than O(mn) auxiliary space. Our decomposition allows the rows and columns to be operated on independently during in-place Transposition, reducing work complexity to O(mn), given O(max(m, n)) auxiliary space. This decomposition leads to an efficient and naturally parallel algorithm: we have measured median throughput of 19.5 GB/s on an NVIDIA Tesla K20c processor. An implementation specialized for the skinny matrices that arise when converting Arrays of Structures to Structures of Arrays yields median throughput of 34.3 GB/s, and a maximum throughput of 51 GB/s. Because of the simple structure of this algorithm, it is particularly suited for implementation using SIMD instructions to transpose the small arrays that arise when SIMD processors load from or store to Arrays of Structures. Using this algorithm to cooperatively perform accesses to Arrays of Structures, we measure 180 GB/s throughput on the K20c, which is up to 45 times faster than compiler-generated Array of Structures accesses. In this paper, we explain the algorithm, prove its correctness and complexity, and explain how it can be instantiated efficiently for solving various transpose problems on both CPUs and GPUs.

  • PPOPP - A decomposition for in-place Matrix Transposition
    Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming - PPoPP '14, 2014
    Co-Authors: Bryan Catanzaro, Alexander Keller, Michael Garland
    Abstract:

    We describe a decomposition for in-place Matrix Transposition, with applications to Array of Structures memory accesses on SIMD processors. Traditional approaches to in-place Matrix Transposition involve cycle following, which is difficult to parallelize, and on matrices of dimension m by n require O(mn log mn) work when limited to less than O(mn) auxiliary space. Our decomposition allows the rows and columns to be operated on independently during in-place Transposition, reducing work complexity to O(mn), given O(max(m, n)) auxiliary space. This decomposition leads to an efficient and naturally parallel algorithm: we have measured median throughput of 19.5 GB/s on an NVIDIA Tesla K20c processor. An implementation specialized for the skinny matrices that arise when converting Arrays of Structures to Structures of Arrays yields median throughput of 34.3 GB/s, and a maximum throughput of 51 GB/s. Because of the simple structure of this algorithm, it is particularly suited for implementation using SIMD instructions to transpose the small arrays that arise when SIMD processors load from or store to Arrays of Structures. Using this algorithm to cooperatively perform accesses to Arrays of Structures, we measure 180 GB/s throughput on the K20c, which is up to 45 times faster than compiler-generated Array of Structures accesses. In this paper, we explain the algorithm, prove its correctness and complexity, and explain how it can be instantiated efficiently for solving various transpose problems on both CPUs and GPUs.

Fred G Gustavson - One of the best experts on this subject based on the ideXlab platform.

  • PPAM (2) - Algorithms for In-Place Matrix Transposition
    Parallel Processing and Applied Mathematics, 2014
    Co-Authors: Fred G Gustavson, David W Walker
    Abstract:

    This paper presents an implementation of an in-place swap-based algorithm for transposing rectangular matrices, and a proof of correctness is also sketched. The implementation is based on an algorithm described by Tretyakov and Tyrtyshnikov [4], but we have introduced a number of variations. In particular, we show how the original algorithm can be modified to require constant additional memory. We also identify opportunities for exploiting parallelism.

  • algorithms for in place Matrix Transposition
    International Conference on Parallel Processing, 2013
    Co-Authors: Fred G Gustavson, David W Walker
    Abstract:

    This paper presents an implementation of an in-place swap-based algorithm for transposing rectangular matrices, and a proof of correctness is also sketched. The implementation is based on an algorithm described by Tretyakov and Tyrtyshnikov [4], but we have introduced a number of variations. In particular, we show how the original algorithm can be modified to require constant additional memory. We also identify opportunities for exploiting parallelism.

Viktor K Prasanna - One of the best experts on this subject based on the ideXlab platform.

  • An efficient algorithm for out-of-core Matrix Transposition
    IEEE Transactions on Computers, 2002
    Co-Authors: Jinwoo Suh, Viktor K Prasanna
    Abstract:

    Efficient Transposition of out-of-core matrices has been widely studied. These efforts have focused on reducing the number of I/O operations. However, in state-of-the-art architectures, the memory-memory data transfer time and the index computation time are also significant components of the overall time. In this paper, we propose an algorithm that considers the index computation time and the I/O time and reduces the overall execution time. Our algorithm reduces the total execution time by reducing the number of I/O operations and eliminating the index computation. In doing so, two techniques are employed: writing the data on to disk in pre-defined patterns and balancing the number of disk read and write operations. The index computation time, which is an expensive operation involving two divisions and a multiplication, is eliminated by partitioning the memory into read and write buffers. The expensive in-processor permutation is replaced by data collection from the read buffer to the write buffer. Even though this partitioning may increase the number of I/O operations for some cases, it results in an overall reduction in the execution time due to the elimination of the expensive index computation. Our algorithm is analyzed using the well-known linear model and the parallel disk model. The experimental results on a Sun Enterprise, an SGI R12000 and a Pentium III show that our algorithm reduces the overall execution time by up to 50% compared with the best known algorithms in the literature.

  • an efficient algorithm for large scale Matrix Transposition
    International Conference on Parallel Processing, 2000
    Co-Authors: Jinwoo Suh, Viktor K Prasanna
    Abstract:

    Efficient Transposition of large-scale matrices has been widely studied. These efforts have focused on reducing the number of I/O operations. However, in the state-of-the-art architectures, data transfer time and index computation time are also significant components of the overall time. In this paper, we propose an algorithm that considers all these costs and reduces the overall execution time. The reduction of the overall execution time is achieved by using two techniques: (1) writing the data onto disk in predefined patterns and (2) balancing the numbers of disk read and write operations. Even though our approach may increase the number of I/O operations for some cases it results in an overall reduction in the execution time. The index computation time, which is an expensive operation involving two divisions and a multiplication, is eliminated by partitioning the memory into two buffers. The expensive in-processor permutation is replaced by data collection operations. Our algorithm is analyzed using the well-known Linear Model and the Parallel Disk Model. The experimental results on a Sun Enterprise and a DEC Alpha show that our algorithm reduces the execution time by about 50%, compared with the best known algorithms in the literature.