Heterogeneous Hardware and Advanced Scheduling

Research work by Aygul Nuryyeva, student of the International University for the Humanities and Development. Instructor: Nurmyrat Allayarov.

Abstract

The end of Dennard scaling and the slowdown of Moore's Law have turned modern data centres into collections of diverse processors: multi-core CPUs, GPUs, tensor processing units, FPGAs and a deep hierarchy of storage and network devices. The performance of a job on such hardware depends on the specific job-device pair, which makes the resource-scheduling problem considerably harder than on homogeneous clusters.

This thesis surveys heterogeneous hardware and advanced scheduling. It explains why heterogeneity arises and what each device class means for a scheduler; presents the theory of scheduling on identical, related and unrelated machines, including approximation results, the HEFT heuristic for task graphs and dominant resource fairness; traces the evolution of cluster schedulers from Quincy, Mesos and YARN through Omega, Borg and Kubernetes to Sparrow, Apollo and Firmament; and reviews heterogeneity-aware and accelerator-aware schedulers for deep learning, including Gandiva, Tiresias, Themis, Gavel, AntMan, HiveD, Pollux and Sia. Practical frameworks (Kubernetes with device plugins and Dynamic Resource Allocation, Kueue, Volcano, Slurm and Ray) are compared, and guidelines are given for institutions with mixed hardware pools.

A small simulation study with 24 devices in three performance classes and 50 synthetic workloads of 200 jobs illustrates the central mechanism. Completion-time-based placement reduced mean makespan by about 27 per cent and mean average job completion time by about 10 per cent compared with availability-based placement, naive use of the fastest hardware performed worst, and longest-first ordering reduced makespan but increased average completion time. These results are synthetic and illustrate direction rather than magnitude.

All 51 sources are listed in an annotated bibliography with links and a verification status for each.

Keywords: heterogeneous computing, cluster scheduling, GPU scheduling, accelerators, resource management, fairness, deep learning systems, Kubernetes, Slurm.

Chapter 1. Introduction

1.1 Background and Motivation

For roughly three decades, the performance of general-purpose processors improved at a pace that allowed software engineers to treat hardware as a stable, homogeneous substrate. Faster clocks, deeper pipelines and larger caches delivered speed-ups with little effort from application developers. That era ended in the mid-2000s, when power density, rather than transistor count, became the dominant constraint. Esmaeilzadeh and colleagues showed that under realistic power budgets a growing fraction of a chip must remain powered down, a phenomenon they named "dark silicon" [1]. Hennessy and Patterson later summarised the consequence: with Dennard scaling over and Moore's Law slowing, further large gains must come from domain-specific architectures and domain-specific languages [2].

The industry response has been the rapid diversification of computing hardware. A modern data centre no longer consists of thousands of near-identical servers. It contains multi-core CPUs of several generations, graphics processing units (GPUs) from multiple vendors and generations, tensor processing units (TPUs) and other neural-network accelerators [6][7], field-programmable gate arrays (FPGAs) embedded in servers and network interface cards [8][9], and a deep hierarchy of storage and memory technologies. This phenomenon is called heterogeneous computing, and the infrastructure that exposes it to users is called a heterogeneous cluster.

Heterogeneity makes the resource-management problem fundamentally harder. A scheduler for a homogeneous cluster may treat a "slot" or a "core" as an interchangeable unit. In a heterogeneous cluster the same job may run ten times faster on one device class than on another, may not run at all on a third, and may interfere destructively with its neighbours on a shared device. Narayanan et al. report, for example, that a ResNet-50 model sees a nearly tenfold speed-up on an NVIDIA V100 compared with a K80 GPU, whereas other model types gain far less [35]. A scheduler that ignores such differences will waste scarce and expensive hardware.

The cost of getting this wrong is large. Accelerators are among the most expensive components of a data centre, and in the training of large machine-learning models they are a binding constraint on research progress. Studies of production GPU clusters at Microsoft and Alibaba have documented low utilisation, long queueing delays and failures caused by poor placement and fragmentation [41][42]. Advanced scheduling, meaning scheduling that is aware of heterogeneity, workload characteristics, fairness, locality and interference, is therefore a central research topic in systems.

1.2 Problem Statement

The central problem addressed in this thesis can be stated as follows:

Given a pool of heterogeneous computing resources (CPUs, GPUs, TPUs, FPGAs, storage and network) and a stream of jobs whose performance depends on the device they are placed on, how should resources be assigned to jobs over time so that cluster-level objectives (throughput, completion time, fairness, utilisation, cost and energy) are optimised, subject to practical constraints (scalability, fault tolerance, multi-tenancy and incomplete information)?

This problem is NP-hard in its general form (Chapter 3), operates at a scale where decisions must be made in milliseconds to seconds, and is complicated by the fact that job performance is often unknown in advance.

1.3 Objectives

The objectives of this research are:

• To survey the hardware landscape of heterogeneous computing and explain why heterogeneity arises and what properties of each device class matter to a scheduler.
• To present the theoretical foundations of scheduling on heterogeneous machines, including classical models, approximation results, DAG-scheduling heuristics and fairness definitions for multiple resource types.
• To trace the historical evolution of cluster schedulers from early two-level designs to modern shared-state and hierarchical systems.
• To critically review heterogeneity-aware and accelerator-aware scheduling techniques, especially for deep-learning workloads.
• To describe how these ideas are realised in widely used practical frameworks (Kubernetes, Slurm, Kueue, Volcano and Ray).
• To perform a controlled, reproducible simulation that illustrates the effect of heterogeneity awareness on makespan and job completion time.
• To identify open challenges and future research directions.

1.4 Research Questions

• RQ1. What distinguishes the major classes of computing hardware from the viewpoint of a resource scheduler?
• RQ2. Which theoretical models and algorithms best describe scheduling on heterogeneous resources, and what are their limits?
• RQ3. How have cluster scheduler architectures evolved to manage heterogeneous, multi-tenant environments?
• RQ4. What mechanisms do state-of-the-art heterogeneity-aware schedulers use, and what trade-offs do they make?
• RQ5. How large is the benefit of heterogeneity awareness under controlled conditions, and when can it hurt?

1.5 Methodology

The study is primarily a systematic literature review and comparative analysis. Sources were selected from top-tier systems and architecture venues (OSDI, SOSP, NSDI, EuroSys, ISCA, ASPLOS, SIGCOMM, USENIX ATC), from foundational journal articles, and from the official documentation of widely used open-source schedulers. Selection criteria were relevance to heterogeneous resource scheduling, influence (citations and adoption in practice) and availability of a stable publisher or DOI link. Every source used is listed with an annotation in the final chapter.

The review is complemented by a small simulation study (Chapter 7). The simulation is deliberately simple and uses synthetic workloads. It is intended to illustrate mechanisms discussed in the literature, not to reproduce or replace the evaluations of the cited systems.

1.6 Scope and Limitations

The thesis concentrates on scheduling of compute jobs on data-centre and cluster resources. It does not cover instruction-level scheduling inside a processor, compiler optimisation in depth, or wireless and edge scheduling, although several ideas transfer. Quantitative figures quoted from the literature are reported as the original authors reported them, under their experimental conditions, and should not be assumed to hold elsewhere. The simulation results in Chapter 7 come from synthetic data and are not claims about any real system.

1.7 Structure of the Thesis

Chapter 2 surveys heterogeneous hardware. Chapter 3 presents scheduling theory. Chapter 4 reviews the evolution of cluster scheduler architectures. Chapter examines heterogeneity-aware and deep-learning schedulers. Chapter 6 discusses practical frameworks. Chapter 7 reports the simulation study. Chapter 8 discusses challenges and future directions, and Chapter 9 concludes. The annotated bibliography follows, and appendices provide a glossary and the simulation design.

Chapter 2. Heterogeneous Hardware

2.1 Why Heterogeneity Arose

Three forces drove the transition from homogeneous to heterogeneous systems.

Power and the end of frequency scaling. Dennard scaling held that as transistors shrank, power density stayed constant, allowing frequency to rise. When voltage scaling stalled, chips could no longer be clocked faster within a fixed power envelope. Esmaeilzadeh et al. projected that multicore scaling alone would leave large areas of future chips unusable at full speed [1].

