Abstract

Hardware is good for expressing static algorithms, where there is a fixed amount of computation to do (eg a 16-bit full adder). Functional languages are good for parameterising static algorithms; you write a function that runs at hardware-generation time, to generate variants of an algorithm (eg an N-bit full adder, where N is specified at hardware generation time.

But what if you want to write a recursive function, or more generally an algorithm that unfolds in a data-dependent way? (Fibonacci, say.) Moreover, we’d like to process heap-allocated data. No hardware description language lets you do those two things conveniently. But it would be great to do so, because that would let us whip up Huffman decoders, graphics processing algorithms, database filtering code, and so on, and have it execute in FPGA hardware 10 mins later.

In this talk we’ll explain how to do this. Of course, the trick is to use a fixed blob of hardware, and re-use it repeatedly, with an iteration counter or stack to keep track of which instantiation of the function is running. We compile a modest, first-order functional language, with full recursion, and access to a heap. We’ll describe the architecture of our system, and show you some running code.

Simon’s web page: http://research.microsoft.com/en-us/people/simonpj/

Satnam’s web page: http://research.microsoft.com/en-us/people/satnams/