Publications by Doran Wilde

"Deriving Formulae to Count Solutions to Parameterized Linear Systems using Ehrhart Polynomials:
Applications to the Analysis of Nested-Loop Programs"

by Philippe Clauss, Vincent Loechner and Doran Wilde

jsc97.ps.gz (184K)

Optimizing parallel compilers need to be able to analyze nested loop programs with parametric affine loop bounds, in order to derive efficient parallel programs. The iteration spaces of nested loop programs can be modeled by polyhedra and systems of linear constraints. Using this model, important program analyses such as computing the number of flops executed by a loop, computing the number of memory locations or cache lines touched by a loop, and computing the amount of processor to processor communication needed during the execution of a loop--- all reduce to the same mathematical problem: finding the formula for number of integer solutions to a system of parameterized linear constraints, as a function of the parameters.

In this paper, we present a method for deriving a closed-form symbolic formula for the number of integer points contained in a polyhedral region in terms of size parameters. If the set of integer points to be counted lies inside a union of rational convex polytopes, then the number of points can be formulated by a special kind of polynomial called an Ehrhart pseudo-polynomial. The procedure consists of first, computing the parametric vertices of a polytope defined by a set of parametric linear constraints, and then solving for the pseudo-polynomial which gives the exact formula for the number of integer points in the polytope. An algorithm to derive this formula is presented. The method is then illustrated using many examples from the literature and in the area of parallel program optimization.

"Parameterized Polyhedra and their Vertices"

by Vincent Loechner and Doran Wilde

ijpp97.ps.gz (121K) to appear in Int'l Journal of Parallel Programming, Vol. 25, No. 6, Dec. 1997 issue

Algorithms specified for parametrically sized problems are more general purpose and more reusable than algorithms for fixed sized problems. For this reason, there is a need for representing and symbolically analyzing linearly parameterized algorithms.

An important class of parallel algorithms can be described as systems of parameterized affine recurrence equations (PARE). In this representation, linearly parameterized polyhedra are used to describe the domains of variables. This paper describes an algorithm which computes the set of parameterized vertices of a polyhedron, given its representation as a system of parameterized inequalities. This provides an important tool for the symbolic analysis of the parameterized domains used to define variables and computation domains in PARE's.

A library of operations on parameterized polyhedra based on the Polyhedral Library has been written in C and is freely distributed.

"A Library for Doing Polyhedral Operations"

by Doran K. Wilde

mathprog.ps.gz (133K) journal version

pi785.ps.gz (134K) IRISA Technical Report #785

Master's thesis

The design and implementation of a library of C-code procedures to perform operations on polyhedra is described. The library supports intersection, union, difference, simplification in context, convex hull, affine image, affine preimage, and computation of dual forms. Since not all of these functions are closed over polyhedra, the library is extended to operate on finite unions of polyhedra. The major design decisions made during the implementation of the library are discussed. The data structures used for representing finite unions of polyhedra is developed and validity rules for the representation of polyhedra are derived. And finally, the algorithms used to implement the various functions in the library are presented.

"Memory Reuse Analysis in the Polyhedral Model"

by D. Wilde and S. Rajopadhye

ppl97.ps.gz (82K) Parallel Processing Letters (to appear Oct 97)

europar96.ps.gz (46K) Europar`96 Conference version

europar96-ext.ps.gz (66K) Extended version

In the context of developing a compiler for Alpha, a functional language based on systems of affine recurrence equations (SAREs), we address the problem of transforming scheduled single-assignment code to multiple assignment code. We show how the polyhedral model allows us to statically compute the usage table of an Alpha program, and how this provides a foundation for many kinds of compile time optimizations. We illustrate this by showing a constructive method to generate memory efficient code, and indicate how it can also be used in communication optimization.

"A Regular VLSI Array for an Irregular Algorithm"

by F. de Dinechin, D. Wilde, S. Rajopadhye, R. Andonov

irreg95.ps.gz (34K) Irregular`96 Conference version

knapsack95.ps.gz (66K) Extended Version

We present an application specific, asynchronous VLSI processor array for the dynamic programming algorithm for the 0/1 knapsack problem. The array is derived systematically, using correctness-preserving transformations in two steps: the standard (dense) dynamic programming is first transformed into an irregular (sparse) functional program which has better efficiency. The program is then implemented on a modular VLSI architecture with nearest neighbor connections and constant memory in each processor. To do this, we prove that buffer sizes are bounded, and then show how a number of processors can be configured so that the buffers are pooled. This yields a linear array of identical asynchronous processors, each with a simple comparator, multiplexor and a pair of fixed size fifos.

