ESG: Pipeline-Conscious Efficient Scheduling of DNN Workflows on Serverless Platforms with Shareable GPUs
Xinning Hui Yuanchao Xu Zhishan Guo Xipeng Shen















xhui@ncsu.edu





  North Carolina State University
  
  Raleigh
  NC
  USA
  27606



yxu314@ucsc.edu

  University of California, Santa Cruz
  
  Santa Cruz
  USA


zguo32@ncsu.edu

  North Carolina State University
  Raleigh
  NC
  USA



xshen5@ncsu.edu

 North Carolina State University
 Rono-Hills
 Raleigh
 NC
 USA













Recent years have witnessed increasing interest in machine learning inferences on serverless computing for its auto-scaling and cost effective properties. Existing serverless computing, however, lacks effective job scheduling methods to handle the schedule space dramatically expanded by GPU sharing, task batching, and inter-task relations. Prior solutions have dodged the issue by neglecting some important factors, leaving some large performance potential locked. This paper presents ESG, a new scheduling algorithm that directly addresses the difficulties. 
ESG treats sharable GPU as a first-order factor in scheduling. It employs an optimality-guided adaptive method by combining A*-search and a novel dual-blade pruning to dramatically prune the scheduling space without compromising the quality. It further introduces a novel method, dominator-based SLO distribution, to ensure the scalability of the scheduler. The results show that ESG can significantly improve the SLO hit rates (61%-80%) while saving 47%-187% costs over prior work.







<ccs2012>
    <concept>
    <concept_id>10010520</concept_id>
    <concept_desc>Computer systems organization</concept_desc>
    <concept_significance>500</concept_significance>
    </concept>
    <concept>
    <concept_id>10010147.10010178.10010199</concept_id>
    <concept_desc>Computing methodologies Planning and scheduling</concept_desc>
    <concept_significance>500</concept_significance>
    </concept>
</ccs2012>


[500]Computer systems organization Cloud Computing
[500]Computing methodologies Planning and scheduling






















25 January 2024

[accepted]25 March 2024




ESG: Pipeline-Conscious Efficient Scheduling of DNN Workflows on Serverless Platforms with Shareable GPUs
    Xipeng Shen
    April 29, 2024
=========================================================================================================





§ INTRODUCTION















Recent years have witnessed a rapidly growing interest in machine learning (ML) inferences on serverless platforms, thanks to the ease of programming and maintenance, autoscaling, and pay-as-you-go billing of serverless computing <cit.>. 



Due to the computing-intensive nature of ML inferences, it is desirable to provide GPU support on serverless platforms to ML workloads, which can help significantly boost the service throughput for the massive parallelism of GPUs <cit.>. However, the current state of commercial serverless platforms (e.g., AWS Lambda <cit.>, Google Cloud Function <cit.>, Azure Function <cit.>, and Knative <cit.>) is falling behind: The schedulers and resource management are still CPU-centric, oblivious to GPU resources. 

There have been some recent research efforts toward adding GPU support to ML on serverless platforms. Some approaches have leveraged NVIDIA MPS <cit.> to facilitate GPU sharing across distinct function instances <cit.>. Others have introduced techniques to enable batching for ML inference, thus increasing overall throughput <cit.>. Additionally, certain studies have extended scheduling algorithms to manage heterogeneous computing resources more effectively <cit.>.

Despite the progress made so far, two challenges remain, which have kept much of the potential of GPU out of reach for serverless ML. 

(i) The dramatically expanded search space for scheduling.



An important step in serverless scheduling is to configure the serverless functions, that is to determine the amount of resource to assign to each of the serverless functions in an application to meet the Service Level Objective (SLO) while consuming the minimum resource. The configuration space is as large as n=m^k, where m is the number of resource allocation options for one serverless function in the application, and k is the number of functions in the application. Without considering sharable GPUs, the options for a function are just the number of vCPUs to consider. With sharable GPUs, the space becomes three-dimensional: (batch size, number of vCPUs, number of vGPUs). The "batch size" here refers to the number of invocations of a serverless function to be grouped into one batch to run. Batching is essential for GPU throughput due to its massive parallelism. The search space hence expands cubically, from n=m^k to n=(m^k)^3 (assuming the same number of options in all dimensions and a function can have its own options values). For m=5, k=7, the space increases from 78K options to 476 trillions. 

(ii) The significantly increased complexity in handling performance variations. Because the number of different states of available resources is multiplied by the available vGPUs, it calls for an adaptive scheduling algorithm to handle them properly. Performance variation is an inherent problem in serverless computing, where the running times of a serverless function vary much across invocations <cit.>. Batching exacerbates it as unpredictable job arrival times cause variations in the waiting time for forming a batch. Along with these variations, the system workload and resource availability on a serverless system show constant changes. Therefore, adapting agilely to dynamic changes and variations becomes crucial for a scheduler. 



