## Advanced variable ordering configuration

The CIF data-based synthesis performance depends greatly on the variable ordering. After selecting an initial ordering, it can subsequently be improved by algorithms for automatic variable ordering. This may be configured using basic options, but they offer only limited flexibility. For the most flexibility, variable ordering can be configured using the BDD advanced variable ordering option (see the options section). Advanced ordering allows configuring which orderers, such as predefined orders and ordering algorithms, to use. It also allows configuring the order in which the various orderers are applied, as well as the settings to use for each orderer.

Variable ordering may be configured using either the basic options or using the advanced option. It is not supported to configure variable ordering using both basic and advanced configuration at the same time.

### Examples

The predefined initial variable orderings can be expressed using the advanced syntax as follows:

Predefined initial ordering | Advanced syntax
--- | ---
`model` | `model`
`reverse-model` | `model(effect=var-order) → reverse(effect=both)`
`sorted` | `sorted`
`reverse-sorted` | `sorted(effect=var-order) → reverse(effect=both)`
`random` | `random`
`random:SEED` | `random(seed=SEED)`
`<custom-order>` | `custom(order="<custom-order>")`

Some other examples of advanced variable orderings:

- `model -> dcsh -> force -> slidwin`: Start with model order as initial order, and then apply the DCSH, FORCE and sliding window algorithms with their default settings.

- `sorted -> dcsh(relations=linearized)`: Start with sorted order as initial order, and then apply the DCSH algorithm with linearized variable relations.

- `random -> or(choices=[dcsh,force])`: Start with a random order as initial order, and then apply the DCSH and FORCE algorithms, choosing the best order from the ones produced by the two algorithms.

- `force -> reverse`: Start with the default initial model order, then apply the FORCE algorithm, and finally reverse the variable order.

### Syntax

The syntax to specify advanced variable ordering generally works as follows:

- Orderers are specified by their name.

- Arguments to configure orderers may optionally be given after the name of the orderer between parentheses: `(...)`.

- It is allowed to provide empty parentheses, e.g., `model()` is equivalent to specifying `model`.

- Each argument is given by a name and a value: `name=value`.

- To specify multiple arguments, separate them with a comma. After the last argument, optionally a comma may be specified as well.

- To apply multiple algorithms in sequence, separate them with an arrow (`->`).

- If needed, a sequence of orderers may be enclosed in parentheses: `(... -> ... -> ...)`.

- Spaces, tabs, and newline characters are generally ignored, but can be used to improve readability.

### Orderers

The following orderers can be specified:

- Basic ordering

  Uses the configuration as configured by the basic variable ordering options.

  - Name: `basic`

  - Arguments: n/a

  - Example: `basic`

- Model order

  Uses the predefined model order.

  - Name: `model`

  - Arguments:

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `both`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `model`, `model(effect=var-order)`

- Sorted order

  Uses the predefined sorted order.

  - Name: `sorted`

  - Arguments:

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `both`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `sorted`, `sorted(effect=var-order)`

- Random order

  Uses the predefined random order.

  - Name: `random`

  - Arguments:

    - `seed`

      - Description: a seed for the random order

      - Mandatory: no

      - Default: use a random seed

      - Type: number

      - Constraints: seed must be in the range [0 .. 264 - 1]

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `both`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `random`, `random(seed=123)`, `random(seed=123, effect=var-order)`

- Custom order

  Uses a custom order.

  - Name: `custom`

  - Arguments:

    - `order`

      - Description: the custom order, with the same syntax as for the basic configuration option

      - Mandatory: yes

      - Default: n/a

      - Type: string

      - Constraints: the order must be complete in that it contains all variables, and must not contain any duplicate variables

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `both`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `custom(order="a,b;c,d")`, `custom(order="a,b;c,d", effect=var-order)`

