Publications - Henrik Barthels

Peer Reviewed Conference Publications

  1. The Generalized Matrix Chain Algorithm
    Proceedings of the International Symposium on Code Generation and Optimization, February 2018.
    @inproceedings{Barthels2018:130,
        author  = "Henrik Barthels and Marcin Copik and Paolo Bientinesi",
        title   = "The Generalized Matrix Chain Algorithm",
        year    = 2018,
        address = "Vienna, Austria",
        month   = feb
    }
    In this paper, we present a generalized version of the matrix chain algorithm to generate efficient code for linear algebra problems, a task for which human experts often invest days or even weeks of works. The standard matrix chain problem consists in finding the parenthesization of a matrix product $M := A_1 A_2 \cdots A_n$​ that minimizes the number of scalar operations. In practical applications, however, one frequently encounters more complicated expressions, involving transposition, inversion, and matrix properties. Indeed, the computation of such expressions relies on a set of computational kernels that offer functionality well beyond the simple matrix product. The challenge then shifts from finding an optimal parenthesization to finding an optimal mapping of the input expression to the available kernels. Furthermore, it is often the case that a solution based on the minimization of scalar operations does not result in the optimal solution in terms of execution time. In our experiments, the generated code outperforms other libraries and languages on average by a factor of about 5. The motivation for this work comes from the fact that---despite great advances in the development of compilers---the task of mapping linear algebra problems to optimized kernels is still to be done manually. In order to relieve the user from this complex task, new techniques for the compilation of linear algebra expressions have to be developed.
    abstractbibtexhide
  2. Efficient Pattern Matching in Python
    Manuel Krebber, Henrik Barthels and Paolo Bientinesi
    Proceedings of the 7th Workshop on Python for High-Performance and Scientific Computing, November 2017.
    In conjunction with SC17: The International Conference for High Performance Computing, Networking, Storage and Analysis.
    @inproceedings{Krebber2017:404,
        author    = "{Manuel } Krebber and Henrik Barthels and Paolo Bientinesi",
        title     = "Efficient Pattern Matching in Python",
        booktitle = "Proceedings of the 7th Workshop on Python for High-Performance and Scientific Computing",
        year      = 2017,
        month     = nov,
        note      = "In conjunction with SC17: The International Conference for High Performance Computing, Networking, Storage and Analysis",
        url       = "https://arxiv.org/pdf/1710.00077.pdf"
    }
    Pattern matching is a powerful tool for symbolic computations. Applications include term rewriting systems, as well as the manipulation of symbolic expressions, abstract syntax trees, and XML and JSON data. It also allows for an intuitive description of algorithms in the form of rewrite rules. We present the open source Python module MatchPy, which offers functionality and expressiveness similar to the pattern matching in Mathematica. In particular, it includes syntactic pattern matching, as well as matching for commutative and/or associative functions, sequence variables, and matching with constraints. MatchPy uses new and improved algorithms to efficiently find matches for large pattern sets by exploiting similarities between patterns. The performance of MatchPy is investigated on several real-world problems.
    abstractwebPDFbibtexhide
  3. Linnea: Compiling Linear Algebra Expressions to High-Performance Code
    Proceedings of the 8th International Workshop on Parallel Symbolic Computation, July 2017.
    @inproceedings{Barthels2017:254,
        author    = "Henrik Barthels and Paolo Bientinesi",
        title     = "Linnea: Compiling Linear Algebra Expressions to High-Performance Code",
        booktitle = "Proceedings of the 8th International Workshop on Parallel Symbolic Computation",
        year      = 2017,
        month     = jul,
        url       = "http://hpac.rwth-aachen.de/~barthels/publications/PASCO_2017.pdf"
    }
    Linear algebra expressions appear in fields as diverse as computational biology, signal processing, communication technology, finite element methods, and control theory. Libraries such as BLAS and LAPACK provide highly optimized building blocks for just about any linear algebra computation; thus, a linear algebra expression can be evaluated efficiently by breaking it down into those building blocks. However, this is a challenging problem, requiring knowledge in high-performance computing, compilers, and numerical linear algebra. In this paper we give an overview of existing solutions, and introduce Linnea, a compiler that solves this problem. As shown through a set of test cases, Linnea’s results are comparable with those obtained by human experts.
    abstractwebPDFbibtexhide
  4. MatchPy: A Pattern Matching Library
    Manuel Krebber, Henrik Barthels and Paolo Bientinesi
    Proceedings of the 15th Python in Science Conference, July 2017.
    @inproceedings{Krebber2017:550,
        author    = "{Manuel } Krebber and Henrik Barthels and Paolo Bientinesi",
        title     = "MatchPy: A Pattern Matching Library",
        booktitle = "Proceedings of the 15th Python in Science Conference",
        year      = 2017,
        month     = jul,
        url       = "http://conference.scipy.org/proceedings/scipy2017/pdfs/manuel_krebber.pdf"
    }
    Pattern matching is a powerful tool for symbolic computations, based on the well-defined theory of term rewriting systems. Application domains include algebraic expressions, abstract syntax trees, and XML and JSON data. Unfortunately, no lightweight implementation of pattern matching as general and flexible as Mathematica exists for Python Mathics,MacroPy,patterns,PyPatt. Therefore, we created the open source module MatchPy which offers similar pattern matching functionality in Python using a novel algorithm which finds matches for large pattern sets more efficiently by exploiting similarities between patterns.
    abstractwebPDFbibtexhide
  5. A Compiler for Linear Algebra Operations
    SPLASH '16 Companion, ACM, October 2016.
    Student Research Competition.
    @inproceedings{Barthels2016:280,
        author    = "Henrik Barthels",
        title     = "A Compiler for Linear Algebra Operations",
        booktitle = "SPLASH '16 Companion",
        year      = 2016,
        month     = oct,
        publisher = "ACM",
        note      = "Student Research Competition"
    }
    In this paper we present a compiler that translates arithmetic expressions containing matrices to efficient sequences of calls to basic linear algebra kernels.
    abstractwebbibtexhide
  6. Juggrnaut – An Abstract JVM
    Jonathan Heinen, Henrik Barthels and Christina Jansen
    International Conference on Formal Verification of Object-Oriented Software, pp. 142-159, 2011.
    @inproceedings{Heinen2011:370,
        author       = "Jonathan Heinen and Henrik Barthels and Christina Jansen",
        title        = "Juggrnaut – An Abstract JVM",
        booktitle    = "International Conference on Formal Verification of Object-Oriented Software",
        year         = 2011,
        pages        = "142--159",
        organization = "Springer",
        url          = "http://hpac.rwth-aachen.de/~barthels/publications/juggrnaut.pdf"
    }
    We introduce a new kind of hypergraphs and hyperedge replacement grammars, where nodes are associated types. We use them to adapt the abstraction framework Juggrnaut presented by us in [7, 8] – for the verification of Java Bytecode programs. The framework is extended to handle additional concepts needed for the analysis of Java Bytecode like null pointers and method stacks as well as local and static variables. We define the abstract transition rules for a significant subset of opcodes and show how to compute the abstract state space. Finally we complete the paper with some experimental results.
    abstractPDFbibtexhide

