logicaffeine_compile/codegen_sva/choreography.rs
1//! **The control plane of a spatial pipeline**: the tokens and credits that make a metapipeline run, and the
2//! buffer depth that follows from them.
3//!
4//! A dataflow stage does not simply "have a buffer of depth 2". A channel between a producer and a consumer
5//! is a credit loop: the producer spends a credit to send an item, the item crosses the fabric, the consumer
6//! reads it and returns the credit, and the credit crosses back. While that loop is in flight the producer
7//! may only keep sending if it holds further credits. So the depth a channel needs to sustain one item every
8//! `II` cycles is the loop's bandwidth-delay product,
9//!
10//! ```text
11//! credits = ceil((forward latency + backward latency) / II)
12//! ```
13//!
14//! and nothing else: fewer stalls the producer, more is dead scratchpad. [`credit_depth`] is that solve,
15//! [`synthesize`] applies it per channel from the pipeline and its placement, and [`eval_credit_flow`] is the
16//! executable meaning — a cycle-exact token/credit simulation whose steady state runs at exactly `1/II` when
17//! the depth is right and stalls the moment a single credit is taken away. That two-sided property is what
18//! separates a solve from a guess, and `plasticine_choreography_lock` holds both sides over a corpus.
19//!
20//! The shipped depth is the deeper of this solve and Spatial's published writer-to-reader N-buffer rule
21//! (Koeplinger et al., PLDI 2018: a value written in stage `i` and read in stage `j` must survive `j - i + 1`
22//! stage-times), because a channel must satisfy both: enough credits to never stall, and enough buffers to
23//! keep every live value alive.
24//!
25//! Control is not free and not invisible. Every channel carries two nets — data-valid forward, space-available
26//! backward — and they are budgeted on the mesh's SCALAR network, separately from the vector network the data
27//! itself crosses, against the PCU's own control ports. An over-subscribed control plane is reported, never
28//! silently ignored. MODELED: these are the model's cycles, never a Plasticine simulation.
29
30use super::metapipeline::Metapipeline;
31use super::plasticine::PlasticineTarget;
32use super::plasticine_place::LinkBudget;
33
34/// Which way a control net runs.
35#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize)]
36pub enum ControlKind {
37 /// Data-valid, writer to reader: "an item is here".
38 Token,
39 /// Space-available, reader to writer: "a slot is free again".
40 Credit,
41}
42
43/// One control net of a channel.
44#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize)]
45pub struct ControlNet {
46 /// The channel it belongs to, always `(writer, reader)`.
47 pub edge: (usize, usize),
48 pub kind: ControlKind,
49 /// The stage it leaves and the stage it reaches (reversed from `edge` for a credit).
50 pub from: usize,
51 pub to: usize,
52 /// Mesh hops the net crosses.
53 pub hops: usize,
54}
55
56/// A credit-controlled channel between two stages.
57#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize)]
58pub struct Channel {
59 pub edge: (usize, usize),
60 /// Mesh hops between the two stages, from the placement.
61 pub hops: usize,
62 /// Producing the item and carrying it to the consumer.
63 pub forward_latency: usize,
64 /// Carrying the freed credit back.
65 pub backward_latency: usize,
66 /// Spatial's writer-to-reader N-buffer rule — the floor.
67 pub n_buffer_depth: usize,
68 /// The bandwidth-delay solve — what it takes never to stall.
69 pub credit_depth: usize,
70 /// What the channel ships: the deeper requirement.
71 pub depth: usize,
72}
73
74/// The synthesized control plane of a metapipeline.
75#[derive(Clone, Debug, PartialEq, serde::Serialize)]
76pub struct Choreography {
77 pub channels: Vec<Channel>,
78 pub nets: Vec<ControlNet>,
79 /// The pipeline's initiation interval — the rate the credits are sized for.
80 pub ii: usize,
81 /// Hops summed over every control net.
82 pub control_hops: usize,
83 /// Most control nets incident on any one stage (its control ports must carry them).
84 pub max_scalar_occupancy: usize,
85 /// The scalar links a switch provides (Spade `slink`).
86 pub scalar_link_budget: usize,
87 /// Whether the control plane fits that budget.
88 pub control_routed_statically: bool,
89}
90
91/// Credits a channel needs to sustain one item every `ii` cycles: the loop's bandwidth-delay product. A
92/// channel always holds at least one credit — without one nothing can be sent at all.
93pub fn credit_depth(forward_latency: usize, backward_latency: usize, ii: usize) -> usize {
94 let round_trip = forward_latency + backward_latency;
95 let ii = ii.max(1);
96 round_trip.div_ceil(ii).max(1)
97}
98
99/// Synthesize the control plane of `mp` given the mesh distance of each edge (`hops[i]` for `mp.edges[i]`).
100/// Forward latency is producing the item plus carrying it; backward latency is the credit's return trip.
101pub fn synthesize(
102 mp: &Metapipeline,
103 hops: &[usize],
104 t: &PlasticineTarget,
105 budget: LinkBudget,
106) -> Choreography {
107 assert_eq!(hops.len(), mp.edges.len(), "one route distance per edge");
108 let ii = mp.ii();
109 let mut channels = Vec::with_capacity(mp.edges.len());
110 let mut nets = Vec::with_capacity(2 * mp.edges.len());
111 for (i, &(w, r)) in mp.edges.iter().enumerate() {
112 let h = hops[i];
113 let forward_latency = mp.stages[w].latency + h;
114 let backward_latency = h;
115 let n_buffer_depth = Metapipeline::buffer_depth(w, r);
116 let credits = credit_depth(forward_latency, backward_latency, ii);
117 channels.push(Channel {
118 edge: (w, r),
119 hops: h,
120 forward_latency,
121 backward_latency,
122 n_buffer_depth,
123 credit_depth: credits,
124 depth: credits.max(n_buffer_depth),
125 });
126 nets.push(ControlNet {
127 edge: (w, r),
128 kind: ControlKind::Token,
129 from: w,
130 to: r,
131 hops: h,
132 });
133 nets.push(ControlNet {
134 edge: (w, r),
135 kind: ControlKind::Credit,
136 from: r,
137 to: w,
138 hops: h,
139 });
140 }
141 let mut incident = vec![0usize; mp.stages.len()];
142 for n in &nets {
143 incident[n.from] += 1;
144 incident[n.to] += 1;
145 }
146 let max_scalar_occupancy = incident.iter().copied().max().unwrap_or(0);
147 // The PCU's own control ports bound the plane as well as the switch's scalar links; a descriptor that
148 // declares control ports takes the tighter of the two.
149 let ports = t
150 .pcu_control_io
151 .map(|(i, o)| i.min(o))
152 .unwrap_or(usize::MAX);
153 let scalar_link_budget = budget.scalar_links;
154 Choreography {
155 channels,
156 nets,
157 ii,
158 control_hops: hops.iter().sum::<usize>() * 2,
159 max_scalar_occupancy,
160 scalar_link_budget,
161 control_routed_statically: max_scalar_occupancy <= scalar_link_budget.min(ports),
162 }
163}
164
165/// What a credit-flow run did.
166#[derive(Clone, Copy, Debug, PartialEq, serde::Serialize)]
167pub struct CreditRun {
168 /// Completion cycle of the last iteration.
169 pub cycles: usize,
170 /// Completion cycle of the FIRST iteration — the pipeline's fill.
171 pub fill_cycles: usize,
172 /// Cycles lost against the ideal steady state `(iters - 1) * II`. **This is the number that matters.**
173 /// Back-pressure that merely paces a fast producer down to the pipeline's rate costs nothing and is not
174 /// counted here; only credits that hold the pipeline below `1/II` are a loss.
175 pub throughput_loss: usize,
176 /// Diagnostic: issues where a credit was the binding constraint, healthy pacing included.
177 pub credit_stalls: usize,
178 pub items: usize,
179}
180
181/// Run the pipeline as a cycle-exact token/credit machine for `iters` iterations.
182///
183/// Stage `s` issues iteration `t` at the latest of: its own initiation interval since its last issue; the
184/// arrival of every input token (`issue(w, t) + forward`); and a free credit on every output channel — which,
185/// with `depth` credits outstanding, is the return of the credit spent on iteration `t - depth`
186/// (`issue(r, t - depth) + backward`). Stages are visited in edge order, a topological order of the
187/// metapipelines this models (writer < reader).
188///
189/// The verdict is [`CreditRun::throughput_loss`], not the raw stall count: a producer whose own interval is
190/// shorter than the pipeline's is *supposed* to be paced by back-pressure, and that costs nothing. A depth is
191/// right when the loss is zero and wrong the moment one credit is removed.
192pub fn eval_credit_flow(
193 c: &Choreography,
194 mp: &Metapipeline,
195 iters: usize,
196 depth_override: Option<usize>,
197) -> CreditRun {
198 let n = mp.stages.len();
199 if iters == 0 || n == 0 {
200 return CreditRun {
201 cycles: 0,
202 fill_cycles: 0,
203 throughput_loss: 0,
204 credit_stalls: 0,
205 items: 0,
206 };
207 }
208 let depth_of = |k: usize| depth_override.unwrap_or(c.channels[k].depth).max(1);
209 // issue[s][t] — the cycle stage `s` began iteration `t` (and consumed its inputs).
210 let mut issue = vec![vec![0usize; iters]; n];
211 let mut credit_stalls = 0usize;
212 for t in 0..iters {
213 for s in 0..n {
214 let ready_ii = if t == 0 {
215 0
216 } else {
217 issue[s][t - 1] + mp.stages[s].ii()
218 };
219 let ready_data = c
220 .channels
221 .iter()
222 .filter(|ch| ch.edge.1 == s)
223 .map(|ch| issue[ch.edge.0][t] + ch.forward_latency)
224 .max()
225 .unwrap_or(0);
226 let ready_credit = c
227 .channels
228 .iter()
229 .enumerate()
230 .filter(|(_, ch)| ch.edge.0 == s)
231 .map(|(k, ch)| {
232 let d = depth_of(k);
233 if t < d {
234 0
235 } else {
236 issue[ch.edge.1][t - d] + ch.backward_latency
237 }
238 })
239 .max()
240 .unwrap_or(0);
241 let without_credit = ready_ii.max(ready_data);
242 if ready_credit > without_credit {
243 credit_stalls += 1;
244 }
245 issue[s][t] = without_credit.max(ready_credit);
246 }
247 }
248 let last = n - 1;
249 let done = |t: usize| issue[last][t] + mp.stages[last].latency;
250 let (cycles, fill_cycles) = (done(iters - 1), done(0));
251 let ideal = (iters - 1) * mp.ii();
252 CreditRun {
253 cycles,
254 fill_cycles,
255 throughput_loss: (cycles - fill_cycles).saturating_sub(ideal),
256 credit_stalls,
257 items: iters,
258 }
259}