Fair-share queuing

Overview

When you submit a job to a quantum system on the IBM Cloud, it enters a queue with jobs from other users before eventual execution. The order which these jobs are executed is, by default, determined by a fair-share queuing formula. As discussed below, this algorithm attempts to balance the workload between different providers so as to guarantee that each gets its allocated amount of time on the system. In practice, this means that jobs from various providers are interweaved in a non-trivial manner, and the order in which jobs complete is not necessarily the order in which they were submitted. As the queue order is calculated dynamically as new jobs arrive, it is impossible to guarantee when a fair-share job will be executed. For time-critical applications or iterative algorithms, therefore, consider instead scheduling a reservation for system time.

How the fair-share queue works

Fair-share queuing executes jobs on a quantum system in a dynamic order so that no provider can monopolize the system. The shares in fair-share queuing represent the fraction of system time that is allocated to a given provider. Providers with the most device time have the highest priority in the fair-share algorithm. A provider’s dynamic priority depends on how much of the provider’s allotted system time has been consumed over a given floating window of time. When you send a job, it will be executed by the provider with the highest dynamic priority (or lowest fraction of allotted time used) at that moment.

Note on queuing

Each IBM Quantum system has its own queue, so the fair-share calculation is on a per-system basis.

The fair-share algorithm is best illustrated by example. Consider the following example of seven providers split between two different hubs (see providers for an overview of hubs, groups, and projects). Each hub is assigned a given amount of time on a quantum system. The administrators of a hub in turn assign a given fraction of that time to each group in the hub. A similar allocation is done for each project in a group. As jobs flow through the system, each provider consumes some fraction of its allotted time, and the computed dynamic priority for that provider decreases.

Fair-share queue example.

Figure 1 - A snapshot view of dynamic priority assigned to hubs, groups, and projects that make up seven different providers. Here the dynamic priorities are normalized so that the next selected hub, group, or project has priority 1.0 when selected by the fair-share algorithm. In this example, the provider Hub-A/Group-1/Project-Y is selected, and the oldest job (first submitted) in the provider is executed.

When consuming a job, the fair-share queue first looks at each hub and selects the one with the largest dynamic priority at that time. With the hub selected, the algorithm then looks at the dynamic priorities of the underlying groups, selecting the highest. This is repeated at the project level as well. Once a provider is selected, the oldest job in queue from that provider is executed.

After a job is completed, the amount of time the job consumed on the system is used to recompute the dynamic priorities for the providers within the hub from which the job originated. The fair-share algorithm then selects the next job based on these updated priorities.

Recomputed fair-share priorities.

Figure 2 - Recomputed fair-share priorities reflecting the previous job execution. A new provider (Hub-B/Group-2/Project-N) is selected based on these updated values.