Paper VIII: Arithmetic, storage, and data movement

3 Arithmetic, storage, and data movement

On this page · Visual guide: Compute the representation first · Permalink · Source line 245

We count one scalar multiplication and one scalar addition as two modeled floating point operations. These counts describe a declared event model for a representation. They do not predict wall time without a memory and launch model. A multiply–accumulate charges two scalar operations even for the first coefficient. Thin corrections accumulate into an already computed diagonal or sparse result. Index metadata, temporary workspace, launch overhead, discovery, transfer, and materialization are accounted for separately.

Permalink · Source line 247

Theorem 3.1: Dense and packet application counts

A dense \(n\) by \(n\) matrix applied to \(q\) right hand sides has modeled cost

\[ \boxed{ {\operatorname{flop}}_{\rm dense}=2n^2q. } \]

A packet representation with active edge set \(E\) has modeled cost

\[ \boxed{ {\operatorname{flop}}_{\rm packet} = 2q \sum_{(\beta,\alpha)\in E} n_\beta n_\alpha. } \]

It stores

\[ \boxed{ M_{\rm packet} = \sum_{(\beta,\alpha)\in E} n_\beta n_\alpha } \]

scalar entries.

Read proof · Visual guide: Work removed is not time measured · Read statement and proof side by side · Permalink · Source line 249 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 3.1

The active block \(B_{\beta\alpha}\) is an \(n_\beta\) by \(n_\alpha\) matrix. Applying it to an \(n_\alpha\) by \(q\) input costs \(2n_\beta n_\alpha q\) modeled operations and stores \(n_\beta n_\alpha\) scalars. Summation over the active addresses gives both formulas.

Back to statement · Read statement and proof side by side · Permalink · Source line 278 · Claim record · Lean coverage · Code · Worked examples

Corollary 3.2: Equal diagonal packets

Let \(p\ge1\) and \(b\ge1\) be integers and \(n=pb\). Suppose \(n\) is divided into \(p\) equal diagonal packets of width \(b\). Then

\[ {\operatorname{flop}}_{\rm block}=2qnb, \qquad M_{\rm block}=nb. \]

The dense-to-block storage reduction factor is the following; the arithmetic reduction factor has the same value when \(q\ge1\):

\[ \boxed{ \frac{n}{b}. } \]

Read proof · Visual guide: Work removed is not time measured · Read statement and proof side by side · Permalink · Source line 282 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary 3.2

There are \(n/b\) active diagonal blocks. Each contains \(b^2\) entries.

Back to statement · Read statement and proof side by side · Permalink · Source line 297 · Claim record · Lean coverage · Code · Worked examples

Definition 3.3: Block diagonal plus low rank operator

A block diagonal plus low rank operator has the form

\[ A=D+UV^*, \]

where

\[ D=\bigoplus_{\alpha\in I}D_\alpha, \qquad U,V\in{\mathbb C}^{n\times r}. \]

The abbreviation BDLR will be used below.

Permalink · Source line 301 · Claim record · Lean coverage · Code · Worked examples

Theorem 3.4: BDLR application and storage

For \(q\) right hand sides,

\[ AZ=DZ+U(V^*Z) \]

has modeled cost

\[ \boxed{ 2q \left( \sum_\alpha n_\alpha^2+2nr \right). } \]

The representation stores

\[ \boxed{ \sum_\alpha n_\alpha^2+2nr } \]

scalars. For \(n=pb\), with integers \(p,b\ge1\), the ideal dense storage reduction factor is the following; the arithmetic reduction factor has the same value when \(q\ge1\):

\[ \boxed{ \frac{n}{b+2r}. } \]

Read proof · Visual guide: A dense-looking matrix, one scalar coupling · Visual guide: Work removed is not time measured · Visual guide: Close the loop on the running example · Read statement and proof side by side · Permalink · Source line 315 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 3.4

The block diagonal product costs

\[ 2q\sum_\alpha n_\alpha^2. \]

The products \(V^*Z\) and \(U(V^*Z)\) cost \(2nrq\) each. Storage consists of the diagonal blocks and the two low rank factors. For equal packets,

\[ \sum_\alpha n_\alpha^2=nb. \]

Back to statement · Read statement and proof side by side · Permalink · Source line 343 · Claim record · Lean coverage · Code · Worked examples

