Having a quite large search space the optimal Dijkstra scheduler is quite slow, essentially investigating the best options breadth-first until a solution is found.
Implementation wise there's still some low-hanging fruit that could improve performance mainly:
pruning the graphs to be scheduled pre-search: The IRGraph represents a function as a DAG with vertices being "computations" (function calls / opcodes / constant instantiations) and edges either being data or read/write dependencies. In many situations read/write dependencies could be pruned if nodes are already defined as being dependent in some other way (indirect data or read/write dependency). This would speed up the algorithm as every time a node is undone all its connections have to be iterated through. Pruning would be a one-time effort and provide a minimal but continuous speed-up.
The biggest performance improvements will come from designing a better heuristic for the A scheduler. Thanks to the properties of A, as long as the heuristic is admissible (i.e. never over-estimates the remaining distance) the final result is still guaranteed to be optimal unlike the current default heuristic "Guessoor", which delivers decent results but doesn't have the best guarantees.
A better heuristic may require a slight modification of the scheduler to allow for non-whole number cost values.
Once a better algorithm is found the compiler can be extended to speed up scheduling even further (at the cost of the solution's optimality) via bounded relaxation.
Having a quite large search space the optimal Dijkstra scheduler is quite slow, essentially investigating the best options breadth-first until a solution is found.
Implementation wise there's still some low-hanging fruit that could improve performance mainly:
IRGraphrepresents a function as a DAG with vertices being "computations" (function calls / opcodes / constant instantiations) and edges either being data or read/write dependencies. In many situations read/write dependencies could be pruned if nodes are already defined as being dependent in some other way (indirect data or read/write dependency). This would speed up the algorithm as every time a node is undone all its connections have to be iterated through. Pruning would be a one-time effort and provide a minimal but continuous speed-up.The biggest performance improvements will come from designing a better heuristic for the A scheduler. Thanks to the properties of A, as long as the heuristic is admissible (i.e. never over-estimates the remaining distance) the final result is still guaranteed to be optimal unlike the current default heuristic "Guessoor", which delivers decent results but doesn't have the best guarantees.
A better heuristic may require a slight modification of the scheduler to allow for non-whole number cost values.
Once a better algorithm is found the compiler can be extended to speed up scheduling even further (at the cost of the solution's optimality) via bounded relaxation.