# Load Balancing Strategies for Slice-Based Parallel Versions of JEM Video Encoder
## 3 Parallel Approaches
### Synchronous Algorithm: JEM-SP-Sync  
Algorithm 1 shows the parallel algorithm, called JEM-SP-Sync, which includes synchronization processes. In Algorithm 1, the size of the slice is first computed in numbers of CTUs. To do this, we initially compute the number of horizontal (\(FrWidth\)) and vertical (\(FrHeight\)) CTUs, and the total number of CTUs (\(NoCTUs\)) available in a frame, which will depend on the video resolution. It is worth noting that both the right-hand and bottom CTUs in the frame may be incomplete (see lines 4 and 8). Furthermore, since the slices may not have the same number of CTUs, the algorithm sets the size of the last slice as equal to or smaller than the size of the rest of the slices in order to achieve a better load balance (lines 13-18).  
Before starting the encoding process of the whole video sequence, each thread computes the CTUs of the slice assigned to that thread, which always remains the same throughout the encoding process (lines 20-26). The encoding process starts by reading the frame to be encoded and storing it in memory. This initial process is performed by a single thread, and a synchronization point is therefore needed to ensure that the process waits until the frame is available (line 30). In a similar way, the reconstructed frame is also stored in the shared memory. This task is carried out by each individual thread after encoding the assigned slice, meaning that another synchronization point is required before applying the \"loop filter\" process (line 32). The encoded video data stream (i.e., the bit stream) is organized into network abstraction layer units (NALUs), where each NALU is a packet containing an integer number of bytes. To finish the encoding process, the NALUs corresponding to each slice must be written in the correct order to form the final bit stream (line 35). It is worth mentioning that the slice-based parallel strategy for HEVC proposed in [20] obtained good speed-ups when all slices had the same number of CTUs, or differed by a maximum of a single CTU. However, this behavior changes greatly when the JEM encoder is used. As explained in Section 2, changes to the coding procedure introduced in the JEM with respect to HEVC result in significant differences in computational cost when encoding different CTUs. Note that this load imbalance is mainly due to the intrinsic characteristics of the video content.  
Figure 7: Division of a full-HD frame (1920 \(\times\) 1080 pixels) into 10 slices of 51 CTUs each.  
```
1:Set \(NoT\) to the number of threads (equal to the number of slices)
2:procedureCompute the number of CTUs per frame
3:\(NoLzCTUs=FWith/CTUsSize\)
4:if\(FrWeight@TCUISizel=0\)then
5:\(NoLzCTUs++\)
6:endif
7:\(NoVCTUs=FrHeight/CTUsSize\)
8:if\(FrHeight@TCUISizel=0\)then
9:\(NoVCTUs++\)
10:endif
11:\(NoCTUs=NoLzCTUs*NoVCTUs\)
12:endprocedure
13:procedureCompute the number of CTUs per slice
14:\(NoCTUsSlice=NoCTUs/NoTthreads\)
15:if\(NoCTUsPosNoThreads=0\)then
16:\(NoCTUsSlice++\)
17:endif
18:endprocedure
19:In PARALLEL (NoT:
20:procedureassign the dimms of the slice(\(Tid\))
21:\(intCTU_{Tid}=Tid*NoCTUsSlice\)
22:\(endCTU_{Tid}=intCU_{Tid}+NoCTUsSlice\)
23:if\(Tid==(NoT-1)\)then
24:\(endCTU_{Tid}=NoCTUs-1\)
25:endif
26:endprocedure
27:for\(i=1\) to \(NumFramesInSequence\)do
28:Single thread:
29: Read frame \(i\) it in global memory.
30: Synchronization point #1
31: Encode Slice (\(intCTU_{Tid}\) to \(endCTU_{Tid}\))
32: Synchronization point #2
33: Apply the loop filter process to whole frame
34: Generate NALUs
35:Ordered:
36: Write NALUs to bitstream.
37:endfor
```  
**Algorithm 1** JEM-SP-Sync: Slice-based parallel algorithm with synchronization processes.  
Figure 8 shows graphically the structure of the synchronous parallel algorithm JEM-SP-Sync. As explained in Algorithm 1, each thread (T\({}_{X}\)) always processes the same slice (S\({}_{X}\)) in all frames. Before starting the processing of a new frame, the threads must synchronize (Sync) to compose the bitstream of the last frame (line 35 of Algorithm 1).