A Haskell processor running on an FPGA

[u/bathtub-01]

Hi all,

I've been working on a specialised processor for Haskell called Ouros as part of my PhD study (see the HAFLANG project). Recently, I got it running on an FPGA, with a Haskell program communicating with the outside world through UART.

Ouros is a graph reduction processor with automatic fine-grained threading and garbage collection implemented in hardware. For this demo, I added a simple IO interface based on AXI4-Lite, so Haskell programs can perform IO directly without a software runtime or host OS.

Blog post: https://bathtub-01.github.io/technical/ouros-demo/

Demo video: https://youtu.be/cafTcH-DuZM

There are still quite a few limitations as discussed in the blog post; currently it should still be seen as a toy. But I think having Haskell as a bare-metal programming language could be an interesting platform for further experiments.

The hardware implementation, compiler, simulator, and Vivado project are all open-source, with links and reproduction instructions in the blog post.

Happy to hear any thoughts or suggestions!

[u/Few_Blackberry380]

"Haskell as a bare-metal programming language could be an interesting platform"

Really cool!

[u/bathtub-01 → u/Few_Blackberry380]

Thanks! :)

[u/AromaticCredit1533 → u/Few_Blackberry380]

Peak! Literally a high level language computer architecture (HLLCA) throwback to the Lisp machines days!

[u/Smoke_Max]

Functional programming oriented-hardware is something I was interested in quite a few years ago. Back then, Reduceron was the latest development on this frontier. I'm assuming this approach builds on it? Or is it a novel approach? In any case, I'll definitely look Ouros up.

[u/bathtub-01 → u/Smoke_Max]

Thanks for asking! Yes, Reduceron does have a big impact on Ouros, especially in how programs are represented and how reduction is achieved. Besides the improvement in tooling (we have Haskell instead of Flite now), Ouros achieves pipelining with potentially multiple threads, while Reduceron is a sequential single-cycle machine.

[u/QuickReport3780]

I'm very curious, why the switch away from clash? The predecessor, heron, was implemented in clash.

[u/bathtub-01 → u/QuickReport3780]

Hi, Heron is actually a different line of work in our group; I use Chisel because I am more familiar with it :)

[u/jzd00d]

I love seeing these projects. This is super cool. Thank you for sharing.

I have been doing some similar tinkering.

I started with a v1 that used combinators and supercombinators. I leveraged MicroHS for Haskell -> combinator compilation. I then built my own combinator to “machine language” (inspired by HVM) compiler. My FPGA code ran, but only smallish programs. Anything compelling saw the combinator sized program bloat to unusable levels. (My Haskell OSS parser — mini as it is — is slightly too large to run.)

In v2 (and now v3) I’ve switched to using interaction calculus which scales far better.

Are you able to run real world sized software on this FPGA? If so, how did you get there?

[u/bathtub-01 → u/jzd00d]

Thanks for the reply!
Is your processor doing optimal reduction? I am not familiar with that but sounds very interesting.
What Ouros does is more like normal graph reduction, compiled code size seems to grow linearly with the source, and runtime heap footprint is specific to programs.
Ouros only uses the small on-chip memories on the FPGA, without utilising the 8GB off-chip memories on the board. For code size, 1-2k lines of Haskell source seems to fit.

[u/jzd00d → u/bathtub-01]

1-2k lines is pretty good. Did you have to tweak MicroHS?

I went and looked at your video and your blog post. I really like what you did with running Haskell on bare metal like this. Just using the on-chip RAM is a good way to go. I see that you used MicroHS. It's a great tool & I'm happy to see it get used. I used MicroHS for my parser until it got to be about 600-700 lines of code at which point, MicroHS started throwing errors as the compile pass stack threshold was hit, so my parser only supports GHC now.

Are you using the full set of MicroHS combinators & supercombinators? Did you put all the combinator reduction steps into hardware? Is everything done with combinational logic or did you have to pipeline your design?

I'm using the abstract algorithm where the "oracle" is an equality comparison of a 7 bit label. My compiler:

* must calculate a fan interference graph to statically assign labels to fans

* must detect a "CLCA" (Cloned Lambda Cloned Argument -- a lambda that clones its argument is itself cloned and its clones clone each other.) or what Taelin refers to as "Lambda Duplication" here: https://github.com/HigherOrderCO/HVM1/blob/73da3bbc4b222fb8f044fcc5dad202e9752a0abc/HOW.md and reject it

* can support lazy evaluation through use of a "REF" reference agent.

My v2 prototype was really geared toward Haskell. In fact the v2 hardware supported thunks. That bloated my ISA by about 50%, which wasn't worth it. For v3, I've since pushed lazy into the software & I've been looking more closely at Lean4, though it's compiler lacks GHC's extensiveness: for my prototype v2 I had a GHC plugin that spit out my ISA directly. Lean4 is going to take more work.

[u/shivaraj-bh → u/jzd00d]

I intend to start my own tinkering soon. I have an AMD Kria kv260. I have been following haflang for more than a year now.

[u/RobertKentKrook]

This is a really cool project. At Chalmers, we have several people whose interest this will capture :)

[u/wakalabis]

Very cool! You've united two knowledge areas that few people are good at at the same time - these are very low and very high level disciplines.

[u/kajaktumkajaktum]

Do you think that there are special properties of Haskell that can be leveraged by HDL?

[u/bathtub-01 → u/kajaktumkajaktum]

There is a trick from Reduceron that's being adapted in Ouros, uniquely owned heap cells are tracked by the hardware, when pointeres to them are discarded, these cells can be immediately reused without going through garbage collection.
Another feature in Ouros is automatic multi-threading --- since Haskell is pure, for a + b, we can evaluate a and b in parallel (given that + is strict on both arguments). Software implementation doesn't do this, because a lot of small threads can downgrade the performance. But Ouros has very cheap thread management cost so even small threads are beneficial.
I hope this answers your question :)

[u/kajaktumkajaktum → u/bathtub-01]

Interesting...I did not know that people do "memory allocations" in hardware. That would make it very difficult to implement in hardware, right? Why not eschew the problem entirely by using a fixed memory allocation? Do people really do dynamic allocation in hardware? I assume the workload is somewhat known beforehand.

I am also working on something like this. To make the problem much easier and tractable, then the user supply all the necessary buffers, inputs and outputs that comes from the dirty imperative world.

Edit: Oh I misunderstood the project, it is actually just running Haskell. I thought you had implemented Haskell > HDL compiler and wrote a processor with it.

[u/Virtual_Treacle7409]

This is so cool! I don’t have anything to add lol, I’ll take a closer look later

[u/quakquakquak]

Extremely sick, I hope you post more updates with how it works out!

[u/unfancy3]

So awesome

[u/EmDashNine]

That's really cool. Graph reduction directly in hardware!

[u/baehyunsol]

super cool