Software, technology, sysadmin war stories, and more. Feed
Sunday, September 18, 2011

Reading the manual lets me skip a ton of monkey work

Sometimes you really should just read the manual. You never know when something you've been trying to do has already been done for you.

Back in one of my EE classes, there was one called Digital System Design, and it involved another bag full of parts and a breadboard. The difference was that this one had a pair of AMD programmable logic devices. It looks like it was a PALCE22V10, for those who know what that means -- it's just another random string to me now, years later.

Anyway, we had been given an assignment: create a small arithmetic logic unit (ALU) using our parts. We had to support four operations: add, increment, decrement, and negate. This meant we had two input lines to select the operation, and eight for our four-bit operands: A and B. Finally, there was a clock line.

We had to generate the following outputs: negative, zero, overflow, and the actual four-bit result. We were also supposed to supply an "odd" flag, but I just specified that as "use bit 0 of the output" -- my first optimization.

Here's where it started getting interesting. It appeared that the entire rest of the class had decided to go the brute force approach. From what I could see and what I overheard, everyone was making tables in their notebooks which looked like this:


... and so on. It was miserable monkey work. Four bits multiplied by two operands plus a two-bit operator equals ten bits of possibilities. 2^10 is 1024! As far as I could tell, they were actually going through and manually cutting and pasting and then flipping the bits to count all the way from 00,0000,0000 to 11,1111,1111. Then they'd figure out the results and fill in those bits. 1024 times. What a mess.

I managed to get it working without spending much time on it. I reasoned that a simple problem had a simple solution, and anything involving that kind of brute force was just wrong. The key was reading the manual for the MINC software we were using. In it, they had native operations to handle things like addition and subtraction! The rest was just a matter of using it.

That means instead of having 256 rows just to handle the "operator == 00" case of addition, it looked like this (actual code from the lab):

IF FN = 00b THEN                " add
        Z = A .+. B;
        neg = Z[3];
        zero = (Z = 0);
        over = (A[3] = B[3]) * (Z[3] <> A[3]);

Yeah, that's it. It's like a miniature program, only it gets turned into a bunch of gate connection instructions and gets burned into a chip and just sits there. Here, I just say that Z (my output) is equal to A added to B, using the discovery from the manual: an operator called ".+." which did basic addition. Easy!

The other three operations worked about the same. Increment was just adding 1 to A, and decrement was subtracting (.-.) 1 from A while handling the special case for starting at 0. Finally, negation was just subtracting A from 16.

The whole thing, including comments, fit in a 47 line file. Then, it turned into a solution which would fit into a single PLD chip. This was a good thing, because I had managed to fry my part kit's second chip earlier in the class by using the wrong setting on our PROM burner.

So there I was, with a working solution, and people looked at my board: it only had one PLD on it. All of their horrible hacks had multiple chips, and they had to do this terrible cross-chip wiring stuff to get them to share the work. Many of them didn't even function properly.

They wanted to know how I did it and wanted to look at my source. Now, back in those days, I was a total free software kool-aid drinking fanatic, but this was different. I decided to give just one hint: "it's in the manual". I don't know if they ever bothered.

Looking back on it now, it seems apparent that this MINC software had those operators for a reason. It would know how to reduce all of that stuff in a meaningful way to make it fit in a reasonable amount of chip space. It's also possible it could not do the same thing for that other mode where you just supplied a huge table of inputs and outputs.

All I know is that yet again, it came down to understanding the system instead of just poking around blindly. I wonder if the other students ever figured that out.