Previous studies have all dodged those challenges by neglecting some important dimensions of the problem (Table <ref>), causing a substantial loss in the quality of scheduling. These dimensions include inter-function relations, GPU sharing, and runtime system state variations. Specifically, based on the neglected dimension(s), previous solutions fall into one of two groups. (i) Those works neglecting the relations between functions, represented by Fast-GShare <cit.> and INFless <cit.>, two most recent studies on sharable GPU support for serverless ML. An ML-based application often consists of multiple stages of work, which form a pipeline or a directed acyclic graph (DAG) <cit.>. A chatbot, for example, responds to a user's input by going through stages of speech recognition, natural language understanding, speech synthesis, and so on. The SLO of an AI-based application is usually for the end-to-end latency of the entire process. The schedule and configuration of one stage hence affect other stages, such as how much latency those stages can still have to allow the end-to-end time to meet the SLO, how much resource used in total, whether the data transfer is local or remote, and so on. Neglecting the inter-stage relations to reduce the scheduling complexity is hence not ideal, causing a large loss in quality (36%-61% as Section <ref> shows). (ii) Those that neglect GPU sharing and runtime variations, represented by Orion <cit.> and Aquatope <cit.>. These proposals regard a GPU as a single device attached to a CPU and schedule jobs purely based on CPU and memory availability. Moreover, they are rigid: They pick a good configuration for every stage of the application before its execution, and then stick to the configuration throughout that execution, regardless of whether the actual latencies of some functions differ substantially from the expectation or how the resource availability changes as the execution reaches later stages. The strategy also leads to a large loss in scheduling quality (46%-80% as Section <ref> shows). 




















































Addressing the limitations is essential for unlocking the full potential of GPU for serverless ML. It is, however, not easy: The solution must be efficient enough to handle the enormous configuration space and agile enough to adapt to the dynamic changes of the system.

This paper presents our solution, a new scheduling algorithm named ESG (which stands for Efficient Serverless Scheduling for Sharable GPUs), which, for the first time, addresses all those challenges at the same time. ESG treats sharable GPU as a first-order factor in scheduling. For scheduling efficiency, ESG employs A*-search and introduces a dual-blade pruning to dramatically prune the huge search space of schedules without compromising the quality. For scalability, ESG further introduces dominator-based SLO distribution to prevent space explosion. For the quality of the scheduling results, ESG takes an optimality-guided adaptive approach. Rather than deciding the resource assignment of all functions in a workflow at the beginning and keeping it unchanged throughout the DAG execution as previous solutions <cit.> do, ESG revisits and adjusts the schedules before the dispatch of every serverless function to adapt to the dynamic changes of the environment and the performance variability of the functions. 













We have evaluated ESG on a series of workloads involving six DNNs and compared the performance with four state-of-the-art serverless scheduling solutions, INFless <cit.>, FaST-GShare <cit.>, Orion <cit.> and Aquatope <cit.>. The results show that the new scheduling algorithm ESG is effective in addressing the new challenges, consistently achieving the highest SLO hit rates with significantly lower resource usage, exhibiting a notable 61%-80% improvement in SLO hit rates and saving 47%-187% in costs than INFless and Fast-GShare, especially in challenging scenarios.

Overall this work makes the following major contributions:



  * It provides ESG, the first scheduling algorithm that simultaneously tackles inter-function relations, GPU sharing, batching, and runtime variations.


  * It introduces a set of novel optimizations to ensure high efficiency and scalability of the scheduling algorithm.


  * It empirically confirms the effectiveness of ESG by comparing it with the state of the art represented by four previous scheduling algorithms. 





§ BACKGROUND






 
Serverless architecture. We use OpenWhisk <cit.> as an example to explain the common architecture of serverless computing. OpenWhisk is an open-source,
distributed Serverless platform that executes functions
[“Function” in this paper refers to Serverless Function.]
in response to events at any scale. Figure <ref> shows the architecture of OpenWhisk <cit.>.
It has a RESTful API, through which, users can create actions, invoke actions 
and check the action status.
NGINX translates the command and forwards it to the Controller. Controller is where task scheduling happens. It 
maintains the health and remaining capacity of each Invoker (i.e., a computing node), tracks the warm instances on each Invoker, decides the resource assignments to tasks, and assigns tasks to Invokers. Then the Controller sends the invocation message 
to the selected Invoker via distributed messaging component (Kafka).
The Invoker creates an execution environment (Docker container) 
after receiving the invocation message and manages its runtime 
(including stopping the container). 
OpenWhisk sets a fixed 10-minute keep-alive policy for each instance; the Invoker informs the Controller when it unloads a container <cit.>.



Scheduling of Serverless Functions. 
There are two main steps in scheduling serverless functions. 

The first step is resource assignment, which determines the amount of resources assigned to a function. It is based on the memory requirement specified in the configuration, which is converted by some platforms into a number of vCPUs (each vCPU is associated with a fixed amount of memory). The scheduler ultimately determines the amount of resources to be assigned to that instance, which may be more than required to achieve better performance. OpenWisk uses the required amount by default, while recently schedulers <cit.> used a more sophisticated algorithm to decide the assignment of resources. 


The second step is to map a function instance to an Invoker (e.g., a computing node). 
The controller maintains the available CPU resources of each Invoker according to its memory usage. In OpenWhisk, the controller picks one of the Invokers based on the hash value 
calculated by the namespace and action of the function.
The generated index is called "home-invoker" <cit.>, which is the invoker where the future instances of the function will reside by default. But if that invoker becomes unhealthy or lacks capacity, the scheduler will look for other invokers through a deterministic search. The mapping scheme is designed to get more warm starts.

























GPU Sharing.
GPU sharing is to allow multiple processes to share a single GPU for their executions. Modern GPUs support time sharing (one after the other) and spatial sharing. Spatial sharing is essential for ML inferences because an inference by an ML model often uses only a fraction of the massive parallel computing capacity of a GPU. Allowing multiple processes to execute concurrently on a GPU is essential for turning its computing power into throughput. Modern GPUs from NVIDIA offer two mechanisms for spatial sharing, Multi-Process Service (MPS) <cit.> and Multi-Instance GPU (MIG) <cit.>. MIG gives better isolations between partitions. MIG's ability to partition a single GPU into multiple hardware-isolated instances not only maximizes resource utilization but also significantly bolsters security, a critical aspect in today's cloud computing landscape. 

