9 ms·

Things I would have told myself before building an autorouter

396 points by seveibar 2y ago

knodi123 2y ago
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.
- seveibar 2y ago
  Algorithms are a lot more fun now that LLMs have all the geometric heuristics memorized. I think a lot of algorithms are just inescapable in game development, so if you're itching to make an algorithm making something like like a tower defense game has a lot of classic algorithms involved!
  - Animats 2y ago
    Right. There was a time when I had a well-worn copy of Knuth, vol. 1 at hand. No longer.
  - tlarkworthy 2y ago
    Llms do not have it memorized. Try asking it to calculate the signed angle between two signed planes. I gave up and told it to copy the unity implementation.
- mschuster91 2y ago
  The core problem is a severe mismatch between academic curricula and what the job market actually needs on one side and the fact that companies use "needs a college degree" as a proxy to weed out risk and bypass ADA/anti discrimination laws. Both are a massive drain on the economy. IMHO, at the very least the current CS degree needs to be split up - CS should be split into various smaller (and faster achievable) subdegrees - the fancy math stuff should be its own degree, possibly be fused with a new degree relating to AI, database and network theory should be its own degree, and frankly stuff like low-level assembler as well, and the "how do electronic components, NAND gates, boolean logic and whatnot work" moved off to electronics engineering. And what the market actually needs the most - people who can crank out CRUD app stuff - should be either its own degree if one insists that this needs academic knowledge, or be moved off to something like trades education. In parallel, the job requirements gatekeeping should be tackled by laws - companies must no longer be allowed to require degrees that have little to no impact on the actual job duties. It's forcing our children to waste years of their life and take on five to six figures worth of debt, all only for companies to be able to weed out people.
phendrenad2 2y ago
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.
- thrtythreeforty 2y ago
  As far as I know, the design rules are managed as net properties, and the typical auto router opinion of aesthetics is "lol." So a lot of effort that could be spent typing in rules and cleaning up aesthetics is often spent just routing the damn board manually.
Animats 2y ago
That's a great discussion of autorouting. Then he ends with: "key piece to enable the “vibe-building” of electronics." Ouch Routing 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] https://forum.kicad.info/t/autorouting-and-autoplacement/18569/8 https://forum.kicad.info/t/autorouting-and-autoplacement/185...
- seveibar 2y ago
  Haha I feel like the right reaction to "vibe-*" is to cringe. I cringe a little bit every time I see someone promoting a vibe-coded app at the moment, but I think back to how I got started in coding (I was constantly annoying people on old ActionScript forums to fix my code) and I see so much potential in people being able to get started quickly in any domain. I hope that our autorouter (and others that follow!) will similarly allow people to ship their first electronics without needing tons of guidance or formal education. That said a good autorouter should also be useful to professionals! So hopefully we help with that as well!
- bsder 2y ago
  I wish these folks well and hope that their autorouter gets folded into KiCad. However, as one of the cranky old people who don't really want to see KiCad expend any energy on autorouters, PCB autorouters are a pain in the ass that never work. We can look at VLSI autorouters to determine why that is. VLSI autorouters also were a pain in the ass that never worked. But what happened was that VLSI suddenly got lots of layers and you could dedicate a layer to routing vertically, a layer to routing horizontally, a layer to routing power and still have a couple of layers for global vertical interconnect, global horizontal interconnect, and global power. The fundamental problem with PCB autorouting is that PCBs have WAY more obstructions than VLSI chips do. First, components themselves are obstructions and choke points. Second, PCB vias almost always obstruct all the layers of the board while VLSI vias only obstruct the two layers being connected. Third, PCB vias tend to be bigger than your interconnect metal width. Fourth, the number of PCB layers in use is way smaller than the number of layers in VLSI--the most common numbers of layers are 4 layers (most projects--of which only 2 are really used for general routing), 2 layers (because of cost engineering--good luck autorouting these) and 6 (a tiny minority). It all adds up to PCB autorouting being a significantly more complicated job than VLSI autorouting.
