Scheduling Strategies¶
DQC currently exposes four concrete scheduling strategies:
fifodes_link_fifodes_link_shortest_durationdes_link_critical_path
Shared Timing Model¶
All schedulers use the same deterministic gate durations from the scheduler timing model:
A remote gate is not one operation but a catent / catdisent pair, and each
is priced separately. An rswap is two state teleportations, and one
teleportation costs a two-qubit gate, three single-qubit gates, and two
measurements — hence the factor of 2. See
Hardware & Settings for the worked numbers
under each packaged profile.
The deterministic EPR duration used by fifo is
where \(r\) is the configured entanglement generation rate.
The DES schedulers instead model repeated entanglement attempts with cycle time \(t_c\) and per-attempt success probability \(p\).
Configuring the parameters¶
\(t_{1q}\), \(t_{2q}\), \(t_{\mathrm{meas}}\), \(r\), and the EPR lifetime are the
primitive parameters; every duration above is derived from them. They default
to the modality and entanglement profile selected in
src/memq_dqc/settings.toml, and each can be overridden per compile or per
scheduler run on SchedulerHardwareProfile. Hardware &
Settings documents every parameter and profile; the short
version is:
from memq_dqc import SchedulerHardwareProfile
profile = SchedulerHardwareProfile.sr_trapped_ion(
two_qubit_gate_time=120.0,
epr_lifetime=80.0,
)
Pass it as Scheduler(source, profile=profile), or as
SchedulingCompileOptions(hardware_profile=profile) for
compile_scheduling_instance. The derived durations recompute from whatever
values are in effect, so they always stay consistent with the primitives.
\(t_c\) (des_entanglement_time_step) remains global to settings.toml.
FIFO¶
File:
src/memq_dqc/scheduler/fifo.py
Class:
FIFOScheduler
Plain-language description: This is a greedy baseline scheduler. It walks the DAG layer by layer and schedules each operation at the earliest time when all of its qubits are free. Remote operations receive just-in-time EPR events of fixed duration, and the remote gate starts immediately after those EPR windows finish.
Core rule:
where \(Q_i\) is the set of qubits touched by operation \(i\) and \(a_q\) is the current availability time of qubit \(q\).
For a remote operation, the start time is also constrained by the required EPR windows:
This strategy is fast and deterministic, but it is only locally greedy. It does not search globally for the best schedule, and it does not model stochastic EPR retries or expiration.
DES Link FIFO¶
File:
src/memq_dqc/scheduler/des_link_fifo.py
Class:
DESLinkFIFOScheduler
Plain-language description: This scheduler runs a discrete-event simulation in which remote operations request EPR pairs on their communication links. Each link can host at most one active entanglement process at a time. If several operations want the same link, the oldest blocked request wins when that link becomes free.
Entanglement attempt model:
Link arbitration rule:
where \(R_{\ell}(t)\) is the set of requests waiting for link \(\ell\) at time \(t\).
This strategy keeps the physical DES model of retries, waiting, expiration, and regeneration, but it resolves link contention using pure FIFO order.
DES Link Shortest Duration¶
File:
src/memq_dqc/scheduler/des_link_shortest_duration.py
Class:
DESLinkShortestDurationScheduler
Plain-language description:
This strategy uses the same DES engine as des_link_fifo, but changes the
link-arbitration rule. When several blocked remote operations want the same
link, it prefers the request whose remote operation has the smallest
deterministic duration.
Link arbitration rule:
Tie break:
This strategy is useful when the goal is to clear short remote work quickly and reduce head-of-line blocking on busy links.
DES Link Critical Path¶
File:
src/memq_dqc/scheduler/des_link_critical_path.py
Class:
DESLinkCriticalPathScheduler
Plain-language description: This strategy also uses the same DES engine, but it prioritizes requests that sit on a larger remaining downstream critical path. It is a heuristic for improving overall makespan when link contention would otherwise delay the most important remote work.
Remaining-path score:
with
Link arbitration rule:
Tie break:
This strategy keeps the stochastic DES model while biasing the scheduler toward requests whose delay is most likely to extend the final makespan.