COS Method

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

Read this chapter with formatted equations

1 \chapter{Polyphase propagation and scheduling}\label{ch:phases}
2 \chapterlead{Storage blocks say where data are held. Structural phases say where an
3 operator can send a vector. Exact zero couplings produce finite propagation
4 frontiers. Weak couplings produce a controlled leakage problem instead.
5 The scheduler must distinguish those two cases and state what knowledge of
6 the phase graph is assumed.}
7 \section{Polyphase structure}\label{sec:final-14}
8 
9 Let the phase projectors form an orthogonal decomposition of variant space:
10 \[
11 P_h^\top=P_h=P_h^2,\qquad P_hP_g=0\ (h\ne g),\qquad \sum_hP_h=I.
12 \]
13 Thus $P_h$ projects onto variant phase $h$. Again set
14 \[
15 H=A^\top A.
16 \]
17 Define the exact phase graph by
18 \[
19 g\to h
20 \quad\Longleftrightarrow\quad
21 P_hHP_g\ne0.
22 \]
23 
24 \begin{theorem}[Polyphase light cone]\label{claim:final-14-1}
25 If the graph distance from phase \(g\) to phase \(h\) exceeds \(k\), then
26 \[
27 \boxed{
28 P_hH^kP_g=0.
29 }
30 \]
31 \end{theorem}
32 
33 \begin{proof}
34 Insert the projector resolution
35 \(\sum_jP_j=I\) between successive factors of \(H\).  Every nonzero term in
36 \(P_hH^kP_g\) corresponds to a phase path of length \(k\).  If no such path
37 exists, every term vanishes.
38 \end{proof}
39 
40 
41 \begin{figure}[htbp]
42 \centering
43 \includegraphics[width=\linewidth]{figures_production/figure_04_polyphase_lightcone.pdf}
44 \caption{Active phase-depth pairs in the retained PSD chain control are filled squares. Open circles mark inactive pairs. All stored norms beyond the graph frontier are zero. The dashed boundary separates reachable phases from those that the finite-depth query cannot use.}
45 \label{fig:polyphase-lightcone}
46 \end{figure}
47 
48 \begin{theorem}[Streaming-polyphase composition]\label{claim:final-14-2}
49 At Krylov depth \(k\), an exact matrix-free iteration may omit every phase
50 outside the exact light cone.  Within each active phase, arbitrary storage
51 refinement may be used.
52 \end{theorem}
53 
54 \begin{proof}
55 The light-cone theorem removes inactive phase contributions exactly.
56 Partition-refinement invariance shows that the remaining active phase
57 operators may be streamed through any exact subpartition.
58 \end{proof}
59 
60 This is the key composition law:
61 \[
62 \boxed{
63 \text{mathematical locality}
64 \longrightarrow
65 \text{active phases}
66 \longrightarrow
67 \text{active storage blocks}.
68 }
69 \]
70 
71 
72 \section{Certified approximate light cones}\label{sec:final-15}
73 \label{sec:approx-lightcone}
74 
75 The exact light-cone theorem requires literal zero phase couplings.  Real LD,
76 annotation, and feature graphs are often only approximately sparse.  This
77 section replaces exact support by a computable phasewise envelope.
78 
79 Let the phase projectors be $P_1,\ldots,P_q$, and let $X$ be a vector or block
80 vector.  Define its phase-norm profile
81 \[
82 \rho(X)_g=\lVert P_gX\rVert_F,
83 \]
84 and define the nonnegative phase-transfer matrix
85 \[
86 \mathcal B_{hg}=\lVert P_hHP_g\rVert_2.
87 \]
88 The matrix $\mathcal B$ records the strength of every one-step phase transfer
89 without assuming that weak couplings vanish.
90 
91 \begin{theorem}[Weighted phase-transfer envelope]
92 \label{thm:weighted-transfer}
93 For every block vector $X$,
94 \[
95 \boxed{
96 \rho(HX)\leq \mathcal B\rho(X)
97 }
98 \]
99 componentwise.  Consequently, for every integer $k\geq0$,
100 \[
101 \boxed{
102 \rho(H^kX)\leq \mathcal B^k\rho(X).
103 }
104 \]
105 \end{theorem}
106 
107 \begin{proof}
108 Using $\sum_gP_g=I$ and submultiplicativity,
109 \[
110 \begin{aligned}
111 \lVert P_hHX\rVert_F
112 &=\left\lVert\sum_gP_hHP_gX\right\rVert_F\\
113 &\leq\sum_g\lVert P_hHP_g\rVert_2\lVert P_gX\rVert_F\\
114 &=(\mathcal B\rho(X))_h.
115 \end{aligned}
116 \]
117 Iteration gives the power bound.
118 \end{proof}
119 
120 Now choose a symmetric set of retained phase blocks and define
121 \[
122 H_0=\sum_{(h,g)\in\mathcal E_0}P_hHP_g.
123 \]
124 Let
125 \[
126 (\mathcal B_0)_{hg}=
127 \begin{cases}
128 \mathcal B_{hg},&(h,g)\in\mathcal E_0,\\
129 0,&\text{otherwise},
130 \end{cases}
131 \qquad
132 \mathcal R=\mathcal B-\mathcal B_0.
133 \]
134 Symmetric pair retention preserves self-adjointness of $H_0$, although the
135 following error theorem does not require positive semidefiniteness of $H_0$.
136 
137 \begin{theorem}[Thresholded-power certificate]
138 \label{thm:thresholded-power}
139 For every $k\geq1$,
140 \[
141 \boxed{
142 \rho\bigl((H^k-H_0^k)X\bigr)
143 \leq
144 (\mathcal B^k-\mathcal B_0^k)\rho(X).
145 }
146 \]
147 In particular,
148 \[
149 \boxed{
150 \lVert(H^k-H_0^k)X\rVert_F
151 \leq
152 \left\lVert(\mathcal B^k-\mathcal B_0^k)\rho(X)\right\rVert_2.
153 }
154 \]
155 \end{theorem}
156 
157 \begin{proof}
158 Write $E=H-H_0$.  The telescoping identity gives
159 \[
160 H^k-H_0^k
161 =
162 \sum_{j=0}^{k-1}H^{k-1-j}EH_0^j.
163 \]
164 The block-norm matrix of $E$ is $\mathcal R$.  Applying
165 Theorem~\ref{thm:weighted-transfer} successively to each term gives
166 \[
167 \rho\bigl((H^k-H_0^k)X\bigr)
168 \leq
169 \sum_{j=0}^{k-1}
170 \mathcal B^{k-1-j}\mathcal R\mathcal B_0^j\rho(X).
171 \]
172 The matrix telescoping identity
173 \[
174 \mathcal B^k-\mathcal B_0^k
175 =
176 \sum_{j=0}^{k-1}
177 \mathcal B^{k-1-j}(\mathcal B-\mathcal B_0)\mathcal B_0^j
178 \]
179 yields the phasewise formula.  Orthogonality of the phase projectors gives
180 \[
181 \lVert Y\rVert_F^2=\sum_h\lVert P_hY\rVert_F^2,
182 \]
183 which proves the global bound.
184 \end{proof}
185 
186 \begin{corollary}[Certified approximate light cone]
187 \label{cor:approx-lightcone}
188 Assume $X$ is supported on a set of start phases $S$.  If phase $h$ is not
189 reachable from $S$ by a retained path of length at most $k$, then
190 \[
191 P_hH_0^kX=0
192 \]
193 and
194 \[
195 \boxed{
196 \lVert P_hH^kX\rVert_F
197 \leq
198 \bigl[(\mathcal B^k-\mathcal B_0^k)\rho(X)\bigr]_h.
199 }
200 \]
201 Thus an exact zero outside the retained light cone is replaced by a certified
202 nonzero leakage budget.
203 \end{corollary}
204 
205 \begin{corollary}[Scalar threshold law]\label{claim:final-15-4}
206 For any induced matrix norm, let
207 \[
208 M=\max\{\lVert\mathcal B\rVert,\lVert\mathcal B_0\rVert\}.
209 \]
210 Then
211 \[
212 \boxed{
213 \lVert\mathcal B^k-\mathcal B_0^k\rVert
214 \leq
215 kM^{k-1}\lVert\mathcal R\rVert.
216 }
217 \]
218 Hence weak discarded coupling produces a first-order error bound proportional
219 to the discarded transfer norm and to the Krylov depth.
220 \end{corollary}
221 
222 \begin{theorem}[Krylov-polynomial certificate]
223 \label{thm:polynomial-certificate}
224 Let
225 \[
226 p(t)=\sum_{j=0}^d a_jt^j.
227 \]
228 Then
229 \[
230 \boxed{
231 \rho\bigl((p(H)-p(H_0))X\bigr)
232 \leq
233 \sum_{j=1}^d
234 |a_j|(\mathcal B^j-\mathcal B_0^j)\rho(X).
235 }
236 \]
237 \end{theorem}
238 
239 \begin{proof}
240 Apply Theorem~\ref{thm:thresholded-power} to every nonconstant power and use
241 the triangle inequality.  The constant terms cancel.
242 \end{proof}
243 
244 The theorem compares the same polynomial $p$ and the same starting block
245 $X$ under the two operators. It therefore covers fixed polynomial filters
246 and fixed linear combinations of Krylov powers, not only $H^kX$.
247 If an adaptive iteration selects different coefficients or restart vectors
248 under $H$ and $H_0$, their discrepancy requires a separate bound. The
249 fixed-polynomial certificate alone does not control that additional change.
250 
251 \begin{corollary}[Certified phase pruning]\label{claim:final-15-6}
252 If a thresholded phase graph is chosen so that
253 \[
254 \left\lVert
255 (\mathcal B^k-\mathcal B_0^k)\rho(X)
256 \right\rVert_2
257 \leq\tau,
258 \]
259 then replacing $H^kX$ by $H_0^kX$ incurs Frobenius error at most $\tau$.
260 The same statement holds for a Krylov polynomial with the certificate in
261 Theorem~\ref{thm:polynomial-certificate}.
262 \end{corollary}
263 
264 This turns graph thresholding into an error-budget decision.  A phase or
265 interface is not discarded because it merely appears small. It is discarded
266 only when the weighted sum of all paths using discarded couplings remains
267 inside the requested tolerance.
268 
269 \begin{figure}[htbp]
270 \centering
271 \includegraphics[width=\linewidth]{figures_production/figure_09_approximate_lightcone_certificate.pdf}
272 \caption{Observed propagation error and the transfer-matrix envelope in the retained PSD control. The envelope remains above the measured error at every tested depth. Shading makes the conservative margin visible without treating it as statistical uncertainty.}
273 \label{fig:approx-lightcone-certificate}
274 \end{figure}
275 
276 \begin{figure}[htbp]
277 \centering
278 \includegraphics[width=\linewidth]{figures_production/figure_10_threshold_tradeoff.pdf}
279 \caption{At Krylov depth five, retaining more off-diagonal blocks reduces both the measured truncation error and its transfer bound in this control. Lines join recorded samples. The bound ignores cancellation and singular-vector alignment, so its margin is intentionally conservative.}
280 \label{fig:threshold-tradeoff}
281 \end{figure}
282 
283 \subsection{Numerical audit}
284 
285 The validation operator has twelve phases of width four.  A block-bidiagonal
286 factor generates a positive-definite local operator $H_0$, and weak symmetric
287 long-range blocks are then added to obtain $H$.  Both normalized operators
288 remain positive definite.  A three-column start block is supported in phase
289 zero.
290 
291 For depths one through eight:
292 \begin{itemize}
293 \item every observed phase norm lay below $\mathcal B^k\rho(X)$.
294 \item every observed thresholding error lay below
295 $(\mathcal B^k-\mathcal B_0^k)\rho(X)$.
296 \item the largest total observed-error-to-certificate ratio was approximately
297 $0.669$.
298 \end{itemize}
299 
300 A separate hard-threshold sweep retained between $22$ and $132$ directed
301 off-diagonal phase blocks.  Every measured depth-five error remained below its
302 certificate. The largest observed-error-to-certificate ratio was approximately
303 $0.376$.  Finally, a degree-four signed polynomial in $H$ satisfied the
304 phasewise polynomial certificate in all twelve phases, with maximum ratio
305 approximately $0.068$.
306 
307 These computations validate the implementation and illustrate sharpness.  The
308 universal result is supplied by the preceding proofs, not by the finite test.
309 
310 
311 
312 \section{Certified budget-optimal phase scheduling}\label{sec:final-16}
313 \label{sec:budget-scheduler}
314 
315 The preceding section answers a validation question: given a retained phase
316 operator $H_0$, how large can the Krylov error be?  This section turns that
317 certificate into a selection rule.  The goal is to remove as much phase
318 communication as possible while remaining inside a prescribed error budget.
319 
320 Let $\mathcal E$ denote the set of undirected off-diagonal phase pairs.  Because
321 $H$ is self-adjoint, $\mathcal B$ is symmetric.  For a phase pair
322 $e=\{h,g\}$ define the nonnegative matrix $\Delta_e$ by
323 \[
324 (\Delta_e)_{hg}=\mathcal B_{hg},\qquad
325 (\Delta_e)_{gh}=\mathcal B_{gh},
326 \]
327 with every other entry zero.  If $\mathcal O\subseteq\mathcal E$ is the set
328 of omitted pairs, define
329 \[
330 \mathcal B_{\mathcal O}
331 =\mathcal B-\sum_{e\in\mathcal O}\Delta_e.
332 \]
333 The diagonal is always retained. The corresponding pruned operator is
334 \[
335 H_{\mathcal O}
336 =H-\sum_{\{h,g\}\in\mathcal O}
337 \bigl(P_hHP_g+P_gHP_h\bigr).
338 \]
339 Thus $\mathcal B_{\mathcal O}$ is its block-norm transfer matrix.
340 
341 For depth $k\ge1$ and starting phase profile $\rho_0=\rho(X)$, define the
342 \emph{edge risk vector}
343 \[
344 \boxed{
345 q_e^{(k)}
346 =
347 \sum_{j=0}^{k-1}
348 \mathcal B^{k-1-j}\Delta_e\mathcal B^j\rho_0
349 }
350 \]
351 and its scalar risk
352 \[
353 \boxed{
354 \beta_e^{(k)}=\lVert q_e^{(k)}\rVert_2.
355 }
356 \]
357 Unlike the raw block norm $\mathcal B_{hg}$, this quantity depends on the
358 start profile and on Krylov depth.
359 
360 \begin{theorem}[Edge-additive leakage majorant]
361 \label{thm:edge-additive-majorant}
362 For every omitted set $\mathcal O\subseteq\mathcal E$,
363 \[
364 \boxed{
365 0\le
366 (\mathcal B^k-\mathcal B_{\mathcal O}^k)\rho_0
367 \le
368 \sum_{e\in\mathcal O}q_e^{(k)}
369 }
370 \]
371 componentwise.  Consequently,
372 \[
373 \boxed{
374 \lVert(H^k-H_{\mathcal O}^k)X\rVert_F
375 \le
376 \left\lVert
377 (\mathcal B^k-\mathcal B_{\mathcal O}^k)\rho_0
378 \right\rVert_2
379 \le
380 \sum_{e\in\mathcal O}\beta_e^{(k)}.
381 }
382 \]
383 \end{theorem}
384 
385 \begin{proof}
386 The first inequality in the second display is
387 Theorem~\ref{thm:thresholded-power}.  For the transfer matrices, the exact
388 noncommutative telescoping identity is
389 \[
390 \mathcal B^k-\mathcal B_{\mathcal O}^k
391 =
392 \sum_{j=0}^{k-1}
393 \mathcal B^{k-1-j}
394 (\mathcal B-\mathcal B_{\mathcal O})
395 \mathcal B_{\mathcal O}^j.
396 \]
397 All matrices and $\rho_0$ are nonnegative, and
398 $0\le\mathcal B_{\mathcal O}\le\mathcal B$ entrywise.  Hence
399 \[
400 \mathcal B_{\mathcal O}^j\rho_0
401 \le
402 \mathcal B^j\rho_0.
403 \]
404 Substituting
405 \[
406 \mathcal B-\mathcal B_{\mathcal O}
407 =
408 \sum_{e\in\mathcal O}\Delta_e
409 \]
410 and distributing the sum gives the componentwise majorant.  The final scalar
411 bound follows from the Euclidean triangle inequality.
412 \end{proof}
413 
414 \begin{corollary}[Polynomial edge-risk certificate]\label{claim:final-16-2}
415 Let
416 \[
417 p(t)=\sum_{d=0}^{D}a_dt^d.
418 \]
419 Define
420 \[
421 q_e^{(p)}
422 =
423 \sum_{d=1}^{D}|a_d|q_e^{(d)},
424 \qquad
425 \beta_e^{(p)}=\lVert q_e^{(p)}\rVert_2.
426 \]
427 Then
428 \[
429 \boxed{
430 \lVert(p(H)-p(H_{\mathcal O}))X\rVert_F
431 \le
432 \sum_{e\in\mathcal O}\beta_e^{(p)}.
433 }
434 \]
435 Thus the same scheduling machinery applies to finite Krylov combinations and
436 polynomial filters.
437 \end{corollary}
438 
439 \begin{corollary}[Query-invisible phase pair]\label{claim:final-16-3}
440 If
441 \[
442 \Delta_e\mathcal B^j\rho_0=0
443 \qquad
444 \text{for every }0\le j<k,
445 \]
446 then
447 \[
448 \beta_e^{(k)}=0.
449 \]
450 Therefore a phase pair can be large in operator norm and still have zero
451 risk for a particular finite-depth query.  A magnitude-only threshold cannot
452 represent this distinction.
453 \end{corollary}
454 
455 \subsection{Equal-cost optimality}
456 
457 Suppose each retained phase pair has the same communication or scheduling
458 cost, and fix a budget $\tau\ge0$. Under the additive certificate, a set of
459 omitted pairs is feasible if
460 \[
461 \sum_{e\in\mathcal O}\beta_e^{(k)}\le\tau.
462 \]
463 Sort the risks as
464 \[
465 \beta_{(1)}\le\beta_{(2)}\le\cdots\le\beta_{(N)}.
466 \]
467 
468 \begin{theorem}[Cardinality-optimal certified pruning]
469 \label{thm:unit-cost-optimal}
470 Let $r\in\{0,\ldots,N\}$ be the largest integer satisfying
471 \[
472 \sum_{i=1}^{r}\beta_{(i)}\le\tau.
473 \]
474 Then omitting the $r$ least-risk phase pairs is feasible, and no feasible
475 omitted set can contain more than $r$ pairs under the scalar additive
476 certificate.
477 \end{theorem}
478 
479 \begin{proof}
480 If $r=N$, every candidate pair can be omitted and optimality is immediate.
481 Otherwise, among all subsets of cardinality $r+1$, the smallest possible sum
482 of risks is
483 \[
484 \sum_{i=1}^{r+1}\beta_{(i)}.
485 \]
486 By maximality of $r$, that sum exceeds $\tau$.  Hence no set of $r+1$ omitted
487 pairs is feasible.  The prefix of length $r$ is feasible by construction.
488 \end{proof}
489 
490 Optimality is relative to the scalar additive certificate, not to the actual
491 operator error or to every tighter certificate. The exact transfer envelope
492 can leave additional slack.
493 
494 \subsection{Exact-envelope refinement}
495 
496 After the cardinality-optimal additive schedule is found, recomputing
497 \[
498 \left\lVert
499 (\mathcal B^k-\mathcal B_{\mathcal O}^k)\rho_0
500 \right\rVert_2
501 \]
502 may reveal unused budget.  Additional pairs can then be removed one at a time,
503 provided the exact transfer envelope remains below $\tau$.
504 
505 \begin{proposition}[Certified refinement]\label{claim:final-16-5}
506 Any sequence of additional omissions accepted only when
507 \[
508 \left\lVert
509 (\mathcal B^k-\mathcal B_{\mathcal O}^k)\rho_0
510 \right\rVert_2\le\tau
511 \]
512 remains a valid $\tau$-certificate for the original operator error.
513 \end{proposition}
514 
515 The refinement rule used in the reference implementation chooses, among all
516 currently feasible next omissions, the pair that produces the smallest
517 increase in the exact transfer envelope.  It is certified but is not claimed
518 globally optimal.
519 
520 \subsection{Unequal communication costs}
521 
522 Let $c_e\ge0$ denote the communication or storage cost saved by omitting pair
523 $e$.  Under the scalar additive certificate, the exact discrete selection
524 problem is
525 \[
526 \boxed{
527 \max_{x_e\in\{0,1\}}
528 \sum_e c_ex_e
529 \quad\text{subject to}\quad
530 \sum_e\beta_e^{(k)}x_e\le\tau.
531 }
532 \]
533 This is the $0$--$1$ knapsack problem.  Hence unequal-cost scheduling is
534 combinatorial in general.  The implementation supplies a safe
535 cost-to-risk greedy heuristic. Its output remains certified because it never
536 exceeds the additive risk budget.  A fractional-knapsack relaxation supplies
537 an upper bound on the maximum possible saved cost.
538 
539 \begin{figure}[htbp]
540 \centering
541 \includegraphics[width=\linewidth]{figures_production/figure_11_budget_scheduler_comparison.pdf}
542 \caption{Query-aware schedulers omit more phase pairs than a global norm threshold in this depth-five control. Envelope refinement uses slack left by the additive bound. The figure compares retained schedules, not measured execution times or a universal optimality claim.}
543 \label{fig:budget-scheduler-comparison}
544 \end{figure}
545 
546 \begin{figure}[htbp]
547 \centering
548 \includegraphics[width=\linewidth]{figures_production/figure_13_edge_risk_vs_block_norm.pdf}
549 \caption{Block norm and query-dependent risk for each phase pair in the retained control. Adjacency is distinguished by both marker and color. The query risk includes the start profile and finite-depth transfer paths, information absent from the block norm alone.}
550 \label{fig:edge-risk-vs-norm}
551 \end{figure}
552 
553 \subsection{Numerical audit}
554 
555 The twelve-phase operator from Section~\ref{sec:approx-lightcone} was reused at
556 Krylov depth five.  There are $66$ undirected off-diagonal phase pairs.
557 For error budgets $10^{-3}$, $2\times10^{-3}$, $5\times10^{-3}$, and
558 $10^{-2}$, the additive-optimal scheduler retained respectively
559 $61$, $56$, $45$, and $36$ pairs.  Exact-envelope refinement reduced those
560 counts further to
561 $58$, $50$, $36$, and $30$ pairs while remaining inside budget.
562 
563 In the same test, the best single global threshold on the raw block norm
564 retained $65$ pairs at every one of those four budgets.  The difference is
565 structural: the global threshold is blind to start phase and Krylov depth.
566 
567 A separate six-phase problem contains $15$ candidate phase pairs, so all
568 $2^{15}=32768$ subsets can be enumerated.  At four distinct budgets, the
569 sorted-risk scheduler matched the brute-force cardinality optimum under the
570 additive certificate in every case.  The exact-envelope greedy refinement also
571 matched the brute-force exact-envelope optimum in cardinality for all four
572 budgets in this finite audit.  The latter agreement is empirical and is not
573 promoted to a theorem.
574 
575 For an unequal-cost eight-phase test, costs were proportional to the bytes in
576 symmetric dense phase blocks.  The cost-to-risk heuristic saved $5408$ bytes
577 out of a $9472$-byte communication proxy while using additive risk $0.011632$
578 under budget $0.012$.  The fractional relaxation upper bound was $5647.8$
579 bytes, placing the greedy schedule within about $4.25\%$ of that relaxation
580 bound on this instance.
581 
582 
583 \section{Asynchronous double-buffer execution model}\label{sec:final-17}
584 \label{sec:double-buffer}
585 
586 The mathematical streaming identities do not require transfers and GEMMs to be
587 serial.  Consider $B$ storage blocks.  Let $t_b$ be the transfer time for block
588 $b$ and $c_b$ its device compute time.
589 
590 \begin{proposition}[Ideal two-buffer pipeline]\label{claim:final-17-1}
591 In a model with perfect asynchronous overlap, transfer of block $b+1$ may run
592 while block $b$ is being processed.  The serial one-buffer time is
593 \[
594 T_{\rm serial}=\sum_{b=1}^{B}(t_b+c_b),
595 \]
596 whereas the two-buffer pipeline time is
597 \[
598 \boxed{
599 T_{\rm pipe}
600 =
601 t_1
602 +
603 \sum_{b=1}^{B-1}\max\{c_b,t_{b+1}\}
604 +
605 c_B.
606 }
607 \]
608 For uniform times $t_b=t$ and $c_b=c$,
609 \[
610 T_{\rm pipe}=t+c+(B-1)\max\{t,c\}.
611 \]
612 \end{proposition}
613 
614 \begin{proof}
615 After the first block arrives, every interior pipeline stage finishes only when
616 both the current computation and the next transfer have completed.  Their
617 joint stage duration is therefore the maximum of those two times.  The initial
618 transfer and final compute cannot be hidden and form the two boundary terms.
619 \end{proof}
620 
621 If one resident block uses $M_{\rm block}$ bytes and all other fixed working
622 state uses $M_{\rm fixed}$ bytes, the corresponding memory models are
623 \[
624 M_{\rm single}=M_{\rm fixed}+M_{\rm block},
625 \qquad
626 \boxed{
627 M_{\rm double}=M_{\rm fixed}+2M_{\rm block}.
628 }
629 \]
630 The proposition is a scheduling model, not a hardware timing claim.  PCIe or
631 NVLink contention, kernel launch overhead, synchronization, page pinning, and
632 library workspaces can reduce realized overlap.
633 
634 \begin{figure}[htbp]
635 \centering
636 \includegraphics[width=\linewidth]{figures_production/figure_12_double_buffer_model.pdf}
637 \caption{Modeled wall time for five per-block I/O and compute settings, with 64 blocks in each case. The vertical labels specify I/O time followed by compute time. Connected points compare single and double buffering. These are model predictions, not accelerator measurements.}
638 \label{fig:double-buffer-model}
639 \end{figure}
640 
641 

Back to source controls

Back to COS Method