Testing Guide for DR_EVT Scheduler

Overview

DR_EVT’s expected test outputs are generated by running scripts/python_reference_scheduler.py - a from-scratch, independently written EASY backfilling implementation - and recording what it produces. Agreement between the C++ simulator and the expected files means that the C++ implementation matches the Python reference implementation’s behavior. If both share the same misunderstanding of EASY backfilling, both would agree with each other and with the expected files while both being wrong in the same way.

What this means in practice: matching the expected output is a regression check (did this change alter scheduling behavior?), not proof of algorithmic correctness. For the smallest tests (2-5 jobs), it’s practical to hand-verify a computed schedule against the algorithm’s rules yourself if you want actual independent confirmation - see “Manual Verification” below. For larger tests, that’s not practical, and the expected file’s authority rests entirely on the Python reference being correct.

Quick Navigation

How to Run Tests

cd tests

# Run comprehensive test suite (34 tests)
./test_all_dr_evt.sh

# Run unit tests
./run_unit_tests.sh

# Run feature tests
./run_feature_tests.sh

# Run scale tests (manually, no wrapper script yet)
${CMAKE_INSTALL_PREFIX}/bin/simulator test_traces/scale/small_10jobs.csv --total_nodes 795 --run_time_mode limit

# Run replay tests
./run_replay_tests.sh

# Run streaming API tests (compiled binaries, installed under bin/tests/ - not shell scripts, so not in tests/)
${CMAKE_INSTALL_PREFIX}/bin/tests/test_streaming_api
${CMAKE_INSTALL_PREFIX}/bin/tests/test_batch_vs_streaming

# Run queue implementation differential tests (circular/deque/multimap/block)
./test_fcfs_comprehensive.sh --correctness

# Run column alias tests (time_limit/actual_run_time accepted column-name variants)
./test_column_aliases.sh

./test_run_time_modes.sh

Installed Test Binaries

make install installs the C++ test binaries (test_streaming_api, test_batch_vs_streaming, test_block_queue, test_mpi_streaming, test_grpc_multi_client_server, t_state, t_state_cereal, t_state_rngen, t_rngen) under ${CMAKE_INSTALL_PREFIX}/bin/tests/, separate from the production binaries (simulator, tracer, dr_evt_server, dr_evt_client) directly under ${CMAKE_INSTALL_PREFIX}/bin/:

${CMAKE_INSTALL_PREFIX}/bin/tests/test_streaming_api
${CMAKE_INSTALL_PREFIX}/bin/tests/t_state

Comprehensive Tests

Location: tests/test_traces/comprehensive/ Total: 34 tests organized in 9 tiers Node count: 100 Purpose: Verify EASY backfilling scheduler correctness

Expected outputs generated by: Python reference implementation (scripts/python_reference_scheduler.py)

How to run a single test:

cd build
${CMAKE_INSTALL_PREFIX}/bin/simulator ../tests/test_traces/comprehensive/01_backfill_allowed.csv \
    --total_nodes 100 \
    --run_time_mode limit \
    --outfile /tmp/output.csv

# Compare with expected
diff /tmp/output.csv ../tests/test_traces/comprehensive/01_backfill_allowed.expected_output.csv

Test artifacts for each test:

  • [test_name].csv - Input trace (job arrivals)

  • [test_name].expected_output.csv - Expected job schedule

  • [test_name].expected_resources.csv - Expected resource timeline

  • [test_name].construction.md - Scenario description

  • [test_name].answer.json - Test constraints (not validated by scripts)

Tier 1-2: FCFS & Basic Backfilling (10 tests)

Test

Description

Jobs

Key Feature

Artifacts

01_backfill_allowed

Small job backfills while large job waits

3

Basic backfill

Input · Expected · Desc

02_backfill_blocked_time

Job too long for backfill window

3

Time constraint

Input · Expected · Desc

03_backfill_blocked_resources

Job too large for available nodes

3

Resource constraint

Input · Expected · Desc

04_backfill_resource_competition

Multiple small jobs compete for backfill

4

FCFS among backfillers

Input · Expected · Desc

05_multiple_backfills

Two jobs backfill simultaneously

4

Concurrent backfills

Input · Expected · Desc

06_backfill_out_of_order

Later job backfills before earlier

4

Out-of-order execution

Input · Expected · Desc

07_simultaneous_submit

Jobs arrive at same time

3

Tie-breaking

Input · Expected · Desc

08_simultaneous_completion

(no verified description)

5

-

Input · Expected