Specialisation as the remaining lever. If general-purpose cores cannot be made much faster per watt, efficiency must come from matching hardware to the structure of the computation. Dally, Turakhia and Han argue that domain-specific accelerators gain their efficiency from specialised operations, parallelism, local memory and reduced overhead [3]. Hennessy and Patterson call the resulting trend a new golden age for computer architecture [2].

Economic and workload pressure. Deep learning created a workload with enormous, regular linear-algebra demand, making it economical to build dedicated silicon. Cloud providers operating at huge scale can amortise the design cost of custom accelerators [6][8].

A further source of heterogeneity is more mundane: hardware is purchased over time. A cluster that is five years old contains several CPU generations and possibly several GPU generations at once. Analysis of Google's production trace showed that machines in a cluster differ in platform and capacity, and that workloads are themselves highly diverse [27]. Heterogeneity is therefore both a design choice and an unavoidable consequence of incremental procurement.

2.2 Taxonomy of Heterogeneity

It is useful to distinguish several kinds of heterogeneity, because each affects scheduling differently.

• Architectural (inter-class) heterogeneity: CPUs, GPUs, TPUs, FPGAs and ASICs implement fundamentally different execution models.
• Generational (intra-class) heterogeneity: GPUs of different generations differ in memory capacity, tensor-core support and bandwidth.
• Capacity heterogeneity: machines differ in cores, memory, local storage and network bandwidth.
• Topological heterogeneity: the speed of communication between devices depends on whether they share a node, a high-speed interconnect or only the data-centre network.
• Workload heterogeneity: jobs differ in resource demand, duration, elasticity and sensitivity to hardware.
• Performance variability: nominally identical devices can perform differently because of thermal, silicon or contention effects.

2.3 Device Classes

2.3.1 Central Processing Units (CPUs)

CPUs are latency-optimised, general-purpose processors with a small number of powerful cores, deep cache hierarchies, out-of-order execution and branch prediction. They execute almost any code and are the only device class that can run an operating system and orchestrate the others. From a scheduling viewpoint a CPU is a fungible and divisible resource: cores and memory can be allocated in small units and many jobs can share a machine. CPUs remain the best choice for control-heavy, irregular or low-parallelism tasks and for data pre-processing, which frequently becomes the bottleneck that starves accelerators.

2.3.2 Graphics Processing Units (GPUs)

GPUs are throughput-optimised processors with thousands of simple lanes organised into streaming multiprocessors and fed by high-bandwidth memory. They excel at data-parallel work such as dense linear algebra. Programming models include CUDA, OpenCL [5] and vendor-specific stacks. For schedulers the key properties are: (i) devices are typically allocated in whole units, historically one device per job or a fixed count per job; (ii) memory capacity is a hard constraint, since a model that does not fit cannot run; (iii) multi-GPU jobs are sensitive to interconnect topology, so placement quality matters; and (iv) generations differ widely in speed. Hardware partitioning, such as NVIDIA Multi-Instance GPU (MIG), allows a single physical GPU to be divided into isolated instances with dedicated memory and compute slices [49], which turns a coarse resource into a finer-grained one.

2.3.3 Tensor Processing Units and Other Neural-Network ASICs

The first-generation TPU of Google was an inference accelerator built around a large matrix-multiply unit of 65,536 8-bit multiply-accumulate elements, and was reported to be 15 to 30 times faster than contemporary CPUs and GPUs on its production workloads and 30 to 80 times better in performance per watt [6]. Later generations added training support, floating-point formats suited to training and custom optical or electrical interconnects joining thousands of chips into a single "pod" [7]. Such devices are scheduled in slices of a regular topology, so a scheduler must find a contiguous, correctly shaped block rather than any set of free chips. Their software stack is more constrained than that of GPUs, which narrows the set of jobs that can use them and makes "can this job run here?" a first-class scheduling constraint.

2.3.4 Field-Programmable Gate Arrays (FPGAs)

FPGAs are reconfigurable logic devices whose function is defined by a bitstream. They offer deterministic low latency and high energy efficiency for streaming and pipelined computations. Microsoft's Catapult project placed an FPGA in each of 1,632 servers to accelerate Bing web-search ranking and reported a 95 per cent increase in ranking throughput at comparable latency for about a 10 per cent increase in power [8]. In Azure, FPGA-based SmartNICs were used to offload network virtualisation functions to hardware [9]. Scheduling FPGAs introduces a unique concern: reconfiguration cost. Loading a different bitstream takes time, so the scheduler must weigh the benefit of switching functions against the overhead, and may prefer to keep a device dedicated to one function for long periods.

2.3.5 Memory and Storage Hierarchy

Heterogeneity extends below the compute layer. A node may hold DRAM, high-bandwidth memory on accelerators, persistent memory, NVMe flash, spinning disks and remote object storage, with latency differences of several orders of magnitude. Data locality, namely placing computation near its data, has been a design principle since MapReduce-era schedulers [22]. In machine-learning pipelines, a slow storage tier or an overloaded CPU pre-processing stage can leave a costly GPU idle, so a scheduler that optimises only accelerator allocation can still produce poor end-to-end throughput.

2.3.6 Networking and Smart NICs

Modern data centres combine Ethernet, InfiniBand and proprietary accelerator interconnects. Bandwidth inside a node (for example between GPUs) is far higher than between nodes. Smart NICs and data processing units add programmable compute at the network edge of each server [9]. For distributed training, the placement of workers relative to the network topology can matter as much as the number of devices allocated, a point emphasised by studies of multi-tenant GPU clusters [41].

2.4 Comparative Summary

Table 2.1 summarises scheduling-relevant characteristics of the device classes. The qualitative entries synthesise the cited literature and are not benchmark results.

2.5 Programming Models and Portability

A scheduler can only place a job on a device if the job's software can execute there. Open standards such as OpenCL aim to give one source code multi-device portability [5], but performance portability, meaning good performance on every device without hand tuning, remains hard. Compiler frameworks such as TVM generate optimised code for diverse hardware back ends from a high-level model description [10], which widens the set of devices a given model can use. Task-based runtimes such as StarPU manage data transfers and schedule tasks over CPUs and GPUs using performance models learned at run time [14]. These software layers matter to scheduling in two ways: they determine the feasibility set (which devices can run the job) and they supply the performance estimates the scheduler needs.

2.6 Implications for Scheduling

From the preceding survey, five properties recur and define the scheduling problem for heterogeneous hardware:

• Performance is job-and-device specific. There is no single "speed" for a device; speed is a matrix over (job, device) pairs.
• Feasibility is non-trivial. Memory capacity, software support and topology rule out some placements entirely.
• Allocation granularity differs across device types, which complicates packing and fairness across resource types.
• Switching and sharing have costs: bitstream reconfiguration, context switches, checkpoint and migration, and interference between co-located jobs.
• Information is imperfect. Job runtimes and device sensitivities are often unknown until the job has run, so schedulers must profile, predict or learn.

These observations motivate the models of Chapter 3.

Chapter 3. Theoretical Foundations of Scheduling

3.1 The Classical Scheduling Problem

Scheduling theory studies how to assign a set of jobs to a set of machines over time to optimise an objective. Problems are conventionally described by a three-field notation alpha | beta | gamma, where alpha describes the machine environment, beta the job characteristics (release times, precedence constraints, pre-emption) and gamma the objective. The machine environments most relevant here are:

• P (identical machines): every machine processes every job at the same speed.
• Q (uniform or related machines): machine i has a speed si, and job j with size pj takes pj / si time on it.
• R (unrelated machines): the time of job j on machine i is an arbitrary number pij.

The unrelated model R is the natural abstraction of a heterogeneous cluster in which job performance depends on the job-device pair, as described in Section 2.6. The related model Q captures the simpler case in which a newer device is uniformly faster for every job. Real accelerator clusters lie between the two, and this gap is exactly what heterogeneity-aware schedulers exploit.

Common objectives are the makespan Cmax (completion time of the last job, relevant to batch workloads), the average job completion time (JCT, relevant to user experience), the weighted completion time, tardiness with respect to deadlines, and fairness or utilisation measures defined across users.

3.2 Complexity and Approximation

Minimising makespan on identical machines is NP-hard, even for two machines, since it generalises the partition problem. Graham's list-scheduling analysis showed that simply assigning each job, in any order, to the machine that becomes free first yields a makespan at most (2 - 1/m) times the optimum on m identical machines, and that ordering jobs by non-increasing size (the longest-processing-time rule) improves the bound [11]. These are the oldest and most influential performance guarantees in the field, and the earliest-free rule is the ancestor of the "agnostic" baseline used in Chapter 7.