"A Shift Register Based Systolic Array for the General Knapsack Problem"

by Rumen Andonov, Sanjay Rajopadhye and Doran Wilde

ppl95.ps.gz (51K) Parallel Processing Letters

We present a shift register based systolic array for a class of recurrences with dynamic dependences called knapsack problem recurrences. All previous arrays or parallel implementations led to either low efficiency or to complicated control. To the best of our knowledge,the proposed design is the first realistic pure systolic and optimal array of a pseudo-polynomial, NP-complete problem. The key feature of the array is that it requires almost no control circuitry.

"From Alpha to Imperative Code: A Transformational Compiler for an Array Based Functional Language"

by Doran Wilde

wilde95.ps.gz (285K) Ph.D. Dissertation, Oregon State University

Practical parallel programming demands that the details of distributing data to processors and interprocessor communication be managed by the compiler. These tasks quickly become too difficult for a programmer to do by hand for all but the simplest parallel programs. Yet, many parallel languages still require the programmer to manage much of the the parallelism.

I discuss the synthesis of parallel imperative code from algorithms written in a functional language called Alpha. Alpha is based on systems of affine recurrence equations and was designed to specify algorithms for regular array architectures. Being a functional language, Alpha implicitly supports the expression of both concurrency and communication. Thus, the programmer is freed from having to explicitly manage the parallelism.

Using the information derived from static analysis, Alpha can be transformed into a form suitable for generating imperative parallel code through a series of provably correct program transformations. The kinds of analysis needed to generate efficient code for array-based functional programs are a generalization of dependency analysis, usage analysis, and scheduling techniques used in systolic array synthesis.

"The Naive Execution of Affine Recurrence Equations"

by Patrice Quinton, Sanjay Rajopadhye, Doran Wilde

asap95.ps.gz (67K) ASAP'95, Jul, 1995, Strasbourg, France

In recognition of the fundamental relation between regular arrays and systems of affine recurrence equations, the Alpha language was developed as the basis of a computer aided design methodology for regular array architectures. Alpha is used to initially specify algorithms at a very high algorithmic level. Regular array architectures can then be derived from the algorithmic specification using a transformational approach supported by the Alpha environment. This design methodology guarantees the final design to be correct by construction, assuming the initial algorithm was correct.

In this paper, we address the problem of validating an initial specification. We demonstrate a translation methodology which compiles Alpha into the imperative sequential language C. The C-code may then be compiled and executed to test the specification. We show how an Alpha program can be naively implemented by viewing it as a set of monolithic arrays and their filling functions, implemented using applicative caching. This is the approach which is used by the translator. We discuss two problems that had to be solved before implementing the translator. The first is how to allocate 1-dimensional storage for a polyhedron, and the second is how to scan a polyhedron with nested loops.

"Deriving Imperative Code from Functional Programs"

by Patrice Quinton, Sanjay Rajopadhye, Doran Wilde

fpca95.ps.gz (55K) FPCA`95, June 1995, La Jolla, California

Alpha is a data parallel functional language which has the capability of specifying algorithms at a very high level. Our ultimate objective is to generate efficient parallel imperative code from an Alpha program. In this paper, we discuss the related problem of generating efficient single processor imperative code. Analysis techniques that were developed for the synthesis of systolic arrays are extended and adapted for the compilation of functional programming languages. We also demonstrate how a transformational methodology can be used as a compilation engine to transform an Alpha program to a sequential form. C--code is then generated using a straightforward pretty printer from the sequential form Alpha program. The C-code may then be compiled to efficiently execute the program.

"On Deriving Data Parallel Code from a Functional Program"

by Patrice Quinton, Sanjay Rajopadhye, Doran Wilde

ipps95.ps.gz (49K) IPPS, April 1995, Santa Barbara,CA

We discuss a translation methodology for transforming a high level Algorithmic specification written in Alpha to an imperative data parallel language. We informally introduce the Alpha language with the aid of an example and explain how it is adapted for doing static analysis and transformation. An Alpha program can be naively compiled using applicative caching. Our compilation method makes incremental transformations on the abstract syntax tree of an Alpha program in order to make efficiency and performance improvements over the naive code and optimize it for a given architecture. The compilation steps described include scheduling, alignment, partitioning, allocation, loop nest generation, and code generation and they are illustrated with an example.

"Regular Array Synthesis Using Alpha"

by Doran Wilde and Oumarou Sie

asap94.ps.gz (61K) ASAP`94, June, 1994, San Francisco

We report our current research in a computer assisted methodology for synthesizing regular array processors using the Alpha language and design environment. The design process starts from an algorithmic level description of the function and finishes with a netlist of an array processor which performs the specified function. To illustrate the proposed approach, we present the design of an array processor to do polynomial division.

"The Alpha Compiler and Uncompiler, Technical Report"

by Doran Wilde and Andrew Snoddy

nt9401.ps.gz (76K) IRISA Technical Report 1994-#1

The Alpha parser translates an Alpha source program into an abstract syntax tree (AST). The Alpha unparser, or pretty printer, does the opposite translation from an Alpha AST back to a source program. These two translators are an integral part of the Alpha environment. This report is both a user's guide and technical documentation for these two programs.

"Allocating Memory Arrays for Polyhedra"

by Doran Wilde and Sanjay Rajopadhye

pi749.ps.gz (89K) IRISA Technical Report #749

We have been investigating problems which arise in compiling single assignment languages (in which memory is not explicitly allocated) into parallel code. Like standard parallelizing compilers, different index space transformations are performed on variables declared over convex polyhedral regions. Polyhedra can be transformed in such a way as to reduce the volume of the bounding box which we use to reduce the amount of memory allocated to a variable. Allocation of memory to variables which are defined over finite convex polyhedral regions requires a tradeoff in the complexity of the memory addressing function versus the amount of memory used. We present a tradeoff in which the memory address function is limited to an affine function of the indices (thus memory is allocated to a rectangular parallelepiped region). Given this constraint, we seek a unimodular transformation which minimizes the volume of the bounding box of the polyhedron. This is a non-linear programming problem. We present a method in which the volume of the bounding box is minimized one dimension at a time by a succession of skewing transformations. Each one of these is a linear programming problem.

"An Inductive Constructive Method for Computation of the Face Lattice of a Polyhedron"

by Doran Wilde

pi786.ps.gz (82K) IRISA Technical Report #786

This article describes two algorithms to generate the face lattice of a polyhedron. A procedure by Motzkin which computes the dual of a polyhedron is presented and then extended to compute the entire face lattice of a polyhedron. This new algorithm recursively generates the lattice. Another non-recursive algorithm to construct lattices which was invented by Seidel is also presented.

"The Alpha Language"

by Doran Wilde

pi827.ps.gz (81K) IRISA Technical Report #827

This report is a formal description of the Alpha language, as it is currently implemented. Alpha is a strongly typed, functional language which embodies the formalism of systems of affine recurrence equations. In this report, Alpha language constructs are described, and denotational and type semantics are given. The theorems which are the basis for doing transformations on an Alpha program are stated. And finally, the syntax and semantics of Alpha are given.

"Using Static Analysis to Derive Imperative Code from Alpha"

by Patrice Quinton, Sanjay Rajopadhye, Doran Wilde

pi828.ps.gz (79K) IRISA Technical Report #828

In this article, we demonstrate a translation methodology which transforms a high level algorithmic specification written in the Alpha language to an imperative data parallel language. Alpha is a functional language which was designed to facilitate the kinds of static analyses needed for doing regular array synthesis. We show that the same methods which are used for solving regular array synthesis problems can be applied to the compilation of Alpha as a functional language.

We informally introduce the Alpha language with the aid of examples and explain how it is adapted to doing static analysis and transformation. We first show how an Alpha program can be naively implemented by viewing it as a set of monolithic arrays and their filling functions, implemented using applicative caching. We then show how static analysis can be used to improve the efficiency of this naive implementation by orders of magnitude. We present a compilation method which makes incremental transformations on the abstract syntax tree of an Alpha program in order to make performance improvements and optimize it for a given architecture. The compilation steps described include scheduling, alignment, partitioning, allocation, loop nest generation, and code generation and they are illustrated with a running example. We discuss some of the static analysis issues which come up at each of these steps and briefly describe what static analysis tools are used.

"Loop Nest Synthesis using the Polyhedral Library"

by Herve Le Verge, Vincent Van Dongen, Doran Wilde

pi830.ps.gz (55K) IRISA Technical Report #830 (English)

Presented at RENPAR`6 (French).

A new method to synthesis loop nests given a polyhedral domain, the context domain, and the loop nesting order is described. The method is based on functions in the IRISA polyhedral library.