LATENCY — what signed-digit units cost wired together

The object: units, operators that read signed-digit streams and write one, wired so that a unit reads another's output. A unit alone is priced on REDUNDANT: The many-stream theorem, whose vocabulary this page keeps: a cell (b, a⁻, a⁺), the digits D = {−a⁻, …, a⁺} in radix b at slack ρ = a⁻ + a⁺ + 1 − b ≥ 1; a stream is an infinite string of D worth a real in [−M⁻, M⁺], M± = a±/(b − 1), M̂ = max(M⁻, M⁺) and w = M⁻ + M⁺; n digits confine it to a box w/b^n wide; a unit writes with a lead o, its root tile holding its range, at a delay L, the digits it reads before committing one, counted from the lead; by the tile lemma it is dead iff some box's image strictly contains a zone, the w − 1 long overlap of two consecutive output tiles; and its floor, the least delay it reads at, is the margin law's L* at Λ for a curved map and at most L* for an affine one, Λ the sup of its gradient's 1-norm, here its box width rate: a box w/b^n wide has an image at most Λw/b^n wide. A unit reading two streams waits for the later, so a wiring costs its latency, the largest sum of delays along a path from a fresh stream to the output. This page prices units in series (the chained delay, the threshold-miss law, the matching law) and in trees, and gives one entry point reading a unit's delay.

The chained delay

Tier: theorem.
Verifier: proof; chains.py::section_ca, chains.py::section_cb.

Units wired in series: a producer is the unit whose output stream the next unit reads, here one reading x and y and emitting the digits of U = x y as a D-stream, and a consumer reads U and a fresh stream z, digit n of each together. A chain at delays (L₁, L₂) pays L₁ + L₂ in the inputs. The literature prices a series by that sum: "for a series of online operations, the overall latency is the sum of online delays of the corresponding operation" (Usman, Ercegovac and Lee, J. Signal Processing Systems 95, 2023, section 4.2.2). A consumer that knows the producer's selector, its rule for choosing a digit where two are legal, might read more from a prefix of U than its box. Wherever a± ≤ b − 1 and the root tile at lead 0 holds U's range, (a⁻)² ≤ a⁺(b − 1) (the cell is representable), that buys the adder U + z no digit, at every radix: the sum of the two floors is the chain's floor, whatever the selector.

The hull. What the consumer knows of x y is the fibre of the prefix it has seen, every value of x y the producer's selector sends to that prefix, and its tiles are intervals, so it reads the fibre only through its hull: an interval inside U's box, inset by α at the bottom and β at the top. By the tile lemma the adder is dead at L₂ iff an integer lies in

((b^L₂ − 2)M⁺ + β,  b^L₂ − (b^L₂ − 2)M⁻ − α),

the sum x + z's clause (REDUNDANT: The many-stream theorem, k = 2) with U's box shortened. Its escape cost E(L₂) is the least α + β that empties that interval. The budget is what the producer can spend on insets: its images at level n + L₁ are up to 2M̂w/b^L₁ wide in level-n units near the product's corner, where they are dense, so hulls there must overlap by that much in the limit of depth, and

α + β ≤ S(L₁) = (w − 1) − 2M̂w/b^L₁,

exactly the condition for a reader into tiles narrowed by α below and β above, with the same digits and zones w − 1 − α − β long, to read x y at L₁. So the chain lives at (L₁, L₂) when E(L₂) ≤ S(L₁) and the narrowed root tile still holds U's range at lead 0, and is predicted dead when E(L₂) > S(L₁), the inset law. The budget puts one hull at each value; past level 1 strings of U that share a value carry hulls of their own, and can beat it behind z·U (the threshold-miss law).

