Austin Mueller and I started a company earlier this summer, called Tabus Nine Computing. The focus of the company right now is writing Android apps, and we’ve been working through the summer to release our first one. It’s called Modulus, and it’s a math puzzle game.
The idea of the game is that in every puzzle, you’re given a starting number, and there’s a target number. The goal is to get your number to equal the target number, and this is done using the six buttons. Each button performs a different math operations on your number. The amount that the Add button adds to your number, or how much the Divide button divides it by, is called the value of the button. The six buttons are Add, Subtract, Multiply, Divide, Modulus, and Exponent.
There are three difficulty modes: Easy, Medium, and Hard. In the Easy difficulty mode, the values of the buttons are displayed on the buttons. However, in Medium, they aren’t. So the values of the buttons are something you’ll have to figure out as you solve the puzzle. In the Hard difficulty mode, the buttons aren’t labeled at all. The positions of all the buttons are randomized, so you have to figure out which operation each button performs. To make sure you don’t have to keep all of the values and operations in your head, in the Medium and Hard difficulty modes, you can hold a button down to label it with the value or operation you think it is.
There are three game modes: Puzzle, Challenge, and Free Play. For each difficulty mode in the Puzzle and Challenge modes, there are twenty games, so 120 games total. In Puzzle mode, you just have to solve each puzzle. There are no limits on the number of moves you can make. In Challenge mode, there is a limit set on the number of moves you can make to solve each puzzle. Free Play mode generates random Medium difficulty puzzles, so you can keep playing indefinitely.
All in all, it’s a fun game. You need to think, and it stretches your mental math skills. We haven’t seen much else out there like it, so it’s a new experience, not just a new look put on an old game.
As a quick overview of my senior project, it was to design a stack-based processor (the OZ-4) and compare its performance and architecture to that of a register-based processor (the OZ-3) that I designed about a year and a half ago. I decided to do this project because I was rather unfamiliar with stack-based architectures, and I wanted to explore them and see just how well they perform. To make these processors a reality, I implemented both of them, as well as a small system around them, to test their performance. Since I was also exploring stack-based processors, I programmed the OZ-4 to generate Mandelbrot fractals, as it did in this picture:
Since I last posted here in March, I’ve finished my senior project and presented it at my high school on one of the senior project nights, as you can see in the video above. At the end of March, I had almost finished the VHDL code for the stack-based OZ-4. It was only about a week after that that I had finished the OZ-4 without running into too much trouble, and then I started programming it to generate Mandelbrot fractals.
This was rather difficult. I had to get used to moving things around the stack and keeping them in the right places while also performing the calculations and setting up the stack for the next iteration. For the actual calculation of each iteration on a certain pixel, I changed the order in which some things are calculated so that they can be on the stack in such a way that when the iteration is all said and done, the stack is ready for the next one. At the end of it all, I had a 76-instruction loop that was the core of the Mandelbrot calculations. It rand the actual calculation, checked the various exit conditions, and moved the stack around appropriately. As I was making this program, I discovered that there was a fair amount of wasted cycles when programming a stack-based processor, and those cycles were dedicated to manipulating the stack. Those operations don’t actually do much to advance the program in the right direction, since they aren’t actually doing calculations.
I finished the Mandelbrot generator after letting the project sit around for about a month while I finished up the school year. It generates the image you see in the video in about twenty seconds, which is a bit slow compared to other Mandelbrot generators. However, I think that I could have clocked the processor faster than 25 MHz and taken that number down. At that rate, it was calculating about 15,000 pixels per second. In the end, I wasn’t really out to make the speediest Mandelbrot generator, I was just learning about how to program stack-based processors.
Now, since my project is officially a comparison of stack- and register-based processors, I compared the OZ-3 and OZ-4. The OZ-3 is a register-based, pipelined processor that I designed a couple years ago, then implemented over the year after I finished designing it. To make a fair comparison, the two processors had very similar I/O capabilities, so they could be plugged into the same system as the other. They ran at the same frequency, 25 MHz, and they had access to the same amount of memory, and had the same ALU for performing the complex fixed-point multiplication that they would need to generate Mandelbrot fractals. Here’s the system that they were in:
Unfortunately, I didn’t have time to get the OZ-3 to generate Mandelbrot fractals or use the mouse, but I compared the two processors in other ways. I broke down the results into the table below. The four programs they ran were simply counting to 100, finding all of the prime numbers from 0 to 100, calculating the first 50 numbers in the Fibonacci sequence, and calculating a math expression.
|Count to 100||102 cycles||202 cycles|
|Prime Numbers||3.0 ms||3.8 ms|
|Fibonacci||153 cycles||151 cycles|
|Math Expression||19 cycles||19 cycles|
(((5 + 3)6) + 24) – ((33 – 6)2) / (7 + (2*4)) = ?
For reference, that’s the math expression I had the processors calculate. As you can see, the OZ-3, the register-based processor, performed better than the OZ-4 overall. I was surprised about this. At the start of this project, I had just assumed that stack-based processors are faster than register-based processors. This was not the case here. The assumptions came from the fact that it seemed like stacks are used a lot in modern computing, and that HP calculators, with their stacks, can usually do math faster than other calculators. Nothing solid to base my hypothesis on, and it was proven false here.
I found a few reasons for this result. First, the stack-based OZ-4 wasted quite a bit of time just moving the stack around so that it could work on the right numbers, and this is one of the main faults of stack-based processors. Register-based architectures allow access to all of the data in the register at any time, and are thus more flexible, whereas the stack denies access to all but a few pieces of information at any one time. Next, the instruction set of the OZ-4 was somewhat limiting. It wasn’t very flexible, and basic functions like branches and jumps took two to three cycles each, as opposed to one or two. I did this to keep in line with the zero-operand instruction sets of many other stack-based processors, but that certainly didn’t create an advantage.
To look at a specific example, the reason the OZ-3 ran twice as fast in counting to 100 is that the OZ-3 could run this instruction in one cycle: “addi r1, r1, 1″, which adds 1 to register 1. The OZ-4, though, had to use one instruction to push 1 onto the stack, then another to add it to the counter. Another one to look at is evaluating the math expression. I thought the OZ-4 would cream the OZ-3 in this test, but they were exactly equal. The stack-based architecture can easily and intuitively evaluate that expression from the inside out, keeping sub-results on the stack until they need to be combined into the full result. But, because of the flexibility of register-based architectures, I was actually able to program the OZ-3 to use its registers as a sort of pseudo-stack, and it could keep the same performance as the OZ-4.
However, just looking at their performance doesn’t provide a full comparison. The OZ-4 may be slower in software, but its hardware is significantly smaller and simpler than the OZ-3, and this would, in theory, let it run at a higher frequency than the OZ-3. I didn’t test this specifically, but it is one advantage the OZ-4 has. This also made it easier to design the OZ-4. The second big advantage the OZ-4 has over the OZ-3 is program size. The OZ-3′s instructions are a full 32 bits long because they need an opcode and three fields to specify the source and destination registers. In other addressing modes, the space is taken up by immediate values. The OZ-4′s instructions, though, are only twelve bits long, and could even be six bits long 99% of the time. The first six bits are the opcode, and the last six bits are for specifying which immediate value is to be used in the event of a PUSH instruction. The instructions are shorter because the operands are implicitly on the stack, and don’t need to be encoded into the instruction.
Finally, here are the block diagrams for both processors:
I took this project on as a present for my girlfriend, who, during the colder months, is more or less addicted to coffee/hot chocolate/tea. Her mug broke, and I was just going to get a new one for her birthday, but I wanted to add a little functionality to it. The new mug now senses and displays the relative temperature of its contents on a 10-LED blue bar display and has a rechargeable battery, which is charged through a 5.0V DC jack. Turned out pretty well, although it reacts a tad slow to temperature changes, as you can see in the video.
I took another crack at making my own circuit boards, and with much better results. The first thing I did was change the design to be better suited for toner transfer. The traces before were 0.010″ wide, so I bumped them up to 0.016″. Doing that makes the breaking of traces less likely when transferring the toner. I also put more copper around the pads for the five jumpers, so the copper I accidentally remove during drilling doesn’t make too much of a difference.
I made my first circuit board yesterday, and it was a lot of fun. I used the toner-transfer method, with an etching solution made out of hydrochloric acid and hydrogen peroxide. I more or less followed this guide, although I read at least a dozen on different methods. Unfortunately, I forgot to bring my camera to the workshop, so I only have a picture of the finished product, not the process.
So, I came across this simple, yet cool project and decided to make a couple of these guys as a smaller present for my girlfriend’s birthday. It was a bit challenging to get all of the soldering to work out, and I’m sure almost all of the joints were made cold. I modified the design a little to use the capacitor as a leg, since in the original ones, the ground wire is a leg and the capacitor is on the board. I took out the ground wire, since one of the capacitor’s leads goes to ground, which became the new ground wire. So now they’re more free-standing, and able to dance.
As my Christmas present to my girlfriend, Cat, as well as an introduction to microcontrollers, I made a cube that glows different colors as it’s tilted different ways. I works by having a PIC12F615 take readings from a 3-axis accelerometer, then turning those readings into colors for each component of a few RGB LEDs, which are controlled with pulse width modulation.