threshold-computers / rocq /Schedule.v
phanerozoic's picture
Put the organism first and move serialization, sizes and the Rocq map to appendices
5ee1fb5
Raw History Blame Contribute Delete
13.4 kB
(* Lemma 3.3. A pass of records that read and write the window alone, held in the active bank and followed by empty
slots, runs them in order on the window. The records of a clocked netlist of units of at most two inputs, one for
each unit in the order of the netlist, each writing a cell that holds the unit's value until the last record that
reads it, and the record of each next value writing its state bit after every record that reads the bit, leave the
next state in the cells of the state bits after one pass. *)
From Stdlib Require Import List Bool Arith ZArith Lia.
Import ListNotations.
From TH Require Import TwoHead Net Abstract Indep Run View Stored WinRun StoredBoot.
(* ---- a pass of window records ------------------------------------------------------------------------------------ *)
Lemma wrec_empty : wrec EMPTY.
Proof. unfold wrec, EMPTY. auto. Qed.
Lemma rec_ok_empty : forall al, rec_ok al EMPTY.
Proof. intro al. pose proof (Nat.pow_nonzero 2 al ltac:(lia)). unfold rec_ok, EMPTY. lia. Qed.
Lemma wrun_empty : forall p w, wrun (repeat EMPTY p) w = w.
Proof. induction p as [|p IH]; intro w; [reflexivity|]. cbn [repeat wrun]. unfold wexec. cbn [ao_of EMPTY]. apply IH. Qed.
Lemma Forall_prefix : forall (T : Type) (P : T -> Prop) l j, Forall P l -> Forall P (firstn j l).
Proof. intros T P l j H. rewrite <- (firstn_skipn j l) in H. apply Forall_app in H. exact (proj1 H). Qed.
Section Pass.
Variables (al K S0 L : nat) (s0 : st) (rs : list rec).
Hypotheses (Hal : 4 <= al) (HK : 2 <= K) (HS : 1 <= S0) (HL : 1 <= L) (Hfit : fits al K S0 L s0)
(Hbank : bq (nth (kap s0) (banks s0) bank0) = encA al (rs ++ repeat EMPTY (S0 - length rs)))
(Hslot : bs (nth (kap s0) (banks s0) bank0) = 0) (Hlen : length rs <= S0)
(Hok : Forall (rec_ok al) rs) (Hw : Forall wrec rs) (Hq : reqclear (win s0)).
Let pad : list rec := rs ++ repeat EMPTY (S0 - length rs).
Lemma pad_len : length pad = S0.
Proof. unfold pad. rewrite length_app, repeat_length. lia. Qed.
Lemma pad_wrec : Forall wrec pad.
Proof.
unfold pad. apply Forall_app. split; [exact Hw|]. apply Forall_forall. intros r Hr. apply repeat_spec in Hr. subst r.
exact wrec_empty.
Qed.
(* the S0 steps of a pass are the records of the bank run in order on the window; the heads and the bank index stay *)
Theorem pass_run :
View.mv al K S0 L s0 S0 (itern al K S0 L S0 s0)
(mkV (wrun rs (win s0)) (vr (view0 al K s0)) (va (view0 al K s0)) (vc (view0 al K s0)) false).
Proof.
assert (Hq0 : reqclear (vw (view0 al K s0))) by exact Hq.
assert (Hok' : Forall (rec_ok al) pad).
{ unfold pad. apply Forall_app. split; [exact Hok|]. apply Forall_forall. intros r Hr. apply repeat_spec in Hr.
subst r. apply rec_ok_empty. }
assert (Hho : forall j, 1 <= j < length pad -> vho (vrun (S0 * recw al) L (firstn j pad) (view0 al K s0)) = false).
{ intros j _. rewrite (vrun_wrun _ _ _ _ (Forall_prefix _ _ _ j pad_wrec) Hq0). reflexivity. }
pose proof (seg_run al K S0 L s0 Hal HK HS HL Hfit pad [] ltac:(rewrite app_nil_r; exact Hbank) Hslot
ltac:(rewrite pad_len; lia) Hok' Hho S0 ltac:(rewrite pad_len; lia)) as M.
rewrite firstn_all2 in M by (rewrite pad_len; lia).
rewrite (vrun_wrun _ _ _ _ pad_wrec Hq0) in M. unfold pad in M. rewrite wrun_app, wrun_empty in M. exact M.
Qed.
End Pass.
(* ---- the records of a netlist ----------------------------------------------------------------------------------- *)
Section Sched.
(* the n state bits in the cells sc i, unit k writing cell oc k *)
Variables (n : nat) (us : list tu) (sc oc : nat -> nat).
(* the cell of a signal: a state bit has its own, a unit's value is in the cell its record writes *)
Definition scell (p : nat) : nat := if p <? n then sc p else oc (p - n).
(* the record of unit k: its inputs by their cells, the empty places reading the sink with weight 0 *)
Definition rec_of (k : nat) (u : tu) : rec :=
match tin u with
| [] => Rec SINK 0 SINK 0 (Net.tb u) (oc k)
| [(p, z)] => Rec (scell p) z SINK 0 (Net.tb u) (oc k)
| (p0, z0) :: (p1, z1) :: _ => Rec (scell p0) z0 (scell p1) z1 (Net.tb u) (oc k)
end.
Definition net_recs : list rec := map (fun k => rec_of k (nth k us tu0)) (seq 0 (length us)).
(* the last of the first m records that writes cell c *)
Fixpoint lastw (m c : nat) : option nat :=
match m with O => None | S m' => if Nat.eqb (oc m') c then Some m' else lastw m' c end.
Variable w0 : list bool.
Hypotheses
(Hrb : forall k, k < length us -> reads_below (nth k us tu0) (n + k))
(Hsc : forall i, i < n -> HO < sc i < length w0)
(Hoc : forall k, k < length us -> HO < oc k < length w0).
(* the state the window holds, and the values of the netlist on it *)
Definition x0 : list bool := map (fun i => wget w0 (sc i)) (seq 0 n).
Definition E0 : nat -> bool := run us n (fun i => nth i x0 false).
(* the records read and write the window alone *)
Theorem net_recs_wrec : Forall wrec net_recs.
Proof.
apply Forall_forall. intros r Hr. unfold net_recs in Hr. apply in_map_iff in Hr as (k & <- & Hk). apply in_seq in Hk.
assert (Hc : forall p, p < n + k -> CPY < scell p).
{ intros p Hp. unfold scell. destruct (Nat.ltb_spec p n); [pose proof (Hsc p ltac:(lia)) | pose proof (Hoc (p - n) ltac:(lia))];
unfold CPY, HO in *; lia. }
pose proof (Hoc k ltac:(lia)) as Ho. pose proof (Hrb k ltac:(lia)) as Hb.
unfold rec_of. destruct (tin (nth k us tu0)) as [|[p0 z0] [|[p1 z1] t]] eqn:Et; unfold wrec.
- split; [auto|]. split; [auto | right; lia].
- split; [right; right; apply Hc; apply (Hb p0 z0); rewrite Et; left; reflexivity|]. split; [auto | right; lia].
- split; [right; right; apply Hc; apply (Hb p0 z0); rewrite Et; left; reflexivity|].
split; [right; right; apply Hc; apply (Hb p1 z1); rewrite Et; right; left; reflexivity | right; lia].
Qed.
(* they fit the code of the records when the weights are 1 and -1, the biases lie in [-8, 7] and the cells in 2^al *)
Theorem net_recs_ok : forall al, length w0 = 2 ^ al ->
(forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> z = 1%Z \/ z = (-1)%Z) ->
(forall k, k < length us -> (-8 <= Net.tb (nth k us tu0) <= 7)%Z) -> Forall (rec_ok al) net_recs.
Proof.
intros al HW Hz Hbias. apply Forall_forall. intros r Hr. unfold net_recs in Hr.
apply in_map_iff in Hr as (k & <- & Hk). apply in_seq in Hk.
assert (Hc : forall p, p < n + k -> scell p < 2 ^ al).
{ intros p Hp. unfold scell. destruct (Nat.ltb_spec p n); [pose proof (Hsc p ltac:(lia)) | pose proof (Hoc (p - n) ltac:(lia))];
lia. }
pose proof (Hoc k ltac:(lia)) as Ho. pose proof (Hrb k ltac:(lia)) as Hb. pose proof (Hbias k ltac:(lia)) as Hbs.
pose proof (Nat.pow_nonzero 2 al ltac:(lia)) as Hp2.
unfold rec_of. destruct (tin (nth k us tu0)) as [|[p0 z0] [|[p1 z1] t]] eqn:Et; unfold rec_ok, SINK.
- lia.
- assert (H0 : In (p0, z0) (tin (nth k us tu0))) by (rewrite Et; left; reflexivity).
pose proof (Hz k p0 z0 ltac:(lia) H0). pose proof (Hc p0 (Hb p0 z0 H0)). lia.
- assert (H0 : In (p0, z0) (tin (nth k us tu0))) by (rewrite Et; left; reflexivity).
assert (H1 : In (p1, z1) (tin (nth k us tu0))) by (rewrite Et; right; left; reflexivity).
pose proof (Hz k p0 z0 ltac:(lia) H0). pose proof (Hz k p1 z1 ltac:(lia) H1).
pose proof (Hc p0 (Hb p0 z0 H0)). pose proof (Hc p1 (Hb p1 z1 H1)). lia.
Qed.
Hypotheses
(Hfan : forall k, k < length us -> length (tin (nth k us tu0)) <= 2)
(* the cell of a unit's value holds it until every record that reads it *)
(Hunit : forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> n <= p -> lastw k (oc (p - n)) = Some (p - n))
(* the cell of a state bit is not written before a record that reads the bit *)
(Hbit : forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> p < n -> lastw k (sc p) = None).
Lemma wval_rec : forall k u w, length (tin u) <= 2 -> (forall p z, In (p, z) (tin u) -> wcell w (scell p) = E0 p) ->
wval w (rec_of k u) = fire u E0.
Proof.
intros k u w Hl H. unfold rec_of, fire. destruct (tin u) as [|[p0 z0] [|[p1 z1] t]] eqn:Et; cbn [length] in Hl.
- cbn [wval wsum]. f_equal. lia.
- cbn [wval wsum]. rewrite (H p0 z0 (or_introl eq_refl)). f_equal. lia.
- destruct t as [|? ?]; [|cbn [length] in Hl; lia]. cbn [wval wsum].
rewrite (H p0 z0 (or_introl eq_refl)), (H p1 z1 (or_intror (or_introl eq_refl))). f_equal. lia.
Qed.
Lemma net_recs_nth : forall k, k < length us -> nth_error net_recs k = Some (rec_of k (nth k us tu0)).
Proof.
intros k Hk. unfold net_recs. rewrite nth_error_map, nth_error_seq.
destruct (Nat.ltb_spec k (length us)); [reflexivity | lia].
Qed.
(* after the first m records every cell holds the value of the last record that wrote it, or its first value *)
Lemma sched_inv : forall m, m <= length us -> forall c,
wget (wrun (firstn m net_recs) w0) c = match lastw m c with Some k => E0 (n + k) | None => wget w0 c end.
Proof.
induction m as [|m IH]; intros Hm c; [reflexivity|].
rewrite (firstn_S_nth _ m _ (net_recs_nth m ltac:(lia))), wrun_app. cbn [wrun]. unfold wexec.
set (w := wrun (firstn m net_recs) w0).
assert (Hlw : length w = length w0) by apply length_wrun.
assert (Hao : ao_of (rec_of m (nth m us tu0)) = oc m) by (unfold rec_of; destruct (tin _) as [|[? ?] [|[? ?] ?]]; reflexivity).
rewrite Hao, wget_wnext by (pose proof (Hoc m ltac:(lia)); lia).
cbn [lastw]. rewrite (Nat.eqb_sym c (oc m)). destruct (Nat.eqb_spec (oc m) c) as [Ec|Ec]; [|apply IH; lia].
unfold E0. rewrite run_at by (lia || exact Hrb). apply wval_rec; [apply Hfan; lia|].
intros p z Hin. pose proof (Hrb m ltac:(lia) p z Hin) as Hp.
unfold scell, wcell. destruct (Nat.ltb_spec p n) as [Hpn|Hpn].
- pose proof (Hsc p Hpn) as Hs. replace (Nat.eqb (sc p) SINK) with false by (symmetry; apply Nat.eqb_neq; unfold SINK, HO in *; lia).
unfold w. rewrite (IH ltac:(lia)), (Hbit m p z ltac:(lia) Hin Hpn). unfold E0. rewrite run_prefix by exact Hpn.
unfold x0. rewrite (nth_map_seq _ (fun i => wget w0 (sc i)) n p false Hpn). reflexivity.
- pose proof (Hoc (p - n) ltac:(lia)) as Ho.
replace (Nat.eqb (oc (p - n)) SINK) with false by (symmetry; apply Nat.eqb_neq; unfold SINK, HO in *; lia).
unfold w. rewrite (IH ltac:(lia)), (Hunit m p z ltac:(lia) Hin Hpn). f_equal. lia.
Qed.
(* the cell of each state bit is written last by the unit of its next value *)
Variable nx : list nat.
Hypotheses (Hnx : length nx = n)
(Hnext : forall i, i < n -> exists k, nth i nx 0 = n + k /\ lastw (length us) (sc i) = Some k).
(* one run of the records leaves the next state of the netlist in the cells of the state bits *)
Theorem sched_run : forall i, i < n -> wget (wrun net_recs w0) (sc i) = nth i (netstep n us nx x0) false.
Proof.
intros i Hi. assert (Hl : length net_recs = length us) by (unfold net_recs; rewrite length_map, length_seq; reflexivity).
rewrite <- (firstn_all2 net_recs (le_n _)), Hl, (sched_inv (length us) (le_n _)).
destruct (Hnext i Hi) as (k & Ek & Lk). rewrite Lk.
unfold netstep. cbv zeta. rewrite (nth_map_d _ _ _ nx i false 0) by lia. rewrite Ek. reflexivity.
Qed.
End Sched.
(* ---- Lemma 3.3: one pass of the records of a netlist evaluates it ------------------------------------------------- *)
Theorem netlist_pass : forall al K S0 L s0 n us nx sc oc,
4 <= al -> 2 <= K -> 1 <= S0 -> 1 <= L -> fits al K S0 L s0 ->
let rs := net_recs n us sc oc in
bq (nth (kap s0) (banks s0) bank0) = encA al (rs ++ repeat EMPTY (S0 - length rs)) ->
bs (nth (kap s0) (banks s0) bank0) = 0 -> length us <= S0 -> reqclear (win s0) ->
(forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> z = 1%Z \/ z = (-1)%Z) ->
(forall k, k < length us -> (-8 <= Net.tb (nth k us tu0) <= 7)%Z) ->
(forall k, k < length us -> length (tin (nth k us tu0)) <= 2) ->
(forall k, k < length us -> reads_below (nth k us tu0) (n + k)) ->
(forall i, i < n -> HO < sc i < 2 ^ al) -> (forall k, k < length us -> HO < oc k < 2 ^ al) ->
(forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> n <= p -> lastw oc k (oc (p - n)) = Some (p - n)) ->
(forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> p < n -> lastw oc k (sc p) = None) ->
length nx = n -> (forall i, i < n -> exists k, nth i nx 0 = n + k /\ lastw oc (length us) (sc i) = Some k) ->
let s := itern al K S0 L S0 s0 in
(forall i, i < n -> wget (win s) (sc i) = nth i (netstep n us nx (x0 n sc (win s0))) false)
/\ View.mv al K S0 L s0 S0 s
(mkV (win s) (vr (view0 al K s0)) (va (view0 al K s0)) (vc (view0 al K s0)) false).
Proof.
intros al K S0 L s0 n us nx sc oc Hal HK HS HL Hfit rs Hbank Hslot Hlen Hq Hz Hbias Hfan Hrb Hsc Hoc Hunit Hbit
Hnx Hnext s.
assert (HW : length (win s0) = 2 ^ al) by (destruct Hfit; assumption).
assert (Hlr : length rs = length us) by (unfold rs, net_recs; rewrite length_map, length_seq; reflexivity).
rewrite <- HW in Hsc, Hoc.
pose proof (pass_run al K S0 L s0 rs Hal HK HS HL Hfit Hbank Hslot ltac:(lia)
(net_recs_ok n us sc oc (win s0) Hrb Hsc Hoc al HW Hz Hbias)
(net_recs_wrec n us sc oc (win s0) Hrb Hsc Hoc) Hq) as M.
fold s in M.
assert (Ew : win s = wrun rs (win s0)) by (destruct M as (_ & E & _); exact E).
split.
- intros i Hi. rewrite Ew. exact (sched_run n us sc oc (win s0) Hrb Hsc Hoc Hfan Hunit Hbit nx Hnx Hnext i Hi).
- rewrite Ew. exact M.
Qed.