wire-fpga icon indicating copy to clipboard operation
wire-fpga copied to clipboard

Rewrite FPGA entity execution algorithm

Open llysdal opened this issue 3 years ago • 0 comments

The current algorithm is queue based, which worked great when loops weren't a thing. As execution has grown more complex, it went from worst case n², to in complex case n². What I mean by this, is that any complex chip with loops (a CPU with registers / memory for example), is going to execute pretty slow.

The really nice things about the current algorithm is that it always executes in the right order, detects infinite loops, and only executes relevant nodes.

An alternative algorithm could be a stack based one. I've made some sketches and tests, and it seems it'd be worst case n, with a slightly higher constant. I couldn't get it to only execute relevant nodes however, so it is a tradeoff instead of a direct improvement.

It would be great if this could be a drop in replacement - not changing any behaviour, just execution times - but there's a chance it won't be. The "last" gates might change behaviour, and depending on how it chooses which nodes are executed when, some gates that change output when given the same input (increment gate as an example) will change behaviour.

llysdal avatar Mar 05 '21 22:03 llysdal