Although the size of a MIG partition is fixed at system booting time, one application or serverless function may use more than one MIG partition by launching multiple GPU kernels concurrently.  



§ SOLUTION: ESG SCHEDULING ALGORITHM


This section presents ESG, our GPU sharing-aware scheduling algorithm that is designed to respond to the unsolved challenges from inter-function relations and dynamic changes of resources. 



 §.§ Overview











ESG runs on the Controller of a serverless platform. Its objective is to maximize the  Service Level Objective (SLO) hits of DNN inferences—that is, make as many DNN inferences deliver their results within the SLO latency as possible—while minimizing resource consumption (and hence cost). The problem is intuitive to understand, so a formal definition is omitted here for the sake of space. Interested readers may see the Appendix <ref> for a formal rigorous definition of the problem.

For easy explanation, Figures <ref> (a) and (b) illustrate two serverless ML-based applications in the form of DAG. Application 1 uses three DNN serverless functions in a sequence to first upscale an input image, then deblur it, and finally classify it. Application 2 uses two DNN serverless functions to first deblur an input image and then generate a depth image from it. 

ESG introduces application-function-wise (AFW) job queues to group requests for the same serverless function of the same application together. The five serverless functions in Figure <ref> (a) and (b) each have their own AFW job queue, as illustrated in Figure <ref> (c). Notice that even though the same Deblur function is used in both applications, two AFW queues are created, one for each. This design allows ESG to put the functions of the same application on the same machine when possible to reduce the overhead of communications between functions (Section <ref>). The AFW queues reside on the Controller. Each of them gets populated as user requests arrive or its predecessor functions produce some triggering outputs. 





  
Two-step Design. Figure <ref> (d) outlines the high-level workflow of the two core algorithms of ESG. The Controller examines the job queues in a round-robin manner. If a job queue is ready to be scheduled, ESG_1Q, the first core algorithm of ESG, figures out an appropriate configuration for some jobs in that queue. The configuration includes (i) batch size: the number of jobs to be scheduled as a group—which we call a task; (ii) #vCPUs: the amount of CPU resources to use; (iii) #vGPUs: the amount of GPU resource to use. (Section <ref> details the resource model).  Then, the second core algorithm of ESG, ESG_Dispatch, assigns the task to an appropriate Invoker machine to run. 

Note that ESG_1Q does not consider current resource availability constraints; as a result, ESG_Dispatch may not be able to find any Invokers having enough resource to run the task in a configuration found by ESG_1Q. ESG solves the issue by letting ESG_1Q output multiple top configurations, forming a configuration priority queue. ESG_Dispatch repeatedly dequeus the priority queue until it finds an Invoker that has enough resources to handle the configuration. If none of the configurations works, the scheduler records that AFW job queue in a recheck list, and moves on to the next AFW job queue. Each time it finishes processing a job queue, it tries again on the job queues in the recheck list; it may succeed now, as the states of the worker nodes have changed. If a queue stays in the recheck list too long (e.g., 3 rounds), it will be dispatched with the minimum configuration to ensure progress. 

This two-step design is for two reasons: (i) finding optimal configurations takes some time and the states of the workers may have changed during that time; (ii) finding optimal configurations itself is already complicated, adding the dynamic changing machine status into the search process would further complicate the problem. The two-step design decouples the complexities and hence simplifies the solution. Meanwhile, by postponing the resource availability check to the second step, it is able to consider the current state of workers. 

The two core algorithms both feature some novel designs, which help ESG address the two key challenges in adding sharable GPU into serverless computing, namely, the dramatically expanded resource assignment space and the increased complexity in handling dynamic changes in resource availability and function running times. We next first explain the resource and task models used in this work and then detail both algorithms.




 §.§ Resource Model and Task Model



Resource model.
A change to the resource model for heterogeneous serverless computing is the inclusion of GPU units. Modern GPUs are equipped with built-in mechanisms to support GPU partition and sharing. Multi-instance GPU (MIG) in NVIDIA GPU, for instance, allows GPUs to be securely partitioned into up to seven separate GPU Instances for CUDA applications. With MIG, each instance's processors have separate and isolated paths through the entire memory system, including the on-chip crossbar ports, L2 cache banks, memory controllers, and DRAM address buses that are assigned uniquely to an individual instance. We accordingly integrate the notion of vGPU into the serverless computing resource model. Here, each vGPU is equivalent to the minimum GPU partition of the sharing system (in our case, MIG). We assume each GPU is partitioned into the maximum number of MIG instances (7 for A100). 

For a modern GPU-supported container, when it is launched, it can be set to use one or more vCPUs and one or more vGPUs. When it is set to use multiple vGPUs, it can use them by invoking multiple GPU kernels concurrently, one on each. 

Current serverless platforms typically associate a certain amount of memory with one vCPU, which simplifies resource allocation: the platform can use vCPU as the allocation unit without explicitly allocating memory. GPU memory is associated with vGPU in a similar way, naturally enabled by MIG. We, however, do not associate vGPU with vCPU but make them separate resources for allocation. It is because there is no clear correlation between the amount of CPU usage and the amount of GPU usage in applications. 