swayvil 2y ago
Don't diss monte carlo. 10000000000 random guesses can be way faster than a clever calculation. And maybe there is no clever calculation.
- TheHideout 2y ago
  Agreed, if you aren't using Monte Carlo methods in your algorithms then your problem probably isn't hard enough, or your solutions are fragile to variance.
ChrisGammell 2y ago
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.
- seveibar 2y ago
  We will absolutely be supporting KiCad! Placement is something we have big plans for but I think it’s important to have a really fast, cache-friendly autorouter as a foundation (if you are cache friendly, moving components and trying different layouts is much much faster) Javascript is fairly portable now with many runtimes (some even quite small such as QuickJS or Proffor), so I anticipate people will be able to run locally and build their own ginormous cache :) I think everyone should be concerned about lockin and fragmenting ecosystems in EDA, but tscircuit and our autorouter are MIT-permissive technology (very rare in EDA) so we play nice (interoperable) with everyone.
  - _fizz_buzz_ 2y ago
    How are you planning to support kicad? Would it be using kicad's new IPC API? In principle it should be possible to create javascript bindings for the new protobuf interface.
    - seveibar 2y ago
      We are looking hard at the IPC interface or doing a plugin, but we will also support “uploading” kicad_sch/kicad_pcb to a browser (local-first, so not actually uploading)
nine_k 2y ago
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.
Lerc 2y ago
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.
- rocqua 2y ago
  This is why I use python with Jupyter notebooks. Though admittedly animations are quite arduous.
- misiek08 2y ago
  I'd love to see what is the easiest way, for a hardcore backend guy with completely dumb part of brain responsible for visuals, to quickly visualize things in JS. I would pay for a "d3/p5 tutorial".
  - seveibar 2y ago
    Author here. I would recommend booting up React Cosmos[1] and prompting Claude to "generate a react app that...". You can visualize inside of Claude then when you're finished, drop the output of Claude into React Cosmos as a file. This is great for prototyping algorithms and recording the progression. For example you might say "generate an interactive react app that implements a simple pathfinder that uses A* with a penalty for going near edges". You can also just drop in a paper or pseudo code of an algorithm you're ideating on. Here's an example how we use react cosmos for our autorouter[2] [1] https://reactcosmos.org/docs https://reactcosmos.org/docs [2] https://unraveller.vercel.app/?fixtureId=%7B%22path%22%3A%22examples%2Fend-to-end%2Fe2e3.fixture.tsx%22%7D https://unraveller.vercel.app/?fixtureId=%7B%22path%22%3A%22...
- WillAdams 2y ago
  Visualization is actually one of the reasons I've been successful with my current project (creating a 3D modeling library which uses 3D tool representations and movement as afforded by G-code to write out G-code or DXFs) --- the tool which makes it possible is: https://pythonscad.org/ https://pythonscad.org/ Being able to just plot something and see the algorithm on-screen has been an incredible benison. I'm hopeful OpenPythonSCAD will be merged into OpenSCAD presently.
MrLeap 2y ago
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.
- seveibar 2y ago
  It is a really fun idea to build a boids router (shelving that for a future article!) I wrote previously about recursive pattern autorouters which are really good at having small solution spaces (and therefore, easier to get conventional machine learning algorithms to predict). There are so many interesting unexplored areas in autorouting!! I hadn't heard of jumpflooding (for others: fast, parallel algorithm for approximating distance fields), that could definitely be interesting, thanks for the tip!
- shadowgovt 2y ago
  I think the trees were a lot more useful in the past when memory and caches were smaller (and I suspect they can still be useful for precomputation, though I'd have to sit down and benchmark fixed-grid-with-smart-sizing vs. tree). Trees are also amendable to recursive algorithms but the author has noted that they have reasons to choose iterative over recursive algorithms, so these pieces of advice synergize. (It is perhaps worth noting: broadly speaking, "recursive" vs. "non-recursive" is a bit of an artificial distinction. The real question is "does a pre-baked algorithm with rigid rules handle flow control, or do you?" If you care about performance a lot, you want the answer to be you, so having your run state abstracted away into an execution-environment-provided stack that you can't easily mutate weirdly at runtime begins to get in your way).
