Method and system for assigning a virtual machine in virtual GPU enabled systems

Disclosed are aspects of task assignment for systems that include graphics processing units (GPUs) that are virtual GPU (vGPU) enabled. In some examples, an algorithm is determined based on predetermined virtual machine assignment algorithms. The algorithm optimizes for a predetermined cost function. A virtual machine is queued in an arrival queue for assignment. A graphics configuration of a system is determined. The graphics configuration specifies a number of graphics processing units (GPUs) in the system. The system includes a vGPU enabled GPU. The algorithm is selected based on a correlation between the algorithm and the graphics configuration of the system. The virtual machine is assigned to a run queue based on the selected algorithm.

RELATED APPLICATIONS

Benefit is claimed under 35 U.S.C. 119(a)-(d) to Foreign Application Serial No. 201944003007 filed in India entitled “TASK ASSIGNMENT IN VIRTUAL GPU ENABLED SYSTEMS”, on Jan. 24, 2019, by VMWARE, INC., which is herein incorporated in its entirety by reference for all purposes.

BACKGROUND

A cluster can include a collection of hosts in which processor, memory, storage, and other hardware resources are aggregated for utilization by the hosts in the cluster. A host is capable of running one or more virtual computing instances, such as virtual machines (VMs). A VM typically includes an operating system (OS) running one or more applications to perform a workload. VMs running on a host utilize cluster resources to perform the workloads. However, if a VM is placed on a host with insufficient resources available to meet the resource demands of the VMs, the host becomes overloaded.

In some existing solutions, one or more VMs on an overloaded host can be relocated to a different host in the cluster in an attempt to remediate the overloaded host. A scheduler is utilized in some systems to select a host for placement of VMs and balance the resource utilization among the hosts in the cluster. However, these placement decisions are frequently made based on insufficient information regarding resource demands of the VMs and resource availability of the hosts. This can result in sub-optimal placement of VMs, unbalanced hosts, network saturation, overloading of network links, and/or overall inefficient utilization of available cluster resources.

DETAILED DESCRIPTION

The present disclosure relates to task assignment for systems that include graphics processing units (GPUs) that are virtual GPU (vGPU) enabled. Virtual GPU enabled systems can include data centers and cloud computing services. These systems can perform tasks such as virtual machines (VMs) that can share a single GPU or a set of GPUs in a vGPU enabled architecture. The number of VMs that share the GPUs can be configured manually by a user or automatically by a scheduler. Further, VMs, virtual GPUs, and other tasks can be assigned or re-assigned to GPUs dynamically. This approach can allow tasks/jobs that use GPUs to run in individual VMs for isolation while also sharing resources. As disclosed herein, an efficient and fast solution can be provided for the problem of assigning VMs or tasks to GPUs in cloud environments or environments with multiple servers, each with one or more GPUs.

In some examples, the aspects of the present disclosure can be utilized to determine an algorithm that optimizes for a predetermined cost function. In some aspects, the predetermined cost function can include a geometric mean of GPU utilization and a parameter that is calculated based on virtual machine execution time and virtual machine wait time—for example, a ratio of virtual machine execution time and a sum of the virtual machine execution time and virtual machine wait time.

This can be performed based on simulated and real world results from virtual machine assignments according to a predetermined set of virtual machine assignment algorithms. In some cases, the algorithm is one of the predetermined set, and in other cases, the algorithm is a new algorithm. The new algorithms can be a modified version of at least one of the predetermined virtual machine assignment algorithms.

A machine learning technique can be utilized to generate the modification. For example, the machine learning technique can include at least one of: simulated annealing optimization, bin packing optimization, and particle swarm optimization. A virtual machine can be identified. The virtual machine can be one that is queued in an arrival queue. The virtual machine can be associated with a virtual graphics processing unit (vGPU) profile. A graphics configuration of a system can be determined or identified. The graphics configuration can specify a number of graphics processing units (GPUs) in the system. The system can include a vGPU enabled GPU.

The algorithm can be selected for use based on a correlation between the algorithm, and the graphics configuration of the system. The virtual machine can be assigned to a run queue of a vGPU enabled GPU according to the selected algorithm. The run queue can be associated with the vGPU profile. In some examples, the run queue can be an existing run queue in the system. In other examples, no existing run queue matches the vGPU profile, and the run queue can be a new run queue created to match the vGPU profile once the vGPU enabled GPU is identified as supporting the vGPU profile.

FIG.1shows an example networked environment100including data center101, cloud102, and data storage device103in communication over a network106. Data center(s)101can be representative of one or more data centers101. The networked environment100can be utilized to provide optimized task assignment for virtual GPU enabled systems. Data centers101can include heterogeneous systems that utilize more than one kind of processor, core, or coprocessor. The data centers101can also use multiple instruction-set architectures (ISA).

For example, data centers101can include multiple different accelerators, including GPUs110, field-programmable gate arrays (FPGAs) and application specific integrated circuits (ASICs). A machine such as a host computing device200in a data center101can have one or more of these accelerators. Assignment of a task or virtual machine to a host can depend on matching the requirements of the task to the available accelerators on the machine. Virtual GPUs can present opportunities to improve resource utilization with the benefit of ease of management. It can allow a large number of virtual machines to share the use of a limited number of physical GPUs in a server112, cluster116, data center101or cloud102. In some cases, a task with GPU requirements can be assigned to a vGPU enabled data center101or cloud102. For example, NVIDIA® GPUs and other vGPU enabled GPUs can be supported using a number of different mechanisms.

The data center101can execute a task scheduler108that is capable of task assignment for virtual GPU enabled systems. For example, the scheduler108can assign tasks, including individual ones of the virtual machines104to a particular GPU110. A GPU110can include architecture that supports virtual GPUs120. The virtual machines104can be hosted in the data center101or cloud102. The GPU110can include hardware provided by the data center101or cloud102.

