# Load Balancing Strategies for Slice-Based Parallel Versions of JEM Video Encoder
## 3 Parallel Approaches
### Asynchronous Algorithm: JEM-SP-ASync
\begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline
**Slice Size** & **QP** & **(0-4)** & **(4-8)** & & & & & & \\ \hline \multirow{4}{*}{4} & 22 & 56\% & 44\% & & & & & & \\  & 27 & 57\% & 43\% & & & & & & \\  & 32 & 58\% & 42\% & & & & & & \\  & 37 & 61\% & 39\% & & & & & & \\  & & (0-3) & (3-6) & (6-8) & & & & & \\  & 22 & 51\% & 31\% & 18\% & & & & & \\  & 32 & 53\% & 29\% & 18\% & & & & & \\  & 37 & 56\% & 27\% & 17\% & & & & & \\  & & (0-2) & (2-4) & (4-6) & (6-8) & & & & & \\  & 22 & 35\% & 21\% & 26\% & 18\% & & & & \\  & 27 & 36\% & 20\% & 25\% & 18\% & & & & \\  & 32 & 38\% & 20\% & 24\% & 18\% & & & & \\  & 37 & 40\% & 21\% & 22\% & 17\% & & & & \\  & & (0-1) & (1-2) & (2-3) & (3-4) & (4-5) & (5-6) & (6-7) & (7-8) \\  & & 22 & 18\% & 18\% & 16\% & 5\% & 13\% & 13\% & 14\% & 4\% \\
1 & 27 & 20\% & 17\% & 15\% & 5\% & 13\% & 12\% & 14\% & 4\% \\  & 32 & 22\% & 17\% & 15\% & 5\% & 12\% & 12\% & 14\% & 4\% \\  & 37 & 22\% & 17\% & 16\% & 5\% & 11\% & 11\% & 13\% & 4\% \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Computational cost per slice for BQ Square video sequence. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Slice** & **QP** & **(0-4)** & **(4-8)** & & & & \\ \hline \multirow{4}{*}{4} & 22 & 56\% & 44\% & & & & \\  & 27 & 57\% & 43\% & & & & \\  & 32 & 58\% & 42\% & & & & \\  & 37 & 61\% & 39\% & & & & \\  & & (0-3) & (3-6) & (6-8) & & & & \\  & 22 & 51\% & 31\% & 18\% & & & & \\
3 & 27 & 51\% & 31\% & 18\% & & & & \\  & 32 & 53\% & 29\% & 18\% & & & & \\  & 37 & 56\% & 27\% & 17\% & & & & \\  & & (0-2) & (2-4) & (4-6) & (6-8) & & & \\  & & 22 & 35\% & 21\% & 26\% & 18\% & & & \\
2 & 27 & 36\% & 20\% & 25\% & 18\% & & & \\  & 32 & 38\% & 20\% & 24\% & 18\% & & & \\  & & 37 & 40\% & 21\% & 22\% & 17\% & & & \\  & & (0-1) & (1-2) & (2-3) & (3-4) & (4-5) & (5-6) & (6-7) & (7-8) \\  & & 22 & 18\% & 18\% & 16\% & 5\% & 13\% & 13\% & 14\% & 4\% \\
1 & 27 & 20\% & 17\% & 15\% & 5\% & 13\% & 12\% & 14\% & 4\% \\  & 32 & 22\% & 17\% & 15\% & 5\% & 12\% & 12\% & 14\% & 4\% \\  & & 37 & 22\% & 17\% & 16\% & 5\% & 11\% & 11\% & 13\% & 4\% \\ \hline \hline \end{tabular}
\end{table} 
Table 11: Sequential computational times. The JEM-SP-Sync algorithm, which includes synchronization points, generally obtains good parallel efficiency when few threads are used (set by NoT value), but does not have good scalability, meaning that its efficiency degrades as the number of threads increases. The high computational cost of the JEM video encoder means that if the load is not perfectly balanced, the parallel performance is strongly affected. In this case, and as mentioned above, the load imbalance may be caused by differences in slice sizes, by some slices having incomplete CTUs, or by the difference in the intrinsic complexity of the CTUs in the coding process in JEM. As shown in Tables 7-10, the computational cost is not balanced despite the quasi-balanced domain decomposition according to the volume of data assigned to each processor. The load imbalance is due to the nature of the data, i.e., the content of each CTU. Since the JEM-SP-Sync algorithm is synchronous, when a thread has completed the processing of the assigned CTUs of one frame, it must wait in an idle state until the rest of threads also complete the assigned CTUs, which in turn decreases parallel efficiency, as shown in Table 12.