kayson 2y ago
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.
- leoedin 2y ago
  I had a play with the tscircuit CAD tool which they're writing this autorouter for. It's hardware-as-code, leveraging React. I love the concept of schematics-as-code. But layout-as-code is awful. Maybe AI tools will improve it enough - but unless there's a user friendly escape hatch which lets you tweak things with a mouse, it's a dead end. I've had the same problem with auto-generated wiring diagrams and flowcharts. Great in theory, but then the tool generates some ugly thing you can't make sense of and there's no way to change it. There's definitely tremendous potential for AI in electronic design. But I think the really complicated bit is component selection and library management - you have to somehow keep track of component availability, size and a range of parameters which are hidden on page 7 of a PDF datasheet. Not to mention separate PDF application notes and land patterns. Compared to all that, connecting up schematic lines and laying out a PCB is fairly straight forward.
  - seveibar 2y ago
    Love that you tried the tool and couldn't agree more. We think that new layout paradigms similar to flex and CSS grid need to be invented for circuit layout. This is an active area of research for us!
aranchelk 2y ago
> 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 iteration It 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.
- bigiain 2y ago
  I think there's a fair argument to be made that when you're chasing Big O algorithmic improvements, then the effective constant terms incurred by "faster or slower language execution" are premature optimisation. The difference between Rust or hardcoded assembler compared to Javascript or VisualBasic are pretty irrelevant if you're still trying to get your exponent or polynomial terms under control.
  - HdS84 2y ago
    Yep. Also, js is easy to iterate on - it's more lenient than rust or say c#. Especially if you are exploring thinks, that's a huge boon. Obviously, for the same algorithm, compiled languages will be slower. Does it matter? Maybe. But time to find this algorithm is also critical - and if js helps here, it's a good choice.
  - kalaksi 2y ago
    But what about afterwards? You move to a more performant language or just accept that you're now invested in JS?
    - andrewaylett 2y ago
      One or the other, probably — Facebook were sufficiently invested in PHP that they released a whole new VM for the language. In Python, one would relatively commonly extract the performance-critical sections into C (or, nowadays, Rust) and you could do the same with Node too. Or the JIT might be fast enough that it's not worthwhile.
sitkack 2y ago
What a wonderfully written post! Much respect.
djmips 2y ago
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!
weinzierl 2y ago
"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.*
kalaksi 2y ago
> 2. Implementation Language doesn’t matter I'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.
deleted 2y ago
[deleted]
n4r9 2y ago
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.
- deleted 2y ago
  [deleted]
- hansvm 2y ago
  > recursive == DFS The intuition there is that people tend to write algorithms recursively when they easily map to interactions with the top of the stack, since that's easier to express in most languages than bringing in an external stack to think about. Hence, if you see something recursive in the wild it likely looks more like DFS than BFS. As you point out, that isn't a hard rule.
- thequux 2y ago
  Indeed, BFS, DFS, and A* are the same algorithm just with a different data structure to track unexplored nodes. BFS uses a FIFO queue, DFS uses a LIFO stack, and A* uses a priority queue (generally a heap)
hyperbrainer 2y ago
> > 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.
- fire_lake 2y ago
  And even then, execution depends on your language and compiler. Write a recursive BFS in Haskell and it won’t blow up the stack.
  - hyperbrainer 2y ago
    Any language with decent TCO won't do that. Python is the only big language that I can think of that doesn't do it.
    - fire_lake 2y ago
      Guaranteed TCO is pretty rare unfortunately. Java, Go, JavaScript all lack it.
      - hyperbrainer 2y ago
        Actually, you are right.
