Owned solve buffers and pending recursive queue records
DefinitionNearlyOptimalPPR_Computation_compiler_buffersformalizationgraph-algorithmspagerank
This module supplies the owned buffer and intermediate-memory interfaces for sparse exact solves and touched-vertex queue refresh. Its records describe enumerations, right-hand sides, answer buffers, index epochs, pending queue coverage, and memory frames. The constructor and transport APIs express preservation of these structural records; they do not assume algorithmic accuracy, termination, or a desired work bound. These interfaces support independent verification of numeric assembly, exact-solve invocation, and restoration of valid recursive keys.
Definition code
import Definitions.Def_NearlyOptimalPPR_Computation_compiler_runtime
import Definitions.Def_NearlyOptimalPPR_Computation_recursive
import Mathlib.Data.Finset.Union
set_option linter.all false
-- Buffer and update interface from Solutions.HeapMemory
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
namespace SparseQueue
open Batteries.BinomialHeap.Imp
noncomputable section
lemma ForestRep.frame {I J : ℤ → ℤ} {p : ℤ} {t : HeapNode ℕ} {F : Finset ℤ}
(h : ForestRep I p t F) (he : ∀ a ∈ F, J a=I a) : ForestRep J p t F := by
induction h with
| nil => exact ForestRep.nil
| node p a cp sp c s C S hp hk hc hs rc rs hdC hdS hdCS ic is =>
apply ForestRep.node p a cp sp c s C S hp
· rw [he p (by simp [nodeCells]),hk]
· rw [he (p+1) (by simp [nodeCells]),hc]
· rw [he (p+2) (by simp [nodeCells]),hs]
· exact ic (fun a ha => he a (by simp [ha]))
· exact is (fun a ha => he a (by simp [ha]))
· exact hdC
· exact hdS
· exact hdCS
end
end SparseQueue
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.RankArrayMemory
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
namespace SparseQueue
noncomputable section
lemma mem_arrayCells (base z : ℤ) (length : ℕ) :
z ∈ arrayCells base length ↔ ∃ i : ℕ, i < length ∧ z=base+(i : ℤ) := by
simp [arrayCells,Finset.mem_image,eq_comm]
lemma SlotRep.frame {I J : ℤ → ℤ} {p : ℤ} {v : Option RankedTree} {F : Finset ℤ}
(h : SlotRep I p v F) (he : ∀ a ∈ F, J a=I a) : SlotRep J p v F := by
cases v with
| none => exact h
| some t => exact ForestRep.frame h he
lemma RankArrayRep.frame {I J : ℤ → ℤ} {base : ℤ} {length : ℕ} {slots : RankSlots}
{roots : ℕ → ℤ} {feet : ℕ → Finset ℤ} (h : RankArrayRep I base length slots roots feet)
(he : ∀ a ∈ queueCells base length feet, J a=I a) : RankArrayRep J base length slots roots feet := by
refine ⟨h.positive,?_,?_,h.separate,h.pairwise,h.bounded,h.valid⟩
· intro i hi
rw [he _ (Finset.mem_union_left _ ((mem_arrayCells _ _ _).mpr ⟨i,hi,rfl⟩)),h.array i hi]
· intro i hi
apply (h.node i hi).frame
intro a ha
apply he
exact Finset.mem_union_right _ (Finset.mem_biUnion.mpr ⟨i,Finset.mem_range.mpr hi,ha⟩)
end
end SparseQueue
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.RankQueueObject
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
namespace SparseQueue
noncomputable section
namespace RankQueueObject
def frame {I J : ℤ → ℤ} {base : ℤ} {length : ℕ} {free nextFree floor : ℤ}
(obj : RankQueueObject I base length free floor)
(hI : ∀ z ∈ obj.cells, J z=I z) (hFree : free ≤ nextFree) :
RankQueueObject J base length nextFree floor := {
slots := obj.slots
roots := obj.roots
feet := obj.feet
representation := obj.representation.frame hI
unique := obj.unique
below := fun z hz => (obj.below z hz).trans_le hFree
above := obj.above
}
end RankQueueObject
structure ExteriorQueueContext (st : MachineState) (width levelBase flagOffset length : ℕ)
(base floor : ℤ) (q : ℝ) : Prop where
zero : st.scalar.core.ptrs 0=0
basePointer : st.scalar.core.ptrs 13=base
lengthPointer : st.scalar.core.ptrs 25=(length : ℤ)
widthPointer : st.scalar.core.ptrs 50=(width : ℤ)
levelPointer : st.scalar.core.ptrs 87=(levelBase : ℤ)
flagPointer : st.scalar.core.ptrs 88=(flagOffset : ℤ)
threshold : st.scalar.core.regs 20=q
floorBound : floor ≤ st.scalar.core.ptrs 20
end
end SparseQueue
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.KeyListRepresentation
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
namespace SparseQueue
open Batteries.BinomialHeap.Imp
noncomputable section
lemma KeyListRep.frame {I J : ℤ → ℤ} {head : ℤ} {keys : List ℕ} {F : Finset ℤ}
(h : KeyListRep I head keys F) (he : ∀ z ∈ F, J z=I z) : KeyListRep J head keys F :=
ForestRep.frame h he
end
end SparseQueue
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.VertexListRepresentation
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
lemma VertexListRep.frame {n : ℕ} {I J : ℤ → ℤ} {head : ℤ} {vertices : List (Fin n)} {F : Finset ℤ}
(h : VertexListRep I head vertices F) (he : ∀ z ∈ F, J z=I z) : VertexListRep J head vertices F := KeyListRep.frame h he
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.FramePendingKeys
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
structure FramePendingKeys {n : ℕ} (g : InputGraph n) (logical : RecursiveState n)
(j width length : ℕ) (machine : MachineState) (floor : ℤ) where
N : machine.scalar.core.mem (levelHeaderAddress j 0)=(logical.frames j).N
q : machine.scalar.core.mem (levelHeaderAddress j 1)=(logical.frames j).q
Q : machine.scalar.core.mem (levelHeaderAddress j 3)=(logical.frames j).Q
W : machine.scalar.core.mem (levelHeaderAddress j 4)=(logical.frames j).W
theta : machine.scalar.core.mem (levelHeaderAddress j 5)=(logical.frames j).theta
block : machine.scalar.integerMemory (levelHeaderAddress j 14)=((logical.frames j).block : ℤ)
pc : machine.scalar.integerMemory (levelHeaderAddress j 0)=(normalizePCNumber (logical.frames j).pc : ℤ)
openBudget : machine.scalar.integerMemory (levelHeaderAddress j 9)=if (logical.frames j).openBudget then 1 else 0
needFull : machine.scalar.integerMemory (levelHeaderAddress j 10)=if (logical.frames j).needFull then 1 else 0
children : machine.scalar.integerMemory (levelHeaderAddress j 11)=((logical.frames j).childrenThisEpisode : ℤ)
reference : ∀ v ∈ parentDomain logical j,
machine.scalar.core.mem (vertexRecordAddress width v.val (16*(j+1)))=(logical.frames j).reference v
residual : ∀ v ∈ parentDomain logical j,
machine.scalar.core.mem (vertexRecordAddress width v.val (16*(j+1)+1))=(logical.frames j).residual v
activeFlags : ∀ v ∈ parentDomain logical j,
machine.scalar.integerMemory (vertexRecordAddress width v.val (16*(j+1)+2))=if v ∈ (logical.frames j).active then 1 else 0
cacheFlags : ∀ v ∈ parentDomain logical j,
machine.scalar.integerMemory (vertexRecordAddress width v.val (16*(j+1)+4))=if v ∈ (logical.frames j).cache then 1 else 0
activeVertices : List (Fin n)
activeFoot : Finset ℤ
activeRep : VertexListRep machine.scalar.integerMemory (machine.scalar.integerMemory (levelHeaderAddress j 1)) activeVertices activeFoot
activeNodup : activeVertices.Nodup
activeSet : activeVertices.toFinset=(logical.frames j).active
activeCount : machine.scalar.integerMemory (levelHeaderAddress j 3)=((logical.frames j).active.card : ℤ)
activeVolume : machine.scalar.integerMemory (levelHeaderAddress j 2)=(volumeNat g (logical.frames j).active : ℤ)
activeBelow : ∀ z ∈ activeFoot, z < machine.scalar.core.ptrs 20
activeAbove : ∀ z ∈ activeFoot, floor ≤ z
cacheVertices : List (Fin n)
cacheFoot : Finset ℤ
cacheRep : VertexListRep machine.scalar.integerMemory (machine.scalar.integerMemory (levelHeaderAddress j 4)) cacheVertices cacheFoot
cacheNodup : cacheVertices.Nodup
cacheSet : cacheVertices.toFinset=(logical.frames j).cache
cacheCount : machine.scalar.integerMemory (levelHeaderAddress j 5)=((logical.frames j).cache.card : ℤ)
cacheVolume : machine.scalar.integerMemory (levelHeaderAddress j 6)=(volumeNat g (logical.frames j).cache : ℤ)
cacheBelow : ∀ z ∈ cacheFoot, z < machine.scalar.core.ptrs 20
cacheAbove : ∀ z ∈ cacheFoot, floor ≤ z
exteriorBase : ℤ
highBase : ℤ
exteriorPointer : machine.scalar.integerMemory (levelHeaderAddress j 7)=exteriorBase
highPointer : machine.scalar.integerMemory (levelHeaderAddress j 8)=highBase
exteriorObject : RankQueueObject machine.scalar.integerMemory exteriorBase length (machine.scalar.core.ptrs 20) floor
highObject : RankQueueObject machine.scalar.integerMemory highBase length (machine.scalar.core.ptrs 20) floor
exteriorData : ExteriorQueueMemory machine.scalar.integerMemory machine.scalar.core.mem width
(16*(j+1)) (16*(j+1)+3) (logical.frames j).q (parentDomain logical j)
((logical.frames j).exterior.image Fin.val) exteriorObject.keys
virtualExcluded : ∀ v ∈ parentDomain logical j,
machine.scalar.integerMemory (vertexRecordAddress width v.val (16*(j+1)+5))=0
highFlags : QueuedFlags machine.scalar.integerMemory width (16*(j+1)+6) (parentDomain logical j) highObject.keys
highDomain : highObject.keys ⊆ (parentDomain logical j).image Fin.val
highValid : ∀ v ∈ parentDomain logical j, v.val ∈ (logical.frames j).high.image Fin.val ↔
machine.scalar.integerMemory (vertexRecordAddress width v.val (16*(j+1)+2)) ≠ 0 ∧
3*(logical.frames j).theta*(machine.scalar.integerMemory (vertexRecordAddress width v.val 0) : ℝ) ≤
machine.scalar.core.mem (vertexRecordAddress width v.val (16*(j+1)+1))
namespace FramePendingKeys
def owned {n : ℕ} {g : InputGraph n} {logical : RecursiveState n} {j width length : ℕ}
{machine : MachineState} {floor : ℤ} (f : FramePendingKeys g logical j width length machine floor) : Finset ℤ :=
f.activeFoot ∪ f.cacheFoot ∪ f.exteriorObject.cells ∪ f.highObject.cells
def pieces {n : ℕ} {g : InputGraph n} {logical : RecursiveState n} {j width length : ℕ}
{machine : MachineState} {floor : ℤ} (f : FramePendingKeys g logical j width length machine floor) : List (Finset ℤ) :=
[f.activeFoot,f.cacheFoot,f.exteriorObject.cells,f.highObject.cells]
def ofMemory {n : ℕ} {g : InputGraph n} {logical : RecursiveState n} {j width length : ℕ}
{machine : MachineState} {floor : ℤ} (f : RecursiveFrameMemory g logical j width length machine floor) :
FramePendingKeys g logical j width length machine floor := {
N := f.N
q := f.q
Q := f.Q
W := f.W
theta := f.theta
block := f.block
pc := f.pc
openBudget := f.openBudget
needFull := f.needFull
children := f.children
reference := f.reference
residual := f.residual
activeFlags := f.activeFlags
cacheFlags := f.cacheFlags
activeVertices := f.activeVertices
activeFoot := f.activeFoot
activeRep := f.activeRep
activeNodup := f.activeNodup
activeSet := f.activeSet
activeCount := f.activeCount
activeVolume := f.activeVolume
activeBelow := f.activeBelow
activeAbove := f.activeAbove
cacheVertices := f.cacheVertices
cacheFoot := f.cacheFoot
cacheRep := f.cacheRep
cacheNodup := f.cacheNodup
cacheSet := f.cacheSet
cacheCount := f.cacheCount
cacheVolume := f.cacheVolume
cacheBelow := f.cacheBelow
cacheAbove := f.cacheAbove
exteriorBase := f.exteriorBase
highBase := f.highBase
exteriorPointer := f.exteriorPointer
highPointer := f.highPointer
exteriorObject := f.exteriorObject
highObject := f.highObject
exteriorData := f.exteriorData
virtualExcluded := f.virtualExcluded
highFlags := f.highFlags
highDomain := f.highDomain
highValid := f.highValid
}
end FramePendingKeys
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.CompilerExteriorNonactivation
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
noncomputable section
def compilerExteriorDelta {n : ℕ} (g : InputGraph n) (α : ℝ) (st : RecursiveState n) (t : ℕ) (v : Fin n) : ℝ :=
min ((st.frames t).residual v/(5*LocalPush.deg g.graph v)) (3*(st.frames t).q/8-relative st t v)
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.RecursiveFrameTransport
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
def RecursiveFrameMemory.logical_frame {n : ℕ} {g : InputGraph n} {a b : RecursiveState n}
{j width length : ℕ} {machine : MachineState} {floor : ℤ}
(f : RecursiveFrameMemory g a j width length machine floor)
(hFrame : b.frames j=a.frames j) (hDomain : parentDomain b j=parentDomain a j) :
RecursiveFrameMemory g b j width length machine floor := {
N := by rw [hFrame]; exact f.N
q := by rw [hFrame]; exact f.q
Q := by rw [hFrame]; exact f.Q
W := by rw [hFrame]; exact f.W
theta := by rw [hFrame]; exact f.theta
block := by rw [hFrame]; exact f.block
pc := by rw [hFrame]; exact f.pc
openBudget := by rw [hFrame]; exact f.openBudget
needFull := by rw [hFrame]; exact f.needFull
children := by rw [hFrame]; exact f.children
reference := by rw [hFrame,hDomain]; exact f.reference
residual := by rw [hFrame,hDomain]; exact f.residual
activeFlags := by rw [hFrame,hDomain]; exact f.activeFlags
cacheFlags := by rw [hFrame,hDomain]; exact f.cacheFlags
activeVertices := f.activeVertices
activeFoot := f.activeFoot
activeRep := f.activeRep
activeNodup := f.activeNodup
activeSet := by rw [hFrame]; exact f.activeSet
activeCount := by rw [hFrame]; exact f.activeCount
activeVolume := by rw [hFrame]; exact f.activeVolume
activeBelow := f.activeBelow
activeAbove := f.activeAbove
cacheVertices := f.cacheVertices
cacheFoot := f.cacheFoot
cacheRep := f.cacheRep
cacheNodup := f.cacheNodup
cacheSet := by rw [hFrame]; exact f.cacheSet
cacheCount := by rw [hFrame]; exact f.cacheCount
cacheVolume := by rw [hFrame]; exact f.cacheVolume
cacheBelow := f.cacheBelow
cacheAbove := f.cacheAbove
exteriorBase := f.exteriorBase
highBase := f.highBase
exteriorPointer := f.exteriorPointer
highPointer := f.highPointer
exteriorObject := f.exteriorObject
highObject := f.highObject
exteriorData := by rw [hFrame,hDomain]; exact f.exteriorData
exteriorCover := by rw [hFrame]; exact f.exteriorCover
highBoolean := by rw [hFrame,hDomain]; exact f.highBoolean
virtualExcluded := by rw [hDomain]; exact f.virtualExcluded
highFlags := by rw [hDomain]; exact f.highFlags
highDomain := by rw [hDomain]; exact f.highDomain
highValid := by rw [hFrame,hDomain]; exact f.highValid
highCover := by rw [hFrame]; exact f.highCover
}
def RecursiveFrameMemory.memory_frame {n : ℕ} {g : InputGraph n} {logical : RecursiveState n}
{j width length : ℕ} {st out : MachineState} {floor : ℤ}
(f : RecursiveFrameMemory g logical j width length st floor)
(hFree : st.scalar.core.ptrs 20 ≤ out.scalar.core.ptrs 20)
(hHeaderI : ∀ slot < 32, out.scalar.integerMemory (levelHeaderAddress j slot)=st.scalar.integerMemory (levelHeaderAddress j slot))
(hHeaderR : ∀ slot < 32, out.scalar.core.mem (levelHeaderAddress j slot)=st.scalar.core.mem (levelHeaderAddress j slot))
(hFieldsI : ∀ v ∈ parentDomain logical j, ∀ field < 16*(j+1)+7,
out.scalar.integerMemory (vertexRecordAddress width v.val field)=st.scalar.integerMemory (vertexRecordAddress width v.val field))
(hFieldsR : ∀ v ∈ parentDomain logical j, ∀ field < 16*(j+1)+7,
out.scalar.core.mem (vertexRecordAddress width v.val field)=st.scalar.core.mem (vertexRecordAddress width v.val field))
(hOwned : ∀ z ∈ f.owned, out.scalar.integerMemory z=st.scalar.integerMemory z) :
RecursiveFrameMemory g logical j width length out floor := by
let ext := f.exteriorObject.frame
(fun z hz => hOwned z (Finset.mem_union_left _ (Finset.mem_union_right _ hz))) hFree
let high := f.highObject.frame (fun z hz => hOwned z (Finset.mem_union_right _ hz)) hFree
refine {
N := (hHeaderR 0 (by decide)).trans f.N
q := (hHeaderR 1 (by decide)).trans f.q
Q := (hHeaderR 3 (by decide)).trans f.Q
W := (hHeaderR 4 (by decide)).trans f.W
theta := (hHeaderR 5 (by decide)).trans f.theta
block := (hHeaderI 14 (by decide)).trans f.block
pc := (hHeaderI 0 (by decide)).trans f.pc
openBudget := (hHeaderI 9 (by decide)).trans f.openBudget
needFull := (hHeaderI 10 (by decide)).trans f.needFull
children := (hHeaderI 11 (by decide)).trans f.children
reference := fun v hv => (hFieldsR v hv _ (by omega)).trans (f.reference v hv)
residual := fun v hv => (hFieldsR v hv _ (by omega)).trans (f.residual v hv)
activeFlags := fun v hv => (hFieldsI v hv _ (by omega)).trans (f.activeFlags v hv)
cacheFlags := fun v hv => (hFieldsI v hv _ (by omega)).trans (f.cacheFlags v hv)
activeVertices := f.activeVertices
activeFoot := f.activeFoot
activeRep := ?_
activeNodup := f.activeNodup
activeSet := f.activeSet
activeCount := (hHeaderI 3 (by decide)).trans f.activeCount
activeVolume := (hHeaderI 2 (by decide)).trans f.activeVolume
activeBelow := fun z hz => (f.activeBelow z hz).trans_le hFree
activeAbove := f.activeAbove
cacheVertices := f.cacheVertices
cacheFoot := f.cacheFoot
cacheRep := ?_
cacheNodup := f.cacheNodup
cacheSet := f.cacheSet
cacheCount := (hHeaderI 5 (by decide)).trans f.cacheCount
cacheVolume := (hHeaderI 6 (by decide)).trans f.cacheVolume
cacheBelow := fun z hz => (f.cacheBelow z hz).trans_le hFree
cacheAbove := f.cacheAbove
exteriorBase := f.exteriorBase
highBase := f.highBase
exteriorPointer := (hHeaderI 7 (by decide)).trans f.exteriorPointer
highPointer := (hHeaderI 8 (by decide)).trans f.highPointer
exteriorObject := ext
highObject := high
exteriorData := ?_
exteriorCover := f.exteriorCover
highBoolean := ?_
virtualExcluded := fun v hv => (hFieldsI v hv _ (by omega)).trans (f.virtualExcluded v hv)
highFlags := ?_
highDomain := f.highDomain
highValid := ?_
highCover := f.highCover
}
· rw [hHeaderI 1 (by decide)]
apply f.activeRep.frame
intro z hz
apply hOwned
exact Finset.mem_union_left _ (Finset.mem_union_left _ (Finset.mem_union_left _ hz))
· rw [hHeaderI 4 (by decide)]
apply f.cacheRep.frame
intro z hz
apply hOwned
exact Finset.mem_union_left _ (Finset.mem_union_left _ (Finset.mem_union_right _ hz))
· refine ⟨f.exteriorData.queuedDomain,?_,?_,?_⟩
· intro v hv
rw [hFieldsI v hv _ (by omega)]
exact f.exteriorData.flags v hv
· intro v hv
rw [hFieldsI v hv _ (by omega)]
exact f.exteriorData.activeNonnegative v hv
· intro v hv
rw [hFieldsI v hv _ (by omega),hFieldsI v hv 0 (by omega),hFieldsR v hv _ (by omega)]
exact f.exteriorData.eligibility v hv
· intro v hv
rw [hFieldsR v hv _ (by omega),hFieldsI v hv _ (by omega),hFieldsI v hv 0 (by omega),hFieldsR v hv _ (by omega)]
exact f.highBoolean v hv
· intro v hv
rw [hFieldsI v hv _ (by omega)]
exact f.highFlags v hv
· intro v hv
rw [hFieldsI v hv _ (by omega),hFieldsI v hv 0 (by omega),hFieldsR v hv _ (by omega)]
exact f.highValid v hv
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.RecursiveMachineFrame
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
noncomputable section
def RecursiveMachineMemory.frame {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ}
{ell length : ℕ} {logical : RecursiveState n} {st out : MachineState}
(pm : RecursiveMachineMemory g s α ε ell length logical st)
(hI : out.scalar.integerMemory=st.scalar.integerMemory) (hR : out.scalar.core.mem=st.scalar.core.mem)
(hP : ∀ r ∈ ([0,20,50,100] : List ℕ), out.scalar.core.ptrs r=st.scalar.core.ptrs r)
(hG : ∀ r ∈ ([30,31] : List ℕ), out.scalar.core.regs r=st.scalar.core.regs r)
(hO : out.output=st.output) : RecursiveMachineMemory g s α ε ell length logical out := {
zero := (hP 0 (by simp)).trans pm.zero
top := (hP 100 (by simp)).trans pm.top
width := (hP 50 (by simp)).trans pm.width
alphaRegister := (hG 30 (by simp)).trans pm.alphaRegister
one := (hG 31 (by simp)).trans pm.one
alphaMemory := by rw [hR]; exact pm.alphaMemory
epsilonMemory := by rw [hR]; exact pm.epsilonMemory
depthMemory := by rw [hI]; exact pm.depthMemory
lengthMemory := by rw [hI]; exact pm.lengthMemory
seedMemory := by rw [hI]; exact pm.seedMemory
allocator := by rw [hP 20 (by simp)]; exact pm.allocator
potential := by rw [hR]; exact pm.potential
seedMarker := by rw [hR]; exact pm.seedMarker
boundary := by rw [hI]; exact pm.boundary
graphCache := by rw [hI,hP 20 (by simp)]; exact pm.graphCache
rowAbove := by rw [hI]; exact pm.rowAbove
knownDegree := by rw [hI]; exact pm.knownDegree
unknownDegree := by rw [hI]; exact pm.unknownDegree
frames := fun i hi => (pm.frames i hi).memory_frame (by rw [hP 20 (by simp)])
(by intros; exact congrFun hI _) (by intros; exact congrFun hR _)
(by intros; exact congrFun hI _) (by intros; exact congrFun hR _) (by intros; exact congrFun hI _)
pieceSeparation := pm.pieceSeparation
frameSeparation := pm.frameSeparation
cacheSeparation := by
intro i hi
change Disjoint (pm.frames i hi).owned (cachedRowCells g out.scalar.integerMemory (16*(ell+3)) logical.stored)
rw [hI]
exact pm.cacheSeparation i hi
output := hO.trans pm.output
}
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.HeapNodeAllocation
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
namespace SparseQueue
noncomputable section
def nodeAllocMemory (I : ℤ → ℤ) (p key : ℤ) : ℤ → ℤ :=
Function.update (Function.update (Function.update I p key) (p+1) 0) (p+2) 0
end
end SparseQueue
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.GraphCacheFresh
set_option autoImplicit false
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
def cacheWriteCells (width vertex : ℕ) (free : ℤ) (degree : ℕ) : Finset ℤ :=
arrayCells free degree ∪ {vertexRecordAddress width vertex 0,vertexRecordAddress width vertex 1,vertexRecordAddress width vertex 2}
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.MachinePendingKeys
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
structure MachinePendingKeys {n : ℕ} (g : InputGraph n) (s : Fin n) (α ε : ℝ) (ell length : ℕ)
(logical : RecursiveState n) (machine : MachineState) where
zero : machine.scalar.core.ptrs 0=0
top : machine.scalar.core.ptrs 100=(logical.top : ℤ)
width : machine.scalar.core.ptrs 50=((16*(ell+3) : ℕ) : ℤ)
alphaRegister : machine.scalar.core.regs 30=α
one : machine.scalar.core.regs 31=1
alphaMemory : machine.scalar.core.mem 0=α
epsilonMemory : machine.scalar.core.mem 1=ε
depthMemory : machine.scalar.integerMemory 2=((ell+2 : ℕ) : ℤ)
lengthMemory : machine.scalar.integerMemory 5=(length : ℤ)
seedMemory : machine.scalar.integerMemory 0=(s.val : ℤ)
allocator : 128+32*((ell+2 : ℕ) : ℤ) ≤ machine.scalar.core.ptrs 20
potential : ∀ v : Fin n, machine.scalar.core.mem (vertexRecordAddress (16*(ell+3)) v.val 0)=logical.x v
seedMarker : ∀ v : Fin n, machine.scalar.core.mem (vertexRecordAddress (16*(ell+3)) v.val 2)=LocalPush.e s v
boundary : machine.scalar.integerMemory 7=logical.boundaryEdges
graphCache : GraphCache g machine.scalar.integerMemory (16*(ell+3)) logical.stored (machine.scalar.core.ptrs 20)
rowAbove : ∀ v ∈ logical.stored,
128+32*((ell+2 : ℕ) : ℤ) ≤ machine.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 1)
knownDegree : ∀ v ∈ recursiveDegreeDomain g s logical,
machine.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 0)=((g.neighbors v).length : ℤ)
unknownDegree : ∀ v ∉ recursiveDegreeDomain g s logical,
machine.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 0)=0
frames : ∀ j ≤ logical.top, FramePendingKeys g logical j (16*(ell+3)) length machine (128+32*((ell+2 : ℕ) : ℤ))
pieceSeparation : ∀ j, ∀ hj : j ≤ logical.top,
((frames j hj).pieces).Pairwise Disjoint
frameSeparation : ∀ i, ∀ hi : i ≤ logical.top, ∀ j, ∀ hj : j ≤ logical.top, i ≠ j →
Disjoint (frames i hi).owned (frames j hj).owned
cacheSeparation : ∀ j, ∀ hj : j ≤ logical.top,
Disjoint (frames j hj).owned (cachedRowCells g machine.scalar.integerMemory (16*(ell+3)) logical.stored)
output : machine.output=[]
namespace MachinePendingKeys
def ofMemory {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ} {ell length : ℕ}
{logical : RecursiveState n} {machine : MachineState}
(f : RecursiveMachineMemory g s α ε ell length logical machine) :
MachinePendingKeys g s α ε ell length logical machine := {
zero := f.zero
top := f.top
width := f.width
alphaRegister := f.alphaRegister
one := f.one
alphaMemory := f.alphaMemory
epsilonMemory := f.epsilonMemory
depthMemory := f.depthMemory
lengthMemory := f.lengthMemory
seedMemory := f.seedMemory
allocator := f.allocator
potential := f.potential
seedMarker := f.seedMarker
boundary := f.boundary
graphCache := f.graphCache
rowAbove := f.rowAbove
knownDegree := f.knownDegree
unknownDegree := f.unknownDegree
frames := fun j hj => FramePendingKeys.ofMemory (f.frames j hj)
pieceSeparation := f.pieceSeparation
frameSeparation := f.frameSeparation
cacheSeparation := f.cacheSeparation
output := f.output
}
end MachinePendingKeys
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.ScalarLevelLoop
set_option autoImplicit false
set_option maxRecDepth 10000
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
noncomputable section
def levelRealMemoryFold (update : ℕ → (ℤ → ℝ) → (ℤ → ℝ)) : ℕ → ℕ → (ℤ → ℝ) → (ℤ → ℝ)
| _,0,R => R
| i,k+1,R => levelRealMemoryFold update (i+1) k (update i R)
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.PayloadLevelLoop
set_option autoImplicit false
set_option maxRecDepth 10000
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
noncomputable section
def levelPayloadFold {Payload : Type} (update : ℕ → Payload → Payload) : ℕ → ℕ → Payload → Payload
| _,0,payload => payload
| i,k+1,payload => levelPayloadFold update (i+1) k (update i payload)
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.FramePendingScopedTransport
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
def FramePendingKeys.scoped_frame {n : ℕ} {g : InputGraph n} {logical : RecursiveState n}
{j width length : ℕ} {st out : MachineState} {floor : ℤ}
(f : FramePendingKeys g logical j width length st floor)
(hFree : st.scalar.core.ptrs 20 ≤ out.scalar.core.ptrs 20)
(hHeaderI : ∀ slot < 32, out.scalar.integerMemory (levelHeaderAddress j slot)=st.scalar.integerMemory (levelHeaderAddress j slot))
(hHeaderR : ∀ slot < 32, out.scalar.core.mem (levelHeaderAddress j slot)=st.scalar.core.mem (levelHeaderAddress j slot))
(hFieldsI : ∀ v ∈ parentDomain logical j, ∀ field < 16*(j+1)+7, (field=0 ∨ 16*(j+1) ≤ field) →
out.scalar.integerMemory (vertexRecordAddress width v.val field)=st.scalar.integerMemory (vertexRecordAddress width v.val field))
(hFieldsR : ∀ v ∈ parentDomain logical j, ∀ field < 16*(j+1)+7, (field=0 ∨ 16*(j+1) ≤ field) →
out.scalar.core.mem (vertexRecordAddress width v.val field)=st.scalar.core.mem (vertexRecordAddress width v.val field))
(hOwned : ∀ z ∈ f.owned, out.scalar.integerMemory z=st.scalar.integerMemory z) :
FramePendingKeys g logical j width length out floor := by
let ext := f.exteriorObject.frame
(fun z hz => hOwned z (Finset.mem_union_left _ (Finset.mem_union_right _ hz))) hFree
let high := f.highObject.frame (fun z hz => hOwned z (Finset.mem_union_right _ hz)) hFree
refine {
N := (hHeaderR 0 (by decide)).trans f.N
q := (hHeaderR 1 (by decide)).trans f.q
Q := (hHeaderR 3 (by decide)).trans f.Q
W := (hHeaderR 4 (by decide)).trans f.W
theta := (hHeaderR 5 (by decide)).trans f.theta
block := (hHeaderI 14 (by decide)).trans f.block
pc := (hHeaderI 0 (by decide)).trans f.pc
openBudget := (hHeaderI 9 (by decide)).trans f.openBudget
needFull := (hHeaderI 10 (by decide)).trans f.needFull
children := (hHeaderI 11 (by decide)).trans f.children
reference := fun v hv => (hFieldsR v hv _ (by omega) (by omega)).trans (f.reference v hv)
residual := fun v hv => (hFieldsR v hv _ (by omega) (by omega)).trans (f.residual v hv)
activeFlags := fun v hv => (hFieldsI v hv _ (by omega) (by omega)).trans (f.activeFlags v hv)
cacheFlags := fun v hv => (hFieldsI v hv _ (by omega) (by omega)).trans (f.cacheFlags v hv)
activeVertices := f.activeVertices
activeFoot := f.activeFoot
activeRep := ?_
activeNodup := f.activeNodup
activeSet := f.activeSet
activeCount := (hHeaderI 3 (by decide)).trans f.activeCount
activeVolume := (hHeaderI 2 (by decide)).trans f.activeVolume
activeBelow := fun z hz => (f.activeBelow z hz).trans_le hFree
activeAbove := f.activeAbove
cacheVertices := f.cacheVertices
cacheFoot := f.cacheFoot
cacheRep := ?_
cacheNodup := f.cacheNodup
cacheSet := f.cacheSet
cacheCount := (hHeaderI 5 (by decide)).trans f.cacheCount
cacheVolume := (hHeaderI 6 (by decide)).trans f.cacheVolume
cacheBelow := fun z hz => (f.cacheBelow z hz).trans_le hFree
cacheAbove := f.cacheAbove
exteriorBase := f.exteriorBase
highBase := f.highBase
exteriorPointer := (hHeaderI 7 (by decide)).trans f.exteriorPointer
highPointer := (hHeaderI 8 (by decide)).trans f.highPointer
exteriorObject := ext
highObject := high
exteriorData := ?_
virtualExcluded := fun v hv => (hFieldsI v hv _ (by omega) (by omega)).trans (f.virtualExcluded v hv)
highFlags := ?_
highDomain := f.highDomain
highValid := ?_
}
· rw [hHeaderI 1 (by decide)]
apply f.activeRep.frame
intro z hz
apply hOwned
exact Finset.mem_union_left _ (Finset.mem_union_left _ (Finset.mem_union_left _ hz))
· rw [hHeaderI 4 (by decide)]
apply f.cacheRep.frame
intro z hz
apply hOwned
exact Finset.mem_union_left _ (Finset.mem_union_left _ (Finset.mem_union_right _ hz))
· refine ⟨f.exteriorData.queuedDomain,?_,?_,?_⟩
· intro v hv
rw [hFieldsI v hv _ (by omega) (by omega)]
exact f.exteriorData.flags v hv
· intro v hv
rw [hFieldsI v hv _ (by omega) (by omega)]
exact f.exteriorData.activeNonnegative v hv
· intro v hv
rw [hFieldsI v hv _ (by omega) (by omega),hFieldsI v hv 0 (by omega) (by omega),hFieldsR v hv _ (by omega) (by omega)]
exact f.exteriorData.eligibility v hv
· intro v hv
rw [hFieldsI v hv _ (by omega) (by omega)]
exact f.highFlags v hv
· intro v hv
rw [hFieldsI v hv _ (by omega) (by omega),hFieldsI v hv 0 (by omega) (by omega),hFieldsR v hv _ (by omega) (by omega)]
exact f.highValid v hv
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.PendingQueuePotential
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
noncomputable section
def FramePendingKeys.queueMass {n : ℕ} {g : InputGraph n} {logical : RecursiveState n}
{j width length : ℕ} {machine : MachineState} {floor : ℤ}
(frame : FramePendingKeys g logical j width length machine floor) : ℕ :=
frame.exteriorObject.mass+frame.highObject.mass
def MachinePendingKeys.queueMass {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ}
{ell length : ℕ} {logical : RecursiveState n} {machine : MachineState}
(memory : MachinePendingKeys g s α ε ell length logical machine) : ℕ :=
∑ i ∈ Finset.range (logical.top+1), if hi : i ≤ logical.top then (memory.frames i hi).queueMass else 0
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.MachinePendingFrame
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
noncomputable section
def MachinePendingKeys.frame {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ}
{ell length : ℕ} {logical : RecursiveState n} {st out : MachineState}
(pm : MachinePendingKeys g s α ε ell length logical st)
(hI : out.scalar.integerMemory=st.scalar.integerMemory) (hR : out.scalar.core.mem=st.scalar.core.mem)
(hP : ∀ r ∈ ([0,20,50,100] : List ℕ), out.scalar.core.ptrs r=st.scalar.core.ptrs r)
(hG : ∀ r ∈ ([30,31] : List ℕ), out.scalar.core.regs r=st.scalar.core.regs r)
(hO : out.output=st.output) : MachinePendingKeys g s α ε ell length logical out := {
zero := (hP 0 (by simp)).trans pm.zero
top := (hP 100 (by simp)).trans pm.top
width := (hP 50 (by simp)).trans pm.width
alphaRegister := (hG 30 (by simp)).trans pm.alphaRegister
one := (hG 31 (by simp)).trans pm.one
alphaMemory := by rw [hR]; exact pm.alphaMemory
epsilonMemory := by rw [hR]; exact pm.epsilonMemory
depthMemory := by rw [hI]; exact pm.depthMemory
lengthMemory := by rw [hI]; exact pm.lengthMemory
seedMemory := by rw [hI]; exact pm.seedMemory
allocator := by rw [hP 20 (by simp)]; exact pm.allocator
potential := by rw [hR]; exact pm.potential
seedMarker := by rw [hR]; exact pm.seedMarker
boundary := by rw [hI]; exact pm.boundary
graphCache := by rw [hI,hP 20 (by simp)]; exact pm.graphCache
rowAbove := by rw [hI]; exact pm.rowAbove
knownDegree := by rw [hI]; exact pm.knownDegree
unknownDegree := by rw [hI]; exact pm.unknownDegree
frames := fun i hi => (pm.frames i hi).scoped_frame (by rw [hP 20 (by simp)])
(by intros; exact congrFun hI _) (by intros; exact congrFun hR _)
(by intros; exact congrFun hI _) (by intros; exact congrFun hR _) (by intros; exact congrFun hI _)
pieceSeparation := pm.pieceSeparation
frameSeparation := pm.frameSeparation
cacheSeparation := by
intro i hi
change Disjoint (pm.frames i hi).owned (cachedRowCells g out.scalar.integerMemory (16*(ell+3)) logical.stored)
rw [hI]
exact pm.cacheSeparation i hi
output := hO.trans pm.output
}
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.PendingIntegerFrame
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
noncomputable section
structure PendingIntegerFrame {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ}
{ell length : ℕ} {logical : RecursiveState n} {st out : MachineState}
(old : MachinePendingKeys g s α ε ell length logical st)
(next : MachinePendingKeys g s α ε ell length logical out) : Prop where
free : st.scalar.core.ptrs 20 ≤ out.scalar.core.ptrs 20
oldOwned : ∀ i, ∀ hi : i ≤ logical.top, ∀ z ∈ (next.frames i hi).owned,
z < st.scalar.core.ptrs 20 → z ∈ (old.frames i hi).owned
integerFrame : ∀ z, 0 ≤ z → z < st.scalar.core.ptrs 20 →
(∀ i, ∀ hi : i ≤ logical.top, z ∉ (old.frames i hi).owned) →
out.scalar.integerMemory z=st.scalar.integerMemory z
indexFrame : ∀ v : Fin n,
out.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 7)=
st.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 7)
namespace PendingIntegerFrame
lemma trans {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ} {ell length : ℕ}
{logical : RecursiveState n} {st mid out : MachineState}
{old : MachinePendingKeys g s α ε ell length logical st}
{middle : MachinePendingKeys g s α ε ell length logical mid}
{next : MachinePendingKeys g s α ε ell length logical out}
(a : PendingIntegerFrame old middle) (b : PendingIntegerFrame middle next) : PendingIntegerFrame old next := by
refine ⟨a.free.trans b.free,?_,?_,fun v => (b.indexFrame v).trans (a.indexFrame v)⟩
· intro i hi z hz hBelow
exact a.oldOwned i hi z (b.oldOwned i hi z hz (hBelow.trans_le a.free)) hBelow
· intro z hz hBelow hOutside
have hMid : ∀ i, ∀ hi : i ≤ logical.top, z ∉ (middle.frames i hi).owned := by
intro i hi hm
exact hOutside i hi (a.oldOwned i hi z hm hBelow)
exact (b.integerFrame z hz (hBelow.trans_le a.free) hMid).trans (a.integerFrame z hz hBelow hOutside)
lemma frame {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ} {ell length : ℕ}
{logical : RecursiveState n} {st out : MachineState}
(pm : MachinePendingKeys g s α ε ell length logical st)
(hI : out.scalar.integerMemory=st.scalar.integerMemory) (hR : out.scalar.core.mem=st.scalar.core.mem)
(hP : ∀ r ∈ ([0,20,50,100] : List ℕ), out.scalar.core.ptrs r=st.scalar.core.ptrs r)
(hG : ∀ r ∈ ([30,31] : List ℕ), out.scalar.core.regs r=st.scalar.core.regs r)
(hO : out.output=st.output) : PendingIntegerFrame pm (pm.frame hI hR hP hG hO) := by
refine ⟨le_of_eq (hP 20 (by simp)).symm,?_,?_,fun v => congrFun hI _⟩
· intro i hi z hz hBelow
exact hz
· intro z hz hBelow hOutside
exact congrFun hI z
end PendingIntegerFrame
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.PendingVisitedKeys
set_option autoImplicit false
set_option maxRecDepth 10000
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
structure PendingVisitedKeys {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ} {ell length : ℕ}
{logical : RecursiveState n} {machine : MachineState}
(memory : MachinePendingKeys g s α ε ell length logical machine) (visited : Finset (Fin n)) : Prop where
boolean : ∀ j ≤ logical.top, HighBooleanRecords machine.scalar.integerMemory machine.scalar.core.mem (16*(ell+3)) (16*(j+1))
(logical.frames j).theta (parentDomain logical j ∩ visited)
exterior : ∀ j, ∀ hj : j ≤ logical.top, ∀ v ∈ visited, v ∈ (logical.frames j).exterior → v.val ∈ (memory.frames j hj).exteriorObject.keys
high : ∀ j, ∀ hj : j ≤ logical.top, ∀ v ∈ visited, v ∈ (logical.frames j).high → v.val ∈ (memory.frames j hj).highObject.keys
namespace PendingVisitedKeys
def frame {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ} {ell length : ℕ}
{logical : RecursiveState n} {st out : MachineState} {visited : Finset (Fin n)}
{pm : MachinePendingKeys g s α ε ell length logical st} (inv : PendingVisitedKeys pm visited)
(hI : out.scalar.integerMemory=st.scalar.integerMemory) (hR : out.scalar.core.mem=st.scalar.core.mem)
(hP : ∀ r ∈ ([0,20,50,100] : List ℕ), out.scalar.core.ptrs r=st.scalar.core.ptrs r)
(hG : ∀ r ∈ ([30,31] : List ℕ), out.scalar.core.regs r=st.scalar.core.regs r)
(hO : out.output=st.output) : PendingVisitedKeys (pm.frame hI hR hP hG hO) visited := by
refine ⟨?_,inv.exterior,inv.high⟩
rw [hI,hR]
exact inv.boolean
end PendingVisitedKeys
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.MemoryBufferFrame
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
noncomputable section
structure MemoryBufferFrame {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ}
{ell length : ℕ} {logical nextLogical : RecursiveState n} {st out : MachineState}
(old : RecursiveMachineMemory g s α ε ell length logical st)
(next : RecursiveMachineMemory g s α ε ell length nextLogical out) : Prop where
top : nextLogical.top=logical.top
free : st.scalar.core.ptrs 20 ≤ out.scalar.core.ptrs 20
oldOwned : ∀ i, ∀ hi : i ≤ logical.top, ∀ hn : i ≤ nextLogical.top,
∀ z ∈ (next.frames i hn).owned, z < st.scalar.core.ptrs 20 → z ∈ (old.frames i hi).owned
integerFrame : ∀ z, 0 ≤ z → z < st.scalar.core.ptrs 20 →
(∀ i, ∀ hi : i ≤ logical.top, z ∉ (old.frames i hi).owned) →
out.scalar.integerMemory z=st.scalar.integerMemory z
realPositive : ∀ z, 0 ≤ z → out.scalar.core.mem z=st.scalar.core.mem z
indexFrame : ∀ v : Fin n,
out.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 7)=
st.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 7)
namespace MemoryBufferFrame
lemma trans {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ} {ell length : ℕ}
{logical middleLogical nextLogical : RecursiveState n} {st mid out : MachineState}
{old : RecursiveMachineMemory g s α ε ell length logical st}
{middle : RecursiveMachineMemory g s α ε ell length middleLogical mid}
{next : RecursiveMachineMemory g s α ε ell length nextLogical out}
(a : MemoryBufferFrame old middle) (b : MemoryBufferFrame middle next) : MemoryBufferFrame old next := by
refine ⟨b.top.trans a.top,a.free.trans b.free,?_,?_,?_,fun v => (b.indexFrame v).trans (a.indexFrame v)⟩
· intro i hi hn z hz hBelow
have hm : i ≤ middleLogical.top := by rw [a.top]; exact hi
exact a.oldOwned i hi hm z (b.oldOwned i hm hn z hz (hBelow.trans_le a.free)) hBelow
· intro z hz hBelow hOutside
have hMid : ∀ i, ∀ hi : i ≤ middleLogical.top, z ∉ (middle.frames i hi).owned := by
intro i hi hOwned
have ho : i ≤ logical.top := by rw [←a.top]; exact hi
exact hOutside i ho (a.oldOwned i ho hi z hOwned hBelow)
exact (b.integerFrame z hz (hBelow.trans_le a.free) hMid).trans (a.integerFrame z hz hBelow hOutside)
· intro z hz
exact (b.realPositive z hz).trans (a.realPositive z hz)
lemma frame {n : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ} {ell length : ℕ}
{logical : RecursiveState n} {st out : MachineState}
(pm : RecursiveMachineMemory g s α ε ell length logical st)
(hI : out.scalar.integerMemory=st.scalar.integerMemory) (hR : out.scalar.core.mem=st.scalar.core.mem)
(hP : ∀ r ∈ ([0,20,50,100] : List ℕ), out.scalar.core.ptrs r=st.scalar.core.ptrs r)
(hG : ∀ r ∈ ([30,31] : List ℕ), out.scalar.core.regs r=st.scalar.core.regs r)
(hO : out.output=st.output) : MemoryBufferFrame pm (pm.frame hI hR hP hG hO) := by
refine ⟨rfl,le_of_eq (hP 20 (by simp)).symm,?_,?_,?_,fun v => congrFun hI _⟩
· intros i hi hn z hz hBelow
exact hz
· intros z hz hBelow hOutside
exact congrFun hI z
· intros z hz
exact congrFun hR z
end MemoryBufferFrame
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.KeyListPrependMemory
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
namespace SparseQueue
open Batteries.BinomialHeap.Imp
noncomputable section
def listPrependMemory (I : ℤ → ℤ) (free : ℤ) (key : ℕ) (head : ℤ) : ℤ → ℤ :=
Function.update (nodeAllocMemory I free key) (free+2) head
end
end SparseQueue
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.FrameListPrepend
set_option autoImplicit false
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
def frameListPrependMemory (I : ℤ → ℤ) (free : ℤ) (vertex level headSlot : ℕ) : ℤ → ℤ :=
Function.update (listPrependMemory I free vertex (I (levelHeaderAddress level headSlot)))
(levelHeaderAddress level headSlot) free
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.FrameListMetadata
set_option autoImplicit false
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
noncomputable section
def frameListMetadataMemory (I : ℤ → ℤ) (level cardSlot volumeSlot width vertex field : ℕ) (degree : ℤ) : ℤ → ℤ :=
Function.update (Function.update (Function.update I (levelHeaderAddress level cardSlot)
(I (levelHeaderAddress level cardSlot)+1)) (levelHeaderAddress level volumeSlot)
(I (levelHeaderAddress level volumeSlot)+degree)) (vertexRecordAddress width vertex (16*(level+1)+field)) 1
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.FrameListInsert
set_option autoImplicit false
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
def frameListInsertMemory (I : ℤ → ℤ) (free : ℤ) (vertex level headSlot cardSlot volumeSlot width field : ℕ)
(degree : ℤ) : ℤ → ℤ :=
frameListMetadataMemory (frameListPrependMemory I free vertex level headSlot)
level cardSlot volumeSlot width vertex field degree
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.SolveBufferAllocation
set_option autoImplicit false
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
structure SolveBufferLayout (st : LocalPush.State) (base : ℤ) (dimension capacity : ℕ) : Prop where
rows : st.core.ptrs 71=base
columns : st.core.ptrs 72=base+(capacity : ℤ)
values : st.core.ptrs 73=base+2*(capacity : ℤ)
rhs : st.core.ptrs 78=base+3*(capacity : ℤ)
answer : st.core.ptrs 79=base+3*(capacity : ℤ)+(dimension : ℤ)
free : st.core.ptrs 20=base+3*(capacity : ℤ)+2*(dimension : ℤ)
dimensionPointer : st.core.ptrs 77=(dimension : ℤ)
capacityPointer : st.core.ptrs 82=(capacity : ℤ)
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.SolveIterationBuffers
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
noncomputable section
structure SolveIterationBuffers {n k : ℕ} {g : InputGraph n} {s : Fin n} {α ε : ℝ} {ell length : ℕ}
{logical : RecursiveState n} {machine : MachineState}
(memory : RecursiveMachineMemory g s α ε ell length logical machine)
(enumBase answerBase : ℤ) (e : Fin k → Fin n) (h : Fin n → ℝ) : Prop where
enumNonnegative : 0 ≤ enumBase
answerNonnegative : 0 ≤ answerBase
enumBelow : ∀ i : Fin k, enumBase+(i.val : ℤ) < machine.scalar.core.ptrs 20
answerBelow : ∀ i : Fin k, answerBase+(i.val : ℤ) < machine.scalar.core.ptrs 20
enumForeign : ∀ i : Fin k, ∀ j, ∀ hj : j ≤ logical.top, enumBase+(i.val : ℤ) ∉ (memory.frames j hj).owned
enumeration : EnumerationStored machine.scalar.integerMemory enumBase e
answers : ∀ i : Fin k, machine.scalar.core.mem (answerBase+(i.val : ℤ))=h (e i)
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.ExteriorSelfBudget
set_option autoImplicit false
set_option maxRecDepth 10000
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
noncomputable section
def exteriorSelfBudgetMemoryUpdate (I : ℤ → ℤ) (width : ℕ) (vertex : ℕ) (t : ℕ)
(z flow : ℝ) (i : ℕ) (R : ℤ → ℝ) : ℤ → ℝ :=
let self := if i ≤ t then Function.update R (vertexRecordAddress width vertex (16*(i+1)+1))
(R (vertexRecordAddress width vertex (16*(i+1)+1))+(if i < t then -z else -5*z)) else R
if t ≤ i ∧ 0 < I (levelHeaderAddress i 9) then
Function.update self (levelHeaderAddress i 4) (self (levelHeaderAddress i 4)+flow) else self
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.DomainResidualBody
set_option autoImplicit false
set_option maxRecDepth 10000
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
noncomputable section
def domainResidualMemoryUpdate {n : ℕ} (logical : RecursiveState n) (width : ℕ) (v : Fin n)
(delta : ℝ) (i : ℕ) (R : ℤ → ℝ) : ℤ → ℝ :=
if v ∈ parentDomain logical i then Function.update R (vertexRecordAddress width v.val (16*(i+1)+1))
(R (vertexRecordAddress width v.val (16*(i+1)+1))+delta) else R
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.StoredNeighborBody
set_option autoImplicit false
set_option maxRecDepth 10000
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
noncomputable section
def storedNeighborVertex {n : ℕ} (g : InputGraph n) (source : Fin n) (i : ℕ) : Fin n :=
((g.neighbors source)[i]?).getD source
def storedNeighborMemoryUpdate {n : ℕ} (g : InputGraph n) (source : Fin n)
(logical : RecursiveState n) (ell : ℕ) (delta : ℝ) (i : ℕ) (payload : (ℤ → ℤ) × (ℤ → ℝ)) :
(ℤ → ℤ) × (ℤ → ℝ) :=
let v := storedNeighborVertex g source i
(Function.update payload.1 (vertexRecordAddress (16*(ell+3)) v.val 0) ((g.neighbors v).length : ℤ),
levelRealMemoryFold (domainResidualMemoryUpdate logical (16*(ell+3)) v delta) 0 (logical.top+1) payload.2)
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.ActivationBoundary
set_option autoImplicit false
set_option maxRecDepth 10000
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
noncomputable section
def activationBoundaryMemory {n : ℕ} (g : InputGraph n) (source : Fin n) (active : Finset (Fin n))
(boundary level : ℕ) (I : ℤ → ℤ) : ℤ → ℤ :=
if level=0 then Function.update I 7
((boundary+(g.neighbors source).length-2*((g.neighbors source).filter (fun v => v ∈ active)).length : ℕ) : ℤ) else I
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.ActivationScalars
set_option autoImplicit false
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
noncomputable section
def activationScalarsMemory (R : ℤ → ℝ) (width vertex level : ℕ) (half : ℝ) (opened : Bool) : ℤ → ℝ :=
Function.update (Function.update R (vertexRecordAddress width vertex (16*(level+1)+1))
(R (vertexRecordAddress width vertex (16*(level+1)+1))+half)) (levelHeaderAddress level 4)
(R (levelHeaderAddress level 4)+(if opened then ((level+3 : ℕ) : ℝ)*half else 0))
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.LevelVertexFlagsClear
set_option autoImplicit false
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
noncomputable section
def clearLevelVertexFlagsMemory (I : ℤ → ℤ) (width vertex base : ℕ) (offsets : List ℕ) : ℤ → ℤ :=
offsets.foldl (fun J offset => Function.update J (vertexRecordAddress width vertex (base+offset)) 0) I
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.FreshVertexExecution
set_option autoImplicit false
set_option maxRecDepth 10000
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
def freshVertexRealMemory (R : ℤ → ℝ) (width vertex parent : ℕ) : ℤ → ℝ :=
Function.update (Function.update (Function.update R (vertexRecordAddress width vertex (parent+16))
(R (vertexRecordAddress width vertex 0))) (vertexRecordAddress width vertex (parent+17))
(R (vertexRecordAddress width vertex (parent+1)))) (vertexRecordAddress width vertex (parent+20)) 0
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.ExteriorNumericMemory
set_option autoImplicit false
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
def exteriorNumericPayload {n : ℕ} (g : InputGraph n) (logical : RecursiveState n) (ell : ℕ)
(α : ℝ) (t : ℕ) (v : Fin n) (δ : ℝ) (I : ℤ → ℤ) (R : ℤ → ℝ) : (ℤ → ℤ) × (ℤ → ℝ) :=
levelPayloadFold (storedNeighborMemoryUpdate g v logical ell ((1-α)*δ)) 0 (g.neighbors v).length
(I,levelRealMemoryFold (exteriorSelfBudgetMemoryUpdate I (16*(ell+3)) v.val t (LocalPush.deg g.graph v*δ)
((1-α)*LocalPush.deg g.graph v*δ)) 0 (logical.top+1)
(Function.update R (vertexRecordAddress (16*(ell+3)) v.val 0) (R (vertexRecordAddress (16*(ell+3)) v.val 0)+δ)))
end
end NearlyOptimalPPR.Computation
-- Buffer and update interface from Solutions.ExteriorActivationExecution
set_option autoImplicit false
set_option maxRecDepth 10000
open scoped ENNReal
namespace NearlyOptimalPPR.Computation
open SparseQueue
noncomputable section
def exteriorActivationIntegerMemory {n : ℕ} (g : InputGraph n) (source : Fin n) (rootActive : Finset (Fin n))
(boundary level top width : ℕ) (free : ℤ) (I : ℤ → ℤ) : ℤ → ℤ :=
let base := frameListInsertMemory (activationBoundaryMemory g source rootActive boundary level I)
free source.val level 1 3 2 width 2 ((g.neighbors source).length : ℤ)
if level < top then clearLevelVertexFlagsMemory base width source.val (16*(level+1)+16) [2,3,4,5,6] else base
def exteriorActivationRealMemory (R : ℤ → ℝ) (source level top width : ℕ) (half : ℝ) (opened : Bool) : ℤ → ℝ :=
let base := activationScalarsMemory R width source level half opened
if level < top then freshVertexRealMemory base width source (16*(level+1)) else base
end
end NearlyOptimalPPR.Computation
Source
Li, Xu, Yang, Zhou, Nearly optimal Personalized PageRank computation, STOC 2027 submission #884, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/884.pdf, Algorithms 6–9, pp.14–22; sparse buffer and memory-frame realization in the charged exact-SDDM local-machine model.