# Load Balancing Strategies for Slice-Based Parallel Versions of JEM Video Encoder
## 3 Parallel Approaches
### Asynchronous Algorithm: JEM-SP-ASync  
To solve the load imbalance drawback, we designed a parallel algorithm called JEM-SP-ASync, as shown in Algorithm 2, which does not use any type of synchronization during the overall encoding process. The calculation of both the number of CTUs per frame and the number of CTUs per slice (line 3) is identical to that in Algorithm 1 (lines 2-18). Before starting the parallel region, the dimensions of all slices are calculated (lines 3-10) and stored in memory, which will be configured as shared memory (the iniCTUs and endCTUs arrays) since these values will be used by all threads. At the beginning of the parallel region, the first slice to be encoded by every thread is set (line 12) based on the thread identifier (\(Tid\)). However, the mapping of slices to threads will change for every new frame, following a round-robin-like scheduling (lines 24-27). For this reason, each thread must update the CTUs to be encoded when starting the encoding of a new frame (lines 15 and 16). Since there are no synchronization points, the encoded NALUs must be stored in shared memory. When the encoding process for the slice is complete, each thread checks whether there is a frame for which all of the slices are encoded; if so, this thread stores the complete encoded frame in the bit stream. This procedure should be performed within a parallel critical region (lines 20-23). The proposed mapping of slices to threads included in Algorithm 2 provides an automatic load balancing mechanism without the need for synchronization points or a coordinating process. By alternating the coding slice for each thread from one frame to another, the computational cost per thread tends to balance, with a greater probability as the number of frames to be encoded increases. In the asynchronous algorithm, shown in Figure 9, there are no synchronization points; to compose the bit stream, each thread after processing a slice checks if all the slices of the frame following the last fully encoded one are already encoded, and in that case the thread will compose that frame and remove the stored data. This process (line 17 in Algorithm 2) does not involve any synchronization point. Furthermore, each thread (T\({}_{\text{x}}\)) processes a different slice (S\({}_{\text{x}}\)) in each frame. Figure 8: JEM-SP-Sync: Graphical scheme of the slice-based synchronous parallel algorithm. ```
1:Set \(NoT\) to the number of threads (equal to the number of slices)
2:\(NoCTUs\) and \(NoCTUsSlice\) computed as in Algorithm JEM-SP-Sync
3:procedureComputeDimensions of all slices
4:for\(i=0\) to \((NoT-2)\)do
5:\(initCTUs[i]=i*NoCTUsSlice\)
6:\(endCTUs[i]=(i+1)*NoCTUsSlice-1\)
7:endfor
8:\(initCTUs[NoT-1]=(NoT-1)*NoCTUsSlice\)
9:\(endCTUs[NoT-1]=NoCTUs-1\)
10:endprocedure
11:INPARALLEL (NoT):
12:\(i\)_slice \(\equiv\)Tid_
13:for\(i=1\) to \(NumFramesInSequence\)do
14: Read slice \(i\)_slice \(\equiv\)_t_slice \(\equiv\)_t_slice \(\equiv\)_t_slice



## 4 Experimental Results

The reference software used in our experiments was JEM-7.0 rc1 [21], and the parallel algorithms were developed and tested using the GCC v.4.8.5 compiler [22] and OpenMP [23]. The shared memory platform used consisted of two Intel XEON X5660 hexacores, with up to 2.8 GHz and 12 MB cache per processor, and 48 GB of RAM. The operating system used as CentOS Linux 5.6 for x86/64-bit systems. The proposed algorithms were tested for the video sequences listed in Table 3, each of which had a different resolution and a different frame rate. In all of the experiments, we used the same number of frames to be encoded (120) for all video sequences. Hence, the number of seconds to be encoded varied depending on the frame rate of the video sequence tested. We used a small number of frames for encoding in order to evaluate the load balancing capability of the JEM-SP-ASync algorithm (Algorithm 2).