Abstract:
The present invention discloses a system and methods for parallel processing of multiple processing job requests; the system may include a server for receiving a job request, an algorithm for segmenting the job request to a few sub jobs and a few processors for processing the few sub jobs in parallel. Each sub job contains a few frames to be processed by the job processors and the outputs of few job processors are combined into a single output. The invention further discloses methods for proportional allocation of job segments and an optimization algorithm to automatically assign job requests and to adapt the resources of the system to meet customers demand according to predefined criteria.

Description:
FIELD AND BACKGROUND OF THE INVENTION 
       [0001]    The present invention is related to the field of computers; more specifically but not exclusively, the invention is related to the field of processing few frames in parallel for speeding overall processing duration. 
         [0002]    Today, the media which is being produced by computers is increasing exponentially. The media which is being produced includes for example, videos, animations and other such combinations which are designed to “catch the eye” of the viewers, to arise intrigue, and as a result, to convey a message to the viewer or simply to draw his attention for gaining commercial value. 
         [0003]    For this reason, displaying a static message such as an advertisement to a potential viewer will probably not suffice to draw the attention of the viewer as the static ad will not stand out compared to the other animated ads which are present near the static ad. 
         [0004]    As the digital media gradually cuts out the traditional physical media, the demand for videos and animations exceeds with it. For instance, newspapers and books are being published digitally; in fact, specific hardware in the form of digital readers is being developed to ease the readers to consume more and more digital media and to enhance their experience when doing so. The digital newspapers and books are not mere replications of their physical versions; they often include animations and videos to better convey the messages for which they were edited. Such enhanced user experience is cross-bounding; users demand such experience even in their own digital media. For example, users want their; web-sites, digital albums, etc. to include such animations and videos. Business owners utilize this technology to generate banners, digital menus, and video clips to attract potential customers. 
         [0005]    However, although producing such digital media is on demand, the production of such media has yet been adopted by the masses. The adoption of such digital media entails a few setbacks. 
         [0006]    First, the processing power which is required to produce such digital media is considerable. The processing of a few frames is usually referred to by the art as “rendering”. The rendering which is required to produce a video or an animation is dependent on the length of the video (the number of frames) and on the resolution of the video (the weight of each frame). Because videos usually include twenty five frames per second and because a standard frame may consist of 640×480 pixels, producing a few seconds of animation may take about an hour of rendering time depending of the processors performing the rendering job. Not to mention, when the media rendered is long (a few hours) and the resolution is high (1024×768 or more) the rendering time may take a few hours even when utilizing state-of the art processors. 
         [0007]    Second, producing animations requires skill. In order to produce animations one needs to use a software tool such as “Adobe After Effects”. The use of such software tools is not trivial to a layman. In addition, these software tools often charge a monthly fee or a licensing fee, making them out of reach for mass adoption. 
         [0008]    In order to overcome the first setback described above, Adobe suggested the notion of utilizing a “Rendering Farm”; 
         [0009]    http://help.adobe.com/en_US/AfterEffects/9.0/WS3878526689cb91655866c1103a 4f2dff7-79a2a.html 
         [0010]    A Rendering Farm uses multiple computers over the network to save rendering time. Some Rendering Farms work on a frame by frame basis. Meaning, a certain computer starts rendering a certain frame, if another computer is being indicated that the frame is already being rendered by the certain computer, and then the other computer simply starts rendering the next frame instead. 
         [0011]    As for the second setback described above, some suggestions have been offered by the art in order to overcome it, here are a few examples: 
         [0012]    US Patent Application US2010223128 to Dukellis, depicts templates that contain visual effects, synchronization information, and possibly director assistance. These templates are utilized by a second set of persons to generate personalized motion photo videos from photographs, video segments, personal narratives or animation. 
         [0013]    World publication WO2008109233 to Estrop, depicts audiovisual works which can be automatically created based upon inferred and implicit metadata including music genre, image captions, song structure, image focal points, as well as user-supplied data such as text tags, emphasis flags, groupings, and preferred video style. 
       SUMMARY OF THE INVENTION 
       [0014]    The present invention discloses a method for parallel processing; the method may comprise the following steps:
       a. Receiving multiple job requests;   b. Segmenting job requests into sub jobs;   c. Processing sub jobs by few processors in parallel;       
 
         [0018]    wherein each sub job may contain a few frames to be processed by the job processors and wherein the outputs of few job processors may be aggregated into a single output. 
         [0019]    The method may further include assigning a priority value to each of the job requests. The priority value may be comprised by taking into consideration the priority of the job request as requested by the client and by the obligations to meet the priority requested by the client. 
         [0020]    The method may further comprise an optimization algorithm; the optimization algorithm may take into consideration; the priority of the job requests, the proximity of the node to the job request, the availability of the job processors, the processing power of each job processor and operate the system in accordance. The optimization algorithm may further take into consideration the estimated rendering required to specific frames in order to segment a job into sub jobs proportionally. The optimization algorithm may also take into consideration cost-effective parameters such as; the cost of the node or a number of nodes on a particular cloud, the urgency of the job request compared to the availability and cost of the nodes, the availability of the licensed plugins for the relevant job request etc. 
         [0021]    The method may include segmenting a job into a number of sub jobs which is larger than the number of the job processors. 
         [0022]    The method may include forming sub jobs which are comprised of frames which are randomly selected from the job request. 
         [0023]    The optimization algorithm may modify the structure of the system to improve performance and to adapt processing resources to clients&#39; demand. 
         [0024]    The structure of the system may include job processors at different geographic locations all over the world. The job processors may be computers of private users or commercial processing clouds which may be utilized for an agreed upon compensation. 
         [0025]    The method may further include encoding the output data by the few processors. 
         [0026]    The method may further comprise a rendezvous server; the structure of the system may be controlled by the rendezvous server manually or automatically by the optimization algorithm. 
         [0027]    The method may further comprise sharing or sending the single output to a destination provided by the client such as a social network. 
         [0028]    The method may further comprise an intuitive user interface; the user interface may be applied via a web-site. 
         [0029]    The present invention discloses a system for parallel processing, the system may comprise:
       a. A server for receiving a job request;   b. An algorithm for segmenting each request to few sub jobs;   c. A few processors for processing few sub jobs in parallel;       
 
         [0033]    wherein each sub job contains a few frames to be processed by the job processors and wherein the outputs of the few job processors are combined into a single output. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0034]    In the drawings: 
           [0035]      FIG. 1  schematically shows a rendering farm scheme as depicted by the prior art. 
           [0036]      FIG. 2  schematically shows a scheme of the main components of a system for parallel processing of multiple frame packs. 
           [0037]      FIG. 3  schematically shows a scheme of the main components of a hierarchical system for parallel processing of multiple frame packs. 
           [0038]      FIG. 4  schematically shows a method for parallel processing of multiple frame packs. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0039]    For a better understanding of the invention and to show how the same may be carried into effect, reference will now be made, purely by way of example, to the accompanying drawings. With specific reference to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of preferred embodiments of the present invention only, and are presented for the purpose of providing what is believed to be the most useful and readily understood description of the principles and conceptual aspects of the invention. In this regard, no attempt is made to show structural details of the invention in more detail than is necessary for a fundamental understanding of the invention. From the description taken together with the drawings it will be apparent to those skilled in the art how the several forms of the invention may be embodied in practice. Moreover, it is to be understood that the phraseology and terminology employed herein is for the purpose of description and should not be regarded as limiting the scope of the invention hereof. 
         [0040]      FIG. 1  schematically shows a rendering farm scheme as depicted by the prior art  100 . A client  101  sends a job to be managed by a server  102 , the job consists of processing six frames  103   a - 103   f.  Three processors  104   a - 104   c  are assigned in parallel to do the job. The first processor  104   a,  starts rendering the first frame  103   a,  the second processor  104   b  accesses the first frame  103   a,  when the second processor  104   b  is being indicated by the server  102  that the first frame  103   a  is already being rendered by the first processor  104   a,  the second processor  104   b  accesses the next frame in line  103   b,  if no other processor had already begun rendering the second frame  103   b  then the second processor  104   b  will begin to do so. The third processor  104   c,  accesses the first frame  103   a,  when indicated that the first frame  103   a  is already being processed, the third processor  104   c  accesses the second frame  103   b,  when indicated that the second frame  103   b  is already being processed, the third processor  104   c  accesses the third frame  103   c  which is free to work on. Whenever a processor  104   a - 104   c  finishes working on a certain frame, it continues to search for the next frame in line which is free to work on mutatis mutandis. 
         [0041]      FIG. 2  schematically shows a scheme of the main components of a system for parallel processing of multiple frame packs  200 . A client  201  sends a job request  202  to the system  200 , the job request  202  includes processing of multiple frames (rendering) in order to produce a video animation; the job request  202  is received by the job dispatcher  203 . The job dispatcher  203  runs an optimization engine  207  to analyze the amount of resources required to perform the job request  202  and to prioritize the job request  202  compared to other pending job requests received by the system  200 . The optimization engines  207  outputs are used to segment the job request  202  to job segments  202 A- 202 C, each job segment  202 A- 202 C includes a pack of frames to be rendered by a corresponding job processor  204 A- 204 C. 
         [0042]    In order to maximize the usage of the job processors, the job dispatcher may segment the job into a number of segments which is larger than the number of the job processors, such that if a certain job processor finishes processing a sub job and becomes available, a pending job segment may be dispatched to be processed by that job processor. The advantage of such a segmentation strategy is that it is simple to execute, it does not require pre-processing to evaluate the processing power required to each job segment and it takes into account the actual performance of the job processors in real-time. The ideal proportion between the number of job segments with respect to a job and to the number of job processors being used may be a function of the efficiency learned from past experience taking into consideration real-time parameters such as the actual delivery of specific product segments by specific job processors. 
         [0043]    The segmentation of the job request  202  may further dependent on few criteria among which are; the number of available job processors taking into consideration the processing power of each job processor. For instance, if a certain job request includes processing six hundred frames, and there are three job processors available having an equal processing power, then the job request will be segmented to three equal sub jobs and each job processor will be assigned a sub job of processing two hundred frames. However, if a certain job processor is faster than the other job processors then the job dispatcher may assign a larger job segment to the faster job processor such that the three job processors will finish their sub jobs at the same time. For example, if one of the job processors has a processing power which is twice as fast as the other two job processors, than the job dispatcher will assign a sub job segment twice as large (processing three hundred frames) to that job processor and each of the other job processors will be assigned a sub job of processing one hundred and fifty frames such that all three job processors will finish their sub jobs approximately at the same time. Because each frame may require a different amount of rendering, additional measures may be taken to achieve proportional segmentation of the sub jobs. For instance, the system may evaluate in advance, the processing power required to each frame or to random frames and segment the job into sub jobs while taking this factor into consideration. Such evaluation may be done while running a preview for example. Alternatively, each sub job may be comprised of random frames selected from the job to reduce probability of undesired processing power deviations between sub jobs. After the job segments have been processed into product segments, the job dispatcher rearranges the processed frames according to their original order to create the final product. Another criteria which is taken into consideration for the job segmentation process is the priority of each job request as further detailed in  FIG. 4 . Such segmentation calculations as detailed herewith can be performed on large scales mutatis mutandis, taking into consideration many job requests to be processed in parallel by many job processors taking into consideration the aforementioned as well as additional criteria. The job segments  202 A- 202 C are performed in parallel by the job processor  204 A- 204 C. The output of each job processor  204 A- 204 C is a corresponding product segment  206 A- 206 C. The job dispatcher  203  aggregates the product segment  206 A- 206 C into the final product  206  which is the complete rendered video animation which is provided to the client  201 . The system may also run a similar process to provide a preview of the requested job mutatis mutandis. 
         [0044]      FIG. 3  schematically shows a scheme of the main components of a hierarchical system for parallel processing of multiple frame packs  300 . A hierarchical system for parallel processing of multiple frame packs  300  is used to provide scalability and flexibility in the amount of parallel processing which can be performed by the system with respect to time. Such flexibility can be used to perform large job requests fast and to perform few job requests for a few clients in parallel. In other words, the system  300  manages and modifies its processing resources based on interchangeable criteria as further described below. 
         [0045]    The system  300  provides services to multiple clients  301 A- 301 E simultaneously. The clients are digital animators, digital graphic designers, digital editors, video artists, layman wishing to create effects for leisure such as photo albums or for commercial use such as websites, restaurants digital menus, banners etc. The client&#39;s  301  may access the service using Personal Computers, Laptops, Tablets, Smartphones, and Smart TVs  301 A- 301 E respectively. 
         [0046]    The services of the system  300  are provided via a web-site which includes an intuitive interface and templates (not shown) by which both professionals and layman can use the services of the system  300 . Using the web-site does not require dedicated installations (plug-ins). 
         [0047]    The job requests sent by the clients  301  are received by the parent job dispatchers  302 . Each parent job dispatcher  302 A and  302 B, dispatches the job requests to its corresponding sub job dispatcher  303 A and  303 B respectively. The sub job dispatchers  303 A and  303 B segment the job requests into sub jobs to be performed by the parent job processors  304 . The parent job processors  304 A and  304 B segment the sub jobs again to tasks to be performed by the sub job processors  305 . Each sub job processor  305 A and  305 B having performed its tasks, sends its outputs to the corresponding parent job processor which assigned it the task ( 304 A and  304 B respectively). The parent job processors  304  aggregates the tasks outputs into product segments and send the product segments to the corresponding sub job dispatcher  303 A and  303 B respectively, the sub job dispatchers  303  aggregates the product segments into the final products and send the final products to their corresponding parent job dispatchers  302 A and  302 B from which the final product is being sent to the clients  301 . The final product is a file which can be downloaded or shared by the clients  301 . 
         [0048]    A rendezvous server  306  is used to add and remove components to the system  300 . For instance, the rendezvous server  306  is used to add sub job processors  305  when additional processing power is required. The structure of the system  300  can be modified manually by an operator via the rendezvous server  306 . Alternatively, the structure of the system  300  can be modified automatically according to predefined criteria. For example, when the processing power required exceeds a certain criteria, the rendezvous server  306  can automatically add sub job processors to the system  300 , until the processing load is decreased to a desired level. An optimization algorithm  307  calculates the processing power required taking into consideration time constraints. For example, if a certain customer demands a job request to be performed immediately, and the system currently lacks a certain resource to enable such instant performance, then the optimization algorithm  307  may add that missing resource to the system automatically via the rendezvous server  306 . When the job is finished, the resource may be removed from the system until further use is required. In other words, the system includes a flexible structure which can be modified in real-time taking into consideration the overall work load and the priority given to each job. This flexibility is also used for redundancy purposes. For example, is a certain sub job processor malfunctions or if the communication with it is down, the system simply adds another functional sub job processor in lieu of the malfunctioning job processor. The sub job processors  305  may be computers all over the world. Meaning, the system  300  may utilize its own integral sub job processors  305 , in addition, the system may utilize other sub job processors according to permissions or to leasing agreements with the owners of the sub job processors. For example, a private person may permit the system  300  to utilize his Personal Computer as a sub job processor during certain hours in exchange for agreed upon compensation. The compensation can be based on a monthly fee or on the actual use of computation power per month etc. According to such permissions, the system  300  can therefore be adapted, to execute large amounts of job requests simultaneously by utilizing a large number of job processors at its disposal. The job processors may be geographically located all over the world. 
         [0049]      FIG. 4  schematically shows a method for parallel processing of multiple frame packs  400 . Step  401  is receiving multiple jobs to be performed by the system. Step  402  is diagnosing the resources required to perform each job, including checking the number of frames to be processed and the resolution of each frame. Each job is assigned a priority value  403 , the priority value differentiates the urgency between pending jobs. The priority value is determined by the clients request for the job, for instance; immediate, within the next hour, within the next three hours etc. In addition, the obligation of the system to meet the clients request is determined by the client&#39;s agreement with the company providing the services. For example, the client may pay a fee which credits the client with a certain amount of real-time processing or a smaller fee which credits the client with up to an hour of a certain amount of processing, alternatively, the client may use the services free of charge subject to the availability of the system to run the clients job request without compromising the services to other clients at a given time. The system receives the availability status from multiple job processors  404 , each job processor sends its availability status, and if the job processor is unavailable (due to its occupation by another job) then the job processor sends its prediction as to when it will be available (when the current job is expected to be finished). An optimization algorithm  405  lists the pending jobs according to their priority and calculates the cost-effectiveness of each job request for example, the optimization algorithm may calculated the amount paid by the client for the execution of the job request compared to the cost of the job request which may be comprised by rendering job processors, paying for plug-ins etc. The job dispatcher  406  segments the job into multiple sub jobs, each sub job is dispatched  407  to a job processor, and each sub job includes a few frames to be processed (rendered) by a corresponding job processor  408 . The job processors render the frame packs assigned to them and encode the data, the encoded data from each job processor (the “segmented product”) is sent to the job dispatcher  410 , the job dispatcher aggregates segmented products into final product  411  and sends the final product to the client. The final product can be sent as a link or as a file, the final product can also be sent directly to Facebook, YouTube or any other desired location according to the users&#39; preferences  412 . 
         [0050]    Although the invention has been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, it is intended to embrace all such alternatives, modifications and variations that fall within the spirit and broad scope of the appended claims. All publications, patents and patent applications mentioned in this specification are herein incorporated in their entirety by reference into the specification, to the same extent as if each individual publication, patent or patent application was specifically and individually indicated to be incorporated herein by reference. In addition, citation or identification of any reference in this application shall not be construed as an admission that such reference is available as prior art to the present invention.