Proof. Below L₁* the producer is dead, and below the adder's lead 1 its first digit must hold a hull plus z's root box, longer than any tile. At L₂ = 1 a hull [h₀, h₁] of the box at 0 passes the clause iff no integer lies in (a⁺ − h₁, b − a⁻ − h₀), that is iff it lies in [k, k + ρ] for an integer k. The clause is 2w − b^L₂(w − 1) long, at most 0 for L₂ ≥ 2 or ρ ≥ 3; at ρ = 2 its ends sit s/(b − 1) and (s + 2)/(b − 1) above one integer, s = b − 1 − a⁺ in [0, b − 3] as a± ≤ b − 1. So the one pair below the sum is (L₁*, 1) at slack 1, where every hull the adder accepts lies in an aligned interval [k, k + 1] of its level: the values sent to a prefix of U at level n must lie between consecutive multiples of b^−n. x y cannot. With y in its box at depth 1 + L₁ at the corner of largest magnitude and x in each box from there to 0, the images' starts step less than their widths (w > 1), and their union runs from below 1/b to M̂² ≥ b²/(4(b − 1)²) > 1/b, so one image holds 1/b strictly inside and is homeless: no hull the adder accepts holds it, however many prefixes share a value. So (L₁, 1) is dead at every L₁, and (L₁*, L₂*) lives, the producer's and the adder's floors. Section CB checks it to radix 60: 1,770 slack-1 cells, 34,220 of slack 2 or more, and 4,364 pairs of a representable slack-1 cell and L₁* ≤ L₁ ≤ L₁* + 3, each image homeless.

The fused unit x y + z reads below the chain at 9 of the 13 representable cells of radices 2 to 5 and level with it at the 4 where the product's own floor is 1: against it the chain costs the fusion forgone, not the multiplier's choices. Where U needs a lead the led chain is not priced.

The threshold-miss law

