I have implemented group of pictures parallelism for hevc encoding on distributed platform. In this we have to send different video chunks to different machines, these machines encode data in parallel and send data to master node. Here linear improvement in encoding is seen as number of nodes are increased. But now I want to further optimize this algorithm to get better results. Chunks I send to different machines might take different amount of time for encoding depending on content in that video chunk. So which algorithms in distributed parallel processing can be used here to optimize this process? To implement his system I am using OpenMPI framework.


You have a static number of tasks to be executed, and each task is independent (i.e., no communication among tasks is required). However, the chunks assigned to different machines might take a different amount of time for encoding.

In this situation, the simplest and probably the best possible approach, consists in cyclically mapping tasks to processors, in order to balance the computational load. This is a form of probabilistic mapping (see sub-section on Probabilistic Methods and Cyclic Mappings, just before Section 2.5.2 on the linked web page). As an example, if you have $p$ processors and $n$ tasks (with $n > p$), you can simply assign task $i$ to processor $i \mod p$.

  • $\begingroup$ but for content dependent data(like in case of video encoding, encoding time will depend on video content present in video chunk sent to the node), can we apply some feedback kind of algorithm for load balancing of data across nodes (instead of simple round robin algorithm and sending fixed size of data)? where can I read more about such optimization algorithms? $\endgroup$ – rishi007bansod Feb 3 '16 at 12:54
  • $\begingroup$ Unless you know in advance how much time each chunk requires for encoding, there is nothing that will beat a probabilistic mapping. If your scenario is slightly different, and you have instead a dynamic number of tasks to be handled, always with no intertask communications, then you should use a task-scheduling algorithm. As an example, in this case you can use any variation (there are many possible) of a manager/worker algorithm (also known as master/slave). $\endgroup$ – Massimo Cafaro Feb 3 '16 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.