For unrelated machines, Lenstra, Shmoys and Tardos gave a polynomial-time 2-approximation for makespan using linear-programming rounding and showed that no algorithm can guarantee better than 3/2 unless P = NP [51]. The significance for our topic is twofold: the problem is intrinsically hard, and LP relaxations are a natural tool. Modern systems exploit the second observation, as Gavel does when it expresses scheduling policies as optimisation problems solved by sequences of linear programs [35].

3.3 Online Scheduling and Information

Batch theory assumes all jobs are known in advance. A cluster scheduler operates online: jobs arrive over time and, usually, their durations are unknown (non-clairvoyant scheduling).

Policies such as Shortest Remaining Processing Time are optimal for average completion time when sizes are known, but without size knowledge systems approximate them with attained-service heuristics. Tiresias applies this idea to deep-learning training, using two-dimensional attained service (time multiplied by number of GPUs) and the Gittins index when partial duration information exists [33]. The practical lesson is that information quality is a design axis as important as the algorithm itself.

3.4 Precedence-Constrained Tasks and the HEFT Heuristic

Many applications are workflows: directed acyclic graphs (DAGs) in which a task may start only after its predecessors have finished and transferred their data. Scheduling a DAG on heterogeneous processors is NP-hard, so practical algorithms are heuristics. The best-known is Heterogeneous Earliest Finish Time (HEFT) by Topcuoglu, Hariri and Wu [13]. HEFT has two phases:

• Prioritisation. Each task receives an upward rank: its average computation cost over all processors plus the maximum, over its successors, of the average communication cost plus the successor's rank. Tasks are sorted by decreasing rank, which respects precedence and favours tasks on the critical path.
• Processor selection. In rank order, each task is assigned to the processor that gives the earliest finish time, using an insertion policy that may fill idle gaps.

With e edges and p processors the algorithm runs in O(e x p) time, which explains its popularity as a baseline. Task-based runtimes such as StarPU implement HEFT-like policies informed by run-time performance models [14]. HEFT assumes accurate cost estimates, a static view of the system, and a single DAG; its weakness in multi-tenant clusters is that it optimises one application's makespan rather than shared-resource fairness.

3.5 Real-Time Scheduling

Where jobs have deadlines, as in serving workloads with latency targets, real-time theory applies. Liu and Layland's classical result established rate-monotonic and earliest-deadline-first priority assignment for periodic tasks on a single processor and gave utilisation bounds under which deadlines are guaranteed [12]. Although cluster workloads are not strictly periodic, deadline-aware policies underlie service-level objectives for latency-critical applications and appear in the design of schedulers that co-locate such services with batch jobs [31].

3.6 Fairness with Multiple Resource Types

Allocation of a single resource can use max-min fairness. With several resource types, such as CPUs, memory and GPUs, a job's demand vector is multi-dimensional and a single-resource notion no longer applies. Ghodsi et al. proposed Dominant Resource Fairness (DRF) [21]. A user's dominant resource is the resource for which the user's demand is the largest share of total capacity, and DRF equalises users' dominant shares, subject to capacity.

A worked example follows the original paper's classic setting. Suppose the system has 9 CPUs and 18 GB of memory. User A runs tasks needing (1 CPU, 4 GB) and user B tasks needing (3 CPUs, 1 GB). A's dominant resource is memory (4/18 of capacity per task) and B's is CPU (3/9 per task). Equalising dominant shares gives A three tasks (3 CPUs, 12 GB) and B two tasks (6 CPUs, 2 GB); each user then holds two thirds of the system in its dominant resource. DRF is known to satisfy sharing incentive, strategy-proofness, Pareto efficiency and envy-freeness [21].

DRF treats resources as divisible and assumes demand ratios are constant. In heterogeneous clusters neither assumption is exact: one GPU-hour is not worth the same on every GPU generation. Finish-time fairness, proposed in Themis, addresses part of this by comparing a job's finish time in the shared cluster with its finish time in an exclusive 1/N share [34]. Gavel generalises several fairness and efficiency policies by replacing raw resource counts with effective throughput, the throughput a job actually obtains across the device types it is allocated [35].

3.7 Multi-Resource Packing

Packing is the dual of fairness: it seeks high utilisation by placing tasks whose resource demands fit together, as in multi-dimensional bin packing. Grandl et al. showed that combining an alignment score between a task's demand vector and a machine's free-resource vector with a shortest-remaining-work preference can improve both makespan and average completion time over fairness-only schedulers [26]. Packing and fairness conflict, and many designs treat the trade-off explicitly, for example by providing fairness as a constraint within an efficiency-maximising allocation.

3.8 Amdahl's Law and Heterogeneous Speed-Up

Amdahl's law bounds the speed-up of a program by its serial fraction [15]. In heterogeneous systems it explains why accelerating only the parallel portion yields diminishing returns, and why host-side CPU work, data movement and orchestration overhead often become the bottleneck. For scheduling this implies that a job's measured speed-up on an accelerator is not a constant of the device but a function of the whole pipeline, which strengthens the case for measuring rather than assuming job-device performance.

3.9 Summary of Theoretical Insights

• Heterogeneous scheduling is most naturally modelled by unrelated machines, and is NP-hard; efficient heuristics and LP-based methods are the practical tools [11][51].
• Online, non-clairvoyant operation is the norm, so information acquisition (profiling, prediction, learning) is part of the scheduling problem [33].
• Multi-resource fairness requires dominant-share or effective-throughput style definitions [21][35].
• Fairness, efficiency and latency goals conflict, so policies must state explicit priorities.

Chapter 4. Evolution of Cluster Scheduler Architectures

4.1 Design Dimensions

Cluster schedulers differ along several architectural dimensions: centralised versus distributed decision-making; monolithic versus two-level or shared-state control; per-task versus per-job (gang) placement; queue-based versus flow-based placement algorithms; and how they learn about resources, either through static configuration, offers or a global view of state. The following sections trace how successive systems moved along these axes as workloads and hardware became more diverse.

4.2 Locality-Aware Flow-Based Scheduling: Quincy

Quincy cast the placement of data-parallel tasks as a min-cost flow problem in which edge costs encode data locality and fairness trade-offs, and demonstrated that a global optimisation could improve locality compared with greedy queue-based schedulers [22]. Quincy's importance for this thesis is conceptual: it showed that a principled optimisation model could handle conflicting objectives, an approach later generalised in Firmament.

4.3 Two-Level Scheduling: Mesos and YARN

Apache Mesos introduced two-level scheduling. A central resource manager offers resources to framework-specific schedulers, which decide whether to accept an offer, enabling several frameworks (batch, streaming, services) to share one cluster with fine-grained allocation [16]. Mesos also deployed DRF as its allocation policy [21]. A drawback is that framework schedulers see only the resources currently offered, which complicates placement of jobs with strict constraints, such as a large GPU group.

Apache Hadoop YARN separated resource management from application-specific logic: a global ResourceManager allocates containers, while each application's ApplicationMaster negotiates and manages its own tasks [17]. YARN made the same cluster usable for many frameworks and introduced the container abstraction with CPU and memory dimensions, later extended with other resources.

4.4 Shared-State Scheduling: Omega

Google's Omega argued that monolithic and two-level designs limit scalability and flexibility. In Omega, multiple parallel schedulers read a shared copy of the full cluster state and commit placement decisions as transactions using optimistic concurrency control, resolving conflicts when two schedulers claim the same resources [18]. This gives each scheduler a complete view, which is valuable when placement must respect heterogeneous constraints, at the cost of conflict handling and retries under high contention.

4.5 Borg and Kubernetes

Borg is Google's production cluster manager, running hundreds of thousands of jobs across clusters of up to tens of thousands of machines. Its scheduler scores machines using a combination of feasibility checking and scoring to balance packing against fragmentation and failure domains, and it supports job priorities, quotas, and pre-emption of lower-priority work [19]. The authors of Borg and Omega later described how lessons from both shaped Kubernetes, the open-source orchestrator that is now the de facto standard for container scheduling [20]. Section 6.1 examines Kubernetes' handling of accelerators in detail.

4.6 Distributed and Low-Latency Scheduling: Sparrow and Apollo

