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

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.

Projects

I've a few projects I'd like to do:

• USB Audio Interface
• for hooking up my guitar to my computer
• using those fancy PICs
• A darts scoring system
• Just to use those *HUGE* LEDs
• Would suite my mates' "Bar and Darts" room.

Projects in the works

• RTL visualiser
• Python and wxWidgets
• inspired by Nova's Debussy

Projects I've recently completed:

• Multi-Zone Lighting Controller for a friend's new gaff.
• PICs, keypads and high-voltages!