Theses and papers on the HDC compiler

Papers on the compiler

• A Transformational Approach which Combines Size Inference and Program Optimization [SAIG'01]
  ( Christoph Herrmann, Christian Lengauer )
• HDC: A Higher-Order Language for Divide-and-Conquer [PPL'00]
  ( Christoph Herrmann, Christian Lengauer )
• Short description: The HDC Compiler Project [CPC 2000]
  ( Christoph Herrmann, Christian Lengauer )
• Full description: A Compiler for HDC [Tech. Rep. 99]
  ( Christoph Herrmann, Christian Lengauer, Robert Günz, Jan Laitenberger, Christian Schaller )
• A description of the elimination of higher-order functions and the inlining of function calls:
  Static Parallelization of Functional Programs: Elimination of Higher-Order Functions & Optimized Inlining [Euro-Par'99]
  ( Christoph Herrmann, Christian Lengauer, Jan Laitenberger, Christian Schaller )
• A description of the size inference (has since been developed further):
  Size Inference of Nested Lists in Functional Programs [IFL'98]
  ( Christoph Herrmann , Christian Lengauer )

Ph.D. thesis

• "The Skeleton-Based Parallelization of Divide-and-Conquer Recursions" (Christoph Herrmann)
  This thesis provides a detailed discussion of the background.

Diploma theses

• "Implementierung von parallelem Divide-and-Conquer auf Gittertopologien" (Marian Musiol)
  The thesis contains a mapping and communication scheme for divide-and-conquer on mesh topologies. The efficiency results were promising but the lack of programming comfort by using C skeletons led us to the development of the HDC compiler.
• "Automatische Verifikation von Gleichheitsbeweisen in Haskell" (Robert Günz)
  The thesis is about an automatic checker of equational reasoning proofs in Haskell. The system checks the steps contained in a proof script against the rules given in a database. Backtracking is used to make sure that among all possibilities of selection of a rule, location of a rule application and instantiation a solution can be found, if there is one. Partial evaluation is used to overcome ambiguities introduced by syntactic sugar in Haskell. Transformation rules used for skeleton implementations in the HDC compiler are checked by the tool developed in this thesis.
• "Elimination von Funktionen höherer Ordnung in Haskell-Programmen" (Christian Schaller)
  Higher-order functions are a sound way of describing the nesting of skeletons, but they cause problems in program analysis and code generation. The thesis describes an elimination procedure for higher-order functions in HDC programs using monomorphization and specialization.
• "Codeoptimierung für strikte funktionale Programme" (Jan Laitenberger)
  This thesis contains a collection of optimization techniques which are required if a functional program is to be executed not by a specialized execution principle like, e.g., graph reduction, but in the context of imperative skeletons. The implementation of these techniques constitutes some phase of the HDC compiler.

Related papers in our group

• Parallelization of Divide-and-Conquer by Translation to Nested Loops [JFP 99]
  ( Christoph Herrmann , Christian Lengauer )
• The Static Parallelization of Loops and Recursions [J. Supercomputing 97]
  ( Christian Lengauer, Sergei Gorlatch, Christoph Herrmann )
• On the Space-Time Mapping of a Class of Divide-and-Conquer Recursions [PPL 96]
  ( Christoph Herrmann , Christian Lengauer )
• Notes on the Space-Time Mapping of Divide-and-Conquer Recursions [PARS'95]
  ( Christoph Herrmann , Christian Lengauer )