On Tuesday, June 10, 2025 at 10:01:38 AM UTC-5 Edward K. Ream wrote: This paper <https://www.nature.com/articles/s41586-021-03544-w> about AlphaChip <https://deepmind.google/discover/blog/how-alphachip-transformed-computer-chip-design/>mentioned hypergraphs <https://en.wikipedia.org/wiki/Hypergraph>.
Some highlights of the AlphaChip paper: Training placement policies that generalize across chips is extremely challenging, because it requires learning to optimize the placement of all possible chip netlists onto all possible canvases. Chip floorplanning is analogous to a game with [a state space] of 1000 [factorial] (greater than 10**2,500), whereas Go has a state space of 10**360. The underlying problem is a high-dimensional contextual bandits problem <https://towardsdatascience.com/an-overview-of-contextual-bandits-53ac3aa45034/> [not to be confused with a multi-armed bandit problem <https://en.wikipedia.org/wiki/Multi-armed_bandit>] but, as in prior work, ... we have chosen to reformulate it as a sequential Markov decision process <https://en.wikipedia.org/wiki/Markov_decision_process> (MDP), because this allows us to more easily incorporate the problem constraints as described below. To address [the challenge of an enormous state space] we first focused on learning rich representations of the state space. Our intuition was that a policy capable of the general task of chip placement should also be able to encode the state associated with a new unseen chip into a meaningful signal at inference time. We therefore trained a neural network architecture capable of predicting reward on placements of new netlists, with the ultimate goal of using this architecture as the encoder layer of our policy. Seems like brilliant science and mathematics to me :-) Edward -- You received this message because you are subscribed to the Google Groups "leo-editor" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion visit https://groups.google.com/d/msgid/leo-editor/79d3c1fd-52f0-495e-8de3-eac6409c8635n%40googlegroups.com.
