Skip to content


Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: 9716d959c3
Fetching contributors…

Cannot retrieve contributors at this time

139 lines (91 sloc) 4.647 kb
Reduceron for Embedded Systems
Reduceron is a high performance FPGA softcore for running lazy functional
programs, complete with hardware garbage collection. Reduceron has been
implemented on various FPGAs with clock frequency ranging from 60 to 150
MHz depending on the FPGA. A high degree of parallelism allows Reduceron
to implement graph evaluation very efficiently.
Reduceron is the work of Matthew Naylor, Colin Runciman and Jason Reich,
who have kindly made their work available for others to use. Please see for supporting articles, memos, and
original distribution.
The present is a fork of the original distribution which intends to take
the (York) Reduceron from the research prototype to the point where it
can be useful for embedded projects. One could imagine an Arduino-like
ecosystem, except replacing C++ for Haskell and the inexpensive Atmel AVR
for a less inexpensive FPGA.
The York Reduceron needs the following enhancements to meet our needs:
0. The heap and program must (for the most parts) be kept in external
memory, with FPGA block memory used for the stacks and heap and
program caches.
This simultaneously enables smaller and less expensive FPGAs to be
used as well as allows for a much larger heap and larger programs.
1. Access to memory mapped IO devices (and optionally, RAM).
2. Richer set of primitives, including multiplication, shifts, logical
and, or, ...
3. Support for 32-bit integers - this greatly simplifies interfacing to
existing IO devices and simplifies various numerical computations.
[[Work is progressing on all four fronts, but we are not there yet.]]
While Reduceron technically refers to the FPGA implementation, it is
supported by
- Flite: the F-lite to Red translator.
- A Red emulator in C
- York Lava: Reduceron is a York Lava program, which generate VHDL and Verilog
- Support for Verilog simulation and synthesis for various FPGA dev kits.
As much of the history as was available has been gathered and
reduceron, york-lava, and the Flite distribution have been merged into
one repository.
Optionally: just run make in the toplevel directory and a large regression
run will start. The Verilog simulation part will take weeks to finish.
To build:
First the F-lite -> Red compiler:
$ make -C flite
Next, the Reduceron Red -> RTL generator:
$ make -C fpga
Translate your favorite program:
$ cd fpga; flite -r ../programs/Fib.hs | ./Red -v
Optionally, simulate:
$ make -C Reduceron
Finally, building a Reduceron system for DE2-70
$ cd Reduceron/DE2-70; quartus_map Reduceron;
$ quartus_fit Reduceron; quartus_asm Reduceron
Some manual effort is needed here, but should be straight forward if
you are used to working with DE2-70. Note, the generated
Reduceron.v is the same regardless of the Red input, only the memory
initialization file changes.
Step 1: Port to Verilog and Altera. DONE!
Step 2: Shrink to fit mid-sized FPGA kits (eg. DE2-70 and DE2-115).
DONE! (However note that the shrunk version doesn't run all
In some order:
Step ?: Improve Lava simulation and RTL gen
- Add a C backend for much faster simulation
- Use names from the design
- generate busses where possible
Step I: Add primitives (mul, AND, OR, XOR, SHL, ASR, [SHR], ...)
(*), (.&.), (.|.), (.^.), (.<<.), (.>>.)
DONE: (.&.)
Step X: Add IO primitives (store and load from the IO bus)
(*<-), (<-*) [subword variants]
DONE: (*<-) with room for improvement
Step ?: Add the ability to accept bubbles (eg. cache misses)
- Start with (<-*) which will block for some cycles until IO returns
Step H1: Move the heap [and tospace] to external memory
Step H2: Add a heap cache/newspace memory
Step H3: Implement the emu-32.c representation for the external heap
Finally: Performance improvements
Q1: Currently there doesn't seem an efficient way to handle toplevel
variable bindings (CAFs). What did the York team have in mind
there or does it require an extension? (Obviously one can treat
them all other functional arguments, but that would mean a lot of
parameters to pass around).
Q2: Why does Flite default to 0 for the MAXREGS parameter? Eg, why is
redDefaults = CompileToRed 6 4 2 1 0
Q3: What happend to Memo 24?
Questions, suggestions, help, etc. are most welcome,
please write
Jump to Line
Something went wrong with that request. Please try again.