Q: Algorithms used for component placement to minimize crossing/trace length

[m.elsayed]

Hello,

A quick background, I am trying to design an LED matrix using Charlieplexing and looking for an approach where I can scale the design to any number of inputs.

My first thought was to try to brute-force the layout, but the complexity is (N+2)! which is not practical.

My guess is that graph theory can give a solution for this, by modeling the circuit as a directed graph with inputs as nodes and tracks as nodes, but I have no idea how to approach this.

I know that there are already algorithms for routing but I was not able to find anything on component placement.

So my question is, what are the algorithms that can be used for component placement so it would minimize tracks crossings(vias)?
And is there any pointers or books that I can read that addresses this?

Thanks.

[Infraviolet]

My suspicion is that if such an algorithm existed, in any reasnably efficient form, we'd already have auto-routers which could select part positions for you as well as routing traces between them.

Fortunately for you it looks like you've got a lot of space to play with for wiggling traces round one another and having vias, it might not be the optimum choice, but on a board like this it won't be difficult to fit.

If keeping the back side of the board as clear as possible (for fairly solid ground plane, or for placing components and traces not involved in the charliplexing layout) matters for you, I'd suggest the following two tips:
1. only go to the bottom layer for traces running vertically, traces which run horizontally should stay on the top layer. You could do this the other way round, but the trick is to reserve the back layer only for traces going in one of the directions, and only put traces of thatdirection on the back when routing on top isn't possible.
2. when you need to swap the "order" (which is furthest left, next left, middle, right...) of a series of traces, have them undergo a 90 degree cornering in the area where you put your vias, you can often get a whole swarm of traces to swap order, in many diferent mappings using just one via per trace (some traces not needing a via at all) or two vias if all traces afterwards are to be back on the top layer.

[Doctorandus_P]

I simply avoid charlieplexing. It's just too much trouble (both PCB layout and software) for not enough gain (saving a few I/O pins). A rectangular matrix is easy to route on a dual layer PCB, and easy to control in software. For adding I/O pins if needed, the 74hc595 or 74ls138 or a slightly bigger uC are among the possibilities.