For workloads dominated by very short tasks, a centralised scheduler becomes a bottleneck. Sparrow uses decentralised, randomised "batch sampling" with late binding, probing a few workers per task and placing the task on the least-loaded, which delivers millisecond-scale scheduling latency [24]. Microsoft's Apollo is a distributed, coordinated scheduler for large-scale data analytics which makes decisions with a global cost model and a feedback loop that corrects for stale information [25]. Both illustrate the trade-off between decision quality and decision latency.

4.7 Flow-Based Scheduling at Scale: Firmament

Firmament revisits Quincy's min-cost flow approach and shows that, with a faster incremental solver and careful modelling, flow-based scheduling can make high-quality placement decisions at the scale of thousands of machines with sub-second latency [23]. Its policy-as-cost-model design makes it a natural framework for heterogeneity: different device types and their interference can be represented as costs on graph arcs, a technique relevant to the optimisation-based schedulers of Chapter 5.

4.8 Comparison

Table 4.1 compares the architectures discussed. Entries summarise the cited papers.

4.9 Observations

Three trends emerge. First, the unit of allocation moved from slots to multi-dimensional resource vectors, then to typed, scarce devices. Second, schedulers moved from per-task decisions toward gang and topology-aware decisions, necessary when a job needs several accelerators simultaneously. Third, scheduling became an optimisation problem with explicit policy objectives, a transition continued by the machine-learning-specific systems of Chapter 5.

Chapter 5. Heterogeneity-Aware and Accelerator-Aware Scheduling

5.1 Interference and Resource Sharing on Heterogeneous Servers

Before deep-learning schedulers, a line of work addressed two problems that remain central: which hardware suits a workload, and what happens when workloads share hardware.

Paragon uses collaborative-filtering techniques, borrowed from recommender systems, to classify an incoming workload with respect to both heterogeneity (which server configurations suit it) and interference (which co-runners hurt it) using only short profiling, then places it accordingly [29]. Quasar extends this to a resource-quantity decision: instead of users reserving resources, they state a performance target and the system determines both the amount and type of resources, again using classification to avoid exhaustive profiling [30]. Heracles addresses co-location of latency-critical services with best-effort batch jobs on the same server using real-time feedback control over isolation mechanisms, showing that high utilisation is compatible with strict latency targets [31]. Dean and Barroso's analysis of tail latency explains why this matters: at scale, rare slow responses dominate user-visible latency, so interference control is a first-order concern [28].

5.2 The Deep-Learning Workload

Deep-learning training jobs have properties that shape scheduler design [41][42]:

• Gang requirements. Distributed data-parallel training needs all its GPUs simultaneously; partial allocation is useless.
• Long and iterative execution. Jobs run for hours to weeks, but consist of many near-identical iterations, so short profiling predicts long-term behaviour.
• Pre-emptibility via checkpointing. Jobs can be suspended at iteration boundaries and resumed, at the cost of checkpoint and restore overhead.
• Locality sensitivity. Communication-heavy models run much faster when their GPUs share a node or fast interconnect.
• Heterogeneous speed-ups. Different models benefit very differently from newer accelerators [35].
• Elasticity. Many jobs can change their number of workers during training, if their hyper-parameters adapt accordingly [38].

Jeon et al. analysed a multi-tenant GPU cluster at Microsoft and found that both queueing delay and the failure and locality-related behaviour of jobs reduce effective utilisation, motivating schedulers that trade strict locality against waiting time [41]. Weng et al. analysed a large production cluster at Alibaba and examined the mix of workloads and the heterogeneity of GPU resources there [42].

5.3 Survey of Deep-Learning Cluster Schedulers

5.3.1 Gandiva

Gandiva exploits the iterative structure of training to introduce time-slicing of GPUs among jobs, migration of jobs to defragment the cluster, grow-shrink of job size to use idle devices, and application-aware profiling to decide placements [32]. It was an early demonstration that introspective, mechanism-rich scheduling could greatly improve GPU efficiency compared with static allocation.

5.3.2 Tiresias

Tiresias addresses distributed training without assuming known job durations. It introduces a two-dimensional attained-service metric, combining running time and number of GPUs, and a discretised priority queue structure to approximate least-attained-service scheduling and avoid starvation. It also profiles models to decide when to enforce consolidated placement, since some models are insensitive to the spread of their GPUs [33].

5.3.3 Themis

Themis targets finish-time fairness, a metric that compares the finish time of a job in the shared cluster with that in an exclusive, equal-share cluster. It uses a two-level auction in which jobs bid for resources, with an arbiter allocating according to bids; the design encourages truthful reporting while retaining efficiency [34].

5.3.4 Gavel

Gavel is explicitly heterogeneity-aware. Its key abstraction is effective throughput, which captures the throughput a job obtains given the fractions of time it spends on each accelerator type. A broad family of policies, among them least-attained-service fairness, FIFO, makespan minimisation, finish-time fairness, shortest-job-first, cost minimisation subject to SLOs and hierarchical policies, is expressed as an optimisation problem over a job-by-accelerator allocation matrix and solved with convex-optimisation techniques. A round-based mechanism then realises the computed allocation by time-slicing. Gavel also supports space sharing, co-locating jobs on a device when beneficial. The authors report that heterogeneity-aware policies sustain higher load and improve makespan and average job completion time by up to 3.5 times compared with heterogeneity-agnostic ones [35]. This result is the strongest direct evidence in the literature for the value of heterogeneity awareness.

5.3.5 AntMan

AntMan, deployed at Alibaba, co-designs the deep-learning framework and the scheduler to allow dynamic scaling of memory and computation of co-located jobs. Production (guaranteed) jobs are protected while opportunistic jobs scavenge idle GPU capacity, raising utilisation without breaching production performance targets [36].

5.3.6 HiveD

HiveD addresses the tension between sharing and tenant isolation. Its "cell" abstraction lets a tenant reserve a virtual private cluster that preserves the topology of its share, avoiding a "sharing anomaly" in which a tenant could be offered fewer well-connected GPUs in the shared cluster than it would have in a private one [37].

5.3.7 Pollux

Pollux observes that the resource decision and the training-hyper-parameter decision are coupled: increasing the batch size to use more GPUs affects statistical efficiency. It defines goodput, the product of system throughput and statistical efficiency, and co-adaptively allocates resources and tunes batch size and learning rate to maximise cluster-wide goodput [38].

5.3.8 Sia

Sia combines the two ideas of heterogeneity awareness and resource adaptivity. The authors observe that existing schedulers address one aspect or the other but not both, and many scale poorly. Sia introduces a scheduling formulation that matches jobs and their configurations to GPU types and counts, supported by a low-overhead way of bootstrapping throughput models for each new job. On clusters of 44 to 64 GPUs with three GPU types they report reductions of 30 to 93 per cent in average job completion time, 28 to 95 per cent in 99th-percentile completion time and makespan, and 12 to 55 per cent in GPU hours, and they show scaling to at least 2,000-GPU clusters [39]. As with all published evaluations these numbers depend on the workloads and baselines used by the authors.

5.3.9 Learning-Based Scheduling: Decima

Decima uses reinforcement learning with graph neural networks to learn scheduling policies for DAG-structured data-processing jobs, rather than hand-designing heuristics, and is trained in a simulator before deployment [40]. It indicates a direction in which scheduling policies are discovered rather than engineered, although practical concerns remain about robustness, explainability and training cost.

5.4 Comparison of Deep-Learning Schedulers

5.5 Cross-Cutting Mechanisms

Profiling and performance modelling. Every heterogeneity-aware system needs the job-device performance matrix. Approaches include short online profiling runs, models learned from similar past jobs (Paragon, Quasar), analytic throughput models (Sia) and run-time calibration (StarPU) [14][29][30][39].

Time-slicing and round-based allocation. Because accelerators are coarse and jobs indivisible, fractional optimal allocations are realised in time by rotating jobs among devices in rounds [35].

Space sharing and hardware partitioning. Co-locating jobs on one device increases utilisation but creates interference; hardware partitioning such as MIG gives isolation at the price of fixed slice sizes [36][49].

Elasticity and adaptivity. Changing a job's size over its lifetime lets the scheduler fill gaps, but the job's convergence must be protected [38][39].

Placement and topology. Consolidated placement improves communication performance but may increase queueing, so the right balance is model-dependent [33][41].

