problemreductions/models/misc/
minimum_code_generation_parallel_assignments.rs

1//! Minimum Code Generation for Parallel Assignments problem implementation.
2//!
3//! Given a set of simultaneous variable assignments, find an execution ordering
4//! (permutation) that minimizes the number of backward dependencies -- cases where
5//! a variable is overwritten before a later assignment reads its old value.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "MinimumCodeGenerationParallelAssignments",
15        display_name: "Minimum Code Generation (Parallel Assignments)",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Find an ordering of parallel assignments minimizing backward dependencies",
21        fields: &[
22            FieldInfo { name: "num_variables", type_name: "usize", description: "Number of variables" },
23            FieldInfo { name: "assignments", type_name: "Vec<(usize, Vec<usize>)>", description: "Each assignment (target_var, read_vars)" },
24        ],
25    }
26}
27
28/// The Minimum Code Generation for Parallel Assignments problem.
29///
30/// Given a set V of variables and a collection of assignments A_i: "v_i <- op(B_i)"
31/// where v_i is the target variable and B_i is the set of variables read,
32/// find a permutation of the assignments that minimizes the number of backward
33/// dependencies. A backward dependency occurs when assignment pi(i) writes
34/// variable v and assignment pi(j) (j > i) reads v.
35///
36/// # Example
37///
38/// ```
39/// use problemreductions::models::misc::MinimumCodeGenerationParallelAssignments;
40/// use problemreductions::{Problem, BruteForce};
41///
42/// // 4 variables, 4 assignments:
43/// // A_0: a <- op(b, c)   -> (0, [1, 2])
44/// // A_1: b <- op(a)      -> (1, [0])
45/// // A_2: c <- op(d)      -> (2, [3])
46/// // A_3: d <- op(b, c)   -> (3, [1, 2])
47/// let assignments = vec![
48///     (0, vec![1, 2]),
49///     (1, vec![0]),
50///     (2, vec![3]),
51///     (3, vec![1, 2]),
52/// ];
53/// let problem = MinimumCodeGenerationParallelAssignments::new(4, assignments);
54/// let solver = BruteForce::new();
55/// let solution = solver.solve(&problem).unwrap();
56/// assert!(solution.is_some());
57/// ```
58#[derive(Debug, Clone, Serialize, Deserialize)]
59#[serde(try_from = "MinimumCodeGenerationParallelAssignmentsData")]
60pub struct MinimumCodeGenerationParallelAssignments {
61    num_variables: usize,
62    assignments: Vec<(usize, Vec<usize>)>,
63}
64
65#[derive(Deserialize)]
66struct MinimumCodeGenerationParallelAssignmentsData {
67    num_variables: usize,
68    assignments: Vec<(usize, Vec<usize>)>,
69}
70
71impl TryFrom<MinimumCodeGenerationParallelAssignmentsData>
72    for MinimumCodeGenerationParallelAssignments
73{
74    type Error = crate::registry::ConstructionError;
75    fn try_from(data: MinimumCodeGenerationParallelAssignmentsData) -> Result<Self, Self::Error> {
76        Self::try_new(data.num_variables, data.assignments)
77    }
78}
79
80impl MinimumCodeGenerationParallelAssignments {
81    /// Create a new MinimumCodeGenerationParallelAssignments instance.
82    ///
83    /// # Panics
84    /// Panics if any target variable or read variable index is >= num_variables.
85    pub fn new(num_variables: usize, assignments: Vec<(usize, Vec<usize>)>) -> Self {
86        Self::try_new(num_variables, assignments).unwrap_or_else(|error| panic!("{error}"))
87    }
88
89    fn try_new(
90        num_variables: usize,
91        assignments: Vec<(usize, Vec<usize>)>,
92    ) -> Result<Self, crate::registry::ConstructionError> {
93        for (i, (target, reads)) in assignments.iter().enumerate() {
94            if *target >= num_variables {
95                return Err(format!(
96                    "assignment {i}: target variable {target} >= num_variables {num_variables}"
97                )
98                .into());
99            }
100            for &r in reads {
101                if r >= num_variables {
102                    return Err(format!(
103                        "assignment {i}: read variable {r} >= num_variables {num_variables}"
104                    )
105                    .into());
106                }
107            }
108        }
109        Ok(Self {
110            num_variables,
111            assignments,
112        })
113    }
114
115    /// Returns the number of variables.
116    pub fn num_variables(&self) -> usize {
117        self.num_variables
118    }
119
120    /// Returns the number of assignments.
121    pub fn num_assignments(&self) -> usize {
122        self.assignments.len()
123    }
124
125    /// Returns the assignments.
126    pub fn assignments(&self) -> &[(usize, Vec<usize>)] {
127        &self.assignments
128    }
129}
130
131impl Problem for MinimumCodeGenerationParallelAssignments {
132    const NAME: &'static str = "MinimumCodeGenerationParallelAssignments";
133    type Solution = Vec<usize>;
134    type Value = Min<i64>;
135
136    crate::problem_parameters![
137        ("num_variables", num_variables),
138        ("num_assignments", num_assignments),
139    ];
140
141    fn variant() -> Vec<(&'static str, &'static str)> {
142        crate::variant_params![]
143    }
144
145    fn evaluate(
146        &self,
147        config: &Self::Solution,
148    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
149        Ok({
150            let m = self.num_assignments();
151
152            // Validate config length
153            if config.len() != m {
154                return Err(crate::traits::EvaluationError::InvalidConfiguration(
155                    "assignment length does not match the internal nodes".into(),
156                ));
157            }
158
159            if config.iter().any(|&position| position >= m) {
160                return Err(crate::traits::EvaluationError::InvalidConfiguration(
161                    "assignment contains an out-of-range execution position".into(),
162                ));
163            }
164
165            // Validate permutation: all values must be distinct and in 0..m
166            let mut seen = vec![false; m];
167            for &pos in config {
168                if seen[pos] {
169                    return Ok(Min(None));
170                }
171                seen[pos] = true;
172            }
173
174            // config[i] = position of assignment i in execution order
175            // Build execution order: order[pos] = assignment index
176            let mut order = vec![0usize; m];
177            for (assignment_idx, &pos) in config.iter().enumerate() {
178                order[pos] = assignment_idx;
179            }
180
181            // Count backward dependencies: for each pair (i, j) where i < j
182            // (i executes before j), check if the target variable of order[i]
183            // is in the read set of order[j]
184            let mut count = 0usize;
185            for (i, &earlier) in order.iter().enumerate() {
186                let (target_var, _) = &self.assignments[earlier];
187                for &later in &order[(i + 1)..] {
188                    let (_, read_vars) = &self.assignments[later];
189                    if read_vars.contains(target_var) {
190                        count += 1;
191                    }
192                }
193            }
194
195            Min(Some(i64::try_from(count).map_err(|_| {
196                crate::traits::EvaluationError::IntegerOverflow(
197                    "converting parallel instruction count to i64".into(),
198                )
199            })?))
200        })
201    }
202}
203
204impl crate::solvers::BruteForceProblem for MinimumCodeGenerationParallelAssignments {
205    fn dimensions(&self) -> Vec<usize> {
206        let m = self.num_assignments();
207        vec![m; m]
208    }
209}
210
211crate::declare_variants! {
212    default MinimumCodeGenerationParallelAssignments => "2^num_assignments",
213}
214
215crate::register_brute_force! {
216    MinimumCodeGenerationParallelAssignments,
217}
218
219#[cfg(feature = "example-db")]
220pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
221    // 4 variables, 4 assignments:
222    // A_0: a <- op(b, c) -> (0, [1, 2])
223    // A_1: b <- op(a)    -> (1, [0])
224    // A_2: c <- op(d)    -> (2, [3])
225    // A_3: d <- op(b, c) -> (3, [1, 2])
226    //
227    // Optimal ordering: config [0, 3, 1, 2] means
228    // A_0 at position 0, A_1 at position 3, A_2 at position 1, A_3 at position 2
229    // Order: (A_0, A_2, A_3, A_1)
230    // Backward deps: A_0 writes a, A_1 reads a (later) -> 1
231    //                A_2 writes c, A_3 reads c (later) -> 1
232    //                Total: 2
233    let assignments = vec![(0, vec![1, 2]), (1, vec![0]), (2, vec![3]), (3, vec![1, 2])];
234    vec![crate::example_db::specs::ModelExampleSpec {
235        id: "minimum_code_generation_parallel_assignments",
236        instance: Box::new(MinimumCodeGenerationParallelAssignments::new(
237            4,
238            assignments,
239        )),
240        optimal_config: serde_json::json!(vec![0, 3, 1, 2]),
241        optimal_value: serde_json::json!(2),
242    }]
243}
244
245#[cfg(test)]
246#[path = "../../unit_tests/models/misc/minimum_code_generation_parallel_assignments.rs"]
247mod tests;
problemreductions/models/misc/minimum_code_generation_parallel_assignments.rs

problemreductions/models/misc/
minimum_code_generation_parallel_assignments.rs
