This will be the first problem I solve in MyHDL before coming up with a hardware solution in VHDL ahead of time. I'm also excited about this problem because it's clear from the description that division and potentially square roots will be necessary operations in the algorithm, and those are not things often avoided like the plague by hardware designers.
MyHDL is an open source python package for hardware design. It's biggest apparent benefit over other languages is that with it you can use python for the entire process of designing a chip, from hardware design, to unit test, to tool control (as a tcl replacement), to other glue logic to get the design through synthesis and place and route tools. The manual and tutorial the developers have written is pretty good, and worth reading through if you're interested. The designers of the language say that it might be an easier language to start off with than VHDL or Verilog, but that sounds so much like what the C - like language guys say that it's hard for me to believe that. Since it's an addition to python though, there are a lot of resources out there, probably more than VHDL or verilog though they won't be hardware design specific which can also be an issue. Python has modern methodologies in mind already, and the tools to deal with them which can be a nice change of pace from some of the older processes hardware design can seem mired in. Like other go between languages, the tools have to convert to VHDL or Verilog prior to synthesis and place and route.
The package installs pretty easily with
pip install myhdl
on my linux box, though I do remember it being a little more involved installing it in cygwin. We're going to start out with the same project euler problem set, starting off with problem 1:
Find the sum of all the multiples of 3 or 5 below 1000
Since I've solved the problem before, I have access to the forums where people post their solutions to the problem, so I thought it'd be fun to try taking a pythonic solution and see if I can get it into hardware with the myHDL package (spoiler alert, I don't think it's going to work). Here's the function that I'm going to use in unittest that I'm going to try to massage into turning into compilable hardware
To model concurrency in python, MyHDL makes heavy use of generators in the same way VHDL uses processes or Verilog uses always blocks, with the yield statement in python acting as the sensitivity list. Here's another unittest function: this describes the generator that creates the clk.
the use of these myHDL specific decorators (always(), always_comb(), always_seq()) seems pretty familiar coming from VHDL, though only dabbling in python I'm not sure how familiar they are to those coming at it solely from a software background.
Because we're doing hardware design, we need some help with hardware oriented objects. MyHDL gives us Signals as the objects to connect different concurrently running generators, and intbv (integer bit vector) for support for indexing and slicing particular bits out of a single object and being more hardware cognizant with the sizes of our signals and registers. We're going to use the same top level structure as the other problems, with clk and reset for synchronous design going in, enable to start processing, and results and results_valid as outputs.
So in our unit test, we'll have to define these inputs and outputs as Signal objects:
So we've got most of the unit test pasted in chunks above. Only a few things left to make it actually run a test, use the traceSignals function in myHDL to create a UUT instance so we can get a trace of the inputs and outputs to help with debugging, create an instance of the checkResult code, and pass that plus the clkgen to the myHDL simulation function. So next up we define the generator that runs this python code. We're going to do some bad practices and just copy the test function into a generator and give that a go. First pass will look like this:
And then run the unit test, and voila!
This is a little suspicious though, if we have the result in less than a clock cycle, we probably don't really generate any hardware that calculates the result. So we'll add a toVHDL function to see what the hardware output looks like.
So good news, and bad news. The good news is the python is convertible to synthesizable hardware. The bad news is this is definitely not the sort of algorithm implementation I was looking for -- the algorithm isn't implemented in hardware, it's calculated ahead of time and the hardware spits out the result. This is one of the issues in choosing problems from a site focussing on the algorithm to implement the problem instead of focussing on problems that hardware would be good at.
So we can modify the function to count by cycle instead of using the range function. And then we'll need to create our own summing registers to store those values. And finally, we run into a little bit of a hack figuring out when we're done counting -- knowing the problem we know that the threes counter will take the longest to get to the end. And we know it'll take an extra cycle for the threes accumulator to then sum up the end. Finally, because we are converting things to VHDL, MyHDL requires you to use convertable types with bitwidths defined. This isn't necessary for simulation only, but could certainly be a little confusing. Here's a pass trying to implement the 4 line pythonic solution in hardware convertable code.
We end up with 25 lines of code, and a little bit of hacking to get timing to work out just right. We could turn the fives and fifteens accumulators into independent functions to keep from repeating how the work, but in the end that doesn't save us any code since there's only two of them, and in conversion to VHDL makes even more separate processes.
One of the other take-aways from this first pass is the converted VHDL is surprisingly readable and editable. Other mechanized tools that do this sort of conversion have a pretty bad track record, but this uses the same signal and variable names used in python, uses function names as process names, and even will take comments that use the python DocString format and convert them over to VHDL comments.