THINK FIRST·CODE LATER

← All labs

GPU cluster: pod-by-pod vs. gang scheduling

Problem

Simulate distributed training jobs on a GPU cluster.

Input: policy (partial or gang), number of GPUs, number of jobs, then per job name workers duration, then the list of pod requests (job names, one token per pod) — all arriving at time 0 in that order.

Events happen at integer times. At each event time:

  • partial: go through the waiting pods in order and give each one a free GPU if there is one (pods that get no GPU keep waiting, in order).
  • gang: go through the jobs in input order and give a job all its missing GPUs if enough are free (first fit — later, smaller jobs may start before earlier, bigger ones).
  • A job whose pods all have GPUs starts now (print t=0: JA starts on 6 GPUs, jobs in input order) and runs for its duration.
  • If no job is running at this point, print t=T: DEADLOCK, holding: JA=4/6 JB=4/6, free GPUs 0 (unfinished jobs, input order) and stop.
  • Otherwise advance to the next finish time; print t=10: JA finishes, frees 6 GPUs (input order) and release them; repeat.

When all jobs are done print All jobs finished, makespan T.

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

os8-4-data-1.txt

partial 8
2
JA 6 10
JB 6 10
JA JB JA JB JA JB JA JB JA JB JA JB
What your program must print for os8-4-data-1.txt
t=0: DEADLOCK, holding: JA=4/6 JB=4/6, free GPUs 0

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < os8-4-data-1.txt

Windows PowerShell does not understand <:

Get-Content os8-4-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.