tobyhinloopen 2y ago
If you're navigating on a 2D grid, Jump Point Search "Plus" can be extremely fast: https://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter14_JPS_Plus_An_Extreme_A_Star_Speed_Optimization_for_Static_Uniform_Cost_Grids.pdf https://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter14_JP...
jofla_net 2y ago
Wish i had read #3 a few years ago before doing one of those 'interview' 'projects'.
dkjaudyeqooe 2y ago
> 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)) algorithm This 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.
- rtpg 2y ago
  Measure measure measure measure. Each case is different. But more seriously I think tree based algos tend to be overhyped, and people get a bit absorbed into thinking about big-O behavior when the constant factors are super important even when you’re looking at hundreds of thousands of elements. Not to mention stuff like data locality. Like sometimes your computer will be faster at just looking in a seq scan rather than dealing with the bookkeeping of a fancier structure. Sometimes. I think a nicer argument overall is to build a tiny wrapper around your operations, build out what is easy, and then figure it out through measurements. Worst case you end up entirely rewriting your program to accommodate a different structure to try for better perf but in my experience rewriting entire files from scratch tends to get you a good number of improvements for free.
  - dkjaudyeqooe 2y ago
    Sequential scans are terribly underrated given today's architectures. If the datum is small and it's like 1000 elements max it's going to be hard to beat a simple scan of an array for speed and memory efficiency. But trees et al also make a lot of sense as a default. If you need the performance to scale in a roughly linear manner you need to be smart about it. This is what sinks a lot of software, usability wise.
GistNoesis 2y ago
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).
- ttyprintk 2y ago
  Yet the author mentioned simulated annealing, so was probably not even trying a neural net, since SA does not compute a gradient.
  - ttul 2y ago
    Simulated annealing has long been one of the classic metaheuristic methods applied to autorouting in circuit design. It was widely used in early research and some commercial tools because its probabilistic approach helps escape local minima in these NP‐hard problems. Today, while many modern autorouters in industry tend to favor faster or more specialized hybrid methods, simulated annealing remains a common benchmark in academic studies and research prototypes for routing and related tasks like floorplanning. Source: I once wrote a simulated annealer for VLSI wiring. It was cool.
xg15 2y ago
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.
- windward 2y ago
  Agreed. Adding a test that generates a random 32 bit int to your project is adding 4 billion tests to your project and only running one of them.
fooblaster 2y ago
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.
amiga386 2y ago
> 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...
bArray 2y ago
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] https://github.com/vygr/Python-PCB https://github.com/vygr/Python-PCB [1] https://github.com/freerouting/freerouting https://github.com/freerouting/freerouting
CamouflagedKiwi 2y ago
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.
- swiftcoder 2y ago
  Not to mention that most hashmap implementations for managed languages incur ~2 cache misses per lookup. I've had an awful lot of optimisation wins over the years just by ripping hash maps out of software that either didn't actually need arbitrary key->value lookups, or had datasets large enough that a sufficiently wide tree-like structure handily beat the hashmap
thenthenthen 2y ago
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
shadowgovt 2y ago
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.
deleted 2y ago
[deleted]
teleforce 2y ago
>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): https://news.ycombinator.com/item?id=43447616 https://news.ycombinator.com/item?id=43447616 [2] Diagrams AI can, and cannot, generate (68 comments): https://news.ycombinator.com/item?id=43398434 https://news.ycombinator.com/item?id=43398434 [3] Constraint programming: https://en.wikipedia.org/wiki/Constraint_programming https://en.wikipedia.org/wiki/Constraint_programming [4] Logic, Optimization, and Constraint Programming: A Fruitful Collaboration - John Hooker - CMU (2023) [video]: https://www.youtube.com/live/TknN8fCQvRk https://www.youtube.com/live/TknN8fCQvRk [5] "We Really Don't Know How to Compute!" - Gerald Sussman - MIT (2011) [video]: https://youtube.com/watch?v=HB5TrK7A4pI https://youtube.com/watch?v=HB5TrK7A4pI [6] High-Quality Ultra-Compact Grid Layout of Grouped Networks [PDF]: https://ialab.it.monash.edu/~dwyer/papers/gridlayout2015.pdf https://ialab.it.monash.edu/~dwyer/papers/gridlayout2015.pdf

