PLANNER API
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 uses Linux OS kernel's red-black binary search tree code to update and query the resource states over time. 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's efficient mechanism is specifically designed to mitigate the scalability and performance risk of such a graph-based scheduling approach. More specifically, it enables a novel scheme called scheduler-driven aggregate updates.
As part of scheduling update activities (i.e., update for an allocation or reservation), the scheduler will update all of the planner objects which were involved in the allocation/reservation. This then allows each of the resource vertices to retain the up-to-date summary information on the vertices at its sub-tree or through other relevant topological connectivity. This information then allows the scheduler to prune the graph search for the subsequent allocation or reservation.
[1] Red-black tree (Visited 9/27/2017), Wikipedia, https://en.wikipedia.org/wiki/Red-black_tree
[2] Red-black Trees (rbtree) in Linux (Visited 9/27/2017), Rob Landley, https://www.kernel.org/doc/Documentation/rbtree.txt