Running dynamic algorithms on static hardware

Add to your list(s) Download to your calendar using vCal

• Simon Peyton-Jones and Satnam Singh (Microsoft Research Cambridge)
• Thursday 17 February 2011, 16:00-17:00
• SS03 of the Computer Lab.

If you have a question about this talk, please contact Eiko Yoneki.

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/

This talk is part of the Computer Laboratory Systems Research Group Seminar series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• CL's SRG seminar
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Computer Laboratory Systems Research Group Seminar
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• SS03 of the Computer Lab
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.