Understanding and synthesising hardware-like algorithms


Some algorithms are suitable for implementation directly in hardware (on an integrated circuit or field programmable gate array). Examples are sorting networks and parallel prefix (or scan) networks. (A typical microprocessor will have several parallel prefix networks on it, and they are the hot spots!)

These kinds of algorithms are often rather regular and they lend themselves well to being described using a functional programming language and higher order functions. This has been the topic of research by Mary Sheeran, Koen Claessen and Emil Axelsson here at Chalmers, resulting in Lava and Wired. Lava, particularly, has been very influential and has spawned more such libraries. 

The original Lava paper: http://www.cse.chalmers.se/edu/year/2012/course/_courses_2011/TDA956/Pap...
Cool uses of Kansas Lava: http://gergo.erdi.hu/blog/tags/FPGA/

Recently, Sheeran gave an invited keynote talk at the International Conference on Functional Programming about the combination of hardware design and functional programming and why it is still interesting:
and the slides, with lots of clickable links are available too.

Minutes 17 to 37 of this talk cover these fascinating regular algorithms and the many open questions that remain. A major topic of the talk is the idea that having a language to express hardware-like algorithms allows us to play with them, and thus to understand them and invent new ones.

There are a number of different possible masters thesis projects that could be designed around this theme. Details need to be worked out in a dialogue between the student and supervisor.

1) Understanding and synthesising sorting networks
There are many open questions here, and I would like to demonstrate that using a functional langauge allows at least one to be solved. For example, there is a lot of ongoing work on searching for small networks (with small numbers of inputs). Can we do better? There are interesting uses of SAT and SMT solvers possible here.

2) Better median networks
Median networks don't entirely sort their inputs, but output the "middle" element on the "middle" output wire, with smaller elements above and larger elements below, unsorted. They are important in much used functions like median filtering (an image processing function that is interesting both in hardware and in software). Folklore says that for 25 inputs, 99 compare and swaps is as well as we can do, but Sheeran has got this down to 96, in a rather ad hoc manner. Can we do this more nicely, and also do better? See the keynote for a little more detail, and the relevant paper is

3) Implementing regular algorithms on FPGA (field programmable gate array)
The latest incarnation of Lava at Chalmers is work by Markus Aronsson on a library called Signal, which can be used to generate VHDL code. We would like to explore the use of Signal, and push its development, by implementing interesting examples on the FPGA on the Parallella board from Adapteva.

4) case studies in Bluespec System Verilog (BSV)
Bluespec is a high level hardware description language with strong influences from functional programming (and even Lava-like ideas) and Term Rewriting Systems (see the keynote again). We would like to explore the use of Bluespec in programming the FPGA on the Parallella board from Adapteva. We would be strongly influenced by our contacts at Bluespec Inc. in choosing relevant case studies.

5) case studies in Chisel
Chisel is a new hardware construction language (similar in spirit to Lava) in Scala. It is being developed at Berkeley and is getting a lot of press. It is being used very successfully by a group designing new parallel architectures. The chisel page: https://chisel.eecs.berkeley.edu/
This is an open source project. It would be interesting to do some case studies in Chisel, and to contribute to its development. This project would be relevant to those who already know Scala, or would like to learn it.

Relevant courses:
Advanced Functional Programming
Parallel Functional Programming
Compiler construction
Software Engineering using Formal Methods

All of the above projects could be designed to lead to research paper publication.