The data center101can include one or more physical computing devices or hosts in the server(s)112and data storage device(s)118. The servers112can include a single server, as well as two or more servers in a cluster116. The cluster116can include a group of two or more physical server devices. The server112or cluster116can include VMWARE® vSphere. The data center101can be equipped with vGPUs120, which can include NVIDIA® vGPU solution. In some cases, the data center101can be considered part of the cloud102. In other examples, the data center101that executes the scheduler108can be considered separate from the cloud102.

The cloud102can include a cloud computing platform. For example, the cloud102can be implemented as a private cloud, a public cloud, or a hybrid cloud. A hybrid cloud can be a cloud that includes a public cloud and a private cloud. VMWARE® vCloud Hybrid Services (vCHS) can be an example of a hybrid cloud implementation. In some examples, the cloud102can run one or more virtual computing instances, such as, but not limited to, individual ones of the virtual machines104. The virtual machines104can utilize virtual GPUs120of the data center101or the cloud102. Cloud services associated with the cloud102can be provided through a network106.

The network106can include a Wide Area Network (WAN) accessible to the public, such as the Internet. The cloud102can be provided through one or more physical servers, as discussed regarding the servers112of the data center101. A virtual machine104can include a virtual computing instance, a container, or any other type of virtualized instance. A host can support a virtual machine104, a virtual computing instance, a container, and/or any other virtualized instance. The servers112can include an RSA housing a plurality of physical servers, and one or more blade servers.

The servers112can host or execute virtual machines104. The data storage device(s)118can include one or more devices for storing data. The data storage device(s)118can be implemented as any type of data storage, including, but without limitation, a hard disk, optical disk, a redundant array of independent disks (RAID), a solid state drive (SSD), a flash memory drive, a storage area network (SAN), or any other type of data storage device. The data storage device(s)118can include rotational storage, such as a disk. The data storage device(s)118can also include non-rotational storage media, such as SSD or flash memory. The data storage device(s)118can provide a shared data store that is accessible by two or more physical hosts in the cluster116. The networked environment100can include a remote data storage device, such as data storage device103. The remote data storage device103is accessible by the set of servers112through the network106. Networking resources can include on-host and off-host components. The on-host components can include physical network interface controller (NIC). The off-host components can include a switch and rack.

The virtual machines104in the cluster116can include highly diverse resource requirements along central processing unit (CPU), memory, and input/output (I/O) dimensions. Existing schedulers can result in sub-optimal virtual machine placements for virtual GPU-enabled systems, causing host network saturation and overloading of network links in core/aggregation level. A distributed resource scheduler (DRS) can include a scheduler108for managing virtual GPU enabled resources in a cluster, such as CPU, memory and storage.

The scheduler108can include a network-aware and virtual GPU-aware distributed resource scheduler. The scheduler108can execute on one or more computing devices associated with the data center101, such as a server in the set of servers112. In other examples, the scheduler108can execute in the cloud102.

The scheduler108can optimize assignment of a task to a particular GPU110that includes or supports virtual GPUs120. While some examples provided in the present disclosure refer to assignment of virtual machines104, the scheduler108can also assign other types of tasks. For example, a task can include a group of virtual machines, a virtual machine, an application, or a thread. The scheduler108can simulate assignment of tasks within a particular graphics configuration that includes, for example, a particular number of GPUs, to generate an optimized assignment algorithm. The optimized algorithm can be correlated with the graphics configuration.

In addition to management of virtual GPUs, the scheduler108can manage dynamic entitlement. Entitlement can be a function of the virtual machines actual resource demands, overall cluster capacity, and the virtual machines resource settings. The VM resource settings can include reservations, limits, and shares. A reservation can include a claim or guarantee on a specific amount of a resource should the virtual machine demand it. A virtual machine's entitlement for a resource is higher than its reservation and lower than its limit. Dynamic entitlement can be equal to virtual machine demand if there are sufficient resources in the cluster to meet all virtual machine demands Otherwise, entitlement can be scaled down based on cluster capacity, the demands of other virtual machines, and settings for reservations, shares, and limits. Host load, or normalized entitlement, can be calculated by summing up entitlements of virtual machines running in a host, and normalizing it using the host's capacity. This normalized entitlement can be used to calculate a cluster balance metric, which can include a standard deviation of the normalized entitlements of hosts. Optimization can include minimizing the standard deviation value close to zero when making assignment decisions or load-balancing considerations. Support for reservations on a virtual machine's outbound bandwidth, such as transmit bandwidth, can allow the scheduler108to perform an admission control check to ensure that the sum of network reservations on a host do not exceed its capacity.

FIG.2Ais a block diagram of a host computing device200for serving one or more virtual machines104. The illustrated host computing device200can be implemented as any type of host computing device, such as a server112. The host computing device200can be implemented as a VMWARE® ESXi host. The host computing device200can include a host for running one or more virtual machines104.

The host computing device200can represent any device executing instructions, for example, application(s), operating system(s), operating system functionalities, and other functionalities associated with the host computing device200. The host computing device200can include desktop personal computers, kiosks, tabletop devices, industrial control devices, and servers. The host computing device200can be implemented as a blade server within a RSA. Additionally, the host computing device200can represent a group of processing units or other computing devices.

The host computing device200can include a hardware platform202. The hardware platform202can include one or more processor(s)204, a memory206, and at least one user interface, such as user interface component250.

The processor(s)204can include any quantity of processing units and can execute computer-executable instructions for implementing the described functionalities. The instructions can be performed by the processor or by multiple processors within the host computing device200and can be performed by a processor external to the host computing device200.

The host computing device200can include one or more computer readable media, such as the memory206. The memory206can include media associated with or accessible by the host computing device200. The memory206can include portions that are internal to the host computing device200, external to the host computing device, or both. In some examples, the memory206can include a random access memory (RAM)210and read only memory (ROM)212. The RAM210can be any type of random access memory. The RAM210can be part of a shared memory architecture. In some examples, the RAM210can include one or more cache(s). The memory206can include stores one or more computer-executable instructions214.