The ideal reduction grows with dimension only when packet width and transfer rank remain controlled.

Definition 3.5: One pass streaming model

Fix a scalar size \(s\) bytes. For every active block, the one pass streaming model reads the block once, reads its source packet once, and reads and writes its target packet once. It does not assume cache reuse across edges.

Permalink · Source line 361 · Claim record · Lean coverage · Code · Worked examples

Proposition 3.6: Streaming byte count

Under Definition 3.5, applying a packet operator to \(q\) right hand sides moves

\[ \boxed{ B_{\rm stream} = s \sum_{(\beta,\alpha)\in E} \left( n_\beta n_\alpha +n_\alpha q +2n_\beta q \right) } \]

bytes.

Read proof · Visual guide: Batch shapes, account for traffic · Read statement and proof side by side · Permalink · Source line 365 · Claim record · Lean coverage · Code · Worked examples

Proof of Proposition 3.6

The three terms count the matrix block, the source values, and the read plus write traffic for the target accumulation. The model counts these quantities independently for every active edge.

Back to statement · Read statement and proof side by side · Permalink · Source line 383 · Claim record · Lean coverage · Code · Worked examples

Definition 3.7: Arithmetic intensity

When the modeled byte traffic is strictly positive, the modeled arithmetic intensity is

\[ {\mathcal I} = \frac{{\operatorname{flop}}}{{\operatorname{bytes}}}. \]

Permalink · Source line 387 · Claim record · Lean coverage · Code · Worked examples

Theorem 3.8: Roofline lower bound

Suppose a device sustains at most \(P>0\) modeled operations per second and at most \(W>0\) bytes per second. A computation that requires \(F\) operations and \(B\) bytes satisfies

\[ \boxed{ T\geq \max\left\{ \frac{F}{P}, \frac{B}{W} \right\}. } \]

For positive elapsed time and positive byte traffic, its work rate is at most

\[ \min\{P,W{\mathcal I}\}. \]

Read proof · Visual guide: Batch shapes, account for traffic · Read statement and proof side by side · Permalink · Source line 396 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 3.8

The operation capacity gives \(T\geq F/P\). The bandwidth capacity gives \(T\geq B/W\). Both restrictions hold at once.

Back to statement · Read statement and proof side by side · Permalink · Source line 413 · Claim record · Lean coverage · Code · Worked examples

The roofline model is a guide rather than an exact execution law [WilliamsWatermanPatterson2009]. Packet structure changes both \(F\) and \(B\). An irregular representation may remove arithmetic while lowering intensity enough to become bandwidth or launch limited.

Permalink · Source line 417

A representation can move the same mathematical problem between memory limited and compute limited regimes.

Corollary 3.9: Capacity threshold

Let a device have available memory \(M\ge0\) bytes and scalar size \(s>0\), and let \(n\ge0\). The matrix representation alone can fit only when

\[ n\leq\sqrt{M/s}. \]

The equal packet BDLR representation alone fits when

\[ n(b+2r)s\leq M. \]

Read proof · Visual guide: Work removed is not time measured · Read statement and proof side by side · Permalink · Source line 426 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary 3.9

Substitute the dense and BDLR storage counts into the capacity inequality.

Back to statement · Read statement and proof side by side · Permalink · Source line 437 · Claim record · Lean coverage · Code · Worked examples

Proposition 3.10: Materialization cost

Materializing \(D+UV^*\) as an explicit matrix requires storage for \(n^2\) scalars and modeled arithmetic

\[ 2n^2r+O(n^2) \]

when the low rank correction is formed by dense multiplication.

Read proof · Read statement and proof side by side · Permalink · Source line 441 · Claim record · Lean coverage · Code · Worked examples

Proof of Proposition 3.10

The product \(UV^*\) multiplies an \(n\) by \(r\) matrix by an \(r\) by \(n\) matrix. Adding the diagonal part changes only the lower order term.

Back to statement · Read statement and proof side by side · Permalink · Source line 449 · Claim record · Lean coverage · Code · Worked examples

Source and conversion record

Source SHA-256: ef616bca9291ac766d492b88f3166be4bc2b39f9ba6034dea3a4bcf2d2bf5d7f

Unsupported prose commands stop the build. The mathematical expression sequence is checked against the source, with manuscript macros expanded for display.

Conversion records

Read and explore

Proofs and implementation

About this work

Other resources