- DCSH

  Applies the DCSH algorithm.

  - Name: `dcsh`

  - Arguments:

    - `node-finder`

      - Description: the node finder algorithm to use for the Weighted-Cuthill-McKee orderer

      - Mandatory: no

      - Default: `george-liu`

      - Type: enum (`george-liu` or `sloan`)

      - Constraints: none

    - `metric`

      - Description: the metric to use to compare orders

      - Mandatory: no

      - Default: `wes`

      - Type: enum (`total-span` or `wes`)

      - Constraints: none

    - `relations`

      - Description: the kind of relations to use when computing metric values

      - Mandatory: no

      - Default: `configured` (per the BDD hyper-edge creation algorithm option)

      - Type: enum (`configured`, `legacy` or `linearized`)

      - Constraints: none

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `var-order`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `dcsh`, `dcsh(metric=wes)`, `dcsh(node-finder=george-liu, metric=wes, relations=configured, effect=both)`

- FORCE

  Applies the FORCE algorithm.

  - Name: `force`

  - Arguments:

    - `metric`

      - Description: the metric to use to compare orders

      - Mandatory: no

      - Default: `total-span`

      - Type: enum (`total-span` or `wes`)

      - Constraints: none

    - `relations`

      - Description: the kind of relations to use when computing metric values

      - Mandatory: no

      - Default: `configured` (per the BDD hyper-edge creation algorithm option)

      - Type: enum (`configured`, `legacy` or `linearized`)

      - Constraints: none

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `var-order`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `force`, `force(metric=total-span)`, `force(metric=total-span, relations=configured, effect=both)`

- Sliding window

  Applies the sliding window algorithm.

  - Name: `slidwin`

  - Arguments:

    - `size`

      - Description: the maximum size of the window

      - Mandatory: no

      - Default: 4 (as configured by the BDD sliding window size option)

      - Type: number

      - Constraints: size must be in the range [1 .. 12]

    - `metric`

      - Description: the metric to use to compare orders

      - Mandatory: no

      - Default: `total-span`

      - Type: enum (`total-span` or `wes`)

      - Constraints: none

    - `relations`

      - Description: the kind of relations to use when computing metric values

      - Mandatory: no

      - Default: `configured` (per the BDD hyper-edge creation algorithm option)

      - Type: enum (`configured`, `legacy` or `linearized`)

      - Constraints: none

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `var-order`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `slidwin`, `slidwin(size=5)`, `slidwin(size=5, metric=total-span, relations=configured, effect=both)`

- Sloan

  Applies the Sloan profile/wavefront-reducing algorithm.

  - Name: `sloan`

  - Arguments:

    - `relations`

      - Description: the kind of relations to use when computing metric values

      - Mandatory: no

      - Default: `configured` (per the BDD hyper-edge creation algorithm option)

      - Type: enum (`configured`, `legacy` or `linearized`)

      - Constraints: none

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `var-order`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `sloan`, `sloan(relations=configured, effect=both)`

- Weighted Cuthill-McKee

  Applies the Weighted Cuthill-McKee bandwidth-reducing algorithm.

  - Name: `weighted-cm`

  - Arguments:

    - `node-finder`

      - Description: the node finder algorithm to use

      - Mandatory: no

      - Default: `george-liu`

      - Type: enum (`george-liu` or `sloan`)

      - Constraints: none

    - `relations`

      - Description: the kind of relations to use when computing metric values

      - Mandatory: no

      - Default: `configured` (per the BDD hyper-edge creation algorithm option)

      - Type: enum (`configured`, `legacy` or `linearized`)

      - Constraints: none

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `var-order`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `weighted-cm`, `weighted-cm(relations=configured)`, `weighted-cm(node-finder=george-liu, relations=configured, effect=both)`