Checkpointing and migration. The ability to suspend and relocate jobs underpins pre-emption, defragmentation and fair sharing [32].

5.6 Critical Discussion

Three tensions deserve emphasis. First, generality versus specialisation: policy-as-optimisation frameworks are flexible but their solvers must scale; Sia's contribution is partly a formulation that scales to thousands of GPUs [39]. Second, fairness versus efficiency: heterogeneity-aware efficiency can disadvantage jobs that gain little from fast devices, so fairness definitions (Section 3.6) must be heterogeneity-aware too [34][35]. Third, evaluation validity: most results derive from simulation using traces from particular organisations, so portability of the numbers is uncertain. A reader should treat the reported improvements as evidence that heterogeneity awareness can matter a great deal, not as predictions for any specific cluster.

Chapter 6. Practical Frameworks and Industry Practice

6.1 Kubernetes

Kubernetes models accelerators as extended resources advertised by device plugins. A device plugin registers with the kubelet and exposes vendor devices, such as GPUs, FPGAs or high-performance NICs, as countable resources that pods request in their resource limits [43]. Extended resources are integral and not over-committable, which suits whole-device allocation but is coarse for fractional sharing. Heterogeneity between nodes is expressed using node labels, node affinity, taints and tolerations, so a job can require, say, a particular GPU model.

The default scheduler works by filtering nodes that cannot host a pod and scoring the remainder, a design that descends from Borg [19][20]. Its scheduling framework provides plugin extension points (for example queue sorting, filter, score, reserve, permit and bind), allowing custom logic such as gang scheduling or topology-aware scoring to be added without forking the scheduler [44]. Dynamic Resource Allocation (DRA) generalises device requests by letting pods claim devices through structured, attribute-based descriptions, which is a better fit for heterogeneous and partitionable devices than integer counters [45]. Because DRA and related features have been maturing across recent Kubernetes releases, readers should consult the current documentation for their version.

6.2 Batch Scheduling Add-Ons: Kueue and Volcano

The default Kubernetes scheduler was designed for services, not for batch queues with quotas and gangs. Kueue adds job queueing: cluster administrators define quotas and resource flavors (for example different GPU types), and Kueue decides when a job should be admitted and on which flavor, delegating the actual pod placement to the scheduler [46]. Volcano provides batch-oriented scheduling with gang scheduling, queues and fair-share policies for machine-learning and high-performance workloads [47]. Resource flavors in Kueue are, in effect, a pragmatic implementation of heterogeneity awareness at the admission layer.

6.3 Slurm and HPC Scheduling

In high-performance computing, Slurm is widely used. Accelerators are described as generic resources (GRES), declared per node and requested per job, optionally with a type such as a GPU model; Slurm then handles allocation, binding and accounting of those resources [48]. Slurm's backfill scheduling lets small jobs run in gaps without delaying the highest-priority job, an instance of the packing principles of Section 3.7.

6.4 Ray

Ray is a distributed execution framework for emerging AI applications, with a task and actor model and a bottom-up distributed scheduler, in which tasks are first scheduled locally and escalated to a global scheduler when needed. Tasks can declare custom resource requirements such as GPUs [50]. Ray demonstrates how heterogeneity-aware placement can be offered as an application-level library rather than a cluster-level service.

6.5 Comparison of Practical Frameworks

6.6 Gap Between Research and Practice

Research systems such as Gavel and Sia use rich job-device performance models and global optimisation. Production tools mostly rely on administrator-defined labels, quotas and static priorities. This gap exists for good reasons: production systems need predictability, debuggability, integration with existing tooling and conservative failure behaviour. A plausible path for adoption is incremental: expose accurate device attributes (as DRA does), add admission-layer awareness of device flavors (as Kueue does), and then introduce measured, per-job throughput estimates into the queueing policy.

6.7 Guidelines for Designing a Heterogeneity-Aware Scheduler

Synthesising Chapters 3 to 6, the following guidelines are proposed for practitioners, such as a university computing centre with a mixed GPU pool:

• Maintain an explicit inventory with typed attributes (device model, memory, interconnect, location).
• Collect per-job performance measurements on each device type, even coarse ones, and reuse them for similar jobs.
• Define the policy objective explicitly (for example minimise average completion time subject to a fairness floor) rather than relying on queue order.
• Use gang scheduling and topology-aware placement for multi-device jobs.
• Keep a fairness guard: ensure jobs that gain little from fast devices are not starved.
• Prefer incremental adoption: start with labels and flavors, add optimisation later.

Chapter 7. Simulation Study: The Value of Heterogeneity Awareness

7.1 Purpose

Chapters 3 to 5 argue that heterogeneity-aware placement can substantially improve cluster objectives. This chapter tests the argument in the simplest possible setting. The goal is not to reproduce the evaluations of Gavel [35] or Sia [39], which use real traces, richer policies and physical clusters, but to isolate one mechanism: choosing a device by predicted completion time rather than by availability alone.

7.2 Experimental Design

Cluster. 24 single-device slots in three classes of 8 devices each (called A, B and C, from oldest to newest GPU generation).

Workload. 200 jobs per experiment, all submitted at time zero (a batch scenario, so job completion time equals completion time from the start). Each job has a size in "class-A hours" drawn from a log-normal distribution (mu = 3.0, sigma = 0.9), which gives the heavy-tailed durations typical of training workloads. Each job also has a random sensitivity drawn uniformly between 0 and 1 that determines its speed-up on newer classes. Speed-up on class B is between about 1 and 2.8 and on class C between about 1 and 10.6, with C never slower than B. The range of speed-ups is chosen to be in the order of magnitude that the literature reports for GPU generations [35] but is otherwise arbitrary. Insensitive jobs gain little from new hardware, sensitive ones gain a lot.

Policies. Jobs are placed one at a time without pre-emption, each running to completion on one device.

• Random placement (agnostic). Jobs are shuffled, then each goes to the device that becomes free earliest. Speed is ignored.
• FIFO, earliest-free device (agnostic). The same rule in arrival order. This is Graham's list-scheduling rule [11] applied as if the devices were identical.
• Always fastest class (greedy). Every job goes to the fastest device class available to it, queuing there. This is a naive form of "use the best hardware".
• Minimum completion time (aware, MCT). Each job goes to the device on which it would finish earliest, given the device's current backlog and the job's speed on that device.
• LPT order plus MCT (aware). Jobs are first sorted by decreasing duration on the fastest class (the longest-processing-time idea [11]), then placed by MCT.

Metrics. Makespan, average job completion time (JCT) and 95th-percentile JCT, averaged over 50 independently generated workloads (seeds). The values after the plus-minus sign in the table are standard deviations across the 50 workloads.

7.3 Results

7.4 Analysis

Heterogeneity awareness helps. Relative to the agnostic FIFO baseline, minimum-completion-time placement reduced mean makespan from 229.9 to 168.8 hours (about 27 per cent) and mean average JCT from 61.5 to 55.3 hours (about 10 per cent). The tail also improved: 95th-percentile JCT fell from 119.5 to 108.1 hours.

Ordering matters for makespan, and it costs average JCT. Adding longest-first ordering cut mean makespan further, to 128.7 hours (about 44 per cent below FIFO), because starting long jobs early on fast devices avoids a long straggler at the end. But it raised mean average JCT to 88.5 hours, about 44 per cent worse than FIFO, because the many short jobs now wait behind the long ones. This reproduces, in miniature, the textbook conflict between makespan and average completion time and shows that "better" depends on the objective, a point made by systems such as Gavel that expose the policy as an explicit parameter [35].

Naive use of the best hardware backfires. Sending every job to the fastest class produced the worst results on all three metrics (makespan 253.0 hours, average JCT 106.7 hours). The newest devices become a bottleneck while older devices sit idle. This confirms the intuition that heterogeneity awareness is not "prefer the fastest hardware" but "match jobs to devices considering load and sensitivity", in line with the optimisation formulations of Gavel and Sia [35][39].

Variance. The standard deviations are large because the log-normal job sizes create heavy-tailed workloads in which a single very long job can dominate makespan. The comparisons above use means over the same set of workloads for every policy, but no significance test was applied, and the ranking of policies on individual workloads can differ.

7.5 Threats to Validity

