.. _api-planner:

.. 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.

.. doxygenfile:: planner.h
   :project: flux-sched

[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