# Load Balancing Strategies for Slice-Based Parallel Versions of JEM Video Encoder
## 3 Parallel Approaches
### Asynchronous Algorithm: JEM-SP-ASync
Note that as the number of frames to be encoded increases, the automatic load balancing method of Algorithm 2 is expected to improve, since it is statistically more likely that the computational cost per thread will be balanced. The values of the quantization parameter (QP) used were 37, 32, 27 and 22. Before addressing the efficiency of the parallel algorithms described in Section 3, we analyze the theoretical load balance index, which will depend on both the resolution of the video sequence and the number of slices (i.e., the number of threads). In all of the experiments, the CTU size was set to 128, based on common testing conditions [24]. Table 4 shows the dimensions of the different video resolutions tested, in numbers of CTUs of \(128\times 128\) pixels. As mentioned above, there may be incomplete CTUs at the right-hand and bottom edges of the video sequence. This occurs when the number of horizontal/vertical CTUs is not an integer, as shown in Table 4. This is the primary source of potential load imbalance, even if the computational costs associated with different CTUs are similar. Table 5 shows the theoretical size of the slices, in number of CTUs, required to obtain a balanced load. As previously explained for Algorithm 1, when the number of CTUs per dimension is not an integer, the size is rounded up to the next integer value; otherwise, the number of slices would not match the number of threads. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Resolution** & \multicolumn{2}{c}{**Horizontal CTUs**} & \multicolumn{2}{c}{**Vertical CTUs**} & \multicolumn{2}{c}{**Number of CTUs**} \\ \hline
1920 \(\times\) 1080 & 15 & 15 & 8.4 & 9 & 135 \\
1280 \(\times\) 720 & 10 & 10 & 5.6 & 6 & 60 \\
832 \(\times\) 480 & 6.5 & 7 & 3.8 & 4 & 28 \\
416 \(\times\) 240 & 3.25 & 4 & 1.9 & 2 & 8 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Number of 128 \(\times\)128 CTUs for each video sequence resolution. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Video Seq.** & **Acronym** & **Resolution** & **Rate (Hz)** & **N. Frames** & **Time (s)** \\ \hline Park Scene & PARK & 1920 \(\times\) 1080 & 24 & 120 & 5 \\ Four People & FOUR & 1280 \(\times\) 720 & 60 & 120 & 2 \\ Party Scene & PART & 832 \(\times\) 480 & 50 & 120 & 2.4 \\ BQ Square & BQSQ & 416 \(\times\) 240 & 60 & 120 & 2 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Video sequences. Table 6 shows the size differences, in numbers of CTUs, between the last slice and the other slices in the same frame. As can be seen, when 12 slices are used in the HD video sequence, the difference reaches nine CTUs. This is the second source of potential load imbalance, and as in the previous case, this holds even if the computational costs associated with different CTUs are similar. In addition, the use of a given number of threads is not recommended in certain cases. For example, when 11 threads are used in the \(1280\times 720\) video sequence (60 CTUs in Table 6), all slices have six CTUs while the last has none, meaning that it will remain idle throughout the encoding process. The third and final source of potential load imbalance depends on the encoding complexity of JEM, which does not depend on the number of CTUs but on the intrinsic characteristics of the intra-prediction, which may be affected by the CTU contents. As explained in Section 2, this load imbalance cannot be predicted, as it depends on the intrinsic characteristics of the video content to be encoded, which modifies the amount of processing required to encode each CTU. To show that domain decomposition using slices does not ensure that the load is balanced, we experimentally obtained the computational cost of each slice for the sequences listed in Table 3. Tables 7-10, show the experimental percentages of the computational cost assigned to each slice for the Park Scene, Four People, Party Scene and BQ Square video sequences, respectively.