Re: gEDA-user: Need cool first application for gdatabase

[John Griessen <john_g@cibolo.com>]

On Wed, 2003-11-05 at 15:41, Bill Cox wrote:

>  It would help a lot if 
> you or anyone on this group could suggest some placement algorithms for 
> schematics. 
> 
> The goals for placement of schematics are  
>   Inputs are on the left, outputs on the right. 

>  Instances can be placed from 
> the right side to the left in columns based on max levels of logic to an 
> output.  

[jg]After placing by counting levels leading to an output, discover
the number of inputs to each instance and the angle that "fly lines" [1.]  
enter inputs.   Input angle [2.] is only available after an initial placement 
on a "printable drawable layout".   Large input angle is an indicator of bad 
readability, so then rank the instances with a score like 
input1 * input-angle1-degrees + input2 * input-angle2-degrees  
and so on for all inputs of each instance.  That could be a first cut 
for a readability rank.  For the above ranking number, higher is worse.

Without doing an iterative annealing approach, remove the worst problems 
first, then do one neatening that will not disturb the previous improvement.   
The worst readability problem would be the longest logic chain that 
also has worst readability score.   

How long the logic chains are per printed page will depend on how the design 
is partitioned into pages!   That is likely a hard algorithm, but is first to consider.  
Designers would often override a quick-scripted algorithm created partitioning to 
make some sense out of a design, so maybe we just skip that part?  For now 
at least, I skip that problem.  Perhaps an autogenerator like we are talking can be used
as first cut to partition by human powered processing, then redo each of those for
a decent generated schematic.

Take the identified worst  readability problem longest logic chain and
compare it to the longest logic chain placed now.   IF the longest one
placed now is longer or more branched and interconnected with other
logic than the bad readability chain, leave it and its branches in
place, strip all the rest out, lay down the unreadable chain
horizontally right to left and recalc the fist cut readability stats and
also mark these two chains as now frozen and their area as taken. 

Next move any short (3 levels to page edge or 2 levels to page edge)
branches to use nearby untaken area near horizontally.  Freeze them. 
Recalc the fist cut readability stats.

Repeat all above until none left.

[1.] Fly lines are defined as the "future wires" that could be drawn
straight between outputs and inputs so they cross over everything and
some could lie on top of each other. 

[2.] Input angle is defined as the angle of the fly line from an
instance output to an instance input in absolute value degrees from left
entry, (horizontal on a printed page or drawn video screen).   Abs value
means angle up or down has same number for ranking purpose.  

>  I'll need an algorithm to reduce overall crossings by ordering 
> instances within columns.  Once the ordering of instances within a 
> column is determined, I'll need an algorithm to minimize overall 
> wire length by adjusting the Y coordinates of instances, but without 
> swapping positions of instances within a column.  Also, it needs to be 
> very fast (not simulated annealing).
> 

-- 
John Griessen    Cibolo Design       Austin Texas
EE good at IR systems, power supplies, logic design, A2D D2A, digital amps, 
mechatronics, SiGe and CMOS layout, MEMS/mech/electronic/photonic 
modeling, charge pump PV/battery/fuel cell power converters, more...