#196 Add DCSH variable ordering algorithm to data-based synthesis.

Closed Dennis Hendriks requested to merge 196-datasynth-dcsh-varorder-3 into develop

Variable ordering changes/additions:

  • Prepared VarOrdererHelper for more metrics besides total span.
    • Reduced space used for printing total span metric.
    • Variable amount of space based on initial metric value.
  • Added WES to VarOrdererHelper as additional variable ordering metric.

Graph related additions:

  • Added Graph and Node classes to represent graphs for data-based synthesis variable ordering algorithms to use.
  • Added graph representation support to VarOrdererHelper.
    • For now, graphs are created from the existing hyper-edges, ensuring consistency between the different representations.
    • We could later opt for other ways to create the hyper-edges/graphs.
    • Added extra utility methods for use by variable ordering algorithms.
  • Updated CifToSynthesisConverter for the added graph representation.

DCSH algorithm related additions:

  • Added rooted level structure constructor for graphs.
  • Added pseudo-peripheral node finder algorithms.
    • I tried to stay as close as possible to the original papers.
    • We have multiple algorithms here.
      • These are the ones which are needed for the node ordering heuristic algorithms.
      • We could experiment later which ones work best. (see below)
      • For now, node ordering algorithms use the ones from their corresponding papers.
  • Added node ordering heuristic algorithms.
    • I tried to stay as close as possible to the original papers.
    • These are the ones we need for the DCSH variable ordering algorithm.
    • Weighted Cuthill-McKee has been improved wrt the original paper: it works also for multiple unconnected partitions with >1 node.
  • Added variable ordering algorithms.
    • Added Sloan and Weighted Cuthill-McKee variable ordering algorithms, using the corresponding node ordering algorithms.
    • Added 'choice' and 'reverse' wrapper variable ordering algorithms.
    • Add DCSH variable ordering algorithm.
      • Is for now based on graphs constructed from the existing hyper-edges, ensuring consistency between the different representtations.
      • Could later create DMSs/hyper-edges based on the paper's approach.

Data-based synthesis tool additions:

  • Added new option for enabling DCSH variable ordering.
    • Is disabled by default, as I consider it experimental for now.
    • The 'experimental' label here is for end users. It does not concern the implementation.

Data-based synthesis variable ordering documentation additions/changes:

  • Added DCSH algorithm/option.
  • Extended explanation of heuristic algorithms in general.
  • Extended explanation of when algorithms are not applied.
  • Extended descriptions of the FORCE and sliding window algorithms.

Data-based synthesis tests additions/changes:

  • Renamed data-based synthesis test cases relating to force.
    • The force tests were about FORCE and sliding window, so were wrongly named.
    • Changed _force_ to _algos_.
    • Also extracted the related common options in the test ToolDef script to variables.
  • Added DCSH to variable ordering integration tests, to be applied with all the other algorithms for the algos tests.
    • Resulting metrics are the same or better for all these tests with DCSH added to it.
  • Added single variable ordering algorithm integration tests, besides the ones that test all the algorithms at once.
    • But only for a single initial random order, not for all the other initial orders, to avoid an explosion of tests.

Regarding reviewing:

  • I tried to keep the stack of commits reviewable one by one, although there are a few fixes/changes at the end that could potentially have been integrated into earlier commits.
  • Still, reviewing this per commit can be useful, as otherwise the totality of changes can be overwhelming, and the commits build towards the end result nicely.

I stopped here with this branch, as it is quite extensive already. The following are left as future work. I've created issues for the most relevant ones:

  • #375 (closed) It would be good to have some scripts to benchmark the benchmark models, comparing for instance FORCE + sliding window against DCSH + FORCE + sliding window, in an automated fashion. I partly put something together for this already.
  • #376 (closed) I think more testing is needed. I don't yet know whether the improvements we get in terms of better variable orderings and reduced synthesis effort match what the DCSH paper indicates. That would be good to check before lifting the 'experimental' label for end users to use it.
  • The choice variable orderer could support reverse orders as well, natively, to avoid applying the algorithms twice. However, that leads to more code, and a less modular design. I hope execution times are very short already anyway. But, I still want to measure those times to be sure. Otherwise we may want to look into this optimization.
  • #374 (closed) I found that our product-escet launch configuration is configured with only 4 GB of memory. That seems very low for todays systems.
  • #377 (closed) Hyper-edge creation has a bug, where for location invariants actually the component invariants are used. I'm a bit hesitant to change this now though, as it makes comparing the performance of DCSH against the paper more difficult. Also, what if it reduces synthesis performance. We have no good benchmarking set yet to test this.
  • #378 (closed) Data-based synthesis now only allows DCSH to be applied before FORCE and FORCE before sliding window. The order is fixed. I think the options should be generalized, to allow for instance choice(dcsh, sequence(force, sliding-window(9))) etc. This gives more flexibility for testing different configurations. Actual testing would require more benchmark models though.
  • #379 (closed) There are several places where choices can be made. We can choose the current hyper-edges vs the ones defined in the DCSH paper. We can enable DCSH by default or not. We can choose per algorithm (DCSH, FORCE, sliding window), to base it on the total span or WES metric. For the node ordering algorithms, we can choose which pseudo-peripheral node finding algorithm to use. All of this requires that we can determine what is better, hence we need ways to specify these choices, scripts to easily test the differences, and enough benchmarking models to conclude what is really better in general.
  • Variable ordering seems to lack cancellation checking. If the code runs for longer times (see other point), then we may need to add more of it. For now, this does not seem needed.
  • #380 (closed) We currently use the original hyper-edges. We could implement the hyper-edges defined in the DCSH paper, which may perform better.

Closes #196 (closed)

Edited by Dennis Hendriks

Merge request reports