Word-RAM programs and bounds for the clique counting compiler
DefinitionVWZClique_NativeCliqueCompilerclique-countinggraph-algorithmsword-ram
The compiler uses one finite program for each fixed clique size. Each recursive frame stores the weighted nine-vertex pattern, the position of its compacted masks and spectral labels, and the integer value passed back to its caller. The projected contraction precomputes support tables, materializes three dense matrices, and packs them into square tiles for multiplication. This module defines these programs, their matrix layouts, the memory predicates that connect stored integers to matrix entries, and the instruction-count bounds used in the recursion. Its interface also specifies when the resulting finite program realizes the asymptotic counting bound for every graph size.
Definition code
import Definitions.Def_OAI_MatrixMultiplication_Arithmetic_omega
import Definitions.Def_VWZClique_Contraction
import Definitions.Def_VWZClique_Count
import Definitions.Def_VWZClique_FoldedSum
import Definitions.Def_VWZClique_Operators
import Definitions.Def_VWZClique_Weighted
import Mathlib
import Mathlib.Algebra.Polynomial.Eval.Coeff
import Mathlib.Algebra.Polynomial.Roots
import Mathlib.Data.Fintype.EquivFin
import Mathlib.LinearAlgebra.Finsupp.LinearCombination
import Mathlib.LinearAlgebra.Pi
import Mathlib.Tactic.Choose
import Mathlib.Tactic.Ring
import Definitions.Def_VWZClique_NativeProjectionContract
/- CliqueVM -/
section
/-! Simulation of bounded integer arithmetic, indirect addressing and branches on
the fixed-width instruction interpreter used for clique counting. -/
namespace VWZClique.IntegerRAM
open TrulySubcubicAPSP
def input (ws : List ℤ) : Memory := fun a => if a < 0 then 0 else ws.getD a.toNat 0
end VWZClique.IntegerRAM
end
/- CliqueReduction -/
section
/-! Exact reduction from unordered cliques to a single weighted nine-vertex instance.
A fixed vertex fills unused slots, and order constraints choose one increasing
enumeration of each clique. The extra slots allow all clique sizes. -/
namespace VWZClique
namespace BlockReduction
open Finset
open scoped BigOperators
noncomputable section
open Classical
/-- Group and coordinate of one padded slot, with row-major numbering. -/
def slot {t : ℕ} (i : V) (p : Fin t) : Fin (9*t) := finProdFinEquiv (i,p)
/-- Value in an encoded block. -/
def digit {n t : ℕ} (a : Fin (n^t)) : Fin t → Fin n := finFunctionFinEquiv.symm a
/-- A pair of active slots holds adjacent vertices in the order fixed by its positions. -/
def compatible {n t : ℕ} (G : SimpleGraph (Fin n)) (k : ℕ)
(r s : Fin (9*t)) (u v : Fin n) : Prop :=
r.val < k → s.val < k →
(r < s → u < v ∧ G.Adj u v) ∧ (s < r → v < u ∧ G.Adj v u)
/-- Unary constraints enforce internal pairs and a unique padding value. -/
def unaryOK {n t : ℕ} (G : SimpleGraph (Fin n)) (k : ℕ)
(pad : Fin n) (i : V) (a : Fin (n^t)) : Prop :=
(∀ p, k ≤ (slot i p).val → digit a p = pad) ∧
∀ p q, compatible G k (slot i p) (slot i q) (digit a p) (digit a q)
/-- An edge constraint checks all pairs crossing the two blocks. -/
def edgeOK {n t : ℕ} (G : SimpleGraph (Fin n)) (k : ℕ) (i j : V)
(a b : Fin (n^t)) : Prop :=
∀ p q, compatible G k (slot i p) (slot j q) (digit a p) (digit b q)
/-- Initial values use only zero and one in the weighted nine-vertex instance. -/
def weights {F : Type*} [Field F] {n t : ℕ} (G : SimpleGraph (Fin n)) (k : ℕ)
(pad : Fin n) : WeightKey (n^t) → F
| .inl (i, a) => if unaryOK G k pad i a then 1 else 0
| .inr (i, j, a, b) => if edgeOK G k i j a b then 1 else 0
end
end BlockReduction
end VWZClique
end
/- CliqueStructured -/
section
/-! Composition of fixed, bounded integer loops for the published clique VM. -/
namespace VWZClique.IntegerRAM.Structured
open TrulySubcubicAPSP
/-- Advance a counter and test whether the next iteration is still below the limit. -/
def tick (i one limit test : ℤ) : Command :=
.seq (.atom (.add i i one)) (.atom (.sub test i limit))
def nextMemory (m : Memory) (i test : ℤ) (q N : ℕ) : Memory :=
update (update m i ((q:ℤ)+1)) test (((q:ℤ)+1)-N)
theorem tick_runs {W : ℕ} {i one limit test : ℤ} {q N : ℕ} {m : Memory}
(hneq : limit ≠ i) (hi : m i = (q:ℤ)) (h1 : m one = 1) (hn : m limit = (N:ℤ)) :
Runs W (tick i one limit test) m 2 (nextMemory m i test q N) := by
have hs := Runs.seq (Runs.atom (Step.add (W := W) m i i one))
(Runs.atom (Step.sub (W := W) (update m i (m i+m one)) test i limit))
simpa only [tick,nextMemory,hi,h1,update,if_pos rfl,if_true,if_neg hneq,hn] using hs
/-- A fixed ascending for-loop. The caller initializes the counter and the input limit. -/
def repeatN (body : Command) (i one limit test : ℤ) : Command :=
.repeatWhileNegative (.seq body (tick i one limit test)) test
/-- With a per-iteration body bound `B`, the compiled loop uses at most
`N(B+3)` instructions, charging the two counter updates and the backward test. -/
theorem repeatN_runs {W N B : ℕ} (hN : 0 < N) (body : Command) {i one limit test : ℤ}
(hneq : limit ≠ i) (inv : ℕ → Memory → Prop)
(fits : ∀ q : ℕ, q ≤ N → Fits W ((q:ℤ)-N))
(step : ∀ q : ℕ, q < N → ∀ m : Memory, inv q m →
∃ t : ℕ, t ≤ B ∧ ∃ x : Memory, Runs W body m t x ∧
x i = (q:ℤ) ∧ x one = 1 ∧ x limit = (N:ℤ) ∧ inv (q+1) (nextMemory x i test q N))
{m : Memory} (hm : inv 0 m) :
∃ t : ℕ, t ≤ N*(B+3) ∧ ∃ out, Runs W (repeatN body i one limit test) m t out ∧ inv N out := by
have go (r q : ℕ) (he : q+r=N) (hr : 0<r) (m : Memory) (hin : inv q m) :
∃ t : ℕ, t ≤ r*(B+3) ∧ ∃ out,
Runs W (repeatN body i one limit test) m t out ∧ inv N out := by
induction r generalizing q m with
| zero => omega
| succ r ih =>
obtain ⟨s,hs,x,hx,hxi,hx1,hxN,hin'⟩ := step q (by omega) m hin
let y := nextMemory x i test q N
have run : Runs W (.seq body (tick i one limit test)) m (s+2) y :=
Runs.seq hx (tick_runs hneq hxi hx1 hxN)
have htest : y test = ((q:ℤ)+1)-N := by simp [y,nextMemory,update]
have hfit : Fits W (y test) := by
rw [htest]
exact_mod_cast fits (q+1) (by omega)
by_cases hz : r=0
· subst r
have hqn : q+1=N := by omega
refine ⟨(s+2)+1,by omega,y,Runs.loop_done run hfit ?_,hqn ▸ hin'⟩
rw [htest]
exact_mod_cast (show ¬ ((q:ℤ)+1-(N:ℤ))<0 by omega)
· obtain ⟨t,ht,out,ho,final⟩ := ih (q+1) (by omega) (by omega) y hin'
refine ⟨(s+2)+1+t,?_,out,Runs.loop_again run hfit ?_ ho,final⟩
· rw [Nat.succ_mul]
omega
· rw [htest]
omega
exact go N 0 (by omega) hN m hm
end VWZClique.IntegerRAM.Structured
namespace VWZClique.BlockReduction
open IntegerRAM IntegerRAM.Structured
end VWZClique.BlockReduction
end
/- WordButterfly -/
section
/-! A fixed native signed-word program for one product-basis digit.
Four contiguous input stripes are streamed into one contiguous output array.
Each output quartet has the order 00, 11, 01+10, 01−10. -/
namespace VWZClique.IntegerRAM.Butterfly
open Structured TrulySubcubicAPSP
namespace Reg
abbrev p0 : ℤ := -1
abbrev p1 : ℤ := -2
abbrev p2 : ℤ := -3
abbrev p3 : ℤ := -4
abbrev dest : ℤ := -5
abbrev x0 : ℤ := -6
abbrev x1 : ℤ := -7
abbrev x2 : ℤ := -8
abbrev x3 : ℤ := -9
abbrev sum : ℤ := -10
abbrev diff : ℤ := -11
abbrev count : ℤ := -12
abbrev srcBase : ℤ := -13
abbrev dstBase : ℤ := -14
abbrev stride : ℤ := -15
abbrev one : ℤ := -16
abbrev zero : ℤ := -17
abbrev stages : ℤ := -18
abbrev swap : ℤ := -19
end Reg
/-- Straight-line commands, with one native instruction per list entry. -/
def line : List Atom → Command
| [] => .skip
| a :: as => .seq (.atom a) (line as)
def prepare : List Atom := [
.one Reg.one, .sub Reg.zero Reg.one Reg.one,
.add Reg.p0 Reg.srcBase Reg.zero, .add Reg.p1 Reg.p0 Reg.stride,
.add Reg.p2 Reg.p1 Reg.stride, .add Reg.p3 Reg.p2 Reg.stride,
.add Reg.dest Reg.dstBase Reg.zero, .sub Reg.count Reg.zero Reg.stride]
def readInputs : List Atom := [
.load Reg.x0 Reg.p0, .load Reg.x1 Reg.p1, .load Reg.x2 Reg.p2, .load Reg.x3 Reg.p3,
.add Reg.sum Reg.x2 Reg.x3, .sub Reg.diff Reg.x2 Reg.x3]
def writeOne (r : ℤ) : Command := line [.store Reg.dest r,.add Reg.dest Reg.dest Reg.one]
def writeOutputs : Command := .seq (writeOne Reg.x0) (.seq (writeOne Reg.x1)
(.seq (writeOne Reg.sum) (writeOne Reg.diff)))
def advance : List Atom := [
.add Reg.p0 Reg.p0 Reg.one, .add Reg.p1 Reg.p1 Reg.one,
.add Reg.p2 Reg.p2 Reg.one, .add Reg.p3 Reg.p3 Reg.one,
.add Reg.count Reg.count Reg.one]
def body : Command := .seq (line readInputs) (.seq writeOutputs (line advance))
def sweep : Command := .repeatWhileNegative body Reg.count
def stage : Command := .seq (line prepare) sweep
set_option maxHeartbeats 1600000
attribute [local simp] Reg.p0 Reg.p1 Reg.p2 Reg.p3 Reg.dest Reg.x0 Reg.x1 Reg.x2 Reg.x3
Reg.sum Reg.diff Reg.count Reg.srcBase Reg.dstBase Reg.stride Reg.one Reg.zero Reg.stages Reg.swap
end VWZClique.IntegerRAM.Butterfly
end
/- NativeMaskScan -/
section
/-! Uniform stable compaction for mask and projected-label records. -/
namespace VWZClique.IntegerRAM.MaskScan
open Structured Butterfly
abbrev idx : ℤ := -200
abbrev lim : ℤ := -201
abbrev unit : ℤ := -5
abbrev test : ℤ := -202
abbrev outC : ℤ := -203
abbrev outV : ℤ := -204
abbrev flag : ℤ := -205
abbrev value : ℤ := -206
/-- One output record consists of its original numeric code and its signed value. -/
def appendRow : List Atom := [.store outC idx, .store outV value,
.add outC outC unit, .add outV outV unit]
def scanBody (classify : Command) := Command.seq classify (.whenNonnegative flag (line appendRow))
def scan (classify : Command) := repeatN (scanBody classify) idx unit lim test
end VWZClique.IntegerRAM.MaskScan
end
/- WordGraphDivide -/
section
/-! Repeated subtraction for radix decoding. It uses one graph-order cell and
four negative cells, with a time linear in the quotient. A blocked input table
can afford linear work per packed key. -/
namespace VWZClique.IntegerRAM.Graph
open Structured BlockReduction
namespace Division
abbrev num : ℤ := -1
abbrev quot : ℤ := -2
abbrev test : ℤ := -3
abbrev one : ℤ := -5
def body : Command :=
.seq (.atom (.sub num num 0))
(.seq (.atom (.add quot quot one))
(.seq (.atom (.sub test 0 num))
(.atom (.sub test test one))))
def loop : Command := .repeatWhileNegative body test
def command : Command :=
.seq (.atom (.sub quot quot quot))
(.seq (.atom (.sub test num 0))
(.whenNonnegative test loop))
theorem Room.fits {W M : ℕ} (cap : Room W M) {v : ℤ} (lo : -(M:ℤ) ≤ v)
(hi : v ≤ (M:ℤ)) : Fits W v := ⟨(neg_le_neg cap.le).trans lo, hi.trans_lt cap⟩
end Division
end VWZClique.IntegerRAM.Graph
end
/- WordGraphDigits -/
section
/-! Radix-n unpacking of a blocked vertex label by the native word machine. -/
namespace VWZClique.IntegerRAM.Graph
open Structured BlockReduction
namespace Digits
open Division
def step (r : ℤ) : Command :=
.seq command (.seq (.atom (.mul r num one)) (.atom (.mul num quot one)))
end Digits
end VWZClique.IntegerRAM.Graph
end
/- NativeMaskScanClass -/
section
namespace VWZClique.IntegerRAM.MaskScan
open Structured Graph
abbrev digit : ℤ := -6
abbrev amount : ℤ := -207
abbrev sign : ℤ := -208
abbrev countFrom : ℤ := -209
abbrev signFrom : ℤ := -210
abbrev remSteps : ℤ := -211
abbrev len : ℤ := -212
abbrev zero : ℤ := -213
abbrev cmp : ℤ := -214
def mark (h dst : ℤ) (act : Atom) : Command :=
.seq (.atom (.sub cmp digit h)) (.whenNonnegative cmp (.atom act))
def oneDigit : Command := .seq (Graph.Digits.step digit)
(.seq (mark countFrom amount (.add amount amount unit))
(.seq (mark signFrom sign (.sub sign zero sign)) (.atom (.add remSteps remSteps unit))))
end VWZClique.IntegerRAM.MaskScan
end
/- NativeMaskScanDigits -/
section
namespace VWZClique.IntegerRAM.MaskScan
open Structured Graph
open Division (num)
def beginDigits : List Atom := [.sub zero unit unit,.sub amount unit unit,.one sign,
.mul num idx unit,.sub remSteps zero len,.sub cmp len unit]
def allDigits : Command := .seq (Butterfly.line beginDigits)
(.whenNonnegative cmp (.repeatWhileNegative oneDigit remSteps))
end VWZClique.IntegerRAM.MaskScan
end
/- NativeMaskScanTable -/
section
namespace VWZClique.IntegerRAM.MaskScan
open Structured Graph Butterfly
abbrev leftCut : ℤ := -215
abbrev rightCut : ℤ := -216
abbrev coef : ℤ := -217
abbrev ptr : ℤ := -218
def writeValue : List Atom := [.add ptr coef amount,.load value ptr,.mul value value sign,
.sub flag amount rightCut,.sub cmp leftCut amount]
def post : Command := .seq (line writeValue) (.whenNonnegative cmp (.atom (.one flag)))
def classifier : Command := .seq allDigits post
end VWZClique.IntegerRAM.MaskScan
end
/- FoldKernel -/
section
open VWZClique
namespace VWZClique.FoldProof
abbrev Quad := Bool × Bool × Bool × Bool
def pin {L : ℕ} (m : Option (Mask L)) (read : Quad → Bool) (u : Bits L) : Prop :=
match m with
| none => True
| some mask => ∀ i r, mask i = some r → u i = read r
def restore {L : ℕ} (m : Mask L) (read : Quad → Bool) (u : Bits L) : Bits L :=
fun i => (m i).elim (u i) read
open Classical in
noncomputable def flag {F : Type*} [Field F] {L : ℕ} (m : Option (Mask L)) (read : Quad → Bool)
(u : Bits L) : F := if pin m read u then 1 else 0
end VWZClique.FoldProof
end
/- FoldRouting -/
section
open VWZClique
namespace VWZClique.FoldProof
def perm {L : ℕ} (m : Option (Mask L)) (i : Fin 3) : Fin 3 :=
if m.isSome then ![1,0,2] i else i
def adjust {L : ℕ} (m : Option (Mask L)) (i : Fin 3) (s : Bits L) : Bits L :=
match m with
| none => s
| some m => ![restore m (fun r => r.2.2.1) s, restore m (fun r => r.2.2.2) s,s] i
def route {L : ℕ} (a b : Option (Mask L)) (h : Fin 3) : Slot → V × (Bits L → Bits L)
| .inl i => if h=1 then (site h (perm b i),adjust b i) else (site h i,id)
| .inr i => if h=2 then (site (next h) (perm a i),adjust a i) else (site (next h) i,id)
end VWZClique.FoldProof
end
/- GraphWeights -/
section
open VWZClique OAI.MatrixMultiplication.Arithmetic
namespace VWZClique.FoldProof
abbrev Kind := V ⊕ V × V
def kind (p : V × V) : Kind :=
if p.1=p.2 then .inl p.1 else if p.1<p.2 then .inr p else .inr (p.2,p.1)
def shape {n : ℕ} : WeightKey n → Kind
| .inl (i,_) => .inl i
| .inr (i,j,_,_) => .inr (i,j)
def addressValue {n : ℕ} : WeightKey n → V → Fin n
| .inl (_,x), _ => x
| .inr (i,_,x,y), k => if k=i then x else y
def collect {F I T : Type*} [Field F] [Fintype T] {n : ℕ} (ep : T → V × V)
(f : T → Fin n → Fin n → (I → F) → F) (k : WeightKey n) (w : I → F) : F :=
∏ t ∈ Finset.univ.filter (fun t => kind (ep t) = shape k),
f t (addressValue k (ep t).1) (addressValue k (ep t).2) w
end VWZClique.FoldProof
end
/- FoldFactors -/
section
open VWZClique
namespace VWZClique.FoldProof
abbrev FoldToken (E : Finset EdgeSlot) := Fin 4 ⊕ (Fin 3 × Slot) ⊕ ↥E
def pinSite (i : Fin 4) : V := ![site 0 0,site 0 1,site 1 0,site 1 1] i
noncomputable def pinWeight {F : Type*} [Field F] {L : ℕ} (a b : Option (Mask L))
(i : Fin 4) (s : Bits L) : F :=
![flag a Prod.fst s,flag a (fun r => r.2.1) s,flag b Prod.fst s,flag b (fun r => r.2.1) s] i
def ends {L : ℕ} (a b : Option (Mask L)) {E : Finset EdgeSlot} : FoldToken E → V × V
| .inl i => (pinSite i,pinSite i)
| .inr (.inl (h,s)) => ((route a b h s).1,(route a b h s).1)
| .inr (.inr e) => ((route a b e.val.1 e.val.2.1).1,(route a b e.val.1 e.val.2.2).1)
noncomputable def weight {F : Type*} [Field F] {L : ℕ} (a b : Option (Mask L)) {E : Finset EdgeSlot} :
FoldToken E → Bits L → Bits L → (ChannelKey L → F) → F
| .inl i, s, _, _ => pinWeight a b i s
| .inr (.inl (h,i)), s, _, w => w (h,.inl (i,(route a b h i).2 s))
| .inr (.inr e), s,t,w => w (e.val.1,.inr (e.val.2.1,e.val.2.2,
(route a b e.val.1 e.val.2.1).2 s,(route a b e.val.1 e.val.2.2).2 t))
end VWZClique.FoldProof
end
/- FoldEdges -/
section
open VWZClique
namespace VWZClique.FoldProof
def epPair {L : ℕ} (a b : Option (Mask L)) (e : EdgeSlot) : V × V :=
((route a b e.1 e.2.1).1, (route a b e.1 e.2.2).1)
def edgeImage {L : ℕ} (a b : Option (Mask L)) (e : EdgeSlot) : Sym2 V :=
s((epPair a b e).1, (epPair a b e).2)
def foldedGraph {L : ℕ} (a b : Option (Mask L)) (E : Finset EdgeSlot) : SimpleGraph V :=
SimpleGraph.fromEdgeSet ↑(E.image (edgeImage a b))
theorem image_drop {α β : Type*} [DecidableEq α] [DecidableEq β]
(T : Finset α) (f : α → β) (x y : α) (hy : y ∈ T) (hyx : y ≠ x) (h : f x = f y) :
T.image f = (T.erase x).image f := by
apply Finset.Subset.antisymm _ (Finset.image_mono f (Finset.erase_subset _ _))
intro z hz
obtain ⟨u,hu,rfl⟩ := Finset.mem_image.mp hz
by_cases heq : u = x
· subst u
exact Finset.mem_image.mpr ⟨y, Finset.mem_erase.mpr ⟨hyx,hy⟩, h.symm⟩
· exact Finset.mem_image_of_mem f (Finset.mem_erase.mpr ⟨heq,hu⟩)
def leftEdge (h : Fin 3) : EdgeSlot := (h, .inl 0, .inl 2)
def rightEdge (h : Fin 3) : EdgeSlot := (h, .inr 1, .inr 2)
theorem folded_count {L : ℕ} (a b : Option (Mask L)) (E : Finset EdgeSlot)
(ha : a.isSome = true → wedgePlaced E 0 2)
(hb : b.isSome = true → wedgePlaced E 1 0) :
Nat.card (foldedGraph a b E).edgeSet + a.isSome.toNat + b.isSome.toNat ≤ E.card := by
have graphBound : Nat.card (foldedGraph a b E).edgeSet ≤ (E.image (edgeImage a b)).card := by
rw [Nat.card_coe_set_eq, foldedGraph, SimpleGraph.edgeSet_fromEdgeSet, ← Set.ncard_coe_finset]
exact Set.ncard_le_ncard Set.sdiff_subset
obtain ⟨T,hImage,hCard,hb'⟩ : ∃ T : Finset EdgeSlot,
E.image (edgeImage a b) = T.image (edgeImage a b) ∧
T.card + a.isSome.toNat = E.card ∧
(b.isSome = true → wedgePlaced T 1 0) := by
cases a with
| none => exact ⟨E,rfl,by simp,hb⟩
| some m =>
have hA := ha rfl
refine ⟨E.erase (leftEdge 0), ?_, Finset.card_erase_add_one hA.1, ?_⟩
· exact image_drop E (edgeImage (some m) b) (leftEdge 0) (rightEdge 2) hA.2 (by decide) rfl
· intro h
exact ⟨Finset.mem_erase.mpr ⟨by decide,(hb h).1⟩,
Finset.mem_erase.mpr ⟨by decide,(hb h).2⟩⟩
have countT : (T.image (edgeImage a b)).card + b.isSome.toNat ≤ T.card := by
cases b with
| none => simpa using (Finset.card_image_le (s := T) (f := edgeImage a none))
| some m =>
have hB := hb' rfl
rw [image_drop T (edgeImage a (some m)) (leftEdge 1) (rightEdge 0) hB.2 (by decide) rfl]
have hErase : (T.erase (leftEdge 1)).card + 1 = T.card := Finset.card_erase_add_one hB.1
have hBound := Finset.card_image_le (s := T.erase (leftEdge 1)) (f := edgeImage a (some m))
change _ + 1 ≤ _
omega
rw [hImage] at graphBound
omega
end VWZClique.FoldProof
end
/- WeightedPlacement -/
section
open VWZClique VWZClique.FoldProof OAI.MatrixMultiplication.Arithmetic
namespace VWZClique.WeightedProof
theorem pairs_card (H : SimpleGraph V) : (pairs H).card ≤ Nat.card H.edgeSet := by
classical
let mapEdge : ↥(pairs H) → H.edgeSet := fun p =>
⟨s(p.val.1,p.val.2),(Finset.mem_filter.mp p.property).2.2⟩
have hinj : Function.Injective mapEdge := by
intro p q hpq
obtain ⟨p,hp⟩ := p
obtain ⟨q,hq⟩ := q
apply Subtype.ext
obtain ⟨hp,_⟩ := (Finset.mem_filter.mp hp).2
obtain ⟨hq,_⟩ := (Finset.mem_filter.mp hq).2
have huv : s(p.1,p.2) = s(q.1,q.2) := congrArg Subtype.val hpq
rcases Sym2.eq_iff.mp huv with huv|huv
· exact Prod.ext huv.1 huv.2
· exact (not_lt_of_ge hq.le (by simpa only [huv.1,huv.2] using hp)).elim
simpa [Nat.card_eq_fintype_card] using Fintype.card_le_of_injective mapEdge hinj
theorem slots_card (π : Equiv.Perm V) (H : SimpleGraph V) :
(slots π H).card ≤ Nat.card H.edgeSet := Finset.card_image_le.trans (pairs_card H)
theorem slots_adj (π : Equiv.Perm V) (H : SimpleGraph V) {u v : V} (hlt : u<v)
(h : H.Adj (π u) (π v)) : locate u v ∈ slots π H := by
classical
have ne : π u ≠ π v := π.injective.ne hlt.ne
rcases lt_or_gt_of_ne ne with hnum|hnum
· exact Finset.mem_image.mpr ⟨(π u,π v),Finset.mem_filter.mpr ⟨Finset.mem_univ _,hnum,h⟩,
by simp [chosen,min_eq_left hlt.le,max_eq_right hlt.le]⟩
· exact Finset.mem_image.mpr ⟨(π v,π u),Finset.mem_filter.mpr ⟨Finset.mem_univ _,hnum,h.symm⟩,
by simp [chosen,min_eq_right hlt.le,max_eq_left hlt.le]⟩
theorem place_wedges (H : SimpleGraph V) (f g : Fin 3 → V)
(hf : wedge H f) (hg : wedge H g) (hfg : ∀ i j, f i ≠ g j) :
∃ π : Equiv.Perm V, wedgePlaced (slots π H) 0 2 ∧ wedgePlaced (slots π H) 1 0 := by
let sites : Slot → V := Sum.elim ![0,2,1] ![3,5,4]
let verts := Sum.elim f g
have hs : Function.Injective sites := by decide
have hv : Function.Injective verts := by
intro v w h
rcases v with i|i <;> rcases w with j|j
· exact congrArg Sum.inl (hf.1 h)
· exact (hfg _ _ h).elim
· exact (hfg _ _ h.symm).elim
· exact congrArg Sum.inr (hg.1 h)
obtain ⟨π,hπ⟩ := Equiv.Perm.exists_extending_pair sites verts hs hv
have A (i : Fin 3) : π (![0,2,1] i) = f i := hπ (.inl i)
have B (i : Fin 3) : π (![3,5,4] i) = g i := hπ (.inr i)
refine ⟨π,⟨?_,?_⟩,⟨?_,?_⟩⟩
· exact slots_adj π H (u:=0) (v:=2) (by decide) (by simpa [← A 0,← A 1] using hf.2.1)
· exact slots_adj π H (u:=1) (v:=2) (by decide) (by simpa [← A 2,← A 1] using hf.2.2.symm)
· exact slots_adj π H (u:=3) (v:=5) (by decide) (by simpa [← B 0,← B 1] using hg.2.1)
· exact slots_adj π H (u:=4) (v:=5) (by decide) (by simpa [← B 2,← B 1] using hg.2.2.symm)
end VWZClique.WeightedProof
end
/- WeightedPadding -/
section
open VWZClique OAI.MatrixMultiplication.Arithmetic
namespace VWZClique.WeightedProof
variable {F I J : Type*} [Field F]
def padTag {n N : ℕ} : WeightKey N → WeightKey n ⊕ F
| .inl (i,x) => if h : x.val < n then .inl (.inl (i,⟨x,h⟩)) else .inr 0
| .inr (i,j,x,y) => if h : x.val < n ∧ y.val < n then .inl (.inr (i,j,⟨x,h.1⟩,⟨y,h.2⟩)) else .inr 0
end VWZClique.WeightedProof
end
/- UniformFoldWeights -/
section
open VWZClique VWZClique.FoldProof VWZClique.WeightedProof
namespace VWZClique.UniformFolds
/-- The literal product of all unary, edge and pin factors routed to this table entry. -/
noncomputable def updated {F : Type*} [Field F] {L : ℕ} (E : Finset EdgeSlot)
(a b : Option (Mask L)) (w : ChannelKey L → F) (k : WeightKey (2^L)) : F :=
collect (ends (E:=E) a b)
(fun t x y => weight a b t ((wordIndex L).symm x) ((wordIndex L).symm y)) k w
end VWZClique.UniformFolds
end
/- NativeMaskScanScale -/
section
namespace VWZClique.IntegerRAM.MaskScan
open Structured Graph Butterfly
abbrev powBase : ℤ := -219
def scaleFinish : List Atom := [.add ptr powBase amount,.load ptr ptr,.mul value value ptr,.add countFrom countFrom unit]
def scaleClass : Command := .seq classifier (.seq (.atom (.add countFrom unit unit)) (.seq allDigits (line scaleFinish)))
end VWZClique.IntegerRAM.MaskScan
end
/- NativeMaskScanForward -/
section
/-! A contiguous convolution triangle realizes every coefficient (shift^[s] c) 0
with one pass in O((L+1)^2) native instructions. -/
namespace VWZClique.IntegerRAM.MaskScan.Forward
open Structured Butterfly
abbrev rd : ℤ := -240
abbrev wr : ℤ := -241
abbrev other : ℤ := -242
abbrev ireg : ℤ := -243
abbrev maxI : ℤ := -244
abbrev check : ℤ := -245
abbrev va : ℤ := -246
abbrev vb : ℤ := -247
abbrev unit : ℤ := -5
def block : List Atom := [.add other rd unit, .load va rd, .load vb other, .add vb vb vb,
.sub va va vb,.store wr va,.add rd rd unit,.add wr wr unit]
def forward : Command := repeatN (line block) ireg unit maxI check
end VWZClique.IntegerRAM.MaskScan.Forward
end
/- NativeMaskScanResidual -/
section
namespace VWZClique.IntegerRAM.MaskScan.Forward
open Structured Butterfly
abbrev resWr : ℤ := -249
abbrev powWr : ℤ := -250
abbrev stride : ℤ := -251
abbrev parity : ℤ := -252
abbrev power : ℤ := -253
abbrev nilReg : ℤ := -254
def gatherBlock : List Atom := [.load va rd,.mul va parity va,.sub va unit va,
.store resWr va,.store powWr power,.add rd rd stride,.add resWr resWr unit,
.sub powWr powWr unit,.sub parity nilReg parity,.add power power power]
def gather : Command := repeatN (line gatherBlock) ireg unit maxI check
end VWZClique.IntegerRAM.MaskScan.Forward
end
/- NativeMaskScanPrecompute -/
section
namespace VWZClique.IntegerRAM.MaskScan.Forward
open Structured Butterfly
/-- A caller places four runtime words in this fixed header. The coefficients
occupy the first row of the triangular buffer. The two answers are contiguous
arrays with arbitrary disjoint base addresses beyond the triangle. -/
abbrev inLen : ℤ := 300
abbrev inTriangle : ℤ := 301
abbrev inResidual : ℤ := 302
abbrev inPowers : ℤ := 303
def startF : List Atom := [.one unit,.sub ireg unit unit,.mul rd inTriangle unit,.add stride inLen unit,
.add wr rd stride,.mul maxI inLen stride,.sub check inLen unit]
def startG : List Atom := [.one unit,.sub ireg unit unit,.sub nilReg unit unit,.mul rd inTriangle unit,
.mul resWr inResidual unit,.add powWr inPowers inLen,.add stride inLen unit,.add maxI stride nilReg,
.one parity,.one power]
def precompute : Command := .seq (line startF) (.seq (.whenNonnegative check forward) (.seq (line startG) gather))
end VWZClique.IntegerRAM.MaskScan.Forward
end
/- NativeMaskScanPower -/
section
namespace VWZClique.IntegerRAM.MaskScan.Pow
open Structured Butterfly
abbrev base : ℤ := -264
abbrev bound : ℤ := -265
abbrev x : ℤ := -266
abbrev ireg : ℤ := -267
abbrev flag : ℤ := -268
abbrev one : ℤ := -269
def setup := [Atom.one one,.sub ireg one one,.one x,.sub flag bound one]
def command := Command.seq (line setup) (.whenNonnegative flag
(repeatN (.atom (.mul x x base)) ireg one bound flag))
end VWZClique.IntegerRAM.MaskScan.Pow
end
/- NativeMaskScanArena -/
section
namespace VWZClique.IntegerRAM.MaskScan.Arena
open Structured Butterfly
abbrev Lr : ℤ := 300
abbrev Cr : ℤ := 301
abbrev Rr : ℤ := 302
abbrev Pr : ℤ := 303
abbrev Ar : ℤ := 304
abbrev Dr : ℤ := 305
abbrev MC : ℤ := 306
abbrev MV : ℤ := 307
abbrev LC : ℤ := 308
abbrev LV : ℤ := 309
abbrev counts : ℤ := 310
abbrev originalN : ℤ := 311
abbrev maskN : ℤ := 312
abbrev slab : ℤ := 313
abbrev labelN : ℤ := 314
abbrev inputLen : ℤ := 320
abbrev scratch : ℤ := -275
def layout (w : ℤ) : List Atom := [.one unit,.mul originalN 0 unit,.mul Lr inputLen unit,
.mul labelN 0 0,.mul slab labelN 0,.add scratch 0 0,.add scratch scratch scratch,.add scratch scratch scratch,
.add scratch scratch 0,.mul Cr scratch scratch,.add Cr Cr scratch,.add Cr Cr w,
.add Rr Cr slab,.add Pr Rr slab,.add MC Pr slab,.add MV MC slab,.add LC MV slab,.add LV LC slab,
.add counts LV slab,.mul (-2) Cr unit,.mul (-12) Lr unit]
end VWZClique.IntegerRAM.MaskScan.Arena
end
/- NativeMaskScanStart -/
section
namespace VWZClique.IntegerRAM.MaskScan.Arena
open Structured Butterfly
def maskInit : List Atom := [.one unit,.sub idx unit unit,.add 0 unit unit,.add 0 0 0,.add 0 0 unit,
.mul len Lr unit,.one countFrom,.add signFrom unit unit,.add signFrom signFrom unit,.mul coef Cr unit,
.mul leftCut Dr unit,.add rightCut Lr unit,.mul outC MC unit,.mul outV MV unit,.mul lim maskN unit]
def labelInit : List Atom := [.one unit,.sub idx unit unit,.add 0 unit unit,.add 0 0 0,
.mul len Lr unit,.sub countFrom 0 unit,.mul signFrom 0 unit,.mul coef Rr unit,.mul powBase Pr unit,
.sub leftCut Ar unit,.add rightCut Ar Dr,.add rightCut rightCut unit,.mul outC LC unit,.mul outV LV unit,.mul lim labelN unit]
def radixSetup : List Atom := [.one unit,.mul Pow.bound Lr unit,.add Pow.base unit unit,.add Pow.base Pow.base Pow.base,
.add Pow.base Pow.base unit]
def radixCommand := Command.seq (line radixSetup) (.seq Pow.command (.atom (.mul maskN Pow.x unit)))
end VWZClique.IntegerRAM.MaskScan.Arena
end
/- NativeMaskScanSave -/
section
namespace VWZClique.IntegerRAM.MaskScan.Arena
open Structured Butterfly
def saveMask := [Atom.sub scratch outC MC,.store counts scratch]
def saveLabel := [Atom.sub scratch outC LC,.add ptr counts unit,.store ptr scratch,.mul 0 originalN unit]
end VWZClique.IntegerRAM.MaskScan.Arena
end
/- NativeMaskScanBoth -/
section
namespace VWZClique.IntegerRAM.MaskScan.Arena
open Structured Graph RankSwap RankSwap.MaskEnumeration UniformFolds Butterfly
def compact := Command.seq (line maskInit) (.seq (scan classifier) (.seq (line saveMask)
(.seq (line labelInit) (.seq (scan scaleClass) (line saveLabel)))))
end VWZClique.IntegerRAM.MaskScan.Arena
end
/- NativeSignedDivision -/
section
/-! Exact signed division on the published add/subtract/multiply word machine.
The divisor is positive. A fixed scan takes one quotient bit per iteration. -/
namespace VWZClique.IntegerRAM.SignedDivision
open Structured
abbrev value : ℤ := -100
abbrev divisor : ℤ := -101
abbrev length : ℤ := -102
abbrev remn : ℤ := -103
abbrev result : ℤ := -104
abbrev threshold : ℤ := -105
abbrev index : ℤ := -106
abbrev unit : ℤ := -107
abbrev flag : ℤ := -108
abbrev signReg : ℤ := -109
def grow : Command := .atom (.add threshold threshold threshold)
def scale : Command := repeatN grow index unit length flag
def save : Command := .seq (.atom (.sub remn remn threshold)) (.atom (.add result result unit))
def digit : Command :=
.seq (.atom (.add result result result))
(.seq (.atom (.add remn remn remn))
(.seq (.atom (.sub flag remn threshold)) (.whenNonnegative flag save)))
def scan : Command := repeatN digit index unit length flag
def initCode : Command :=
.seq (.atom (.one unit))
(.seq (.atom (.sub index index index))
(.seq (.atom (.sub result result result))
(.seq (.atom (.mul threshold divisor unit))
(.seq (.atom (.sub remn result value))
(.seq (.atom (.sub signReg result unit))
(.whenNonnegative value (.seq (.atom (.mul remn value unit)) (.atom (.one signReg)))))))))
def command : Command :=
.seq initCode (.seq scale (.seq (.atom (.sub index index index)) (.seq scan (.atom (.mul result result signReg)))))
end VWZClique.IntegerRAM.SignedDivision
end
/- NativeWindowInit -/
section
namespace VWZClique.IntegerRAM.WindowInit
open Structured SignedDivision
/-- L remains in the register produced by the graph-size preparation. -/
abbrev Lreg : ℤ := -12
abbrev loReg : ℤ := -15
abbrev hiReg : ℤ := -16
abbrev degreeReg : ℤ := -7
abbrev negLower : ℤ := -8
def constant (dest : ℤ) : ℕ → Command
| 0 => .atom (.sub dest dest dest)
| n+1 => .seq (constant dest n) (.atom (.add dest dest unit))
def setup (c r : ℕ) : Command :=
.seq (.atom (.one unit)) (.seq (constant value c) (.seq (constant divisor r)
(.seq (.atom (.mul value value Lreg)) (.atom (.add length Lreg unit)))))
def ratio (c r : ℕ) : Command := .seq (setup c r) command
/-- Copy a register without assuming a resident constant. -/
def copy (dst src : ℤ) : Command := .seq (.atom (.one unit)) (.atom (.mul dst src unit))
def window (K : ℕ) := Command.seq (ratio (K-4) (4*K))
(.seq (copy loReg result) (.seq (ratio (K+4) (4*K)) (.seq (copy hiReg result)
(.seq (.atom (.sub degreeReg hiReg loReg)) (.seq (.atom (.sub negLower negLower negLower))
(.atom (.sub negLower negLower loReg)))))))
end VWZClique.IntegerRAM.WindowInit
end
/- NativeFoldBits -/
section
namespace VWZClique.IntegerRAM.FoldBits
open Structured
def code : List Atom → Command
| [] => .skip
| h :: t => .seq (.atom h) (code t)
end VWZClique.IntegerRAM.FoldBits
end
/- NativeWindowSeed -/
section
namespace VWZClique.IntegerRAM.WindowSeed
open Structured FoldBits
abbrev idx : ℤ := -21
abbrev lim : ℤ := -22
abbrev test : ℤ := -23
abbrev sign : ℤ := -24
abbrev zero : ℤ := -25
abbrev one : ℤ := -6
abbrev ptr : ℤ := -26
abbrev term : ℤ := -27
abbrev cut : ℤ := -28
abbrev base : ℤ := -2
def paritySetup : List Atom := [.one one,.sub zero one one,.sub sign zero one,
.sub idx one one,.sub lim one WindowInit.negLower]
def parityLoop : Command := repeatN (.atom (.sub sign zero sign)) idx one lim test
def parity : Command := .seq (code paritySetup) parityLoop
def fillSetup : List Atom := [.sub idx one one,.add lim WindowInit.Lreg one,.mul ptr base one]
def before : List Atom := [.sub cut WindowInit.degreeReg idx,.sub term one one]
def writeCell : List Atom := [.store ptr term,.add ptr ptr one]
def fillOne : Command := .seq (code before) (.seq (.whenNonnegative cut (.atom (.mul term sign one))) (code writeCell))
def fill : Command := .seq (code fillSetup) (repeatN fillOne idx one lim test)
end VWZClique.IntegerRAM.WindowSeed
end
/- WordWindow -/
section
namespace VWZClique.IntegerRAM.WindowSweep
open Structured
namespace Reg
abbrev ptr : ℤ := -1
abbrev base : ℤ := -2
abbrev carry : ℤ := -3
abbrev val : ℤ := -4
abbrev test : ℤ := -5
abbrev one : ℤ := -6
end Reg
/-- Update a coefficient by c[h] + 2b[h+1], write it back, and move one entry left. -/
def body : Command :=
.seq (.atom (.load Reg.val Reg.ptr))
(.seq (.atom (.add Reg.carry Reg.carry Reg.carry))
(.seq (.atom (.add Reg.carry Reg.val Reg.carry))
(.seq (.atom (.store Reg.ptr Reg.carry))
(.seq (.atom (.sub Reg.test Reg.base Reg.ptr))
(.atom (.sub Reg.ptr Reg.ptr Reg.one))))))
def command : Command := .repeatWhileNegative body Reg.test
end VWZClique.IntegerRAM.WindowSweep
end
/- WordWindowTable -/
section
namespace VWZClique.IntegerRAM.WindowSweep
open Structured
open VWZClique.RankSwap.Window
abbrev degrees : ℤ := -7
abbrev counter : ℤ := -8
/-- Reset the pointer and carry before each backward sweep. -/
def reset : Command :=
.seq (.atom (.add Reg.ptr Reg.base degrees)) (.atom (.sub Reg.carry Reg.one Reg.one))
def outerBody : Command :=
.seq reset (.seq command (.atom (.add counter counter Reg.one)))
def tableCommand : Command := .repeatWhileNegative outerBody counter
def guardSetup : Command :=
.seq (.atom (.sub Reg.test Reg.one Reg.one))
(.seq (.atom (.sub Reg.test Reg.test Reg.one)) (.atom (.sub Reg.test Reg.test counter)))
def generateCommand : Command := .seq guardSetup (.whenNonnegative Reg.test tableCommand)
end VWZClique.IntegerRAM.WindowSweep
end
/- NativeWindowTables -/
section
namespace VWZClique.IntegerRAM.WindowSweep
open Structured VWZClique.RankSwap.Window
end VWZClique.IntegerRAM.WindowSweep
namespace VWZClique.IntegerRAM.WindowSeed
open Structured UniformFolds VWZClique.RankSwap.Window
def coefficients (K : ℕ) := Command.seq (WindowInit.window K) (.seq parity (.seq fill WindowSweep.generateCommand))
end VWZClique.IntegerRAM.WindowSeed
end
/- NativeMaskScanLocal -/
section
namespace VWZClique.IntegerRAM.MaskScan.Arena
open Structured Graph RankSwap UniformFolds Butterfly
def reloadLength := [Atom.one unit,.mul WindowInit.Lreg Lr unit]
def stashCuts := [Atom.one unit,.mul Ar WindowInit.loReg unit,.mul Dr WindowInit.degreeReg unit]
def prepare (K : ℕ) (source : ℤ) := Command.seq (line (layout source)) (.seq (WindowSeed.coefficients K)
(.seq (line reloadLength) (.seq (WindowInit.window K) (.seq (line stashCuts) (.seq Forward.precompute radixCommand)))))
def buildMaskMetadata (K : ℕ) (source : ℤ) := Command.seq (prepare K source) compact
end VWZClique.IntegerRAM.MaskScan.Arena
end
/- CliqueBlockMM -/
section
/-! Fixed integer-coefficient bilinear schemes recursively multiply arbitrary
tensor powers of their base dimension. Clearing the base coefficients'
denominators introduces just one fixed scale factor per level. -/
namespace VWZClique.BlockMM
open scoped BigOperators
abbrev Square (I : Type*) := Matrix I I ℤ
def linear {b : ℕ} (L A : Square (Fin b)) : ℤ := ∑ i, ∑ j, L i j * A i j
/-- An integer bilinear multiplication scheme, possibly representing a rational
scheme whose fixed denominators have been cleared. -/
structure Scheme (b r : ℕ) where
left : Fin r → Square (Fin b)
right : Fin r → Square (Fin b)
out : Fin b → Fin b → Fin r → ℤ
scale : ℤ
correct : ∀ (A B : Square (Fin b)) (i j : Fin b),
(∑ s, out i j s * (linear (left s) A * linear (right s) B)) = scale * (A*B) i j
end VWZClique.BlockMM
end
/- MMUniform -/
section
namespace VWZClique.BlockMM
/-- Least upper-power padding is unnecessary: this explicit depth pads by at most a factor b. -/
def depth (b n : ℕ) : ℕ := Nat.log b n + 1
end VWZClique.BlockMM
end
/- NativeFrame -/
section
namespace VWZClique.IntegerRAM.NativeFrame
open Structured
theorem reg_positive (d : ℕ) (f : Field) : 0 < reg d f := by
cases f <;> simp [reg,Field.offset] <;> omega
theorem reg_below {d : ℕ} (hd : d ≤ 36) (f : Field) : reg d f < 297 := by
cases f <;> simp [reg,Field.offset] <;> omega
theorem separate {a b : ℕ} (h : a<b) (f g : Field) : reg a f < reg b g := by
cases f <;> cases g <;> simp [reg,Field.offset] <;> omega
/-- Restoring an accumulator from any source register, independent of its current value. -/
def copy (dst src : ℤ) : Command :=
.seq (.atom (.one dst)) (.atom (.mul dst dst src))
theorem copy_runs (W : ℕ) (dst src : ℤ) (hd : src≠dst) (m : Memory) :
Runs W (copy dst src) m 2 (update m dst (m src)) := by
let a := update m dst 1
have first : Runs W (.atom (.one dst)) m 1 a := .atom (.one _ _)
have second := Runs.atom (Step.mul (W:=W) a dst dst src)
have eq : update a dst (a dst*a src) = update m dst (m src) := by
funext i; by_cases hi : i=dst <;> simp [a,update,hd,hi]
rw [eq] at second
exact first.seq second
end VWZClique.IntegerRAM.NativeFrame
end
/- UniformFolds -/
section
open VWZClique VWZClique.FoldProof VWZClique.WeightedProof
namespace VWZClique.UniformFolds
def representative : Bool → Option (Mask 0)
| false => none
| true => some Fin.elim0
def first : Branch → Bool
| .right => false
| _ => true
def second : Branch → Bool
| .left => false
| _ => true
/-- A branch's graph is fixed before the size of the assignment domain is known. -/
def child (E : Finset EdgeSlot) (d : Branch) : SimpleGraph V :=
foldedGraph (representative (first d)) (representative (second d)) E
def HasWedges (H : SimpleGraph V) : Prop :=
∃ f g : Fin 3 → V, wedge H f ∧ wedge H g ∧ ∀ i j, f i ≠ g j
theorem placeable (H : SimpleGraph V) (h : HasWedges H) :
∃ π : Equiv.Perm V, wedgePlaced (slots π H) 0 2 ∧ wedgePlaced (slots π H) 1 0 := by
obtain ⟨f,g,hf,hg,hd⟩ := h
exact place_wedges H f g hf hg hd
theorem branch_smaller (H : SimpleGraph V) (π : Equiv.Perm V)
(h : wedgePlaced (slots π H) 0 2 ∧ wedgePlaced (slots π H) 1 0) (d : Branch) :
Nat.card (child (slots π H) d).edgeSet < Nat.card H.edgeSet := by
let E := slots π H
have bound := folded_count (representative (first d)) (representative (second d)) E
(fun _ => h.1) (fun _ => h.2)
have hE : E.card ≤ Nat.card H.edgeSet := slots_card π H
change Nat.card (foldedGraph _ _ E).edgeSet < Nat.card H.edgeSet
cases d <;> simp [representative,first,second] at bound hE ⊢ <;> omega
/-- A finite table of placements and graph branches can be fixed for each initial pattern.
A split's three children may be used repeatedly for different masks and sizes. -/
inductive Plan : SimpleGraph V → Type where
| leaf (H : SimpleGraph V) (h : ¬ HasWedges H) : Plan H
| split (H : SimpleGraph V) (π : Equiv.Perm V)
(h : wedgePlaced (slots π H) 0 2 ∧ wedgePlaced (slots π H) 1 0)
(children : (d : Branch) → Plan (child (slots π H) d)) : Plan H
noncomputable def compile : (k : ℕ) → (H : SimpleGraph V) → Nat.card H.edgeSet < k → Plan H
| 0, _, h => (Nat.not_lt_zero _ h).elim
| k+1, H, hk => by
classical
by_cases hw : HasWedges H
· let π := Classical.choose (placeable H hw)
have hp := Classical.choose_spec (placeable H hw)
exact .split H π hp (fun d => compile k (child (slots π H) d)
(by have hdec := branch_smaller H π hp d; omega))
· exact .leaf H hw
theorem edge_limit (H : SimpleGraph V) : Nat.card H.edgeSet ≤ 36 := by
classical
rw [Nat.card_eq_fintype_card,← SimpleGraph.edgeFinset_card]
exact (SimpleGraph.card_edgeFinset_le_card_choose_two (G:=H)).trans_eq (by decide)
/-- This finite object depends on the nine-vertex pattern alone. -/
noncomputable def fixed (H : SimpleGraph V) : Plan H :=
compile 37 H (by have := edge_limit H; omega)
end VWZClique.UniformFolds
end
/- UniformFoldPaths -/
section
open VWZClique VWZClique.FoldProof VWZClique.WeightedProof
namespace VWZClique.UniformFolds
noncomputable def Round.apply {L : ℕ} (r : Round L) (w : WeightKey (2^L) → ℚ) : WeightKey (2^L) → ℚ :=
updated (slots r.π r.H) r.a r.b (r.inputs w)
end VWZClique.UniformFolds
end
/- SparsePartition -/
section
open VWZClique
namespace VWZClique.SparseProof
theorem make_wedge {H : SimpleGraph V} {u i v : V} (hu : H.Adj i u) (hv : H.Adj i v)
(hne : u ≠ v) : wedge H ![u,i,v] := by
have hui := hu.ne
have hiv := hv.ne
refine ⟨?_,hu.symm,hv⟩
intro x y he
fin_cases x <;> fin_cases y <;> simp_all
theorem hitting_set (H : SimpleGraph V)
(hh : ¬ ∃ f g : Fin 3 → V, wedge H f ∧ wedge H g ∧ ∀ i j, f i ≠ g j) :
∃ S : Finset V, S.card ≤ 3 ∧
∀ i u v : V, i ∉ S → u ∉ S → v ∉ S → H.Adj i u → H.Adj i v → u = v := by
classical
have hit : ∃ S : Finset V, S.card ≤ 3 ∧ ∀ g, wedge H g → ∃ k, g k ∈ S := by
by_cases h : ∃ f, wedge H f
· obtain ⟨f,hf⟩ := h
refine ⟨Finset.univ.image f, Finset.card_image_le.trans (by simp), ?_⟩
intro g hg
by_contra! hd
apply hh
exact ⟨f,g,hf,hg,fun i j hij => hd j (hij ▸ Finset.mem_image_of_mem f (Finset.mem_univ i))⟩
· exact ⟨∅,by simp,fun g hg => (h ⟨g,hg⟩).elim⟩
obtain ⟨S,hs,hhit⟩ := hit
refine ⟨S,hs,?_⟩
intro i u v hi hu hv heu hev
by_contra hne
obtain ⟨k,hk⟩ := hhit _ (make_wedge heu hev hne)
fin_cases k <;> simp_all
abbrev Bag := Finset V
abbrev Bucket := Option Bag
abbrev Fiber (key : V → Bucket) (b : Bucket) := {i : V // key i = b}
theorem matching_partition (H : SimpleGraph V)
(hh : ¬ ∃ f g : Fin 3 → V, wedge H f ∧ wedge H g ∧ ∀ i j, f i ≠ g j) :
∃ key : V → Bucket, Fintype.card (Fiber key none) ≤ 3 ∧
(∀ b : Bag, Fintype.card (Fiber key (some b)) ≤ 2) ∧
∀ i j, H.Adj i j → key i = none ∨ key j = none ∨ key i = key j := by
classical
obtain ⟨S,hs,hm⟩ := hitting_set H hh
let bag := fun i : V => Finset.univ.filter fun v : V => v ∉ S ∧ (v = i ∨ H.Adj i v)
let key := fun i : V => if i ∈ S then (none : Bucket) else some (bag i)
have mem_self (i : V) (hi : i ∉ S) : i ∈ bag i := by simp [bag,hi]
have bag_size (i : V) (hi : i ∉ S) : (bag i).card ≤ 2 := by
by_cases h : ∃ v, v ∉ S ∧ H.Adj i v
· obtain ⟨v,hv,he⟩ := h
apply (Finset.card_le_card (t := {i,v}) ?_).trans Finset.card_le_two
intro x hx
obtain ⟨hx,hxi|hedge⟩ := (Finset.mem_filter.mp hx).2
· simp [hxi]
· simp [hm i x v hi hx hv hedge he]
· have sub : bag i ⊆ {i} := by
intro x hx
obtain ⟨hx,hxi|he⟩ := (Finset.mem_filter.mp hx).2
· simp [hxi]
· exact (h ⟨x,hx,he⟩).elim
exact (Finset.card_le_card sub).trans (by simp)
have same {i j : V} (hi : i ∉ S) (hj : j ∉ S) (he : H.Adj i j) : bag i ⊆ bag j := by
intro x hx
obtain ⟨hx,hxi|he'⟩ := (Finset.mem_filter.mp hx).2
· subst x; simp [bag,hi,he.symm]
· have := hm i x j hi hx hj he' he
subst x; exact mem_self _ hj
refine ⟨key,?_,?_,?_⟩
· have : Finset.univ.filter (fun i => key i = none) = S := by ext i; simp [key]
simpa only [Fiber, Fintype.card_subtype, this] using hs
· intro b
have hcard : Fintype.card (Fiber key (some b)) =
(Finset.univ.filter (fun i => key i = some b)).card := Fintype.card_subtype _
rw [hcard]
let T := Finset.univ.filter (fun i => key i = some b)
change T.card ≤ 2
by_cases h : T.Nonempty
· obtain ⟨i,hi⟩ := h
have read (x : V) (hx : x ∈ T) : x ∉ S ∧ bag x = b := by
have hh := (Finset.mem_filter.mp hx).2
by_cases hm : x ∈ S <;> simp_all [key]
have ⟨hn, he⟩ := read i hi
apply (Finset.card_le_card (t := b) ?_).trans (he ▸ bag_size i hn)
intro x hx
have ⟨hn', he'⟩ := read x hx
exact he' ▸ mem_self x hn'
· simp [Finset.not_nonempty_iff_eq_empty.mp h]
· intro i j he
by_cases hi : i ∈ S
· simp [key,hi]
by_cases hj : j ∈ S
· simp [key,hj]
exact Or.inr (Or.inr (by simp [key,hi,hj,Finset.Subset.antisymm (same hi hj he) (same hj hi he.symm)]))
end VWZClique.SparseProof
end
/- SparseFactor -/
section
open VWZClique
namespace VWZClique.SparseProof
abbrev Token := V ⊕ V × V
abbrev Assignment (key : V → Bucket) (n : ℕ) (b : Bucket) := Fiber key b → Fin n
open Classical in
noncomputable def factor {F : Type*} [Field F] {n : ℕ} (H : SimpleGraph V)
(w : WeightKey n → F) (x : V → Fin n) : Token → F
| .inl i => w (.inl (i,x i))
| .inr (i,j) => if i < j ∧ H.Adj i j then w (.inr (i,j,x i,x j)) else 1
def owner (key : V → Bucket) : Token → Bag
| .inl i => (key i).getD ∅
| .inr (i,j) => (key i).getD ((key j).getD ∅)
def localAssignment {n : ℕ} (key : V → Bucket) (zero : Fin n) (z : Assignment key n none)
(k : Bag) (y : Assignment key n (some k)) (i : V) : Fin n :=
if h : key i = none then z ⟨i,h⟩ else if h' : key i = some k then y ⟨i,h'⟩ else zero
noncomputable def piece {F : Type*} [Field F] {n : ℕ} (H : SimpleGraph V) (key : V → Bucket)
(zero : Fin n) (z : Assignment key n none) (k : Bag) (y : Assignment key n (some k))
(w : WeightKey n → F) : F :=
∏ t ∈ Finset.univ.filter (fun t => owner key t = k), factor H w (localAssignment key zero z k y) t
def assignmentEquiv (key : V → Bucket) (n : ℕ) :
(V → Fin n) ≃ Assignment key n none × ((k : Bag) → Assignment key n (some k)) :=
(Equiv.piCongrFiberwise (f := key) (γ₁ := fun _ => Fin n)
(fun b => Equiv.refl (Assignment key n b))).trans Equiv.piOptionEquivProd
theorem local_matches {n : ℕ} (key : V → Bucket) (zero : Fin n)
(x : V → Fin n) (k : Bag) (i : V) (hi : key i = none ∨ key i = some k) :
localAssignment key zero (fun u => x u.val) k (fun u => x u.val) i = x i := by
rcases hi with h | h <;> simp [localAssignment,h]
theorem restrict_factor {F : Type*} [Field F] {n : ℕ} (H : SimpleGraph V) (key : V → Bucket)
(hedge : ∀ i j, H.Adj i j → key i = none ∨ key j = none ∨ key i = key j)
(zero : Fin n) (x : V → Fin n) (t : Token) (w : WeightKey n → F) :
let k := owner key t
factor H w (localAssignment key zero (fun u => x u.val) k (fun u => x u.val)) t =
factor H w x t := by
classical
cases t with
| inl i =>
change w (.inl (_,localAssignment _ _ _ _ _ i)) = w (.inl (_,x i))
rw [local_matches]
cases h : key i <;> simp [owner,h]
| inr v =>
obtain ⟨i,j⟩ := v
by_cases he : i < j ∧ H.Adj i j
· simp only [factor, if_pos he]
have h := hedge i j he.2
have hi : key i = none ∨ key i = some (owner key (.inr (i,j))) := by
cases hi : key i <;> simp [owner,hi]
have hj : key j = none ∨ key j = some (owner key (.inr (i,j))) := by
cases hi : key i <;> cases hj : key j <;> simp_all [owner]
rw [local_matches _ _ _ _ _ hi, local_matches _ _ _ _ _ hj]
· simp [factor,he]
theorem factorization {F : Type*} [Field F] {n : ℕ} (H : SimpleGraph V) (key : V → Bucket)
(hedge : ∀ i j, H.Adj i j → key i = none ∨ key j = none ∨ key i = key j)
(zero : Fin n) (w : WeightKey n → F) :
weightedSum H w = ∑ z : Assignment key n none, ∏ k : Bag,
∑ y : Assignment key n (some k), piece H key zero z k y w := by
classical
have localProd (x : V → Fin n) :
(∏ t : Token, factor H w x t) =
∏ k : Bag, piece H key zero (fun u => x u.val) k (fun u => x u.val) w := by
rw [← Finset.prod_fiberwise Finset.univ (owner key)]
apply Finset.prod_congr rfl
intro k _
apply Finset.prod_congr rfl
intro t ht
have hk := (Finset.mem_filter.mp ht).2
subst k
exact (restrict_factor H key hedge zero x t w).symm
let e := assignmentEquiv key n
calc
weightedSum H w = ∑ x : V → Fin n, ∏ t : Token, factor H w x t := by
simp [weightedSum, Fintype.prod_sum_type, Fintype.prod_prod_type, factor]
_ = ∑ x : V → Fin n, ∏ k : Bag, piece H key zero ((e x).1) k ((e x).2 k) w :=
Finset.sum_congr rfl fun x _ => localProd x
_ = ∑ p : Assignment key n none × ((k : Bag) → Assignment key n (some k)),
∏ k : Bag, piece H key zero p.1 k (p.2 k) w := e.sum_comp (fun p => ∏ k : Bag, piece H key zero p.1 k (p.2 k) w)
_ = _ := by
rw [Fintype.sum_prod_type]
simp_rw [Fintype.prod_sum]
end VWZClique.SparseProof
end
/- UniformFoldEvaluator -/
section
open VWZClique VWZClique.FoldProof VWZClique.WeightedProof
namespace VWZClique.UniformFolds
abbrev LeafEval (L : ℕ) :=
(H : SimpleGraph V) → (¬ HasWedges H) → (WeightKey (2^L) → ℚ) → ℚ
open SparseProof in
noncomputable def leafKey (H : SimpleGraph V) (hw : ¬ HasWedges H) : V → Bucket :=
Classical.choose (matching_partition H hw)
open SparseProof in
noncomputable def sparseLeaf (L : ℕ) : LeafEval L := fun H hw w =>
let key := leafKey H hw
let zero : Fin (2^L) := ⟨0,by positivity⟩
∑ z : Assignment key (2^L) none, ∏ b : Bag,
∑ y : Assignment key (2^L) (some b), piece H key zero z b y w
open SparseProof in
theorem sparseLeaf_correct (L : ℕ) (H : SimpleGraph V) (hw : ¬ HasWedges H)
(w : WeightKey (2^L) → ℚ) : sparseLeaf L H hw w = weightedSum H w :=
(factorization H (leafKey H hw) (Classical.choose_spec (matching_partition H hw)).2.2 _ w).symm
end VWZClique.UniformFolds
end
/- IntegerTiling -/
section
namespace VWZClique.Double.IntegerTiling
theorem exact_shape (L q : ℕ) : blocks L q * side L q = (2^L)^3 := by
have h := Nat.div_le_self L q
unfold blocks side
rw [← pow_add, ← pow_mul]
congr 1
omega
end VWZClique.Double.IntegerTiling
end
/- UniformFoldBudget -/
section
namespace VWZClique.UniformFolds
/-- One projection and the actual numbers of left, right and double-mask calls.
The three per-call units allow for coefficient multiplications and accumulation. -/
def splitWork (m projection prep left right both : ℕ) : ℕ :=
projection + m*(prep+left+3) + m*(prep+right+3) + m^2*(prep+both+3) + 3
/-- Integer scalar-work recurrence for the same static windows and graph branches
as the evaluator. Local setup and sparse leaves may each cost U n^5, preparing a
single child's weights may cost G n^2, and the transform constant is T. -/
noncomputable def planWork (mm : ℕ → ℕ) (T U G L : ℕ) : {H : SimpleGraph V} → Plan H → ℕ
| _,.leaf _ _ => U*(2^L)^5
| _,.split H _ _ kids =>
let e := Nat.card H.edgeSet
let q := windowExpansion (windowAt e) L
splitWork (Fintype.card q.Index)
(projectionWork mm T (tileAt e) L q.labels.card + U*(2^L)^5) (G*(2^L)^2)
(planWork mm T U G L (kids .left)) (planWork mm T U G L (kids .right))
(planWork mm T U G L (kids .both))
end VWZClique.UniformFolds
end
/- IntegerFoldEvaluation -/
section
open VWZClique VWZClique.SparseProof
namespace VWZClique.UniformFolds
def bitValue (x : ℚ) : ℤ := if x=1 then 1 else 0
theorem bitValue_cast {x : ℚ} (h : Binary x) : (bitValue x:ℚ) = x := by
rcases h with rfl | rfl <;> norm_num [bitValue]
open Classical in
noncomputable def integerFactor {n : ℕ} (H : SimpleGraph V) (w : WeightKey n → ℚ)
(x : V → Fin n) : Token → ℤ
| .inl i => bitValue (w (.inl (i,x i)))
| .inr (i,j) => if i < j ∧ H.Adj i j then bitValue (w (.inr (i,j,x i,x j))) else 1
theorem integerFactor_cast {n : ℕ} (H : SimpleGraph V) (w : WeightKey n → ℚ)
(hw : ∀ k, Binary (w k)) (x : V → Fin n) (t : Token) :
(integerFactor H w x t:ℚ) = factor H w x t := by
classical
cases t with
| inl i => exact bitValue_cast (hw _)
| inr a =>
obtain ⟨i,j⟩ := a
by_cases he : i < j ∧ H.Adj i j <;> simp [integerFactor,factor,he,bitValue_cast (hw _)]
/-- Evaluate the static sparse partition using integer products and sums. -/
noncomputable def integerLeaf (L : ℕ) (H : SimpleGraph V) (hh : ¬ HasWedges H)
(w : WeightKey (2^L) → ℚ) : ℤ :=
let key := leafKey H hh
let zero : Fin (2^L) := ⟨0,by positivity⟩
∑ z : Assignment key (2^L) none, ∏ b : Bag,
∑ y : Assignment key (2^L) (some b), ∏ t ∈ Finset.univ.filter (fun t => owner key t = b),
integerFactor H w (localAssignment key zero z b y) t
theorem integerLeaf_cast (L : ℕ) (H : SimpleGraph V) (hh : ¬ HasWedges H)
(w : WeightKey (2^L) → ℚ) (hw : ∀ k, Binary (w k)) :
(integerLeaf L H hh w:ℚ) = sparseLeaf L H hh w := by
simp only [integerLeaf,sparseLeaf,piece,Int.cast_sum,Int.cast_prod,integerFactor_cast H w hw]
/-- Integer addition, subtraction, multiplication and exact quotient suffice
throughout the signed recursion on binary weight tables. -/
noncomputable def integerPlan (L : ℕ) :
{H : SimpleGraph V} → Plan H → (WeightKey (2^L) → ℚ) → ℤ
| _,.leaf H hh,w => integerLeaf L H hh w
| _,.split H π _ kids,w =>
let K := windowAt (Nat.card H.edgeSet)
let q := windowExpansion K L
let call (d : Branch) (a b : Option (Mask L)) :=
integerPlan L (kids d) ((Round.mk H π a b).apply w)
integerTrace K L H π w +
(∑ i, q.coefficients i * call .left (some (q.masks i)) none) +
(∑ j, q.coefficients j * call .right none (some (q.masks j))) -
∑ i, ∑ j, (q.coefficients i * q.coefficients j) *
call .both (some (q.masks i)) (some (q.masks j))
end VWZClique.UniformFolds
end
/- NativeFoldTraversal -/
section
namespace VWZClique.NativeTraversal
open UniformFolds IntegerRAM IntegerRAM.Structured
noncomputable def childWeights {L : ℕ} (H : SimpleGraph V) (π : Equiv.Perm V) (c : Call L)
(w : WeightKey (2^L) → ℚ) := (Round.mk H π c.a c.b).apply w
end VWZClique.NativeTraversal
end
/- NativeFoldProgram -/
section
namespace VWZClique.NativeTraversal
open UniformFolds IntegerRAM IntegerRAM.Structured
open WeightedProof
structure Charges where
small : SimpleGraph V → ℕ
projection : SimpleGraph V → ℕ
push : SimpleGraph V → ℕ
pop : ℕ
reset : ℕ
finish : ℕ
end VWZClique.NativeTraversal
end
/- NativeLeafCore -/
section
namespace VWZClique.IntegerRAM.NativeLeaf
open Structured
open Graph.Table (wordIndex)
structure Data where
W : ℕ
n : ℕ
base : ℕ
w : WeightKey n → ℤ
pos : 0 < n
guard : ∀ j : ℕ, j ≤ n → Fits W ((j:ℤ)-n)
address : ∀ i : WeightKey n, Fits W ((base+wordIndex i : ℕ):ℤ)
structure Ready {I : Type} (p : Data) (r : I → ℤ) (x : I → Fin p.n) (m : Memory) : Prop where
base : m (-1) = p.base
dim : m (-2) = p.n
one : m (-3) = 1
vars : ∀ i, m (r i) = (x i).val
table : ∀ i, m ((p.base+wordIndex i : ℕ):ℤ) = p.w i
def Frame (z : ℤ) (m o : Memory) := ∀ a, z<a → o a=m a
theorem Frame.trans {z : ℤ} {m o v : Memory} (a : Frame z m o) (b : Frame z o v) : Frame z m v :=
fun k h => (b k h).trans (a k h)
theorem Frame.weaken {z z' : ℤ} {m o : Memory} (f : Frame z m o) (h : z ≤ z') : Frame z' m o :=
fun k hk => f k (by omega)
theorem frameUpdate (m : Memory) (a z v : ℤ) (h : a≤z) : Frame z m (update m a v) := by
intro k hk
simp [update,show k≠a by omega]
theorem Ready.frame {I : Type} {p : Data} {r : I → ℤ} {x : I → Fin p.n} {m o : Memory}
(h : Ready p r x m) {z : ℤ} (hz : z < -3) (hr : ∀ i, z < r i) (f : Frame z m o) :
Ready p r x o :=
⟨(f _ (by omega)).trans h.base, (f _ (by omega)).trans h.dim, (f _ (by omega)).trans h.one,
fun i => (f _ (hr i)).trans (h.vars i),fun i => (f _ (by have := Int.natCast_nonneg (p.base+wordIndex i); omega)).trans (h.table i)⟩
abbrev Sem (I : Type) := (p : Data) → (I → Fin p.n) → ℤ
/-- A fixed machine block for all input sizes. Its scratch cells lie at or below z. -/
def Builds {I : Type} (d : ℕ) (f : Sem I) : Prop :=
∀ (z : ℤ), z < -3 → ∀ (r : I → ℤ), (∀ i, z<r i) → ∃ (c : Command) (C : ℕ),
∀ (p : Data) (x : I → Fin p.n) (m : Memory), Ready p r x m →
∃ t o, Runs p.W c m t o ∧ t ≤ C*p.n^d ∧ o z=f p x ∧ Frame z m o
theorem mono {I : Type} {f : Sem I} {d e : ℕ} (h : Builds d f) (hle : d≤e) : Builds e f := by
intro z hz r hr
obtain ⟨c,C,H⟩ := h z hz r hr
refine ⟨c,C,?_⟩
intro p x m ready
obtain ⟨t,o,run,cost,val,fr⟩ := H p x m ready
exact ⟨t,o,run,cost.trans (Nat.mul_le_mul_left _ (Nat.pow_le_pow_right p.pos hle)),val,fr⟩
theorem fromReg {I : Type} (f : Sem I) (reg : (I → ℤ) → ℤ)
(read : ∀ (p : Data) (r : I → ℤ) (x : I → Fin p.n) (m : Memory),
Ready p r x m → m (reg r)=f p x) : Builds 0 f := by
intro z hz r hr
refine ⟨.atom (.mul z (reg r) (-3)),1,?_⟩
intro p x m h
refine ⟨1,_,.atom (.mul _ _ _ _),by simp,?_,frameUpdate _ _ _ _ le_rfl⟩
simp [update,h.one,read p r x m h]
theorem one {I : Type} : Builds 0 (fun (_ : Data) (_ : I → _) => 1) :=
fromReg _ (fun _ => -3) (fun _ _ _ _ h => h.one)
theorem dim {I : Type} : Builds 0 (fun (p : Data) (_ : I → _) => (p.n:ℤ)) :=
fromReg _ (fun _ => -2) (fun _ _ _ _ h => h.dim)
theorem start {I : Type} : Builds 0 (fun (p : Data) (_ : I → _) => (p.base:ℤ)) :=
fromReg _ (fun _ => -1) (fun _ _ _ _ h => h.base)
theorem coord {I : Type} (i : I) : Builds 0 (fun (_ : Data) (x : I → _) => ((x i).val:ℤ)) :=
fromReg _ (fun r => r i) (fun _ _ _ _ h => h.vars i)
theorem zero {I : Type} : Builds 0 (fun (_ : Data) (_ : I → _) => 0) := by
intro z hz r hr
refine ⟨.atom (.sub z (-3) (-3)),1,?_⟩
intro p x m h
exact ⟨1,_,.atom (.sub _ _ _ _),by simp,by simp [update],frameUpdate _ _ _ _ le_rfl⟩
theorem binary {I : Type} {d : ℕ} {f g : Sem I} (hf : Builds d f) (hg : Builds d g)
(op : ℤ → ℤ → ℤ) (ins : ℤ → ℤ → ℤ → Atom)
(step : ∀ (W : ℕ) (m : Memory) (z a b : ℤ), Step W (ins z a b) m (update m z (op (m a) (m b)))) :
Builds d (fun p x => op (f p x) (g p x)) := by
intro z hz r hr
obtain ⟨u,C,hu⟩ := hf z hz r hr
obtain ⟨v,D,hv⟩ := hg (z-1) (by omega) r (fun i => lt_trans (by omega) (hr i))
refine ⟨.seq u (.seq v (.atom (ins z z (z-1)))),C+D+1,?_⟩
intro p x m ready
obtain ⟨s,o,rr,sc,sv,sf⟩ := hu p x m ready
obtain ⟨t,a,tt,tc,tv,tf⟩ := hv p x o (ready.frame hz hr sf)
refine ⟨_,_,rr.seq (tt.seq (.atom (step _ _ _ _ _))),?_,?_,
(sf.trans (tf.weaken (by omega))).trans (frameUpdate _ _ _ _ le_rfl)⟩
· have hp : 1 ≤ p.n^d := Nat.one_le_pow _ _ p.pos
rw [Nat.add_mul,Nat.add_mul,Nat.one_mul]; omega
· simp [update,tf z (by omega),sv,tv]
theorem plus {I : Type} {d : ℕ} {f g : Sem I} (hf : Builds d f) (hg : Builds d g) :
Builds d (fun p x => f p x + g p x) := binary hf hg (·+·) .add (fun _ => Step.add)
theorem times {I : Type} {d : ℕ} {f g : Sem I} (hf : Builds d f) (hg : Builds d g) :
Builds d (fun p x => f p x * g p x) := binary hf hg (·*·) .mul (fun _ => Step.mul)
theorem literal {I : Type} (k : ℕ) : Builds 0 (fun (_ : Data) (_ : I → _) => (k:ℤ)) := by
induction k with
| zero => simpa using (zero (I:=I))
| succ k ih => simpa using (plus ih (one (I:=I)))
theorem readKey {I : Type} (key : (p : Data) → (I → Fin p.n) → WeightKey p.n)
(hf : Builds 0 (fun p x => ((p.base+wordIndex (key p x):ℕ):ℤ))) :
Builds 0 (fun p x => p.w (key p x)) := by
intro z hz r hr
obtain ⟨u,C,hu⟩ := hf z hz r hr
refine ⟨.seq u (.atom (.load z z)),C+1,?_⟩
intro p x m h
obtain ⟨s,o,run,sc,sv,sf⟩ := hu p x m h
have fits : Fits p.W (o z) := sv ▸ p.address (key p x)
refine ⟨_,_,run.seq (.atom (.load _ _ _ fits)),by simpa using Nat.add_le_add_right sc 1,?_,
sf.trans (frameUpdate _ _ _ _ le_rfl)⟩
simp only [update,if_pos rfl,sv]
exact (h.frame hz hr sf).table _
end VWZClique.IntegerRAM.NativeLeaf
end
/- NativeLeafSum -/
section
namespace VWZClique.IntegerRAM.NativeLeaf
open Structured
theorem rename {I J : Type} {f : Sem I} {d : ℕ} (h : Builds d f) (ι : I → J) :
Builds d (fun p x => f p (x ∘ ι)) := by
intro z hz r hr
obtain ⟨c,C,H⟩ := h z hz (r ∘ ι) (fun i => hr (ι i))
refine ⟨c,C,?_⟩
intro p x m ready
exact H p (x ∘ ι) m ⟨ready.base,ready.dim,ready.one,fun i => ready.vars (ι i),ready.table⟩
def bind {I α : Type} (a : α) (x : I → α) : Option I → α := fun i => i.elim a x
/-- Bind a single summation index using one fixed loop under the published native semantics. -/
theorem sumOne {I : Type} {d : ℕ} {f : Sem (Option I)} (body : Builds d f) :
Builds (d+1) (fun p x => ∑ i : Fin p.n, f p (bind i x)) := by
intro z hz r hr
let ix := z-1
let fl := z-2
let tmp := z-3
let rr : Option I → ℤ := bind ix r
have ht : tmp < -3 := by dsimp [tmp]; omega
have hrr : ∀ i, tmp < rr i := by
intro i; cases i with
| none => change z-3 < z-1; omega
| some i => change z-3 < r i; have := hr i; omega
obtain ⟨u,C,hu⟩ := body tmp ht rr hrr
let step := Command.seq u (.atom (.add z z tmp))
let init := Command.seq (.atom (.sub z (-3) (-3))) (.atom (.sub ix (-3) (-3)))
refine ⟨.seq init (repeatN step ix (-3) (-2) fl), C+6,?_⟩
intro p x m ready
let g : ℕ → ℤ := fun j => if h : j < p.n then f p (bind ⟨j,h⟩ x) else 0
let pref (q : ℕ) := ∑ j ∈ Finset.range q, g j
let inv (q : ℕ) (s : Memory) := Ready p r x s ∧ s ix=(q:ℤ) ∧ s z=pref q ∧ Frame z m s
let m₁ := update m z 0
let m₂ := update m₁ ix 0
have first : Runs p.W (.atom (.sub z (-3) (-3))) m 1 m₁ := by
simpa [m₁] using Runs.atom (Step.sub (W:=p.W) m z (-3) (-3))
have second : Runs p.W (.atom (.sub ix (-3) (-3))) m₁ 1 m₂ := by
simpa [m₂] using Runs.atom (Step.sub (W:=p.W) m₁ ix (-3) (-3))
have hxz : ix < z := by dsimp [ix]; omega
have hfz : fl < z := by dsimp [fl]; omega
have htx : tmp < ix := by dsimp [tmp,ix]; omega
have htz : tmp < z := htx.trans hxz
have hzi : z ≠ ix := ne_of_gt hxz
have hif : ix ≠ fl := by dsimp [ix,fl]; omega
have baseFrame : Frame z m m₂ := (frameUpdate _ _ _ _ le_rfl).trans (frameUpdate _ _ _ _ hxz.le)
have initInv : inv 0 m₂ := ⟨ready.frame hz hr baseFrame,by simp [m₂,update],
by simp [m₂,m₁,update,hzi,pref],baseFrame⟩
have iteration (j : ℕ) (hj : j < p.n) (s : Memory) (hs : inv j s) :
∃ t : ℕ, t ≤ C*p.n^d+1 ∧ ∃ a : Memory, Runs p.W step s t a ∧
a ix=j ∧ a (-3)=1 ∧ a (-2)=p.n ∧ inv (j+1) (nextMemory a ix fl j p.n) := by
obtain ⟨sready,six,sz,sframe⟩ := hs
let v : Fin p.n := ⟨j,hj⟩
have sbody : Ready p rr (bind v x) s := by
refine ⟨sready.base,sready.dim,sready.one,?_,sready.table⟩
intro i; cases i with
| none => exact six
| some i => exact sready.vars i
obtain ⟨t,b,run,cost,bv,bf⟩ := hu p (bind v x) s sbody
let a := update b z (b z+b tmp)
have frA : Frame z m a :=
(sframe.trans (bf.weaken htz.le)).trans (frameUpdate _ _ _ _ le_rfl)
have ra := ready.frame hz hr frA
have aix : a ix=j := by simp [a,update,ne_of_lt hxz,bf ix htx,six]
have suma : a z=pref (j+1) := by simp [a,update,bf z htz,sz,bv,pref,Finset.sum_range_succ,g,hj,v]
have frB : Frame z m (nextMemory a ix fl j p.n) :=
(frA.trans (frameUpdate _ _ _ _ hxz.le)).trans (frameUpdate _ _ _ _ hfz.le)
refine ⟨t+1,Nat.add_le_add_right cost 1,a,run.seq (.atom (.add _ _ _ _)),aix,ra.one,ra.dim,
ready.frame hz hr frB,?_,?_,frB⟩
· simp [nextMemory,update,hif]
· simpa [nextMemory,update,hzi,ne_of_gt hfz] using suma
obtain ⟨cost,cb,o,run,oval⟩ := repeatN_runs (B:=C*p.n^d+1) p.pos step
(show (-2:ℤ) ≠ ix by dsimp [ix]; omega) inv p.guard iteration initInv
have final : pref p.n = ∑ i : Fin p.n, f p (bind i x) := by
change (∑ j ∈ Finset.range p.n, g j) = _
rw [← Fin.sum_univ_eq_sum_range g]
simp [g]
refine ⟨_,o,(first.seq second).seq run,?_,oval.2.2.1.trans final,oval.2.2.2⟩
have hp : 1 ≤ p.n^d := Nat.one_le_pow _ _ p.pos
have scale : p.n ≤ p.n^d * p.n := by simpa using Nat.mul_le_mul_right p.n hp
have pos := p.pos
rw [pow_succ]
calc
_ ≤ 2 + p.n*(C*p.n^d+1+3) := Nat.add_le_add_left cb _
_ ≤ (C+6)*(p.n^d*p.n) := by nlinarith
end VWZClique.IntegerRAM.NativeLeaf
end
/- NativeLeafBind -/
section
namespace VWZClique.IntegerRAM.NativeLeaf
theorem extBuild {I : Type} {d : ℕ} {f g : Sem I} (h : Builds d f)
(eqn : ∀ p x, f p x = g p x) : Builds d g :=
(show f=g from funext fun p => funext (eqn p)) ▸ h
def route {I : Type} (l : ℕ) : I ⊕ Fin (l+1) → Option I ⊕ Fin l :=
Sum.elim (fun i => .inl (some i)) (Fin.cases (.inl none) Sum.inr)
theorem sumFin {d : ℕ} (l : ℕ) {I : Type} {f : Sem (I ⊕ Fin l)} (h : Builds d f) :
Builds (d+l) (fun p x => ∑ y : Fin l → Fin p.n, f p (Sum.elim x y)) := by
induction l generalizing I with
| zero =>
let e : I ⊕ Fin 0 → I := Sum.elim id Fin.elim0
apply extBuild (rename h e)
intro p x
rw [Fintype.sum_unique]
congr 1
funext i
cases i with
| inl i => rfl
| inr i => exact i.elim0
| succ l ih =>
have sub := ih (rename h (route (I:=I) l))
apply extBuild (sumOne sub)
intro p x
let F (y : Fin (l+1) → Fin p.n) := f p (Sum.elim x y)
let e := Fin.consEquiv (fun _ : Fin (l+1) => Fin p.n)
change _ = ∑ y, F y
rw [← e.sum_comp F, Fintype.sum_prod_type]
apply Finset.sum_congr rfl
intro a _
apply Finset.sum_congr rfl
intro b _
apply congrArg (f p)
funext i
cases i with
| inl i => rfl
| inr i =>
exact Fin.cases (motive:=fun i => ((Sum.elim (bind a x) b) ∘ route l) (.inr i) = Sum.elim x (e (a,b)) (.inr i))
rfl (fun _ => rfl) i
theorem sumVars {I J : Type} [Fintype J] [DecidableEq J] {d : ℕ} {f : Sem (I ⊕ J)} (h : Builds d f) :
Builds (d+Fintype.card J) (fun p x => ∑ y : J → Fin p.n, f p (Sum.elim x y)) := by
classical
let e := Fintype.equivFin J
let up : I ⊕ J → I ⊕ Fin (Fintype.card J) := Sum.map id e
apply extBuild (sumFin _ (rename h up))
intro p x
let E := e.symm.arrowCongr (Equiv.refl (Fin p.n))
rw [← E.sum_comp (fun y => f p (Sum.elim x y))]
apply Finset.sum_congr rfl
intro y _
apply congrArg (f p)
funext i
cases i <;> rfl
theorem product {I J : Type} {d : ℕ} (s : Finset J) (f : J → Sem I)
(h : ∀ j ∈ s, Builds d (f j)) : Builds d (fun p x => ∏ j ∈ s, f j p x) := by
classical
induction s using Finset.induction_on with
| empty => simpa using mono (one (I:=I)) (Nat.zero_le d)
| @insert j s hj ih =>
have g := times (h j (by simp)) (ih (fun k hk => h k (Finset.mem_insert_of_mem hk)))
simpa [Finset.prod_insert,hj] using g
end VWZClique.IntegerRAM.NativeLeaf
end
/- NativeLeaf -/
section
namespace VWZClique.IntegerRAM.NativeLeaf
open SparseProof
open Graph.Table (wordIndex)
abbrev Label (I : Type) := (p : Data) → (I → Fin p.n) → Fin p.n
theorem unary {I : Type} (i : V) (a : Label I) (ha : Builds 0 (fun p x => ((a p x).val:ℤ))) :
Builds 0 (fun p x => p.w (.inl (i,a p x))) := by
apply readKey (fun p x => .inl (i,a p x))
simpa only [wordIndex,Nat.cast_add,Nat.cast_mul] using
plus (start (I:=I)) (plus (times (literal i.val) dim) ha)
theorem edge {I : Type} (i j : V) (a b : Label I)
(ha : Builds 0 (fun p x => ((a p x).val:ℤ))) (hb : Builds 0 (fun p x => ((b p x).val:ℤ))) :
Builds 0 (fun p x => p.w (.inr (i,j,a p x,b p x))) := by
apply readKey (fun p x => .inr (i,j,a p x,b p x))
simpa only [wordIndex,Nat.cast_add,Nat.cast_mul,Nat.cast_ofNat] using
plus (start (I:=I)) (plus (plus (plus (times (literal 9) dim)
(times (literal (i.val*9+j.val)) (times dim dim))) (times ha dim)) hb)
abbrev Inner (key : V → Bucket) (b : Bag) := Fiber key none ⊕ Fiber key (some b)
def label (key : V → Bucket) (b : Bag) (i : V) : Label (Inner key b) := fun p x =>
localAssignment key ⟨0,p.pos⟩ (fun u => x (.inl u)) b (fun u => x (.inr u)) i
theorem label_build (key : V → Bucket) (b : Bag) (i : V) :
Builds 0 (fun p x => ((label key b i p x).val:ℤ)) := by
by_cases hc : key i = none
· simpa [label,localAssignment,hc] using (coord (I:=Inner key b) (.inl ⟨i,hc⟩))
by_cases hb : key i = some b
· simpa [label,localAssignment,hc,hb] using (coord (I:=Inner key b) (.inr ⟨i,hb⟩))
· simpa [label,localAssignment,hc,hb] using (zero (I:=Inner key b))
open Classical in
noncomputable def rawFactor (H : SimpleGraph V) (key : V → Bucket) (b : Bag) : Token → Sem (Inner key b)
| .inl i => fun p x => p.w (.inl (i,label key b i p x))
| .inr (i,j) => if i<j ∧ H.Adj i j then
fun p x => p.w (.inr (i,j,label key b i p x,label key b j p x)) else fun _ _ => 1
theorem factor_build (H : SimpleGraph V) (key : V → Bucket) (b : Bag) (t : Token) :
Builds 0 (rawFactor H key b t) := by
classical
cases t with
| inl i => exact unary _ _ (label_build _ _ _)
| inr ij =>
rcases ij with ⟨i,j⟩
by_cases h : i<j ∧ H.Adj i j
· simpa [rawFactor,h] using edge i j _ _ (label_build key b i) (label_build key b j)
· simpa [rawFactor,h] using (one (I:=Inner key b))
noncomputable def bagProduct (H : SimpleGraph V) (key : V → Bucket) (b : Bag) : Sem (Inner key b) :=
fun p x => ∏ t ∈ Finset.univ.filter (fun t => owner key t = b), rawFactor H key b t p x
noncomputable def bagSum (H : SimpleGraph V) (key : V → Bucket) (b : Bag) : Sem (Fiber key none) :=
fun p z => ∑ y : Assignment key p.n (some b), bagProduct H key b p (Sum.elim z y)
noncomputable def rawLeaf (H : SimpleGraph V) (key : V → Bucket) (p : Data) :=
∑ z : Assignment key p.n none, ∏ b : Bag, bagSum H key b p z
theorem raw_build (H : SimpleGraph V) (key : V → Bucket)
(hroot : Fintype.card (Fiber key none) ≤ 3)
(hbag : ∀ b, Fintype.card (Fiber key (some b)) ≤ 2) :
Builds 5 (fun (p : Data) (_ : Empty → _) => rawLeaf H key p) := by
classical
have localB (b : Bag) : Builds 0 (bagProduct H key b) :=
product _ _ (fun t _ => factor_build H key b t)
have smallB (b : Bag) : Builds 2 (bagSum H key b) :=
mono (sumVars (localB b)) (by simpa using hbag b)
have pieces := product Finset.univ (fun b => bagSum H key b) (fun b _ => smallB b)
have closed := sumVars (rename pieces (Sum.inr : Fiber key none → Empty ⊕ Fiber key none))
apply (mono (f:=fun (p:Data) (_ : Empty → _) => rawLeaf H key p) _ (by omega : 2+Fintype.card (Fiber key none)≤5))
exact closed
theorem raw_cast (H : SimpleGraph V) (key : V → Bucket) (b : Bag) (t : Token)
(p : Data) (z : Assignment key p.n none) (y : Assignment key p.n (some b)) :
(rawFactor H key b t p (Sum.elim z y):ℚ) =
factor H (fun a => (p.w a:ℚ)) (localAssignment key ⟨0,p.pos⟩ z b y) t := by
classical
cases t with
| inl i => rfl
| inr ij =>
rcases ij with ⟨i,j⟩
by_cases h : i<j ∧ H.Adj i j <;> simp [rawFactor,factor,h,label]
theorem raw_correct (H : SimpleGraph V) (key : V → Bucket)
(hedge : ∀ i j, H.Adj i j → key i=none ∨ key j=none ∨ key i=key j) (p : Data) :
(rawLeaf H key p:ℚ) = weightedSum H (fun i => (p.w i:ℚ)) := by
classical
rw [factorization H key hedge ⟨0,p.pos⟩]
simp only [rawLeaf,bagSum,bagProduct,piece,Int.cast_sum,Int.cast_prod,raw_cast]
/-- One command per fixed wedge-free pattern evaluates any table in the contiguous
layout, with a dimension-independent constant times n^5 instructions. It preserves
all addresses above the return register, including its input and caller registers. -/
theorem sparse_native (H : SimpleGraph V) (hw : ¬ ∃ f g : Fin 3 → V,
wedge H f ∧ wedge H g ∧ ∀ i j, f i ≠ g j) (dst : ℤ) (hdst : dst < -3) :
∃ (c : Structured.Command) (C : ℕ), ∀ (p : Data) (m : Memory),
Ready p (Empty.elim : Empty → ℤ) (Empty.elim : Empty → Fin p.n) m →
∃ t o, Structured.Runs p.W c m t o ∧ t≤C*p.n^5 ∧
(o dst:ℚ)=weightedSum H (fun i => (p.w i:ℚ)) ∧ Frame dst m o := by
obtain ⟨key,hroot,hbags,edges⟩ := matching_partition H hw
obtain ⟨c,C,run⟩ := raw_build H key hroot hbags dst hdst Empty.elim (fun i => i.elim)
refine ⟨c,C,?_⟩
intro p m hm
obtain ⟨t,o,rr,cc,rv,fr⟩ := run p Empty.elim m hm
exact ⟨t,o,rr,cc,(congrArg (Int.cast : ℤ → ℚ) rv).trans (raw_correct H key edges p),fr⟩
end VWZClique.IntegerRAM.NativeLeaf
end
/- NativeLeafWord -/
section
namespace VWZClique.IntegerRAM.NativeLeaf
open Graph.Table (wordIndex)
open Structured UniformFolds TrulySubcubicAPSP
theorem index_lt {n : ℕ} (i : WeightKey n) : wordIndex i < 9*n+81*(n*n) := by
rcases i with ⟨j,x⟩|⟨i,j,x,y⟩
· have a := Nat.mul_le_mul_right n j.isLt
rw [Nat.succ_mul] at a
have := x.isLt
change j.val*n+x.val < _
omega
· have ix : i.val*9+j.val<81 := by have := i.isLt; have := j.isLt; omega
have a := Nat.mul_le_mul_right (n*n) ix
have b := Nat.mul_le_mul_right n x.isLt
rw [Nat.succ_mul] at a b
have := y.isLt
change 9*n+(i.val*9+j.val)*(n*n)+x.val*n+y.val < _
omega
def inputData {W n base M : ℕ} (hn : 0<n) (cap : Graph.Division.Room W M)
(room : base+9*n+81*(n*n)≤M) (w : WeightKey n → ℤ) : Data where
W := W
n := n
base := base
w := w
pos := hn
guard := by
intro j hj
apply cap.fits <;> omega
address := by
intro i
have := index_lt i
apply cap.fits <;> omega
end VWZClique.IntegerRAM.NativeLeaf
end
/- NativeFrameStack -/
section
namespace VWZClique.IntegerRAM.NativeFrame
open Structured UniformFolds NativeTraversal
theorem StackLayout.transferAll (lay : StackLayout) (d : ℕ) (H : SimpleGraph V) (m o : Memory)
(fr : ∀ a : ℕ, 297≤a → o a=m a) : lay.prepared d H m → lay.prepared d H o :=
lay.transfer d H m o (fun a ha _ => fr a (le_trans (by decide : 297≤512) ((lay.large d).trans ha)))
theorem Globals.transfer {L lay} {m o : Memory} (h : Globals L lay m)
(dim : o 0=m 0) (len : o 320=m 320) (out : o 321=m 321) : Globals L lay o :=
⟨dim.trans h.dim,len.trans h.length,out.trans h.output⟩
theorem weights_transfer {L : ℕ} {lay : StackLayout} {d w} {m o : Memory} (h : @Weights L lay d w m)
(ptr : o (reg d .weights)=m (reg d .weights)) (fr : ∀ a : ℕ, 297≤a → o a=m a) :
Weights lay d w o :=
⟨ptr.trans h.1,fun a => (congrArg (Int.cast : ℤ → ℚ)
(fr (lay.base d+Graph.Table.wordIndex a) (le_trans (by decide : 297≤512) (le_trans (lay.large d) (Nat.le_add_right _ _))))).trans (h.2 a)⟩
theorem saved_transfer {L} (lay : StackLayout) (d : ℕ) (s : List (NativeTraversal.Slot L)) {m o : Memory}
(plane : ∀ a : ℕ, 297≤a → o a=m a) (regs : ∀ i<d, ∀ f, o (reg i f)=m (reg i f))
(pre : Saved lay d s m) : Saved lay d s o := by
induction s generalizing d with
| nil => trivial
| cons h t ih =>
obtain ⟨lt,vd,arm,tail⟩ := pre
refine ⟨lt,?_,?_,ih _ (fun j hj f => regs j (hj.trans lt) f) tail⟩
· cases h with
| input n w => exact weights_transfer vd (regs n lt _) plane
| value n z => exact (regs n lt _).trans vd
| cursor n H π b w i z =>
obtain ⟨a,c,l,ix,v⟩ := vd
exact ⟨weights_transfer a (regs n lt _) plane,lay.transferAll _ _ _ _ plane c,
fun j => (regs n lt _).trans (l j),(regs n lt _).trans ix,(regs n lt _).trans v⟩
· cases h with
| input => exact False.elim arm
| value => exact False.elim arm
| cursor n H π b w i z =>
obtain ⟨hi,hc⟩ := arm
exact ⟨hi,(regs n lt _).trans hc⟩
theorem distinctData {a d : ℕ} (ha : 297 ≤ a) (hd : d ≤ 36) (f : Field) : (a:ℤ)≠reg d f := by
have := reg_below hd f; omega
end VWZClique.IntegerRAM.NativeFrame
end
/- CliqueIntegerPlan -/
section
/-! Apply the integer recursion to the original graph at every input size. -/
namespace VWZClique.BlockReduction
open UniformFolds WeightedProof OAI.MatrixMultiplication.Arithmetic
def graphLength (n k : ℕ) := Nat.clog 2 (n^((k+8)/9))
/-- Put the grouped weights in the next dyadic domain, zeroing the added entries. -/
noncomputable def graphWeights {n : ℕ} (G : SimpleGraph (Fin n)) (hn : 0 < n) (k : ℕ)
(i : WeightKey (2^graphLength n k)) : ℚ :=
literal (weights (F := ℚ) (t := (k+8)/9) G k ⟨0,hn⟩) (padTag i)
end VWZClique.BlockReduction
end
/- NativeSquareExpr -/
section
namespace VWZClique.IntegerRAM.SquareCode
open Structured
/-- Straight-line formulas for one kernel write, with address arithmetic and
indirect loads. Registers and heap cells above the scratch area are readable. -/
inductive Expr where
| zero | one | reg (i : ℤ) | read (a : Expr)
| add (a b : Expr) | sub (a b : Expr) | mul (a b : Expr)
deriving Inhabited
def binary (a b : Command) (op : Atom) := Command.seq a (.seq b (.atom op))
def Expr.code (d : ℤ) : Expr → Command
| .zero => .atom (.sub d d d)
| .one => .atom (.one d)
| .reg i => .seq (.atom (.sub d d d)) (.atom (.add d d i))
| .read a => .seq (a.code d) (.atom (.load d d))
| .add a b => binary (a.code d) (b.code (d-1)) (.add d d (d-1))
| .sub a b => binary (a.code d) (b.code (d-1)) (.sub d d (d-1))
| .mul a b => binary (a.code d) (b.code (d-1)) (.mul d d (d-1))
def Expr.steps : Expr → ℕ
| .zero | .one => 1
| .reg _ => 2
| .read a => a.steps+1
| .add a b | .sub a b | .mul a b => a.steps+(b.steps+1)
def Expr.num : ℕ → Expr
| 0 => .zero
| n+1 => .add (num n) .one
def Expr.int : ℤ → Expr
| .ofNat n => num n
| .negSucc n => .sub .zero (num (n+1))
/-- Compute the destination and value independently then store one word.
The negative scratch segment may be overwritten. -/
def write (d : ℤ) (addr value : Expr) : Command :=
.seq (addr.code d) (.seq (value.code (d-1)) (.atom (.store d (d-1))))
end VWZClique.IntegerRAM.SquareCode
end
/- NativeSquareRegs -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
/-- Read the data registers for one (parent, child-row, child-column) kernel.
All compiled formulas use scratch at or below register -128. -/
def base := Expr.reg (-1)
def nodes := Expr.reg (-2)
def side := Expr.reg (-3)
def node := Expr.reg (-4)
def row := Expr.reg (-5)
def col := Expr.reg (-6)
def floor : ℤ := -128
def num := Expr.num
def plus := Expr.add
def times := Expr.mul
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareControl -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured
/-- Assign a register using the expression scratch segment. -/
def assign (reg : ℤ) (e : Expr) := Command.seq (e.code floor)
(.seq (.atom (.sub reg reg reg)) (.atom (.add reg reg floor)))
def divOne : ℤ := -10
def divK : ℤ := -11
def divQ : ℤ := -12
def divTest : ℤ := -13
def quotientBody (num : ℤ) := Command.seq (.atom (.sub num num divK))
(.seq (.atom (.add divQ divQ divOne)) (.atom (.sub divTest divTest divTest)))
-- A negative remainder is the loop guard, so an exact positive multiple
-- performs precisely q subtraction rounds.
def quotientIter (num : ℤ) := Command.seq (quotientBody num) (.atom (.sub divTest divTest num))
def quotientCmd (d : ℕ) (num : ℤ) := Command.seq (assign divK (Expr.num d))
(.seq (.atom (.one divOne))
(.seq (.atom (.sub divQ divQ divQ))
(.seq (.repeatWhileNegative (quotientIter num) divTest)
(assign num (.reg divQ)))))
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeDyadicWrite -/
section
namespace VWZClique.IntegerRAM.DyadicCell
open Graph Structured SquareCode
def space (N : ℕ) := 9*N+81*(N*N)
def origin (n₀ : ℕ) := 1+n₀*n₀
def target (n₀ N : ℕ) := origin n₀+space N
end VWZClique.IntegerRAM.DyadicCell
end
/- NativeSquareGrid -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured
def loop (i lim : ℤ) (body : Command) := Command.seq (.atom (.one (-7))) <|
.seq (.atom (.sub i i i)) (repeatN body i (-7) lim (-8))
/-- Parent, row and column are generated by three nested loops, with no
division or remainder operations for unpacking a linear address. -/
def grid (body : Command) := loop (-4) (-2) (loop (-5) (-3) (loop (-6) (-3) body))
def gridCost (N side B : ℕ) := 2+N*((2+side*((2+side*(B+3))+3))+3)
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeDyadicGraph -/
section
namespace VWZClique.IntegerRAM.DyadicCell
open Structured Graph BlockReduction
theorem header_floor {n : ℕ} (hn : 32≤n) (N : ℕ) : 512≤target n N := by
have := Nat.mul_le_mul hn hn
unfold target origin; omega
end VWZClique.IntegerRAM.DyadicCell
end
/- NativeArenaLayout -/
section
namespace VWZClique.IntegerRAM.NativeArena
open NativeFrame NativeTraversal UniformFolds BlockReduction MaskScan.Arena
noncomputable def forGraph (n k : ℕ) (hn : 32≤n) : StackLayout :=
layout (graphLength n k) (DyadicCell.target n (n^((k+8)/9))) (DyadicCell.origin n) (DyadicCell.header_floor hn _)
end VWZClique.IntegerRAM.NativeArena
end
/- NativeProjectionArena -/
section
namespace VWZClique.IntegerRAM.Projected
open Structured UniformFolds NativeFrame NativeTraversal NativeArena
/-- The live prefix at the instant the projection starts. Temporary pointer
words and compact-table storage above the parent weights may be overwritten. -/
def projectionPrefix (base n j : ℕ) :=
j<297 ∨ j=320 ∨ j=321 ∨ 512≤j ∧ j < metaBase base n
end VWZClique.IntegerRAM.Projected
end
/- NativeProjectionSetup -/
section
namespace VWZClique.IntegerRAM.Projected.Setup
open Structured SquareCode SquareCode.Layout
def readWord (i : ℕ) := Expr.read (.num i)
end VWZClique.IntegerRAM.Projected.Setup
end
/- NativeProjectionHeaders -/
section
namespace VWZClique.IntegerRAM.Projected.Headers
open Structured SquareCode SquareCode.Layout
/-- All per-call constants come from fixed positive header slots. A header
expression never depends on negative registers clobbered by an earlier call. -/
inductive Value where
| nat (v : ℕ)
| word (src : ℕ)
| add (a b : Value)
| mul (a b : Value)
deriving DecidableEq
def Value.expr : Value → Expr
| .nat v => .num v
| .word k => Setup.readWord k
| .add a b => .add a.expr b.expr
| .mul a b => .mul a.expr b.expr
abbrev Fields := List (ℤ × Value)
def command : Fields → Command
| [] => .skip
| a::xs => .seq (command xs) (assign a.1 a.2.expr)
def time : Fields → ℕ
| [] => 0
| a::xs => time xs+(a.2.expr.steps+2)
end VWZClique.IntegerRAM.Projected.Headers
end
/- NativeProjectionTiles -/
section
namespace VWZClique.IntegerRAM.Projected
abbrev Tile (s : ℕ) := Matrix (Fin s) (Fin s) ℤ
end VWZClique.IntegerRAM.Projected
end
/- NativeProjectionWorkspace -/
section
namespace VWZClique.IntegerRAM.Projected.Workspace
/-- Retained labels and recursive mask data end at `start`; all projector
writes lie in this suffix. A level uses two packed arrays of length 8^h. -/
def level (start : ℕ) : ℕ → ℕ
| 0 => start
| h+1 => level start h+2*8^h
structure Banks where
support : ℕ
left : ℕ
middle : ℕ
right : ℕ
transform : ℕ
weights : ℕ
packetsLeft : ℕ
packetsRight : ℕ
output : ℕ
/-- Four dense tables and three padded tile banks each reserve at most N^6
words. Small products can reuse the three tile banks before packing begins. -/
def banks (start n : ℕ) : Banks :=
let lb := start+4*n^3
let step := n^6
⟨start,lb,lb+step,lb+2*step,lb+3*step,lb+4*step,lb+5*step,lb+6*step,lb+7*step⟩
end VWZClique.IntegerRAM.Projected.Workspace
end
/- NativeProjectionInit -/
section
namespace VWZClique.IntegerRAM.Projected.Init
open Structured Headers NativeFrame MaskScan RankSwap UniformFolds
def n : Value := .word 0
def mul (k : ℕ) (a : Value) : Value := .mul (.nat k) a
def sq : Value := .mul n n
def cube : Value := .mul sq n
def sixth : Value := .mul cube cube
def parent (d : ℕ) : Value := .word (8+8*d)
def orig (d : ℕ) : Value := .add (.add (parent d) (mul 9 n)) (mul 81 sq)
def slot (d i : ℕ) : Value := .add (orig d) (mul i cube)
def start (d : ℕ) : Value := .add (slot d 7) (.nat 2)
def dense (d i : ℕ) : Value := .add (.add (start d) (mul 4 cube)) (mul i sixth)
def fields (d : ℕ) : Fields := [(350,parent d),(356,dense d 4),(358,slot d 5),(370,slot d 6),
(371,dense d 0),(372,dense d 1),(373,dense d 2),(374,dense d 3),
(375,dense d 4),(376,dense d 5),(377,dense d 6),(378,dense d 7),(379,start d),
(380,.add (slot d 7) (.nat 1))]
def countExpr := SquareCode.Expr.read (.reg 380)
def command (d : ℕ) := Command.seq (Headers.command (fields d)) (SquareCode.Layout.assign 359 countExpr)
structure Params (base n count : ℕ) (m : Memory) : Prop where
weights : m 350=base
codeBase : m 358=Arena.slot base n 5
size : m 359=count
coefficients : m 370=Arena.slot base n 6
start : m 379 = (Arena.slot base n 7+2:ℕ)
source : m 371=(Workspace.banks (Arena.slot base n 7+2) n).left
middle : m 372=(Workspace.banks (Arena.slot base n 7+2) n).middle
right : m 373=(Workspace.banks (Arena.slot base n 7+2) n).right
raw : m 374=(Workspace.banks (Arena.slot base n 7+2) n).transform
smallWork : m 356=(Workspace.banks (Arena.slot base n 7+2) n).weights
wt : m 375=(Workspace.banks (Arena.slot base n 7+2) n).weights
leftPack : m 376=(Workspace.banks (Arena.slot base n 7+2) n).packetsLeft
rightPack : m 377=(Workspace.banks (Arena.slot base n 7+2) n).packetsRight
product : m 378=(Workspace.banks (Arena.slot base n 7+2) n).output
end VWZClique.IntegerRAM.Projected.Init
end
/- ProjectionFactors -/
section
open OAI.MatrixMultiplication.Arithmetic
namespace VWZClique.Projection
/-- On the support of a basis vector the first string fixes the second. -/
def partner {L : ℕ} (j : BasisLabel L) (s : Bits L) : Bits L :=
fun i => if j i = 0 then false else if j i = 1 then true else !(s i)
inductive Source where
| pivot (second : Bool)
| center
| other (i : Fin 3)
def nearSource (i : Fin 3) : Source :=
if i = 0 then .pivot false else if i = 1 then .pivot true else .center
def source (rev : Bool) : Slot → Source
| .inl i => if rev then .other i else nearSource i
| .inr i => if rev then nearSource i else .other i
inductive Group where
| pivotCenter
| pivotOther
| centerOther
deriving DecidableEq
/-- An ordered pair of positions can depend on at most two of the three inputs. -/
def group : Source → Source → Group
| .other _, .pivot _ | .pivot _, .other _ => .pivotOther
| .other _, _ | _, .other _ => .centerOther
| _, _ => .pivotCenter
abbrev Factor := Slot ⊕ Slot × Slot
def factorGroup (rev : Bool) : Factor → Group
| .inl i => group (source rev i) (source rev i)
| .inr (i,k) => group (source rev i) (source rev k)
end VWZClique.Projection
end
/- NativeProjectionFactors -/
section
namespace VWZClique.IntegerRAM.Projected.Factors
open Projection UniformFolds WeightedProof FoldProof SquareCode
/-! The pattern, wedge placement, channel and factor group are compile-time
parameters on each of the fixed plan's branches. All word sizes, vertex labels,
table addresses and assignment-domain lengths are runtime data. -/
abbrev sideReg : ℤ := -60
abbrev baseReg : ℤ := -61
def src (args : Source → Expr) (rev : Bool) (s : Slot) := args (source rev s)
def keyU (i : V) (x : Expr) : Expr :=
.read (.add (.reg baseReg) (.add (.mul (.num i.val) (.reg sideReg)) x))
def keyE (i j : V) (x y : Expr) : Expr :=
let n := Expr.reg sideReg
let off := Expr.add (.mul (.num 9) n) (.mul (.num (i.val*9+j.val)) (.mul n n))
.read (.add (.reg baseReg) (.add off (.add (.mul x n) y)))
def entry (args : Source → Expr) (π : Equiv.Perm V) (E : Finset EdgeSlot) (rev : Bool) (h : Fin 3) : Factor → Expr
| .inl (.inl i) => keyU (π (site h i)) (src args rev (.inl i))
| .inl (.inr _) => .one
| .inr (a,b) =>
let i := π (endpoint h a)
let j := π (endpoint h b)
if (h,a,b) ∈ E then
if i < j then keyE i j (src args rev a) (src args rev b) else keyE j i (src args rev b) (src args rev a)
else .one
def prodExpr (xs : List Expr) : Expr := xs.foldr Expr.mul .one
/-- These 42 flags and the shape of the straight-line code are independent of n and L. -/
noncomputable def component (args : Source → Expr) (π : Equiv.Perm V) (E : Finset EdgeSlot) (rev : Bool)
(h : Fin 3) (g : Group) : Expr :=
prodExpr ((Finset.univ : Finset Factor).toList.map
fun f => if factorGroup rev f=g then entry args π E rev h f else .one)
end VWZClique.IntegerRAM.Projected.Factors
end
/- NativeProjectionSlices -/
section
namespace VWZClique.IntegerRAM.Projected.Slices
open Projection UniformFolds TraceDyadic
variable {L : ℕ}
/-- A zero eigenbasis row need not store its partner. The two probe
transforms return packed vertex zero on those rows. -/
def lookupPartner (j : BasisLabel L) (x : Bits L) : Bits L :=
if basisInt j (x,partner j x)=0 then (wordIndex L).symm 0 else partner j x
end VWZClique.IntegerRAM.Projected.Slices
end
/- WordButterflyTransform -/
section
/-! A uniform native program for all bit lengths. A stage moves the leading raw
digit to a transformed trailing digit. After all stages the trailing labels
are in their original order. -/
namespace VWZClique.IntegerRAM.Butterfly
open Structured TrulySubcubicAPSP
def swapBuffers : List Atom := [
.one Reg.one, .sub Reg.zero Reg.one Reg.one,
.add Reg.swap Reg.srcBase Reg.zero, .add Reg.srcBase Reg.dstBase Reg.zero,
.add Reg.dstBase Reg.swap Reg.zero, .add Reg.stages Reg.stages Reg.one]
def iteration : Command := .seq stage (line swapBuffers)
def allStages : Command := .repeatWhileNegative iteration Reg.stages
def butterflySetupAtoms : List Atom := [.one Reg.one,.sub Reg.zero Reg.one Reg.one,
.sub Reg.swap Reg.stages Reg.one,.sub Reg.stages Reg.zero Reg.stages]
def full : Command := .seq (line butterflySetupAtoms) (.whenNonnegative Reg.swap allStages)
end VWZClique.IntegerRAM.Butterfly
end
/- WordButterflyLayout -/
section
/-! Explicit reversible indexing of all input pairs and output labels. -/
namespace VWZClique.IntegerRAM.Butterfly
open Structured TrulySubcubicAPSP
def splitLabel (l : ℕ) : BasisLabel (l+1) ≃ Fin 4 × BasisLabel l where
toFun j := (j 0,fun i => j i.succ)
invFun t := Fin.cons t.1 t.2
left_inv := by
intro j
funext i
exact Fin.cases rfl (fun _ => rfl) i
right_inv := by intro j; simp
/-- The successive base-four digits give a computable bijection with the contiguous
cells from zero up to the table size. -/
def labelIndex : (l : ℕ) → BasisLabel l ≃ Fin (4^l)
| 0 => {
toFun := fun _ => ⟨0,by decide⟩
invFun := fun _ => Fin.elim0
left_inv := by intro j; funext i; exact i.elim0
right_inv := by intro i; apply Fin.ext; have h := i.isLt; simp at h; omega }
| n+1 => (splitLabel n).trans (((Equiv.refl (Fin 4)).prodCongr (labelIndex n)).trans
(finProdFinEquiv.trans (finCongr (by rw [pow_succ,mul_comm]))))
end VWZClique.IntegerRAM.Butterfly
end
/- NativeProjectionSupportDP -/
section
namespace VWZClique.IntegerRAM.Projected.SupportDP
open Structured Projection UniformFolds TraceDyadic SquareCode
/-- Prefixing a basis digit and a first-vertex bit determines the corresponding
partner prefix and the one-bit factor in the sign. -/
def localPartner (d : Fin 4) (b : Bool) := if d=0 then false else if d=1 then true else !b
def coeff (d : Fin 4) (b : Bool) : ℤ := (oneBit d b (localPartner d b)).num
def bit (b : Bool) : ℕ := if b then 1 else 0
def sign {L : ℕ} (j : BasisLabel L) (x : Bits L) := basisInt j (x,partner j x)
def index {L : ℕ} (j : BasisLabel L) (x : Bits L) : ℤ := (wordIndex L (Slices.lookupPartner j x)).val
abbrev inSign : ℤ := -80
abbrev inIndex : ℤ := -81
abbrev outSign : ℤ := -82
abbrev outIndex : ℤ := -83
def n := Expr.reg (-3)
def vertex := Expr.reg (-4)
def label := Expr.add (.mul (.reg (-5)) n) (.reg (-6))
def plane := Expr.mul n n
def src (base : ℤ) := Expr.add (.reg base) (.add (.mul vertex plane) label)
def dst (d : Fin 4) (b : Bool) (base : ℤ) := Expr.add (.reg base) <|
.add (.mul (.add (.mul (.num (bit b)) n) vertex) (.mul (.num 4) plane))
(.add (.mul (.num d.val) plane) label)
def signValue (d : Fin 4) (b : Bool) := Expr.mul (.int (coeff d b)) (.read (src inSign))
def indexValue (d : Fin 4) (b : Bool) := Expr.mul (.mul (signValue d b) (signValue d b))
(.add (.mul (.num (bit (localPartner d b))) n) (.read (src inIndex)))
def cell (d : Fin 4) (b wantIndex : Bool) := write Layout.floor
(dst d b (if wantIndex then outIndex else outSign)) (if wantIndex then indexValue d b else signValue d b)
def cellCost (d : Fin 4) (b wantIndex : Bool) :=
(dst d b (if wantIndex then outIndex else outSign)).steps+((if wantIndex then indexValue d b else signValue d b).steps+1)
end VWZClique.IntegerRAM.Projected.SupportDP
end
/- NativeProjectionSupportStage -/
section
namespace VWZClique.IntegerRAM.Projected.SupportDP
open Structured SquareCode.Layout
abbrev Tag := Fin 4 × Bool × Bool
def tags : List Tag := (List.finRange 4).flatMap fun d => [ (d,false,false),(d,false,true),(d,true,false),(d,true,true) ]
def commands : List Tag → Command
| [] => .skip
| k::ks => .seq (grid (cell k.1 k.2.1 k.2.2)) (commands ks)
end VWZClique.IntegerRAM.Projected.SupportDP
end
/- NativeProjectionSupportFull -/
section
namespace VWZClique.IntegerRAM.Projected.SupportDP
open Structured Projection UniformFolds TraceDyadic SquareCode.Layout Workspace
structure BanksAt (h sig pr : ℕ) (m : Memory) : Prop where
signs : ∀ (j : BasisLabel h) (x : Bits h),
m (sig+(wordIndex h x).val*4^h+(Butterfly.labelIndex h j).val:ℕ)=sign j x
partners : ∀ (j : BasisLabel h) (x : Bits h),
m (pr+(wordIndex h x).val*4^h+(Butterfly.labelIndex h j).val:ℕ)=index j x
/-- One level has a uniform integer cubic cost. The tag-specific costs only
depend on the finite instruction list in each compiled cell. -/
def constant := (tags.map fun k => cellCost k.1 k.2.1 k.2.2+23).sum
end VWZClique.IntegerRAM.Projected.SupportDP
end
/- NativeProjectionSupportLoop -/
section
namespace VWZClique.IntegerRAM.Projected.SupportDP
open UniformFolds Structured SquareCode.Layout Workspace Butterfly Graph
abbrev outerI : ℤ := -90
abbrev total : ℤ := -91
abbrev unit : ℤ := -92
abbrev guardReg : ℤ := -93
abbrev temp : ℤ := -94
abbrev zeroR : ℤ := -95
def initBlock : List Atom := [.one unit,.sub zeroR unit unit,.sub outerI unit unit,.mul total 320 unit,
.one (-2),.one (-3),.add inIndex inSign unit,.add outSign inIndex unit,
.add temp unit unit,.add temp temp temp,.add temp temp temp,.add outIndex outSign temp,
.store inSign unit,.store inIndex zeroR,.sub guardReg total unit]
def bumpBlock : List Atom := [.sub temp outIndex outSign,.mul inSign outSign unit,.mul inIndex outIndex unit,
.add outSign outIndex temp,.add temp temp temp,.add temp temp temp,.add temp temp temp,.add outIndex outSign temp,
.add (-3) (-3) (-3),.mul (-2) (-3) unit]
def body := Command.seq (commands tags) (line bumpBlock)
def execute := Command.seq (line initBlock) (.whenNonnegative guardReg (repeatN body outerI unit total guardReg))
end VWZClique.IntegerRAM.Projected.SupportDP
end
/- NativeProjectionSupportHeaders -/
section
namespace VWZClique.IntegerRAM.Projected.SupportDP
open Structured Butterfly Graph Workspace
abbrev startHeader : ℤ := 379
abbrev signHeader : ℤ := 351
abbrev pairHeader : ℤ := 352
def readSupport : List Atom := [.one unit,.mul inSign startHeader unit]
def writeSupport : List Atom := [.one unit,.mul signHeader inSign unit,.mul pairHeader inIndex unit]
def withHeaders := Command.seq (line readSupport) (.seq execute (line writeSupport))
end VWZClique.IntegerRAM.Projected.SupportDP
end
/- NativeSquareDepth -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured BlockMM
def nReg : ℤ := -34
def scaleReg : ℤ := -15
def paddingTest : ℤ := -14
def scaleMultiply (c : ℤ) := Expr.mul (.reg scaleReg) (.int c)
def padComparison := Expr.sub side (.add (.reg nReg) .one)
def padIter (b : ℕ) (c : ℤ) := Command.seq (assign (-3) (times side (num b)))
(.seq (assign scaleReg (scaleMultiply c)) (assign paddingTest padComparison))
def padCommand (b : ℕ) (c : ℤ) := Command.seq (.atom (.one (-3)))
(.seq (.atom (.one scaleReg)) (.repeatWhileNegative (padIter b c) paddingTest))
def padSteps (b : ℕ) (c : ℤ) := ((times side (num b)).steps+2) +
(((scaleMultiply c).steps+2)+((padComparison.steps+2)) )+1
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeProjectionSmallScale -/
section
namespace VWZClique.IntegerRAM.Projected.SmallScale
open Structured Butterfly Graph BlockMM SquareCode.Layout
abbrev header : ℤ := 367
abbrev one : ℤ := -92
def loadN := [Atom.one one,.mul nReg 0 one]
def writeScale := [Atom.one one,.mul header SquareCode.Layout.scaleReg one]
def calculate (b c : ℕ) := Command.seq (line loadN) (.seq (padCommand b c) (line writeScale))
end VWZClique.IntegerRAM.Projected.SmallScale
end
/- NativeProjectionBatchStep -/
section
namespace VWZClique.IntegerRAM.Projected.Batch
open Structured FoldBits
abbrev labels : ℤ := 358
abbrev labelCount : ℤ := 359
abbrev clock : ℤ := 360
abbrev rowReg : ℤ := 361
abbrev colReg : ℤ := 362
abbrev unit : ℤ := 363
abbrev limit : ℤ := 364
abbrev test : ℤ := 365
abbrev slab : ℤ := 366
abbrev carryTest : ℤ := -187
def headers : List Atom := [.add carryTest labels slab,.load 353 carryTest,.mul 354 rowReg unit,
.mul 355 colReg unit,.mul 357 slab unit]
def plusCol : List Atom := [.add colReg colReg unit,.sub carryTest colReg 0]
def wrapCol : List Atom := [.sub colReg unit unit,.add rowReg rowReg unit,.sub carryTest rowReg 0]
def wrapRow : List Atom := [.sub rowReg unit unit,.add slab slab unit]
def carry := Command.seq (code plusCol) (.whenNonnegative carryTest
(.seq (code wrapCol) (.whenNonnegative carryTest (code wrapRow))))
end VWZClique.IntegerRAM.Projected.Batch
end
/- NativeProjectionPrepare -/
section
namespace VWZClique.IntegerRAM.Projected.Preparation
open Structured UniformFolds NativeFrame NativeTraversal NativeArena BlockMM
def command (d K b c : ℕ) := Command.seq (MaskScan.Arena.buildMaskMetadata K (reg d .weights))
(.seq (Init.command d) (.seq SupportDP.withHeaders (SmallScale.calculate b c)))
def headerTime (d : ℕ) := Headers.time (Init.fields d)+(Init.countExpr.steps+2)
def ticks (d K b c L : ℕ) := (1200+30*K)*(2^L)^5+headerTime d+
(SupportDP.constant+35)*(2^L)^5+(6+(L+1)*SquareCode.Layout.padSteps b c)
structure Ready (L K base count b c : ℕ) (w : WeightKey (2^L)→ℚ) (m : Memory) : Prop where
metadata : MaskScan.Arena.Prepared L K base m
params : Init.Params base (2^L) count m
weights : ∀ i, (m (base+Graph.Table.wordIndex i:ℕ):ℚ)=w i
domain : m 0=((2^L:ℕ):ℤ)
length : m 320=L
banks : SupportDP.BanksAt L (Workspace.level (MaskScan.Arena.slot base (2^L) 7+2) L)
(Workspace.level (MaskScan.Arena.slot base (2^L) 7+2) L+8^L) m
signBase : m 351=Workspace.level (MaskScan.Arena.slot base (2^L) 7+2) L
partnerBase : m 352=((Workspace.level (MaskScan.Arena.slot base (2^L) 7+2) L+8^L:ℕ):ℤ)
scale : m 367=((c^depth b (2^L):ℕ):ℤ)
end VWZClique.IntegerRAM.Projected.Preparation
end
/- NativeSquareGuarded -/
section
namespace VWZClique.IntegerRAM.SquareCode
open Structured
/-- False guards produce a zero entry without evaluating the guarded indirect load. -/
def gatedWrite (d : ℤ) (dst g k value : Expr) : Command :=
.seq (dst.code d) (.seq (g.code (d-1)) (.seq (k.code (d-2))
(.seq (.atom (.sub (d-3) (d-3) (d-3)))
(.seq (.whenNonnegative (d-1) (.whenNonnegative (d-2) (value.code (d-3)))) (.atom (.store d (d-3)))))))
def gatedSteps (dst g k value : Expr) := dst.steps+g.steps+k.steps+value.steps+4
end VWZClique.IntegerRAM.SquareCode
end
/- NativeProjectionRaster -/
section
namespace VWZClique.IntegerRAM.Projected.Raster
open Structured
abbrev row : ℤ := -5
abbrev col : ℤ := -6
abbrev unit : ℤ := -7
abbrev lim : ℤ := -3
abbrev rowFlag : ℤ := -8
abbrev colFlag : ℤ := -9
abbrev floor : ℤ := -128
def scanRow (body : Command) := Command.seq (.atom (.sub col col col)) (repeatN body col unit lim colFlag)
def run (body : Command) := Command.seq (.atom (.one unit)) <| .seq (.atom (.sub row row row)) <|
repeatN (scanRow body) row unit lim rowFlag
end VWZClique.IntegerRAM.Projected.Raster
end
/- NativeSquareProjectPacking -/
section
namespace VWZClique.IntegerRAM.Projected.Packing
open Structured SquareCode
inductive Role where | weight | middle | right
abbrev src : ℤ := -51
abbrev short : ℤ := -52
abbrev count : ℤ := -53
abbrev packet : ℤ := -54
abbrev dst : ℤ := -55
def rowCheck : Role → Bool | .right => false | _ => true
def colCheck : Role → Bool | .middle => false | _ => true
def check (active : Bool) (reg : ℤ) : Expr := if active then .sub (.sub (.reg short) .one) (.reg reg) else .zero
def target := Expr.add (.reg dst) (.add (.mul (.reg Raster.row) (.reg Raster.lim)) (.reg Raster.col))
def source (which : Role) : Expr :=
let a := Expr.reg short
let s := Expr.reg Raster.lim
let r := Expr.reg Raster.row
let c := Expr.reg Raster.col
let start := Expr.mul (.reg packet) s
let idx := match which with
| .weight => Expr.add (.mul c a) r
| .middle => Expr.add (.mul r (.mul (.reg count) s)) (.add start c)
| .right => Expr.add (.mul (.add start r) a) c
.add (.reg src) idx
def writeCell (which : Role) :=
gatedWrite Raster.floor target (check (rowCheck which) Raster.row) (check (colCheck which) Raster.col) (.read (source which))
def cellCost (which : Role) :=
gatedSteps target (check (rowCheck which) Raster.row) (check (colCheck which) Raster.col) (.read (source which))
def pack (which : Role) := Raster.run (writeCell which)
end VWZClique.IntegerRAM.Projected.Packing
end
/- WordDot -/
section
namespace VWZClique.IntegerRAM.WordDot
open Structured
namespace Reg
abbrev leftPtr : ℤ := -1
abbrev rightPtr : ℤ := -2
abbrev x : ℤ := -3
abbrev y : ℤ := -4
abbrev acc : ℤ := -5
abbrev one : ℤ := -6
abbrev count : ℤ := -7
abbrev guard : ℤ := -8
abbrev leftStride : ℤ := -9
abbrev rightStride : ℤ := -10
abbrev length : ℤ := -11
end Reg
def init : Command :=
.seq (.atom (.one Reg.one))
(.seq (.atom (.sub Reg.acc Reg.one Reg.one))
(.seq (.atom (.sub Reg.count Reg.acc Reg.length))
(.atom (.sub Reg.guard Reg.length Reg.one))))
def body : Command :=
.seq (.atom (.load Reg.x Reg.leftPtr))
(.seq (.atom (.load Reg.y Reg.rightPtr))
(.seq (.atom (.mul Reg.x Reg.x Reg.y))
(.seq (.atom (.add Reg.acc Reg.acc Reg.x))
(.seq (.atom (.add Reg.leftPtr Reg.leftPtr Reg.leftStride))
(.seq (.atom (.add Reg.rightPtr Reg.rightPtr Reg.rightStride))
(.atom (.add Reg.count Reg.count Reg.one)))))))
def loop : Command := .repeatWhileNegative body Reg.count
def command : Command := .seq init (.whenNonnegative Reg.guard loop)
end VWZClique.IntegerRAM.WordDot
end
/- NativeProjectionLoop -/
section
namespace VWZClique.IntegerRAM.Projected
open Structured WordDot
namespace Cell
abbrev lhs : ℤ := -30
abbrev rhs : ℤ := -31
abbrev prod : ℤ := -32
abbrev wt : ℤ := -33
abbrev side : ℤ := -34
abbrev area : ℤ := -35
abbrev zero : ℤ := -36
abbrev idx : ℤ := -40
abbrev one : ℤ := -41
abbrev lim : ℤ := -42
abbrev flag : ℤ := -43
abbrev acc : ℤ := -44
end Cell
structure Layout where
lhs : ℕ
rhs : ℕ
prod : ℕ
wt : ℕ
preserve : ℕ := 0
def flat {s : ℕ} (a : Tile s) (i : Fin (s*s)) : ℤ :=
let p := finProdFinEquiv.symm i
a p.1 p.2
def bank (m : Memory) {s : ℕ} (b : ℕ) (a : Tile s) : Prop :=
∀ i : Fin (s*s), m ((b+i.val:ℕ):ℤ) = flat a i
structure Tables (m : Memory) {s t : ℕ} (l : Layout) (a : Tile s) (b c : Fin t → Tile s) : Prop where
weights : bank m l.wt a
left : ∀ p, bank m (l.lhs+p.val*(s*s)) (b p)
right : ∀ p, bank m (l.rhs+p.val*(s*s)) (c p)
/-- One row-major square multiplication on three runtime pointers. Its scratch
area may be reused in all packets. Only input banks and control cells survive. -/
def SquareRun (W K : ℕ) (μ : ℤ) (square : Command) {s t : ℕ} (l : Layout) (a : Tile s)
(b c : Fin t → Tile s) : Prop :=
∀ (p : Fin t) (m : Memory), Tables m l a b c →
m Cell.lhs = (l.lhs+p.val*(s*s):ℕ) → m Cell.rhs = (l.rhs+p.val*(s*s):ℕ) →
m Cell.prod = l.prod → m Cell.side = s →
∃ f, f ≤ K ∧ ∃ out, Runs W square m f out ∧
bank out l.prod (fun i j => μ*(b p * c p) i j) ∧ Tables out l a b c ∧
(∀ z : ℤ, -44 ≤ z → z≤ -30 → out z=m z) ∧
(∀ z : ℕ, z<l.preserve → out z=m z)
def copy (dst src : ℤ) : Command := .atom (.add dst src Cell.zero)
def setupDot : Command :=
.seq (copy Reg.leftPtr Cell.wt)
(.seq (copy Reg.rightPtr Cell.prod)
(.seq (.atom (.one Reg.leftStride))
(.seq (.atom (.one Reg.rightStride)) (copy Reg.length Cell.area))))
def advance : Command :=
.seq (.atom (.add Cell.acc Cell.acc Reg.acc))
(.seq (.atom (.add Cell.lhs Cell.lhs Cell.area)) (.atom (.add Cell.rhs Cell.rhs Cell.area)))
def onePacket (square : Command) : Command :=
.seq square (.seq setupDot (.seq WordDot.command advance))
def packetLoop (square : Command) : Command :=
repeatN (onePacket square) Cell.idx Cell.one Cell.lim Cell.flag
end VWZClique.IntegerRAM.Projected
end
/- NativeSquarePackMany -/
section
namespace VWZClique.IntegerRAM.Projected.Packing
open Structured
abbrev areaReg : ℤ := -56
abbrev packOne : ℤ := -57
abbrev packFlag : ℤ := -58
def onePacket (role : Role) := Command.seq (pack role) (.atom (.add dst dst areaReg))
def packMany (role : Role) := Command.seq (.atom (.mul areaReg Raster.lim Raster.lim))
(.seq (.atom (.one packOne)) (.seq (.atom (.sub packet packet packet))
(repeatN (onePacket role) packet packOne count packFlag)))
end VWZClique.IntegerRAM.Projected.Packing
end
/- MMWordLayout -/
section
namespace VWZClique.BlockMM.WordLayout
/-- One level contains three contiguous banks, each storing N row-major square matrices. -/
def plane (b h N : ℕ) := N*(b^h*b^h)
def size (b h N : ℕ) := 3*plane b h N
/-- Number of cells in all breadth-first layers. -/
def space (b r : ℕ) : (h N : ℕ) → ℕ
| 0,N => size b 0 N
| h+1,N => size b (h+1) N + space b r h (N*r)
end VWZClique.BlockMM.WordLayout
end
/- NativeSquareCell -/
section
namespace VWZClique.IntegerRAM.SquareCode
open Structured
open VWZClique.BlockMM
namespace Layout
open VWZClique.BlockMM.WordLayout
/-- Address in bank-major, node-major, row-major order. -/
def atWord (start count len bank p i j : Expr) : Expr :=
plus start (plus (times (plus (times (plus (times bank count) p) len) i) len) j)
def parentSide (b : ℕ) := times (num b) side
def next (b : ℕ) := plus base (times (times (times (num 3) nodes) (parentSide b)) (parentSide b))
def parentCell {b : ℕ} (k : Fin 3) (a d : Fin b) : Expr :=
atWord base nodes (parentSide b) (num k) node (plus (times (num a) side) row)
(plus (times (num d) side) col)
def childCell (b r : ℕ) (k : Fin 3) (s : Fin r) : Expr :=
atWord (next b) (times nodes (num r)) side (num k) (plus (times node (num r)) (num s)) row col
def sumFin : (n : ℕ) → (Fin n → Expr) → Expr
| 0,_ => .zero
| n+1,f => .add (f 0) (sumFin n (fun i => f i.succ))
def downVal {b : ℕ} (k : Fin 3) (w : Square (Fin b)) :=
sumFin b fun a => sumFin b fun d => times (.int (w a d)) (.read (parentCell k a d))
def upVal {b r : ℕ} (S : Scheme b r) (a d : Fin b) :=
sumFin r fun s => times (.int (S.out a d s)) (.read (childCell b r 2 s))
/-- The code for one transformed child input is a fixed instruction sequence
depending only on scheme coefficients and the bank and rank slot. -/
def downCode {b r : ℕ} (k : Fin 3) (s : Fin r) (w : Square (Fin b)) :=
write floor (childCell b r k s) (downVal k w)
def upCode {b r : ℕ} (S : Scheme b r) (a d : Fin b) :=
write floor (parentCell 2 a d) (upVal S a d)
end Layout
end VWZClique.IntegerRAM.SquareCode
end
/- NativeSquareLeaf -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured
def levelAddr (k : ℕ) := plus base (plus (times (num k) nodes) node)
def levelProd := times (.read (levelAddr 0)) (.read (levelAddr 1))
def leafBody := write floor (levelAddr 2) levelProd
def leafBodySteps := (levelAddr 2).steps+(levelProd.steps+1)
/-- All scalar products on one bottom layer, measured from arbitrary input memory. -/
def leafLayer := Command.seq (.atom (.one (-7))) <| .seq (.atom (.sub (-4) (-4) (-4)))
(repeatN leafBody (-4) (-7) (-2) (-8))
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareCatalog -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured BlockMM BlockMM.WordLayout
def codes {I : Type*} (cmd : I → Command) : List I → Command
| [] => .skip
| j::js => .seq (cmd j) (codes cmd js)
noncomputable def all (I : Type*) [Fintype I] : List I := Finset.univ.toList
def weightDown {b r : ℕ} (S : Scheme b r) (j : Fin 3 × Fin r) : Square (Fin b) :=
if j.1=0 then S.left j.2 else if j.1=1 then S.right j.2 else 0
def downBatchCode {b r : ℕ} (S : Scheme b r) (j : Fin 3 × Fin r) :=
grid (downCode j.1 j.2 (weightDown S j))
noncomputable def downLevel {b r : ℕ} (S : Scheme b r) := codes (downBatchCode S) (all (Fin 3 × Fin r))
def downBatchCost {b r : ℕ} (S : Scheme b r) (j : Fin 3 × Fin r) :=
(childCell b r j.1 j.2).steps+((downVal j.1 (weightDown S j)).steps+1)
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareAscent -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured BlockMM BlockMM.WordLayout
def upBatchCode {b r : ℕ} (S : Scheme b r) (j : Fin b × Fin b) := grid (upCode S j.1 j.2)
def upBatchCost {b r : ℕ} (S : Scheme b r) (j : Fin b × Fin b) :=
(parentCell 2 j.1 j.2).steps+((upVal S j.1 j.2).steps+1)
noncomputable def upLevel {b r : ℕ} (S : Scheme b r) := codes (upBatchCode S) (all (Fin b × Fin b))
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareAdvance -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured BlockMM BlockMM.WordLayout
def rootReg : ℤ := -9
def downAdj (b r : ℕ) := Command.seq (assign (-1) (next b)) (assign (-2) (times nodes (num r)))
def back (b : ℕ) := Expr.sub base (times (times (times (num 3) nodes) (parentSide b)) (parentSide b))
def grow (b : ℕ) := assign (-3) (parentSide b)
noncomputable def downOnce {b r : ℕ} (S : Scheme b r) :=
Command.seq (quotientCmd b (-3)) (.seq (downLevel S) (downAdj b r))
noncomputable def upOnce {b r : ℕ} (S : Scheme b r) :=
Command.seq (quotientCmd r (-2)) (.seq (assign (-1) (back b)) (.seq (upLevel S) (grow b)))
def downAdjTime (b r : ℕ) := ((next b).steps+2)+((times nodes (num r)).steps+2)
def quotTime (d q : ℕ) := (Expr.num d).steps+2+(1+(1+(5*q+4)))
noncomputable def downTime {b r : ℕ} (S : Scheme b r) (h N : ℕ) := quotTime b (b^h) +
(((all (Fin 3 × Fin r)).map (fun j => gridCost N (b^h) (downBatchCost S j))).sum+downAdjTime b r)
noncomputable def upTime {b r : ℕ} (S : Scheme b r) (h N : ℕ) := quotTime r N + ((back b).steps+2+
(((all (Fin b × Fin b)).map (fun j => gridCost N (b^h) (upBatchCost S j))).sum+((parentSide b).steps+2)))
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareFlight -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured BlockMM BlockMM.WordLayout
def flag : ℤ := -14
def downTest := Expr.sub .one side
def upTest := Expr.sub side (.reg rootReg)
noncomputable def downStep {b r : ℕ} (S : Scheme b r) := Command.seq (downOnce S) (assign flag downTest)
noncomputable def upStep {b r : ℕ} (S : Scheme b r) := Command.seq (upOnce S) (assign flag upTest)
noncomputable def charge {b r : ℕ} (S : Scheme b r) : (h N : ℕ) → ℕ
| 0,N => 2+N*(leafBodySteps+3)
| h+1,N => downTime S h N + (downTest.steps+3) + charge S h (N*r) + upTime S h N + (upTest.steps+3)
def Room (W M : ℕ) := ∀ x : ℤ, -(M:ℤ) ≤ x → x ≤ M → Fits W x
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareRate -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured BlockMM BlockMM.WordLayout OAI.MatrixMultiplication.Arithmetic
noncomputable def core {b r : ℕ} (S : Scheme b r) := Command.seq (assign rootReg side)
(.seq (.repeatWhileNegative (downStep S) flag) (.seq leafLayer (.repeatWhileNegative (upStep S) flag)))
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareSetup -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured
abbrev Setup := List (ℤ × Expr)
def setupCode : Setup → Command
| [] => .skip
| (i,e)::xs => .seq (assign i e) (setupCode xs)
def setupCost : Setup → ℕ
| [] => 0
| (_,e)::xs => (e.steps+2)+setupCost xs
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeProjectPackBanks -/
section
namespace VWZClique.IntegerRAM.Projected.Large
open Structured SquareCode SquareCode.Layout Packing
structure Banks where
A : ℕ
B : ℕ
C : ℕ
temp : ℕ
w : ℕ
left : ℕ
right : ℕ
output : ℕ
def Banks.bound (l : Banks) (s a b : ℕ) :=
l.A+a*a ≤ l.w ∧ l.B+a*(b*s) ≤ l.w ∧ l.C+(b*s)*a ≤ l.w ∧
l.w+s*s ≤ l.left ∧ l.left+b*(s*s) ≤ l.right ∧ l.right+b*(s*s) ≤ l.output
structure Pointers (m : Memory) (l : Banks) : Prop where
A : m 371=l.A
B : m 372=l.B
C : m 373=l.C
temp : m 374=l.temp
w : m 375=l.w
left : m 376=l.left
right : m 377=l.right
output : m 378=l.output
def select (ins outs : ℕ) : Setup := [(src,.reg ins),(dst,.reg outs),(packet,.zero)]
def packBank (role : Role) (ins outs : ℕ) := Command.seq (setupCode (select ins outs)) (packMany role)
def packOneW := Command.seq (setupCode (select 371 375)) (pack .weight)
def planeCost (role : Role) (s : ℕ) := 2+s*(1+s*(cellCost role+3)+3)
def bankCost (role : Role) (ins outs b s : ℕ) := setupCost (select ins outs)+(3+b*(planeCost role s+4))
end VWZClique.IntegerRAM.Projected.Large
end
/- NativeProjectPacked -/
section
namespace VWZClique.IntegerRAM.Projected.Large
open Structured Packing
structure Sources {a b s : ℕ} (m : Memory) (l : Banks) (A : Tile a)
(B : Matrix (Fin a) (Fin b × Fin s) ℤ) (C : Matrix (Fin b × Fin s) (Fin a) ℤ) : Prop where
weight : ∀ i j : Fin a, m (l.A+(i.val*a+j.val):ℕ)=A i j
middle : ∀ i : Fin a, ∀ p : Fin b, ∀ c : Fin s, m (l.B+(i.val*(b*s)+(p.val*s+c.val)):ℕ)=B i (p,c)
right : ∀ p : Fin b, ∀ r : Fin s, ∀ i : Fin a, m (l.C+((p.val*s+r.val)*a+i.val):ℕ)=C (p,r) i
def allPacks := Command.seq packOneW (.seq (packBank .middle 372 376) (packBank .right 373 377))
def allCost (s b : ℕ) := (SquareCode.Layout.setupCost (select 371 375)+planeCost .weight s)+
(bankCost .middle 372 376 b s+bankCost .right 373 377 b s)
end VWZClique.IntegerRAM.Projected.Large
end
/- NativeProjectPacketInit -/
section
namespace VWZClique.IntegerRAM.Projected.Large
open Structured SquareCode SquareCode.Layout BlockMM
def setSide : SquareCode.Layout.Setup := [(nReg,.reg Raster.lim)]
def scaleSetup (b : ℕ) (c : ℤ) := Command.seq (setupCode setSide) (.seq (padCommand b c) (.atom (.store 374 scaleReg)))
def controls : SquareCode.Layout.Setup :=
[(Cell.lhs,.reg 376),(Cell.rhs,.reg 377),(Cell.prod,.reg 378),(Cell.wt,.reg 375),
(Cell.area,.mul (.reg Cell.side) (.reg Cell.side)),(Cell.zero,.zero),(Cell.idx,.zero),(Cell.one,.one),
(Cell.lim,.reg Packing.count),(Cell.acc,.zero)]
end VWZClique.IntegerRAM.Projected.Large
end
/- NativeProjectPower -/
section
namespace VWZClique.IntegerRAM.Projected.Power
open Structured
abbrev pos : ℤ := -63
abbrev one : ℤ := -64
abbrev flag : ℤ := -65
abbrev test : ℤ := -66
def code (base exponent : ℤ) := Command.seq (.atom (.one base)) (.seq (.atom (.one one))
(.seq (.atom (.sub pos pos pos)) (.seq (.atom (.sub test exponent one))
(.whenNonnegative test (repeatN (.atom (.add base base base)) pos one exponent flag)))))
end VWZClique.IntegerRAM.Projected.Power
end
/- NativeProjectShape -/
section
namespace VWZClique.IntegerRAM.Projected.Shape
open Structured SquareCode SquareCode.Layout UniformFolds Double
abbrev short : ℤ := -52
abbrev count : ℤ := -53
abbrev side : ℤ := -3
abbrev eCount : ℤ := -61
abbrev eSide : ℤ := -62
abbrev gap : ℤ := -67
def long := Expr.mul (.reg 0) (.mul (.reg 0) (.reg 0))
def header : Setup := [(WindowInit.Lreg,.reg 320),(short,.mul (.reg 359) (.reg 0))]
def exponents : Setup := [(eCount,.reg SignedDivision.result),(eSide,.sub (.mul (.num 3) (.reg 320)) (.reg eCount))]
def chooseGap : Setup := [(gap,.sub (.sub (.reg short) (.reg side)) .one)]
def fallback : Setup := [(count,.one),(side,long)]
def quotient (q : ℕ) : Command := if q=0 then .atom (.sub SignedDivision.result SignedDivision.result SignedDivision.result)
else WindowInit.ratio 1 q
def code (q : ℕ) := Command.seq (setupCode header) (.seq (quotient q) (.seq (setupCode exponents)
(.seq (Power.code count eCount) (.seq (Power.code side eSide)
(.seq (setupCode chooseGap) (.whenNonnegative gap (setupCode fallback)))))))
def amount (q L : ℕ) := setupCost header+(13*(L+1)+q+17)+(setupCost exponents)+(5+4*L)+(5+4*(3*L))+
setupCost chooseGap+1+setupCost fallback
end VWZClique.IntegerRAM.Projected.Shape
end
/- NativeSquareTransfer -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured
abbrev srcPointer : ℤ := -17
abbrev srcStride : ℤ := -18
abbrev dstPointer : ℤ := -19
abbrev dstStride : ℤ := -20
def tileAddr (ptr stride : ℤ) := plus (.reg ptr) (plus (times (.reg stride) row) col)
def tileLoad (copy : Bool) : Expr := if copy then .read (tileAddr srcPointer srcStride) else .zero
def tileStore (copy : Bool) := write floor (tileAddr dstPointer dstStride) (tileLoad copy)
def tilePass (copy : Bool) := grid (tileStore copy)
def tileSteps (copy : Bool) := (tileAddr dstPointer dstStride).steps+((tileLoad copy).steps+1)
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareJob -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured
abbrev rawSide : ℤ := -34
abbrev padSide : ℤ := -16
abbrev workPtr : ℤ := -21
abbrev lhsPtr : ℤ := -30
abbrev rhsPtr : ℤ := -31
abbrev resultPtr : ℤ := -32
structure Anchors where
raw : ℕ
pad : ℕ
work : ℕ
lhs : ℕ
rhs : ℕ
result : ℕ
inductive Width where | raw | padded
inductive Origin where | left | right | result | bank (k : ℕ)
def Width.expr : Width → Expr | .raw => .reg rawSide | .padded => .reg padSide
def Width.val (a : Anchors) : Width → ℕ | .raw => a.raw | .padded => a.pad
def Origin.expr : Origin → Expr
| .left => .reg lhsPtr | .right => .reg rhsPtr | .result => .reg resultPtr
| .bank k => plus (.reg workPtr) (times (num k) (times (.reg padSide) (.reg padSide)))
structure Job where
copy : Bool
dim : Width
src : Origin
srcStep : Width
dst : Origin
dstStep : Width
def Job.setup (q : Job) : Setup :=
[(-2,.one),(-3,q.dim.expr),(srcPointer,q.src.expr),(srcStride,q.srcStep.expr),
(dstPointer,q.dst.expr),(dstStride,q.dstStep.expr)]
def Job.cmd (q : Job) := Command.seq (setupCode q.setup) (tilePass q.copy)
def Job.cost (a : Anchors) (q : Job) := setupCost q.setup+gridCost 1 (q.dim.val a) (tileSteps q.copy)
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareBoundary -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured BlockMM BlockMM.WordLayout
def fillBank (k : ℕ) : Job := ⟨false,.padded,.left,.raw,.bank k,.padded⟩
def copyInto (src : Origin) (k : ℕ) : Job := ⟨true,.raw,src,.raw,.bank k,.padded⟩
def ingest (src : Origin) (k : ℕ) := Command.seq (fillBank k).cmd (copyInto src k).cmd
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareBootstrap -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured BlockMM BlockMM.WordLayout
def chooseArea : Setup :=
[(padSide,.reg (-3)),(workPtr,plus (.reg resultPtr) (times (.reg rawSide) (.reg rawSide)))]
def startSquare (b : ℕ) (c : ℤ) := Command.seq (padCommand b c) (setupCode chooseArea)
def pointCore : Setup := [(-1,.reg workPtr),(-2,.one),(-3,.reg padSide)]
def emitJob : Job := ⟨true,.raw,.bank 2,.padded,.result,.raw⟩
noncomputable def multiply {b r : ℕ} (S : Scheme b r) :=
Command.seq (startSquare b S.scale) (.seq (ingest .left 0) (.seq (ingest .right 1)
(.seq (setupCode pointCore) (.seq (core S) emitJob.cmd))))
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareMultiply -/
section
namespace VWZClique.IntegerRAM.SquareCode.Layout
open Structured BlockMM BlockMM.WordLayout
noncomputable def runtimeCost {b r : ℕ} (S : Scheme b r) (a : Anchors) :=
(2+(depth b a.raw)*padSteps b S.scale + setupCost chooseArea) +
((fillBank 0).cost a+(copyInto .left 0).cost a + ((fillBank 1).cost a+(copyInto .right 1).cost a +
(setupCost pointCore + (4+charge S (depth b a.raw) 1+emitJob.cost a))))
end VWZClique.IntegerRAM.SquareCode.Layout
end
/- NativeSquareProjectionCall -/
section
namespace VWZClique.IntegerRAM.Projected
open Structured BlockMM BlockMM.WordLayout
namespace SquareCaller
open SquareCode.Layout
noncomputable def duration {b r : ℕ} (S : Scheme b r) (s : ℕ) :=
runtimeCost S ⟨s,b^(depth b s),0,0,0,0⟩
end SquareCaller
end VWZClique.IntegerRAM.Projected
end
/- NativeProjection -/
section
namespace VWZClique.IntegerRAM.Projected
open Structured UniformFolds TraceDyadic Double
open Double.IntegerTiling
/-- The retained labels are numbered by increasing addresses in the actual
butterfly output. The free third coordinate then gives the row-major node index. -/
noncomputable def labelNumber {L : ℕ} (S : Finset (BasisLabel L)) : S ≃ Fin S.card :=
let e := (Butterfly.labelIndex L).toEmbedding
(S.equivMap e).trans ((S.map e).orderIsoOfFin (Finset.card_map ..)).toEquiv.symm
noncomputable def nodeNumber {L : ℕ} (S : Finset (BasisLabel L)) :
Node S ≃ Fin (S.card * 2^L) := ((labelNumber S).prodCongr (wordIndex L)).trans finProdFinEquiv
/-- The long dimension consists of three packed vertices. The low tile
coordinate is the remainder in the integer power-of-two blocking schedule. -/
def threeVertices (L : ℕ) : Block L ≃ PairBits L × Bits L where
toFun b := ((b 0,b 1),b 2)
invFun p := block p.1 p.2
left_inv b := by funext i; fin_cases i <;> rfl
right_inv p := by rcases p with ⟨⟨x,y⟩,z⟩; rfl
def longNumber (L : ℕ) : Block L ≃ Fin ((2^L)^3) :=
let pair := ((wordIndex L).prodCongr (wordIndex L)).trans finProdFinEquiv
(threeVertices L).trans ((pair.prodCongr (wordIndex L)).trans
(finProdFinEquiv.trans (finCongr (by ring))))
def blockNumber (L q : ℕ) : Block L ≃ Fin (blocks L q) × Fin (IntegerTiling.side L q) :=
((longNumber L).trans (finCongr (exact_shape L q).symm)).trans finProdFinEquiv.symm
noncomputable def shortWeight {L} (S : Finset (BasisLabel L)) (K : ℕ) (w : ChannelKey L → ℚ) :
Tile (S.card*2^L) :=
fun i j => leftTable S S K K w ((nodeNumber S).symm i) ((nodeNumber S).symm j)
noncomputable def middle {L} (S : Finset (BasisLabel L)) (q : ℕ) (w : ChannelKey L → ℚ) :
Matrix (Fin (S.card*2^L)) (Fin (blocks L q) × Fin (IntegerTiling.side L q)) ℤ :=
fun i j => midTable S w ((nodeNumber S).symm i) ((blockNumber L q).symm j)
noncomputable def right {L} (S : Finset (BasisLabel L)) (q : ℕ) (w : ChannelKey L → ℚ) :
Matrix (Fin (blocks L q) × Fin (IntegerTiling.side L q)) (Fin (S.card*2^L)) ℤ :=
fun i j => rightTable S w ((blockNumber L q).symm i) ((nodeNumber S).symm j)
end VWZClique.IntegerRAM.Projected
end
/- NativeProjectionTileScale -/
section
namespace VWZClique.IntegerRAM.Projected
def scaleMat {I J : Type*} (z : ℤ) (A : Matrix I J ℤ) : Matrix I J ℤ := fun i j => z*A i j
end VWZClique.IntegerRAM.Projected
end
/- NativeProjectLarge -/
section
namespace VWZClique.IntegerRAM.Projected.Large
open Structured SquareCode SquareCode.Layout BlockMM BlockMM.WordLayout UniformFolds TraceDyadic Double IntegerTiling
noncomputable def code {b r : ℕ} (q : ℕ) (S : Scheme b r) :=
Command.seq (Projected.Shape.code q) (.seq allPacks (.seq (scaleSetup b S.scale) (.seq (setupCode controls)
(.seq (packetLoop (multiply S)) (.atom (.load scaleReg 374))))))
noncomputable def cost {b r : ℕ} (q : ℕ) (S : Scheme b r) (L s packets : ℕ) :=
Projected.Shape.amount q L + (allCost s packets + ((setupCost setSide+((2+depth b s*padSteps b S.scale)+1))+
(setupCost controls+(packets*(SquareCaller.duration S s+8*(s*s)+16)+1))))
structure Limits (b r q L labels s packets : ℕ) (l : Banks) (M : ℕ) : Prop where
ratio : 2^(L+1)*q ≤ M
side : (2^L)^3+1 ≤ M
short : labels*2^L ≤ M
clock : 3*L+1 ≤ M
workspace : l.output+s*s+space b r (depth b s) 1 ≤ M
banks : l.bound s (labels*2^L) packets
header : 378<l.temp
temp : l.temp<l.w
end VWZClique.IntegerRAM.Projected.Large
end
/- NativeProjectLargeBounds -/
section
namespace VWZClique.IntegerRAM.Projected.Large
open Structured SquareCode.Layout BlockMM BlockMM.WordLayout UniformFolds TraceDyadic Double IntegerTiling
def workspaceBanks (start n : ℕ) : Banks :=
let l := Workspace.banks start n
⟨l.left,l.middle,l.right,l.transform,l.weights,l.packetsLeft,l.packetsRight,l.output⟩
end VWZClique.IntegerRAM.Projected.Large
end
/- NativeProjectionBatch -/
section
namespace VWZClique.IntegerRAM.Projected.Batch
open Structured FoldBits
def init : List Atom := [.one unit,.sub clock unit unit,.sub slab unit unit,.sub rowReg unit unit,
.sub colReg unit unit,.mul limit labelCount 0,.mul limit limit 0,.sub carryTest limit unit]
def visit (job : Command) := Command.seq (code headers) (.seq job carry)
def grid (job : Command) := Command.seq (code init) (.whenNonnegative carryTest (repeatN (visit job) clock unit limit test))
end VWZClique.IntegerRAM.Projected.Batch
end
/- NativeProjectionScatter -/
section
namespace VWZClique.IntegerRAM.Projected.Scatter
open Structured SquareCode SquareCode.Layout
abbrev src : ℤ := -14
abbrev anchor : ℤ := -15
abbrev rowStride : ℤ := -16
abbrev colStride : ℤ := -17
def destination : Expr := .add (.add (.reg anchor) (.mul row (.reg rowStride))) (.mul col (.reg colStride))
def inputAddress : Expr := .add (.add (.reg src) (.mul row side)) col
def source : Expr := .read inputAddress
def cell := SquareCode.write floor destination source
def run := grid cell
end VWZClique.IntegerRAM.Projected.Scatter
end
/- NativeProjectionScatterLayout -/
section
namespace VWZClique.IntegerRAM.Projected.Scatter
open Structured SquareCode SquareCode.Layout
inductive Channel | left | middle | right deriving DecidableEq
abbrev sourceBase : ℤ := -50
abbrev targetBase : ℤ := -51
abbrev labelID : ℤ := -52
abbrev labels : ℤ := -53
abbrev remoteX : ℤ := -54
abbrev remoteY : ℤ := -55
abbrev pairCode : ℤ := -56
open FoldBits (code)
def initOps := [Atom.one (-2),.mul (-3) 0 (-2),.mul src sourceBase (-2),.mul (-57) 0 0,
.mul (-58) 0 (-57),.mul (-59) labelID 0,.mul (-60) labels 0,
.mul (-61) remoteX 0,.add (-61) (-61) remoteY,.mul (-61) (-61) 0]
def arrange : Channel → List Atom
| .middle => [.mul anchor (-59) (-58),.add anchor anchor targetBase,.add anchor anchor (-61),
.mul rowStride (-58) (-2),.one colStride]
| .right => [.mul anchor (-61) (-60),.add anchor anchor targetBase,.add anchor anchor (-59),
.one rowStride,.mul colStride (-60) (-2)]
| .left => [.mul anchor (-59) 0,.mul anchor anchor (-57),.add anchor anchor targetBase,
.add anchor anchor pairCode,.mul rowStride (-58) (-2),.mul colStride (-57) (-2)]
def prepare (b : Channel) := code (initOps++arrange b)
def command (b : Channel) := Command.seq (prepare b) run
end VWZClique.IntegerRAM.Projected.Scatter
end
/- NativeProjectionLeftGather -/
section
namespace VWZClique.IntegerRAM.Projected.LeftGather
open Structured SquareCode SquareCode.Layout
abbrev codes : ℤ := -20
abbrev coeff : ℤ := -21
abbrev inputBase : ℤ := -22
abbrev dest : ℤ := -23
abbrev stride : ℤ := -24
abbrev rowScalar : ℤ := -25
abbrev limit : ℤ := -3
abbrev index : ℤ := -5
abbrev unit : ℤ := -7
abbrev flag : ℤ := -8
def entry (r : ℤ) := Expr.read (.add (.reg r) (.reg index))
def source := Expr.read (.add (.reg inputBase) (entry codes))
def address := Expr.add (.reg dest) (.mul (.reg index) (.reg stride))
def val := Expr.mul (.mul (.reg rowScalar) (entry coeff)) source
def body := SquareCode.write floor address val
def run := Command.seq (.atom (.one unit)) (.seq (.atom (.sub index index index)) (repeatN body index unit limit flag))
end VWZClique.IntegerRAM.Projected.LeftGather
end
/- NativeProjectionLeftSetup -/
section
namespace VWZClique.IntegerRAM.Projected.LeftSetup
open Structured FoldBits Butterfly
abbrev first : ℤ := -70
abbrev second : ℤ := -71
abbrev current : ℤ := -72
abbrev next : ℤ := -73
abbrev one : ℤ := -74
abbrev save : ℤ := -75
abbrev idx : ℤ := -76
abbrev test : ℤ := -77
abbrev firstOrig : ℤ := -78
abbrev sq : ℤ := -79
def start := [Atom.one one,.mul sq 0 0,.mul firstOrig 357 0,.add firstOrig firstOrig 354,
.mul firstOrig firstOrig 0,.add firstOrig firstOrig 355,.mul firstOrig firstOrig sq,.add firstOrig firstOrig 374,
.mul first firstOrig one,.mul second 356 one,.one next,.sub idx one one]
def step := [Atom.mul save first one,.mul first second one,.mul second save one,.mul current next one,
.add next next next,.add next next next]
def loop := repeatN (FoldBits.code step) idx one 320 test
def kernel := Command.seq (FoldBits.code start) loop
def control := [Atom.mul Reg.srcBase firstOrig one,.mul Reg.dstBase 356 one,.mul Reg.stride current one,.mul Reg.stages 320 one]
def configure := Command.seq kernel (FoldBits.code control)
end VWZClique.IntegerRAM.Projected.LeftSetup
end
/- NativeProjectionLeftJob -/
section
namespace VWZClique.IntegerRAM.Projected.LeftSetup
open Structured FoldBits Butterfly UniformFolds TraceDyadic Double
def prepareGather : List Atom := [.mul LeftGather.limit 359 one,.mul LeftGather.codes 358 one,
.mul LeftGather.coeff 370 one,.mul LeftGather.inputBase first one,.mul LeftGather.stride 0 one,
.mul LeftGather.dest 357 0,.add LeftGather.dest LeftGather.dest 354,.mul save 359 0,
.mul LeftGather.dest LeftGather.dest save,.add LeftGather.dest LeftGather.dest 371,.add LeftGather.dest LeftGather.dest 355,
.add save 370 357,.load LeftGather.rowScalar save]
def job := Command.seq configure (.seq full (.seq kernel (.seq (FoldBits.code prepareGather) LeftGather.run)))
def budget (L a : ℕ) := (16+9*L)+(5+L*(15+20*4^(L-1)))+(12+9*L)+13+
(2+a*(LeftGather.address.steps+(LeftGather.val.steps+1)+3))
end VWZClique.IntegerRAM.Projected.LeftSetup
end
/- NativeProjectionCells -/
section
namespace VWZClique.IntegerRAM.Projected.Slices.Fill
open Structured Projection WeightedProof UniformFolds TraceDyadic SquareCode Factors
abbrev signBase : ℤ := -68
abbrev partnerBase : ℤ := -69
abbrev label : ℤ := -70
abbrev remote0 : ℤ := -71
abbrev remote1 : ℤ := -72
abbrev dest : ℤ := -73
abbrev labelCount : ℤ := -74
def row := Expr.reg (-5)
def col := Expr.reg (-6)
def supportEntry (tab : ℤ) (x : Expr) : Expr :=
.read (.add (.reg tab) (.add (.mul x (.reg labelCount)) (.reg label)))
def idx (g : Group) : Expr := if g=.pivotCenter then col else row
def coords (g : Group) : Source → Expr
| .pivot false => if g=.centerOther then .zero else idx g
| .pivot true => if g=.centerOther then .zero else supportEntry partnerBase (idx g)
| .center => if g=.pivotOther then .zero else row
| .other i => if g=.pivotCenter then .zero else
if i=0 then .reg remote0 else if i=1 then .reg remote1 else col
def arrayPosition := Expr.add (.reg dest) (.add (.mul row (.reg sideReg)) col)
noncomputable def entryValue (π : Equiv.Perm V) (E : Finset EdgeSlot) (rev : Bool)
(h : Fin 3) (g : Group) : Expr :=
let factors := component (coords g) π E rev h g
if g=.pivotCenter then .mul (supportEntry signBase col) factors else factors
noncomputable def cell (π : Equiv.Perm V) (E : Finset EdgeSlot) (rev : Bool)
(h : Fin 3) (g : Group) := write Layout.floor arrayPosition (entryValue π E rev h g)
end VWZClique.IntegerRAM.Projected.Slices.Fill
end
/- NativeProjectionHadamard -/
section
namespace VWZClique.IntegerRAM.Projected.Pointwise
open Structured Butterfly
abbrev src : ℤ := -50
abbrev dst : ℤ := -51
abbrev factor : ℤ := -52
abbrev value : ℤ := -53
abbrev unit : ℤ := -54
abbrev index : ℤ := -55
abbrev limit : ℤ := -56
abbrev guard : ℤ := -57
/-- Scale every entry of a square multiplication result in place, using the
corresponding entry in a separate weight array. -/
def ops : List Atom := [.load factor src,.load value dst,.mul value factor value,.store dst value,
.add src src unit,.add dst dst unit]
def kernel : Command := repeatN (line ops) index unit limit guard
end VWZClique.IntegerRAM.Projected.Pointwise
end
/- NativeProjectionSmall -/
section
namespace VWZClique.IntegerRAM.Projected.Small
open Structured Projection WeightedProof UniformFolds TraceDyadic Slices Slices.Fill SquareCode
/-- The caller prepares these positive scratch words once per slice. -/
abbrev weightsH : ℕ := 350
abbrev signsH : ℕ := 351
abbrev partsH : ℕ := 352
abbrev labelH : ℕ := 353
abbrev f0H : ℕ := 354
abbrev f1H : ℕ := 355
abbrev workH : ℕ := 356
def dim := Headers.Value.word 0
def area := Headers.Value.mul dim dim
def offset (k : ℕ) := Headers.Value.add (.word workH) (.mul (.nat k) area)
def plane : Group → ℕ | .pivotCenter => 0 | .pivotOther => 1 | .centerOther => 2
def sheetFields (g : Group) : Headers.Fields := [(Raster.lim,dim),(Factors.sideReg,dim),
(Factors.baseReg,.word weightsH),(Fill.signBase,.word signsH),(Fill.partnerBase,.word partsH),
(Fill.label,.word labelH),(Fill.remote0,.word f0H),(Fill.remote1,.word f1H),(Fill.dest,offset (plane g)),
(Fill.labelCount,area)]
noncomputable def sheet (π : Equiv.Perm V) (E : Finset EdgeSlot) (rev : Bool) (h : Fin 3) (g : Group) :=
Command.seq (Headers.command (sheetFields g)) (Raster.run (Fill.cell π E rev h g))
def squareFields : Headers.Fields := [(Cell.lhs,offset 0),(Cell.rhs,offset 1),(Cell.prod,offset 3),(Cell.side,dim)]
def pointFields : Headers.Fields := [(Pointwise.src,offset 2),(Pointwise.dst,offset 3),
(Pointwise.unit,.nat 1),(Pointwise.index,.nat 0),(Pointwise.limit,area)]
noncomputable def job (square : Command) (π : Equiv.Perm V) (E : Finset EdgeSlot) (rev : Bool) (h : Fin 3) :=
Command.seq (sheet π E rev h .pivotCenter) <| .seq (sheet π E rev h .pivotOther) <|
.seq (sheet π E rev h .centerOther) <| .seq (Headers.command squareFields) <|
.seq square <| .seq (Headers.command pointFields) Pointwise.kernel
noncomputable def sheetTime (π : Equiv.Perm V) (E : Finset EdgeSlot) (rev : Bool) (h : Fin 3) (g : Group) (n : ℕ) :=
Headers.time (sheetFields g)+ (2+n*(1+n*(Fill.arrayPosition.steps+((Fill.entryValue π E rev h g).steps+1)+3)+3))
noncomputable def jobTime (π : Equiv.Perm V) (E : Finset EdgeSlot) (rev : Bool) (h : Fin 3)
(n squareCost : ℕ) := sheetTime π E rev h .pivotCenter n+(sheetTime π E rev h .pivotOther n+
(sheetTime π E rev h .centerOther n+(Headers.time squareFields+
(squareCost+(Headers.time pointFields+9*(n*n))))))
end VWZClique.IntegerRAM.Projected.Small
end
/- NativeProjectionPairScan -/
section
namespace VWZClique.IntegerRAM.Projected.PairScan
open Structured FoldBits
abbrev x : ℤ := -140
abbrev y : ℤ := -141
abbrev a : ℤ := -142
abbrev b : ℤ := -143
abbrev test : ℤ := -145
abbrev counter : ℤ := -146
abbrev tmp : ℤ := -147
abbrev one : ℤ := -148
abbrev cross : ℤ := -149
abbrev ans : ℤ := -56
abbrev srcX : ℤ := -54
abbrev srcY : ℤ := -55
def extract (v bit : ℤ) := Command.seq (.atom (.add v v v)) <|
.seq (.atom (.sub test v 0)) <| .seq (.atom (.sub bit bit bit)) <|
.whenNonnegative test (.seq (.atom (.sub v v 0)) (.atom (.one bit)))
def finish : List Atom := [.add tmp a b,.add tmp tmp tmp,.add tmp tmp a,
.mul cross a b,.add cross cross cross,.add cross cross cross,.sub tmp tmp cross,
.add ans ans ans,.add ans ans ans,.add ans ans tmp,.add counter counter one]
def body := Command.seq (extract x a) (.seq (extract y b) (code finish))
def loop := Command.repeatWhileNegative body counter
def init := [Atom.one one,.mul x srcX one,.mul y srcY one,.sub ans one one,
.sub counter one one,.sub counter counter 320]
def command := Command.seq (code init) loop
end VWZClique.IntegerRAM.Projected.PairScan
end
/- NativeProjectionScatterValues -/
section
namespace VWZClique.IntegerRAM.Projected.Scatter
open Structured Slices UniformFolds TraceDyadic
def rev : Channel → Bool | .left | .middle => false | .right => true
def index : Channel → Fin 3 | .left => 0 | .middle => 1 | .right => 2
end VWZClique.IntegerRAM.Projected.Scatter
end
/- NativeProjectionScatterHeader -/
section
namespace VWZClique.IntegerRAM.Projected.Scatter
open Structured UniformFolds FoldBits
def bufferReg : Channel → ℤ | .left => 374 | .middle => 372 | .right => 373
def setup (b : Channel) : List Atom := [.one (-62),.mul (-50) 0 0,.add (-63) (-50) (-50),
.add (-50) (-50) (-63),.add (-50) 356 (-50),.mul (-51) (bufferReg b) (-62),.mul (-52) 357 (-62),
.mul (-53) 359 (-62),.mul (-54) 354 (-62),.mul (-55) 355 (-62)]
def fromHeaders (b : Channel) := Command.seq (FoldBits.code (setup b)) (.seq PairScan.command (command b))
end VWZClique.IntegerRAM.Projected.Scatter
end
/- NativeProjectionChannels -/
section
namespace VWZClique.IntegerRAM.Projected.Channels
open Structured Projection UniformFolds WeightedProof TraceDyadic BlockMM Scatter
noncomputable def job {b r} (S : Scheme b r) (π : Equiv.Perm V) (E : Finset EdgeSlot) (ch : Channel) :=
Command.seq (Small.job (SquareCode.Layout.multiply S) π E (rev ch) (index ch)) (fromHeaders ch)
noncomputable def time {b r} (S : Scheme b r) (π : Equiv.Perm V) (E : Finset EdgeSlot) (ch : Channel) (L : ℕ) :=
Small.jobTime π E (rev ch) (index ch) (2^L) (SquareCaller.duration S (2^L))+
(16+24*L+128*(2^L)^2)
end VWZClique.IntegerRAM.Projected.Channels
end
/- NativeProjectionChannelGrid -/
section
namespace VWZClique.IntegerRAM.Projected.Channels
open Structured BlockMM Scatter Projection WeightedProof UniformFolds
noncomputable def program {b r} (S : Scheme b r) (π : Equiv.Perm V) (E : Finset EdgeSlot) (ch : Channel) :=
Batch.grid (job S π E ch)
noncomputable def cost {b r} (S : Scheme b r) (π : Equiv.Perm V) (E : Finset EdgeSlot) (ch : Channel) (L a : ℕ) :=
9+(a*2^L*2^L)*(time S π E ch L+17)
end VWZClique.IntegerRAM.Projected.Channels
end
/- NativeProjectionThree -/
section
namespace VWZClique.IntegerRAM.Projected.Dense
open Structured BlockMM Scatter UniformFolds Projection WeightedProof
abbrev labelSet (K L : ℕ) := (windowExpansion K L).labels
abbrev Bank (base L : ℕ) := Workspace.banks (MaskScan.Arena.slot base (2^L) 7+2) (2^L)
noncomputable def three {b r} (S : Scheme b r) (π : Equiv.Perm V) (E : Finset EdgeSlot) : Command :=
.seq (Channels.program S π E .middle) (.seq (Channels.program S π E .right) (Channels.program S π E .left))
noncomputable def threeCost {b r} (S : Scheme b r) (π : Equiv.Perm V) (E : Finset EdgeSlot) (L a : ℕ) :=
Channels.cost S π E .middle L a+(Channels.cost S π E .right L a+Channels.cost S π E .left L a)
end VWZClique.IntegerRAM.Projected.Dense
end
/- NativeProjectionDense -/
section
namespace VWZClique.IntegerRAM.Projected.Dense
open Structured BlockMM Projection UniformFolds WeightedProof Double
noncomputable def code {b r} (S : Scheme b r) (π : Equiv.Perm V) (E : Finset EdgeSlot) :=
Command.seq (three S π E) (Batch.grid LeftSetup.job)
noncomputable def cost {b r} (S : Scheme b r) (π : Equiv.Perm V) (E : Finset EdgeSlot) (L a : ℕ) :=
threeCost S π E L a+(9+a*2^L*2^L*(LeftSetup.budget L a+17))
end VWZClique.IntegerRAM.Projected.Dense
end
/- NativeLeafPlan -/
section
namespace VWZClique.IntegerRAM.NativeLeaf
open UniformFolds Structured
/-- One leading constant covers all static sparse leaves at every dyadic
length. A returned integer agrees with the recursion's exact integer leaf.
The signed input may occupy any contiguous segment disjoint from scratch. -/
theorem plan_leaf (dst : ℤ) (hdst : dst < -3) :
∃ C : ℕ, ∀ (H : SimpleGraph V) (hh : ¬ HasWedges H),
∃ c : Command, ∀ (L W base M : ℕ) (cap : Graph.Division.Room W M)
(room : base+9*(2^L)+81*(2^L*2^L)≤M)
(w : WeightKey (2^L) → ℤ) (hb : ∀ i, w i=0 ∨ w i=1) (m : Memory),
Ready (inputData (by positivity) cap room w) (Empty.elim : Empty → ℤ)
(Empty.elim : Empty → Fin (2^L)) m →
∃ t o, Runs W c m t o ∧ t≤C*(2^L)^5 ∧
o dst=integerLeaf L H hh (fun i => (w i:ℚ)) ∧ Frame dst m o := by
classical
let Leaf := {H : SimpleGraph V // ¬ HasWedges H}
let _ : Fintype Leaf := Fintype.ofFinite _
choose cmd coeff kernel using (fun j : Leaf => sparse_native j.val j.property dst hdst)
refine ⟨∑ j : Leaf, coeff j,?_⟩
intro H hh
let j : Leaf := ⟨H,hh⟩
refine ⟨cmd j,?_⟩
intro L W base M cap room w hb m ready
obtain ⟨t,o,run,cost,val,fr⟩ := kernel j (inputData (by positivity) cap room w) m ready
have small : coeff j ≤ ∑ h : Leaf, coeff h :=
Finset.single_le_sum (fun h _ => Nat.zero_le (coeff h)) (Finset.mem_univ j)
have hw (i) : Binary (w i:ℚ) := by
rcases hb i with h|h
· exact Or.inl (by simp [h])
· exact Or.inr (by simp [h])
have refValue := (integerLeaf_cast L H hh _ hw).trans (sparseLeaf_correct L H hh _)
refine ⟨t,o,run,cost.trans (Nat.mul_le_mul_right _ small),?_,fr⟩
exact_mod_cast val.trans refValue.symm
end VWZClique.IntegerRAM.NativeLeaf
end
/- NativeFrameLeaf -/
section
namespace VWZClique.IntegerRAM.NativeFrame
open Structured UniformFolds NativeTraversal
def enterLeaf (d : ℕ) : Command :=
.seq (.atom (.one (-3))) (.seq (.atom (.mul (-2) 0 (-3)))
(.atom (.mul (-1) (reg d .weights) (-3))))
theorem enterLeaf_runs (W d : ℕ) (m : Memory) :
∃ o, Runs W (enterLeaf d) m 3 o ∧ o (-1)=m (reg d .weights) ∧
o (-2)=m 0 ∧ o (-3)=1 ∧ ∀ a : ℤ, 0≤a → o a=m a := by
let u := update m (-3) 1
let v := update u (-2) (m 0)
let o := update v (-1) (m (reg d .weights))
have p := reg_positive d .weights
have s : Runs W (.atom (.one (-3))) m 1 u := .atom (.one _ _)
have t : Runs W (.atom (.mul (-2) 0 (-3))) u 1 v := by
simpa [u,v,update] using Runs.atom (Step.mul (W:=W) u (-2) 0 (-3))
have t' : Runs W (.atom (.mul (-1) (reg d .weights) (-3))) v 1 o := by
simpa [o,v,u,update,show reg d .weights≠ -2 by omega,show reg d .weights≠ -3 by omega] using
Runs.atom (Step.mul (W:=W) v (-1) (reg d .weights) (-3))
refine ⟨o,s.seq (t.seq t'),?_,?_,?_,?_⟩
· simp [o,update]
· simp [o,v,update]
· simp [o,v,u,update]
· intro a ha
simp [o,v,u,update,show a≠ -1 by omega,show a≠ -2 by omega,show a≠ -3 by omega]
/-- Fixed commands for every leaf and depth of the traversal. The table
description and suspended parent frames are the same as those of reset and pop. -/
theorem leaf_transitions :
∃ (op : ℕ → SimpleGraph V → Command) (C : ℕ), ∀ (L W d : ℕ) (hd : d≤36)
(lay : StackLayout) (H : SimpleGraph V) (hh : ¬HasWedges H) (w : WeightKey (2^L) → ℚ)
(hb : ∀ i, Binary (w i)) (q : List (NativeTraversal.Slot L))
(_cap : Graph.Division.Room W (lay.base d+9*(2^L)+81*(2^L*2^L))),
Transition W (Repr lay) (op d H) (.input d w::q) (.value d (integerLeaf L H hh w)::q)
(C*(2^L)^5) := by
classical
obtain ⟨C,all⟩ := NativeLeaf.plan_leaf (-4) (by decide)
let cmd (H : SimpleGraph V) := if h : ¬HasWedges H then Classical.choose (all H h) else Command.skip
let op (d : ℕ) (H : SimpleGraph V) := Command.seq (enterLeaf d) (.seq (cmd H) (copy (reg d .value) (-4)))
refine ⟨op,C+5,?_⟩
intro L W d hd lay H hh w hb q cap m init
obtain ⟨global,⟨ptr,tab⟩,anc⟩ := init
obtain ⟨s,enter,bas,nn,one,keep⟩ := enterLeaf_runs W d m
let N := 2^L
let raw (i : WeightKey N) := m ((lay.base d+Graph.Table.wordIndex i:ℕ):ℤ)
have asRat : (fun i => (raw i:ℚ)) = w := funext tab
have bin : ∀ i, raw i=0 ∨ raw i=1 := by
intro i
rcases hb i with a|b
· left; exact_mod_cast (tab i).trans a
· right; exact_mod_cast (tab i).trans b
have ready : NativeLeaf.Ready (NativeLeaf.inputData (by positivity) cap le_rfl raw)
(Empty.elim : Empty → ℤ) (Empty.elim : Empty → Fin N) s :=
⟨bas.trans ptr,nn.trans global.dim,one,fun i => i.elim,fun i => keep _ (Int.natCast_nonneg _)⟩
obtain ⟨t,y,body,cost,out,fr⟩ :=
Classical.choose_spec (all H hh) L W _ _ cap le_rfl raw bin s ready
have native : Runs W (cmd H) s t y := by simpa only [cmd,dif_pos hh] using body
rw [asRat] at out
have retPos := reg_positive d .value
have cp := copy_runs W (reg d .value) (-4) (by omega) y
let o := update y (reg d .value) (y (-4))
have preserved (a : ℤ) (ha : 0≤a) (hne : a ≠ reg d .value) : o a=m a := by
rw [show o a=y a by simp [o,update,hne],fr a (by omega),keep a ha]
have plane (a : ℕ) (ha : 297≤a) := preserved a (Int.natCast_nonneg _) (distinctData ha hd _)
have parent (j : ℕ) (hj : j<d) (f : Field) := preserved (reg j f) (reg_positive j f).le
(ne_of_lt (separate hj _ _))
refine ⟨3+(t+2),?_,o,enter.seq (native.seq cp),global.transfer (preserved 0 le_rfl (ne_of_lt retPos)) (plane 320 (by decide)) (plane 321 (by decide)),
?_,saved_transfer lay d q plane parent anc⟩
· have hp : 0 < (2^L:ℕ)^5 := by positivity
rw [Nat.add_mul]
omega
· change o (reg d .value) = _
simpa [o,update] using out
end VWZClique.IntegerRAM.NativeFrame
end
/- NativeFrameAssembly -/
section
namespace VWZClique.IntegerRAM.NativeFrame
open Structured UniformFolds NativeTraversal
noncomputable def leafCoefficient : ℕ := Classical.choose (Classical.choose_spec leaf_transitions)
noncomputable def fees (L : ℕ) (P B : SimpleGraph V → ℕ) : Charges :=
⟨fun _ => leafCoefficient*(2^L)^5, P, B, 5, 1, 0⟩
/-- The remaining nonrecursive native components are the projected contraction
(which initializes the cursor), and construction of each masked child (which
also installs its signed coefficient on the suspended parent). -/
structure Kernels {L} (W : ℕ) (lay : StackLayout)
(proj : ℕ → SimpleGraph V → Equiv.Perm V → Command)
(push : ℕ → SimpleGraph V → Equiv.Perm V → Branch → Command)
(P B : SimpleGraph V → ℕ) : Prop where
projected : ∀ d H π w (q : List (NativeTraversal.Slot L)), d+Nat.card (SimpleGraph.edgeSet H)≤36 →
(∀ i, Binary (w i)) → Transition W (Repr lay) (proj d H π) (.input d w::q)
(.cursor d H π .left w 0 (integerTrace (windowAt (Nat.card H.edgeSet)) L H π w)::q) (P H)
child : ∀ depth H π b (i : Fin (visits (number L H) b)) w z (q : List (NativeTraversal.Slot L)), depth<36 →
(∀ j, Binary (w j)) → Transition W (Repr lay) (push depth H π b) (.cursor depth H π b w i.val z::q)
(.input (depth+1) (childWeights H π (numbered H b i) w):: .cursor depth H π b w i.val z::q) (B H)
end VWZClique.IntegerRAM.NativeFrame
end
/- NativeFoldRate -/
section
namespace VWZClique.NativeTraversal
open UniformFolds BlockReduction WeightedProof IntegerRAM IntegerRAM.Structured
open OAI.MatrixMultiplication.Arithmetic
/-- This interface includes all setup and final write-back from the original
adjacency input. All constants and bytecode must be fixed before n is supplied. -/
def Realizes (mm : ℕ→ℕ) (T U A : ℕ) : Prop :=
∃ cutoff : ℕ, ∀ k ≥ cutoff, ∃ (machine : Command) (b p : ℕ) (D : ℝ), k+3≤b ∧ 0<D ∧
∀ (n : ℕ) (G : SimpleGraph (Fin n)) (hn : 2≤n), cutoff≤n →
∃ (f : ℕ) (out : Memory), let L := graphLength n k
(f:ℝ)≤D*((L+1:ℕ):ℝ)^p*(planWork mm T U A L (fixed ⊤):ℝ) ∧
Runs (b*(n.log2+1)) machine (input (MonDepMW.graphInput G)) f out ∧
out ((MonDepMW.graphInput G).length:ℤ)=integerPlan L (fixed ⊤) (graphWeights G (by omega) k)
end VWZClique.NativeTraversal
end
/- NativeAssemblyRate -/
section
namespace VWZClique.IntegerRAM.NativeFrame
open Structured UniformFolds NativeTraversal BlockReduction Graph WeightedProof
/-- The two bytecode families are fixed for all input lengths. Their data and
the accounting bounds depend only on the current dyadic dimension and the
static pattern. The compiler chooses its word-width multiplier once per k. -/
structure Implemented (mm : ℕ→ℕ) (T U A : ℕ) where
projection : ℕ → SimpleGraph V → Equiv.Perm V → Command
push : ℕ → SimpleGraph V → Equiv.Perm V → Branch → Command
projectTime : ℕ → SimpleGraph V → ℕ
pushTime : ℕ → SimpleGraph V → ℕ
factor : ℕ
logPower : ℕ
positive : 0<U
sparseTime : ∀ L H, (fees L (projectTime L) (pushTime L)).small H ≤
(factor*(L+1)^logPower)*(U*(2^L)^5)
projectedTime : ∀ L H, projectTime L H + 2 ≤
(factor*(L+1)^logPower)*(NativeTraversal.projected mm T U L H+3)
pushBound : ∀ L H, pushTime L H + 6 ≤ (factor*(L+1)^logPower)*(U*(2^L)^5)
kernels : ∀ k≥32, ∃ b : ℕ, k+3≤b ∧ 2*((k+8)/9)+11≤b ∧ ∀ n (hn : 32≤n),
let L := graphLength n k
let W := b*(n.log2+1)
let layout := NativeArena.forGraph n k hn
@Kernels L W layout projection push (projectTime L) (pushTime L) ∧
(∀ d≤36, Division.Room W (layout.base d+9*2^L+81*(2^L*2^L))) ∧ Division.Room W ((2^L)^6)
end VWZClique.IntegerRAM.NativeFrame
end
Source
V. Vassilevska Williams and O. Zamir, The k-Clique hypothesis is dead, for good, Theorem 1.1 and Appendix A, pp. 21–22. The Lean data structures and interfaces specify the recursive program, projected products, and the transfer to the uniform word RAM. https://zamir.prof/kclq.pdf