Task model.
The applications targeted in this work are ML inference applications. (ML training is out of the scope.) 
There are two special extensions to the task model in heterogeneous serverless computing. (i) Each serverless function may now contain both CPU and GPU parts. (ii) For ML inferences, even though requests may come one by one, the inference function is often written in a way that it can accept a batch of requests and process them together at one invocation of the function. If the function is given multiple vGPUs, it automatically uses data parallel inferences by launching multiple GPU kernels with each processing one portion of the batch on one vGPU. We call the inference of one request a  and the set of jobs processed by an invocation of a serverless function a . 



 §.§ ESG_1Q Algorithm












As Figure <ref>(d) shows, ESG_1Q tries to identify a good configuration for the jobs in an AFW queue so that the application can complete within the SLO latency with the minimum resource cost. 

There are two complications: (i) speed-cost tension; a configuration that leads to faster execution tends to incur a higher cost. (ii) Inter-function dependence; the configuration selected for one function determines how much time is left for other functions in the application and hence affects how to best configure the other functions. 

Our approach is to convert the problem into a path-finding problem in the configuration space of an application. The top part of Figure <ref> illustrates the configuration space of a 3-function application. A path from the leftmost column to the rightmost column specifies the configurations for each of the three functions of the application. The red path in Figure <ref>, for instance, corresponds to a case where the first function processes two requests each time with four vCPUs and one vGPUs, the second function processes two requests with two vCPUs and one vGPU, and the third processes one request with one vCPU and two vGPUs. 

Different paths result in different times and resource costs as exemplified by the table in Figure <ref>(a). The Controller can estimate the times with performance profiles of the functions and calculate the costs based on the unit costs of vCPU and vGPU and the running times. 

With that formulation, the goal of ESG becomes finding the path in the configuration space of the application that meets the SLO latency and has the lowest resource cost. So each time, what ESG_1Q returns is not just a configuration good for the current function, but a sequence of configurations good for the whole application. It is important to note that unlike previous methods, Orion <cit.> and Aquatope <cit.>, ESG calls ESG_1Q again when later functions in the application are to be scheduled, so that it can accommodate the dynamic resource changes and running time fluctuations. 





  
A*-Search with Dual-Bladed Pruning in ESG_1Q
ESG_1Q uses A*-search as the basis for the path finding, and proposes two techniques, Dual-bladed pruning and dominator-based SLO distribution, to ensure the efficiency and scalability of the algorithm for serverless scheduling. 

The A* search algorithm is an efficient and popular path finding and graph traversal method <cit.>. It efficiently finds the shortest path from a start node to a target node in a weighted graph. A* uses a heuristic to estimate the cost to reach the goal from each node, guiding the search towards the target more efficiently than algorithms like Dijkstra's, which only consider the actual cost from the start node. The total cost f(n) of a node n is calculated as f(n) = g(n) + h(n), where g(n) is the cost from the start node to n, and h(n) is the estimated cost (heuristic) from n to the goal. A* is a best-first search algorithm, meaning it explores a path that appears to be most promising by using the cost function f(n). It prioritizes paths that are expected to lead more quickly to the target. The algorithm maintains a priority queue (often implemented as a min-heap) of nodes to be explored, sorted by their f(n) value. A* is both complete and optimal, meaning it will always find a solution if one exists, and the solution will be the shortest possible path, provided that the heuristic function h(n) is admissible (it never overestimates the true cost) and consistent (monotonic).

ESG_1Q builds on A*, the optimality of which makes ESG scheduling optimality-guided. ESG_1Q meanwhile improves the path finding with dual-bladed pruning. Figure <ref> (b) outlines the basic idea. 
It prunes the search space based on both running time and resource usage, efficiently avoiding exploration of unnecessary subspaces. The pruning effectively estimates the lower and upper bounds of the costs of a path. When a partial path p forms, ESG_1Q calculates three bounds, tLow, rscLow, and rscFastest, and uses them for pruning, as follows:



  * tLow: the lower bound of the time cost of all paths prefixed by p. ESG_1Q estimates it by summing the time of the functions in p (obtained from the profiles) and the minimum time of each function (among all its possible configurations) not covered by p. It is used in time-based pruning (function getTimeLowBound in Figure <ref> (b)). 

  * rscLow: the lower bound of the resource usage of all paths prefixed by p. ESG_1Q estimates it by adding the resource usage of the functions in p (obtained from the profiles) and the minimum resource usage of each function (among all its possible configurations) not covered by p. It is used in the cost-based pruning (function getCostLowBound in Figure <ref> (b)). 

  * rscFastest: the summation of the resource consumed by p and the resource consumed by other functions when they run the fastest. It is used in updating 
best_full_paths_maxCost in Figure <ref> (b) to tighten the bound for cost-based pruning. 


Note that for ease of understanding, Figure <ref> (b) shows only the basic design of ESG_1Q; Omitted details (e.g., the use of priority list for best-first search) are documented in Appendix <ref>.




  
Dominator-based SLO Distribution for Scalability

Even with Dual-blade pruning, when dealing with lengthy call sequences within an application, the algorithm's execution time can still be exceedingly long. To address this issue, we introduce a strategy named dominator-based SLO distribution. It uses stage grouping to divide the functions of the application into several function groups, uses  SLO distribution to assign a specific SLO latency to each group, and then applies the ESG_1Q search algorithm to each individual group. To ensure maximal quality, the groups are maximized under the constraints of tolerable schedule latency.  
This strategy provides a way to strike a good balance between the scheduling scalability and the benefits of considering inter-function relations in scheduling. 

