The Reduceron

Matthew Naylor, Colin Runciman and Jason Reich

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