- Choice

  Applies multiple algorithms to the same variable order and chooses the best resulting order.

  - Name: `or`

  - Arguments:

    - `choices`

      - Description: the orderers to apply

      - Mandatory: yes

      - Default: n/a

      - Type: list of orderers

      - Constraints: at least two orderers must be specified

    - `metric`

      - Description: the metric to use to compare orders

      - Mandatory: no

      - Default: `wes`

      - Type: enum (`total-span` or `wes`)

      - Constraints: none

    - `relations`

      - Description: the kind of relations to use when computing metric values

      - Mandatory: no

      - Default: `configured` (per the BDD hyper-edge creation algorithm option)

      - Type: enum (`configured`, `legacy` or `linearized`)

      - Constraints: none

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `var-order`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `or(choices=[dcsh,force])`, `or(choices=[(force -> dcsh), (dcsh -> force)], metric=wes, relations=configured, effect=both)`

- Repeat

  Repeat an orderer a number of times.

  - Name: `repeat`

  - Arguments:

    - `orderer`

      - Description: the variable orderer to repeatedly apply

      - Mandatory: yes

      - Default: n/a

      - Type: orderer

      - Constraints: none

    - `count`

      - Description: the number of types to apply the given variable orderer

      - Mandatory: yes

      - Default: n/a

      - Type: number

      - Constraints: count must be at least one

    - `intermediate-effect`

      - Description: the effect of the given variable orderer, for all but the final time it is applied

      - Mandatory: no

      - Default: `var-order`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

    - `final-effect`

      - Description: the effect of the given variable orderer, for the final time it is applied

      - Mandatory: no

      - Default: `var-order`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `repeat(orderer=(dcsh->force->slidwin), count=4)`, `repeat(orderer=dcsh, count=2, intermediate-effect=both, final-effect=var-order)`

- Reverse

  Reverses the variable order.

  - Name: `reverse`

  - Arguments:

    - `relations`

      - Description: the kind of relations to use when computing metric values

      - Mandatory: no

      - Default: `configured` (per the BDD hyper-edge creation algorithm option)

      - Type: enum (`configured`, `legacy` or `linearized`)

      - Constraints: none

    - `effect`

      - Description: the effect of the variable orderer

      - Mandatory: no

      - Default: `var-order`

      - Type: enum (`var-order`, `representations` or `both`)

      - Constraints: none

  - Examples: `reverse`, `reverse(relations=configured, effect=both)`

### Node finders

Orderers that work on graphs may use a pseudo-peripheral node finder algorithm while computing a variable order. Multiple such node finders can be used:

- George-Liu

  Use the algorithm by George and Liu.

  Name: `george-liu`

- Sloan

  Use the algorithm by Sloan.

  Name: `sloan`

### Metrics

To compare different orders, and choose the best one, metric values are used. Multiple metrics can be used:

- Total span

  Use the total span metric.

  Name: `total-span`

- WES

  Use the Weighted Event Span (WES) metric.

  Name: `wes`

### Relations

Metric value can be computed using different variable relations derived from the CIF specification. Multiple metrics can be used:

- Legacy

  Use the legacy relations.

  Name: `legacy`

- Linearized

  Use the linearized relations.

  Name: `linearized`

- Configured

  Use the relations as configured using the BDD hyper-edge creation algorithm option.

  Name: `configured`

### Effects

A variable orderer produces a variable order. The effect of a variable orderer determines what happens with the produced order:

- It may be used as the new variable order. The produced variable order then becomes the variable order to be used as input to the next orderer, or the final order in case it is the effect of the last orderer. If the produced variable order is not used as the new variable order, the variable order remains unchanged by the orderer.

- It may be used to compute new representations of the variable relations. Subsequent orderers will then use these new representations as input to algorithms and for computing metrics. If the produced variable order is not used to create new representations, the representations remain unchanged by the orderer.

The following effects can be configured:

- Variable order

  Uses the produced variable order as the new variable order. Does not update the representations.

  Name: `var-order`

- Representations

  Updates the representations. Does not use the produced variable order as the new variable order.

  Name: `representations`

- Both

  Uses the produced variable order as the new variable order, and updates the representations.

  Name: `both`