The Reduceron

Matthew Naylor, Colin Runciman and Jason Reich

Sponsored by



Engineering and Physical
Sciences Research Council, UK

FPGA kit provided by



Introduction

From October 2008 to March 2010, we worked on the EPSRC-funded project The Reduceron: High-Level Symbolic Computing on FPGA. This web-page makes available the results of the project.

Published material

The design, implementation, and evaluation of the Reduceron are described in detail in our paper

The Reduceron reconfigured and re-evaluated
(to appear in the Journal of Functional Programming)

This is an extended version of a paper accepted to ICFP'10. Other relevent published material includes our paper Supercompilation and the Reduceron (accepted to META'10) and, from the beginning of the project, our talk proposal (accepted to HFL'09).

The benchmark programs used in our experiments are available here.

Presentations

  • Colin presented on 27 September 2010 about the Reduceron at ICFP'10, Baltimore.
  • Colin presented on 21 July 2010 about guaranteed primitive redex speculation at the Nottingham FP group away day; we hope to have more on this topic soon.
  • Matthew presented on 26 November 2009 about the Reduceron at FitA, Microsoft Cambridge.
  • Jason presented on 3 July 2010 about Supercompilation and the Reduceron at Meta'10, Russia.
  • Matthew also presented at Birmingham University (invited talk), HFL'09, and YDS'08 (invited talk).

Implementation

The implementation of the Reduceron comprises three pieces.

York Lava The Haskell library used to describe the Reduceron
F-lite A compiler for the language that runs on the Reduceron
Reduceron The reduction machine itself

F-lite and York Lava are discussed in memos 9 and 23 respectively. More recent versions of these packages may be available on hackage.

Memos

The following memos record our work-in-progress thoughts and ideas. In general, they are drafty in nature: some are sketchy, some are incomplete, and some are subsumed by later memos and published papers.

1 Widening function bodies
2 Widening function bodies revisited
3 Head reduction, arity raising and shared subexpressions
4 Chunky lists
5 Recursive nested-case function bodies and in-lining
6 Case factorisation and special treatment of constructors
7 Memory layout
8 Speculative evaluation of primitive redexes
9 F-lite: a core subset of Haskell
10 Experminents in inlining, arity-raising, and indirection-avoidance
11 Enabling arity-raising by sharing analysis
12 An algorithm for arity-reduction
13 Compiling case expressions
14 First quarterly review
15 Towards a spineless Reduceron
16 Configuring the XUPV5
18 Spineless versus Spinefull
21 Second quarterly review
22 Compiling F-lite to C
23 York Lava, by example
25 Bounded template instantiation
26 Rotation and one-hot addition
27 Design of the Octostack
28 Mark-Compact in O(survivors) time
31 Design proposal for speculative evaluation of primitive redexes
32 Thoughts about Reducera -- a Plural Reduceron
33 Fourth quarterly review
34 Expected clock-tick run-times for flite-reduceron programs
35 Order of compilation passes
36 Case of known construction -- at compile-time and run-time
37 Counting the clock cycles needed to instantiate a combinator body
38 Benefits of a primitive-value stack
39 The Force-and-Rebind transformation
40 Forcing arguments to primitive functions, revisited
41 FitA-Cambridge Talk: Dynamic analysis in the Reduceron
44 An objective look at PRS
45 Hardware support for exploiting Static PRS
46 Checking for a fixed-point using needed narrowing
47 Descriptions of several F-lite programs
48 Primitive redexes in the spine position
49 hf: a tool that translates (a subset of) Haskell to Flite
50 Finding and increasing PRS candidates

Previous work

The Reduceron was first developed as part of Matthew's thesis, circa 2007. Here are some of the materials that arose from the thesis work.

Thesis Matthew's thesis, see Chapter 2
Paper Published at IFL'07
Source code Of the thesis implementation