@lofty I would love that, though I also don't want to impose!
-
@lofty I would love that, though I also don't want to impose! I'm just mashing the buttons that are exposed in flags to see what happens, and the numbers change. I'm curious though! Seems like it's getting active development so I'm guessing it's tentatively the future?
-
big awoo notationreplied to Dave Anderson last edited by
it's tentatively the future
these days it feels like it's "the future" much like btrfs is "the future"...
grumbling aside: the default placer for ECP5 is HeAP (the reference paper is "analytical placement for heterogeneous FPGAs"), and HeAP works by treating the problem of placing cells together as a bunch of quadratic equations representing wire length. these can be mathematically minimised very efficiently, but the result you get has a bunch of overlapping cells. therefore the result is fed into a pass which snaps cells to their nearest legal position. these positions are then fed back into the quadratics and minimised again, and then the output goes through legalisation, and it all loops until the quadratic output and the legalised output are Close Enough.
static - multi-electrostatic placement - is similar at the high level: mathematical formula to be solved. however the formula this time is much more complex. it's called electrostatic placement because the formula used models cells as electrons with charges that repel each other; this means the explicit legalisation step in HeAP which took place outside the equations can be partially modelled within static. that means there are only two direct legalisation runs: one for non-logic stuff like RAM blocks and DSPs, usually near the start, and one for logic right at the very end.
there are a lot of challenges that mean that static might not take over heap in practice. with heap, after every iteration you have exact cell locations, so you can more accurately guesstimate and factor in timing; that's harder to do with static, where everything is fuzzier. also, calculating derivatives in heap is easy (they're linear equations), while calculating derivatives in static is monstrously hard, and so static has been plagued with issues - the math is difficult for both myself and Myrtle.
but, well, I assume you've tried--placer sa
, and anything is better than that. -
Dave Andersonreplied to big awoo notation last edited by
@lofty Wow, fancy! Thanks for the primer, fascinating stuff. I'm intrigued because both these algorithms sound like deterministic optimization problems, so how does varying random seeds result in different outputs? I'm guessing randomizing initial conditions, because with the loops things fall into a local optimum?
-
big awoo notationreplied to Dave Anderson last edited by
@[email protected] pretty much exactly that, yes.
-
big awoo notationreplied to big awoo notation last edited by
@[email protected] determinism is useful for debugging for hopefully obvious reasons; but it's also worth pointing out that the simulated annealing refinement pass is still inherently based on randomness.
-
Dave Andersonreplied to big awoo notation last edited by
@lofty Yeah the determinism is definitely welcome, even outside debuggability being able to ship source and build configs and know that (modulo same versions) the output will be stable is very nice.
I'd missed that there was always an annealing pass! I was focused on the timing results and managed to somehow miss that output in the logs this whole time.
Even with determinism, the local optima must make it hard to compare these different algorithms reliably!