[thesz]

Eurisco [1], if I remember correctly, was once used to perform placement-and-route task and was pretty good at it.

[1] https://en.wikipedia.org/wiki/Eurisko

What's more, Eurisco was then used in designing Traveler TCS' game fleet of battle spaceships. And Eurisco used symmetry-based placement learned from VLSI design in the design of the spaceships' fleet.

Can AlphaChip's heuistics be used anywhere else?

[gabegobblegoldi]

Doesn’t look like it. In fact the original paper claimed that their RL method could be used for all sorts of combinatorial optimization problems. Yet they chose an obscure problem in chip design and showed their results on proprietary data instead of standard public benchmarks.

Instead they could have demonstrated their amazing method on any number of standard NP hard optimization problems e.g. traveling salesman, bin packing, ILP, etc. where we can generate tons of examples and verify easily whether it produces better results than other solvers or not.

This is why many in the chip design and optimization community felt that the paper was suspicious. Even with this addendum they adamantly refuse to share any results that can be independently verified.

[AshamedCaptain]

> Yet they chose an obscure problem in chip design

It is not obscure (in chip design). If anything it is one of the most easily reachable problems. Almost every other PhD student in the field has implemented a macro placer, even if just for fun, and there are frequent academic competitions. A lot of design houses also roll their own macro placers since it's not a difficult problem and generally adding a bit of knowledge of your design style can help you gain an extra % over the generic commercial tools.

It does not surprise me at all that they decided to start with this for their foray into chip EDA. It's the minimum effort route.

[gabegobblegoldi]

Sorry. I meant obscure relative to the large space of combinatorial optimization problems not just chip design.

Most design houses don’t write their own macro placers but customize commercial flows for their designs.

The problem with macro placement as an RL technology demonstrator is that to evaluate quality you need to go through large parts of the design flow which involves using other commercial tools. This makes it incredibly hard to evaluate superiority since all those steps and tools add noise.

Easier problems would have been to use RL to minimize the number of gates in a logic circuit or just focus on placement with half perimeter wirelength (I think this is what you mean with your grad student example). Essentially solving point problems in the design flow and evaluating quality improvements locally.

They evaluated quality globally and only globally and that destroys credibility in this business due to the noise involved unless you have lots of examples, can show statistical significance, and (unfortunately for the authors) also local improvements.

That’s what the follow on studies did and that’s why the community has lost faith in this particular algorithm.

[AshamedCaptain]

> Most design houses don’t write their own macro placers but customize commercial flows for their designs.

Most I don't know, but all the mid-to-large ones have automated macro placers. Obviously, the output is introduced into the commercial flow, generally by setting placement constraints. The larger houses go much further and may even override specific parts of the flow, but not basing it on an commercial flow is out of the question right now.

> The problem with macro placement as an RL technology demonstrator is that to evaluate quality you need to go through large parts of the design flow which involves using other commercial tools.

Not really, not any more than any other optimization such as e.g. frontend which I'm more familiar with. If you don't want to go through the full design flow (which I agree introduces noise more than anything else), then benchmark your floorplans in some easily calculable metric (e.g., HPWL). Likewise, if you want to test the quality of some logic simplification _in theory_ you'd have to also go through the entire flow (backend included), but no one does that and you just evaluate some easily calculable metric e.g. number of gates. These distinctions are traditional more than anything else.

Academic macro placers generally have limited access to commercial flows (either due to licensing issues or computing resource availability) so it is rather common to benchmark them in other metrics. Google paper tried to be too smart for its own good and therefore incomparable to anything academic.

[gabegobblegoldi]

Thanks.