09_simultaneous_submit_complete

(no verified description)

2

-

Input · Expected

10_queue_drain_idle

System goes idle between jobs

3

Idle periods

Input · Expected · Desc

Tier 3-4: Event Timing & Competition (9 tests)

Tests where job completions and arrivals interact in complex ways.

Note: the descriptions below are inferred from each test’s name and job count only - the earlier implementation of this table had invented, unverified descriptions that didn’t match the actual trace files. Where a .construction.md file exists, it’s linked as the authoritative description; where it doesn’t, treat the name as the only claim being made.

Test

Jobs

Artifacts

11_multiple_drains

3

Input · Expected

12_drain_with_backlog

3

Input · Expected

13_consecutive_fcfs

3

Input · Expected · Desc

14_fcfs_with_backfill

3

Input · Expected

15_fcfs_partial_overlap

3

Input · Expected

16_starvation_prevention

31

Input · Expected

17_late_large_priority

21

Input · Expected

18_backfill_no_starvation

12

Input · Expected

19_resource_fragmentation

4

Input · Expected

Tier 5: Fragmentation & Sustained Load (5 tests)

Test

Jobs

Artifacts

20_fragmentation_recovery

4

Input · Expected

21_sustained_high_load

50

Input · Expected

22_bursty_load

20

Input · Expected

23_mixed_load

30

Input · Expected

24_multiple_running_jobs

4

Input · Expected · Desc

Tier 6-9: Completion Interactions & Backfill Edge Cases (10 tests)

Jobs completing early (actual_run_time < time_limit) and other backfill edge cases - see Run Time Mode Tests above for the run_time_mode mechanics these traces exercise.

Test

Jobs

Artifacts

25_early_completion_basic

3

Input · Expected

26_early_completion_cascading

4

Input · Expected

27_early_vs_late_completion

4

Input · Expected

28_simultaneous_completions_backfill

6

Input · Expected · Desc

29_large_completion_multiple_backfills

5

Input · Expected · Desc

30_fcfs_blocked_backfill_past

3

Input · Expected · Desc

31_completion_arrival_with_queue

4

Input · Expected · Desc

32_simultaneous_backfill_with_reservation

4

Input · Expected · Desc

33_five_simultaneous_events

6

Input · Expected · Desc

34_backfill_overallocation

4

Input · Expected · Desc

Status: 34/34 passing

Unit Tests

Location: tests/test_traces/unit/ Total: 7 tests Purpose: Basic I/O, trace format parsing, simple scenarios

How to run:

cd build
../tests/run_unit_tests.sh

Test

Description

Key Feature

Status

Artifacts

simple_2jobs.csv

2-job sequential execution

Basic CSV parsing

✅ Working

Input

sequential_3jobs.trace

3-job replay format

Tab-separated format

✅ Working

Input

timestamp_epoch_format.csv

Epoch timestamp format

Unix timestamps

✅ Working

Input

timestamp_iso_format.csv

ISO 8601 timestamps

ISO format parsing

✅ Working

Input

timezone_handling.csv

Timezone handling

Timezone conversion

✅ Working

Input

sequential_3jobs.csv

3-job sequential

Simple scenario

✅ Working

Input

simple_basic.csv

Basic 2-job test

Format test

✅ Working

Input

Status: 7/7 passing (fixed Aug 31, 2026 in commit e6da09c)

Known Issue: queue field must be pbatch or pbatch0-3. Other values (e.g., "batch") are silently dropped during load.

Feature Tests

Location: tests/test_traces/feature/ Total: 6 tests Purpose: Compare different scheduling policies and modes

How to run:

cd build
../tests/run_feature_tests.sh

Test

Description

Comparison

Status

Artifacts

conservative_backfill.csv

Conservative vs EASY

Backfill policies

✅ Passing

Input

msec_basic.csv

Millisecond output

Whole-second timestamps

✅ Passing

Input

msec_fractional.csv

Millisecond output

Fractional timestamps

✅ Passing

Input

rejected_job.csv

Oversized-job rejection

Rejected job is excluded from output

✅ Passing

Input

sustained_replay.csv

Replay mode validation

Replay vs simulation

✅ Passing

Input

sustained_simulation.csv

Long-running simulation

Sustained load

✅ Passing

Input

Status: 6/6 passing

Note: easy_vs_conservative_test.csv is run separately by tests/test_easy_vs_conservative_correctness.sh; it validates against algorithm-specific expected outputs rather than a shared oracle.

Scale Tests

