Things I would have told myself before building an autorouter

396 点作者 seveibar大约 2 个月前

28 条评论

ChrisGammell大约 2 个月前

I'm generally in the "never trust the autorouter" camp (and by extension "never trust the bevy of AI tools entering the space"), but it's undeniable there are some big opportunities in the eCAD space to speed up some aspects of layout. I'm probably more likely to use co-creation tools, rather than full auto tools, simply because I rely heavily on iteration. Many times when starting a design my placements aren't set and that has a huge impact on routing. I didn't see on your page whether placement was part of your algorithm. I already rely on tools like push and shove and occasionally auto complete.I'm always curious about people entering the space though. It is a small market, IMO. The tools are fractured, the existing players are lumbering behemoths, and the users are cranky zealots (you will have to pry KiCad out of my cold dead hands). I noted the step about the AR being written in JavaScript, which I have no real opinion on, but I'm curious about plans to plug into ecosystems (CAD vendors, OS tools) or try and draw people into another new ecosystem.

评论 #43501264 未加载

评论 #43506243 未加载

评论 #43501499 未加载

评论 #43503671 未加载

评论 #43503983 未加载

GistNoesis大约 2 个月前

Point 8, the fast dismissal of Monte-Carlo method is a huge blunder.The point of Monte-Carlo method is that you can tradeoff accuracy for speed. The longer you run your algorithm the more accurate you get.But what's even more interesting is that we can often use the contrapositive : You can get shitty accurate result real fast.Instead of exploring all paths, you explore only one path picked at random.And that's where it shines : when you put it into the most imbricated loop of your algorithm.For example when you want to learn a neural network which autoroute. Typically you would have the outerloop which is updating the neural network parameter, and the inner-loop which is computing a path through the graph.When you use Monte-Carlo this inner-loop which control accuracy can be reduced to 1 iteration if everything is bias-less, you will have a slower outerloop due to higher variance but the machine learning should """theoretically""" learn.This is what allows you to build policies which intuitively always pick the right decision. Like in chess or go, you have some monte-carlo tree search variant like alpha-go-zero or alpha-chess-zero or alpha-router-zero, where even without the search part, the giant cache (encoded by the neural network parameters), once trained, can compute your best guess path in one pass through your neural network aka constant time (with a constant which can easily trade memory for speed by augmenting the number of parameters or training for longer).

评论 #43506536 未加载

评论 #43509077 未加载

评论 #43505886 未加载

Animats大约 2 个月前

That's a great discussion of autorouting. Then he ends with: "key piece to enable the “vibe-building” of electronics." OuchRouting itself is easy. It's when the router has to tear up stuff it already routed to fit new stuff in that things get complicated and the combinatorics start to get you.I miss the autorouter KiCAD used to have. It was taken out for iffy IP reasons (the author had worked for an autorouting company). Reaction to users who wanted it back were along the lines of "Real Men Don't Use Autorouters".[1][1] <a href="https://forum.kicad.info/t/autorouting-and-autoplacement/18569/8" rel="nofollow">https://forum.kicad.info/t/autorouting-and-autoplacement/185...</a>

评论 #43500882 未加载

评论 #43501599 未加载

n4r9大约 2 个月前

Article makes some important points - especially re visualisation and cache effects.Some quibbles or glossovers:> A recursive algorithm is a depth first search. Any loop that explores candidates/neighbors without sorting the candidates is a BFS.Not sure what to say about this. It's either wrong or I'm missing the intuition. Both DFS and BFS can either be written iteratively or recursively; the real difference is whether you pop your next candidate from the top or the bottom of the stack. Equivalently, whether you use a stack (FILO) or a queue (FIFO). That said, I took maths rather than CS so verify this for yourself.> It is simply the best foundation for any kind of informed search (not just for 2d grids!)A* is useful in pathfinding if you have some notion of easily-computed "distance" to your desired target and you're only running a few queries for any given graph. If you plan to run many queries on a mostly-static graph (like a road network) then you could be better off applying a pre-processing algorithm like contraction heirarchies. If you're optimising but don't know what target you're aiming for (e.g. Traveling Salesman) then using some other local search heuristic like 2-opt may be better.> The major difference between these [A* and BFS] is BFS explores all adjacent nodes, while A* prioritizes exploring nodes that are closer to the destination.This is definitely a difference. But it glosses over the biggest difference, which is that A* is a dynamic algorithm. That allows you to terminate early with confidence that you have found the shortest path. With BFS you may not be certain until you've searched the whole graph, which could be vast.

