Skip to content

#371 Improved CIF data-based synthesis variable ordering API

There are quite a few changes in this branch:

  • AutoVarOrderer is now VarOrderer and is an interface instead of a base class. It now longer forces a representation of the specification and internal storage decisions upon the actual algorithms. The initialization and cleanup is also gone. There is now just a single method that algorithms should implement.
  • VarOrderHelper contains the hyper-edges, which is currently the only representation of the specification. More representations can be easily added to it.
  • VarOrderHelper also contains various utility methods, moved from AutoVarOrderer.
  • Moved all non-algorithm-specific functionality out of AutoVarOrderer to CifToSynthesisConverter. It now determines whether to apply algorithms or not, and indicates in debug output why it is skipped. Or also prints the general debug output, such as number of hyper-edges.
  • The variable ordering algorithms (through the VarOrderer interface), no longer reorder the variables in SynthesisAutomaton. They just compute new orders for the variables. CifToSynthesisConverter applies the final order to SynthesisAutomaton. This keeps the 'original order' stable. Also, it makes it easier to implement a ChoiceVarOrderer that applies multiple algorithms to the same input order and chooses the best order produced by various algorithms.
  • The VarOrderer interface has dbgLevel to allow arbitrary trees of algorithms. For instance, atomic algorithms such as FORCE and sliding window can now easily be combined with sequence, choice, reverse, etc wrappers algorithms to form complex algorithm trees. Since we get arbitrary nesting levels, dbgLevel allows printing intuitive debug output matching the algorithm tree structure.
  • As a result of the changes, with CifToSynthesisConverter handling the non-algorithm-specific things, with dbgLevel being introduced, and with the reason for skipping automatic variable ordering being printed, the debug output of the regression tests have changed. However, these are only debug output changes. The algorithms function as before, and produce the same variable orders. Functionality, it works as before for end users.
  • I got confused several times while working on this about terminology. Terms like 'order' and 'indices' were used in different ways, which was confusing, and led to regression bugs. Hence, I now use 'order' for orders of the variables (including per variable in the new order its original 0-based index), and (new) indices when referring to per variable in its original order its new 0-based index. Previously 'order' and 'indices' where sometimes used to refer to both these meaning. I've improved and clarified in various places the naming, JavaDoc, comments, etc, to hopefully avoid such confusion in the future.

I did several iterations of changing the API, not just for the current algorithms, but also to support future extensions (#196 (closed)). This is the design I ended up with, that seems to fit well.

If you want to review this, I propose to review it commit by commit. I completely reworked my final solution into smaller commits, for reviewing efficiency. Each commit message has further details on the changes. However, some things only become clear in a later commit, as the changes in different commits are somewhat intertwined, and I could not spend days on even better-reviewable commits.

Closes #371 (closed) Addresses #196 (closed)

Merge request reports