Tier: rule (the gain proved, by the budget bounded by the producer's room and past it by a tree of hulls; the budget's converse false; the silence at slack 2 or more, a± ≤ b − 1, open); pattern (the product-fed gain set at slack 1 is the tree of hulls' over the 441 representable cells with M̂ < 1, radices 3 to 40, on limits derived, not proved).
Verifier: chains.py::section_cc, hulls.py::section_tree, hulls.py::main, lattice.py::section_sweep, floor.py::section_sweep, floor.py::section_far, floor.py::section_honest, floor.py::section_fixed.

A product consumer z·U, U a stream and τ = sup|U|, can beat the sum. Reading U through a hull inset by η, its image of a z box times a hull is at most (τw + M̂(w − η))/b^n wide, so it reads at L₂ wherever τw + M̂(w − η) ≤ b^L₂(w − 1): its box width rate is Λ₂ = τ + M̂, and escaping costs it the miss of its own threshold read in the producer's coordinate, E₂(L₂) = (Λ₂w − b^L₂(w − 1))⁺/M̂. At a signed slack-1 cell (a± ≥ 1, so M̂ ≤ 1), w − 1 = w/b, so the consumer's floor L₂* is 1 when Λ₂ ≤ 1 and 2 when Λ₂ > 1, and the one pair that can read below the sum is (L₁*, L₂* − 1). With [lo, hi] the producer's range, the chain reads one digit below the sum if

0 < Λ₂ − 1 ≤ (M̂/w)·min(S(L₁*), (M⁻ + lo) + (M⁺ − hi)):

the threshold missed by at most the producer's budget, itself O(1/b), bounded by its room, the second term: the most a narrowed reader may inset in total and still hold that range in its root tile at lead 0. The room binds often and moves no verdict to radix 40.

Behind a product, τ = M̂² and Λ₂ = 1 falls at M̂ = 1/φ, φ the golden ratio. The law finds the gains to radix 40 at the slack-1 cells whose M̂, a multiple of 1/(b − 1), falls in the O(1/b) range above it: 2/3 at radix 4, 5/8 at 9, 17, 25 and 33, 7/11 at 12, 13/21 at 22, 18/29 at 30 and 23/37 at 38, 17 cells with their mirrors. At (4, 2, 2), (x y)·z reads at 3 against the naive sum 4, the units' floors added. Behind a sum x + y read at lead 1, τ = 2M̂/b and the producer's budget, S(L₁*) above, is (w − 1) − (2w − 1)/b^L₁, capped by the producer's room, its images on a lattice of pitch 1/b^L₁. Λ₂ = 1 falls at the rational b/(b + 2), and the cell (b, 2, b − 2) and its mirror gain at every radix from 5 to 40, 72 cells; on the lattice a tree of hulls finds no more (lattice.py 40). The budget predicts no gain for either consumer at a cell of slack 2 or more with a± ≤ b − 1 where the root tile at lead 0 holds the ranges of U and z·U, to radix 40.

The budget's converse is false. In a tree of hulls each string's children, one per integer, cover its interval so that every window of width d = 2M̂w/b^L₁ lies in one, their offsets drifting down in their boxes by 1 + d − F as a hull F narrows below the budget's 1 + d, the drift reset at the next parent. A producer sending each image to a child holding it is legal, and z·U accepts any hull at most w − E₂(L₂) wide. hulls.py builds a greedy tree of hulls on a grid, its certificate checked exactly: at (20, 8, 12) and its mirror, (x y)·z reads at 3 against the naive 4, where the budget says dead. On the grid of step 1/(1000(b − 1)) to radix 40 (hulls.py 1000 40) its least width, an upper bound on the tree's, is below 1 + d at 440 of the 441 representable slack-1 cells with M̂ < 1, level at (10, 6, 4), and it certifies 19 live.

A lower bound on the hull widths prices the other 422 (floor.py 200 40). Near the product's corner a producer's strings hold whole private zones, the starts one digit's children alone reach, b − 2 at a time, so on the limits named below, at unbounded depth some hull lying a distance δ below the corner (δ here a distance, not a lattice step) is at least F = 1 + d′ − (w − 1 − d′)/(b − 2) − ((b − 1)/(b − 2))(d − d′)/w, d′ = d√(1 − δ/M̂²) the images' least width there, and z·U at L₂ = L₂* − 1, z near its extreme, kills a fibre wider than w − E₂(L₂) + δw/M̂. Tracked at exact widths, the corner cycles in zones (δ → 0) or falls into an overlap (δ ≤ 1/(9b)); F clears that width at all 274 cells with L₂* = 2 outside the 19, by 0.0062 or more, and at none of the 19; at the 148 with L₂* = 1, w − E₂(0) < 0. So over those 441 cells the product-fed gain set is the tree of hulls' 19, on limits derived and not proved: images dense δ below the corner, their starts' gaps under (d − d′)/w once the diagonals overlap (at most 0.94 of the bound taken at δ + ϑ, ϑ = 4M̂/b^(L₁ + n) the level's tolerance, printed at four cells, one δ each), a cycling corner's deficits falling past the levels run (read off the last cycle's prints), and the consumer's sweep dense with depth.

The matching law

Tier: rule (the least total an upper bound on the floor, and at slack 1 reached greedily and the naive sum less ν outside the adjacent range, proved; naive − ν checked to radix 200 behind a product, greedy least to 40, both heads; not the floor at the two-unit chain at (20, 8, 12)).
Verifier: chains.py::section_cd, chains.py::section_cg.

A chain of units, a head reading fresh streams alone and emitting a stream of largest magnitude τ₁ (M̂² for a product, 2M̂/b for a sum read at lead 1), then product consumers numbered from 2, consumer j reading a stream of largest magnitude τ_(j−1) = τ₁M̂^(j−2), its box width rate Λ_j = M̂ + τ_(j−1), is priced link by link by the threshold-miss reading: a consumer below its floor spends its producer's leftover, and one at its floor hands on its own, S_j = (w − 1) − (Λ_jw − M̂η)/b^(L_j), L_j its L and η the inset of the hull it reads its producer through, bounded by its range's room. The least total over every assignment of delays is an upper bound on the chain's floor, proved by the narrowed reader; a tree of hulls beats it at (20, 8, 12) (the threshold-miss law).

At slack 1 the least total is reached greedily, each unit at the least delay alive on what its producer hands it, and is the units' floors less ν, the size of a maximum matching of the path's gains, the links (j − 1, j) at which unit j reads one below its floor on the floor chain, every unit at its floor, outside the adjacent range of the downstream miss Λ_j − 1 at a link between two consumers (j ≥ 3), 0 < w(Λ_j − 1) < M̂(M̂(w − 1) − w(Λ_(j−1) − 1))/b, about M̂²/b² wide.

Proof. Greedy: of two states of a prefix, totals t < t′ and leftovers v, v′, the first answers a move of the second at L with one at L + 1 and keeps as much, b^(L+1) times the difference being (b − 1)Λw − bM̂v′ + M̂v > 0 as v′ ≤ w − 1 = w/b. At M̂ = 1 no link gains, every miss w(Λ_j − 1)/M̂ exceeding w − 1, so let M̂ < 1. The first gain: Λ_j never rises along the chain and a unit below its floor sits at L = 1 with Λ_j > 1, so every consumer above a gain sits at floor 2; its leftover at zero inset and its room rise down the chain, each consumer scaling its producer's range by M̂, and either head's budget lies below them. So a crossed gain, one its producer's leftover at zero inset misses, has its miss w(Λ_j − 1)/M̂ within M̂w/b³ of any gain's above it, while consecutive misses differ by more than w(1 − M̂)²/M̂² ≥ w/(M̂²(b − 1)²): it is its chain's first gain. Upper: each matched link's downstream unit one below its floor and every other unit at its floor is alive, a crossed gain's producer reading the floor chain. Lower: call a unit low below its floor and high above it; any assignment costs at least the naive sum less the low count plus the high count. Outside the adjacent range no two low units are neighbours, a low unit keeping less than (M̂(w − 1) − w(Λ_j − 1))/b. Charge each low unit to the nearest unit above it off its floor when that one is high, which no other low unit charges; else its producer hands it at most the floor chain's leftover, a low unit keeping less than one at its floor, so its link is a gain, and these links are disjoint: the low count is at most ν plus the high count.

Crossed gains are rare: over every prefix of each representable slack-1 chain behind a product with M̂ < 1 and S(L₁*) ≥ 0, its floor-2 run and one unit more, radices 3 to 200 (chains.py --cg200), four links, unit 34 of (31, 3, 28), 74 of (29, 2, 27), 140 of (46, 2, 44) and 152 of (91, 3, 88). Gains read at zero inset miss the greedy total by one at 36 of the 264,301 prefixes read outside the adjacent range, all at those cells: 34 units at (31, 3, 28) read 67 against 68. Over 12,242 chains, slack-1 cells of radices 3 to 40 at 3 to 12 units and along each finite run of floor-2 consumers to radix 24, greedy is the least over the delays L₁* to L₁* + 2 at the head and L_j* − 1 to L_j* + 2 at each consumer, naive − ν outside the adjacent range, and one below it at 49 inside, among them a five-unit chain behind a sum at (9, 2, 7), 7 against the matching's 8, two adjacent misses bunching within O(1/b²). Non-adjacent gains add: the four-unit chain behind a sum at (b, 2, b − 2) reads two below the naive sum at every radix from 8 to 40.

Trees of units

Tier: property (the fan-in leftover and the tree pass, proved, an upper bound on the floor as on a chain); rule (the gain cells, verified over the 441 representable slack-1 cells with M̂ < 1, radices 3 to 40, against chains behind a product head of 2 to 12 units).
Verifier: proof; graphs.py::build, graphs.py::main.

In a tree of units each product unit reads two streams U and V, each fresh or produced by a unit of its own subtree, and no stream is read twice. On a chain the latency is the sum the chain laws price. The naive latency puts every unit at its floor.

The fan-in leftover. Let U and V reach unit j through hulls inset by η_U and η_V (0 for a fresh stream), of largest magnitudes τ_U and τ_V. Over hulls of widths h_U and h_V, |u₁v₁ − u₂v₂| ≤ τ_V h_U + τ_U h_V, with no cross term, so by the tile lemma j reads at L into its tiles narrowed by η wherever η ≤ v_j, its leftover,

v_j = (w − 1) − (Λ_j w − τ_V η_U − τ_U η_V)/b^L,  Λ_j = τ_U + τ_V,

and hands on min(v_j, its room), alive where v_j ≥ 0: the threshold-miss reading, with one fresh input the chain's. ∎ A product consumer reads a produced stream only through its hull's width, never the split of its inset into α and β, so in this programme one inset serves every reader of a stream.

The tree pass. v_j rises in L and in each inset. So B_j(t), the most a subtree can hand at latency at most t, is the larger over L of min(v_j, room) on the inputs' B(t − L), a fresh input handing 0 at every t ≥ 0; the least t at which the root is alive is the programme's least latency, read in one pass up the tree over latencies up to the naive one. ∎ An input that arrives early is read at its best leftover at the later latency, so slack between siblings is spent by the pass itself.

A tree of units carries new pairs of input magnitudes. A unit's τ is M̂^d, d its count of fresh leaves, so a product unit reads with Λ = M̂^(d_U) + M̂^(d_V), and gains where that lies just above 1 (from floor 2 to delay 1) or just above 1/b (from floor 1 to delay 0), delays read at L ≥ 0 as the pass searches them. A chain's consumers read pairs (1, d); a tree of units reads any. At (8, 3, 5), M̂ = 5/7 and w = 8/7: P = (x y)(x′ y′) has Λ = 2M̂² = 50/49 (floor 2); each head at L₁* = 2 hands S = 1/7 − (80/49)/64 = 23/196, its room 16/49 not binding; at L = 1 the root needs τ_V η_U + τ_U η_V ≥ w(Λ − 1), and (50/49)(23/196) ≈ 0.1197 against 8/343 ≈ 0.0233, so P reads at 2 + 1 = 3 against the naive 4. The two-unit chain there misses its threshold by M̂ + M̂² − 1 = 11/49.

P reads one below its naive latency at 12 cells, and at 10 no chain behind a product head of 2 to 12 units gains in its programme: (8, 3, 5), (15, 5, 10), (19, 6, 13), (22, 7, 15), (25, 8, 17), (26, 8, 18), (29, 9, 20), (32, 10, 22), (36, 11, 25) and (39, 12, 27); chains reach the other two, (5, 2, 3) and (12, 4, 8). ((x y) z)((x′ y′) z′) gains at 26 cells, 2 outside those chains, (35, 8, 27) and (40, 9, 31). Slack spent on an early sibling buys a cell over the sibling held at its floor, (6, 2, 4) in ((x y) z)(x′ y′), which a chain reaches too. None of these three trees, nor the two-unit chain, gains two.

Reading a unit's delay

REDUNDANT's laws and this page's as one entry point, delays.py. Given a radix, a digit set and a unit, it returns the lead, L* and the lookahead: for a unit by its box width rate and range (delays.py::unit), and for six standard units, three with a pole at distance h, with the relative-gradient estimate beside each (delays.py::table); for a map of several streams by its exact image, the output depths at which a scan finds a reader at L* − 1, and one at L*, dead (delays.py::certify); for a piecewise map its floor, or none when it still reads four digits below L* (delays.py::piecewise); for a unit feeding a second, the naive sum and the least total the chain laws admit, nothing where they have no word, as for x y's chains where its range misses the root tile at lead 0 (delays.py::chains). It adds no claim.

Open fronts

The chained delay's floor rides the hull being an interval. Is there a per-unit summary that prices a composition whose fibres are not intervals? Can a producer's ambiguity be removed while its lookahead is kept? Is convexity in a value necessary, or sufficient, for a consumer, under some order on the alphabet?

What is the least hull a tree of hulls sustains, and which cells gain by it at every radix? Do the limits under the floor that prices its dead cells admit a proof: images dense a fixed distance below the corner, their gaps under (d − d′)/w, a cycling corner's deficits falling, and the consumer's dense sweep? Does a tree of hulls beat the matching law at two links? At slack 1 and one digit set two neighbouring units read below their floors together only inside the adjacent range; where each unit carries its own digit set, can they outside it, and can three in a row? Does a cell of slack 2 or more gain twice along a chain, or gain at all past radix 40?

A tree of units is priced by one pass; is a general graph of product units at one cell polynomial or hard? Abstracted to floors, a unit one below its floor only where it gains and no two neighbouring units low, a reduction from satisfiability of three-literal clauses might make the latency hard; it would need two gaining units on one path. The two gain windows allow that even where one pair of leaf counts sits just above 1: a unit downstream of a gaining one reads larger counts, and can sit just above 1/b. Does such a reduction go through at one cell? In the programme fan-out is free; are there two consumers whose safe extents pull a shared hull's insets opposite ways? Can running ahead (REDUNDANT: The relative-gradient law) be carried down a chain by a product consumer that emits before it reads its fresh stream?