Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!rochester!pt.cs.cmu.edu!o.gp.cs.cmu.edu!hagerman
From: hagerman@ece.cmu.edu (John Hagerman)
Newsgroups: comp.lsi.cad
Subject: Re: Looking for references to a circuit-drawing program
Message-ID: <HAGERMAN.90Nov2130058@rx7.ece.cmu.edu>
Date: 2 Nov 90 18:00:58 GMT
References: <17@dhump.lakesys.COM> <9812@discus.technion.ac.il>
Sender: netnews@cs.cmu.edu (USENET News Group Software)
Organization: Carnegie Mellon University
Lines: 58
In-Reply-To: sergio@techunix.BITNET's message of 2 Nov 90 13:46:37 GMT

sergio@techunix.BITNET (Sergio Fogel) writes:

   From: sergio@techunix.BITNET (Sergio Fogel)
   Reply-To: sergio%techunix.bitnet@lilac.berkeley.edu (Sergio Fogel)

   I am looking for references to a program (or algorithms) that receives
   the description of a logic circuit (purely combinatorial, with no cycles,
   if this helps) and produces a drawing of the circuit. What I need is a
   drawing easy for humans to read.

I've used the following algorithm for circuits containing a few dozen
parts (restricted to rectangles with pins on left and right sides):

1: "Levelize" the components for placement in columns.  The simplest
   way to do this is to start from each input and traverse the netlist
   to find the shortest path to each component from an input.  More
   sophisticated and pleasing levelizations are easy to think of.

2: Order the components in each column for placement in rows.  Doing
   this well is difficult.  The goal is to minimize the number of nets
   that have to run vertically.  I have used a recursive mincut method
   that works OK.  A force-directed method might also be used.

3: Order the column of inputs (on the left) and the column of outputs
   (on the right) to minimize net crossings.

4: Draw the components in rows and columns, leaving space for routing
   tracks.  It's easiest to leave a fixed amount of space, although
   you will probably have to leave more space than you'd like to.  I
   draw pins on the components, and also for inputs and outputs.

5: Draw horizontal "stubs" from the pins of the components and the
   input and output pins.  The main task here is to assign nets to
   routing tracks running vertically between columns of components.
   The stubs "connect" pins to the routing tracks.

6: Draw horzontal routing segments between rows of components.  Again,
   nets are assigned to routing tracks running horizontally between
   rows of components.  The horizontal segments are used to connect
   the vertical routing tracks.

7: Draw vertical segments from the stubs to the horizontal segments.
   This completes the routing.

Another thing to deal with is crossing versus connected intersections
of segments.  It's easiest to just draw dots for connections and not
to worry about fancy symbolism for unconnected crossings.

Brute-force data structures and algorithms are sufficient (if you have
a reasonably fast machine).  For example, when assigning a net to a
horizontal track, I first compute the necessary extent, and then try
horizontal tracks until I find one that no other net is using on the
desired extent.  This is a gross method, since all nets are examined
for each track tried, but it's still fast enough.

- John
--
hagerman@ece.cmu.edu