Question for PCB algorithms

Go To Last Post
18 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hello, everyone!

I have a course at university for ICs routing and placement algorithms. That said, our professor wants us to analyze one of the algorithms studied, so I asked him if I could focus my study at PCBs routing and placement (I find it more practical for me).

What algorithm do you suggest me? I'm more interested in something it could come handy for my layouts (it could be placement, routing or both if I have enough free time at christmas, for the moment my placement stinks).

Thanks for reading!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

SirLalala wrote:
our professor wants us to analyze one of the algorithms studied ... What algorithm do you suggest me?
We can't know which algorithms you have studied, so how should we be able to suggest one from a list we don't know?

Stealing Proteus doesn't make you an engineer.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ArnoldB the algorithms we studied are for ICs. I want you to suggest me one you know and use when you manually make pcbs :)

Sorry for my bad explanation :D

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here's my routing algorithm:
1. Start at point A
2. Route best way to point B
3. If more wires, goto 1
Hasn't failed yet.

Seriously, I don't think people are pondering the inner details of PCB routing algorithms.

/Jesper
http://www.yampp.com
The quick black AVR jumped over the lazy PIC.
What boots up, must come down.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

jesper yeah that's what I do. But commercial programs have to use something for autorouting don't they? Certainly most of times that something generates garbage (at least on eagle I haven't used orcad for pcb layout).

I didn't want to start searching for "pcb routing algorithms" on google before asking here if someone uses something in particular.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

But you asked for

SirLalala wrote:
manually make pcbs
The algorithm is as jesper described: Use brain. And when having a problem: Think harder.

Stealing Proteus doesn't make you an engineer.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Steps I use for single-sided PCB lay-out:
1. Dimension PCB
2. Hand-place mounting holes
3. Hand-place GND traces around outer edge of PCB
4. Hand place components, looking for trace routing patterns that ease single-sided layout
5. Hand-route signal traces that support most logical single-sided lay-out
6. Hand-route VCC & GND
7. Hand-route remainder of traces according to their best fit
8. Rip & re-route, repeating step 4 through step 7 until all circuit nodes are complete

PCB lay-out is all about looking ahead, and being able to recognize patterns. It also entails some knowledge of circuit operation and the consequences of how traces are laid down and terminated on the PCB.

Knowing how analog and digital power and signal lines interact, and how to properly isolate their effects from each other is very helpful, and hard to teach a computer to do.

Knowing some RF and hi-speed digital signal theory tends to be a benefit, as well.

Many of my single-sided PCBs will have cleaner analog signals and better looking digital signals, then do many double-sided PCB layouts that have GND planes.

You can avoid reality, for a while.  But you can't avoid the consequences of reality! - C.W. Livingston

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

But commercial programs have to use something for autorouting don't they?

OK, so ask a commercial PCB routing program vendor if you can have their algorithm. 8)

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You could have a look here: http://www.wand.net.nz/~amb33/to...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
The algorithm is as jesper described: Use brain. And when having a problem: Think harder.

But Jesper leaves out the hair pulling, fit throwing and colorful language steps :oops:

If you don't know my whole story, keep your mouth shut.

If you know my whole story, you're an accomplice. Keep your mouth shut. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You might find something about autorouting algorithms in IEEE journals or ACM publications. Certainly, they have been the subject of academic study and those are the sorts of places where it might be published.

If you don't have access to these, well, you don't have access!

Jim

 

Until Black Lives Matter, we do not have "All Lives Matter"!

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Ok I found something for start:
http://lyle.smu.edu/~mitch/ftp_dir/pubs/cnf.ps

ka7ehk: I'll try at my university's library maybe I can find an article from ieee journals.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You might also do a search on the "Greedy Router" algorithm. That started out at MIT (if I recall correctly) back in the early 80's. The "Greedy Router" served as a benchmark partly because it was easy to implement.

Also look up the term "channel router".

I worked in IC CAD back at HP in the early 80's. I remember a co-worker at HP started working on channel routers in the mid-80s saying, "We'll be finished in 6 months." Three years later he said, "You know, routers are hard!"

Stu

Engineering seems to boil down to: Cheap. Fast. Good. Choose two. Sometimes choose only one.

Newbie? Be sure to read the thread Newbie? Start here!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Have you looked in any of the open-source pcb programs? gEDA and KiCAD come to mind.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yeees Stu!

Greedy algorithm is one of the proposed ones, (If I remember right it allowed doglegs on channel routing or something like that). Well then I'll probably do this one, since I can use it for something practical in extreme cases.

Thank you!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

In case someone might be interested I found an interesting book for this subject: Naveed Sherwani, "Algorithms for VLSI Physical Design Automation".

Cheers!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

There are a number of mathematical algorithms for auto-router PCB software, but most vendors keep the algorithms they use "close to the vest". Some work better than others for different PCB layouts and topologies. Most autorouters have settings in which one can set the preferred/defined direction or orientation of tracks on various layers. But, the algorithms themselves are often either shape/geometry based or employ other mathematical set/intersection analyses with resource optimization.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

One thing I'd add to Carl's list is to route the shortest nets first, after routing the critical nets. I don't remember where I saw this, but it seems to work.

I've always wondered why auto-routers don't move components. I remember reading a long time ago that the Bartels router was going to include this, but it's never been implemented. Bartels has some interesting notes on routing strategies:

http://www.bartels.de/baedoc/baear_en.htm

The Bartels auto-router was originally supplied with Pulsonix, but they switched to Electra when it became available.

Leon

Leon Heller G1HSM