VHDL

VHDL: Even Fibonacci numbers

Project Euler problem 2 calculates the Fibonacci sequence

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms

This is the sort of thing problem that I've seen people asked to do fairly often in hardware. We're going to use the same top level entity that we described here.  To calculate the Fibonacci sequence you need two registers. To get the next Fibonacci number you need an adder, and to get the sum of the even numbers, you need an accumulator. Two comparators tell you when you're number is even, and when you've hit the max input value. 

block diagram for a hardware implementation

block diagram for a hardware implementation

Translating this directly into VHDL works out pretty well like this: 

And running that through a simple simulation with a clk, enable, and reset and monitoring the results_valid will get us a simple test bench. Taking a quick look at the start of the simulation shows us if we're on the right track. 

We can see the Fibonacci sequence in the sum register, and the even signal toggling each times it's even and the results accumulator summing these even numbers. 

We can see the Fibonacci sequence in the sum register, and the even signal toggling each times it's even and the results accumulator summing these even numbers. 

And that's about it. We could change the generic we pass in for the max_value to get this to run up to any maximum. One of the things that surprised me is how fast we got to the solution brute forcing our way through each Fibonacci number. 

VHDL: Multiples of 3 and 5

One of the reasons this is such a great starting problem is that anyone can solve it very easily with pretty minimal brute force, which I imagine is the idea to rope people in to start seeing the joy of determining more refined algorithms. I don’t actually have that joy, but I don’t mind solving this problem in a variety of languages, even if that doesn’t end up being a variety of ways. From the site: 

Find the sum of all the multiples of 3 or 5 below 1000.

Since we’re doing synchronous hardware design, our module will have a clock and a reset going into it. It will have a results bus coming out, and a signal telling us when the results are valid. To make solving this multiple times slightly more interesting, we’re going to solve this for any number, n. In this case I made it a generic in VHDL, but it could (and maybe would) also be an input bus.

VHDL entity describing the inputs and outputs of a module. 

VHDL entity describing the inputs and outputs of a module. 


So in hardware we can design a counter to count from 1 to n. We can have an accumulator that will sum the current counter number with the previous sum based on some control logic. And the control logic has is the logical OR of two similar calculations, on whether the count value is divisible by 3 or by 5. Dividing is actually a very bad idea to do in hardware, but we could instead have parallel counters continuously counting from 1 to 3, and 1 to 5. Any time these control counters hit their max value, the main counter will be a multiple of 3 or 5. So from there, we get this block diagram:

We can take this block diagram and turn it pretty literally into a VHDL architecture as is which looks something like this: 

That's pretty long, and one of the major complaints about VHDL coding is that it is quite verbose. But we don't have to take the diagram that literally either. Each element that is sequential (the counters and accumulator) can be inside a single sequential process in VHDL instead of each having their own. Then we can put all the combinatorial logic together in a single section of code and save ourselves about 40 lines. Still not great, but getting better. 

Next up, we have to run this code through simulation. This is where I give a shout-out to Emacs, which while often being a pain in the ass, has one of the best VHDL modes out there that I know about. One of the great things it can do is allow you to is a lot of creation of objects based on a port definition. Select a port map and copy it using the VHDL port copy command, and then you can paste that port as an entity, instance, signals, initialization, or even the entire test bench. This is pretty helpful for such a verbose language. 

The test in this case can pretty easy, we just need to provide a clock, and set enable active and then wait for results_valid to go high. This is a pretty crappy test, but since we don't know what result we're expecting going into the problem solving that's all that we have available to us with the entity definition we used. A quick look at the waveform at the startup to make sure everything is working... 

we can see the modulus counters cycling here, the accumulate enable signals going active, and the results getting summed. 

we can see the modulus counters cycling here, the accumulate enable signals going active, and the results getting summed. 

and voila, we have some hardware that can solve the first problem from Project Euler, for any value of n that we provide in the generic parameter we pass in. 

How's this compare to software implementations? Here's what a friend wrote for me when I asked him to solve the same problem in C++

int sum(0);
for (int i = 0; i < 1000; ++i) {
  if ((!(i % 3)) || (!(i % 5))) sum += i;
} 
return sum;

So, 5 lines of code in what I took about 40 lines to do. That hurts some. You can also see he tried the same dumb brute force algorithm as I did, looping through all the numbers, checking to see if the number was a multiple of 3 or 5, and then summing it if so. And since he did that, when we timed his code being run in a processor, vs my code running in an FPGA my code ran about twice as fast as his, around 1.3 microseconds vs his taking 2.6 microseconds.