University of Cambridge > Talks.cam > Computer Laboratory Systems Research Group Seminar > Running dynamic algorithms on static hardware

Running dynamic algorithms on static hardware

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

  • UserSimon Peyton-Jones and Satnam Singh (Microsoft Research Cambridge)
  • ClockThursday 17 February 2011, 16:00-17:00
  • HouseSS03 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity