UmutAcarLab · colin-mcd · Nov 8, 2023 · Nov 8, 2023 · Nov 8, 2023 · Nov 13, 2023
diff --git a/feynsum-sml/run.sh b/feynsum-sml/run.sh
@@ -1,5 +1,5 @@
-./main.mpl @mpl procs 72 set-affinity megablock-threshold 14 cc-threshold-ratio 1.1 collection-threshold-ratio 2.0 max-cc-depth 1 -- -scheduler gfq -input $@
-# cc-threshold-ratio 1.1 collection-threshold-ratio 2.0 
-
-
-# ./all-main.mpl @mpl procs 72 set-affinity megablock-threshold 14 cc-threshold-ratio 1.25 max-cc-depth 1 -- -sim query-bfs -input $@
+./main.mpl @mpl procs 20 set-affinity megablock-threshold 14 cc-threshold-ratio 1.1 collection-threshold-ratio 2.0 max-cc-depth 1 -- -dense-thresh 1.1 --scheduler-disable-fusion -scheduler $1 -input $2
+# -scheduler-max-branching-stride 1
+#  --scheduler-disable-fusion
+# -dense-thresh 0.75
+# -pull-thresh 0.01
diff --git a/feynsum-sml/src/FullSimBFS.sml b/feynsum-sml/src/FullSimBFS.sml
@@ -1,38 +1,36 @@
 functor FullSimBFS
   (structure B: BASIS_IDX
    structure C: COMPLEX
-   structure SST: SPARSE_STATE_TABLE
+   structure HS: HYBRID_STATE
    structure G: GATE
-   sharing B = SST.B = G.B
-   sharing C = SST.C = G.C
+   sharing B = HS.B = G.B
+   sharing C = HS.C = G.C
 
+   val disableFusion: bool
+   val maxBranchingStride: int
+   val gateScheduler: string
    val blockSize: int
    val maxload: real
-   val gateScheduler: GateScheduler.t
    val doMeasureZeros: bool
    val denseThreshold: real
    val pullThreshold: real):
 sig
-  val run: Circuit.t
+  val run: DataFlowGraph.t
            -> {result: (B.t * C.t) option DelayedSeq.t, counts: int Seq.t}
 end =
 struct
 
-  structure DS = DenseState (structure C = C structure B = B)
-
   structure Expander =
     ExpandState
       (structure B = B
        structure C = C
-       structure SST = SST
-       structure DS = DS
+       structure HS = HS
        structure G = G
        val denseThreshold = denseThreshold
        val blockSize = blockSize
        val maxload = maxload
        val pullThreshold = pullThreshold)
 
-
   val bits = Seq.fromList [ (*"▏",*)"▎", "▍", "▌", "▊"]
 
   fun fillBar width x =
@@ -61,9 +59,9 @@ struct
     let
       val ss =
         case s of
-          Expander.Sparse sst => SST.unsafeViewContents sst
-        | Expander.Dense ds => DS.unsafeViewContents ds
-        | Expander.DenseKnownNonZeroSize (ds, _) => DS.unsafeViewContents ds
+          HS.Sparse sst => HS.SST.unsafeViewContents sst
+        | HS.Dense ds => HS.DS.unsafeViewContents ds
+        | HS.DenseKnownNonZeroSize (ds, _) => HS.DS.unsafeViewContents ds
     in
       Util.for (0, DelayedSeq.length ss) (fn i =>
         case DelayedSeq.nth ss i of
@@ -76,22 +74,45 @@ struct
             end)
     end
 
-
-  fun run {numQubits, gates} =
+  structure DGFQ = DynSchedFinishQubitWrapper
+                     (structure B = B
+                      structure C = C
+                      structure HS = HS
+                      val maxBranchingStride = maxBranchingStride
+                      val disableFusion = disableFusion)
+
+  structure DGI = DynSchedInterference
+                    (structure B = B
+                     structure C = C
+                     structure HS = HS
+                     val maxBranchingStride = maxBranchingStride
+                     val disableFusion = disableFusion)
+  structure DGN = DynSchedNaive
+                    (structure B = B
+                     structure C = C
+                     structure HS = HS
+                     val maxBranchingStride = maxBranchingStride
+                     val disableFusion = disableFusion)
+
+  val gateSched =
+      case gateScheduler of
+          "naive" => DGN.choose
+        | "gfq" => DGFQ.choose
+        | "interference" => DGI.choose
+        | _ => raise Fail ("Unknown scheduler '" ^ gateScheduler ^ "'\n")
+
+  fun run dfg (*{numQubits, gates}*) =
     let
-      val gates = Seq.map G.fromGateDefn gates
+      val gates = Seq.map G.fromGateDefn (#gates dfg)
+      val numQubits = #numQubits dfg
       fun gate i = Seq.nth gates i
       val depth = Seq.length gates
+      val dgstate = DataFlowGraphUtil.initState dfg
 
-      val gateSchedulerPickNextGates = gateScheduler
-        { numQubits = numQubits
-        , numGates = depth
-        , gateTouches = #touches o gate
-        , gateIsBranching = (fn i =>
-            case #action (gate i) of
-              G.NonBranching _ => false
-            | _ => true)
-        }
+      val pickNextGate =
+          let val f = gateSched dfg in
+            fn (s, g) => f (s, g)
+          end
 
       (* val _ =
         if numQubits > 63 then raise Fail "whoops, too many qubits" else () *)
@@ -134,77 +155,74 @@ struct
           density
         end
 
-
-      fun loop numGateApps gatesVisitedSoFar counts prevNonZeroSize state =
-        if gatesVisitedSoFar >= depth then
-          let
-            val (nonZeros, numNonZeros) =
-              case state of
-                Expander.Sparse sst =>
-                  (SST.unsafeViewContents sst, SST.nonZeroSize sst)
-              | Expander.Dense ds =>
-                  (DS.unsafeViewContents ds, DS.nonZeroSize ds)
-              | Expander.DenseKnownNonZeroSize (ds, nz) =>
-                  (DS.unsafeViewContents ds, nz)
-
-            (* val _ = dumpState numQubits state *)
-
-            val density =
-              dumpDensity (gatesVisitedSoFar, numNonZeros, NONE, NONE)
-          in
-            print "\n";
-            (numGateApps, nonZeros, Seq.fromRevList (numNonZeros :: counts))
-          end
-
-        else
-          let
-            (* val _ = dumpState numQubits state *)
-
-            val theseGates = gateSchedulerPickNextGates ()
-            val _ =
-              if Seq.length theseGates > 0 then
-                ()
-              else
-                raise Fail "FullSimBFS: gate scheduler returned empty sequence"
-
-            (* val _ = print
-              ("visiting: " ^ Seq.toString Int.toString theseGates ^ "\n") *)
-
-            val theseGates = Seq.map (Seq.nth gates) theseGates
-            val numGatesVisitedHere = Seq.length theseGates
-            val ({result, method, numNonZeros, numGateApps = apps}, tm) =
-              Util.getTime (fn () =>
-                Expander.expand
-                  { gates = theseGates
-                  , numQubits = numQubits
-                  , maxNumStates = maxNumStates
-                  , state = state
-                  , prevNonZeroSize = prevNonZeroSize
-                  })
-
-            val seconds = Time.toReal tm
-            val millions = Real.fromInt apps / 1e6
-            val throughput = millions / seconds
-            val throughputStr = Real.fmt (StringCvt.FIX (SOME 2)) throughput
-            val density =
-              dumpDensity (gatesVisitedSoFar, numNonZeros, NONE, NONE)
-            val _ = print
-              (" hop " ^ leftPad 3 (Int.toString numGatesVisitedHere) ^ " "
-               ^ rightPad 11 method ^ " "
-               ^ Real.fmt (StringCvt.FIX (SOME 4)) seconds ^ "s throughput "
-               ^ throughputStr ^ "\n")
-          in
-            loop (numGateApps + apps) (gatesVisitedSoFar + numGatesVisitedHere)
-              (numNonZeros :: counts) numNonZeros result
-          end
-
-
-      val initialState = Expander.Sparse
-        (SST.singleton {numQubits = numQubits} (B.zeros, C.defaultReal 1.0))
-
-      val (numGateApps, finalState, counts) = loop 0 0 [] 1 initialState
+      fun getNumZeros state =
+          case state of
+              HS.Sparse sst => HS.SST.zeroSize sst
+            | HS.Dense ds => 0 (*raise Fail "Can't do dense stuff!"*)
+              (*DS.unsafeViewContents ds, DS.nonZeroSize ds, TODO exception*)
+            | HS.DenseKnownNonZeroSize (ds, nz) => 0 (*raise Fail "Can't do dense stuff!"*)
              (*DS.unsafeViewContents ds, nz, TODO exception*)
+
+      val initialState = HS.Sparse
+        (HS.SST.singleton {numQubits = numQubits} (B.zeros, C.defaultReal 1.0))
+
+      fun runloop () =
+          DataFlowGraphUtil.scheduleWithOracle'
+
+            (* data flow graph *)
+            dfg
+
+            (* gate is branching *)
+            (fn i => G.expectBranching (Seq.nth gates i))
+
+            (* select gate *)
+            (fn ((state, numGateApps, counts, gatesVisitedSoFar), gates) => pickNextGate (state, gates))
+
+            (* disable fusion? *)
+            disableFusion
+
+            (* if fusion enabled, what's the max # of branching gates to fuse? *)
+            maxBranchingStride
+
+            (* apply gate fusion seq, updating state *)
+            (fn ((state, numGateApps, counts, gatesVisitedSoFar), theseGates) =>
+                let val numGatesVisitedHere = Seq.length theseGates
+                    val ({result, method, numNonZeros, numGateApps = apps}, tm) =
+                        Util.getTime (fn () =>
+                                         Expander.expand
+                                           { gates = Seq.map (Seq.nth gates) theseGates
+                                           , numQubits = numQubits
+                                           , maxNumStates = maxNumStates
+                                           , state = state
+                                           , prevNonZeroSize = (case counts of h :: t => h | nil => 1)
+                                     })
+
+                    val seconds = Time.toReal tm
+                    val millions = Real.fromInt apps / 1e6
+                    val throughput = millions / seconds
+                    val throughputStr = Real.fmt (StringCvt.FIX (SOME 2)) throughput
+                    val density =
+                        dumpDensity (gatesVisitedSoFar, numNonZeros, SOME (getNumZeros state), NONE)
+                    val _ = print
+                              (" hop " ^ leftPad 3 (Int.toString numGatesVisitedHere) ^ " "
+                               ^ rightPad 11 method ^ " "
+                               ^ Real.fmt (StringCvt.FIX (SOME 4)) seconds ^ "s throughput "
+                               ^ throughputStr ^ "\n")
+                in
+                  (result, numGateApps + apps, numNonZeros :: counts, gatesVisitedSoFar + numGatesVisitedHere)
+                end
+            )
+
+            (* initial state *)
+            (initialState, 0, [], 0)
+
+      val (finalState, numGateApps, counts, gatesVisited) = runloop ()
+      val nonZeros = case finalState of
+                       HS.Sparse sst => HS.SST.unsafeViewContents sst
+                     | HS.Dense ds => HS.DS.unsafeViewContents ds
+                     | HS.DenseKnownNonZeroSize (ds, nz) => HS.DS.unsafeViewContents ds
       val _ = print ("gate app count " ^ Int.toString numGateApps ^ "\n")
     in
-      {result = finalState, counts = counts}
+      {result = nonZeros, counts = Seq.fromList counts}
     end
 end
diff --git a/feynsum-sml/src/MkMain.sml b/feynsum-sml/src/MkMain.sml
@@ -1,9 +1,11 @@
 functor MkMain
   (structure C: COMPLEX
    structure B: BASIS_IDX
+   val disableFusion: bool
+   val maxBranchingStride: int
    val blockSize: int
    val maxload: real
-   val gateScheduler: GateScheduler.t
+   val gateScheduler: string
    val doMeasureZeros: bool
    val denseThreshold: real
    val pullThreshold: real) =
@@ -13,13 +15,26 @@ struct
 
   structure G = Gate (structure B = B structure C = C)
 
+  structure SSTLocked = SparseStateTableLockedSlots (structure B = B structure C = C)
+  structure SSTLockFree = SparseStateTable (structure B = B structure C = C)
+  structure DS = DenseState (structure B = B structure C = C)
+  structure HSLocked = HybridState (structure B = B
+                                    structure C = C
+                                    structure SST = SSTLocked
+                                    structure DS = DS)
+  structure HSLockFree = HybridState (structure B = B
+                                      structure C = C
+                                      structure SST = SSTLockFree
+                                      structure DS = DS)
+
   structure BFSLocked =
     FullSimBFS
       (structure B = B
        structure C = C
-       structure SST =
-         SparseStateTableLockedSlots (structure B = B structure C = C)
+       structure HS = HSLocked
        structure G = G
+       val disableFusion = disableFusion
+       val maxBranchingStride = maxBranchingStride
        val blockSize = blockSize
        val maxload = maxload
        val gateScheduler = gateScheduler
@@ -31,8 +46,10 @@ struct
     FullSimBFS
       (structure B = B
        structure C = C
-       structure SST = SparseStateTable (structure B = B structure C = C)
+       structure HS = HSLockFree
        structure G = G
+       val disableFusion = disableFusion
+       val maxBranchingStride = maxBranchingStride
        val blockSize = blockSize
        val maxload = maxload
        val gateScheduler = gateScheduler
@@ -50,23 +67,23 @@ struct
 
   fun main (inputName, circuit) =
     let
-      val numQubits = Circuit.numQubits circuit
+      val numQubits = #numQubits circuit
       val impl = CLA.parseString "impl" "lockfree"
       val output = CLA.parseString "output" ""
       val outputDensities = CLA.parseString "output-densities" ""
 
       val _ = print ("impl " ^ impl ^ "\n")
 
-      val sim =
+      fun sim () =
         case impl of
-          "lockfree" => BFSLockfree.run
-        | "locked" => BFSLocked.run
+          "lockfree" => BFSLockfree.run circuit
+        | "locked" => BFSLocked.run circuit
         | _ =>
             Util.die
               ("unknown impl " ^ impl
                ^ "; valid options are: locked, lockfree\n")
 
-      val {result, counts} = Benchmark.run "full-sim-bfs" (fn _ => sim circuit)
+      val {result, counts} = Benchmark.run "full-sim-bfs" (fn _ => sim ())
       val counts = Seq.map IntInf.fromInt counts
 
       val maxNumStates = IntInf.pow (2, numQubits)
@@ -146,8 +163,8 @@ struct
       print
         (String.concatWith ","
            [ name
-           , Int.toString (Circuit.numQubits circuit)
-           , Int.toString (Circuit.numGates circuit)
+           , Int.toString (#numQubits circuit)
+           , Int.toString (Seq.length (#gates circuit))
            , Real.fmt (StringCvt.FIX (SOME 12)) (Rat.approx maxDensity)
            , Real.fmt (StringCvt.FIX (SOME 12)) (Rat.approx avgDensity)
            ] ^ "\n")