Location: tests/test_traces/scale/ Total: 7 tests Node count: 795 (not 100 - matches default in src/dr_evt_types.hpp) Purpose: Large-scale performance testing

How to run:

cd build
${CMAKE_INSTALL_PREFIX}/bin/simulator ../tests/test_traces/scale/small_10jobs.csv \
    --total_nodes 795 \
    --run_time_mode limit \
    --outfile /tmp/output.csv

# Compare with expected
diff /tmp/output.csv ../tests/test_traces/scale/small_10jobs.expected_output.csv

Test

Jobs

Status

Description

Artifacts

small_10jobs.csv

10

✅ Passing

Small baseline

Input · Expected

medium_50jobs.csv

50

✅ Passing

Medium scale

Input · Expected

large_100jobs.csv

100

✅ Passing

Large scale

Input · Expected

large_200jobs.csv

200

✅ Passing

Large scale

Input · Expected

xlarge_500jobs.csv

500

✅ Passing

Extra large scale

Input · Expected

huge_2000jobs.csv

2000

✅ Passing

Huge scale

Input · Expected

huge_10000jobs.csv

10000

✅ Passing

Huge scale

Input · Expected

Status: 7/7 passing

Generated via scripts/generators/generate_scale_expected_outputs.py.

Replay Tests

Location: tests/run_replay_tests.sh Purpose: Verify replay mode reproduces resource usage from simulation

How it works:

  1. Run simulation mode → generates job schedule + resource trace

  2. Feed schedule back as replay mode input

  3. Compare resource traces → must match exactly

How to run:

cd build
../tests/run_replay_tests.sh

Tests hardcoded in script:

  • comprehensive/01_backfill_allowed.csv

  • comprehensive/05_multiple_backfills.csv

  • comprehensive/13_consecutive_fcfs.csv

  • comprehensive/21_sustained_high_load.csv

Verified to pass on: All 34 comprehensive tests + 4 scale tests

Resource History Tests

Location: tests/run_resource_history_tests.sh Purpose: Verify the resource-history circular buffer (--resource_history_capacity) produces identical output under forced reclaiming, that invalid input is rejected cleanly, and measure the wall-clock cost of repeated flushing at a too-small capacity

Note: unlike job-store’s m_data, resource-history genuinely accumulates incrementally during the run (not preloaded), and has no grow option - so a too-small capacity here causes real, repeated flush-and-discard for the whole run, not a one-time reallocation. Sufficient capacity is 2x the job count (each job contributes at most 2 events - start, end), not 1x.

How it works:

  1. Run each input twice: once with the default (auto-sized) capacity, once with a small forced capacity (5) that triggers reclaiming on nearly every insert

  2. Compare resource traces → must match exactly, for both simulator and tracer

  3. Separately, feed tracer simulation-format input directly (never valid for run_job_trace(), which only replays begin_time/end_time that’s already set) → must fail cleanly with an actionable error, not crash

  4. Benchmark (informational, not pass/fail): wall-clock time for a tiny (5) vs. sufficient (2x job count) capacity on a 10,000-job trace - confirms repeated flushing is cheap and output-identical

How to run:

cd build
../tests/run_resource_history_tests.sh

Tests hardcoded in script:

  • feature/05_multiple_backfills.csv (simulator)

  • feature/21_sustained_high_load.csv (simulator)

  • feature/huge_2000jobs.csv (tracer, via simulator’s own replay-format output)

  • feature/huge_2000jobs.csv (tracer, fed directly - misuse-rejection check)

  • feature/huge_10000jobs.csv (flush-overhead benchmark)

Job Store Tests

Location: tests/run_job_store_tests.sh Purpose: Verify the job-store circular buffer (Trace::m_data, --job_store_capacity) produces identical output and stats regardless of the requested initial capacity, correctly excludes rejected jobs without stalling, aborts cleanly when capacity can’t be satisfied, and measures the wall-clock cost of a too-small initial capacity

Batch mode note: loading a whole trace file (the only mode that exists today) sizes capacity to fit the entire trace before the run starts - a too-small --job_store_capacity triggers repeated reallocation during loading (falling back to growing), not repeated reclaiming during the run, which essentially can’t happen more than once in batch mode - see docs/dev/design-decisions/OUT_TRACE_STREAMING.md.

How it works:

  1. Run each input twice: once with the default (already-sufficient) capacity, once with a tiny requested capacity (2) that forces several grow reallocations during loading

  2. Compare job output and simulation stats → must match exactly

  3. Separately, run a small trace at default capacity → confirm no job is reclaimed prematurely (guards against a real bug found during development: an earlier version reclaimed unconditionally whenever a job finished, rather than only when the buffer was actually full)

  4. Feed a trace with one job that requests more nodes than exist → confirm it’s rejected, excluded from output/stats, and doesn’t stall completion of the jobs behind it

  5. Force --job_store_overflow abort with a capacity too small to hold the trace even during loading → must fail cleanly with an actionable error, not crash

  6. Benchmark (informational, not pass/fail): wall-clock time for a tiny vs. sufficient initial capacity on a 10,000-job trace - confirms grow-during-load is cheap and output-identical

How to run:

cd build
../tests/run_job_store_tests.sh

Tests hardcoded in script:

  • feature/05_multiple_backfills.csv

  • feature/21_sustained_high_load.csv

  • feature/01_backfill_allowed.csv (default-capacity and abort checks)

  • feature/rejected_job.csv

  • feature/huge_10000jobs.csv (grow-overhead benchmark)

Append-Job Tests

Location: tests/test_append_job_api.cpp (C++), tests/test_append_job_grpc.cpp (gRPC) Purpose: Verify Trace::append_job()/Simulation::append_job() (single-job) and Trace::append_jobs()/Simulation::append_jobs() (batch) - the real streaming insertion points, for jobs the trace has never seen before - together with submit_job()/advance_to()’s general correctness (online scheduling loops, exclusive-vs-inclusive advance, resource-leak checks, idle-gap handling), all driven via append_job()/append_jobs() rather than a preloaded trace file. This file used to be two (a separate test_streaming_api.cpp covered the submit_job()/advance_to() half by loading a small, hand-written CSV first) - consolidated once it became clear none of those tests actually depended on a preloaded file (each one’s submit times were hand-written to match the CSV exactly, never diverging from it), so the same coverage is achievable via append_job() with no file needed at all.

How it works:

  1. (C++) A trace with zero preloaded jobs (empty-of-rows CSV), then jobs appended one at a time via append_job() and run to completion → output/stats must be correct

  2. (C++) Force --job_store_capacity 1; confirm a second append_job() call reclaims the first (already-finished) job’s slot rather than growing - the actual point this ordering matters, unlike load_data() (see docs/dev/design-decisions/OUT_TRACE_STREAMING.md’s “Reclaim at the point of need” section for why load_data() itself never needs this)

  3. (C++) append_job() enforces the same submit_time >= current_time precondition submit_job() already does → must throw on a past submit_time

  4. (C++) append_jobs() batch call - several jobs in one call, run to completion → output/stats must be correct

  5. (C++) append_jobs() rejects a batch not sorted by submit_time, non-decreasing - and, being all-or-nothing on input validation, leaves m_data completely untouched

  6. (C++) append_jobs() rejects a batch containing any submit_time < current_time - same all-or-nothing input validation, nothing from the batch is added

  7. (C++) Reclaim-before-grow (test 2’s guarantee) holds the same way within a batch call - each request goes through the same per-job order, not a single capacity computation for the whole batch upfront

  8. (C++) append_jobs() over an empty request vector is a valid no-op

  9. (C++) Basic append+submit+advance sequencing, exclusive-vs-inclusive advance_to()/run_until_exclusive(), an online-scheduling loop that appends jobs only as they “arrive,” sequential resource-leak detection, and advance_to()’s idle-gap postcondition across a long gap with no pending events

  10. (gRPC, if built with -DDR_EVT_ENABLE_GRPC=ON) Same append scenario as (1), but over the actual network wire via AppendJobRequest, against a real running dr_evt_server, plus the batch case via AppendJobsRequest

  11. (C++) submit_job() records busy_nodes (other jobs’ node occupancy at arrival) for a streaming-arrived job, same as load_data()’s own submission loop already does for a batch-loaded one

  12. (C++) append_jobs() honors --check_memory_pressure the same way load_next_file() (progressive loading) does, since both share ensure_batch_capacity() - forced deterministically via the DR_EVT_TEST_AVAILABLE_MEMORY_BYTES test seam

How to run:

cd build
../tests/run_append_job_tests.sh

Tests hardcoded in script:

  • feature/empty_trace.csv (gRPC test - header-only, zero data rows)

Progressive Loading Tests