The host computing device200can include a user interface component. In some examples, the user interface can include a graphics card for displaying data to the user and receiving data from the user. The hardware platform202or graphics card can include a GPU110. The user interface can also include computer-executable instructions—for example, a driver, for operating the graphics card. Further, the user interface can include computer-executable instructions such as a driver for operating the display. User interface can be shown on a display such as a touch screen displays or natural user interface. The host computing device200can also provide the user interface through hardware including speakers, a sound card, a camera, a microphone, a vibration motor, one or more accelerometers, a BLUETOOTH communication module, global positioning system (GPS) hardware, and a photoreceptive light sensor.

The hardware platform202can also include a network communications interface component216. The network communications interface component216includes a network interface card and/or computer-executable instructions such as a driver for operating the network interface card. Communication between the host computing device200and other devices can occur using any protocol or mechanism over any wired or wireless connection. In some examples, the communications interface is operable with short range communication technologies such as by using near-field communication (NFC) tags.

The data storage device(s)218can be implemented as any type of data storage, including, but without limitation, a hard disk, optical disk, a redundant array of independent disks (RAID), a solid state drive (SSD), a flash memory drive, a storage area network (SAN), or any other type of data storage device. The data storage device(s)218can include rotational storage, such as a disk. The data storage device(s)218can also include non-rotational storage media, such as SSD or flash memory. In some non-limiting examples, the data storage device(s)218provide a shared data store. A shared data store is a data storage accessible by two or more hosts in a host cluster.

The host computing device200can host one or more virtual computing instances, including, but not limited to, virtual machines104aand104b. The virtual machine104acan include instructions including one or more application(s)224, a GPU driver225, and an operating system228. The operating system228can be a guest operating system of the virtual machine104a. The virtual machine104bcan include instructions including one or more application(s)226, a GPU driver227, and an operating system230. The operating system230can be a guest operating system of the virtual machine104b. The instructions, when executed by the processor(s)204, can operate to perform functionality on the host computing device200.

Application(s) can include mail application programs, web browsers, calendar application programs, address book application programs, messaging programs, media applications, location-based services, search programs, and the like. The application(s) can communicate with counterpart applications or services such as web services accessible through a network. For example, the applications can represent downloaded client-side applications that correspond to server-side services executing in a cloud.

In some examples, modern enterprise applications in data center environments can be distributed in nature and can be I/O intensive. Each component of such distributed applications is packed into individual virtual machines and deployed in clusters of physical machines, such as, but not limited to, VMware vSphere clusters. In these examples, each component can have different resource demands. Each of the virtual machines running a component of a distributed application can also have highly diverse resource requirements. The scheduler108can perform an infrastructure optimization such that the application(s) running inside one or more virtual machines104is allotted the necessary resources to run.

Each virtual machine can include a guest operating system (OS). For example, virtual machine104acan include a guest operating system (OS)228, and virtual machine104bcan include guest operating system230. Each virtual machine can also include a GPU Driver. In this example, virtual machine104acan include GPU driver225, and virtual machine104bcan include GPU driver227. The host computing device200further includes one or more computer executable components. Components can include a hypervisor232. The hypervisor232is a virtual machine monitor that creates and runs one or more virtual machines, such as, but without limitation, virtual machine104aor virtual machine104b. The hypervisor232can be implemented as a vSphere Hypervisor from VMware, Inc.

The host computing device200running the hypervisor232can be a host machine, and the virtual machine104acan be a guest machine. The hypervisor232can present the operating system228of the virtual machine104awith a virtual hardware platform. The virtual hardware platform can include virtualized processor234, memory236, user interface device238and network communication interface240. The virtual hardware platform, virtual machine(s) and hypervisor are illustrated and described in more detail below.

FIG.2Bis a drawing that illustrates an example of passthrough operation for GPUs110of the host computing device. In passthrough operation, the scheduler108can assign the virtual machine104ato the GPU110aand the virtual machine104bto GPU110b. In this mode of operation, the scheduler108can give a virtual machine direct access to the physical GPU110, and the virtual machine104can use the GPU as a native device. The operating system228can use the GPU driver225to control a GPU device110a, and the operating system230can use GPU driver227to control a GPU device110b. Accordingly, passthrough operation can allow exclusive assignment of a particular virtual machine to a particular GPU. Alternatively, software GPU sharing can be utilized in passthrough mode. In some cases, software GPU sharing is considered separate from passthrough operation.

To enable software GPU sharing, the hypervisor232can provide an abstraction layer that permits virtual machines to behave as though they have a dedicated GPU. For example, the GPU receives a single stream of requests, as though it serves only one host. The hypervisor232can include a driver that coordinates access to a GPU by the virtual machines on that server. The abstraction layer can be responsible for defining a uniform API that the virtual machines use and translating that API to a form supported by the GPU or an API of the GPU. The abstraction layer can also coordinate access to the GPU among all the virtual machines on that server that are GPU enabled.

FIG.2Cis a drawing that illustrates an example of mediated passthrough operation for virtual GPU enabled GPUs110in the host computing device. One example of a mediated passthrough solution is NVIDIA® GRID vGPU. In mediated passthrough operation, the scheduler108can assign the virtual machine104ato the vGPU120aand the virtual machine104bto vGPU120b. The operating system228can use GPU driver225to control a vGPU device120a, and the operating system230can use GPU driver227to control a vGPU device120b. Accordingly, mediated passthrough operation can allow exclusive assignment of a particular virtual machine104to a particular vGPU120. In some cases, a vGPU120can operate similarly to a GPU110from the perspective of the virtual machine104.

A vGPU manager component can be installed and executed in the hypervisor layer and can virtualize the underlying physical GPUs110. For example GPUs110, including NVIDIA® Pascal and others, can offer virtualization for both graphics and GPGPU (CUDA) applications.

A type of vGPU profile can be determined based on the amount of graphics memory each virtual machine can have. Table 1 includes available vGPU profiles for a GPU110, the graphics memory for each virtual machine assigned to a run queue with the corresponding vGPU profile, and maximum number of virtual machines per physical GPU for each profile type. The vGPU specific profile types can be applicable to NVIDIA® Pascal P40 and other GPUs110with 24 gigabytes of graphics or GPU memory. A type can correspond to an amount of graphics memory per virtual machine.

