Historically, schedulers have largely been static in nature, particularly in the HPC arena. Static schedulers are based on two primary assumptions:

* the resources specified in the allocation request represent the peak resources that will be used by any combination of applications in the allocation. It is recognized that the applications may (and often do) utilize a smaller subset of the overall resources at any given time, and that is ignored by the scheduler. However, the applications are prohibited from using anything beyond the requested resources, regardless of the length of time of the excursion

* the time specified in the allocation request represents the maximum duration of the collection of applications that will execute within the allocation. All execution will be terminated by the scheduler at the end of that time, regardless of the state of the enclosed applications. Application termination prior to the specified duration is acceptable.

These assumptions allow the scheduler to create "bulk" schedules based on the current contents of their submission queues - i.e., the schedule is "fixed" and rigid based on the currently accepted submission requests. The schedule is only recomputed when one of two events occurs:

* an executing allocation terminates early. This triggers the scheduler to execute a "backfill" operation - i.e., it recomputes the schedule based on submissions that can fit within the remaining time and resource constraints of the session that terminated before its scheduled time. Backfill scheduling algorithms are complex as they try to balance use of current available resources (those released by the early terminating session) versus aggregating those resources from soon-to-be-terminating sessions to allow a larger session to be allocated, balancing all that against priority.

* a "reset" event that causes the scheduler to recompute the schedule from a blank slate. This is an unusual event as it takes considerable time to compute the full schedule - it is typically reserved for either a system reboot or injection of a high priority request that involves a large fraction of machine resources.

In contrast, dynamic schedulers remove the two primary assumptions and instead assume that resource requirements for a given session (whether submitted or already in execution) represent a point-in-time scenario that is subject to continual change. This includes the length of time for the session to complete. Dynamic schedulers, therefore, only compute the schedule for a limited window of time into the future based on the current set of requirements. The size of the window defines the responsiveness of the scheduler - shorter windows allow the scheduler to change execution assignments at more rapid intervals, but up the computational load on the scheduler and the "churn" of the executing applications. Longer windows provide for less "churn" but can make the scheduler less responsive to changes in ongoing application needs.

Dynamic schedulers resolve the conflict of changes in resource requirements amongst currently executing allocations by a combination of preemption and notification of resource assignment changes to applications. Preemption can involve simple termination of an executing allocation (with or without warning) or checkpointing and "pausing" all executing applications in an allocation prior to reassigning its resources. Notification of resource changes requires apps registering their ability and willingness to engage in handshakes that negotiate the (possibly) temporary removal of resources for reassignment to another allocation. It is assumed that such resource changes can/will be reversed at a later time as requirements continue to evolve.

Dynamic schedulers require "tuning" to their environment in order to optimize their behavior. Used to be that was done via sys admin "knobs", but more recent research has been focused on using AI to tune the knobs. It still takes awhile for the scheduler to respond to changes in the submission patterns and executing application behavior, but it is possible for the system to improve as it "ages".

Traditional HPC jobs are fine with static schedulers - they simply get submitted and then crank until done. People are used to overestimating both resource and time limits when submitting their jobs, and have developed a sense for how much to overextend those estimates for their applications of interest.

Machine learning and data analytics jobs, however, don't function well in that environment as they are not good at estimating resource and time limits in advance of submission to the scheduler. In fact, their typical use-case involves starting a single process that scans the input situation to develop an initial estimate of required resources, and then seeks to allocate those resources to the initial phase of execution. This obviously has problems in a static environment as the schedule is created prior to the first process computing the required resource envelope. When run under a static scheduler, the only option therefore is to request a maximum envelope of resources and time, and then create an application-specific "mini-scheduler" to dynamically dole out the resources as the programming model determines them. This results in "islands" of resource environments, each controlled directly by the main static scheduler or under the control of an independent "mini-scheduler". Each "mini-scheduler" must have total control over their resource pool, thereby resulting in a lack of efficiency in the overall system.

Further exacerbating the problem is the case where a "mini-scheduler" discovers that it doesn't have enough resources or time to actually complete the computation - i.e., the original submission to the static scheduler included estimates that were too low for one or both of those quantities. In these cases, there is no option but to unsuccessfully terminate the workload, perhaps checkpointing it so that it can be picked up again by a subsequent session.

Moving to a dynamic scheduler allows these non-traditional workloads to operate in an environment better suited to their behavior and eliminates the need for each application and/or programming model to write its own "mini-scheduler". However, handling traditional HPC workloads in the dynamic environment has posed a challenge as such workloads demand certainty and stability in their allocations - i.e., that the resources made available to them will remain theirs for the full requested execution time. This requires some changes to the dynamic scheduler to accommodate these requirements.

The goal of DynaSched is to try to create a dynamic scheduler that can handle both workload types (dynamic and tranitional HPC) in a manner that preserves executional performance while supporting dynamic resource assignments.