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`. ```text 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: ```text 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 ``` ## Intuitive Example If two 50-unit GPU jobs can share one 100-unit GPU slot, placing both on the same slot leaves another full slot free. Placing them on two separate slots creates two 50-unit leftovers, which may be harder for future 75- or 100-unit jobs to use. The same pattern appears outside GPUs: two small tasks may belong in one bin so another bin remains available for a large task. When scores are close, use stable tie-breaks such as urgency, priority, smaller harmless leftovers, and deterministic target order. ## Weighted Objective Context Fragmentation is one objective component. A placement with slightly worse fragmentation may still be better if it substantially improves another weighted component, such as waiting, lateness, resource activation, or unserved-work cost. Conversely, a placement with excellent fragmentation may be bad if it causes a large cost elsewhere. Use the before/after fragmentation estimate as one delta in a general score: ```text weighted_marginal_score = fragmentation_weight * marginal_fragmentation + other_weight_1 * delta_other_component_1 + other_weight_2 * delta_other_component_2 + deterministic_tie_break ```