396 points by seveibar 2y ago

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.

seveibar 2y ago
Algorithms are a lot more fun now that LLMs have all the geometric heuristics memorized. I think a lot of algorithms are just inescapable in game development, so if you're itching to make an algorithm making something like like a tower defense game has a lot of classic algorithms involved!
- Animats 2y ago
  Right. There was a time when I had a well-worn copy of Knuth, vol. 1 at hand. No longer.
- tlarkworthy 2y ago
  Llms do not have it memorized. Try asking it to calculate the signed angle between two signed planes. I gave up and told it to copy the unity implementation.
mschuster91 2y ago
The core problem is a severe mismatch between academic curricula and what the job market actually needs on one side and the fact that companies use "needs a college degree" as a proxy to weed out risk and bypass ADA/anti discrimination laws. Both are a massive drain on the economy. IMHO, at the very least the current CS degree needs to be split up - CS should be split into various smaller (and faster achievable) subdegrees - the fancy math stuff should be its own degree, possibly be fused with a new degree relating to AI, database and network theory should be its own degree, and frankly stuff like low-level assembler as well, and the "how do electronic components, NAND gates, boolean logic and whatnot work" moved off to electronics engineering. And what the market actually needs the most - people who can crank out CRUD app stuff - should be either its own degree if one insists that this needs academic knowledge, or be moved off to something like trades education. In parallel, the job requirements gatekeeping should be tackled by laws - companies must no longer be allowed to require degrees that have little to no impact on the actual job duties. It's forcing our children to waste years of their life and take on five to six figures worth of debt, all only for companies to be able to weed out people.

phendrenad2 2y ago

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.

thrtythreeforty 2y ago
As far as I know, the design rules are managed as net properties, and the typical auto router opinion of aesthetics is "lol." So a lot of effort that could be spent typing in rules and cleaning up aesthetics is often spent just routing the damn board manually.

Animats 2y ago

That's a great discussion of autorouting. Then he ends with: "key piece to enable the “vibe-building” of electronics." Ouch Routing 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] https://forum.kicad.info/t/autorouting-and-autoplacement/18569/8 https://forum.kicad.info/t/autorouting-and-autoplacement/185...

seveibar 2y ago
Haha I feel like the right reaction to "vibe-*" is to cringe. I cringe a little bit every time I see someone promoting a vibe-coded app at the moment, but I think back to how I got started in coding (I was constantly annoying people on old ActionScript forums to fix my code) and I see so much potential in people being able to get started quickly in any domain. I hope that our autorouter (and others that follow!) will similarly allow people to ship their first electronics without needing tons of guidance or formal education. That said a good autorouter should also be useful to professionals! So hopefully we help with that as well!
bsder 2y ago
I wish these folks well and hope that their autorouter gets folded into KiCad. However, as one of the cranky old people who don't really want to see KiCad expend any energy on autorouters, PCB autorouters are a pain in the ass that never work. We can look at VLSI autorouters to determine why that is. VLSI autorouters also were a pain in the ass that never worked. But what happened was that VLSI suddenly got lots of layers and you could dedicate a layer to routing vertically, a layer to routing horizontally, a layer to routing power and still have a couple of layers for global vertical interconnect, global horizontal interconnect, and global power. The fundamental problem with PCB autorouting is that PCBs have WAY more obstructions than VLSI chips do. First, components themselves are obstructions and choke points. Second, PCB vias almost always obstruct all the layers of the board while VLSI vias only obstruct the two layers being connected. Third, PCB vias tend to be bigger than your interconnect metal width. Fourth, the number of PCB layers in use is way smaller than the number of layers in VLSI--the most common numbers of layers are 4 layers (most projects--of which only 2 are really used for general routing), 2 layers (because of cost engineering--good luck autorouting these) and 6 (a tiny minority). It all adds up to PCB autorouting being a significantly more complicated job than VLSI autorouting.