The memory in the physical GPU110can be divided, for example, into equal chunks and assigned to each virtual machine. Where equal division is used, each run queue and vGPU120of the GPU110can include the same vGPU profile, as the vGPU profiles can be correlated to allocated memory for the vGPU120. However, unequal division can also be used, such that a vGPU120and run queue can be created on the GPU110as long as the GPU110includes sufficient unallocated memory to support a memory requirement of the vGPU profile of the vGPU120.

For example, if a GPU110includes 24 gigabytes of memory and one existing vGPU120has been allocated 12 gigabytes, the GPU110can have 12 gigabytes of unallocated memory. A new vGPU120and run queue can be created with a vGPU profile of 1, 2, 3, 4, 6, 8 or 12 gigabytes, but a vGPU profile of 24 gigabytes would not be supported. In other words, the scheduler108can determine that a new vGPU profile for a new run queue or vGPU120can be created if a memory requirement of the new vGPU profile is less than or equal to the unallocated memory of the GPU110.

Selection of a vGPU profile can define a number of virtual machines that can concurrently share the GPU and the performance that can be achieved by GPU based applications running inside those virtual machines. The performance of a vGPU can also depend upon the application/workload that is being executed. For a given task, using a higher-numbered profile or vGPU type can give improved performance in comparison to using a lower-numbered profile or vGPU type. A higher-numbered profile, for example, P40-24Q, can indicate a lower number of concurrent workloads and more device memory, which can reduce the GPU-CPU communication. Using a higher profile such as P40-24Q, as opposed to a lower numbered profile such as P40-6Q, can result in lower execution time for a job/task while increasing the waiting time for other jobs and reducing the utilization of the GPU. As a result, in some cases, in a cluster116of servers112with one or more GPUs110per server that service a number of tasks, the assignment of tasks to GPUs110can determine the utilization of the GPUs110, the time to complete the jobs and the time spent by a job waiting for a GPU110to become available.

FIG.3is an exemplary block diagram illustrating a scheduler108. The scheduler108can place virtual machines on hosts with GPUs and assign virtual machines to a particular vGPU enabled GPU. The scheduler108can be executed by the hardware platform202, for example, in a privileged mode or kernel modein the hypervisor232. The scheduler108can also be executed in a user mode or superuser mode—for example, in a guest operating system such as the operating system228or operating system230. In some cases, the scheduler108can include a component executed by the hypervisor232and another component in a guest operating system.

The scheduler108can include a fixed-share scheduler301, an equal-share scheduler303, a best-effort scheduler305, and other schedulers based on various timing policies. The fixed-share scheduler301can include an optimizer306that finds a suitable host for an incoming or distressed virtual computing instance to optimize based on fixed-share timing as discussed further below. The equal-share scheduler303can include an optimizer307that finds a suitable host for an incoming or distressed virtual computing instance to optimize based on equal-share timing as discussed further below. The best-effort scheduler305can include an optimizer308that finds a suitable host for an incoming or distressed virtual computing instance to optimize based on best-effort timing as discussed further below. In some cases, other schedulers are utilized, or a combination of schedulers is utilized.

The collector310can collect task data associated the currently assigned tasks or virtual machines104. The collector310can provide this task data to the scheduler108. The statistics received from the collector310can include a number of GPUs, a number of tasks, host resource capacity, virtual machine resource demand and virtual machine resource usage. The host resource capacity data can include number of GPUs, total CPU and GPU utilization, total consumed memory and total network receive and transmit usage. The collector310can provide per-VM usage statistics, such as the virtual machine resource demand and virtual machine resource usage, to the scheduler108.

Network traffic between hosts and virtual machines in a cluster can be unstable. The network traffic frequently includes periods of high usage followed by low usage. Due to the peaks and valleys in network traffic, averaging network traffic usage for a virtual machine104or host200is not always useful. Therefore, the virtual machine network resource usage statistics can be provided using a percentile measure. In these examples, a percent high-water mark can be used for stability in determining network usage. In one non-limiting example, the percent high-water mark can be the seventy-fifth percentile. In other examples, a high-water mark of the eightieth percentile can be utilized.

Moreover, in some examples, the cluster statistics can include internal send and receive traffic occurring on a single host, as well as external send and receive traffic occurring across different hosts. The external network traffic can be more expensive than the internal network traffic. These internal versus external communications traffic statistics are considered to avoid separating virtual machines104which communicate at a high rate with one another on the same host200.

The scheduler108can retrieve the statistics from the collector310to evaluate the cluster status as the virtual machines104are generated or created and arrive in an arrival que321for assignment to a GPU110. The scheduler108can receive basic topology information, graphics configuration data, rack boundary data, and link bandwidth data from the static configuration component314. The graphics configuration data can include a number of GPUs110, a number of vGPU enabled GPUs, a GPU memory for each GPU110, a list of available vGPU profiles for each GPU110and a list of current run queues322with corresponding vGPU profiles. Each run queue322can be assigned a particular vGPU profile, and all tasks or virtual machines assigned to the run queue322can be performed according to the profile. Assignment of a virtual machine104to a particular GPU110can include assignment of the virtual machine104to a particular run queue322of the GPU based on a vGPU profile of the run queue322. A task or virtual machine104can be generated and assigned a particular vGPU profile, for example, based on the memory requirements or other requirements of the task.

The scheduler108can assign a particular a task or virtual machine104to a particular GPU110and run queue322. A run queue322can be a queue to be handled by a vGPU120of the GPU110. In some cases, scheduler108can also place the virtual machine104on a particular host318that includes or has access to the GPU110. The hosts200can include virtual machines104running on one or more of the hosts200. The hosts200can be implemented as physical host computing devices. A host200can also include a hypervisor running one or more virtual machines.

