# Frame-Based and Subpicture-Based Parallelization Approaches of the HEVC Video Encoder
## 2 Subpicture-Based Parallel Algorithms  
In this section, two parallel algorithms based on both tile and slice partitioning are analyzed. Slices are fragments of a frame formed by correlative (in raster scan order) Coding Tree Units (CTUs) (see Figure 1). In the developed slice-based algorithm, we divide a frame into as many slices as the number of available parallel processes. All the slices of a frame have the same number of CTUs, except for the last one, whose size corresponds to the number of CTUs remaining in the frame. The process used to calculate the size of each slice is shown in Algorithm 1. This algorithm provides load balances above 99% in most of the performed experiments. If the height (or width) of the frame (in pixels) is not a multiple of the CTU size, there will be some incomplete CTUs (see lines number 3 and 4 in Algorithm 1). Besides, the size of the last slice of a frame will always be equal or less than the size of the rest of slices (see line 7). ```
1:Obtain the number of processes: \(p\)
2:Obtain the width (or height) of a CTU: \(s\)
3:Frame width (number of CTUs): \(fw=ceil(width/s)\)
4:Frame height (number of CTUs): \(fh=ceil(height/s)\)
5:Total number of CTUs per frame: \(t=fw*fh\)
6:Regular slice size: \(ns=ceil(t/p)\)
7:Last slice size: \(t-(ns*(p-1))\)
```  
**Algorithm 1** Computation of the size of the slicesFigure 2 shows the assignment of the slices to the encoding processes performed in our parallel slice-based algorithm. Each parallel process (\(P_{i}\)) encodes one slice (\(S_{i}\)) of the current frame (\(F_{k}\)). This coding procedure is a synchronous process in which a synchronization point is located after the slice encoding procedure. As depicted in Algorithm 1, the size of the last slice is often smaller than the size of the rest of slices, and this fact decreases, theoretically, the maximum achievable efficiency. In the worst cases in our experiments, the theoretical efficiency reaches 94.5% (a drop off of 5.5%) for a video resolution of \(832\times 480\), 98.9% for a video resolution of \(1280\times 720\), 99.4% for a video resolution of \(1920\times 1080\), and 99.2% for a video resolution of \(2560\times 1600\). In Figure 1, we show the slice partitioning of a Full HD frame (\(1920\times 1080\) pixels), divided into 8 slices. Considering a CTU size of 64 \(\times\) 64 pixels, the frame height is 17 CTUs, the frame width is 30 CTUs, and the total number of CTUs per frame is 510. Following Algorithm 1, the size of each slice is equal to 64 CTUs, except for the last one, which has a size of 62 CTUs, which entails a theoretical load balance of 99.6%. The other subpicture-based parallel algorithm presented in this work is based on tiles. Tiles are rectangular divisions of a video frame which can be independently encoded and decoded. This is a new feature included in the HEVC standard, which was not present in previous standards. In our tile-based parallel algorithm, depicted in Figure 3, a set of encoding processes (\(P_{i}\)) encode a single  
Figure 1: Layout of a Full HD frame with 8 slices (7 slices of 64 CTUs and 1 slice of 62 CTUs). Figure 2: Slice-based parallel algorithm. frame in parallel. Each frame (\(F_{k}\)) is split in as many tiles (\(T_{i}\)) as the number of processes to use, in such a way that each node processes one tile. When every process has finished the encoding of its assigned tile, synchronization is carried out in order to properly write the encoded bitstream and thus proceed with the next frame. In all the performed experiments, each CTU covers an area of \(64\times 64\) pixels and each tile consists of an integer number of CTUs. For a specific frame resolution, we can obtain multiple and heterogeneous tile partition layouts. For example, the partition of a frame into 8 tiles can be done by dividing the frame into 1 column by 8 rows of CTUs (\(1\times 8\)), 8 columns by 1 row (\(8\times 1\)), 2 columns by 4 rows (\(2\times 4\)), and 4 columns by 2 rows (\(4\times 2\)).