Monday, December 10, 2007

RTL Visualiser

I'm in the midst of writing a Visualiser for Verilog RTL. It'll take in a Verilog description of a circuit design and produce the corresponding schematics. I hope it will be a joy to use, and produce 'nice' schematics.

Automatic Schematics

I've found that producing nice automatic schematics is difficult.

As for the App: so far, I have a very basic GUI running. It reads in and parses very basic verilog, builds the hierarchy tree and displays very basic schematics of very basic RTL, with very basic ratsnest type flightlines representing the block-to-block connections. It's all very basic. I've a nice recursive algorithm to place module instantiations in the x-axis, but y-axis placement is a whole other ball game. Y-Placement is not very basic. (At least as far as I can tell).

I've been fighting with the Y-Placement problem on-and-off for over 4 months, with no successful outcome. I want to see what I'm capable from a programming design point-of-view, so I have not yet consulted the interweb on how to solve it.

Genetic Algorithms

Another interest of mine is in Genetic Algorithms, so I threw one at it, to see if it could get some nice y-axis values to stick. The GA was s.l.o.w. (about a minute to place ~13 blocks - this is far from 'joy to use' territory), although there is room for some tuning to speed things up. And even though it successfully minimized net crossovers, it did not minimise them all. Also, things that should've been connected with a straight line weren't.

This led me to think about Genetic Algorithms and when it's a good idea to use them. But I never came to any conclusions, except to say that its probably a bad idea for this app. It's a bad idea for a few reasons.

First of all, there's the speed issue. I'm not convinced that even if I farmed the GA out to a 'C' routine, that I'd get through enough genotypes and generations in a GUI-friendly timeframe to get a nice schematic. And since the length of the genome depends directly on the number of things I have to find a y-axis number for, the GA slows down exponentially as this size increases. With the added complication of having to find heuristics to determine what population size and how many generations to run the GA for per genome size, it all just gets too much to deal with.

Another issue with running a GA here is that there's no guarantee that you'll always hit a genome with 'maximum' fitness (ie no crossovers if there needn't be, etc). And due to the nature of the algorithm, you can't get consistent schematics for the same RTL for each GA run if you can't consistently hit the fitness maxima.

The fitness functions used for the GA seems to take up the most programming time. And, how in hell do you write a fitness function for 'nice schematics'? To produce nice schematics, I think it's necessary to minimize net crossovers and ensure that modules are not drawn over the top of each other. It also seems to be important to minimize the gradient (sum of the gradients) of the connections. I have included these measures in the fitness function, and have even tried tweaking the weighting given to each, but all to not much avail.

So?

So I've gone back to basics, and am going to try to draw simple 2 & 3 gate circuits to see if I can get a handle on automatic schematics. Wish me luck...

No comments: