fragmentation-aware-packing

Fragmentation-Aware Packing

Use this skill when several feasible placements exist and the choice affects future capacity.

Core Idea

A placement is not good just because it fits. Good placements preserve useful residual capacity. With fractional GPUs, this often means packing small compatible jobs together while preserving whole or scarce GPU slots. The same idea applies to any slots, bins, or resources with discrete capacities.

Marginal Fragmentation

For each feasible placement, compute a local before/after estimate:

1. Measure current free capacity by resource type and slot.
2. Copy the target machine or bin state.
3. Compute fragmentation_before.
4. Apply the candidate placement.
5. Compute fragmentation_after.
6. Set marginal_fragmentation = fragmentation_after - fragmentation_before.

best = None

for placement in feasible_placements:
  target_before = copy(target_state)
  fragmentation_before = estimate_fragmentation(target_before, workload_types)
  target_after = apply(placement, target_before)
  fragmentation_after = estimate_fragmentation(target_after, workload_types)
  marginal_fragmentation = fragmentation_after - fragmentation_before
  score = weighted_action_score(
    marginal_fragmentation=marginal_fragmentation,
    other_component_deltas=estimate_other_deltas(placement)
  )
  best = lower_score(best, placement, score)

choose best

Respect hard feasibility first. Use marginal_fragmentation as an input to the weighted action score, not as the only decision rule.

Estimating Fragmentation

When workload shape probabilities are available, such as workload_types from cluster_config.json, use them to estimate which free capacity is likely to be useful:

fragmentation = 0

for workload_type in workload_types_from_cluster_config:
  if workload_type.gpu_type is incompatible with target.gpu_type:
    continue

  can_fit =
    target.cpu_free >= workload_type.cpu_units
    and target.memory_free >= workload_type.memory_units
    and any(slot.free_gpu_units >= workload_type.gpu_units
            for slot in target.gpu_slots)

  compatible_free_gpu = sum(slot.free_gpu_units for slot in target.gpu_slots)

  if not can_fit:
    fragmentation += workload_type.probability * compatible_free_gpu
  else:
    small_fragments = sum(
      slot.free_gpu_units
      for slot in target.gpu_slots
      if 0 < slot.free_gpu_units < workload_type.gpu_units
    )
    fragmentation += workload_type.probability * small_fragments