# Frame-Based and Subpicture-Based Parallelization Approaches of the HEVC Video Encoder
## 3 Frame-Based Parallel Algorithms  
Now, we will depict the parallel algorithm for the HEVC encoder at frame level, named DMG-AI, which has been specifically designed for the AI coding mode (Figure 8). A full description of the algorithm can be found in [13]. In the current paper, the DMG-AI algorithm is tested on an  
Figure 6: Searching area to perform the CTU prediction depending of the position of the borders in a Full HD frame. (**a**) 8 slices; (**b**) 1 \(\times\) 8 tiles; (**c**) 8 \(\times\) 1 tiles. Figure 7: Marked CTUs with the coding affected, in column and row tile layouts for the partitioning of a Full HD frame into 8 tiles. (**a**) 1 \(\times\) 8; (**b**) 8 \(\times\) 1.  
heterogeneous memory framework, managed by the Message Passing Interface (MPI) [17], consisting on \(N\) computing nodes (distributed memory architecture). Each node has a shared memory architecture. At each one of the \(N\) available nodes, \(R\) MPI processes are executed (or mapped) in such a way that every MPI process (\(P_{i,j}(i=1\ldots N,j=1\ldots R)\)) of the \(NxR\) available processes, encodes one different frame. Firstly, each coding process (\(P_{i,j}\)) sends an MPI message to the coordinator process (\(P_{coord}\)) requesting a frame to encode. Note that, in the AI encoding mode, all frames are encoded as I frames, i.e., without using previously encoded frames, making use only of the spatial redundancy. The coordinator process is responsible for the assignation of the video data to be encoded to the rest of processes, and for the collection of both statistical and encoded data in order to compose the final bitstream. The coordinator process performs the distribution of the workload by sending one different frame to each coding process. When the coding process \(P_{i,j}\) finishes the encoding of its first received frame (\(F_{i,j,0}\)), it sends the resulting bitstream to the coordinator process, which assigns a new frame (\(F_{i,j,1}\)) to the coding process. This procedure is repeated until all frames of the video sequence have been encoded. In this algorithm, when a coding process becomes idle, it is immediately assigned a new frame to encode, so there is no need to wait until the rest of the processes have finished their own work. This fact provides a good workload balance, and, as a consequence, excellent speed-up values are obtained. This frame-based algorithm is completely asynchronous, so the order in which each encoded frame is sent to the coordinator process is not necessarily the frame rendering order, and the coordinator process therefore must keep track of the encoded data to form the encoded bitstream in the suitable rendering order. The coordinator process is mapped onto a processor that also runs one coding process, because the computational load of the coordinator process is negligible. We want to remark that the DMG-AI algorithm generates a bitstream that is exactly the same as the one produced by the sequential algorithm; therefore, there is no R/D degradation. Figure 8: DMG-AI parallel algorithm. The previously described DMG-AI algorithm presents the following drawbacks: (a) a queuing system to manage the distributed resources must be installed in order to correctly map the MPI processes, (b) the number of MPI messages increases as the number of MPI processes does and, depending on the video frame resolution, the messages are often quite small, and (c) the distribution of processes between the computing nodes (i.e., the number of MPI processes per node) is performed before the beginning of the execution time through the queuing system, which in our case is the Sun Grid Engine. As previously stated, the DMG-AI algorithm includes an automatic workload balance system, but the algorithm itself is not able to change the process distribution pattern during execution time. In order to avoid the aforementioned drawbacks, we propose the new hybrid MPI/OpenMP algorithm named DSM-AI, which does not need a specific queuing system and which outperforms the pure MPI proposal (DMG-AI).