Scheduler of processes having timed predictions of computing loads

Patent metadata

Field	Value
Publication number	US-11006137-B2
Application number	US-201916284881-A
Country	US
Kind code	B2
Filing date	Feb 25, 2019
Priority date	Dec 29, 2015
Publication date	May 11, 2021
Grant date	May 11, 2021

Abstract

A scheduler of computer processes. The scheduler obtains predictions of a computing load of at least one multimedia process comprising real time video encoding or transcoding of a video in real time, including predictions of a target index of video quality to deliver the video over a period of time. Predictions of available computing capacities of a cluster are also retrieved. A determination is made, based on the predictions of the computing load and the predictions of the available computing capacities, of a processing capability to allocate the at least one multimedia process during the period of time. At least one virtual environment is created for the at least one multimedia process. The computing capacity of the at least one virtual environment is adapted to the predictions of the computing load of the at least one multimedia 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 set of processing capabilities, wherein execution of the one or more sequences of instructions cause:
obtaining predictions of a computing load of at least one multimedia process comprising real time video encoding or transcoding of a video in real time at a video quality over a period of time;
retrieving predictions of available computing capacities of the set of processing capabilities for the period of time, wherein said set of processing capabilities resides in one or more physical machines;
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 multimedia process during said period of time;
creating at least one Operating-System-Level virtual environment for said at least one multimedia process, said at least one Operating-System-Level virtual environment having a computing capacity equal to or higher than a prediction of the computing load of said at least one multimedia 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 multimedia process during said period of time so that the encoded or transcoded video possesses said video quality throughout said period of time.

2. The non-transitory computer-readable storage medium of claim 1 , 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.

3. The non-transitory computer-readable storage medium of claim 2 , wherein 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 comprises:
determining a minimum computing load of previous encoding or transcoding for this type of program at said predicted target qualities.

4. 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 the available computing capacities of the processing capabilities for the period of time based on the computing capacities of the processing capabilities and predictions of computing capabilities of Operating-System-Level virtual environments running on the computing capabilities for the period of time.

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

6. The non-transitory computer-readable storage medium of claim 5 , 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.

7. The non-transitory computer-readable storage medium of claim 5 , 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.

8. The non-transitory computer-readable storage medium of claim 5 , 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 the 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.

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

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

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

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 the computing loads of said at least one multimedia process and the predictions of the computing capabilities of the Operating-System-Level virtual environment running on the 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 multimedia process.

13. 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 multimedia process for the period of time, verifying whether a sum of predictions of the computing capabilities of the Operating-System-Level virtual environments running on the 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.

14. The non-transitory computer-readable storage medium of claim 13 , 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 multimedia process and the predictions of computing capabilities of the Operating-System-Level virtual environment running on the processing capabilities;
programmatically solving said one of the multiple knapsack problem or the bin packing problem; and
selecting, based on said solution to said one of the multiple knapsack problem or the bin packaging problem, the processing capability on which to reallocate said at least one multimedia process.

15. An apparatus having a scheduler of computer proc

Assignees

• Harmonic Inc

Inventors

• Le Bars Eric
• Mahe Arnaud
• Berthelot Christophe

Classifications

• G06F9/505 Primary

  considering the load · CPC title

• G06F2209/5019

  Workload prediction · 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

• H04N19/426 Primary

  using memory downsizing methods · CPC title