For this approach to work, we need to determine how to group functions and assign individual SLOs to these groups. This solution should be adaptable to both linear pipelines and more complex DAGs with splits and joins.


Our solution is a reduction-based hierarchical method. It is based on an observation that the DAGs in serverless applications are usually hierarchically reducible, as Figure <ref> illustrates. The design is inspired by dominator-based code analysis in compilers <cit.>. The algorithm includes four steps. 

First, it creates the dominator tree of the DAG following traditional compiler-based code analysis <cit.>. In a dominator tree, each edge indicates an immediate domination relation in the DAG[A dominates B if all paths from the root to B must first reach A; an immediate dominator is the closest dominator except the node itself <cit.>.], as illustrated in Figure <ref>. The data structure offers the basis for an ordered traversal and reduction in processing.

Second, it labels each node in the dominator tree with the average normalized length (ANL) of its function (say f_i), average_c(l_f_i(c)), where c is a configuration, l_f_i(c) is the normalized length of the function f_i in configuration c, calculated as t_f_i(c)/∑_j t_f_j (c); t_f_j(c) is the execution time of function f_i in configuration c, read from the performance profile.



Third, it traverses the dominator tree in a post-order (children before parents). At each node (say x), if it has more than one child, it calls subroutine reduce(x) to first reduce and reorganize its descendants. The reduce operation is to combine its branches into one node, as illustrated in Figure <ref> (c). The ANL of that new node is the maximum of the sums of the ANL of all the branches. After that, the algorithm checks if the parent of x has more than one child and if so, it calls the subroutine slo_group(x) to partition x and its descendants into one or more groups.   
Note that thanks to reduce, the descendants of x are guaranteed to form a single list. The partition simply groups consecutive g nodes into one group, where g is the maximum group size (Section <ref> reports how g affects performance). An exception is the nodes generated by reduction, each of which stays as an individual node to prevent their subsumed groups' sizes from being bloated. This process continues until the algorithm reaches the root. Throughout the process, the algorithm records the reduction process for the next step to use. 

Finally, the algorithm assigns SLO latency to each of the groups. This process reverses the reduction process. It starts from the final form of the reduced dominator tree (which is a list) and partitions the end-to-end SLO latency proportionally based on the ANLs of its groups. It then calls subroutine slo_assign(x) for each reduced node in the current list to partition the SLO latency of x and assigns the partitions to the nodes that x subsumes. This process continues until every group gets its SLO quota. 















 §.§ ESG_Dispatch: Mapping to Worker Nodes



After ESG_1Q, ESG_Dispatch maps the current group of jobs to an Invoker node. As we introduced
in Section <ref>, the OpenWhisk scheduling always chooses the home-invoker first; if not feasible, it tries other worker nodes.
Our algorithm chooses the home-invoker for the first function in the workflow. For other functions, it would try to choose the invoker that runs its predecessor function in the workflow. This locality-sensitive treatment is possible thanks to our introduced AFW queues. It helps reduce data transfer, as communications on the same node can use local file systems rather than remote storage. This consistent policy is beneficial for getting warm starts. 
If the home-invoker or predecessor-invoker does not have enough available resources,
the algorithm will try other warm Invokers. 
If it fails, it will check other cold invokers and choose the one with the most available resources.






§ METHODOLOGY FOR EVALUATION



To evaluate the efficacy of the scheduling algorithm, we create a framework that can emulate various serverless workloads and scenarios. The emulations are based on actual performance of the serverless functions measured on actual machines in various configurations (batch size, CPU and GPU resource allocations). The machine is as specified in Table <ref>. To accommodate the impact of other runtime factors on the performance, the emulations add Gaussian noises to the performance. The emulation is equipped with a workload generator, which generates workloads by sampling the set of serverless functions randomly based on a specified arrival rate. The set of workloads we considered in the evaluation are further detailed in Sec <ref>. The hardware resource of the considered testbed in the emulations consists of 16 nodes, with each equipped with 16 vCPUs and 1 GPU (up to 7 vGPUs by MIG). The scheduler and job dispatching implementation is based on the controller in OpenWhisk <cit.>. 











We use proxy threads to monitor the function call intervals, predict subsequent invocations, and preemptively warm up instances.
Studies have shown that pre-warming can help reduce delays caused by cold starts. There have been several methods proposed before, with some using ML models <cit.> and others <cit.> using a histogram-based policy to adjust container keep-alive times. We use a lightweight method for prewarming. It uses Exponential Weighted Moving Average (EWMA) <cit.> to predict the invocation intervals of functions and pre-warms the function instances accordingly. After pre-warming, ESG uses the same keep-alive policy as OpenWhisk, to keep the instance alive for 10 minutes.
 






 §.§ Applications

 The workloads in the experiments are series of calls to four applications, with each consisting of a sequence of DNN inferences. Table <ref> reports the source, inputs, DNN models, execution time in the minimum configuration (1vCPU, 1vGPU, batch size=1), and cold start time of the functions. The four applications are detailed as follows:
 





    
  * Image classification: It detects and classifies objects, important for autonomous driving <cit.> and other domains. Its workflow is to use super-resolution <cit.> first to enhance the clarity of an image, and then use segmentation <cit.> followed by classification <cit.> to identify the objects.  
    
  * Depth recognition: This application measures the distance of an object from a camera, which is essential to 3D scene reconstruction and augmented reality <cit.>. Its workflow uses deblur <cit.> followed by super-resolution first to enhance the image and then recognize image depth with another DNN <cit.>.
    
  * Background elimination: This application eliminates unnecessary and unwanted items and objects from images <cit.>. Its workflow is super-resolution followed by deblur to enhance the image clarity and then uses background removal DNN <cit.> to eliminate the background.
    
  * Expanded image classification: This is a more advanced image classification application with a longer workflow: deblur, followed by superresolution, background removal, segmentation, and classification.


