The Experts below are selected from a list of 27609 Experts worldwide ranked by ideXlab platform
Saman Amarasinghe - One of the best experts on this subject based on the ideXlab platform.
-
a sparse iteration space transformation framework for sparse Tensor Algebra
Proceedings of the ACM on Programming Languages, 2020Co-Authors: Ryan Senanayake, Stephen Chou, Shoaib Kamil, Saman Amarasinghe, Changwan Hong, Ziheng Wang, Amalee Wilson, Fredrik KjolstadAbstract:We address the problem of optimizing sparse Tensor Algebra in a compiler and show how to define standard loop transformations---split, collapse, and reorder---on sparse iteration spaces. The key idea is to track the transformation functions that map the original iteration space to derived iteration spaces. These functions are needed by the code generator to emit code that maps coordinates between iteration spaces at runtime, since the coordinates in the sparse data structures remain in the original iteration space. We further demonstrate that derived iteration spaces can tile both the universe of coordinates and the subset of nonzero coordinates: the former is analogous to tiling dense iteration spaces, while the latter tiles sparse iteration spaces into statically load-balanced blocks of nonzeros. Tiling the space of nonzeros lets the generated code efficiently exploit heterogeneous compute resources such as threads, vector units, and GPUs. We implement these concepts by extending the sparse iteration theory implementation in the TACO system. The associated scheduling API can be used by performance engineers or it can be the target of an automatic scheduling system. We outline one heuristic autoscheduling system, but other systems are possible. Using the scheduling API, we show how to optimize mixed sparse-dense Tensor Algebra expressions on CPUs and GPUs. Our results show that the sparse transformations are sufficient to generate code with competitive performance to hand-optimized implementations from the literature, while generalizing to all of the Tensor Algebra.
-
a unified iteration space transformation framework for sparse and dense Tensor Algebra
arXiv: Mathematical Software, 2020Co-Authors: Ryan Senanayake, Shoaib Kamil, Fredrik Kjolstad, Changwan Hong, Saman AmarasingheAbstract:We address the problem of optimizing mixed sparse and dense Tensor Algebra in a compiler. We show that standard loop transformations, such as strip-mining, tiling, collapsing, parallelization and vectorization, can be applied to irregular loops over sparse iteration spaces. We also show how these transformations can be applied to the contiguous value arrays of sparse Tensor data structures, which we call their position space, to unlock load-balanced tiling and parallelism. We have prototyped these concepts in the open-source TACO system, where they are exposed as a scheduling API similar to the Halide domain-specific language for dense computations. Using this scheduling API, we show how to optimize mixed sparse/dense Tensor Algebra expressions, how to generate load-balanced code by scheduling sparse Tensor Algebra in position space, and how to generate sparse Tensor Algebra GPU code. Our evaluation shows that our transformations let us generate good code that is competitive with many hand-optimized implementations from the literature.
-
the sparse Tensor Algebra compiler keynote
Compiler Construction, 2019Co-Authors: Saman AmarasingheAbstract:Tensor Algebra is a powerful tool with applications in machine learning, data analytics, engineering, and science. Increasingly often the Tensors are sparse, which means most components are zeros. To get the best performance, currently programmers are left to write kernels for every operation, with different mixes of sparse and dense Tensors in different formats. There are countless combinations, which makes it impossible to manually implement and optimize them all. The Tensor Algebra Compiler (TACO) is the first system to automatically generate kernels for any Tensor Algebra operation on Tensors in any of the commonly used formats. Its performance is competitive with best-in-class hand-optimized kernels in popular libraries, while supporting far more Tensor operations. For more information, see http://Tensor-compiler.org.
-
Tensor Algebra Compilation with Workspaces
2019 IEEE ACM International Symposium on Code Generation and Optimization (CGO), 2019Co-Authors: Fredrik Kjolstad, Shoaib Kamil, Peter Ahrens, Saman AmarasingheAbstract:This paper shows how to extend sparse Tensor Algebra compilers to introduce temporary Tensors called workspaces to avoid inefficient sparse data structures accesses. We develop an intermediate representation (IR) for Tensor operations called concrete index notation that specifies when sub-computations occur and where they are stored. We then describe the workspace transformation in this IR, how to programmatically invoke it, and how the IR is compiled to sparse code. Finally, we show how the transformation can be used to optimize sparse Tensor kernels, including sparse matrix multiplication, sparse Tensor addition, and the matricized Tensor times Khatri-Rao product (MTTKRP). Our results show that the workspace transformation brings the performance of these kernels on par with hand-optimized implementations. For example, we improve the performance of MTTKRP with dense output by up to 35%, and enable generating sparse matrix multiplication and MTTKRP with sparse output, neither of which were supported by prior Tensor Algebra compilers.
-
format abstraction for sparse Tensor Algebra compilers
Proceedings of the ACM on Programming Languages, 2018Co-Authors: Stephen Chou, Fredrik Kjolstad, Saman AmarasingheAbstract:This paper shows how to build a sparse Tensor Algebra compiler that is agnostic to Tensor formats (data layouts). We develop an interface that describes formats in terms of their capabilities and properties, and show how to build a modular code generator where new formats can be added as plugins. We then describe six implementations of the interface that compose to form the dense, CSR/CSF, COO, DIA, ELL, and HASH Tensor formats and countless variants thereof. With these implementations at hand, our code generator can generate code to compute any Tensor Algebra expression on any combination of the aforementioned formats. To demonstrate our technique, we have implemented it in the taco Tensor Algebra compiler. Our modular code generator design makes it simple to add support for new Tensor formats, and the performance of the generated code is competitive with hand-optimized implementations. Furthermore, by extending taco to support a wider range of formats specialized for different application and data characteristics, we can improve end-user application performance. For example, if input data is provided in the COO format, our technique allows computing a single matrix-vector multiplication directly with the data in COO, which is up to 3.6× faster than by first converting the data to CSR.
Fredrik Kjolstad - One of the best experts on this subject based on the ideXlab platform.
-
a sparse iteration space transformation framework for sparse Tensor Algebra
Proceedings of the ACM on Programming Languages, 2020Co-Authors: Ryan Senanayake, Stephen Chou, Shoaib Kamil, Saman Amarasinghe, Changwan Hong, Ziheng Wang, Amalee Wilson, Fredrik KjolstadAbstract:We address the problem of optimizing sparse Tensor Algebra in a compiler and show how to define standard loop transformations---split, collapse, and reorder---on sparse iteration spaces. The key idea is to track the transformation functions that map the original iteration space to derived iteration spaces. These functions are needed by the code generator to emit code that maps coordinates between iteration spaces at runtime, since the coordinates in the sparse data structures remain in the original iteration space. We further demonstrate that derived iteration spaces can tile both the universe of coordinates and the subset of nonzero coordinates: the former is analogous to tiling dense iteration spaces, while the latter tiles sparse iteration spaces into statically load-balanced blocks of nonzeros. Tiling the space of nonzeros lets the generated code efficiently exploit heterogeneous compute resources such as threads, vector units, and GPUs. We implement these concepts by extending the sparse iteration theory implementation in the TACO system. The associated scheduling API can be used by performance engineers or it can be the target of an automatic scheduling system. We outline one heuristic autoscheduling system, but other systems are possible. Using the scheduling API, we show how to optimize mixed sparse-dense Tensor Algebra expressions on CPUs and GPUs. Our results show that the sparse transformations are sufficient to generate code with competitive performance to hand-optimized implementations from the literature, while generalizing to all of the Tensor Algebra.
-
a unified iteration space transformation framework for sparse and dense Tensor Algebra
arXiv: Mathematical Software, 2020Co-Authors: Ryan Senanayake, Shoaib Kamil, Fredrik Kjolstad, Changwan Hong, Saman AmarasingheAbstract:We address the problem of optimizing mixed sparse and dense Tensor Algebra in a compiler. We show that standard loop transformations, such as strip-mining, tiling, collapsing, parallelization and vectorization, can be applied to irregular loops over sparse iteration spaces. We also show how these transformations can be applied to the contiguous value arrays of sparse Tensor data structures, which we call their position space, to unlock load-balanced tiling and parallelism. We have prototyped these concepts in the open-source TACO system, where they are exposed as a scheduling API similar to the Halide domain-specific language for dense computations. Using this scheduling API, we show how to optimize mixed sparse/dense Tensor Algebra expressions, how to generate load-balanced code by scheduling sparse Tensor Algebra in position space, and how to generate sparse Tensor Algebra GPU code. Our evaluation shows that our transformations let us generate good code that is competitive with many hand-optimized implementations from the literature.
-
Tensor Algebra Compilation with Workspaces
2019 IEEE ACM International Symposium on Code Generation and Optimization (CGO), 2019Co-Authors: Fredrik Kjolstad, Shoaib Kamil, Peter Ahrens, Saman AmarasingheAbstract:This paper shows how to extend sparse Tensor Algebra compilers to introduce temporary Tensors called workspaces to avoid inefficient sparse data structures accesses. We develop an intermediate representation (IR) for Tensor operations called concrete index notation that specifies when sub-computations occur and where they are stored. We then describe the workspace transformation in this IR, how to programmatically invoke it, and how the IR is compiled to sparse code. Finally, we show how the transformation can be used to optimize sparse Tensor kernels, including sparse matrix multiplication, sparse Tensor addition, and the matricized Tensor times Khatri-Rao product (MTTKRP). Our results show that the workspace transformation brings the performance of these kernels on par with hand-optimized implementations. For example, we improve the performance of MTTKRP with dense output by up to 35%, and enable generating sparse matrix multiplication and MTTKRP with sparse output, neither of which were supported by prior Tensor Algebra compilers.
-
format abstraction for sparse Tensor Algebra compilers
Proceedings of the ACM on Programming Languages, 2018Co-Authors: Stephen Chou, Fredrik Kjolstad, Saman AmarasingheAbstract:This paper shows how to build a sparse Tensor Algebra compiler that is agnostic to Tensor formats (data layouts). We develop an interface that describes formats in terms of their capabilities and properties, and show how to build a modular code generator where new formats can be added as plugins. We then describe six implementations of the interface that compose to form the dense, CSR/CSF, COO, DIA, ELL, and HASH Tensor formats and countless variants thereof. With these implementations at hand, our code generator can generate code to compute any Tensor Algebra expression on any combination of the aforementioned formats. To demonstrate our technique, we have implemented it in the taco Tensor Algebra compiler. Our modular code generator design makes it simple to add support for new Tensor formats, and the performance of the generated code is competitive with hand-optimized implementations. Furthermore, by extending taco to support a wider range of formats specialized for different application and data characteristics, we can improve end-user application performance. For example, if input data is provided in the COO format, our technique allows computing a single matrix-vector multiplication directly with the data in COO, which is up to 3.6× faster than by first converting the data to CSR.
-
format abstraction for sparse Tensor Algebra compilers
arXiv: Mathematical Software, 2018Co-Authors: Stephen Chou, Fredrik Kjolstad, Saman AmarasingheAbstract:This paper shows how to build a sparse Tensor Algebra compiler that is agnostic to Tensor formats (data layouts). We develop an interface that describes formats in terms of their capabilities and properties, and show how to build a modular code generator where new formats can be added as plugins. We then describe six implementations of the interface that compose to form the dense, CSR/CSF, COO, DIA, ELL, and HASH Tensor formats and countless variants thereof. With these implementations at hand, our code generator can generate code to compute any Tensor Algebra expression on any combination of the aforementioned formats. To demonstrate our technique, we have implemented it in the taco Tensor Algebra compiler. Our modular code generator design makes it simple to add support for new Tensor formats, and the performance of the generated code is competitive with hand-optimized implementations. Furthermore, by extending taco to support a wider range of formats specialized for different application and data characteristics, we can improve end-user application performance. For example, if input data is provided in the COO format, our technique allows computing a single matrix-vector multiplication directly with the data in COO, which is up to 3.6$\times$ faster than by first converting the data to CSR.
Krister Åhlander - One of the best experts on this subject based on the ideXlab platform.
-
Software design for finite difference schemes based on index notation
Future Generation Computer Systems, 2003Co-Authors: Krister ÅhlanderAbstract:A formulation of finite difference schemes based on the index notation of Tensor Algebra is advocated. Finite difference operators on regular grids may be described as sparse, banded, "Tensors". Especially for higher space dimensions, it is claimed that a band Tensor formulation better corresponds to the inherent problem structure than does conventional matrix notation.Tensor Algebra is commonly expressed using index notation. The standard index notation is extended with the notion of index offsets, thereby allowing the common traversal of band Tensor diagonals.The transition from mathematical index notation to implementation is presented. It is emphasized that efficient band Tensor computations must exploit the particular problem structure, which calls for a combination of general index notation software with special-purpose band Tensor routines.
-
on software support for finite difference schemes based on index notation
International Conference on Computational Science, 2002Co-Authors: Krister Åhlander, Kurt OttoAbstract:A formulation of finite difference schemes based on the index notation of Tensor Algebra is advocated. Finite difference operators on regular grids may be described as sparse, banded, "Tensors". Especially for 3D, it is claimed that index notation better corresponds to the inherent problem structure than does conventional matrix notation. The transition from mathematical index notation to implementation is discussed. Software support for index notation that obeys the Einstein summation convention has been implemented in the C++ package Ein-Sum. The extension of EinSum to support typical data structures of finite difference schemes is outlined. A combination of general index notation software and special-purpose routines for instance for fast transforms is envisioned.
Nicholas D Sidiropoulos - One of the best experts on this subject based on the ideXlab platform.
-
Tensor Algebra and multidimensional harmonic retrieval in signal processing for mimo radar
IEEE Transactions on Signal Processing, 2010Co-Authors: Dimitri Nion, Nicholas D SidiropoulosAbstract:Detection and estimation problems in multiple-input multiple-output (MIMO) radar have recently drawn considerable interest in the signal processing community. Radar has long been a staple of signal processing, and MIMO radar presents challenges and opportunities in adapting classical radar imaging tools and developing new ones. Our aim in this article is to showcase the potential of Tensor Algebra and multidimensional harmonic retrieval (HR) in signal processing for MIMO radar. Tensor Algebra and multidimensional HR are relatively mature topics, albeit still on the fringes of signal processing research. We show they are in fact central for target localization in a variety of pertinent MIMO radar scenarios. Tensor Algebra naturally comes into play when the coherent processing interval comprises multiple pulses, or multiple transmit and receive subarrays are used (multistatic configuration). Multidimensional harmonic structure emerges for far-field uniform linear transmit/receive array configurations, also taking into account Doppler shift; and hybrid models arise in-between. This viewpoint opens the door for the application and further development of powerful algorithms and identifiability results for MIMO radar. Compared to the classical radar-imaging-based methods such as Capon or MUSIC, these Algebraic techniques yield improved performance, especially for closely spaced targets, at modest complexity.
Shoaib Kamil - One of the best experts on this subject based on the ideXlab platform.
-
a sparse iteration space transformation framework for sparse Tensor Algebra
Proceedings of the ACM on Programming Languages, 2020Co-Authors: Ryan Senanayake, Stephen Chou, Shoaib Kamil, Saman Amarasinghe, Changwan Hong, Ziheng Wang, Amalee Wilson, Fredrik KjolstadAbstract:We address the problem of optimizing sparse Tensor Algebra in a compiler and show how to define standard loop transformations---split, collapse, and reorder---on sparse iteration spaces. The key idea is to track the transformation functions that map the original iteration space to derived iteration spaces. These functions are needed by the code generator to emit code that maps coordinates between iteration spaces at runtime, since the coordinates in the sparse data structures remain in the original iteration space. We further demonstrate that derived iteration spaces can tile both the universe of coordinates and the subset of nonzero coordinates: the former is analogous to tiling dense iteration spaces, while the latter tiles sparse iteration spaces into statically load-balanced blocks of nonzeros. Tiling the space of nonzeros lets the generated code efficiently exploit heterogeneous compute resources such as threads, vector units, and GPUs. We implement these concepts by extending the sparse iteration theory implementation in the TACO system. The associated scheduling API can be used by performance engineers or it can be the target of an automatic scheduling system. We outline one heuristic autoscheduling system, but other systems are possible. Using the scheduling API, we show how to optimize mixed sparse-dense Tensor Algebra expressions on CPUs and GPUs. Our results show that the sparse transformations are sufficient to generate code with competitive performance to hand-optimized implementations from the literature, while generalizing to all of the Tensor Algebra.
-
a unified iteration space transformation framework for sparse and dense Tensor Algebra
arXiv: Mathematical Software, 2020Co-Authors: Ryan Senanayake, Shoaib Kamil, Fredrik Kjolstad, Changwan Hong, Saman AmarasingheAbstract:We address the problem of optimizing mixed sparse and dense Tensor Algebra in a compiler. We show that standard loop transformations, such as strip-mining, tiling, collapsing, parallelization and vectorization, can be applied to irregular loops over sparse iteration spaces. We also show how these transformations can be applied to the contiguous value arrays of sparse Tensor data structures, which we call their position space, to unlock load-balanced tiling and parallelism. We have prototyped these concepts in the open-source TACO system, where they are exposed as a scheduling API similar to the Halide domain-specific language for dense computations. Using this scheduling API, we show how to optimize mixed sparse/dense Tensor Algebra expressions, how to generate load-balanced code by scheduling sparse Tensor Algebra in position space, and how to generate sparse Tensor Algebra GPU code. Our evaluation shows that our transformations let us generate good code that is competitive with many hand-optimized implementations from the literature.
-
Tensor Algebra Compilation with Workspaces
2019 IEEE ACM International Symposium on Code Generation and Optimization (CGO), 2019Co-Authors: Fredrik Kjolstad, Shoaib Kamil, Peter Ahrens, Saman AmarasingheAbstract:This paper shows how to extend sparse Tensor Algebra compilers to introduce temporary Tensors called workspaces to avoid inefficient sparse data structures accesses. We develop an intermediate representation (IR) for Tensor operations called concrete index notation that specifies when sub-computations occur and where they are stored. We then describe the workspace transformation in this IR, how to programmatically invoke it, and how the IR is compiled to sparse code. Finally, we show how the transformation can be used to optimize sparse Tensor kernels, including sparse matrix multiplication, sparse Tensor addition, and the matricized Tensor times Khatri-Rao product (MTTKRP). Our results show that the workspace transformation brings the performance of these kernels on par with hand-optimized implementations. For example, we improve the performance of MTTKRP with dense output by up to 35%, and enable generating sparse matrix multiplication and MTTKRP with sparse output, neither of which were supported by prior Tensor Algebra compilers.
-
the Tensor Algebra compiler
Conference on Object-Oriented Programming Systems Languages and Applications, 2017Co-Authors: Fredrik Kjolstad, Stephen Chou, David Lugato, Shoaib Kamil, Saman AmarasingheAbstract:Tensor Algebra is a powerful tool with applications in machine learning, data analytics, engineering and the physical sciences. Tensors are often sparse and compound operations must frequently be computed in a single kernel for performance and to save memory. Programmers are left to write kernels for every operation of interest, with different mixes of dense and sparse Tensors in different formats. The combinations are infinite, which makes it impossible to manually implement and optimize them all. This paper introduces the first compiler technique to automatically generate kernels for any compound Tensor Algebra operation on dense and sparse Tensors. The technique is implemented in a C++ library called taco. Its performance is competitive with best-in-class hand-optimized kernels in popular libraries, while supporting far more Tensor operations.
-
Taco: A tool to generate Tensor Algebra kernels
2017 32nd IEEE ACM International Conference on Automated Software Engineering (ASE), 2017Co-Authors: Fredrik Kjolstad, Stephen Chou, David Lugato, Shoaib Kamil, Saman AmarasingheAbstract:Tensor Algebra is an important computational abstraction that is increasingly used in data analytics, machine learning, engineering, and the physical sciences. However, the number of Tensor expressions is unbounded, which makes it hard to develop and optimize libraries. Furthermore, the Tensors are often sparse (most components are zero), which means the code has to traverse compressed formats. To support programmers we have developed taco, a code generation tool that generates dense, sparse, and mixed kernels from Tensor Algebra expressions. This paper describes the taco web and command-line tools and discusses the benefits of a code generator over a traditional library. See also the demo video at Tensor-compiler.org/ase2017.