• Klaus Aehlig's avatar
    tiered allocation: try canonical search path first · a37549ea
    Klaus Aehlig authored
    In tiered allocation, instances are put on the cluster, while they
    fit---and once no more instances of the given size can be fit, smaller
    instances are tried next. There is obviously some heuristics involved
    in how to shrink the instance to get a smaller one of suitable
    size. The standard heuristics is to shrink on the resource that
    prevents to most placements. This, however, can lead into missing out
    possible smaller instances, as noted in issue 483. The way to avoid
    this trap was to consider all shrinkings of a single resource to see
    if this leads to new solutions. This patch now changes the order of
    the search: use this single resource look-ahead only if the standard
    heuristics does not yield any progress. While this does not change the
    complexity of the underlying algorithm, it improves search time
    significantly for those cases where the standard heuristics works,
    which should cover a good part of the practically relevant cases.
    Signed-off-by: default avatarKlaus Aehlig <aehlig@google.com>
    Reviewed-by: default avatarHelga Velroyen <helgav@google.com>
Cluster.hs 71.4 KB