• Synthetic workload. Job sizes and speed-ups are random draws, not measurements from a real trace. Real speed-ups correlate with model architecture and batch size.
• Single-device, non-pre-emptive jobs. The simulator omits gangs, pre-emption, migration, interference and failures, all central to real schedulers (Chapter 5).
• Perfect information. The aware policies know each job's size and speed on each device. Real schedulers must estimate these [29][30], and estimation errors reduce the benefit.
• Batch arrival. Online arrivals and queueing delay, as studied in production traces [41], are not modelled.
• No fairness metric. LPT ordering would likely score poorly under finish-time fairness [34].

Given these limits, the study should be read as a controlled illustration of mechanisms, consistent in direction with the literature, not as independent confirmation of the magnitudes reported there.

Chapter 8. Challenges and Future Directions

8.1 Scaling and Complexity

Optimisation-based schedulers must make decisions over thousands of jobs and devices within seconds. Sia's formulation shows that heterogeneity awareness can scale to at least 2,000 GPUs [39], but larger and more diverse fleets, and richer objectives, will require approximation, decomposition and incremental re-solving, as in flow-based systems [23].

8.2 Performance Estimation

Heterogeneity-aware decisions depend on knowing how each job performs on each device. Profiling every job on every device is expensive. Collaborative-filtering and learned models reduce the cost [29][30], and Sia bootstraps throughput models with little profiling [39], but accuracy under new model architectures and new hardware generations remains a challenge. Integrating compilers and schedulers (Section 2.5) may supply better predictions [10].

8.3 Fairness, Strategy-Proofness and Incentives

When devices differ in value, defining what is a "fair share" is delicate. Finish-time fairness [34] and effective-throughput formulations [35] are steps forward, but users can game schedulers that rely on self-reported information, and hierarchical organisations need fairness at several levels. Multi-resource fairness with heterogeneous devices remains an active area.

8.4 Large Language Models and Extreme-Scale Jobs

Training and serving very large models require thousands of accelerators with specific topologies, tightly synchronised, and are affected by failures that become frequent at scale. Pod-slice-based allocation on TPU systems [7] and topology-aware placement [37] point the way, but the combination of extreme scale, long duration and reliability needs is largely beyond the cluster-level schedulers surveyed here. Serving workloads, with latency targets and bursty demand, also require co-design with batching and caching, which this thesis did not examine.

8.5 Energy and Sustainability

Accelerators consume substantial power, and heterogeneity offers a lever: routing jobs to the most energy-efficient device that meets their requirement. Gavel already supports cost-oriented policies [35]. Extending objectives to energy and carbon, including time-shifting workloads, is a promising direction, but this thesis did not evaluate it quantitatively.

8.6 Resource Disaggregation and Composable Infrastructure

Emerging architectures separate compute, memory and accelerators into pools linked by fast fabrics, allowing a job's resource "shape" to be composed on demand. This may dissolve the node boundary that today constrains placement, but it introduces new questions about latency, bandwidth and failure domains.

8.7 Learning-Based and Hybrid Approaches

Learned schedulers such as Decima [40] show that policies can be discovered automatically. Open issues are generalisation to new workloads, explainability, safety and the cost of training. Hybrid designs, in which a learned component proposes and an optimisation or rule-based layer verifies, are plausible near-term compromises.

8.8 Security and Isolation

Space sharing and multi-tenancy raise isolation concerns. Hardware partitioning offers strong isolation [49], but fine-grained sharing can leak performance information or enable interference attacks. A complete treatment of secure scheduling is outside the scope of this thesis.

8.9 Relevance for Smaller Institutions

The literature is dominated by hyperscale operators, yet universities and small research groups also operate mixed pools of old and new GPUs and CPUs. For them, the most valuable lessons are modest: label hardware accurately, queue jobs with explicit policy, measure per-job performance, and use mature tools such as Slurm or Kubernetes with Kueue before building custom systems (Section 6.7).

Chapter 9. Conclusion

This thesis examined heterogeneous hardware and advanced scheduling from hardware, theoretical, architectural, algorithmic and practical perspectives.

RQ1 (hardware). The end of Dennard scaling and the slowdown of Moore's Law pushed the industry toward specialised devices [1][2][3]. CPUs, GPUs, TPUs, FPGAs and the storage and network hierarchy differ in execution model, allocation granularity, sharing behaviour and flexibility, and the performance of a job depends on the specific job-device pair.

RQ2 (theory). The unrelated-machines model captures heterogeneity and is NP-hard, with LP-based approximations and list-scheduling heuristics as the main tools [11][51]. DAG workflows have heuristics such as HEFT [13], and multi-resource fairness is formalised by DRF [21].

RQ3 (architecture). Cluster scheduler design has moved from slots to resource vectors to typed devices, and from queue-based heuristics to optimisation formulations, through Mesos, YARN, Omega, Borg, Kubernetes, Sparrow, Apollo and Firmament [16][17][18][19][20][23][24][25].

RQ4 (mechanisms). Modern accelerator schedulers use profiling, time-slicing, space sharing, elasticity, topology-aware placement and checkpoint-based migration. Gavel and Sia illustrate that explicit heterogeneity awareness can produce large improvements in completion time and makespan under their authors' evaluations [35][39].

RQ5 (benefit). In the controlled simulation of Chapter 7, completion-time-based placement beat availability-based placement, naive use of the fastest hardware performed worst, and the choice of ordering traded makespan against average completion time. These results are synthetic and indicate direction rather than magnitude.

The main open problems are scalable decision-making, accurate performance estimation, fair and incentive-compatible allocation across heterogeneous devices, extreme-scale model training and serving, energy awareness and the narrowing of the gap between research prototypes and production tools. Future work could extend the simulation with gangs, pre-emption, online arrivals and estimation error, evaluate policies on public traces such as those published from production clusters, and prototype a heterogeneity-aware admission policy on top of Kueue or Slurm.

Appendix A. Glossary

Appendix B. Simulation Details

The simulation was implemented in Python with a standard library random-number generator. Job sizes follow lognormvariate(3.0, 0.9) in class-A hours. For each job a sensitivity value in the interval 0 to 1 is drawn, and speed-ups on classes B and C are computed as 1 plus a constant times the sensitivity times an independent uniform factor between 0.6 and 1.2, with the constants 1.5 for class B and 8.0 for class C, and class C forced to be at least as fast as class B. Workload seeds are 1000 to 1049. Each policy places jobs sequentially, tracking the time at which each device becomes free; the completion time of a job is the free time of its device after adding the job's size divided by its speed on that device.

Annotated Bibliography and Sources Used

This chapter lists every source used in the thesis, numbered as in the text, with a link and an annotation explaining what the source contributes and where it is used. Each entry carries a verification status:

• [V] Verified in this work: the title, authors, venue and key claims were checked against retrieved web pages during the preparation of this thesis (entries 35 and 39).
• [P] Publisher or DOI link recorded: the bibliographic details and the stable DOI or publisher link were recorded from the author's knowledge of the literature and were not re-opened during preparation. Before submission, the student should open each link, confirm that it resolves to the intended work, and read the source before relying on the claims attributed to it. Page numbers are given only where they were verified.

Sources fall into four groups: hardware and architecture (1 to 10), scheduling theory (11 to 15, 51), cluster-management systems and traces (16 to 31, 40 to 42, 50), deep-learning schedulers (32 to 39), and official documentation of practical tools (43 to 49). Documentation pages change over time; access them for the release you use.

[1] [P] H. Esmaeilzadeh, E. Blem, R. St. Amant, K. Sankaralingam, D. Burger. "Dark Silicon and the End of Multicore Scaling." Proceedings of the 38th International Symposium on Computer Architecture (ISCA), 2011.
https://doi.org/10.1145/2000064.2000108
Projects, using empirical device and application models, that power limits will prevent full use of future multicore chips. Used in Chapters 1 and 2 as the primary evidence for why heterogeneity and specialisation became necessary.

[2] [P] J. L. Hennessy, D. A. Patterson. "A New Golden Age for Computer Architecture." Communications of the ACM 62(2), 2019.
https://doi.org/10.1145/3282307
Turing Award lecture article arguing that, with Dennard scaling over and Moore's Law slowing, progress depends on domain-specific architectures. Used for the historical framing in Chapter 1 and Section 2.1.