评论 #43505629 未加载

评论 #43508441 未加载

评论 #43509429 未加载

评论 #43504694 未加载

dkjaudyeqooe大约 2 个月前

> The QuadTree and every general-purpose tree data structure are insanely slow. Trees are not an informed representation of your data.> Any time you’re using a tree you’re ignoring an O(~1) hash algorithm for a more complicated O(log(N)) algorithmThis is incredibly misguided. The hashing approach is fine if your points are evenly distributed and you only really want to query an area relatively close to the fixed subdivisions you've chosen, otherwise your 0(1) is going to degenerate to O(n).Trees are an informed representation when you don't know how your data is distributed.Similar story for randomized algorithms. What happens when your search space is many trillions of items or possibilities? Or there are no heuristics to be had? If you can't brute force it and you can't use a clever algorithm then randomized algorithms are a savior.Maybe these aren't needed for this specific application, but best to not make sweeping statements.

评论 #43505198 未加载

评论 #43506333 未加载

MrLeap大约 2 个月前

Almost everything matches my gamedev heuristics. I even have empathy for choosing JS. I'm making a game modding framework right now that operates on a lispy kind of s-expressions. Optimizing to accelerate creative iteration time > *, I've found.A*, Lee's algorithm and the like are all cool. It's criminal to write any kind of floodfill without having an accompanying visualization, you're squandering so much dopamine.This article has me wondering if all the gamedev things I *didn't* read about but are adjacent have utility in this kind of thing. I can't be the first person to think a boids router would be pretty fun. More seriously, I bet jumpflooding signed distance fields would provide you a lot of power.Everything about spatial hashing in particular matches my experience. Haven't found many occurences in almost 2 decades where any of the tree structures are worth the time. One notable exception. The lovecraftian text editor I made uses quite a lot of trie's for reactivity things. Nice way to compress 45,000 words into a compact state machine for event handling.

评论 #43508075 未加载

评论 #43508626 未加载

amiga386大约 2 个月前

> 95% of your focus should be on reducing the number of iterations. This is why language doesn’t matter.And then once you've used the playful, expressive (interpreted, abstract, slow) language you enjoy using, to develop an excellent, performant algorithm... if performance still matters, write the same thing again in a performant, low-level language, and perhaps even write architecture-specific assembly.There's a reason numpy, pandas, OpenCV, TensorFlow aren't written in pure Python, but instead let Python tell them to do things they've implemented in high performance C++/assembly/CUDA, etc.No matter how proud the authors would be of exploring a problem space and coming up with an efficient algorithm (and blogging about it), I doubt they'd be popular numerical computing libraries if they insisted on it being written in pure Python, or Javascript.While this is a fun blog post, I don't think it'd have the same takeaways if the author's algorithmic insights got a pure-Javascript HEVC encoder down from 1 day per frame to 3 hours per frame...

knodi123大约 2 个月前

Man, look at all those keywords I remember from college. I wish I got to use fancy well-known algorithms. Instead all I'm doing is building UI components and REST APIs to present elasticsearch results. All the fun stuff is buried in black boxes.

评论 #43500786 未加载

评论 #43502418 未加载

nine_k大约 2 个月前

This is great. As someone not working directly on 2D / 3D space problems, my biggest take-away is the value of visualizing things. Humans are really good at grasping and analyzing pictures. Another is the idea to use a stochastic or brute-force method to understand the shape of the problem, so to say, and choose a better method based on that, not from a theoretic understanding alone.

aranchelk大约 2 个月前

> 2. Implementation Language doesn’t matter> I’m controversially writing our autorouter in Javascript. This is the first thing people call out, but it’s not as unreasonable as you might expect. Consider that when optimizing an algorithm, you’re basically looking at improving two things:> Lowering the number of iterations required (make the algorithm smart) Increasing the speed of each iterationIt may be true in this domain, I wouldn’t know, but applied to software engineering in general IMO it would be a massively incorrect assumption to say choice of language doesn’t affect speed and needed number of iterations.

评论 #43502143 未加载

评论 #43503857 未加载

kayson大约 2 个月前

