Bug 760 - calculate signal values in a Topological Ordering
Summary: calculate signal values in a Topological Ordering
Status: CONFIRMED
Alias: None
Product: Libre-SOC's second ASIC
Classification: Unclassified
Component: source code (show other bugs)
Version: unspecified
Hardware: Other Linux
: Lowest enhancement
Assignee: wielgusmikolaj
URL:
Depends on:
Blocks: 665
  Show dependency treegraph
 
Reported: 2021-12-23 18:33 GMT by Jacob Lifshay
Modified: 2021-12-23 19:14 GMT (History)
3 users (show)

See Also:
NLnet milestone: ---
total budget (EUR) for completion of task and all subtasks: 0
budget (EUR) for this task, excluding subtasks' budget: 0
parent task for budget allocation:
child tasks for budget allocation:
The table of payments (in EUR) for this task; TOML format:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Jacob Lifshay 2021-12-23 18:33:19 GMT
https://libre-soc.org/irclog/%23libre-soc.2021-12-23.log.html#t2021-12-23T18:22:12

if you just have a single combinatorial circuit without feedback loops, you should be able to calculate a topological ordering of the signals, such that you don't need a simulate loop cuz it can always calculate all signal values in a 	single step by calculating them in that specific ordering. this should greatly simplify the produced c code and make it run faster cuz you don't need the whole signal change tracking system.

https://en.wikipedia.org/wiki/Topological_sort

that would also help locate combinatorial loops (which is something not done at the moment, at all, in nmigen Simulation, and it's a pain)

the only thing being a pain in the neck, that sort takes place across an entire swathe of modules/fragments/processes
Comment 1 Luke Kenneth Casson Leighton 2021-12-23 19:14:29 GMT
nice idea, bear in mind it is an optimisation (priority set to low)
even detecting feedback loops is slightly problematic when SR latches
are involved.