[qvts] Improve speculation

[eclipse-qvtd-bot]

| --- | --- | | Bugzilla Link | 513375 | | Status | NEW | | Importance | P3 normal | | Reported | Mar 09, 2017 08:03 EDT | | Modified | Aug 09, 2018 04:30 EDT | | Depends on | 532429 | | Blocks | 515236, 511028 | | Reporter | Ed Willink |

Description

The partitioner currently speculates almost everything. This might have been good for exercising code paths, but it is needlessly inefficient. Speculation is only needed as a tool to break cyclic depedencies; acyclic mappings do not need speculation. Adding a cyclic analysis guard eliminates near all speculation in JUnit tests and often halves the number of micromappings to schedule.

[eclipse-qvtd-bot]

By Ed Willink on Apr 01, 2017 08:56

This proves to be very time consuming. copy/in-place is more important.

At run-time we need a Speculation object that accumulates the realized/predicated Speculatable trace objects. Speculations merge as they affect the same group of trace objects. For one realized/one predicated trace, as in the Forward2Reverse daisychain, a merge can be quite eager. However for a one realized/multiple predicate speculation, the number of Speculation instances may grow non-linearly.

Solutions.

one realized/one predicated trace speculations should be scheduled preferentially.

scheduler should have separate queues of speculations for one/two/three/... predicated traces.

speculations should be queued in bulk, then dispatched by eager calling from one speculation to the next so that the Speculation aggregates efficiently without producing numerous partial Speculations that eventually merge.

By doing the easier ones first we improve the chances that the harder ones re-use existing Speculations without non-linear hazards.

Also: safe speculations that have no extra predicates other than a closed group of trace predicates can optimized to bypass speculation altogether.

ewillink/513375 has the deferred work in progress.

[eclipse-qvtd-bot]

By Ed Willink on Mar 14, 2018 04:58

(In reply to Ed Willink from comment #1)

At run-time we need

Bug 532429 outlines a compile-time speculation analysis that may often render run-time support redundant.

[eclipse-qvtd-bot]

By Ed Willink on Jul 16, 2018 03:51

Working on overrides highlights that we need two trace statuses

"matched" to indicate that the partial speculation match has succeeded. (formerly internal-status)

"success" to indicate that the full match has succeeded. (formerly external-status).

But computing "matched" hits a chicken and egg problem. We need a fully partitioned suite of micromappings to work out which mappings need partitioning.

If instead we build a global Producer to/from Element (Node/Edge) graph, where Producer is the Element-group that must exist before the consumer can be created, we can analyze cycles in, and schedule, the Producer-Element graph. We can then grow MicroMapping (phases) on the schedule. Partitioning should be simpler, subsequent merging redundant. With a single multi-phase region we avoid the new/old region naming problems. Possibly the 'partitioned' graphs are just a debug aid drawn as a filter of the overall mapping without actually being reified as micromapping regions.

NB. The major difference here is that a Producer is an Element-group which may differ from a Region. Previously a producer was the Region that realized the Element. The same Producer may be identified in multiple Regions. Producers have a 'composite' inheritance of their Elements.

[eclipse-qvtd-bot]

By Ed Willink on Aug 09, 2018 04:30

For dependency cycles involving output edges, such as the type assignments for ATL2QVTr, partitioning the output assignments off as AssignmentPartitions avoids the output cycles infecting the middle node construction and general global status determination.

For dependency cycles involving input/middle edges, as in Forward2Reverse, the cycles cannot always be broken. Partitioning therefore separates functionality into a speculating/local-status determination of the input pattern prior to a speculation/global-status across instances.

Whether speculation is required appears to be a chicken and egg problem. We need to partition to sometimes break cycles in order to determine whether there are cycles that partitioning needs to partition for.

Currently each XXXPartition encapsulates the immediate synthesis of a MicroMappingRegion.

Solution: make the XXXPartitions work harder. Create all the Partitions, then schedule the Partitions then merge the Partitions then synthesize the MicroMappingRegions.

Future: rather than the current one MicroMappingRegion per Partition, we could instead have the original Region with an enumeration of phases permitting a restart at the prevailing enumerated phase and re-use of any saved context from previous enumerated phases. Too-long fallible computation phases could be split into multiple phases to ease restart with less recomputation.

Future: QVTs is only partially modelled, thus Partition is not modelled but MicroMappingRegion is. Once QVTs is fully modelled the distinction between Partition and MicroMappingRegion might vanish; qvts2qvti can synthesize the partitions of a region directly as an enumeration of phases.