Location: tests/test_progressive_load.cpp (C++), tests/run_progressive_load_tests.sh (both wraps the C++ binary and runs CLI-level checks) Purpose: Verify --infile_list/Trace::load_next_file()/Simulation::run_progressive() - loading a trace as a sequence of separate, pre-sorted files instead of one big one, so --job_store_capacity can actually bound memory (single-file mode always grows to fit the whole trace regardless of this setting; see docs/dev/design-decisions/OUT_TRACE_STREAMING.md)

How it works:

  1. (C++) The same 6 jobs split across 3 files vs. one combined file must produce byte-identical output - splitting the input shouldn’t change the schedule

  2. (C++) With a small --job_store_capacity and job durations short enough that earlier jobs finish before later files load, progressive mode’s peak m_data capacity must stay well below single-file mode’s (confirmed as an honest baseline, not assumed - single-file mode always grows to fit the whole trace)

  3. (C++) --job_store_overflow=abort must throw cleanly, not crash, when a file’s jobs can’t fit even after reclaiming

  4. (C++) An empty file (header only) in the middle of the list must be skipped gracefully, not treated as an error

  5. (C++) A later file whose earliest submit_time precedes the previous file’s latest must be rejected (cross-file continuity)

  6. (C++) REPLAY-format input must be rejected outright for --infile_list - there’s no scheduling decision for progressive loading to plug into for replay at all

  7. (C++) --check_memory_pressure must refuse to load the next file when doing so would push projected job-store usage past the configured fraction of actual available memory - forced deterministically via the DR_EVT_TEST_AVAILABLE_MEMORY_BYTES test seam, not by depending on the test machine’s real memory state

  8. (C++) The same forced-low-memory condition must NOT affect a run that never enables --check_memory_pressure - the check is opt-in, not a background limit

  9. (C++) With --check_memory_pressure enabled but no artificially low memory forced, a normal run must still succeed - no false positive against real, plentiful memory

  10. (C++) The fraction itself is what’s compared against, not a fixed threshold hiding behind a configurable-looking argument - under the exact same forced available-memory condition, a tight fraction must refuse while a loose fraction succeeds

  11. (CLI) The same split-vs-combined comparison as (1), but through the actual simulator --infile_list invocation, exercising Sim_Params::getopt()’s real parsing path

  12. (CLI) The same small-capacity run as (2), confirmed to still produce the correct schedule end-to-end

  13. (CLI) An empty --infile_list file is rejected with a clear error

  14. (CLI) --infile_list together with a positional trace-file argument is rejected (mutually exclusive)

How to run:

cd build
../tests/run_progressive_load_tests.sh

Tests hardcoded in script:

  • progressive/part1.csv, part2.csv, part3.csv, combined.csv, file_list.txt

Streaming API Tests

Location: tests/ Purpose: Test online job submission API

Test

Language

Description

How to Run

test_batch_vs_streaming.cpp

C++

Batch vs streaming equivalence

./build/tests/test_batch_vs_streaming

test_python_api.py

Python

Python bindings

python tests/test_python_api.py

mpi_job_feeder.cpp

C++ (MPI)

Parallel job submission

mpirun -n 4 ./build/tests/mpi_job_feeder

Configuration Tests

Location: tests/test_configs/ (hand-crafted fixtures), tests/test_protobuf_config_doc_examples.py (documentation’s own examples) Purpose: Verify protobuf config files match CLI options, and separately, that every example shown in docs/user-guide/protobuf-config.md actually parses and runs - not just the hand-verified fixtures below, which by construction can never expose a bug in the documentation’s own prose (this caught two real ones: every doc example wrapping fields in a fictional sim_setup { ... } block, and several “Run with” instructions omitting the required positional trace-file argument - see the script’s own docstring for the full story)

How to run:

cd build
cmake .. -DDR_EVT_ENABLE_PROTOBUF=ON
make
../tests/run_configs_tests.sh

Config files tested:

  • minimal_config.pb

  • conservative_config.pb

  • full_config.pb

  • distribution_config.pb

  • resource_trace_config.pb

  • infile_list_config.pb (progressive loading via a protobuf config, not just the CLI)

  • memory_pressure_config.pb (memory_pressure_fraction via a protobuf config, forced to trigger via the DR_EVT_TEST_AVAILABLE_MEMORY_BYTES test seam)

Queue Implementation Testing

Location: tests/test_traces/comprehensive/ (same 34 traces as the Comprehensive Tests above) Purpose: Verify all four FCFS wait-queue data structure implementations (--queue_impl circular/deque/multimap/block) produce byte-for-byte identical output to each other

This checks something different from the Python-reference comparison the rest of this guide describes: not whether the C++ simulator’s scheduling decisions are correct, but whether swapping the underlying queue data structure changes the result. It won’t catch a bug shared by all four implementations, but it will catch a bug introduced in one specific implementation while the others stay correct - something the Python-reference comparison above wouldn’t specifically localize.

circular is the default (--queue_impl unset uses it); deque, multimap, and block all still need to be requested explicitly.

How to run:

cd build
../tests/test_fcfs_comprehensive.sh --correctness

Performance comparison (not correctness - separate script):

../tests/benchmark_block_sizes.sh

Runs in CI (.github/workflows/tests.yml, “Run Queue Implementation Differential Tests”). See dev/design-decisions/CIRCULAR_QUEUE.md for the default implementation and dev/design-decisions/BLOCK_QUEUE.md for the block-based one.

Column Alias Tests

Location: tests/test_column_aliases.sh (generates its own small traces under /tmp/) Purpose: Verify time_limit and actual_run_time are each recognized under multiple accepted column-name aliases, so an existing trace can be reused without editing its header - slow to do by hand on a large file.

  • time_limit accepts: time_limit, timelimit, walltime

  • actual_run_time accepts: actual_run_time, duration, actual_duration, run_time

8 checks: one per alias (confirming both that it’s recognized and that it drives the correct execution time), plus one confirming a trace missing time_limit under all of its aliases is rejected with a clear error rather than silently defaulting.

How to run:

cd build
../tests/test_column_aliases.sh

Runs in CI (.github/workflows/tests.yml, “Run Column Alias Tests”). See user-guide/trace-formats.md for the full column reference.

Run Time Mode Tests

Location: tests/test_run_time_modes.sh Purpose: Verify two specific behavioral contracts not exercised by any other test suite:

  1. Replay mode uses the trace’s own real, historical begin/end times - confirmed using test_traces/comprehensive/25_early_completion_basic.csv, where time_limit and actual_run_time genuinely differ (200s vs 50s).

  2. run_time_mode=distribution’s normal/lognormal samples are capped at time_limit - a real HPC scheduler kills a job at its stated limit, so the simulator must respect the same constraint. Checked against 10,000 jobs for a statistically reliable result.

How to run:

cd build
../tests/test_run_time_modes.sh

Runs in CI (.github/workflows/tests.yml, “Run Duration/Run Time Mode Tests”). See reference/terminology.md for

Test Summary

Category

Total

Passing

Broken

Purpose

Comprehensive

34

34

0

Scheduler correctness

Unit

7

7

0

Basic I/O & formats

Feature

6

6

0

Policy comparisons, output formats, and rejection handling

Conservative

2

2

0

CONSERVATIVE backfilling

Scale

7

7

0

Performance testing

Replay

4

4

0

Resource verification

Resource History

5

5

0

Resource-history circular buffer, flush overhead

Job Store

6

6

0

Job-record circular buffer, capacity sizing

Append-Job

17

17

0

Streaming insertion (append_job/append_jobs) + submit_job()/advance_to()

Progressive Loading

14

14

0

–infile_list, bounding job-store memory across a multi-file trace

Streaming

4

4

0

Online API

Config

7

7

0

Protobuf validation

Queue Impl

34

34

0

Wait-queue data structure consistency (circular/deque/multimap/block)

Column Aliases

8

8

0

time_limit/actual_run_time accepted column-name variants

TOTAL

158+

158+

0

Complete test suite

All tests passing as of Sept 3, 2026

Test File Formats

Input Trace (.csv)

job_submit_time,num_nodes,exit_status,queue,time_limit[,actual_run_time]
0,70,0,pbatch,200
10,50,0,pbatch,300
20,20,0,pbatch,50

  • actual_run_time optional (defaults to time_limit); used for early completion tests. Also accepted under the names duration, actual_duration, or run_time; time_limit is also accepted under timelimit or walltime - useful for reusing an existing trace without editing its header.

  • queue must be pbatch (or pbatch0-pbatch3) - other values are silently dropped during load (see src/trace/job_io.cpp), producing zero loaded jobs with no error. This is not a cosmetic requirement.

Expected Job Output (.expected_output.csv)

job_id,start_time,end_time
0,0,200
1,200,500
2,20,70

job_id corresponds to input row order (0-indexed), which is safe even when multiple jobs share a submit time: the simulator internally stable-sorts by submit time at load, and all comprehensive//scale/ input files are already submit-time-sorted on disk, so this sort is a no-op and row order is preserved.

Expected Resource Timeline (.expected_resources.csv)

Two conventions exist in this repo - check which one a given test uses before writing tooling against it:

time,nodes_used,nodes_free,running_jobs
0,70,30,0
20,90,10,"0,2"

(comprehensive/, scale/ - via the Python reference generators)

time,free_nodes,allocated_nodes
0,30,70
20,10,90

(the C++ simulator’s own --resource_trace output - note the swapped column order and no running_jobs column)

Answer File (.answer.json)

{
  "test_id": "01_backfill_allowed",
  "exact_schedule": [[0,0,200], [1,200,500], [2,20,70]],
  "constraints": [...]
}

exact_schedule: null marks tests where multiple schedules could be valid (e.g. 21_sustained_high_load, deliberately dense/high-contention scenarios). No script in this repo currently validates these .answer.json constraint files - they document intent but aren’t enforced. Don’t assume a test with a well-formed .answer.json is actually being checked against it.

Generating Expected Outputs

All expected outputs are generated by the Python reference implementation:

# Comprehensive tests (34 tests)
python scripts/generators/generate_all_expected_outputs.py

# Scale tests (7 tests)
python scripts/generators/generate_scale_expected_outputs.py

Python reference: scripts/python_reference_scheduler.py Verification: 34/34 comprehensive tests match Python reference

Adding New Tests

  1. Create the input trace under the appropriate directory (comprehensive/, scale/, unit/, or feature/), using pbatch as the queue name.

  2. Run the relevant generator script (generate_all_expected_outputs.py or generate_scale_expected_outputs.py) to produce .expected_output.csv / .expected_resources.csv. Don’t hand-write these - see the Overview above for why that would just duplicate the Python reference’s own computation, badly.

  3. For a genuinely independent check on a small test (2-5 jobs), trace the EASY algorithm by hand yourself and compare - this is the only way to get real independent verification in this suite, and it doesn’t scale to larger tests. If reference implementation passes all of such verifications, the comparison against the reference becomes more useful.

  4. If adding to comprehensive/, add the test name to the TESTS list in generate_all_expected_outputs.py; same for scale/ and its generator.

Common Test Patterns

3-Job Backfill Pattern

Job 0: Running (R0 nodes, duration D0)
Job 1: FCFS head, CANNOT fit (R1 > free)
Job 2: Backfiller, CAN fit (R2 <= free)

Question: Can Job 2 backfill? Check: does Job 2 complete strictly before Job 1’s reservation time? (Strict <, not <= - resources don’t free up instantly when a job completes; the completion event has to be processed first.)

Multiple Running Jobs Pattern

Job 0: R0 nodes, ends at T0
Job 1: R1 nodes, ends at T1 > T0
Job 2: FCFS head, needs more than either alone frees

Reservation is whichever completion time first provides enough cumulative freed capacity - not necessarily T0 or T1 alone.

Early Completion Pattern

Job 0: time_limit=200, actual_run_time=50
Job 1: FCFS head, reservation calculated using 200 (the estimate), not 50

Result: Job 1’s reservation is pessimistic (based on the estimate), but Job 0 actually frees resources at 50 - so anything backfilling against Job 0’s completion benefits from the earlier, actual time once it happens.

Troubleshooting

Test Fails: Schedule Mismatch

  1. Read the test’s construction.md (if present) to understand the intended scenario - but verify it against the actual current behavior first; at least one (29_large_completion_multiple_backfills) has a stale narrative that doesn’t match its own correct, validated schedule.

  2. Manually trace through the EASY algorithm’s rules for the specific jobs involved.

  3. Check whether the expected file might be the one that’s wrong, especially for scale/-style tests that lack a generator history - this has happened before (see tests/test_traces/README.md).

All Tests Pass but Behavior Seems Wrong

Passing tests here means “matches the Python reference,” not “definitely correct” - see the Overview. If you suspect a specific scenario is mishandled, trace it by hand rather than trusting a passing test to rule it out.

Conservative Backfilling Tests

DR_EVT implements both EASY and CONSERVATIVE backfilling algorithms. Conservative backfilling provides stronger fairness guarantees by protecting ALL waiting jobs’ reservations, not just the first job.

Algorithm Comparison

Aspect

EASY

CONSERVATIVE

Reservation

Only first job in queue

ALL jobs in queue

Backfill Check

Complete before first job’s reservation?

Complete before ANY job’s reservation?

Complexity

O(n) per scheduling event

O(n²) per scheduling event

Fairness

Lower - deep queue jobs can be delayed

Higher - all jobs protected

Utilization

Higher (~95% on 2000-job test)

