CS 6410: Advanced Systems
"Mini" Project information
Starting in Fall 2014, students in CS6410 will need to do two mini-projects aimed at confirming their mastery of basic architecture and operating systems material. Neither is intended to take long or be very hard, and both are designed to also be useful to you even if you plan to work in a research area very remote from systems.
Mini-project I: Due September 11.
What we want you to do: You'll work on Linux or Windows (we don't have a preference), in a programming language that permits high performance. Here we do have a preference: we recommend C or C++. This said, we are willing to accept projects in other languages like Java or C# if you really don't want to work in C or C++.
In this language, please implement your own multi-threaded version of the "Game of Life" cellular automata program http://en.wikipedia.org/wiki/Conway's_Game_of_Life), designed to allow an infinite playing board that would have some initial size we'll specify, but can grow without limit as the game runs (for example if gliders head off into outer space...). You can use any data structures you like, for example to maintain "occupied" blocks of the game space and not bother to maintain empty regions. You can implement the code in any way that you feel good about, aiming for high performance and utilization of the available cores.
Now, run your program on a multicore computer. Most of the desktop computers in the department are at least 4-core machines and many have more; there are quite a few 32-core machines around. Matt can explain how to track such a machine down; you may need to ask the user's permission but you should be able to remote login to pretty much anything with permission. You should aim to build and test your project on your 4/8-core desktops, and only collect occassional performance data from larger machines.
Your challenge: squeeze all the speed you can out of the solution you built. Test it on a mix of "classic" Game of Life scenarios (you can find a bunch on the Wikipedia web site link shown above) and on random n x n intiial configurations, for values of n that increase by 10's: 10, 100, 1000, 10,000. We aren't going to be very specific here about what exactly to measure in order to assess speed, because we see that as part of your challenge: we want you to figure out how one even can charactize speed, given the very different ways "life" evolves depending on the initial configuration.
What to hand in: When finished, hand in a short (certainly no more than 6 pages; 2 should be fine) writeup describing your findings, written in a scientific style (e.g. as distinct from an email to a friend from home). Include graphical content if that's the best way to explain things, or "microbenchmark" results in tabular form, or other kinds of analytic material. Think hard about what you learned and how to communicate that knowledge to Ken and Matt. Some ideas regarding the paper: consider looking at good quality graphics in other kinds of performance-oriented systems papers: how did the authors use graphs to communicate succinctly? Consider the ways one might challenge your claims: are you adequately supporting your assertions with rigorous evidence? If your paper feels too long, think hard about what really matters and what is more or less window-dressing. Which were the top five lessons learned? Are you using a lot of paper on the next ten, or on things that were dead ends?
Why so short? We believe that a really good systems analysis gets to the point without wandering around, and is structured and clear. Further, writing in a short and clear way forces you to think about using graphics as a communication tool. Many systems workshops (like HotOS) have a six page limit; some actually have a two page limit.
What are we hoping you might learn? Everyone worries about performance no matter what they are doing in CS. Performance of a multicore program can be surprisingly hard to optimize: you need to think about scheduling, contention, sharing, cache evictions, etc. So it can be hard to really get high speed even from a powerful 12-core desktop "supercomputer". You'll gain experience doing so, and will also find it challenging to communicate your findings in a succinct way, which is a skill that will benefit you later when writing other kinds of papers, whether in systems or in other areas of CS.
Mini-project II: Due Oct 2.
This will involve running Paxos as a service on EC2 using Elastic Beanstalk and then experimenting to find the performance-limiting bottlenecks. Details will be posted soon.
"Main" Project information
IntroductionFor the project, you can write a research paper or, if you prefer a more hands-on approach, build, design, implement an interesting system of your choice. There are six deadlines:
You should feel free to choose any project you like, as long as it is related to storage systems, distributed systems or operating systems. It must have a substantial system-building and evaluation component. A successful class project usually have very well defined goals and is modest in scope (Remember, you only have 2.5 months to finish it). You could look for inspiration about hot topics in the on-line proceedings of recent SOSP, OSDI, Usenix, and NSDI conferences. Tips on preparing a paper appear appear here. Here's a list of ideas that we think could lead to interesting projects. Start as soon as you possibly can!
The best projects will lead to papers you can submit to a good conference. We're ok with projects that have CS 6410 content but are tied to work you are starting with a faculty member in the field. The key thing is that projects need to be serious research activities that lead to publishable or at least very high quality papers (12-14 pages, written very well and in a scientifically literate style, aimed at a clearly defined community).
Questions or comments? email firstname.lastname@example.org
Policy on academic integrity