The Experts below are selected from a list of 24081 Experts worldwide ranked by ideXlab platform
Markus Puschel - One of the best experts on this subject based on the ideXlab platform.
-
Program generation for small scale linear algebra applications
Symposium on Code Generation and Optimization, 2018Co-Authors: Daniele G Spampinato, Diego Fabregattraver, Paolo Bientinesi, Markus PuschelAbstract:We present SLinGen, a Program generation system for linear algebra. The input to SLinGen is an application expressed mathematically in a linear-algebra-inspired language (LA) that we define. LA provides basic scalar/vector/matrix additions/multiplications and higher level operations including linear systems solvers, Cholesky and LU factorizations. The output of SLinGen is performance-optimized single-source C code, optionally vectorized with intrinsics. The target of SLinGen are small-scale computations on fixed-size operands, for which a straightforward implementation using optimized libraries (e.g., BLAS or LAPACK) is known to yield suboptimal performance (besides increasing code size and introducing dependencies), but which are crucial in control, signal processing, computer vision, and other domains. Internally, SLinGen uses synthesis and DSL-based techniques to optimize at a high level of abstraction. We benchmark our Program Generator on three prototypical applications: the Kalman filter, Gaussian process regression, and an L1-analysis convex solver, as well as basic routines including Cholesky factorization and solvers for the continuous-time Lyapunov and Sylvester equations. The results show significant speed-ups compared to straightforward C with Intel icc and clang with a polyhedral optimizer, as well as library-based and template-based implementations.
-
Computer Generation of Platform-Adapted Physical Layer Software
2018Co-Authors: Yevgen Voroneko, Markus Puschel, Volodymyr Arbatov, Christian R. Berger, Ronghui Peng, Franz FranchettiAbstract:In this paper, we describe a Program Generator for physical layer (PHY) baseband processing in a software-defined radio implementation. The input of the Generator is a very highlevel platform-independent description of the transmitter and receiver PHY functionality, represented in a domain-specific declarative language called Operator Language (OL). The output is performance-optimized and platform-tuned C code with single-instruction multiple-data (SIMD) vector intrinsics and threading directives. The Generator performs these optimizations by restructuring the algorithms for the individual components at the OL level before mapping to code. This way known compiler limitation are overcome. Further platform tuning is achieved by a feedback-directed search that determines the fastest solution among a space of candidates. We demonstrate the approach and the excellent performance of the generated code on on the IEEE 802.11a (WiFi) receiver and transmitter for all transmission modes.
-
Computer Generation of Efficient Software Viterbi Decoders
2018Co-Authors: Frederic De Mesmay, Franz Franchetti, Srinivas Chellappa, Markus PuschelAbstract:This paper presents a Program Generator for fast software Viterbi decoders for arbitrary convolutional codes. The input to the Generator is a specification of the code and a single-instruction multiple-data (SIMD) vector length. The output is an optimized C implementation of the decoder that uses explicit Intel SSE vector instructions. At the heart of the Generator is a small domain-specific language called VL to express the structure of the forward pass. Vectorization is done by rewriting VL expressions, which a compiler then translates into actual code in addition to performing further optimizations specific to the vector instruction set. Benchmarks show that the generated decoders match the performance of available expert hand-tuned implementations, while spanning the entire space of convolutional codes. An online interface to the Generator is provided at www.spiral.net.
-
automatic simd vectorization of fast fourier transforms for the larrabee and avx instruction sets
International Conference on Supercomputing, 2011Co-Authors: Daniel S Mcfarlin, Franz Franchetti, Volodymyr Arbatov, Markus PuschelAbstract:The well-known shift to parallelism in CPUs is often associated with multicores. However another trend is equally salient: the increasing parallelism in per-core single-instruction multiple-date (SIMD) vector units. Intel's SSE and IBM's VMX (compatible to AltiVec) both offer 4-way (single precision) floating point, but the recent Intel instruction sets AVX and Larrabee (LRB) offer 8-way and 16-way, respectively. Compilation and optimization for vector extensions is hard, and often the achievable speed-up by using vectorizing compilers is small compared to hand-optimization using intrinsic function interfaces. Unfortunately, the complexity of these intrinsics interfaces increases considerably with the vector length, making hand-optimization a nightmare. In this paper, we present a peephole-based vectorization system that takes as input the vector instruction semantics and outputs a library of basic data reorganization blocks such as small transpositions and perfect shuffles that are needed in a variety of high performance computing applications. We evaluate the system by generating the blocks needed by the Program Generator Spiral for vectorized fast Fourier transforms (FFTs). With the generated FFTs we achieve a vectorization speed-up of 5.5--6.5 for 8-way AVX and 10--12.5 for 16-way LRB. For the latter instruction counts are used since no timing information is available. The combination of the proposed system and Spiral thus automates the production of high performance FFTs for current and future vector architectures.
-
discrete fourier transform on multicore
IEEE Signal Processing Magazine, 2009Co-Authors: Franz Franchetti, Markus Puschel, Yevgen Voronenko, Srinivas Chellappa, Jose M F MouraAbstract:This article gives an overview on the techniques needed to implement the discrete Fourier transform (DFT) efficiently on current multicore systems. The focus is on Intel-compatible multicores, but we also discuss the IBM Cell and, briefly, graphics processing units (GPUs). The performance optimization is broken down into three key challenges: parallelization, vectorization, and memory hierarchy optimization. In each case, we use the Kronecker product formalism to formally derive the necessary algorithmic transformations based on a few hardware parameters. Further code-level optimizations are discussed. The rigorous nature of this framework enables the complete automation of the implementation task as shown by the Program Generator Spiral. Finally, we show and analyze DFT benchmarks of the fastest libraries available for the considered platforms.
Gil Shurek - One of the best experts on this subject based on the ideXlab platform.
-
test Program generation for functional verification of powerpc processors in ibm
Design Automation Conference, 1995Co-Authors: Aharon Aharon, Dave Goodman, Moshe Levinger, Yossi Lichtenstein, Yossi Malka, Charlotte Metzger, Moshe Molcho, Gil ShurekAbstract:A new methodology and test Program Generator have been used for the functional verification of six IBM PowerPC processors. The Generator contains a formal model of the PowerPC architecture and a heuristic data-base of testing expertise. It has been used on daily basis for two years by about a hundred designers and testing engineers in four IBM sites. The new methodology reduced significantly the functional verification period and time to market of the PowerPC processors. Despite the complexity of the PowerPC architecture, the three processors verified so far had fully functional first silicon.
Franz Franchetti - One of the best experts on this subject based on the ideXlab platform.
-
Computer Generation of Platform-Adapted Physical Layer Software
2018Co-Authors: Yevgen Voroneko, Markus Puschel, Volodymyr Arbatov, Christian R. Berger, Ronghui Peng, Franz FranchettiAbstract:In this paper, we describe a Program Generator for physical layer (PHY) baseband processing in a software-defined radio implementation. The input of the Generator is a very highlevel platform-independent description of the transmitter and receiver PHY functionality, represented in a domain-specific declarative language called Operator Language (OL). The output is performance-optimized and platform-tuned C code with single-instruction multiple-data (SIMD) vector intrinsics and threading directives. The Generator performs these optimizations by restructuring the algorithms for the individual components at the OL level before mapping to code. This way known compiler limitation are overcome. Further platform tuning is achieved by a feedback-directed search that determines the fastest solution among a space of candidates. We demonstrate the approach and the excellent performance of the generated code on on the IEEE 802.11a (WiFi) receiver and transmitter for all transmission modes.
-
Computer Generation of Efficient Software Viterbi Decoders
2018Co-Authors: Frederic De Mesmay, Franz Franchetti, Srinivas Chellappa, Markus PuschelAbstract:This paper presents a Program Generator for fast software Viterbi decoders for arbitrary convolutional codes. The input to the Generator is a specification of the code and a single-instruction multiple-data (SIMD) vector length. The output is an optimized C implementation of the decoder that uses explicit Intel SSE vector instructions. At the heart of the Generator is a small domain-specific language called VL to express the structure of the forward pass. Vectorization is done by rewriting VL expressions, which a compiler then translates into actual code in addition to performing further optimizations specific to the vector instruction set. Benchmarks show that the generated decoders match the performance of available expert hand-tuned implementations, while spanning the entire space of convolutional codes. An online interface to the Generator is provided at www.spiral.net.
-
automatic simd vectorization of fast fourier transforms for the larrabee and avx instruction sets
International Conference on Supercomputing, 2011Co-Authors: Daniel S Mcfarlin, Franz Franchetti, Volodymyr Arbatov, Markus PuschelAbstract:The well-known shift to parallelism in CPUs is often associated with multicores. However another trend is equally salient: the increasing parallelism in per-core single-instruction multiple-date (SIMD) vector units. Intel's SSE and IBM's VMX (compatible to AltiVec) both offer 4-way (single precision) floating point, but the recent Intel instruction sets AVX and Larrabee (LRB) offer 8-way and 16-way, respectively. Compilation and optimization for vector extensions is hard, and often the achievable speed-up by using vectorizing compilers is small compared to hand-optimization using intrinsic function interfaces. Unfortunately, the complexity of these intrinsics interfaces increases considerably with the vector length, making hand-optimization a nightmare. In this paper, we present a peephole-based vectorization system that takes as input the vector instruction semantics and outputs a library of basic data reorganization blocks such as small transpositions and perfect shuffles that are needed in a variety of high performance computing applications. We evaluate the system by generating the blocks needed by the Program Generator Spiral for vectorized fast Fourier transforms (FFTs). With the generated FFTs we achieve a vectorization speed-up of 5.5--6.5 for 8-way AVX and 10--12.5 for 16-way LRB. For the latter instruction counts are used since no timing information is available. The combination of the proposed system and Spiral thus automates the production of high performance FFTs for current and future vector architectures.
-
discrete fourier transform on multicore
IEEE Signal Processing Magazine, 2009Co-Authors: Franz Franchetti, Markus Puschel, Yevgen Voronenko, Srinivas Chellappa, Jose M F MouraAbstract:This article gives an overview on the techniques needed to implement the discrete Fourier transform (DFT) efficiently on current multicore systems. The focus is on Intel-compatible multicores, but we also discuss the IBM Cell and, briefly, graphics processing units (GPUs). The performance optimization is broken down into three key challenges: parallelization, vectorization, and memory hierarchy optimization. In each case, we use the Kronecker product formalism to formally derive the necessary algorithmic transformations based on a few hardware parameters. Further code-level optimizations are discussed. The rigorous nature of this framework enables the complete automation of the implementation task as shown by the Program Generator Spiral. Finally, we show and analyze DFT benchmarks of the fastest libraries available for the considered platforms.
-
fft Program generation for shared memory smp and multicore
Conference on High Performance Computing (Supercomputing), 2006Co-Authors: Franz Franchetti, Yevgen Voronenko, Markus PuschelAbstract:The chip maker?s response to the approaching end of CPU frequency scaling are multicore systems, which offer the same Programming paradigm as traditional shared memory platforms but have different performance characteristics. This situation considerably increases the burden on library developers and strengthens the case for automatic performance tuning frameworks like Spiral, a Program Generator and optimizer for linear transforms such as the discrete Fourier transform (DFT). We present a shared memory extension of Spiral. The extension within Spiral consists of a rewriting system that manipulates the structure of transform algorithms to achieve load balancing and avoids false sharing, and of a backend to generate multithreaded code. Application to the DFT produces a novel class of algorithms suitable for multicore systems as validated by experimental results: we demonstrate a parallelization speed-up already for sizes that fit into L1 cache and compare favorably to other DFT libraries across all small and midsize DFTs and considered platforms.
Tiark Rompf - One of the best experts on this subject based on the ideXlab platform.
-
building efficient query engines in a high level language
Very Large Data Bases, 2014Co-Authors: Yannis Klonatos, Christoph Koch, Tiark Rompf, Hassan ChafiAbstract:In this paper we advocate that it is time for a radical rethinking of database systems design. Developers should be able to leverage high-level Programming languages without having to pay a price in efficiency. To realize our vision of abstraction without regret, we present LegoBase, a query engine written in the high-level Programming language Scala. The key technique to regain efficiency is to apply generative Programming: the Scala code that constitutes the query engine, despite its high-level appearance, is actually a Program Generator that emits specialized, low-level C code. We show how the combination of high-level and generative Programming allows to easily implement a wide spectrum of optimizations that are difficult to achieve with existing low-level query compilers, and how it can continuously optimize the query engine. We evaluate our approach with the TPC-H benchmark and show that: (a) with all optimizations enabled, our architecture significantly outperforms a commercial in-memory database system as well as an existing query compiler, (b) these performance improvements require Programming just a few hundred lines of high-level code instead of complicated low-level code that is required by existing query compilers and, finally, that (c) the compilation overhead is low compared to the overall execution time, thus making our approach usable in practice for efficiently compiling query engines.
-
lightweight modular staging a pragmatic approach to runtime code generation and compiled dsls
Communications of The ACM, 2012Co-Authors: Tiark Rompf, Martin OderskyAbstract:Good software engineering practice demands generalization and abstraction, whereas high performance demands specialization and concretization. These goals are at odds, and compilers can only rarely translate expressive high-level Programs to modern hardware platforms in a way that makes best use of the available resources. Generative Programming is a promising alternative to fully automatic translation. Instead of writing down the target Program directly, developers write a Program Generator, which produces the target Program as its output. The Generator can be written in a high-level, generic style and can still produce efficient, specialized target Programs. In practice, however, developing high-quality Program Generators requires a very large effort that is often hard to amortize. We present lightweight modular staging (LMS), a generative Programming approach that lowers this effort significantly. LMS seamlessly combines Program Generator logic with the generated code in a single Program, using only types to distinguish the two stages of execution. Through extensive use of component technology, LMS makes a reusable and extensible compiler framework available at the library level, allowing Programmers to tightly integrate domain-specific abstractions and optimizations into the generation process, with common generic optimizations provided by the framework. LMS is well suited to develop embedded domain-specific languages (DSLs) and has been used to develop powerful performance-oriented DSLs for demanding domains such as machine learning, with code generation for heterogeneous platforms including GPUs. LMS has also been used to generate SQL for embedded database queries and JavaScript for web applications.
-
lightweight modular staging and embedded compilers abstraction without regret for high level high performance Programming
2012Co-Authors: Tiark RompfAbstract:Abstract Programs expressed in a high-level Programming language need to be translated to a low-levelmachine dialect for execution. This translation is usually accomplished by a compiler, whichis able to translate any legal Program to equivalent low-level code. But for individual sourcePrograms, automatic translation does not always deliver good results: Software engineeringpractice demands generalization and abstraction, whereas high performance demands spe-cialization and concretization. These goals are at odds, and compilers can only rarely translateexpressive high-level Programs to modern hardware platforms in a way that makes best use ofthe available resources.Explicit Program generation is a promising alternative to fully automatic translation.Instead of writing down the Program and relying on a compiler for translation, developerswrite a Program Generator, which produces a specialized, efficient, low-level Program as itsoutput. However, developing high-quality Program Generators requires a very large effort thatis often hard to amortize.In this thesis, we propose a hybrid design: Integrate compilers into Programs so thatPrograms can take control of the translation process, but rely on libraries of common compilerfunctionality for help.We present
Moshe Levinger - One of the best experts on this subject based on the ideXlab platform.
-
functional verification methodology for microprocessors using the genesys test Program Generator application to the x86 microprocessors family
Design Automation and Test in Europe, 1999Co-Authors: Laurent Fournier, Yaron Arbetman, Moshe LevingerAbstract:Even though the importance of microprocessor design verification is widely acknowledged, no rigorous methodology is being commonly followed for its realization. This paper attempts to delineate such a methodology, and shows how it is promoted by Genesys, an automatic pseudo-random test-Program Generator. The methodology relies on a verification plan which induces smart sets of tests that carry out the verification tasks. The paper reports on an application of this methodology, using Genesys, to verify an x86 design and describes, in particular, how this methodology could have helped to avoid known escape bugs, such as the recent two infamous Pentium Floating Point bugs.
-
test Program generation for functional verification of powerpc processors in ibm
Design Automation Conference, 1995Co-Authors: Aharon Aharon, Dave Goodman, Moshe Levinger, Yossi Lichtenstein, Yossi Malka, Charlotte Metzger, Moshe Molcho, Gil ShurekAbstract:A new methodology and test Program Generator have been used for the functional verification of six IBM PowerPC processors. The Generator contains a formal model of the PowerPC architecture and a heuristic data-base of testing expertise. It has been used on daily basis for two years by about a hundred designers and testing engineers in four IBM sites. The new methodology reduced significantly the functional verification period and time to market of the PowerPC processors. Despite the complexity of the PowerPC architecture, the three processors verified so far had fully functional first silicon.