Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Rewrite FPGA entity execution algorithm #15

Open
llysdal opened this issue Mar 5, 2021 · 0 comments
Open

Rewrite FPGA entity execution algorithm #15

llysdal opened this issue Mar 5, 2021 · 0 comments
Labels
improvement Something could be done a little better

Comments

@llysdal
Copy link
Member

llysdal commented Mar 5, 2021

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 llysdal added the improvement Something could be done a little better label Mar 5, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
improvement Something could be done a little better
Projects
None yet
Development

No branches or pull requests

1 participant