Slower timing results with higher frequency target about nextpnr

[eddiehung]

There are a few things at play here:

• Simulated Annealing (SA) is an inherently deterministically-random process, such that making small changes in the design or the constraints can lead to wildly different solutions
• The algorithms used in nextpnr are currently pretty basic, and there is definitely room for improvement (e.g. see #27)
• There is a difference between icetime results and nextpnr because they use different timing models

Even in our internal testing, and even with 30 seeds, we've seen that higher Fmax target does not necessarily equate to higher final Fmax. This is definitely a problem, but it's unclear what the fix would be.

[eddiehung]

Actually, I've learned that there may be some issues with timing for LUT permutations. Stay tuned...

[q3k]

@eddiehung wanna take a look at this?

[daveshah1]

This behaviour is not surprising at all, the pseudorandom nature of SA means that small changes such as target frequency (or more directly seed) can have a significant impact on the quality of results. A scientific test would need to average 10-20 runs.

[esden]

@daveshah1 yes you are correct. By running nextpnr with different seed values it does result in different fmax. I ran a few seeds:

Seed	fmax
	1	10.57MHz
	2	11.38MHz
	3	11.60MHz
	4	12.56MHz
	5	12.51MHz
	6	11.76MHz
	7	10.79MHz
	8	11.61MHz
	9	11.67MHz
	10	11.67MHz
	11	11.08MHz
	12	11.48MHz

I am aware that this issue might not be possible to resolve. In that case I think there should be a mechanism to allow for a "search" run. This means running a defined amount of times using random seeds and find one with the best result. Maybe this could even be parallelized to allow for faster search? Of course I can just use a shell or python script to build such a thing but if this is an issue that people will run into on a regular basis it might be more practical to be provided through the command line parameters of nextpnr.

@eddiehung thank you for looking into this. Let me know if you want me to test something or need additional data.

[eddiehung]

Yes, such a feature would be good for internal testing as well as a good for end-users. The embarrassingly-parallel way would be to launch nextpnr as different processes or forking, but I wonder how much data/code can be shared with a multithreaded approach, and whether it would be worth taking this approach...!

Regarding the randomness of placement seeds, this is no different from vendor tools. It's often up to the user (or to pay a cloud service) to do sweeps to find the best timing...