[Model] MinimumCodeGenerationParallelAssignments

[isPANN]

Motivation

MINIMUM CODE GENERATION FOR PARALLEL ASSIGNMENTS (P298) from Garey & Johnson, A11 PO6. Given a set of simultaneous variable assignments, find an execution ordering that minimizes the number of backward dependencies (cases where a variable is overwritten before a later assignment reads its old value). This models the problem of sequencing parallel assignment statements in compilers when all assignments should conceptually happen simultaneously.

Associated reduction rules:

• As target: R319 (FEEDBACK VERTEX SET →)
• Connections (beyond G&J):
  • Closely related to MinimumFeedbackVertexSet: backward dependencies correspond to back-arcs in the dependency graph
  • Applications: parallel assignment scheduling in compilers, register renaming, SSA destruction

Definition

Name: MinimumCodeGenerationParallelAssignments
Reference: Garey & Johnson, Computers and Intractability, A11 PO6

Mathematical definition:

INSTANCE: A set V of variables, a set of assignments A_1, A_2, ..., A_m where each A_i has the form "v_i ← op(B_i)" with v_i ∈ V and B_i ⊆ V being the set of variables read by the assignment.
OBJECTIVE: Find an ordering (permutation π) of the assignments that minimizes the number of backward dependencies. A backward dependency occurs when variable v_{π(i)} (written by the i-th executed assignment) appears in B_{π(j)} (read by the j-th executed assignment) for some j > i — i.e., the old value of v_{π(i)} is needed by a later assignment but has already been overwritten.

Variables

• Count: m (one variable per assignment, representing its position in the execution order)
• Per-variable domain: {0, 1, ..., m-1} (position in the permutation)
• Meaning: A permutation π of assignments. The cost is the number of pairs (i, j) with i < j such that v_{π(i)} ∈ B_{π(j)}.

Schema (data type)

Type name: MinimumCodeGenerationParallelAssignments
Variants: (none)

Field	Type	Description
num_variables	usize	Number of variables
assignments	Vec<(usize, Vec<usize>)>	Each assignment (target_var, read_vars): v_i ← op(B_i)

Complexity

• Decision complexity: NP-complete (Sethi, 1975; transformation from FEEDBACK VERTEX SET).
• Best known exact algorithm: O*(num_assignments! ) brute-force over all permutations, or equivalently O*(2^num_assignments) via dynamic programming.
• Restrictions: NP-complete even when |B_i| ≤ 2 for all assignments.
• References:
  • R. Sethi (1975). "Complete Register Allocation Problems." SIAM Journal on Computing, 4(3), pp. 226–248.

Extra Remark

Full book text:

INSTANCE: Set V of variables, collection of assignments A_i: "v_i ← op(B_i)" where B_i ⊆ V, positive integer K.
QUESTION: Is there an ordering of the assignments such that the number of backward dependencies (where v_{π(i)} ∈ B_{π(j)} for some j > i) is at most K?
Reference: [Sethi, 1975]. Transformation from FEEDBACK VERTEX SET.
Comment: NP-complete even with |B_i| ≤ 2.

Note: The original G&J formulation is a decision problem with threshold K. We use the equivalent optimization formulation: minimize the number of backward dependencies.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all m! permutations of assignments and count backward dependencies for each; return the minimum.)
• It can be solved by reducing to integer programming.
• Other: Reduction to minimum feedback arc set in the dependency digraph.

Example Instance

Variables: V = {a, b, c, d} (indices 0, 1, 2, 3)

Assignments:

• A_0: a ← op(b, c) — writes a (index 0), reads {b, c} (indices {1, 2})
• A_1: b ← op(a) — writes b (index 1), reads {a} (index {0})
• A_2: c ← op(d) — writes c (index 2), reads {d} (index {3})
• A_3: d ← op(b, c) — writes d (index 3), reads {b, c} (indices {1, 2})

