Skip to content ↓
MIT student blogger Evan B. '10

The Impossible Design Project by Evan B. '10

See what it's like to be a Course VI student.

Ok. Well, I’ve been kind of busy these days. Taking 5 classes (2 CIs and 2 labs will do that). So…I thought I’d take the easy way out, by giving you one of my problems to take a look at.

6.033 is Computer Systems Engineering. It has lots of different components to it – so far we’ve talked about the Therac-25, the X Windows System, multi-threading, and a couple of other things. It moves quickly through different topics, all of which are very interesting.

In particular, though, 6.033 has two design projects, where we’re presented with a fairly real world problem, and we have to try to solve it. This year, we have to create a controller for a NAND flash device.

The controller sits between the filesystem and the physical device itself, and has to make the flash look like a traditional magnetic disk, in spite of the fact that flash memory is distinctly unlike a magnetic disk.

Here’s the description of the problem:

Feel free to submit solutions in the comments. My one recommendation is that you should make sure that you actually have enough RAM to store what you want. My friends and I spent multiple days coming up with and throwing out lots of different options, and none of us have a solution that we’re truly satisfied with, so don’t feel bad if you have a hard time coming up with something that works.

You can not solve this problem without making significant sacrifices in either the available storage space, the read and write performance, or the ability of the controller to balance wear over time.

I’ll post my solution after I give you guys time to play with it. Also – feel free to let me know if you have any questions – I know it’s kind of hard to follow at first. (And as usual, questions about other MIT-related things are also OK)

18 responses to “The Impossible Design Project”

  1. Vytautas says:

    Sh1fty, the thing is that the data can only be written once between the erases to the data section and 4 times to the meta section. So dividing to sectors is unpractical. Also, taking count of the writes is not needed(maybe just one bit in meta data to mark it as written). I’m not a wizzard at this thingie, but I’ll try to come up with something. I became curious about it smile

  2. Evan says:

    Ok – good! Sh1fty, you’re definitely starting the right way, just keep the constraints in mind, and remember: there is no “good” solution.

  3. Anonymous says:

    Once upon a time, I actually thought I knew what those words meant….

  4. Nihar says:

    I may be oversimplifying it, but this looks a lot like the Computer Science Dossier concept that I have to complete as a requisite for IB Diploma…..only much more complex…

  5. Evan says:

    I doubt that you’re oversimplifying it, Nihar. It’s definitely not supposed to be a particularly complex problem. And in fact, from the standpoint of 6.033, which is largely about effective communication, a good solution should be pretty simple too.

    I think the best way to start thinking about the problem is to consider the various things you can trade off: there’s the complexity of the solution, the total amount of storage space available at the next level up, the speed of reads and writes, and the effectiveness of your wear leveling strategy.

    Start by figuring out which traits are important to you, and start coming with designs that maintain those traits.

  6. Sh1fty says:

    wear leveling seems like the hardest part to do, especially with only 40K of RAM available. i’d probably use those 40K of RAM as a writing buffer(something like cache) and i’d use the last 2.5MB(20 erase blocks) as virtual memory. i’d dump the whole RAM into that allocated space and i’d do it so that during the first dump the last page from RAM is dumped into the first page of the last erase block, the one before last page would be in the fist page of the erase block before the last one and so on. during the second dump i wouldn’t erase anything, i’d just dump everything into the second page of each erase block until i fill the erase block up(64 dumps) and then erase the blocks. since that would allow me to dump the RAM only 6.4 million times i’d allocate a bit more space(25-50MB) and move on to the next virtual memory block once i reach 98304 erases(64k+32k). that way i’d sacrifice only 0.6% of the capacity and probably gain some speed and definitely gain some time before those fatal 100k erases smile when is that project due? btw this might not be a good idea but it’d be a cool thing to try :p

  7. Sh1fty says:

    i’d split the data area of each page in 4 parts, which would act as sectors(512B). after that i’d just translate the CHS/LBA address and grab the page and then sector i need. reading and writing should be automatised. i’d definitely use part of the meta-data area to count how many times the sector was written to since the last erase. i’m currently working on something so i can’t go any deeper atm :D i’ll let you know if i think of something interesting wink

  8. Anonymous says:

    hmmm, i wish i knew where to begin with this but i dont, hopefully ill learn it next year.

  9. Anonymous says:

    ok, i don’t know what this means (yet!) but that’ why i want to be a course 6 major at MIT

  10. 6033Student says:

    Maybe you’ll want to post your solution after the design due date.

  11. E. Rosser says:

    Ditto. Prospective course 6 say WHAAAAAAT?!?

  12. Steven says:

    Well, I’m beggining to think that there is no possible way on earth that I will make it into MIT. I’m only freshman in high school. When did you guyslearn these things>?

  13. Steven says:

    Vytautas, You still know a lot more than I know. I am signed up for my high school’s computer science class and engineering classes; but what types of books should I be reading>?

  14. Vytautas says:

    Oh, it’s a simple question. You read those books that interest you. And I know that my answer didn’t help you, but still, read what you’re interested in. And if you don’t understand something – look it up.

  15. Evan says:

    Basically the best way to learn this sort of thing is just by playing around with different systems. I know quite a bit about Linux and Linux-like systems (although not as much as other people around here…) just from having a Linux machine to play with.

  16. Vytautas says:

    Steven, along with the highschool course by spending unlimited time reading and doing stuff with my PC. And I still know nothing.

  17. Francisco says:

    Most likely many in this project will find a way to make more space or either an efficient way of data transfer. I would also add in into the project if I was doing it a way where the micro controller would act as an archive where the data is located due to as the space gets bigger the easier data could be found ( I am not talking about a search engine). To increase performance well I would allocate memory differently depending on which o.s is going to be and work with. So in the micro controller one I would put a set of instruction for osx(buya), windows(under_development), linux(buya) to work with data flow ( a tweak). For future development of space I would suggest nanotech.

  18. Steph says:

    Hey guys! I’m currently a graduating senior in CS from MIT. Don’t worry at all about not understanding the project. I actually came into MIT with not much background in CS, and ended up completely fine. Most of the classes actually assume no background at all. So no worries! You all will be great! smile