FIG.4shows an example flowchart400, describing steps that can be performed by instructions executed by the data center101. Generally, the flowchart400describes how the scheduler108can determine whether to assign a particular task/job/virtual machine to a particular GPU, given the constraints imposed by the particular virtual GPU solution, such as vGPU. The scheduler108can determine an optimal virtual machine assignment algorithm for a particular system and utilize the algorithm to assign the virtual machine to a GPU run queue.

In step403, the scheduler108can identify a predetermined set of one or more assignment algorithms. For example, the scheduler108can provide a user interface element through which an assignment algorithm can be entered, uploaded, or otherwise provided to the scheduler108. The assignment algorithms can define rules or policies that can be used to determine whether a particular task or virtual machine should be assigned to a particular GPU, based on a graphics configuration of a system. The graphics configuration can include a number of GPUs, a number of vGPU enabled GPUs, a GPU memory for each GPU, a list of available vGPU profiles for each GPU and a list of existing run queues322and corresponding vGPU profiles.

Predetermined task assignment rules or algorithms can include first come first serve (FCFS), longest first, longest wait first, random, and shortest first. FCFS: On each simulator clock tick, the FCFS algorithm assigns first virtual machine on the arrival queue321, then the second, and so on. Longest first: On each simulator clock tick the longest first assignment algorithm tries to assign the virtual machine with the longest expected run time first, then the one with the second longest run time, and so on. Expected run time can be defined by a user that creates the task, or can be determined based on an average measured time for similar tasks such as those with a related process list, task type, number of lines of code, or other similarity factors. Longest wait first: On each simulator clock tick, this algorithm tries to assign the virtual machine with the longest wait time first, then the one with the second longest wait time, and so on. Wait time can refer to wait time in an arrival queue321, run queue322, or both. Run queue wait time can be utilized where a currently assigned virtual machine is reevaluated, for example, to update its placement to a particular position in a run queue322. Random: On each simulator clock tick, this algorithm randomly selects a virtual machine and tries to assign it, then selects another one at random and so on. Random selection can refer to selection based on a random or pseudorandom selection function. Shortest first: On each simulator clock tick, this algorithm tries to assign the virtual machine with the shortest expected run time first, then the one with the second shortest run time, and so on.

In step406, the scheduler108can generate an optimized algorithm based on machine learning. The scheduler108can correlate these optimized algorithms with aspects or parameters of the graphics configuration including a number of GPUs110, an average or median arrival rate for virtual machines104queued in the arrival queue321, a number of GPUs110with a particular vGPU profile, an average or median number of virtual machines104assigned to each run queue322and other parameters.

A machine learning calculation can utilize simulated and actual inputs, as well as simulated and actual outputs, in order determine the optimal assignment algorithm to maximize for a predetermined cost function. In some cases, the machine learning calculation can select one of the predetermined assignment algorithms as an optimal algorithm. The scheduler108can select an optimal algorithm using simulation and analysis of actual results. In other cases, the machine learning calculation can generate a new algorithm or set of rules. The new algorithm can include a modified version of one or more of the predetermined assignment algorithms. The scheduler108can modify the predetermined assignment algorithms using actual results, simulations, and machine learning techniques as discussed below.

The scheduler108can include a simulator that allows comparison of different techniques and algorithms. A cost function can be defined and can be used to compare the different solutions. The simulator can be built to utilize as many assignment algorithms as needed. The simulator can be viewed as including logical components; a first component can generate a load, task or virtual machine that can be assigned on a vGPU enabled system or cloud. A second component can model the vGPU enabled system as a set of run queues322and the assignment of tasks in the vGPU enabled system using any one of the many assignment algorithms under consideration. The simulator can also consider real-world or actual tasks collected by the cluster and task statistics collector310.

The load-generator can generate tasks using a user-provided or simulator-generated rate parameter, lambda. In the simulator, the inter-arrival time between tasks can be distributed exponentially, linearly or uniformly. In some examples, each time a job is created, the simulator can assign it in a particular category of a list of for task categories. Examples of task categories or types can include:Tasks that do inference using a machine learning (ML) model that has been trained (these can be called ML-inference tasks),Tasks that train a ML model (these can be called ML-training tasks) andTasks that run a CAD software (these can be called CAD-tasks).

Additional categories can also be considered. Each category can include different characteristics. The ML-inference tasks can have a run-time less than one second and need either P40-12Q or P40-24Q profile. The ML-training tasks can use a P40-12Q or a P40-24Q profile and can have a run time of forty-five minutes when using convolution neural networks (CNN) on MNIST benchmark. A run-time of six hours can result when using the recurrent neural network (RNN) on PTB benchmark. CAD-tasks are interactive tasks. In some examples, CAD-tasks can be created in a time window between 8 AM and 10 AM each day and can complete in a time window between 4 PM and 6 PM. These time windows can be chosen or determined by the simulator based upon real-world usage of vGPU enabled systems. The vGPU profile request for CAD-tasks can be uniformly distributed over all available P40 profiles. This can be based on the performance of ML and CAD benchmarks. The vGPU profile associated with a task can be an example constraint on when and where it can be assigned.

ML-training tasks can be considered batch tasks and can be suspended and resumed as needed to make space for other tasks. The example set of results present a rule that can be utilized to decide when to suspend and resume ML-training tasks. For example, ML-training tasks can run only at night, between 6 PM and 8 AM based on industry practices. Other task categories can utilize other rules as defined in a usage rule, policy, or algorithm that includes suspend, resume, run durations, time windows for execution, and other rules various ways.

Once tasks are created by a user or the simulation, they can be assigned into one of the categories described above, for example, using a uniform random variable. With a probability of 50%, a task created between 8 am-10 am can be an ML-inference task, otherwise it can be a CAD-task. Outside this time window, a task can be an ML-inference task with 98% probability and with 2% probability it can be a ML-training task. In other examples, these probabilities can be varied and optimized based on desired or actual conditions, or otherwise as defined. Once a task has been created, it can be queued in an arrival queue321. A system or simulation can include a single arrival queue321or a particular number of arrival queues321. For each simulation clock tick, a task or tasks can be selected from the arrival queue(s)321using an assignment algorithm and assigned to one of several run queues322. Each run queue322can include a list of tasks currently being executed by a GPU110.