swayvil 2y ago

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

TheHideout 2y ago
Agreed, if you aren't using Monte Carlo methods in your algorithms then your problem probably isn't hard enough, or your solutions are fragile to variance.

ChrisGammell 2y ago

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.

seveibar 2y ago
We will absolutely be supporting KiCad! Placement is something we have big plans for but I think it’s important to have a really fast, cache-friendly autorouter as a foundation (if you are cache friendly, moving components and trying different layouts is much much faster) Javascript is fairly portable now with many runtimes (some even quite small such as QuickJS or Proffor), so I anticipate people will be able to run locally and build their own ginormous cache :) I think everyone should be concerned about lockin and fragmenting ecosystems in EDA, but tscircuit and our autorouter are MIT-permissive technology (very rare in EDA) so we play nice (interoperable) with everyone.
- _fizz_buzz_ 2y ago
  How are you planning to support kicad? Would it be using kicad's new IPC API? In principle it should be possible to create javascript bindings for the new protobuf interface.
  - seveibar 2y ago
    We are looking hard at the IPC interface or doing a plugin, but we will also support “uploading” kicad_sch/kicad_pcb to a browser (local-first, so not actually uploading)

nine_k 2y ago

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.

Lerc 2y ago

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.

rocqua 2y ago
This is why I use python with Jupyter notebooks. Though admittedly animations are quite arduous.
misiek08 2y ago
I'd love to see what is the easiest way, for a hardcore backend guy with completely dumb part of brain responsible for visuals, to quickly visualize things in JS. I would pay for a "d3/p5 tutorial".
- seveibar 2y ago
  Author here. I would recommend booting up React Cosmos[1] and prompting Claude to "generate a react app that...". You can visualize inside of Claude then when you're finished, drop the output of Claude into React Cosmos as a file. This is great for prototyping algorithms and recording the progression. For example you might say "generate an interactive react app that implements a simple pathfinder that uses A* with a penalty for going near edges". You can also just drop in a paper or pseudo code of an algorithm you're ideating on. Here's an example how we use react cosmos for our autorouter[2] [1] https://reactcosmos.org/docs https://reactcosmos.org/docs [2] https://unraveller.vercel.app/?fixtureId=%7B%22path%22%3A%22examples%2Fend-to-end%2Fe2e3.fixture.tsx%22%7D https://unraveller.vercel.app/?fixtureId=%7B%22path%22%3A%22...
WillAdams 2y ago
Visualization is actually one of the reasons I've been successful with my current project (creating a 3D modeling library which uses 3D tool representations and movement as afforded by G-code to write out G-code or DXFs) --- the tool which makes it possible is: https://pythonscad.org/ https://pythonscad.org/ Being able to just plot something and see the algorithm on-screen has been an incredible benison. I'm hopeful OpenPythonSCAD will be merged into OpenSCAD presently.

MrLeap 2y ago

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.

seveibar 2y ago
It is a really fun idea to build a boids router (shelving that for a future article!) I wrote previously about recursive pattern autorouters which are really good at having small solution spaces (and therefore, easier to get conventional machine learning algorithms to predict). There are so many interesting unexplored areas in autorouting!! I hadn't heard of jumpflooding (for others: fast, parallel algorithm for approximating distance fields), that could definitely be interesting, thanks for the tip!
shadowgovt 2y ago
I think the trees were a lot more useful in the past when memory and caches were smaller (and I suspect they can still be useful for precomputation, though I'd have to sit down and benchmark fixed-grid-with-smart-sizing vs. tree). Trees are also amendable to recursive algorithms but the author has noted that they have reasons to choose iterative over recursive algorithms, so these pieces of advice synergize. (It is perhaps worth noting: broadly speaking, "recursive" vs. "non-recursive" is a bit of an artificial distinction. The real question is "does a pre-baked algorithm with rigid rules handle flow control, or do you?" If you care about performance a lot, you want the answer to be you, so having your run state abstracted away into an execution-environment-provided stack that you can't easily mutate weirdly at runtime begins to get in your way).