Dependency graph: An arc from A_i to A_j exists when v_i ∈ B_j (A_i's target variable is read by A_j):

• A_0 → A_1 (a written by A_0, read by A_1)
• A_1 → A_0 (b written by A_1, read by A_0)
• A_1 → A_3 (b written by A_1, read by A_3)
• A_2 → A_0 (c written by A_2, read by A_0)
• A_2 → A_3 (c written by A_2, read by A_3)
• A_3 → A_2 (d written by A_3, read by A_2)

Cycles: A_0 ↔ A_1 (mutual dependency on a and b), A_2 ↔ A_3 (mutual dependency on c and d).

Optimal ordering π = (A_0, A_2, A_3, A_1):

• Position 1: A_0 writes a → a ∈ B_{A_1} (position 4) → 1 backward dep
• Position 2: A_2 writes c → c ∈ B_{A_3} (position 3) → 1 backward dep
• Position 3: A_3 writes d → d ∉ B_{A_1} → 0
• Position 4: A_1 writes b → no later assignments → 0
• Total: 2 backward dependencies ✓

Why 1 backward dependency is impossible: The two cycles A_0 ↔ A_1 and A_2 ↔ A_3 are independent. Each cycle forces at least 1 backward dependency (in any ordering, one member of the cycle must come before the other). Since there are 2 independent cycles, the minimum is 2.

Suboptimal ordering π = (A_2, A_0, A_3, A_1):

• A_2 writes c, read by A_0 (pos 2) and A_3 (pos 3) → 2 backward deps
• A_0 writes a, read by A_1 (pos 4) → 1 backward dep
• Total: 3 backward dependencies

Expected Outcome

Optimal value: Min(2) — the minimum number of backward dependencies is 2. Out of 24 permutations: 6 achieve 2 deps, 12 have 3 deps, and 6 have 4 deps, giving 3 distinct objective values.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Planned reduction from FeedbackVertexSet exists but no direct ILP rule linked
Non-trivial	✅ Pass	Distinct feasibility constraints from existing problems
Correctness	❌ Fail	Example analysis contains errors — wrong backward dependency count for stated ordering
Well-written	❌ Fail	Missing Expected Outcome section; example analysis is incorrect; naming convention issue

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The problem CodeGenerationParallelAssignments does not exist in the codebase. The issue mentions a reduction from FEEDBACK VERTEX SET (R319 in G&J), and MinimumFeedbackVertexSet already exists in the reduction graph, so the problem would connect to the existing graph. Pass on connectivity.

However, the "How to solve" section checks brute-force and "other" but does not check the ILP box. This is acceptable since ILP is not claimed. Brute-force is checked and viable (enumerate all m! permutations).

Warning: The motivation is adequate (compiler optimization for parallel assignments), but the planned reduction (FeedbackVertexSet → CodeGenerationParallelAssignments) is only mentioned as a G&J reference (R319), not as a concrete planned [Rule] issue. The connection is clear enough to avoid a failure, but a linked [Rule] issue would strengthen this.

Non-trivial

This problem has genuinely distinct feasibility constraints from all existing problems in the codebase. It involves ordering assignments to minimize backward dependencies (overwritten variables read by later assignments), which is structurally different from MinimumFeedbackVertexSet and MinimumFeedbackArcSet — even though it reduces to/from feedback problems, the input structure (set of variable assignments with read/write sets) and objective (counting backward dependencies in a permutation) are unique. Pass.

Correctness

Reference verification:

• Sethi (1975) — "Complete Register Allocation Problems," SIAM Journal on Computing, 4(3), pp. 226–248. This paper exists and is already in the project bibliography (@article{sethi1975} in docs/paper/references.bib). The DOI 10.1137/0204020 is confirmed. The paper does establish NP-completeness of register allocation problems via reduction from feedback vertex set. Verified.

• Sethi (1973) Technical Report 150 — cited as the preliminary version. This is plausible as the SIAM J. Computing version appeared in 1975. Cannot independently verify the tech report, but this is fine since the journal version is confirmed.

Complexity claim: The issue claims O*(2^m) brute-force as the best known algorithm. This is just exhaustive search over all m! permutations, which is worse than 2^m. No specialized exact algorithm is cited. This is acceptable as a baseline but lazy — the issue should note this is factorial, not exponential. The complexity expression should be m! or m^m, not 2^m (since m! >> 2^m for m > 3). Minor inaccuracy but not a hard failure.

Example verification — FAIL:
The issue claims the ordering π = (A₂, A₀, A₃, A₁) has 2 backward dependencies, but independent verification shows it actually has 3:

1. A₂ writes c → A₀ (step 2) reads c → backward dependency (the issue incorrectly says "old c is still available" — but A₂ already overwrote c)
2. A₂ writes c → A₃ (step 3) reads c → backward dependency (the issue identifies this one)
3. A₀ writes a → A₁ (step 4) reads a → backward dependency (the issue identifies this one)

The issue's step-by-step analysis contains a logical error: it states "A₂ executes first: writes c. Later A₀ reads c (old value needed) — but A₀ hasn't executed yet, old c is still available. OK, no backward dep from A₂." This is wrong — A₀ reads c, and A₂ has already overwritten c, so A₀ gets the new value of c instead of the old one. That IS a backward dependency.

The minimum number of backward dependencies is indeed 2, and optimal orderings include (A₀, A₂, A₃, A₁), but the specific ordering analyzed in the issue is suboptimal.

Well-written

4a: Information Completeness

Section	Status
Motivation	✅ Present and substantive
Name	⚠️ See naming note below
Reference	✅ Sethi 1975 cited
Definition	✅ Formal definition present
Variables	✅ Present
Schema	✅ Present with field table
Complexity	⚠️ O*(2^m) is misleading — brute force is m!, not 2^m
How to solve	✅ Brute-force checked
Example Instance	❌ Example analysis is incorrect (see Correctness above)
Expected Outcome	❌ Missing — no concrete optimal solution with the optimal objective value is provided. The issue analyzes one ordering but does not state a definitive "Optimal solution: π = (A₀, A₂, A₃, A₁) with 2 backward dependencies"

4b: Definition Completeness
The formal definition is well-formed with clear input, feasibility constraints, and objective. The INSTANCE/QUESTION format follows G&J conventions. Pass.

4c: Naming Convention
The name CodeGenerationParallelAssignments does not follow the project's naming convention. Since this is an optimization problem (minimize backward dependencies), it should use the Minimum prefix — e.g., MinimumCodeGenerationParallelAssignments or better yet a more descriptive name like MinimumBackwardDependencies or MinimumParallelAssignmentDependencies. The current name reads like a task description rather than a problem name.

4d: Example Quality

• The example has 4 assignments with 4 variables, giving 24 permutations with 3 distinct dependency counts (2, 3, 4) — this is adequate complexity for round-trip testing.
• However, the analysis is wrong (3 deps claimed as 2), and no correct optimal solution is stated.
• The example itself (the instance) is reasonable; only the analysis needs fixing.

Recommendations

• Fix the example analysis: the ordering (A₂, A₀, A₃, A₁) has 3 backward dependencies, not 2. An optimal ordering is (A₀, A₂, A₃, A₁) with 2 backward dependencies.
• Add an Expected Outcome section with a concrete optimal solution and objective value.
• Correct the complexity from O*(2^m) to O*(m!) or note that brute-force over permutations is factorial.
• Consider renaming to follow the Minimum... prefix convention for optimization problems.
• The budget field in the schema suggests a decision problem formulation, but the issue also says "The optimization version minimizes K." Clarify whether this is implemented as a decision or optimization problem. The codebase typically uses optimization formulations with Min<...> value types.

[isPANN]

Converted from decision to optimization framing: removed bound K, now asks for minimum backward dependencies. Renamed to MinimumCodeGenerationParallelAssignments. Removed Wrong and PoorWritten labels. Companion rule issue: #952 (MinimumFeedbackVertexSet -> MinimumCodeGenerationParallelAssignments, G&J R319).

[isPANN]

Fix-issue changelog

• Example: fixed incorrect backward dependency count — claimed ordering (A_2,A_0,A_3,A_1) has 3 deps, not 2. Replaced with correct optimal ordering (A_0,A_2,A_3,A_1) achieving 2 deps. Verified by brute-force enumeration of all 24 permutations.
• Expected Outcome: added section with Min(2) and permutation distribution (6/12/6 across 3 distinct values)
• Variables: made concrete (m variables, permutation domain)
• Added "why 1 is impossible" reasoning (2 independent cycles)
• Removed <!-- Unverified --> markers from verified sections

Applied by /fix-issue.