Where multiple vGPU profiles are supported, each can support different maximum number of virtual machines. A run queue size can refer to a maximum number of tasks that can be accommodated for a particular vGPU profile. A task can be referred to as a virtual machine since each task can run in its own virtual machine. In some examples, the vGPU profile of a run queue322can be defined by the vGPU profile of the first task that is scheduled on that queue. Tasks that arrive second, third or later at a run queue322can join the queue based on a number of conditions being satisfied, for example:The vGPU profile of the incoming task matching the vGPU profile of the run queue322.The current number of tasks assigned to the run queue322being less than the maximum allowed number of tasks or virtual machines for the run queue's vGPU profile.

Once a run queue322empties out, for example because the GPU has completed all the tasks assigned to it, its profile can be forgotten, erased or removed. In some cases, the run queue322is not associated with any profile until a task is assigned to it, at which time it can assume the profile of that task. Another way to erase the profile of a run queue322can be to suspend all the tasks on that queue thereby emptying it out and clearing its profile. This mechanism of erasing the profile of a run queue322can create another dimension to be handled by assignment algorithms.

Suspending and subsequently resuming tasks as an assignment technique can be used in multiple different ways. In one example, one or more tasks can be suspended to free up capacity in a run queue322for an incoming task with the same vGPU profile. In a second example, all the tasks on a run queue322can be suspended in order to allow assignment of a new task, regardless of its vGPU profile. These two dynamic suspend-resume techniques can allow assignment algorithms significant flexibility.

Once a task has been assigned to a run queue322, the GPU110can control its execution using a number of timing policies, which can include fixed-share timing, equal-share timing, or best-effort timing. A timing policy can be selected based on a user selection or can be selected by the scheduler108to maximize for the cost function. Some example timing policies are described below.

In a fixed-share timing policy, the GPU can divide time into as many time-slices as the maximum number of tasks or virtual machines supported by the GPU at the current vGPU profile. For example, if the GPU is running with a P40-4Q profile, it can divide into six time-slices. If there are only two tasks running on the GPU, each can get one time-slice and the remaining four time-slices can be wasted. This timing policy can result in time-slices being wasted if the run queue322is not full but can result in the execution time for a task regardless of how full the queue is. In other words, the quantum of time for task execution can be equivalent regardless of whether the run queue322is 10% full, or 50% full, or 100% full.

In an equal-share timing policy, the GPU can divide time into as many time-slices as there are tasks in the run queue322. Compared to fixed-time timing, this policy can waste fewer time-slices but can still assign time-slices to a task even if the task does not have any computations to execute on the GPU. If a task is waiting on an I/O or doing CPU computation, it can nevertheless hold on to its time-slice. This policy can potentially waste time-slices but can result in a fair division of GPU time to each task on the run queue322.

In a best-effort timing policy, the GPU can assign time-slices to those tasks that have GPU computation to execute. For example, if a task on the run queue322does not have any GPU computation, it does not receive its time-slice. This timing policy can result in a high GPU utilization but can be unfair in how much time a task receives.

The simulator can implement each of the timing policies. In some cases, the timing policy that is used can be selected by a user. The simulator can also determine if the performance of a particular assignment algorithm is impacted based on the choice of timing policy, and can select a timing policy to maximize a cost function

A cost function can be used to compare different virtual machine assignment algorithms as a product of metrics that can include utilization of the GPUs, a number of tasks completed, time spent by a task waiting for a GPU to become available, and other factors. In some examples, a system can include “r” GPUs, and the simulation can run for “C” clock cycles, as well as a run queue322, wherein “Ri” can execute a task for “Ric” clock cycles. A utilization, “U,” of the GPUs can be described as:

The number of tasks completed can be computed by calculating, at the end of the simulation or for a predefined period of time, the number of tasks completed to the total number of tasks in the system. The total number of tasks in the system can be defined as the sum of the tasks waiting to get onto a run queue322, the tasks in the run queues322, and the tasks that have completed execution. This ration can be defined as “N.”

In some cases, to obtain an optimal solution, the simulator can maximize the metrics “U” and “N,” and minimize time spent waiting. The simulator can redefine the third metric as the ratio of time spent executing to the total time spent in the system so that if a task or job “J” spends “Jri” cycles executing on a run queue322, and “Jwi” cycles waiting to get onto a run queue322, and there are “m” tasks in total in the system, then the ratio, E, can be defined as:

The ratio E can be a ratio of an average execution for a plurality of virtual machines and an average total time in the system for the plurality of virtual machines. Total time can include execution time and wait time. “Jri” can depend on a number of cycles during which the task is actually executing, rather than just the number of cycles for which the task is on the run queue322. This distinction can be relevant because when a GPU is multiplexed among many tasks, only one task executes at a time, and the task does not execute when the current time slice does not belong to it. Further, different GPU timing policies can handle time slices differently as described. A fixed-share timing policy can have a different value for this ratio than a best-effort timing policy as a result of time-slices left idle with fixed-share timing as compared to best-effort timing. A second point to note is that when a task is suspended and subsequently resumed, the clock cycles spent during the suspend and resume operations can be included in the term, “Jri.” The time between completion of suspend and the start of resume can be spent in the waiting queue and can be included in the term, “Jwi.”

Cost functions can be defined in multiple ways, as the specific needs of a system or priorities of administrators can vary. In some cases, the cost function can be defined as:
Cost=U×N×E,0≤Cost≤1  (3)
In other examples, cost function can be defined as a geometric mean of two parameters:

Cost=U×E2,0≤Cost≤1(4)
Other cost functions can also be used.

The VM-assignment simulator can rank the assignment algorithms using cost as a criterion. The simulator can also use machine learning to develop new assignment algorithms that can maximize for the cost function. An algorithm that maximizes the cost can be considered optimal.

