Attention

Fluxion/flux-sched (both refer to the same project) is under development and its interfaces are not yet stable. APIs are not exported or exposed to external consumers. This documentation is meant for developers of Fluxion.

Planner

Planner provides a simple abstraction and efficient mechanisms to keep track of the resource states for batch-job scheduling. Its API builds on two simple concepts:

  • Planner: just like your calendar planner, a planner object allows you to update and query the available resource states over time (i.e., integer unit-less time).

  • Span: just like you mark your activities over consecutive days in your calendar planner with a span, a span allows you to update your resource uses using a start time, duration and resource requirement.

Planner is designed for speed. Specifically, it initially used Linux OS kernel’s red-black binary search tree code to update and query the resource states over time, which was then later ported to Yggrasil’s red-black tree code (with a more permissive licensing, MIT license): https://github.com/tinloaf/ygg. It manages each of the two scheduled points of spans using two highly efficient binary search trees:

  • Scheduled point red-black binary search tree [1,2]

  • Min-time resource augmented red-black search tree [1,2]

The scheduled-point search tree allows the planner to find the accurate resource state of any given instant time with (O(log n)) complexity. On the other hand, the min-time resource tree enables you to find the earliest scheduable point where your resource requirement can be satisfied also with (O(log n)) complexity. Say, you have a total of 10 available resource units and have allocated 5 units between time t1 and t2, [t1, t2), as well as 3 units from time t2 to t3, [t2, t3). Subsequently, you want to find about the earliest scheduled point at which you can allocate 7 units. The min-time tree will answer t2 as the earliest point in O(log N). By contrast, a request for 5 units will be resolved to t1 with the same performance guarantee. Using both of these search trees, you can efficiently operate on the planner over both the time and resource dimensions alike.

Planner was born out of real-world needs in Flux’s batch-job scheduling infrastructure. As high performance computing (HPC) is undergoing significant changes in both performance-limiting resource types and workloads, simple data models (e.g., bitmaps) representing HPC compute and other consumable resources present increasingly greater challenges for effective scheduling. In response, Flux is in the process of modeling complex HPC resources using a graph. While this allows a highly sophisticated resource selections, it can be done at the expense of excessive, highly time-consuming searches of a large graph. Planner is specifically designed to mitigate the scalability and performance risk of such a graph-based approach by allowing our schedulers to prune the search space of a graph more aggressively.

An API reference of the Planner interface is below.

Typedefs

typedef struct planner_t planner_t

Functions

planner_t *planner_new(int64_t base_time, uint64_t duration, uint64_t resource_total, const char *resource_type)

Construct a planner.

Parameters:

  • base_time -- earliest schedulable point expressed in integer time (i.e., the base time of the planner to be constructed).

  • duration -- time span of this planner (i.e., all planned spans must end before base_time + duration).

  • resource_total -- the total count of available resources.

  • resource_type -- the resource type string

Returns:

new planner context; NULL on an error with errno set as follows: pointer to a planner_t object on success; -1 on an error with errno set: EINVAL: invalid argument. ERANGE: resource_total is an out-of-range value.

planner_t *planner_new_empty()

Initialize empty planner.

Returns:

new planner context; NULL on an error with errno set as follows: pointer to a planner_t object on success; -1 on an error with errno set.

planner_t *planner_copy(planner_t *p)

Copy a planner.

Parameters:

p -- the base planner which will be copied and returned as a new planner context.

Returns:

new planner context; NULL on an error with errno set as follows: pointer to a planner_t object on success; -1 on an error with errno set.

void planner_assign(planner_t *lhs, planner_t *rhs)

Assign a planner.

Parameters:

  • lhs -- the base planner which will be assigned to rhs.

  • rhs -- the base planner which will be copied and returned as a new planner context.

int planner_reset(planner_t *ctx, int64_t base_time, uint64_t duration)

Reset the planner with a new time bound. Destroy all existing planned spans.

Parameters:

  • ctx -- opaque planner context returned from planner_new.

  • base_time -- earliest schedulable point expressed in integer time (i.e., the base time of the planner to be constructed).

  • duration -- time span of this planner (i.e., all planned spans must end before base_time + duration).

Returns:

0 on success; -1 on an error with errno set as follows: EINVAL: invalid argument.

void planner_destroy(planner_t **ctx_p)

Destroy the planner.

Parameters:

ctx_p -- pointer to a planner context pointer returned. from planner_new

int64_t planner_base_time(planner_t *ctx)

Getters:

Returns:

-1 or NULL on an error with errno set as follows: EINVAL: invalid argument.

int64_t planner_duration(planner_t *ctx)
int64_t planner_resource_total(planner_t *ctx)
const char *planner_resource_type(planner_t *ctx)
int64_t planner_avail_time_first(planner_t *ctx, int64_t on_or_after, uint64_t duration, uint64_t request)

Find and return the earliest point in integer time when the request can be satisfied.

Note on semantics: this function returns a time point where the resource state changes. If the number of available resources change at time point t1 and t2 (assuming t2 is greater than t1+2), the possible schedule points that this function can return is either t1 or t2, but not t1+1 nor t1+2 even if these points also satisfy the request.

Parameters:

  • ctx -- opaque planner context returned from planner_new.

  • on_or_after -- available on or after the specified time.

  • duration -- requested duration; must be greater than or equal to 1.

  • request -- resource count request.

