Week 6: Microcontroller Programming of DOOM

I designed and routed a simple board based on the template distributed to the class. My design was a little bit different from most of the others, because I wanted my LED to turn on when the pin was set low. This meant that my code was backwards from most other people's. Here is my layout file. (You'll need the fab and ng libraries as well).

I Had a Great Idea

I decided to see how much I could do on one of these little chips. So my plan was to have the blinking of the LED controlled by a Markov Model. Then, when the button is pressed, the sequence would be buffered, and when the pressing stops, the program would the Baum-Welch algorithm to re-train the model to match the input sequence. If you do this enough times, the blinking light should start to mimic the patterns of button presses. This seemed like such a great idea.

Then I Slammed Into Reality

Unfortunately, these chips were not really meant to run complicated programs. I ran into several very difficult problems trying to get this project done.

  1. 256 bytes is not a lot of bytes.
  2. 4k of flash memory is only about 400 lines of C.
  3. It's hard to debug using a blinking LED.

The first challenge is that the attiny44 only has 256 bytes of variable space. The Baum-Welch algorithm requires (number of nodes) x (number of observations) x 2 variables just to run properly. Assuming we use 4 byte floats to do all probability calculations, then 3 nodes and 10 button clicks is already too much to hold in RAM - and that's ignoring all the actual parameters of the model. This means that we're gonna have to give up resolution, and make due with fewer bytes per variable. This also means we'll have to be really careful about variable typing, and make sure we're only instantiating what we have to. I made heavy use of in avr-libc.

Second, it was actually harder to keep the program smaller than 4k than to keep the variables under 256 bytes. For instance, I could not use floating point numbers anywhere in the code. It took almost 3k of memory just to include the necessary libraries!! See, the attiny44's instruction set only works on 8 bit ints. So all floating point numbers have to be managed in software, which requires a lot of code. In fact, it's so much code that it takes almost all of the available flash memory just to load the libraries. So I had to use integer based probability, and manage everything myself.

Also, I quickly realized that every line of code that used a uint32_t translated into at least 20 lines of assembly. Why? Well, while it's not as bad as floating point math, 32 bit ints are also managed in software. So it takes several extra operations to do anything with these bigger variables. Several parts of the algorithm really do need the extra precision, so it was a struggle to keep the program under the limit. Towards the end of development, every time I wanted to add a single line, I had to delete at least one from somewhere else. I really couldn't write all the methods I wanted. The worst part was that I couldn't write any debugging methods - like special blink codes for the LED that might tell me when something went wrong. There was so little space that they simply wouldn't fit.

8-bit Probability Will Murder Your Children

By far the worst part of the whole project was dealing with overflow and underflow errors due to low precision variables. I decided to represent all of my probabilities using 8 bits (with a range from 0 - 255). This is simply not enough resolution to do some of the calculations, so they were done using 32 bit ints. Then the high-resolution calculations had to be down-sampled into this 8-bit representation. This is a terrible process. If numbers are too big they run over the limit and wrap around, giving completely wrong values. If they're too small they end up snapping to zero, which causes all sorts of numerical errors. In the end, my code is full of strange syntax for multiplying and dividing variables in just the right order, to avoid as many conversion errors as possible. I would not recommend this to anyone, but if you want the code, it's available here. I suggest compiling with the Makefile.

Gettin'er Done

So I actually programmed the thing using my own FabISP, and it worked. Well, sort of. It still has underflows and overflows if you press the button too quickly or for too long. But if you avoid those extremes, it actually learns a Markov model, and the light turns on based on sampling it. So It's kind of a success. Kind of.