Machine learning techniques can include simulated annealing. On each simulation clock-cycle, the simulation can generate a state S0 that includes assignments of tasks to GPU110run queues322based on a predetermined algorithm, such as a random algorithm. The simulation can perform simulation for state S0, and compute the cost function. The simulation can set the simulated annealing temperature parameter T=1.0. The simulated annealing technique can be repeated while T>0.0001. For each value of T, the simulation can pick a task at random from state S0. Replace it with a random task NOT in S0. The simulation can compute a cost function for the changed S0. If the new cost is lower, the simulation can keep the changed S0. If the new cost is higher BUT the acceptance probability>a random number from a uniform distribution, the simulation can keep the changed S0. Otherwise, the simulation can discard the change in S0 and put back the task that was previously removed. The simulation can repeat for an updated temperature that can be calculated, for example, as a previous temperature*0.9.

Machine learning techniques can include bin packing heuristic. For this technique, on each simulation clock cycle, for each Job (J) waiting to run, identify GPUs on which the job can run. For each GPU (G) on which the job can run, the simulation can calculate the cost-function C if Job J was assigned to GPU G. The simulation can record or store the tuple <J, G, C>. Choose the tuple <J, G, C> with the highest value of C. The simulation can sort the tuples <J, G, C> using C as the key in reverse order. The simulation can select as many Jobs as possible from the sorted list of tuples.

Other machine learning techniques can also be used, such as particle swarm, genetic algorithm and other machine learning techniques. The scheduler108can perform these techniques using real and simulated systems with a wide variety of graphics configurations. The scheduler108can generate a table or other data structure that correlates an optimized algorithm with a graphics configuration. In some cases, the data structure can specify optimized algorithms correlated to a single parameter, such as a number of GPUs. In other cases, the data structure can specify the optimized algorithm based on multiple parameters of the graphics configuration. The table or other data structure can be stored in the data storage device103or118. An optimized assignment algorithm can be selected or generated based on the results that optimize for the cost function, and can be correlated to a graphics configuration. As can be understood, the machine learning techniques can be seeded or trained based on known assignment techniques but can result in modified versions of the known assignment techniques as results of the machine learning technique are analyzed. For example, in simulated annealing, while the initial assignment can be based on one of the known techniques, replacement of a random tasks in S0 can result in a new rule or modification to the initial seed or known technique. In any of the machine learning techniques, the scheduler108can compare the results of existing algorithms to machine learning analyses in order to determine modifications to the existing algorithms that optimize for the cost function.

The optimized algorithm can specify rules that can be utilized to determine whether to assign a task or to wait. The optimized algorithm can also specify rules that determine an optimal run queue322. Because task position in a run queue322can be considered in these techniques, an optimal position in the run queue322can also be determined.

In step409, the scheduler108can identify a virtual machine104in an arrival queue321. For example, an administrator can generate a new task to perform in a virtual machine104. Once the virtual machine104is defined, it can be queued in an arrival queue321. The arrival queue321can include a list of virtual machines104that are not assigned to a GPU110. The virtual machine104can be assigned a vGPU profile. In some cases, the scheduler108analyzes a process list of the virtual machine104and assigns the vGPU profile based on processes identified in the process list. For example, the scheduler108can associate a process with a particular memory requirement, determine a memory requirement of the virtual machine104based on the process list, and identify an appropriate vGPU profile that corresponds to the memory requirement. In other cases, the scheduler108can associate a particular vGPU profile with a characteristic of the virtual machine104. Characteristics of the virtual machine104can include a type of the virtual machine104or task, a process list, a particular process, a size of the virtual machine104and a time the virtual machine104was created and queued.

In step412, the scheduler108can determine or identify a graphics configuration of the system. For example, the scheduler108can receive statistics from the collector310and the static configuration component314. The scheduler108can receive, from the collector310and the static configuration component314, system configuration data that includes the graphics configuration, as well as basic topology information, rack boundary data and link bandwidth data. The graphics configuration can include a number of GPUs110, a number of vGPU enabled GPUs, a GPU memory for each GPU110, a list of available vGPU profiles for each GPU110and a list of current run queues322with corresponding vGPU profiles. Each run queue322can be assigned a particular vGPU profile, and all tasks or virtual machines assigned to the run queue322can be performed according to that vGPU profile.

In step415, the scheduler108can determine whether an existing run queue322matches a vGPU profile of the virtual machine104. If no run queue322in the system includes a vGPU profile that matches that of the virtual machine104, the scheduler108can move to step418. If one or more of the existing run queues322include a vGPU profile that matches the vGPU profile of the virtual machine104, then the scheduler108can move to step421.

In step418, the scheduler108can create a new run queue322with a vGPU profile that matches the vGPU profile of the virtual machine104. The new run queue322can be added to a GPU110that supports the particular vGPU profile of the virtual machine104and includes sufficient unallocated memory to create the new run queue322. For example, the scheduler108can determine a memory size of the GPU110specified in the graphics configuration and a current list of its run queues322, along with the vGPU profile of each run queue. The scheduler108can determine unallocated memory of the GPU110by subtracting memory allocated to each existing run queue322according to its vGPU profile. The scheduler108can determine that the GPU110includes sufficient unallocated memory if the unallocated memory is equal to or greater than a memory requirement of the new vGPU profile.

In other cases, memory can be allocated equally in a GPU110, and each run queue322can include the same vGPU profile. Each vGPU profile can be associated with a maximum number of vGPUs120or run queues322supported concurrently, for example, based on equal division of memory of the GPU110. The scheduler108can determine whether a number of run queues322of the GPU110is less than the maximum number of queues. The new run queue322can be added to a GPU110that is using the vGPU profile of the virtual machine104, and the GPU110includes less than the maximum number of queues.

In step421, the scheduler108can identify an optimized algorithm based on graphics configuration of the system. As discussed in step406, the scheduler108can, based on machine learning of real and simulated assignment results, correlate optimized algorithms with aspects or parameters of graphics configuration. The scheduler108can analyze the graphics configuration of the system, including its number of GPUs110, average or median arrival rate for virtual machines104queued in the arrival queue321, number of GPUs110with a particular vGPU profile, average or median number of virtual machines104assigned to each run queue322, and other parameters. The scheduler108can match the current graphics configuration to an optimized algorithm based on a table or other data structure stored in the data storage device118or103that correlates optimized algorithm with graphics configuration. In some cases, the scheduler108can identify an optimized algorithm based on a single parameter of the graphics configuration, such as a number of GPUs. In other cases, the scheduler108can identify the optimized algorithm based on multiple parameters of the graphics configuration.