Thesis

  1. Systematic Generation of Algorithms for Iterative Methods
    Master's Thesis, RWTH Aachen, March 2015.
    @mastersthesis{Barthels2015:240,
        author = "Henrik Barthels",
        title  = "Systematic Generation of Algorithms for Iterative Methods",
        school = "RWTH Aachen",
        year   = 2015,
        type   = "Master's Thesis",
        month  = mar,
        url    = "https://arxiv.org/pdf/1703.00279"
    }
    webPDFbibtexhide

Others

  1. A Compiler for Linear Algebra Operations
    Poster, 2 November 2016.
    ACM Student Research Competition at SPLASH 2016.
    @misc{Barthels2016:948,
        author = "Henrik Barthels",
        title  = "A Compiler for Linear Algebra Operations",
        month  = nov,
        year   = 2016,
        note   = "ACM Student Research Competition at SPLASH 2016",
        type   = "Poster",
        url    = "http://hpac.rwth-aachen.de/~barthels/publications/ACM_SRC_2016_poster.pdf"
    }
    PDFbibtexhide
  2. The Matrix Chain Algorithm to Compile Linear Algebra Expressions
    Proceedings of the DSLDI 2016, Extended abstract, 31 October 2016.
    @misc{Barthels2016:600,
        author      = "Henrik Barthels and Paolo Bientinesi",
        title       = "The Matrix Chain Algorithm to Compile Linear Algebra Expressions",
        month       = oct,
        year        = 2016,
        type        = "Extended abstract",
        institution = "RWTH Aachen",
        url         = "https://arxiv.org/pdf/1611.05660"
    }
    webPDFbibtexhide
  3. Automata-Based Detection of Hypergraph Embeddings
    Bachelor's Thesis, RWTH Aachen, September 2011.
    @misc{Barthels2011:804,
        author = "Henrik Barthels",
        title  = "Automata-Based Detection of Hypergraph Embeddings",
        month  = sep,
        year   = 2011,
        type   = "Bachelor's Thesis, RWTH Aachen",
        url    = "http://hpac.rwth-aachen.de/~barthels/publications/bachelor_thesis.pdf"
    }
    The verification of programs using pointers and dynamic data structures requires to deal with potentially infinite state spaces. Because of that, it is reasonable to use abstraction techniques capable of dealing with those potentially infinite structures. The Juggrnaut framework applies hyperedge replacement grammars to dynamically abstract and concretize parts of a heap. Abstraction is done by the backwards application of grammar rules, which is related to subgraph isomorphism and therefore NP-complete. In this thesis, after giving a formal definition to hypergraphs, hyperedge replacement and heap representation, an automata model is introduced which is able to detect embeddings of grammar rules with certain properties efficiently. We provide an algorithm to construct an automaton that is able to detect a given set of embeddings of grammar rules. Finally, proofs of the NP-completeness of subgraph isomorphism on hypergraphs and embedding detection in general are presented.
    abstractPDFbibtexhide