Student Project Proposals for 2012/13
Saturday, 28 January 2012
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, but 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.