kayson 2y ago

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.

leoedin 2y ago
I had a play with the tscircuit CAD tool which they're writing this autorouter for. It's hardware-as-code, leveraging React. I love the concept of schematics-as-code. But layout-as-code is awful. Maybe AI tools will improve it enough - but unless there's a user friendly escape hatch which lets you tweak things with a mouse, it's a dead end. I've had the same problem with auto-generated wiring diagrams and flowcharts. Great in theory, but then the tool generates some ugly thing you can't make sense of and there's no way to change it. There's definitely tremendous potential for AI in electronic design. But I think the really complicated bit is component selection and library management - you have to somehow keep track of component availability, size and a range of parameters which are hidden on page 7 of a PDF datasheet. Not to mention separate PDF application notes and land patterns. Compared to all that, connecting up schematic lines and laying out a PCB is fairly straight forward.
- seveibar 2y ago
  Love that you tried the tool and couldn't agree more. We think that new layout paradigms similar to flex and CSS grid need to be invented for circuit layout. This is an active area of research for us!

aranchelk 2y ago

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

bigiain 2y ago
I think there's a fair argument to be made that when you're chasing Big O algorithmic improvements, then the effective constant terms incurred by "faster or slower language execution" are premature optimisation. The difference between Rust or hardcoded assembler compared to Javascript or VisualBasic are pretty irrelevant if you're still trying to get your exponent or polynomial terms under control.
- HdS84 2y ago
  Yep. Also, js is easy to iterate on - it's more lenient than rust or say c#. Especially if you are exploring thinks, that's a huge boon. Obviously, for the same algorithm, compiled languages will be slower. Does it matter? Maybe. But time to find this algorithm is also critical - and if js helps here, it's a good choice.
- kalaksi 2y ago
  But what about afterwards? You move to a more performant language or just accept that you're now invested in JS?
  - andrewaylett 2y ago
    One or the other, probably — Facebook were sufficiently invested in PHP that they released a whole new VM for the language. In Python, one would relatively commonly extract the performance-critical sections into C (or, nowadays, Rust) and you could do the same with Node too. Or the JIT might be fast enough that it's not worthwhile.

sitkack 2y ago

What a wonderfully written post! Much respect.

djmips 2y ago

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!

weinzierl 2y ago

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

kalaksi 2y ago

> 2. Implementation Language doesn’t matter I'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.

deleted 2y ago

[deleted]

n4r9 2y ago

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.

deleted 2y ago
[deleted]
hansvm 2y ago
> recursive == DFS The intuition there is that people tend to write algorithms recursively when they easily map to interactions with the top of the stack, since that's easier to express in most languages than bringing in an external stack to think about. Hence, if you see something recursive in the wild it likely looks more like DFS than BFS. As you point out, that isn't a hard rule.
thequux 2y ago
Indeed, BFS, DFS, and A* are the same algorithm just with a different data structure to track unexplored nodes. BFS uses a FIFO queue, DFS uses a LIFO stack, and A* uses a priority queue (generally a heap)

hyperbrainer 2y ago

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

fire_lake 2y ago
And even then, execution depends on your language and compiler. Write a recursive BFS in Haskell and it won’t blow up the stack.
- hyperbrainer 2y ago
  Any language with decent TCO won't do that. Python is the only big language that I can think of that doesn't do it.
  - fire_lake 2y ago
    Guaranteed TCO is pretty rare unfortunately. Java, Go, JavaScript all lack it.
    - hyperbrainer 2y ago
      Actually, you are right.