[3] [P] W. J. Dally, Y. Turakhia, S. Han. "Domain-Specific Hardware Accelerators." Communications of the ACM 63(7), 2020.
https://doi.org/10.1145/3361682
Explains where accelerators obtain their efficiency (specialised operations, parallelism, local memory, reduced overhead). Used in Section 2.1 to justify device specialisation.

[4] [P] S. Mittal, J. S. Vetter. "A Survey of CPU-GPU Heterogeneous Computing Techniques." ACM Computing Surveys 47(4), 2015.
https://doi.org/10.1145/2788396
Broad survey of techniques for combining CPUs and GPUs, including work partitioning and scheduling. Background reading for Chapter 2; recommended as a starting point for readers new to the field.

[5] [P] J. E. Stone, D. Gohara, G. Shi. "OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems." Computing in Science and Engineering 12(3), 2010.
https://doi.org/10.1109/MCSE.2010.69
Introduces OpenCL as a portable programming model for heterogeneous devices. Cited in Sections 2.3.2 and 2.5 for programming-model portability.

[6] [P] N. P. Jouppi et al. "In-Datacenter Performance Analysis of a Tensor Processing Unit." Proceedings of the 44th ISCA, 2017.
https://doi.org/10.1145/3079856.3080246
Describes the first-generation TPU, its matrix-multiply unit and its performance and performance-per-watt compared with contemporary CPUs and GPUs. Source of the TPU figures in Section 2.3.3. A preprint is at https://arxiv.org/abs/1704.04760.

[7] [P] N. P. Jouppi et al. "TPU v4: An Optically Reconfigurable Supercomputer for Machine Learning with Hardware Support for Embeddings." Proceedings of the 50th ISCA, 2023.
https://doi.org/10.1145/3579371.3589350
Describes the TPU v4 system and its reconfigurable interconnect for large pods. Used in Sections 2.3.3 and 8.4 for slice-based allocation of accelerator pods.

[8] [P] A. Putnam et al. "A Reconfigurable Fabric for Accelerating Large-Scale Datacenter Services" (Catapult). Proceedings of the 41st ISCA, 2014.
https://doi.org/10.1109/ISCA.2014.6853195
Reports deployment of FPGAs in 1,632 servers for Bing ranking, with a large throughput gain at comparable latency. Used in Section 2.3.4 as the main evidence for FPGAs in data centres.

[9] [P] D. Firestone et al. "Azure Accelerated Networking: SmartNICs in the Public Cloud." 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2018.
https://www.usenix.org/conference/nsdi18/presentation/firestone
Describes FPGA-based SmartNICs offloading network virtualisation in Azure. Cited in Sections 2.3.4 and 2.3.6 to illustrate programmable hardware at the network edge.

[10] [P] T. Chen et al. "TVM: An Automated End-to-End Optimizing Compiler for Deep Learning." 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2018.
https://www.usenix.org/conference/osdi18/presentation/chen
Compiler that generates optimised code for diverse hardware back ends from a model description. Used in Sections 2.5 and 8.2 for portability and performance prediction.

[11] [P] R. L. Graham. "Bounds for Certain Multiprocessing Anomalies." Bell System Technical Journal 45(9), 1966.
https://doi.org/10.1002/j.1538-7305.1966.tb01709.x
Foundational analysis of list scheduling and the (2 - 1/m) bound. Basis of the agnostic baseline and of the LPT rule in Chapters 3 and 7.

[12] [P] C. L. Liu, J. W. Layland. "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment." Journal of the ACM 20(1), 1973.
https://doi.org/10.1145/321738.321743
Classical rate-monotonic and earliest-deadline-first results with utilisation bounds. Cited in Section 3.5 for deadline-driven scheduling.

[13] [P] H. Topcuoglu, S. Hariri, M.-Y. Wu. "Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing." IEEE Transactions on Parallel and Distributed Systems 13(3), 2002.
https://doi.org/10.1109/71.993206
Introduces the HEFT and CPOP algorithms for DAG scheduling on heterogeneous processors. Source of Section 3.4.

[14] [P] C. Augonnet, S. Thibault, R. Namyst, P.-A. Wacrenier. "StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures." Concurrency and Computation: Practice and Experience 23(2), 2011.
https://doi.org/10.1002/cpe.1631
Task runtime that schedules over CPUs and GPUs using performance models calibrated at run time. Cited in Sections 2.5, 3.4 and 5.5.

[15] [P] G. M. Amdahl. "Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities." AFIPS Spring Joint Computer Conference, 1967.
https://doi.org/10.1145/1465482.1465560
Original statement of Amdahl's law. Used in Section 3.8 to explain why accelerator speed-ups depend on the whole pipeline.

[16] [P] B. Hindman et al. "Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center." 8th USENIX NSDI, 2011.
https://www.usenix.org/conference/nsdi11/mesos-platform-fine-grained-resource-sharing-data-center
Presents two-level scheduling with resource offers. Main source for Section 4.3.

[17] [P] V. K. Vavilapalli et al. "Apache Hadoop YARN: Yet Another Resource Negotiator." ACM Symposium on Cloud Computing (SoCC), 2013.
https://doi.org/10.1145/2523616.2523633
Describes YARN's separation of resource management and application logic. Source for Section 4.3.

[18] [P] M. Schwarzkopf, A. Konwinski, M. Abd-El-Malek, J. Wilkes. "Omega: Flexible, Scalable Schedulers for Large Compute Clusters." EuroSys, 2013.
https://doi.org/10.1145/2465351.2465386
Proposes shared-state scheduling with optimistic concurrency. Source for Section 4.4.

[19] [P] A. Verma et al. "Large-Scale Cluster Management at Google with Borg." EuroSys, 2015.
https://doi.org/10.1145/2741948.2741964
Describes Google's production cluster manager, including scheduling, priorities, quotas and pre-emption. Source for Section 4.5 and the filter-and-score lineage in Section 6.1.

[20] [P] B. Burns, B. Grant, D. Oppenheimer, E. Brewer, J. Wilkes. "Borg, Omega, and Kubernetes." ACM Queue 14(1), 2016.
https://queue.acm.org/detail.cfm?id=2898444
Retrospective by the designers on how Borg and Omega influenced Kubernetes. Used in Sections 4.5 and 6.1.

[21] [P] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, I. Stoica. "Dominant Resource Fairness: Fair Allocation of Multiple Resource Types." 8th USENIX NSDI, 2011.
https://www.usenix.org/conference/nsdi11/dominant-resource-fairness-fair-allocation-multipleresource-types
Defines DRF and its fairness properties. Source of the worked example in Section 3.6.

[22] [P] M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar, A. Goldberg. "Quincy: Fair Scheduling for Distributed Computing Clusters." 22nd ACM SOSP, 2009.
https://doi.org/10.1145/1629575.1629601
Formulates scheduling as min-cost flow balancing locality and fairness. Source for Section 4.2.

[23] [P] I. Gog et al. "Firmament: Fast, Centralized Cluster Scheduling at Scale." 12th USENIX OSDI, 2016.
https://www.usenix.org/conference/osdi16/technical-sessions/presentation/gog
Shows that flow-based scheduling can be fast at scale. Source for Section 4.7.

[24] [P] K. Ousterhout, P. Wendell, M. Zaharia, I. Stoica. "Sparrow: Distributed, Low Latency Scheduling." 24th ACM SOSP, 2013.
https://doi.org/10.1145/2517349.2522716
Randomised, decentralised scheduling with batch sampling and late binding. Source for Section 4.6.

[25] [P] E. Boutin et al. "Apollo: Scalable and Coordinated Scheduling for Cloud-Scale Computing." 11th USENIX OSDI, 2014.
https://www.usenix.org/conference/osdi14/technical-sessions/presentation/boutin
Distributed scheduler with a global cost model used at Microsoft. Source for Section 4.6.

[26] [P] R. Grandl, G. Ananthanarayanan, S. Kandula, S. Rao, A. Akella. "Multi-Resource Packing for Cluster Schedulers." ACM SIGCOMM, 2014.
https://doi.org/10.1145/2619239.2626334
Applies multi-dimensional packing heuristics to cluster scheduling. Source for Section 3.7.

[27] [P] C. Reiss, A. Tumanov, G. R. Ganger, R. H. Katz, M. A. Kozuch. "Heterogeneity and Dynamicity of Clouds at Scale: Google Trace Analysis." ACM SoCC, 2012.
https://doi.org/10.1145/2391229.2391236
Analysis of a public Google cluster trace documenting diversity of machines and workloads. Used in Section 2.1 as evidence of real-world heterogeneity.

