RTL Viewer Update

State of the Viewer

Things are progressing slightly well with wxDebuggy, it now does a half-decent job of drawing some verilog modules and the wiring between them -- and all this while limiting the number of crossovers!

As mentioned before, I wasn't too happy with the wire-crossing reduction results when using a straight version of the Sugiyama et al algorithm. The current revision of the RTL Viewer improves the crossover reduction using two techniques:

1. The layer reordering stage of the Sugiyama et al algorithm was tweaked using ideas found here (SFvHM09). With this tweak, the layout algorithm now knows that modules have ports and that these ports are in a fixed order.

2. The orthogonal wire routing algorithm use 'Greedy Assign' to place the vertical line segments of each wire to a unique track between the layers. This idea comes from (EGB04).

Stuff to Fix for 'Dishwater' Tag

• Y co-ordinate assignment of the modules should be improved.
• Long dummy edges should be kept straight.
• Clock/reset-like signals that go to multiple modules in multiple layers need to be handled better.
• Feedback wires are not drawn all that well.

Misc worries

• RTL parser is very slow. The files I test on have basic RTL and wiring, and there are only about 12 of them, but it takes around 3 seconds for my desktop to parse them and build the necessary data structures.
• Greedy assign may not be enough for more involved circuits - I may need to add the 'Sifting' bit too.

References

• SFvHM09 Port Constraints in Hierarchical Layout of Data Flow Diagrams
• EGB04 Orthogonal Circuit Visualization Improved by Merging the Placement and Routing Phases (no link)

Drawing Circuit Diagrams - Update

Well, after a bit of wrangling with the EGB layout algorithm - things are working out!



There are still a few crossovers on the outputs of U8 & U9 which I haven't got to the bottom of yet...

Animation

To help get to the bottom of such things, I've implemented a bit of animation to show me how the layout is progressing at each step. Using python's generators to unroll the main layout loop was the key here. First, the circuit data structure is drawn, then after a small delay the .next() is called on the generator, and the circuit redrawn. This continues until the generator is spent. Pretty nifty if I do say so myself...

Improvements

At the minute, the layout algorithm is sweeping from the inputs of the circuit to the outputs. I'm worried that this won't be optimum for untangling all types of circuits. So, once I debug my EGB algorithm implementation, I'll experiment with the following to see what gives the best results:

• inputs to outputs


• outputs to inputs


• inputs to outputs to inputs

I'm also concerned about the initial state of the circuit data structures. Maybe I've giving the algorithm too easy of a time. The instantiations in the circuit data structure are more or less in the order that they are in the verilog file. Maybe I should mix-up the instantiation order in the verilog files. Or maybe have a switch to randomize the instantiation orders in the data structure...

I've also to trawl/profile the code and look for optimizations...

Next Steps

After playing around with the layout algorithm, I think I'll add a final stage to tidy up the drawing of the nets. Once I get something half-pretty going, I'll concentrate on parsing a bigger subset of the verilog language.

Drawing Circuit Diagrams

If you've been browsing some of my previous posts, you'll know that I'm interested in writing an open source tool to generate schematics from some Verilog RTL. And you'll also probably remember that I was trying to come up with the layout & routing algorithms for the schematics myself.
I'm also failing miserably, you may remember. This is as far as I got with the genetic algorithm layout before I decided to abandon it on speed and reproducability grounds:


So, I've honoured the pragmatic promise I made to myself, and I've turned to the interwebs for help.

Vocabulary

Drawing automated pictures of relationships in Computer Science goes by the name of Graph Drawing, a branch of Graph Theory. According to this stuff, I'm looking to draw Layered Orthogonal Directed Graphs:

• 'Layered' from the fact that I can arrange the instances into columns. Sugiyama seems to be the main man when it comes to algorithms for this sort of graph.
  
• 'Orthogonal' because I want the nets to go in right-angles.
• 'Directed' because there's a flow in the drawing. For us EEs, this flow is left to right, but in graph theory it's usually top to bottom. So my problem would've been with the x-placement.

In graph theory, my RTL module instantiations are nodes and nets are edges.

Existing Code

The first thing I did with my new-found pragmatism was to look for open-sourced code I could rob use. Preferably this code would be a C/C++ library (for speed) with Python bindings (for handiness), but I'd settle for pure Python. I didn't find exactly what I was looking for; either there was a lack of examples and screenshots, no python bindings, or the library was closed source. That said, if I'm willing to learn SWIG to create python bindings, or I'm willing to create my own examples, there are a few libraries to investigate further:

• OGDF: C++
• networkx: Python
• igraph: Python binding of C library.

Some of the proprietary stuff could've been exactly what I need: tomsayer.com (sorry, this tries to resize your browser window) had a teaser of a circuit diagram, and yFiles had intrigingly-named ChannelEdgeRouter class.

Even if none of the above open source libraries end up suiting my project, at least I have the freedom to look at the code and study the algorithms they use when cooking my own.

Literature Search

Then I stuck a whole pile of terms into the search engine to see what turned up. I tried various combinations of terms including 'graph', 'drawing', 'routing', 'layout', 'channel', 'layered', '2d' etc. and added more as they turned up. Although I got some useful introductory slide decks from university courses, I did bang my head up against sites such as ieeexplore and springerlinks which expected me to pay for stuff.

The searching did throw up a pair of papers by Eschbach, Günther & Becker which seem promising. One of which, Orthogonal Circuit Visualization Improved by Merging the Placement and Routing Phases, especially so.

Homework

I think the next stage of my endeavour is to read the papers by EGB (hehe, Eternal Golden Braid) I mentioned above, and have a look into those graph drawing libraries, maybe igraph seems the most appealing at a first cut.

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...

BEDROOMNET: Subversion & Samba

As I mentioned on a previous post, one of the projects I have on the go is an RTL Visualiser. As I want this to be cross-platform, I suppose I had better test it on a few platforms. To this end, I set up a small local network where my mintLinux desktop could talk to my XP laptop. The idea was to host a Subversion repository on the desktop, where I'd be doing most of the development, and use a mix of Samba, Subversion and TortoiseSVN to get the XP laptop to access the repo.

Samba

Out of the box (and with a crossover cable) the desktop could read shared folders on the laptop, but the laptop couldn't see the desktop. So after installing Samba, running the Network Setup Wizard on the laptop and sharing a few folders on both machines, things were running well. I think I disabled the password stuff on Samba because I still haven't figured out how to add accounts - I don't need them anyway for this network. I'll poke about on it a bit more once I fork out for an internet connection.

Subversion

Getting this running was fairly easy too. First I installed Subversion on the desktop and set up a repository on an ext3 partition. Then I installed TortoiseSVN on the laptop - a SVN client program which hooks into Windows explorer and gives extra SVN command options when you right-click on a folder or file. After this, I easily checked out the SVN repo on the laptop and ran my RTL Visualiser (Version 0.1!) successfully on the laptop!

I couldn't check any changes in though. But after adding a user and a password to the repo's passwd file and enabling password authentication, I was soon checking stuff into the desktop repo from the laptop.

At the end of the day...

All in all I'm fairly happy with this setup, and it wasn't too difficult to set up after doing a bit of digging around in the Subversion docs.