Lower (~87% on 2000-job test)

Makespan

Shorter

Longer (+9% on 2000-job test)

Performance

Fast (0.05s for 2000 jobs)

Slow (144s for 2000 jobs, 2715x slower)

Test 1: Behavioral Correctness (EASY vs CONSERVATIVE)

Purpose: Demonstrates the key behavioral difference between algorithms Script: tests/test_easy_vs_conservative_correctness.sh Duration: ~1 second Jobs: 6 jobs, 100 nodes

Key Scenario:

Running at t=0:
  Job 0: 60 nodes, ends at t=50
  Job 1: 20 nodes, ends at t=100
  Free: 20 nodes

Waiting queue (FCFS order):
  Job 2: 50 nodes, duration 200 → reservation at t=50
  Job 3: 30 nodes, duration 50  → reservation at t=50
  Job 4: 15 nodes, duration 100 → reservation at t=0 (could start now!)
  Job 5: 10 nodes, duration 40  → BACKFILL CANDIDATE

Expected Behavior:

  • EASY: Job 5 backfills at t=0 (only checks Job 2’s reservation, 40 < 50 ✓)

  • CONSERVATIVE: Job 5 delayed to t=100 (checks Job 4’s reservation, 40 > 0 ✗)

Job 4 could start immediately but is behind Jobs 2-3 in the queue. EASY ignores Job 4’s reservation and backfills Job 5, delaying Job 4. CONSERVATIVE protects Job 4’s reservation and rejects Job 5.

Run:

./tests/test_easy_vs_conservative_correctness.sh

Success Criteria:

  • ✅ Job 5 starts at t=0 with EASY

  • ✅ Job 5 starts at t=100 with CONSERVATIVE

  • ✅ All job schedules match expected output

  • ✅ Resource traces match expected utilization

Test 2: Implementation Equivalence (C++ vs Python)

Purpose: Verifies C++ and Python CONSERVATIVE implementations produce identical schedules Script: tests/compare_cpp_python_conservative.sh Duration: ~8 minutes Jobs: 2000 jobs, 400 nodes (default)

What it tests:

  • Both implementations follow the same algorithm

  • Schedules match exactly (start/end times for all jobs)

  • No divergence on complex, long-running simulations

  • Performance comparison (C++ vs Python)

Run:

# Default: 2000 jobs, 400 nodes
./tests/compare_cpp_python_conservative.sh

# Custom trace and node count
./tests/compare_cpp_python_conservative.sh <trace.csv> <nodes> <output_dir>

Success Criteria:

  • ✅ Same number of jobs completed

  • ✅ All job start times match (within 0.001s)

  • ✅ All job end times match (within 0.001s)

  • ✅ Makespan is identical

Verified Results (2000 jobs, 400 nodes):

Jobs compared:  2000
Mismatches:     0
Python time:    504s (8m24s)
C++ time:       143.9s (2m24s)
Speedup:        3.5x
Makespan:       993,969 seconds (identical)
Utilization:    87.13% (identical)

Conservative Backfilling Implementation

C++ Implementation:

  • Location: src/sim/scheduler_fcfs_conservative.cpp

  • Key method: try_backfill()

  • Complexity: O(n²) - calculates reservations for all waiting jobs

  • Optimization: Uses pre-built resource timeline

  • Queue: Currently only std::deque implementation (circular buffer variant not yet implemented for ~10-15% potential speedup)

Python Reference:

  • Location: scripts/python_conservative_scheduler.py

  • Key method: try_start_jobs()

  • Purpose: Reference implementation for verification

  • Note: ~3.5x slower than C++ due to interpreter overhead

Critical Implementation Details: Both implementations must:

  1. Track effective running jobs (actual running + backfilled this cycle)

  2. Calculate reservations using effective running state

  3. Exclude already-backfilled jobs from window calculation

  4. Update effective running as jobs backfill within the same scheduling event

Test Data Files

Behavioral test:

Equivalence test:

References

Key Principles

  1. No independent ground truth: expected outputs come from the Python reference implementation, not from first-principles calculation.

  2. Passing tests demonstrate consistency, not correctness: a shared bug between implementations would still pass.

  3. Hand-verification is only practical for small tests: use it when you need actual confidence beyond “matches the reference.”

  4. Some scenarios genuinely have no unique correct schedule: see exact_schedule: null in .answer.json files.

  5. Not everything documented here is validated by running code: the .answer.json constraints and the config tests both need protobuf/ manual verification this document didn’t perform - check before assuming.