[28] [P] J. Dean, L. A. Barroso. "The Tail at Scale." Communications of the ACM 56(2), 2013.
https://doi.org/10.1145/2408776.2408794
Explains why rare latency outliers dominate at scale and how to mitigate them. Used in Section 5.1.

[29] [P] C. Delimitrou, C. Kozyrakis. "Paragon: QoS-Aware Scheduling for Heterogeneous Datacenters." ASPLOS, 2013.
https://doi.org/10.1145/2451116.2451125
Uses classification to select server configurations and avoid interference. Source for Section 5.1.

[30] [P] C. Delimitrou, C. Kozyrakis. "Quasar: Resource-Efficient and QoS-Aware Cluster Management." ASPLOS, 2014.
https://doi.org/10.1145/2541940.2541941
Determines resource amount and type from performance targets. Source for Section 5.1.

[31] [P] D. Lo, L. Cheng, R. Govindaraju, P. Ranganathan, C. Kozyrakis. "Heracles: Improving Resource Efficiency at Scale." ISCA, 2015.
https://doi.org/10.1145/2749469.2749475
Feedback control of isolation mechanisms to co-locate latency-critical and batch jobs. Source for Sections 3.5 and 5.1.

[32] [P] W. Xiao et al. "Gandiva: Introspective Cluster Scheduling for Deep Learning." 13th USENIX OSDI, 2018.
https://www.usenix.org/conference/osdi18/presentation/xiao
Time-slicing, migration and grow-shrink for GPU training clusters. Source for Section 5.3.1.

[33] [P] J. Gu et al. "Tiresias: A GPU Cluster Manager for Distributed Deep Learning." 16th USENIX NSDI, 2019.
https://www.usenix.org/conference/nsdi19/presentation/gu
Scheduling without known durations using two-dimensional attained service. Source for Sections 3.3 and 5.3.2.

[34] [P] K. Mahajan et al. "Themis: Fair and Efficient GPU Cluster Scheduling." 17th USENIX NSDI, 2020.
https://www.usenix.org/conference/nsdi20/presentation/mahajan
Finish-time fairness and auction-based allocation. Source for Sections 3.6 and 5.3.3.

[35] [V] D. Narayanan, K. Santhanam, F. Kazhamiaka, A. Phanishayee, M. Zaharia. "Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads." 14th USENIX OSDI, 2020, pp. 481-498.
https://www.usenix.org/conference/osdi20/presentation/narayanan-deepak
Gavel: expresses policies as optimisation problems using effective throughput, with round-based time-slicing and space sharing; reports up to 3.5x improvement in completion time and makespan over heterogeneity-agnostic policies. Verified during this work against the USENIX page, the arXiv version (https://arxiv.org/abs/2008.09213) and the authors' PDF (https://people.eecs.berkeley.edu/~matei/papers/2020/osdi_gavel.pdf). Central source for Chapters 3, 5 and 7.

[36] [P] W. Xiao et al. "AntMan: Dynamic Scaling on GPU Clusters for Deep Learning." 14th USENIX OSDI, 2020.
https://www.usenix.org/conference/osdi20/presentation/xiao
Framework-and-scheduler co-design for co-locating jobs at Alibaba. Source for Section 5.3.5.

[37] [P] H. Zhao et al. "HiveD: Sharing a GPU Cluster for Deep Learning with Guarantees." 14th USENIX OSDI, 2020.
https://www.usenix.org/conference/osdi20/presentation/zhao-hanyu
Cell abstraction for virtual private clusters. Source for Section 5.3.6.

[38] [P] A. Qiao et al. "Pollux: Co-adaptive Cluster Scheduling for Goodput-Optimized Deep Learning." 15th USENIX OSDI, 2021.
https://www.usenix.org/conference/osdi21/presentation/qiao
Goodput metric and joint tuning of resources and training hyper-parameters. Source for Section 5.3.7.

[39] [V] S. Jayaram Subramanya, D. Arfeen, S. Lin, A. Qiao, Z. Jia, G. R. Ganger. "Sia: Heterogeneity-Aware, Goodput-Optimized ML-Cluster Scheduling." 29th ACM SOSP, 2023, pp. 642-657.
https://doi.org/10.1145/3600006.3613175
Sia: schedules heterogeneous, resource-adaptive deep-learning jobs; reports large reductions in completion time and GPU hours and scaling to 2,000-GPU clusters. Verified during this work through the ACM DOI recorded on the authors' pages, the CMU Parallel Data Lab abstract (https://www.pdl.cmu.edu/PDL-FTP/BigLearning/sia_sosp23-final_abs.shtml) and the NSF-hosted paper (https://par.nsf.gov/biblio/10462590). Source for Section 5.3.8 and Chapter 8.

[40] [P] H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan, Z. Meng, M. Alizadeh. "Learning Scheduling Algorithms for Data Processing Clusters" (Decima). ACM SIGCOMM, 2019.
https://doi.org/10.1145/3341302.3342080
Reinforcement learning with graph neural networks for DAG job scheduling. Source for Sections 5.3.9 and 8.7.

[41] [P] M. Jeon, S. Venkataraman, A. Phanishayee, J. Qian, W. Xiao, F. Yang. "Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads." USENIX Annual Technical Conference (ATC), 2019.
https://www.usenix.org/conference/atc19/presentation/jeon
Analysis of a Microsoft GPU cluster: queueing, locality and failures. Source for Sections 1.1, 2.3.6 and 5.2.

[42] [P] Q. Weng et al. "MLaaS in the Wild: Workload Analysis and Scheduling in Large-Scale Heterogeneous GPU Clusters." 19th USENIX NSDI, 2022.
https://www.usenix.org/conference/nsdi22/presentation/weng
Workload analysis of a large production GPU cluster at Alibaba with heterogeneous GPUs. Source for Sections 1.1 and 5.2.

[43] [P] Kubernetes Documentation. "Device Plugins."
https://kubernetes.io/docs/concepts/extend-kubernetes/compute-storage-net/device-plugins/
Official documentation of how vendor devices are advertised to Kubernetes. Source for Section 6.1. Documentation changes with releases; check the version you use.

[44] [P] Kubernetes Documentation. "Scheduling Framework."
https://kubernetes.io/docs/concepts/scheduling-eviction/scheduling-framework/
Describes scheduler plugin extension points. Source for Section 6.1.

[45] [P] Kubernetes Documentation. "Dynamic Resource Allocation."
https://kubernetes.io/docs/concepts/scheduling-eviction/dynamic-resource-allocation/
Describes attribute-based device claims. Source for Section 6.1; feature maturity depends on release.

[46] [P] Kueue project documentation (Kubernetes SIGs).
https://kueue.sigs.k8s.io/
Job queueing, quotas and resource flavors. Source for Section 6.2.

[47] [P] Volcano project documentation (CNCF).
https://volcano.sh/
Batch scheduling system for Kubernetes with gang scheduling and queues. Source for Section 6.2.

[48] [P] SchedMD. "Slurm Workload Manager: Generic Resource (GRES) Scheduling."
https://slurm.schedmd.com/gres.html
Official documentation of GRES in Slurm. Source for Section 6.3.

[49] [P] NVIDIA. "NVIDIA Multi-Instance GPU User Guide."
https://docs.nvidia.com/datacenter/tesla/mig-user-guide/
Describes hardware partitioning of supported GPUs into isolated instances. Source for Sections 2.3.2, 5.5 and 8.8.

[50] [P] P. Moritz et al. "Ray: A Distributed Framework for Emerging AI Applications." 13th USENIX OSDI, 2018.
https://www.usenix.org/conference/osdi18/presentation/moritz
Describes Ray's task and actor model and bottom-up distributed scheduler. Source for Section 6.4.

[51] [P] J. K. Lenstra, D. B. Shmoys, E. Tardos. "Approximation Algorithms for Scheduling Unrelated Parallel Machines." Mathematical Programming 46, 1990.
https://doi.org/10.1007/BF01585745
Gives a 2-approximation for makespan on unrelated machines and a 3/2 inapproximability bound. Source for Section 3.2.

---

Research work by Aygul Nuryyeva, student of the International University for the Humanities and Development. Instructor: Nurmyrat Allayarov.