Returns:

earliest time at which the request can be satisfied; -1 on an error with errno set as follows: EINVAL: invalid argument. ERANGE: request is an out-of-range value. ENOENT: no scheduleable point

int64_t planner_avail_time_next(planner_t *ctx)

Find and return the next earliest point in time at which the same request queried before via either planner_avail_time_first or planner_avail_time_next can be satisfied. Same semantics as planner_avail_time_first.

Parameters:

ctx -- opaque planner context returned from planner_new.

Returns:

earliest time at which the request can be satisfied; -1 on error with errno set as follows: EINVAL: invalid argument. ERANGE: request is out of range ENOENT: no scheduleable point

int planner_avail_during(planner_t *ctx, int64_t at, uint64_t duration, uint64_t request)

Test if the given request can be satisfied at the start time. Note on semantics: Unlike planner_avail_time* functions, this function can be used to test an arbitrary time span.

Parameters:

  • ctx -- opaque planner context returned from planner_new.

  • at -- start time from which the requested resources must be available for duration.

  • duration -- requested duration; must be greater than or equal to 1.

  • request -- resource count request.

Returns:

0 if the request can be satisfied; -1 if it cannot be satisfied or an error encountered (errno as follows): EINVAL: invalid argument. ERANGE: request is an out-of-range value. ENOTSUP: internal error encountered.

int64_t planner_avail_resources_during(planner_t *ctx, int64_t at, uint64_t duration)

Return how resources are available for the duration starting from at.

Parameters:

  • ctx -- opaque planner context returned from planner_new.

  • at -- instant time for which this query is made.

  • duration -- requested duration; must be greater than or equal to 1.

Returns:

available resource count; -1 on an error with errno set as follows: EINVAL: invalid argument.

int64_t planner_avail_resources_at(planner_t *ctx, int64_t at)

Return how many resources are available at the given time.

Parameters:

  • ctx -- opaque planner context returned from planner_new.

  • at -- instant time for which this query is made.

Returns:

available resource count; -1 on an error with errno set as follows: EINVAL: invalid argument.

int64_t planner_add_span(planner_t *ctx, int64_t start_time, uint64_t duration, uint64_t request)

Add a new span to the planner and update the planner's resource/time state. Reset the planner's iterator so that planner_avail_time_next will be made to return the earliest schedulable point.

Parameters:

  • ctx -- opaque planner context returned from planner_new.

  • start_time -- start time from which the resource request must be available for duration.

  • duration -- requested duration; must be greater than or equal to 1.

  • request -- resource count request.

Returns:

span id on success; -1 on an error with errno set as follows: EINVAL: invalid argument. EKEYREJECTED: can't update planner's internal data. ERANGE: a resource state became out of a valid range, e.g., reserving more than available.

int planner_rem_span(planner_t *ctx, int64_t span_id)

Remove the existing span from the planner and update its resource/time state. Reset the planner's iterator such that planner_avail_time_next will be made to return the earliest schedulable point.

Parameters:

  • ctx -- opaque planner context returned from planner_new.

  • span_id -- span_id returned from planner_add_span.

Returns:

0 on success; -1 on an error with errno set as follows: EINVAL: invalid argument. EKEYREJECTED: span could not be removed from the planner's internal data structures. ERANGE: a resource state became out of a valid range.

int planner_reduce_span(planner_t *ctx, int64_t span_id, int64_t to_remove, bool &removed)

Reduce the existing span's resources from the planner. This function will be called for a partial release/cancel. If the number of resources to be removed is equal to those allocated to the span, completely remove the span.

Parameters:

  • ctx -- opaque planner context returned from planner_new.

  • span_id -- span_id returned from planner_add_span.

  • to_remove -- number of resources to free from the span

  • removed -- bool indicating if the entire span was removed.

Returns:

0 on success; -1 on an error with errno set as follows: EINVAL: invalid argument. EKEYREJECTED: span could not be removed from the planner's internal data structures. ERANGE: a resource state became out of a valid range.

int64_t planner_span_first(planner_t *ctx)

Span iterators — there is no specific iteration order.

int64_t planner_span_next(planner_t *ctx)
size_t planner_span_size(planner_t *ctx)
bool planner_is_active_span(planner_t *ctx, int64_t span_id)

Return 0 if the span has been inserted and active in the planner.

int64_t planner_span_start_time(planner_t *ctx, int64_t span_id)

Getters for span. Return -1 on an error.

int64_t planner_span_duration(planner_t *ctx, int64_t span_id)
int64_t planner_span_resource_count(planner_t *ctx, int64_t span_id)
bool planners_equal(planner_t *lhs, planner_t *rhs)
int planner_update_total(planner_t *ctx, uint64_t resource_total)

Update the resource count to support elasticity.

Parameters:

  • ctx -- opaque planner context returned from planner_new.

  • resource_total -- 64-bit unsigned integer of the total count of available resources of the resource type.

Returns:

0 on success; -1 on an error with errno set as follows: EINVAL: invalid argument.

[1] Red-black tree (Visited 9/27/2017), Wikipedia, https://en.wikipedia.org/wiki/Red-black_tree

[2] Red-black Trees (restorer) in Linux (Visited 9/27/2017), Rob Landley, https://www.kernel.org/doc/Documentation/rbtree.txt

[3] Yggdrasill (Visitied 6/16/2021), https://github.com/tinloaf/ygg