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