I want to love hardware as code. I really do. I love infrastructure as code, devops as codezyou nake it. But I just don't think it's ever going to happen. At least not fully. Something about it to me just has to be graphical. Maybe it's the information density, or the fact that circuits are graphs / networks, or maybe it's just habit.On the topic of autorouters, the post doesn't really go into why there are no open source data sets and why there aren't many open source tools. It's probably no surprise but there's a TON of money in it. The author mentions iphones and 10s of thousands of routes. That's nothing. Modern ICs have billions of transistors and billions of routes with an insanely complicated rule set governing pitch, spacing, jobs, etc. Not to mention the entire time you have to make sure the parasitic resistance and capacitance from the routing doesn't break the timing assumptions.Cadence and Synopsys probably put billions yearly into R&D and I bet a big chunk goes into "Place & Route". I've heard that licenses for their tools run into the miions of dollars per head per year.

评论 #43504415 未加载

shadowgovt大约 2 个月前

I love this article. Two things I'd consider highlighting:1. Autrouting in particular is a problem well-suited to visualization and not all problems are. it's fundamentally about real things in real space (bonus: they're mostly constrained to a 2D plane, which makes them easy to visualize on a computer screen). A lot of hard and interesting problems don't match that reality and so aren't as amenable to visualization.(... but the general advice, "look for opportunities to visualize," stands. Your eyes and brain are very fast matchers for a broad variety of patterns in a way a computer isn't without a lot of special-purpose, tuned software).2. JavaScript, between the language itself (specifically the ability to reflect data structures at runtime) and the ecosystem around it, is very amenable to visualization. In that way specifically, it was a strong choice for this problem domain. Imagine how much work you'd be taking on if you decided to "just bang out a quick visualization" for an arbitrary piece of the algorithm in C++, or Rust.

CamouflagedKiwi大约 2 个月前

The third point - "Spatial Hash Indexing > Tree Data Structures" - is probably great in this domain, but shouldn't necessarily be taken as global truth. I've optimised a system significantly before by going from a grid to a tree - because if your points are significantly unevenly distributed then you effectively have a bad hash function, and it devolves to O(n) performance.

评论 #43507556 未加载

phendrenad2大约 2 个月前

I wonder how autorouters encode all of the various electronics rules. Such as min distance between traces, max angle of a turn, how to snap multiple connections together so they look good, etc.

评论 #43501339 未加载

Lerc大约 2 个月前

I am a strong proponent of visualisations. I also have a tendency to write things in JavaScript that others might choose a different language. I'm now wondering if those things are related. Having the browser to provide an interface can make that a lot easier. Recently I have been doing a fair bit of transformer and NNet stuff so consequently Python. I have found it a bit of a step back when it comes to visualisations. It's easy to used canned techniques to plot data, but not as easy to knock up a custom interactive visualisation.Hmm, I wonder what python raylib is like, that might be the ticket.

评论 #43503822 未加载

评论 #43503043 未加载

评论 #43502073 未加载

bArray大约 2 个月前

Does anybody have materials regarding how you would go about writing an autorouter? I was thinking to maybe use something like this [0] as a starting point?I have a few major nags about current autorouters:1. No way to prioritise connections.2. Handling of differential pairs or buses is terrible.3. Does not use best practices for high-speed signal lines.4. No way to add arbitrary rules to the autorouting process, i.e. block a trace from going through an area. For example, maybe you don't want a power trace being autorouted under your IMU, but some low voltage signals are fine.I've use freerouting [1] in the past but it has a somewhat difficult time of being maintained. Freerouting seems to really struggle with larger designs, it seems to be greedily routing traces and spends ages trying to fix those early placed traces.[0] <a href="https://github.com/vygr/Python-PCB" rel="nofollow">https://github.com/vygr/Python-PCB</a>[1] <a href="https://github.com/freerouting/freerouting" rel="nofollow">https://github.com/freerouting/freerouting</a>

hyperbrainer大约 2 个月前

> > A recursive algorithm is a depth first search. Any loop that explores candidates/neighbors without sorting the candidates is a BFS.BFS is also a recursive search. Even in the case of non-recursive search, the only difference is whether you use a queue or stack.Apart from that, great article.

评论 #43503990 未加载

kalaksi大约 2 个月前

> 2. Implementation Language doesn’t matterI'm not sure how performant modern day JS is but aren't you still leaving a lot of performance improvements on the table? Sure, algorithm may matter more but who says you can't use the same algorithm.