tobyhinloopen 2y ago

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

jofla_net 2y ago

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

dkjaudyeqooe 2y ago

> 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)) algorithm This 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.

rtpg 2y ago
Measure measure measure measure. Each case is different. But more seriously I think tree based algos tend to be overhyped, and people get a bit absorbed into thinking about big-O behavior when the constant factors are super important even when you’re looking at hundreds of thousands of elements. Not to mention stuff like data locality. Like sometimes your computer will be faster at just looking in a seq scan rather than dealing with the bookkeeping of a fancier structure. Sometimes. I think a nicer argument overall is to build a tiny wrapper around your operations, build out what is easy, and then figure it out through measurements. Worst case you end up entirely rewriting your program to accommodate a different structure to try for better perf but in my experience rewriting entire files from scratch tends to get you a good number of improvements for free.
- dkjaudyeqooe 2y ago
  Sequential scans are terribly underrated given today's architectures. If the datum is small and it's like 1000 elements max it's going to be hard to beat a simple scan of an array for speed and memory efficiency. But trees et al also make a lot of sense as a default. If you need the performance to scale in a roughly linear manner you need to be smart about it. This is what sinks a lot of software, usability wise.

GistNoesis 2y ago

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

ttyprintk 2y ago
Yet the author mentioned simulated annealing, so was probably not even trying a neural net, since SA does not compute a gradient.
- ttul 2y ago
  Simulated annealing has long been one of the classic metaheuristic methods applied to autorouting in circuit design. It was widely used in early research and some commercial tools because its probabilistic approach helps escape local minima in these NP‐hard problems. Today, while many modern autorouters in industry tend to favor faster or more specialized hybrid methods, simulated annealing remains a common benchmark in academic studies and research prototypes for routing and related tasks like floorplanning. Source: I once wrote a simulated annealer for VLSI wiring. It was cool.

xg15 2y ago

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.

windward 2y ago
Agreed. Adding a test that generates a random 32 bit int to your project is adding 4 billion tests to your project and only running one of them.

fooblaster 2y ago

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.

amiga386 2y ago

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

bArray 2y ago

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] https://github.com/vygr/Python-PCB https://github.com/vygr/Python-PCB [1] https://github.com/freerouting/freerouting https://github.com/freerouting/freerouting

CamouflagedKiwi 2y ago

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.

swiftcoder 2y ago
Not to mention that most hashmap implementations for managed languages incur ~2 cache misses per lookup. I've had an awful lot of optimisation wins over the years just by ripping hash maps out of software that either didn't actually need arbitrary key->value lookups, or had datasets large enough that a sufficiently wide tree-like structure handily beat the hashmap

thenthenthen 2y ago

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

shadowgovt 2y ago

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.

deleted 2y ago

[deleted]

teleforce 2y ago

>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): https://news.ycombinator.com/item?id=43447616 https://news.ycombinator.com/item?id=43447616 [2] Diagrams AI can, and cannot, generate (68 comments): https://news.ycombinator.com/item?id=43398434 https://news.ycombinator.com/item?id=43398434 [3] Constraint programming: https://en.wikipedia.org/wiki/Constraint_programming https://en.wikipedia.org/wiki/Constraint_programming [4] Logic, Optimization, and Constraint Programming: A Fruitful Collaboration - John Hooker - CMU (2023) [video]: https://www.youtube.com/live/TknN8fCQvRk https://www.youtube.com/live/TknN8fCQvRk [5] "We Really Don't Know How to Compute!" - Gerald Sussman - MIT (2011) [video]: https://youtube.com/watch?v=HB5TrK7A4pI https://youtube.com/watch?v=HB5TrK7A4pI [6] High-Quality Ultra-Compact Grid Layout of Grouped Networks [PDF]: https://ialab.it.monash.edu/~dwyer/papers/gridlayout2015.pdf https://ialab.it.monash.edu/~dwyer/papers/gridlayout2015.pdf