miden_processor/trace/chiplets/ace/
mod.rs

1use alloc::{collections::BTreeMap, vec::Vec};
2
3use miden_air::trace::{Challenges, MainTrace, RowIndex, chiplets::ace::ACE_CHIPLET_NUM_COLS};
4use miden_core::{Felt, ZERO, field::ExtensionField};
5
6use crate::trace::TraceFragment;
7
8mod trace;
9pub use trace::{CircuitEvaluation, NUM_ACE_LOGUP_FRACTIONS_EVAL, NUM_ACE_LOGUP_FRACTIONS_READ};
10
11mod instruction;
12#[cfg(test)]
13mod tests;
14
15pub const PTR_OFFSET_ELEM: Felt = Felt::ONE;
16pub const PTR_OFFSET_WORD: Felt = Felt::new(4);
17pub const MAX_NUM_ACE_WIRES: u32 = instruction::MAX_ID;
18
19/// Arithmetic circuit evaluation (ACE) chiplet.
20///
21/// This is a VM chiplet used to evaluate arithmetic circuits given some input, which is equivalent
22/// to evaluating some multi-variate polynomial at a tuple representing the input.
23///
24/// During the course of the VM execution, we keep track of all calls to the ACE chiplet in an
25/// [`CircuitEvaluation`] per call. This is then used to generate the full trace of the ACE chiplet.
26#[derive(Debug, Default)]
27pub struct Ace {
28    circuit_evaluations: BTreeMap<RowIndex, CircuitEvaluation>,
29}
30
31impl Ace {
32    /// Gets the total trace length of the ACE chiplet.
33    pub(crate) fn trace_len(&self) -> usize {
34        self.circuit_evaluations.values().map(|eval_ctx| eval_ctx.num_rows()).sum()
35    }
36
37    /// Fills the portion of the main trace allocated to the ACE chiplet.
38    ///
39    /// This also returns helper data needed for generating the part of the auxiliary trace
40    /// associated with the ACE chiplet.
41    pub(crate) fn fill_trace(self, trace: &mut TraceFragment) -> Vec<EvaluatedCircuitsMetadata> {
42        // make sure fragment dimensions are consistent with the dimensions of this trace
43        debug_assert_eq!(self.trace_len(), trace.len(), "inconsistent trace lengths");
44        debug_assert_eq!(ACE_CHIPLET_NUM_COLS, trace.width(), "inconsistent trace widths");
45
46        let mut gen_trace: [Vec<Felt>; ACE_CHIPLET_NUM_COLS] = (0..ACE_CHIPLET_NUM_COLS)
47            .map(|_| vec![ZERO; self.trace_len()])
48            .collect::<Vec<_>>()
49            .try_into()
50            .expect("failed to convert vector to array");
51
52        let mut sections_info = Vec::with_capacity(self.circuit_evaluations.keys().count());
53
54        let mut offset = 0;
55        for eval_ctx in self.circuit_evaluations.into_values() {
56            eval_ctx.fill(offset, &mut gen_trace);
57            offset += eval_ctx.num_rows();
58            let section = EvaluatedCircuitsMetadata::from_evaluation_context(&eval_ctx);
59            sections_info.push(section);
60        }
61
62        for (out_column, column) in trace.columns().zip(gen_trace) {
63            out_column.copy_from_slice(&column);
64        }
65
66        sections_info
67    }
68
69    /// Adds an entry resulting from a call to the ACE chiplet.
70    pub(crate) fn add_circuit_evaluation(
71        &mut self,
72        clk: RowIndex,
73        circuit_eval: CircuitEvaluation,
74    ) {
75        self.circuit_evaluations.insert(clk, circuit_eval);
76    }
77}
78
79/// Stores metadata associated to an evaluated circuit needed for building the portion of the
80/// auxiliary trace segment relevant for the ACE chiplet.
81#[derive(Debug, Default, Clone)]
82pub struct EvaluatedCircuitsMetadata {
83    ctx: u32,
84    clk: u32,
85    num_vars: u32,
86    num_evals: u32,
87}
88
89impl EvaluatedCircuitsMetadata {
90    pub fn clk(&self) -> u32 {
91        self.clk
92    }
93
94    pub fn ctx(&self) -> u32 {
95        self.ctx
96    }
97
98    pub fn num_vars(&self) -> u32 {
99        self.num_vars
100    }
101
102    pub fn num_evals(&self) -> u32 {
103        self.num_evals
104    }
105
106    fn from_evaluation_context(eval_ctx: &CircuitEvaluation) -> EvaluatedCircuitsMetadata {
107        EvaluatedCircuitsMetadata {
108            ctx: eval_ctx.ctx(),
109            clk: eval_ctx.clk(),
110            num_vars: eval_ctx.num_read_rows(),
111            num_evals: eval_ctx.num_eval_rows(),
112        }
113    }
114}
115
116/// Stores metadata for the ACE chiplet useful when building the portion of the auxiliary
117/// trace segment relevant for the ACE chiplet.
118///
119/// This data is already present in the main trace but collecting it here allows us to simplify
120/// the logic for building the auxiliary segment portion for the ACE chiplet.
121/// For example, we know that `clk` and `ctx` are constant throughout each circuit evaluation
122/// and we also know the exact number of ACE chiplet rows per circuit evaluation and the exact
123/// number of rows per `READ` and `EVAL` portions, which allows us to avoid the need to compute
124/// selectors as part of the logic of auxiliary trace generation.
125#[derive(Clone, Debug, Default)]
126pub struct AceHints {
127    offset_chiplet_trace: usize,
128    pub sections: Vec<EvaluatedCircuitsMetadata>,
129}
130
131impl AceHints {
132    pub fn new(offset_chiplet_trace: usize, sections: Vec<EvaluatedCircuitsMetadata>) -> Self {
133        Self { offset_chiplet_trace, sections }
134    }
135
136    pub(crate) fn offset(&self) -> usize {
137        self.offset_chiplet_trace
138    }
139
140    /// Encodes an ACE wire value into a bus message.
141    ///
142    /// Layout: `alpha + beta^0*clk + beta^1*ctx + beta^2*wire[0] + beta^3*wire[1] + beta^4*wire[2]`
143    #[inline(always)]
144    fn encode_ace_wire_value<E: ExtensionField<Felt>>(
145        challenges: &Challenges<E>,
146        clk: u32,
147        ctx: u32,
148        wire: [Felt; 3],
149    ) -> E {
150        challenges.encode([Felt::from_u32(clk), Felt::from_u32(ctx), wire[0], wire[1], wire[2]])
151    }
152
153    pub(crate) fn build_divisors<E: ExtensionField<Felt>>(
154        &self,
155        main_trace: &MainTrace,
156        challenges: &Challenges<E>,
157    ) -> Vec<E> {
158        let num_fractions = self.num_fractions();
159        let mut total_values = vec![E::ZERO; num_fractions];
160        let mut total_inv_values = vec![E::ZERO; num_fractions];
161
162        let mut chiplet_offset = self.offset_chiplet_trace;
163        let mut values_offset = 0;
164        let mut acc = E::ONE;
165        for section in self.sections.iter() {
166            let clk = section.clk();
167            let ctx = section.ctx();
168
169            let values = &mut total_values[values_offset
170                ..values_offset + NUM_ACE_LOGUP_FRACTIONS_READ * section.num_vars() as usize];
171            let inv_values = &mut total_inv_values[values_offset
172                ..values_offset + NUM_ACE_LOGUP_FRACTIONS_READ * section.num_vars() as usize];
173
174            // read section
175            for (i, (value, inv_value)) in values
176                .chunks_mut(NUM_ACE_LOGUP_FRACTIONS_READ)
177                .zip(inv_values.chunks_mut(NUM_ACE_LOGUP_FRACTIONS_READ))
178                .enumerate()
179            {
180                let trace_row = i + chiplet_offset;
181
182                let wire_0 = main_trace.chiplet_ace_wire_0(trace_row.into());
183                let wire_1 = main_trace.chiplet_ace_wire_1(trace_row.into());
184
185                let value_0 = Self::encode_ace_wire_value(challenges, clk, ctx, wire_0);
186                let value_1 = Self::encode_ace_wire_value(challenges, clk, ctx, wire_1);
187
188                value[0] = value_0;
189                value[1] = value_1;
190                inv_value[0] = acc;
191                acc *= value_0;
192                inv_value[1] = acc;
193                acc *= value_1;
194            }
195
196            chiplet_offset += section.num_vars() as usize;
197            values_offset += NUM_ACE_LOGUP_FRACTIONS_READ * section.num_vars() as usize;
198
199            // eval section
200            let values = &mut total_values[values_offset
201                ..values_offset + NUM_ACE_LOGUP_FRACTIONS_EVAL * section.num_evals() as usize];
202            let inv_values = &mut total_inv_values[values_offset
203                ..values_offset + NUM_ACE_LOGUP_FRACTIONS_EVAL * section.num_evals() as usize];
204            for (i, (value, inv_value)) in values
205                .chunks_mut(NUM_ACE_LOGUP_FRACTIONS_EVAL)
206                .zip(inv_values.chunks_mut(NUM_ACE_LOGUP_FRACTIONS_EVAL))
207                .enumerate()
208            {
209                let trace_row = i + chiplet_offset;
210
211                let wire_0 = main_trace.chiplet_ace_wire_0(trace_row.into());
212                let wire_1 = main_trace.chiplet_ace_wire_1(trace_row.into());
213                let wire_2 = main_trace.chiplet_ace_wire_2(trace_row.into());
214
215                let value_0 = Self::encode_ace_wire_value(challenges, clk, ctx, wire_0);
216                let value_1 = Self::encode_ace_wire_value(challenges, clk, ctx, wire_1);
217                let value_2 = Self::encode_ace_wire_value(challenges, clk, ctx, wire_2);
218
219                value[0] = value_0;
220                value[1] = value_1;
221                value[2] = value_2;
222                inv_value[0] = acc;
223                acc *= value_0;
224                inv_value[1] = acc;
225                acc *= value_1;
226                inv_value[2] = acc;
227                acc *= value_2;
228            }
229
230            chiplet_offset += section.num_evals() as usize;
231            values_offset += NUM_ACE_LOGUP_FRACTIONS_EVAL * section.num_evals() as usize;
232        }
233
234        // invert the accumulated product
235        acc = acc.inverse();
236
237        for i in (0..total_values.len()).rev() {
238            total_inv_values[i] *= acc;
239            acc *= total_values[i];
240        }
241
242        total_inv_values
243    }
244
245    fn num_fractions(&self) -> usize {
246        self.sections
247            .iter()
248            .map(|section| {
249                NUM_ACE_LOGUP_FRACTIONS_READ * (section.num_vars as usize)
250                    + NUM_ACE_LOGUP_FRACTIONS_EVAL * (section.num_evals as usize)
251            })
252            .sum()
253    }
254}
miden_processor/trace/chiplets/ace/mod.rs

miden_processor/trace/chiplets/ace/
mod.rs
