# 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} \hline \hline  & & \multicolumn{5}{c}{**Parallel Efficiency**} \\ \hline Video & & QP & QP & QP & QP \\ sequence & NoT & 22 & 27 & 32 & 37 \\ \hline \multirow{4}{*}{BQSQ} & 2 & 85.0\% & 85.2\% & 82.6\% & 79.1\% \\  & 3 & 61.5\% & 61.3\% & 59.4\% & 57.2\% \\  & 4 & 67.6\% & 65.2\% & 62.5\% & 60.3\% \\  & 8 & 61.7\% & 56.7\% & 52.2\% & 51.1\% \\ \hline \multirow{4}{*}{PART} & 2 & 94.1\% & 96.1\% & 96.9\% & 94.1\% \\  & 3 & 77.3\% & 76.3\% & 76.0\% & 75.5\% \\  & 4 & 86.1\% & 83.1\% & 82.4\% & 78.9\% \\  & 5 & 79.6\% & 78.7\% & 75.6\% & 74.2\% \\  & 6 & 73.1\% & 69.0\% & 66.0\% & 64.6\% \\  & 7 & 74.2\% & 70.9\% & 67.8\% & 64.7\% \\  & 8 & 65.4\% & 61.8\% & 59.2\% & 56.8\% \\  & 10 & 72.5\% & 70.4\% & 68.4\% & 67.1\% \\ \hline \multirow{4}{*}{FOUR} & 2 & 88.4\% & 88.1\% & 86.3\% & 85.3\% \\  & 3 & 62.2\% & 60.1\% & 57.9\% & 60.1\% \\  & 4 & 74.5\% & 70.9\% & 70.7\% & 71.5\% \\  & 5 & 65.0\% & 62.9\% & 63.8\% & 65.3\% \\  & 6 & 59.6\% & 56.1\% & 55.1\% & 55.5\% \\  & 7 & 61.0\% & 57.8\% & 57.8\% & 58.3\% \\  & 8 & 55.5\% & 50.2\% & 50.1\% & 51.2\% \\  & 9 & 59.6\% & 56.8\% & 57.0\% & 57.8\% \\  & 10 & 59.5\% & 54.5\% & 54.7\% & 56.3\% \\  & 11 & 53.8\% & 50.1\% & 49.9\% & 50.8\% \\  & 12 & 55.7\% & 51.7\% & 49.5\% & 49.3\% \\ \hline \hline \end{tabular}
\end{table} 
Table 12: Parallel efficiency for Algorithm JEM-SP-Sync. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & \multicolumn{5}{c}{**Computational Time (s.)**} \\ \hline Video & & QP & QP & QP \\ sequence & NoT & 22 & 27 & 32 & 37 \\ \hline \multirow{5}{*}{BQSQ} & 2 & 5882 & 4751 & 3857 & 3215 \\  & 3 & 5415 & 4402 & 3577 & 2964 \\  & 4 & 3694 & 3694 & 3694 & 3694 \\  & 8 & 2026 & 2026 & 2026 & 2026 \\ \hline \multirow{5}{*}{PART} & 2 & 23,305 & 19,153 & 15,346 & 11,753 \\  & 3 & 18,911 & 16,069 & 13,053 & 9763 \\  & 4 & 12,733 & 11,070 & 9030 & 7007 \\  & 5 & 11,012 & 9347 & 7867 & 5964 \\  & 6 & 9991 & 8887 & 7518 & 5703 \\  & 7 & 8445 & 7412 & 6266 & 4882 \\  & 8 & 8384 & 7444 & 6287 & 4864 \\  & 10 & 6051 & 5224 & 4349 & 3295 \\ \hline \multirow{5}{*}{FOUR} & 2 & 26,479 & 19,172 & 14,441 & 10,709 \\  & 3 & 25,103 & 18,716 & 14,362 & 10,141 \\  & 4 & 15,705 & 11,898 & 8809 & 6385 \\  & 5 & 14,407 & 10,732 & 7818 & 5595 \\  & 6 & 13,085 & 10,034 & 7547 & 5484 \\  & 7 & 10,960 & 8348 & 6158 & 4476 \\  & 8 & 10,545 & 8410 & 6218 & 4464 \\  & 9 & 8727 & 6606 & 4860 & 3512 \\  & 10 & 7861 & 6200 & 4558 & 3244 \\  & 11 & 7909 & 6128 & 4546 & 3269 \\  & 12 & 7007 & 5440 & 4194 & 3089 \\ \hline \multirow{5}{*}{PARK} & 2 & 95,117 & 66,946 & 45,846 & 29,237 \\  & 3 & 66,202 & 46,565 & 31,348 & 20,128 \\  & 4 & 49,218 & 35,234 & 25,017 & 16,821 \\  & 5 & 38,857 & 28,583 & 20,025 & 13,708 \\  & 6 & 35,411 & 25,915 & 17,845 & 11,654 \\  & 7 & 29,830 & 21,576 & 15,453 & 10,048 \\  & 8 & 25,811 & 19,243 & 13,695 & 9396 \\  & 9 & 22,458 & 16,426 & 11,831 & 7804 \\  & 10 & 21,319 & 15,965 & 11,511 & 7916 \\  & 11 & 20,207 & 14,978 & 10,567 & 7110 \\  & 12 & 18,894 & 14,159 & 10,507 & 7188 \\ \hline \hline \end{tabular}
\end{table} 
Table 13: Computational times (s.) for Algorithm JEM-SP-Sync. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & \multicolumn{5}{c}{**Parallel Efficiency**} \\ \hline  & 2 & 91.7\% & 92.9\% & 92.1\% & 93.9\% \\  & 3 & 87.9\% & 89.0\% & 89.8\% & 91.0\% \\  & 4 & 88.6\% & 88.3\% & 84.3\% & 81.6\% \\  & 5 & 89.8\% & 87.0\% & 84.3\% & 80.1\% \\  & 6 & 82.1\% & 80.0\% & 78.8\% & 78.6\% \\   PARK & 7 & 83.6\% & 82.4\% & 78.0\% & 78.1\% \\  & 8 & 84.5\% & 80.8\% & 77.0\% & 73.1\% \\  & 9 & 86.3\% & 84.1\% & 79.3\% & 78.2\% \\  & 10 & 81.9\% & 77.9\% & 73.3\% & 69.4\% \\  & 11 & 78.5\% & 75.5\% & 72.6\% & 70.2 The second algorithm, JEM-SP-ASync, was developed to avoid the use of synchronization processes, and can improve the parallel efficiency if load balancing is achieved. The process implemented in this algorithm to balance the load assigns a different slice to each thread depending on the frame to be encoded, thus providing automatic load balancing.