Scheduler of processes having timed predictions of computing loads

Patent metadata

Field	Value
Publication number	US-10216541-B2
Application number	US-201615391717-A
Country	US
Kind code	B2
Filing date	Dec 27, 2016
Priority date	Dec 29, 2015
Publication date	Feb 26, 2019
Grant date	Feb 26, 2019

Abstract

A scheduler of computer processes. The scheduler comprises first processing logic configured to obtain predictions of a computing load of a computer process to allocate. Predictions are associated with a period of time. The processing logic retrieves predictions of available computing capacities for the period of time, and determines, based on the predictions, a processing capability to allocate at least one computer process during the period of time. The scheduler may comprise second processing logic configured to create at least one Operating-System-Level virtual environment, for a computer program, that has a computing capacity equal to or higher than the predicted computing load of at least one computer process to allocate at a start of the period of time. The second processing logic may adapt the computing capacity of an Operating-System-Level virtual environment to the predictions of the computing load of at least one computer process during the period of time.

First claim

What is claimed is:

1. A non-transitory computer-readable storage medium storing one or more sequences of instructions for a scheduler of computer processes to be executed upon a cluster of processing capabilities, wherein execution of the one or more sequences of instructions cause:
obtaining predictions of a computing load of at least one computer process to allocate, wherein said predictions are associated with a period of time;
retrieving predictions of available computing capacities of the cluster of processing capabilities for the period of time;
determining, based on the predictions of the computing load for the period of time and the predictions of the available computing capacities for the period of time, a processing capability to allocate said at least one computer process during said period of time;
creating at least one Operating-System-Level virtual environment for said at least one computer process, said at least one Operating-System-Level virtual environment having a computing capacity equal to or higher than at least one of said predictions of the computing load of said at least one computer process to allocate at a start of the period of time; and
adapting the computing capacity of said at least one Operating-System-Level virtual environment to the predictions of the computing load of said at least one computer process during said period of time.

2. The non-transitory computer-readable storage medium of claim 1 , wherein execution of the one or more sequences of instructions further cause:
calculating predictions of available computing capacities of the processing capabilities for the period of time based on computing capacities of the processing capabilities and predictions of computing capabilities of Operating-System-Level virtual environments running on computing capabilities for the period of time.

3. The non-transitory computer-readable storage medium of claim 1 , wherein said at least one computer process is a multimedia process comprising real time video encoding or transcoding, and wherein said predictions of the computing load of the process are based at least on predictions of a target index of video quality to deliver in real time.

4. The non-transitory computer-readable storage medium of claim 3 , wherein execution of the one or more sequences of instructions further cause:
calculating (a) the predictions of computing load of said multimedia process based on a resolution and a number of frames per second of video, and (b) predictions of target video quality to deliver in real time.

5. The non-transitory computer-readable storage medium of claim 3 , wherein execution of the one or more sequences of instructions further cause:
calculating (a) the predictions of computing load of said multimedia process based on a resolution, a number of frames per second, and a type of the video, and (b) predictions of target video quality to deliver in real time.

6. The non-transitory computer-readable storage medium of claim 3 , wherein the video during the period of time belongs to types of programs which have already been broadcasted, and wherein execution of the one or more sequences of instructions further cause:
calculating the predictions of computing load of said multimedia process based on the computing load of previous encoding or transcoding of this type of program at predicted target qualities.

7. The non-transitory computer-readable storage medium of claim 3 , wherein said at least one computer process executes a video encoding or transcoding process which is able to deliver video in real time while adapting its encoding quality to available computing capacities.

8. The non-transitory computer-readable storage medium of claim 1 , wherein the computing load is a CPU load.

9. The non-transitory computer-readable storage medium of claim 1 , wherein execution of the one or more sequences of instructions further cause:
selecting a processing capability to allocate said at least one computer process in order that a sum of predictions of computing capabilities of Operating-System-Level virtual environment running on a processing capability never exceeds a computing capacity of said processing capability for the period of time.

10. The non-transitory computer-readable storage medium of claim 9 , wherein execution of the one or more sequences of instructions further cause:
formulating one of a multiple knapsack problem or a bin packing problem based on the predictions of computing loads of said at least one computer process and the predictions of computing capabilities of Operating-System-Level virtual environment running on processing capabilities;
programmatically solving said one of a multiple knapsack problem or a bin packing problem; and
selecting, based on said solution to said one of a multiple knapsack problem or a bin packaging problem, a processing capability on which to allocate said at least one computer process.

11. The non-transitory computer-readable storage medium of claim 1 , wherein execution of the one or more sequences of instructions further cause:
upon a modification of the predictions of the computing load of said at least one computer process for a period of time, verifying whether a sum of predictions of computing capabilities of Operating-System-Level virtual environments running on a processing capability exceeds a computing capacity of said processing capability for the period of time; and
upon verifying that the sum of predictions does exceed said computing capacity of said processing capability for the period of time, calculating a re-allocation of Operating-System-Level virtual environments on physical machines.

12. The non-transitory computer-readable storage medium of claim 11 , wherein execution of the one or more sequences of instructions further cause:
formulating one of a multiple knapsack problem or a bin packing problem based on the predictions of computing loads of said at least one computer process and the predictions of computing capabilities of Operating-System-Level virtual environment running on processing capabilities;
programmatically solving said one of a multiple knapsack problem or a bin packing problem; and
selecting, based on said solution to said one of a multiple knapsack problem or a bin packaging problem, a processing capability on which to reallocate said at least one computer process.

13. An apparatus having a scheduler of computer processes to be executed upon a cluster of processing capabilities, comprising:
one or more processors; and
one or more non-transitory computer-readable storage mediums storing one or more sequences of instructions, which when executed, cause:
obtaining predictions of a computing load of at least one computer process to allocate, wherein said predictions are associated with a period of time;
retrieving predictions of available computing capacities of the cluster of processing capabilities for the period of time;
determining, based on the predictions of the computing load for the period of time and the predictions of the available computing capacities for the period of time, a processing capability to allocate said at least one computer process during said period of time;
creating at least one Operating-System-Level virtual environment for said at least one computer process, said at least one Operating-System-Level virtual environment having a computing capacity equal to or higher than at least one of said predictions of the computing load of said at least one computer process to allocate at a start of the period of time; and
adapting the computing capacity of said at least one Operating-System-Level virtual environment to the predi

Assignees

• Harmonic Inc

Inventors

• Le Bars Eric
• Mahe Arnaud
• Berthelot Christophe

Classifications

• H04N19/426 Primary

  using memory downsizing methods · CPC title

• G06F9/505 Primary

  considering the load · CPC title

• G06F9/5077

  Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455) · CPC title

• H04N19/40

  using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream · CPC title

• G06F9/4887 Primary

  involving deadlines, e.g. rate based, periodic · CPC title