teleforce大约 1 个月前

>I believe that solving autorouting will be a massive unlock for physical-world innovation and is a key piece to enable the “vibe-building” of electronics.I strongly believe that the CAD world including EDA is at the verge of disruption by an AI or more correctly Machine Intelligence (Constraint Programming - CP to be exact) very similar to how LLM disrupting the Chatbot technology [1],[2].The path to this is most probably by solving the autorouting mechanism with CP, a deterministic logic, optimization and constraint programming machine based intelligence [3], [4], [5],[6].Fun facts, the modern founder of logic, optimization, and constraint programming is George Boole, the grandfather of Geoffrey Everest Hinton, the "Godfather of AI" and "Godfather of Deep Learning".[1] Most AI value will come from broad automation, not from R & D (313 comments):<a href="https://news.ycombinator.com/item?id=43447616">https://news.ycombinator.com/item?id=43447616</a>[2] Diagrams AI can, and cannot, generate (68 comments):<a href="https://news.ycombinator.com/item?id=43398434">https://news.ycombinator.com/item?id=43398434</a>[3] Constraint programming:<a href="https://en.wikipedia.org/wiki/Constraint_programming" rel="nofollow">https://en.wikipedia.org/wiki/Constraint_programming</a>[4] Logic, Optimization, and Constraint Programming: A Fruitful Collaboration - John Hooker - CMU (2023) [video]:<a href="https://www.youtube.com/live/TknN8fCQvRk" rel="nofollow">https://www.youtube.com/live/TknN8fCQvRk</a>[5] "We Really Don't Know How to Compute!" - Gerald Sussman - MIT (2011) [video]:<a href="https://youtube.com/watch?v=HB5TrK7A4pI" rel="nofollow">https://youtube.com/watch?v=HB5TrK7A4pI</a>[6] High-Quality Ultra-Compact Grid Layout of Grouped Networks [PDF]:<a href="https://ialab.it.monash.edu/~dwyer/papers/gridlayout2015.pdf" rel="nofollow">https://ialab.it.monash.edu/~dwyer/papers/gridlayout2015.pdf</a>

djmips大约 2 个月前

This blog post sings to me. Well done. I remember the time a colleague effectively used A* as the optimizer for the AI's plans in 2 player game. Indeed it really can be purposed for a lot of different things!

xg15大约 2 个月前

I want to thank this guy for the "avoid Monte Carlo" point and the big "no randomness" image.I feel people are getting way to comfortable throwing randomness at things, pretending it's perfectly fine or even beneficial because you can reason over the probability distributions and then shrugging their shoulders when the results have unpredictable and impossible to debug edge case behavior.We already have enough unpredictable factors in a program, I feel we don't have to purposefully add even more of them.

评论 #43506503 未加载

tobyhinloopen大约 2 个月前

If you're navigating on a 2D grid, Jump Point Search "Plus" can be extremely fast:<a href="https://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter14_JPS_Plus_An_Extreme_A_Star_Speed_Optimization_for_Static_Uniform_Cost_Grids.pdf" rel="nofollow">https://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter14_JP...</a>

fooblaster大约 2 个月前

I find it very amusing how essentially all digital vlsi has been autorouted for years, but no one can seemingly solve the board level PCB autorouting problem. I get that one is digital, and the other can be essentially anything, but the difference in practice is a strange juxtaposition.

swayvil大约 2 个月前

Don't diss monte carlo.10000000000 random guesses can be way faster than a clever calculation.And maybe there is no clever calculation.

评论 #43504685 未加载

weinzierl大约 2 个月前

"Know A* like the back of your hand, use it everywhere"Are state-of-the-art autorouters still based on A*?From what I remember A* was used in the 80s before Specctra introduced a cost based push and shove capable approach in the mid 90s.A* being what it is, is probably still a part of contemporary solutions, but I am surprised about the emphasis it got in the post.*

thenthenthen大约 2 个月前

Looking forward! Feature request: would it be possible to add obfuscation? This is not a solution to my issue ( it is more social), but could be… interesting

sitkack大约 2 个月前

What a wonderfully written post! Much respect.

jofla_net大约 2 个月前

Wish i had read #3 a few years ago before doing one of those 'interview' 'projects'.