I've uploaded my proposed student projects for next academic year.
They are (1) a project about developing good sorting algorithms to make
use of scratchpad memory (SPM), (2) a project about automatic Redstone circuit
generation for Minecraft, and (3) a Tetris solver to be developed using
FPGA hardware. They're available for undergraduate students who will be
able to apply for them early next term.
The first proposal is based on a paper, submitted to a major conference
(but not accepted) in which I reached the interesting conclusion that the
very best usage of SPM for data storage would require new algorithm designs.
Just because Quicksort works well if you have a cache does not mean it will
work well with SPM. In fact, there may be some other algorithm that works
even better than Quicksort, by taking advantage of SPM. The topic is "external
sorting" (to use the appropriate terminology from Knuth) and the algorithm
I worked out was an SPM-specialised variant of Merge Sort. Merge Sort has
the general disadvantage that data is copied as it is sorted, so in-place
sorts are not possible,
with SPM you cannot sort in place anyway, as you are forced to explicitly
copy data between external memory and SPM.
The second is based on the game Minecraft where you can build logic circuits
out of an in-game material named Redstone. The process is crude, but could
be greatly improved with the aid of some Electronic Design Automation (EDA)
tool targetting the Minecraft world.
The third is based on a project I ran this year to develop a real-time Tetris
solver in software. The FPGA will be an ideal target for evaluating various
possible moves and determining the best one, because it can test thousands
of possible moves in parallel.