For the workload setting, we examined the traces published by Azure <cit.> to determine job arrival rates. We get the job arrival rates of every minute from the Azure traces, based on which we derived three situations for our DNN applications respectively with heavy, normal, and light workloads. In each workload, one of the four DNN applications is randomly picked to get invoked in each time interval. The length of a job arrival interval is selected randomly in ranges [10–16.8ms], [20–33.6ms], and [40–67.2ms] respectively in the three situations. Figure <ref> shows the distribution of the job arrival intervals in the three situations.





We tested three SLOs. Let L be the time needed by the application to complete its entire workflow when it runs alone with the minimum configuration. (i) In the strict setting, a SLO hit occurs when the application completes within 0.8× L. (ii) In the moderate setting, a SLO hit happens when the application completes within 1× L. (iii) In the relaxed setting, a SLO hit happens when the application completes within 1.2× L. 


Those three levels of requirements correspond to users' possible expectations of service: strict for the light case, moderate for the normal case, and relaxed for the heavy case, denoted as strict-light, moderate-normal, and relaxed-heavy workloads in the evaluation section. 


Following AWS EC2 pricing <cit.>, we set the price of a vCPU to 0.034$/hour. Based on the pricing of an entire GPU on AWS, we divide it by # of vGPUs and set the price of a vGPU to 0.67$/hour. 






 §.§ Comparison Counterparts




We evaluate our ESG algorithm by comparing it with four state-of-the-art scheduling algorithms, including INFless <cit.> and FaST-GShare <cit.>, the latest algorithms for sharable GPU-based serverless ML, as well as the best-first search algorithm in Orion <cit.> and the Bayesian Optimization-based scheduling in Aquatope <cit.>. The original Orion <cit.> and Aquatope <cit.> do not support GPU sharing, but their scheduling algorithms represent the latest search-based scheduling and model-based scheduling, respectively. For comparison, we extend both with GPU sharing support, as explained below.



InFless: InFless schedules jobs by enumerating the configurations for each function without considering the inter-function relations. In worker node selection, a resource efficiency metric is used to maximize the throughput while reducing resource fragmentation. InFless provides no method for distributing an application's SLO to its functions. Our experiment follows a prior work <cit.> to do the distribution based on the average service times of the functions. 

FaST-Gshare: This work uses FaST-Manager to manage spatio-temporal resources for GPU multiplexing. It also employs an enumeration-based scheduling algorithm which enumerates the configurations based on throughput performance metrics. Its node selection tries to minimize GPU resource fragmentation. It offers no method for distributing an application's SLO either. We apply the same method as in INFless.



Aquatope: Aquatope relies on an offline training process, in which the application of interest is profiled in many sample executions based on Bayesian Optimization (BO), through which it builds up a performance model and learns about the statistically good configurations for every stage in the application (encoded in an acquisition function). In deployment, it uses the learned best configurations for the application. Specifically, the training process starts with 100 bootstrapping samples, iterates 50 rounds (we sample five configurations in each round), and selects the best configuration. The nature of its reliance on offline training makes it unable to adapt to dynamic workload changes, as shown in the next section. 