In step424, the scheduler108can assign a virtual machine104to a run queue322of a GPU110based on the optimized algorithm. The scheduler108can also place or implement the virtual machine104in a host200available to the selected run queue322. In some cases, the scheduler108places the new virtual machine104at an end of the run queue322to which it is assigned. The scheduler108can also determine an optimal position in the run queue322and assign the virtual machine104to that position. The scheduler108can move or shift a position of one or more virtual machine104to accommodate the new virtual machine104.

Multiple virtual machines104, such as a batch or group of virtual machines104can be considered concurrently. The group of virtual machines104can include all virtual machines104in the arrival queue321or a predetermined number of virtual machines104from the arrival queue321. Where multiple virtual machines104are analyzed concurrently, the scheduler108can determine an optimal order to assign the virtual machines104and perform the assignments of the virtual machines104in that order.

The scheduler108can perform the identification of the optimized algorithm to utilize and the assignment of the virtual machine104in real time, for example, within in milliseconds or tens of milliseconds. However, generating the optimized algorithms can be performed for a predetermined initial simulation time and continuously during real-world operations.

FIG.5Ashows an example of normalized cost vs. a number of run queues322for an arrival rate of 72 tasks per hour, using the best-effort timing policy. For each choice of assignment policy, parameters can be varied, which can include varying the number of run queues322from four to eight to twelve. The cost function in this example can be the cost function of equation 3.

FIG.5Bshows an example of normalized cost vs. a number of run queues322for an arrival rate of 144 tasks per hour, using the best-effort timing policy. For each choice of assignment policy, parameters can be varied, which can include varying the number of run queues322from four to eight to twelve. The cost function in this example can be the cost function of equation 3.

FIG.5Cshows an example of normalized cost vs. a number of run queues322for an arrival rate of 216 tasks per hour, using the best-effort timing policy. For each choice of assignment policy, parameters can be varied, which can include varying the number of run queues322from four to eight to twelve. The cost function in this example can be the cost function of equation 3.

FIG.5Dshows an example of normalized cost vs. a number of run queues322for an arrival rate of 288 tasks per hour, using the best-effort timing policy. For each choice of assignment policy, parameters can be varied, which can include varying the number of run queues322from four to eight to twelve. The cost function in this example can be the cost function of equation 3.

In the examples ofFIGS.5A-5D, the “shortestFirst” policy can be most suitable to the system configuration. The performance measured using the normalized cost function value can show an improvement in the cost function values as the arrival rate increases from 72 to 144 per hour but subsequent increases in the arrival rate have minimal or no impact on the cost function values. In other situations, other policies can be chosen based on user selection, cost function definition, or other considerations. The simulator can also include assignment policies based on simulated annealing optimization, particle swarm optimization, and a bin packing optimization. Different cost functions can be designed and utilized for comparison or ranking of assignment policies. Different workloads can also be utilized and compared based on real world expectations for execution in a vGPU cloud, for example, based on actual or detected workloads in a functioning cloud.

A number of software components are stored in the memory and executable by a processor. In this respect, the term “executable” means a program file that is in a form that can ultimately be run by the processor. Examples of executable programs can be, for example, a compiled program that can be translated into machine code in a format that can be loaded into a random access portion of one or more of the memory devices and run by the processor, code that can be expressed in a format such as object code that is capable of being loaded into a random access portion of the one or more memory devices and executed by the processor, or code that can be interpreted by another executable program to generate instructions in a random access portion of the memory devices to be executed by the processor. An executable program can be stored in any portion or component of the memory devices including, for example, random access memory (RAM), read-only memory (ROM), hard drive, solid-state drive, USB flash drive, memory card, optical disc such as compact disc (CD) or digital versatile disc (DVD), floppy disk, magnetic tape, or other memory components.

Memory can include both volatile and nonvolatile memory and data storage components. Also, a processor can represent multiple processors and/or multiple processor cores, and the one or more memory devices can represent multiple memories that operate in parallel processing circuits, respectively. Memory devices can also represent a combination of various types of storage devices, such as RAM, mass storage devices, flash memory, or hard disk storage. In such a case, a local interface can be an appropriate network that facilitates communication between any two of the multiple processors or between any processor and any of the memory devices. The local interface can include additional systems designed to coordinate this communication, including, for example, performing load balancing. The processor can be of electrical or of some other available construction.

The flowcharts show examples of the functionality and operation of an implementation of portions of components described herein. If embodied in software, each block can represent a module, segment, or portion of code that can include program instructions to implement the specified logical function(s). The program instructions can be embodied in the form of source code that can include human-readable statements written in a programming language or machine code that can include numerical instructions recognizable by a suitable execution system such as a processor in a computer system or other system. The machine code can be converted from the source code. If embodied in hardware, each block can represent a circuit or a number of interconnected circuits to implement the specified logical function(s).

Although the flowcharts show a specific order of execution, it is understood that the order of execution can differ from that which is depicted. For example, the order of execution of two or more blocks can be scrambled relative to the order shown. Also, two or more blocks shown in succession can be executed concurrently or with partial concurrence. Further, in some embodiments, one or more of the blocks shown in the drawings can be skipped or omitted.

The computer-readable medium can include any one of many physical media, such as magnetic, optical, or semiconductor media. More specific examples of a suitable computer-readable medium include solid-state drives or flash memory. Further, any logic or application described herein can be implemented and structured in a variety of ways. For example, one or more applications can be implemented as modules or components of a single application. Further, one or more applications described herein can be executed in shared or separate computing devices or a combination thereof. For example, a plurality of the applications described herein can execute in the same computing device, or in multiple computing devices.