Orion: Orion creates a performance model to address runtime variations, consolidates parallel invocations into a single virtual machine (VM), and implementes instance pre-warming to eliminate cold starts. Its scheduling uses best-first search, which creates a priority queue, in which all new states are added. Adding vGPU into the algorithm, we expand its state definition to a vector of (batch size, #vCPUs, and #vGPUs), one for each stage. The algorithm examines possible states, with each new state increasing the current state in one dimension of the configuration vector, and the start state S_0 has the minimum values for every stage function. The scheduling method decides the schedule for all the stages of an application at the invocation of the first stage; no dynamic adaptation between stages. 
As in the original work, P95 latency is used as the search goal. The configuration with the closest latency to the SLO is returned when the search exceeds a cut-off time (e.g., 100ms) before reaching the goal.







The GPU-sharing and batching policy can improve resource utilization, as shown in Section <ref>.
So, to evaluate the effectiveness of the scheduling algorithm, in our comparisons, we enable the same GPU-sharing and batching for all the scheduling algorithms; the same data locality and pre-warming policy proposed in this work are also used; the only difference is the scheduling algorithm. INFless and FaST-GShare do not follow the data locality policy but their resource fragmentation minimization policy.





§ EVALUATION











Our evaluation examines (i) the overall effectiveness of ESG in maximizing SLO hit rates while minimizing the cost; (ii) the reasons for the benefits of ESG over the state-of-the-art scheduling algorithms (INFless <cit.>, FaST-GShare <cit.>, Orion <cit.> and Aquatope <cit.>); (iii) the overhead and sensitivity analysis of ESG. 














 §.§ End-to-End Performance




Figure <ref> shows the average SLO hit rates and total normalized cost (ESG is 1) for all applications across three situations.
In all three scenarios, ESG consistently shows a high SLO hit rate. Its benefit is especially pronounced in the strict-light scenario: Its hit rate is 46%-80% higher than BO and Orion, and 36%-61% higher than INFless and Fast-GShare. 
It is noteworthy that ESG achieves the significantly higher SLO hit rates with similar or much less resource cost compared to other methods, as Figure <ref> shows.  Detailed SLO hit rates
and cost of each application are shown in Figure <ref>. ESG consistently achieves the highest SLO hit rate at a lower cost, whereas INFless consumes the most resources.








For a more detailed view, Figure <ref> shows the end-to-end latencies of each of the four applications in the relaxed-heavy setting.
ESG consistently achieves latencies below but close to the SLO latency. The configurations found by other methods cause the jobs to either run too slow (e.g., FaST-GShare) or to use more resources (e.g., INFless) than necessary at the expense of larger cost or poor performance of other applications. 

For instance, INFless selects configurations that yield lower latencies for applications such as “image classification”, “depth recognition”, and “background elimination” compared to other methods. This is due to its resource efficiency metric in scheduling, which reduces resource fragmentation and increases system throughput, thereby preferring to utilize all remaining resources in one invoker. However, this approach of allocating excessive resources, as confirmed by the highest resource costs shown in Figure <ref>, leads to prolonged waiting times and increased latency for the “expanded image classification” application. This application is particularly affected due to its extensive pipeline, which involves more pipeline stages awaiting resources.










 §.§ Detailed Analysis


In this section, we provide a detailed analysis to examine the reasons for the benefits of ESG over other methods. 



Compared to INFless and FaST-GShare: INFless and FaST-GShare distribute the end-to-end SLO to different stages based on their average service times, without considering their inter-dependencies. Consequently, if certain early stages experience delays due to data transfer overhead and cold start latency, the later stages do not adjust their SLO settings, resulting in prolonged execution time, especially when the application has multiple functions. As demonstrated in Figure <ref>(d), FaST-GShare and INFless always yield the largest latency. Furthermore, in selecting worker nodes, they prefer reducing resource fragmentation rather than focusing on data locality and data transfer latency. This results in even lower SLO hit rates, a fact that is evidenced by the numerous strikes seen in the FaST-GShare curve of Figure <ref>.






Compared to Orion: Orion is a search-based method. It faces a trade-off between the search time and the quality of the search result. Figure <ref> shows the tradeoff in the strict-light setting. In this setting, Orion can find quite good configurations. The blue curve in Figure <ref> shows the hit rates of those configurations when search overhead is not counted in. But when the search time is counted in, the 
hit rates drop dramatically, as the green curve in Figure <ref> shows. Moreover, because Orion decides the configurations for all functions in an application when scheduling the first function and does not adjust the configurations of later stages, the configurations are often low in quality or do not even apply. It is especially common when the resource availability changes significantly along time. Table <ref> shows the percentage of times when the configurations fail to apply to a function because the batch size in the configuration is even greater than the number of jobs in the queue of that function when it is time to be scheduled. In the moderate-normal and relaxed-heavy settings, because resource availability changes substantially, the percentage is as much as 27–52%.

ESG overperforms Orion because (i) ESG finds better configurations much faster, thanks to its dual-bladed pruning and dominator-based SLO distribution (overhead analysis shown in the next subsection); (ii) ESG adapts the configurations for every function in a workflow. As a result, with a smaller overhead, ESG produces configurations that meet the SLO and demand fewer computing resources. The lower computing resource demand gives multi-fold benefits. It not only lowers the cost, but also makes the function more likely to fit into the available resource of the predecessor worker node, which in turn leads to better data locality, less communication overhead, and fewer cold starts, which all contribute to the higher SLO hits. 





   Compared to Aquatope: Aquatope relies on a statistical model trained with offline traces. It has negligible scheduling overhead. However, ESG surpasses Aquatope because of the better quality of the configurations given by ESG. As shown in Figure <ref>, real workloads and resource conditions continually change. Being a method based on an offline training model, the BO method cannot adapt to dynamic changes. It assumes that configurations remain unchanged unless functions or inputs are modified, but this static scheduling configuration proves inadequate in an ever-changing real-world environment where future job and worker node statuses are uncertain. It is confirmed by the rightmost column in Table <ref>, which shows that 59–86% of the configurations preset by the BO method do not apply in actual executions because the actual queue length is smaller than the batch size in the configuration. 





































































































 §.§ Overhead Analysis





Figure <ref> reports the scheduling overhead distribution of ESG in the three settings (using the default function group size 3), with the green triangle indicating the average. The searching overhead increases with more relaxed SLO settings. It is because in relaxed SLO settings, more configurations can satisfy the SLO, resulting in fewer configurations being pruned during the search process. But overall, the search overhead is less than 10ms. In comparison, the time taken by a brute-force search would be orders of magnitude higher. In the case where each function has 256 configurations, the search time is 7258ms.
























 §.§ Sensitive study





In ESG, there are two parameters, the maximal size of a function group and the number of solutions in the configuration priority queue (K). The default maximal group size is set to 3 because when the size increases to 4, the search time jumps to 1201ms (for 256 configurations per function) due to the exponential growth of the configuration space. Regarding the impact of K value, Figure <ref> reports our observations. As K increases from 1 to 80, the average search overhead increases from 3ms to 8ms, the latency remains similar, and the cost decreases slightly. The default K is set to 5 in ESG. 






 §.§ Impact of GPU-sharing and Batching



Through our ablation study, we assess how the GPU-sharing and batching strategies enhance GPU resource efficiency. We individually removed either the GPU-sharing or batching strategy from ESG and contrasted the results with the original ESG. We set a heavy workload in this experiment specifically to underline the effects of the batching strategy. The results indicate that both strategies boost the usage of GPU resources, as evident in Figure <ref>.

Without the GPU-sharing strategy, the waiting time is substantially prolonged compared to ESG. This is because jobs are queued, waiting for a GPU (currently in use) to free up. Consequently, the data-locality strategy may falter, leading to substantial data transfer costs and worse SLO hit rates. The batching strategy is crucial in conserving cost, as shown in Figure <ref>. The batching policy will delay the execution time; thus, no-batching policy will not decrease the SLO hit rates.































§ RELATED WORK


 


Heterogeneous serverless computing: Recent studies on GPU-based serverless computing focused on CPU-GPU data transfer <cit.> and cold start overhead <cit.>. Some prior works  <cit.> studied the scheduling tasks on GPUs but regarded an entire GPU as the minimal computing unit. Other works <cit.> proposed the GPU-sharing scheduling for inference applications but neglected the inter-function relations of the DAG workflows. There have been efforts to extend serverless computing support to heterogeneous hardware, including FPGAs and Nvidia DPUs <cit.>. Additionally, Dgsf <cit.> proposed the disaggregated GPU for serverless computing that is orthogonal to our work.



Serverless resource management: Several works <cit.> have studied the resource management problem in serverless computing. Orion <cit.> and INFless <cit.> are search-based scheduling algorithm. SIMPPO <cit.> used reinforcement learning for serverless resource management. Aquatope <cit.> is a Bayesian Optimization based scheduling algorithm, which builds upon IceBreaker <cit.> and CLITE <cit.> and extends BO in new ways than what was previously done in other BO-inspired solutions like SATORI <cit.> or Ribbon <cit.>, and inspired the OLPart <cit.>. 

Optimization of data transfer: Researchers realize the data transfer between workers and remote database lead to unnecessary latency. FaaSFlow <cit.> proposed to partition the workflow into sub-graphs and schedule these functions in one invoker to avoid data transfer. Nightcore <cit.> proposed the internal function calls and low-latency message channels, and efficient threading for I/O to reduce the data transfer latency. Sonic <cit.> proposed the hybrid data passing methods, which are direct-message passing and remote storage to reduce the data transfer latency. Palette <cit.> used the "colors" to place successive
invocations related to each other on the same executing node.
As shown in previous sections, due to the lack of effective methods to handle large schedule space, prior work left much potential for sharable GPU locked for ML on serverless platforms.





§ CONCLUSION


This study has proposed and evaluated a new algorithm ESG to effectively schedule ML workloads on serverless platforms with sharable GPUs. The search algorithm employs an optimality-guided adaptive method by combining A*-search and a novel dual-blade pruning to effectively prune the scheduling space without compromising the quality. Its dominator-based SLO distribution offers a way to keep the algorithm scalable. Across a diverse set of real-world serverless applications, ESG gives the highest SLO hit rates, while significantly reducing the cost.








This material is based upon work supported by the National Science
Foundation (NSF) under Grants No. CNS-2312207, CNS-2107068, and CMMI-2246671. Any opinions, findings,
and conclusions or recommendations expressed in this material are
those of the authors and do not necessarily reflect the views of NSF.





ACM-Reference-Format






§ PROBLEM FORMAL DEFINITION



For clarity, we provide a formal definition of the scheduling problem as follows.

Assumptions:


    
  * One serverless function invocation uses at most one worker node.
    
  * All worker nodes have the same hardware resources (we made this assumption for the explanation simplicity, our algorithm still works with heterogeneous hardware resources). 
    
  * The serverless functions are in a form that can accept a single job or a batch of jobs.



Given: 
A set of jobs B= { e_i | I ≥ i>0} with each job as an invocation of one of the serverless functions {f_j | J ≥ j>0}; each job in B belongs to one and only one of the applications A={a_m | M ≥ m>0} and one application consists of one or more jobs; each application a_m has a tolerable latency upper limit d_m; a set of workers { w_k | K ≥ k>0} with each worker being equipped with R_C CPU resource units and R_G GPU resource units; 

Objective: 
Produce a set of schedule configurations C={c_l = (b_l, r_l, p_l, q_l) | L≥ l>0}, where each configuration c_l represents that at time q_l, a set of jobs b_l are assigned to the worker p_l to run with r_l=(u_c_l, u_g_l) resources (u_c for CPU resource units, u_g for GPU resource units), such that:


    
  * argmin_C ∑ (α u_c_l + β u_g_l), 1≥α≥ 0, β =1-α.


Constraints:

    
  * ∑ h_m >γ, where h_m=1 if the end-to-end time of application m, denoted as t_a_m, is no greater than d_m, and 0 otherwise; t_a_m = ∑ t_b_i where t_b_i is the end-to-end time of job b_i, that is, the time from its invocation to its completion.
    
  * ∪_l^L b_l = ∪_i^I e_i (every job is scheduled)
    
  * b_i ∩ b_j = ∅,   ∀ l ≥ i, j>0  and i ≠ j (each job belongs to only one set)
    
  * ∑_l=0^Lu_c_l1(b_l, k,t)≤ R_C,  ∀ t, ∀ K≥ k> 0, where, 1(b_l,k,t) is 1 if b_l is active at time t on worker k, and 0 otherwise. (within total CPU resource) 
    
  * ∑_l=0^Lu_g_l1(b_l, k,t)≤ R_G,  ∀ t, ∀ K≥ k> 0, where, 1(b_l,k,t) is 1 if b_l is active at time t on worker k, and 0 otherwise. (within total GPU resource)





§ ESG_1Q ALGORITHM

 






































