WIXLIB

Ahn et al. EURASIP Journal on Image and Video Processing 2014, 4/1/16in computational complexity. For HEVC inter prediction coding, a large number of coding modes for varioussize blocks are evaluated and coded by computing ratedistortion costs. In addition, the hierarchical block partition is traversed in a recursive fashion in HM.Table 2 shows percentages of the cycles for intra prediction, inter prediction, and skip modes, depending onthe CU sizes. Regardless of the CU sizes, the percentageof inter prediction coding is about 73.7% to 83.4%. Forthe CU of 8 8, the cycle percentage of the intra prediction coding is approximately 2 to 3 times higher than theothers, because 4 4 and 8 8 intra prediction modes aretested for RDO.Table 3 shows the percentiles of the numbers of cyclesfor the top four functions. The interpolation filter, sum ofabsolute differences (SAD), sum of absolute transformeddifferences (SATD), and discrete cosine transform (DCT)/inverse DCT (IDCT) take approximately 67% to 71% inthe total cycles. The interpolation filter is the most complex function of HEVC encoders and is used for motionestimation and motion compensation. SAD and SATD arecost functions to calculate distortions between originaland prediction blocks. In particular, SAD and SATD arethe metrics for motion estimation of integer-pels andfractional-pels, respectively. In addition, SATD is also usedfor intra prediction. DCT/IDCT is applied to the residualsignal from intra or inter prediction for data compactionin the DCT domain. We can say that optimization of thefour functions is inevitable in order to accelerate HEVCencoder.3 Data-level parallelization of video encodersData-level and function-level parallelization approachesare widely used for high-speed video codecs. In particular,function-level parallel processing is frequently used forTable 2 Percentages of computational cycles, dependingon CU sizes and modesSize64 6432 3216 168 8ModeRA (%)LD (%)Average (%)Ratio in eachCU size 73.7Skip1.70.61.212.8Page 4 of 19Table 3 Percentages of computational cycles of top fourfunctionsModuleRA (%)LD (%)Interpolation filter35.7436.00Average form/inverse transform3.523.083.30Total (%)67.5870.9169.25hard-wired implementations. Note that function-levelparallel processing is not easily implemented mainlydue to difficulties of load balancing and longer development period. Data-level parallel processing is relativelyeasy to be employed for video encoders because thedata processing flows are the same for all the data. Thedata-level parallelism for HEVC can be conducted interms of CU-, slice-, and frame-level ones. In addition,HEVC contains a parallel tool, called tile, which dividesa picture into multiple rectangles [16]. In tile partitioning, the number of CTUs adjacent to boundaries of tilepartitions is less than that of slices. From this fact, tilepartitioning can yield slightly lower coding loss in compression efficiency compared to an implementation withthe same number of slices [17].For parallel implementations, we need to consider several factors, such as throughput and core scalability, aswell as coding efficiency. Note that the core scalabilitymeans how much we need to change an implementation,depending on an increasing or decreasing number ofcores. In addition, the throughput can be improved withparallel processing as compared with the single processing unit. However, many video coding algorithms, ingeneral, have dependencies among neighboring codingunits, neighboring frame, earlier-coded syntaxes, and soon. At the same time, we need to consider the codingefficiency degradation from the parallelization. Eventhough the throughput can be improved with parallelprocessing, it is not desirable that the coding efficiencyis significantly degraded. Regarding the core scalability,it is better to employ a scalable parallelization methodthat can be easily extended for an increasing number ofcores. If not, we are required to change the implementation, depending on the number of cores.The 2D wavefront algorithm [18] has been used for theparallelization of video coding in CTU level. This codingtool does not impact the coding gain, but there is a limitation in the parallelization factor, even with many cores,due to coding dependence. Frame-level parallelization canbe also used for non-reference bidirectional pictures; however, it depends on the encoding of reference structures.The slice-level parallelism is widely used because we canassume any dependencies among multiple slices. However,we need to realize that the coding gain can be degraded

Ahn et al. EURASIP Journal on Image and Video Processing 2014, 4/1/16with increased number of slices. In this paper, we evaluated bitrate increases in terms of the number of slices inthe HM encoder software. Figure 3 shows the bitrate increases in terms of the number of slices, for four sequenceclasses. In our evaluation, class A (2,560 1,600), class B(1,920 1,080), class C (832 480), and class D (416 240)of the HEVC common test sequences [15] were used,under HEVC common test conditions. As shown inFigure 3, we can see the bitrate increases in terms ofthe number of slices. The bitrate increase becomes lesssignificant as video resolution increases. In general,multiple slices are widely used for larger sequences dueto parallel processing and error resilience. Regardingmany commercial applications, the slice-level parallelprocessing is one of the good approaches for such largeresolution videos.As mentioned before, the slice-level parallelism hasrelatively high coding losses of around 2% to 4% compared to tile-level parallelism and wavefront processing[19]. However, slice-level parallelism has an advantage thatthe slice partitioning is more flexible and accurate for picture partitioning, by adjusting the number of CTUs, compared to the tile partitioning. Note that the tiles withinthe same row and column should use the same tilewidth and height, respectively. Slice-level parallelismof a fine-grained load balancing can yield additionalPage 5 of 19encoding speed-up compared to the tile levels. WPPhas the advantage that the loss of parallelization is relatively small compared to other parallelization methods.However, the acceleration factor of WPP is not so highcompared to slice- or tile-level parallelism because WPPhas prolog and epilog so that parts of the cores are inactivated. It is not easy to utilize all the cores with WPP onaverage. In our work, slice-level parallelism was chosen forthe acceleration of parallelization. In addition, slice partitioning is widely used for the packetizing of bitstreams forerror resiliencies, in practical video encoders and services.There are two main criteria to divide a picture intomultiple slices. One is an equal bitrate, and the other isthe same number of CTUs for all the slices. The first onecannot be easily employed for parallel encoding becausewe cannot define the target bit prior to actual encoding.For the second method, we can easily use the same number of CTUs at a time.4 Optimization for fast HEVC encoderIn this section, two software optimization methods, framelevel processing and SIMD implementation, for three mostcomplex functions at the function-level are presented.The proposed software optimization methods have several advantages to accelerate HEVC encoders withoutany bitrate increase.130ClassDClassCClassBClassA125Ratio of bitrate increments12011511010510012841632Number of slicesFigure 3 Bitrate increment in terms of the number of slices, for four sequence classes. HEVC common test sequences [15]; class A, 2,560 1,600; class B, 1,920 1,080; class C, 832 480; class D, 416 240.

Ahn et al. EURASIP Journal on Image and Video Processing 2014, 4/1/16integer sample in an entire frame. In addition, SIMD instructions and multi-thread processes using OpenMPand GPU can be easily used for fast encoding.4.1 Frame-level interpolation filter in HEVC encoderThe HEVC DCT-based interpolation filter (DCT-IF),which is used for obtaining fractional sample positions,is the most complex function, especially with motion estimation in encoders. Instead of using 6-tap and bilinearinterpolation filters of H.264/AVC, HEVC adopts 8(7)-tapDCT-IF for luminance components, and 4-tap DCT-IF forchrominance components [20]. Furthermore, all of thefractional position samples are derived by increasing thenumber of filter taps without intermediate rounding operations which can reduce potential rounding errors compared to H.264/AVC. In order to determine the optimalCU size and coding modes, HM encoder uses a recursivescheme for the RD optimization process. In particular,the PU-level interpolation filter causes iterative memoryaccesses for the same positions redundantly. Excessivememory accesses significantly increase encoding timedue to the limit of memory bandwidth. Actually, theDCT-IF occupies approximately 30% to 35% of thetotal cycles in the HM encoder. We adopt a framelevel interpolation filter to reduce redundant memoryaccesses. The frame-level interpolation filter avoids redundant execution that occurs in the RD optimizationprocess and enables parallel process with independencyamong neighboring blocks. However, it requires the additional amount of memory for 15 factional samples per12711195i7127i6111111j7PACKUSWB 14763j9jjH ði; jÞjj 2i2i11i879!31i363i9I;JX47j1279ð1Þwhere i and j are the pixel indices, and their ranges aredetermined by a block size. O(i,j) and P(i,j) are the original and predicted pixel values, respectively. Note that63j13jjOði; jÞ Pði; jÞjji;jj479j14SATD ¼63j5I;JXi;ji1279j6SAD ¼63i1395SAD, SATD, and DCT are the most complex functionsin the HEVC encoder, except for DCT-IF. Several costfunctions are used to decide the best coding mode andits associated parameters. SAD and SATD are the twomain metrics to find integer and quarter-pel motion vectors in the motion estimation process, respectively. SADtakes around 10% to 12% of the total cycles in HEVC encoder, and SATD takes 15% to 16%. These two costfunctions are defined byi479i144.2 SIMD implementation of cost function andtransformation63i595i1512779Page 6 of 190i1i015j3j20j1j0PSADBW1271110 0950 0790 063SAD[15-8]Figure 4 Computation steps of SAD using SIMD instructions.470 0310 0150 00SAD[7-0]PACKUSWB

Ahn et al. EURASIP Journal on Image and Video Processing 2014, 4/1/16Page 7 of 19c0 c1 c2 c3c8 c9 c10 c11c4 c5 c6 c7c12 c13 c14 c15PUNPCKLWDPUNPCKLWDc0 c4 c1 c5 c2 c6 c3 c7c8 c12 c9 c13 c10 c14 c11 c15PUNPCKLDQPUNPCKHDQc0 c4 c8 c12 c1 c5 c9 c13c2 c6 c10 c14 c3 c7 c11 c15PUNPCKLQDQPUNPCKHQDQPUNPCKLQDQPUNPCKHQDQc0 c4 c8 c12 c0 c4 c8 c12c1 c5 c9 c13 c1 c5 c9 c13c2 c6 c10 c14 c2 c6 c10 c14c3 c7 c11 c15 c3 c7 c11 c15k0 k4 k8 k12 k1 k5 k9 k13k0 k4 k8 k12 k1 k5 k9 k13k0 k4 k8 k12 k1 k5 k9 k13k0 k4 k8 k12 k1 k5 k9 k13PMADDWDPMADDWDc0*k0 c4*k4c8*k8 c12*k12c0*k1 c4*k5c8*k9 c12*k13k2 k6 k10 k14 k3 k7 k11 k15c8*k10 c12*k14c0*k3 c4*k7c8*k11 c12*k15c0*k1 c4*k5 c8*k9 c12*k13c0*k2 c4*k6 c8*k10 c12*k14c0*k3 c4*k7 c8*k11 c12*k15c1*k1 c5*k5c9*k9 c13*k13k2 k6 k10 k14 k3 k7 k11 k15c1*k2 c5*k6c1*k0 c5*k4 c9*k8 c13*k12c2*k0 c6*k4c10*k8 c14*k12c2*k1 c6*k5c10*k9 c14*k13k2 k6 k10 k14 k3 k7 k11 k15c1*k3 c5*k7c9*k11 c13*k15c1*k1 c5*k5 c9*k9 c13*k13c1*k2 c5*k6 c9*k10 c13*k14c1*k3 c5*k7 c9*k11 c13*k15c2*k2 c6*k6c10*k10 c14*k14c2*k3 c6*k7c10*k11 c14*k15c2*k1 c6*k5 c10*k9 c14*k13c2*k2 c6*k6 c10*k10 c14*k14c2*k3 c6*k7 c10*k11 c14*k15c11*k8 c15*k12c3*k1 c7*k5c11*k9 c15*k13k2 k6 k10 k14 k3 k7 k11 k15c3*k2 c7*k6c11*k10 c15*k14c3*k3 c7*k7c11*k11 c15*k15c3*k1 c7*k5 c11*k9 c15*k13c3*k2 c7*k6 c11*k10 c15*k14c3*k3 c7*k7 c11*k11 c15*k15PHADDDPHADDDc2*k0 c6*k4 c10*k8 c14*k12c3*k0 c7*k4PMADDWDPMADDWDc9*k10 c13*k14PHADDDPHADDDc0*k0 c4*k4 c8*k8 c12*k12c9*k8 c13*k12PMADDWDPMADDWDc0*k2 c4*k6c1*k0 c5*k4PMADDWDPMADDWDc3*k0 c7*k4 c11*k8 c15*k12Figure 5 Computation steps of HEVC inverse transform using SIMD instructions.H(i,j) is the Hadamard transformation of the predictionerror, O(i,j) P(i,j) [8]. Because only addition and subtraction operations are involved for the cost functions,SATD can yield an accurate cost in the transform domain with relatively small complexity compared to DCT.Since both apply the same operations on multiple data,vector instructions are quite useful to reduce the requiredclock cycles. This work uses SSE2 and SSE3 instructionsdefined in Intel SIMD architecture, which are widelyemployed for many DSP processors [21]. In the case ofthe SAD operation, we employed PSADBW (packed sumof absolute differences), PACKUSWB (packed with unsigned saturation), and PADDD (add packed double wordintegers) instructions. Sixteen SAD values can be computed by PSADBW instruction at once. Figure 4 showshow to compute SAD with SIMD instructions. Data packing is conducted with sixteen 16-bit original pixels (ix) andsixteen 16-bit reference pixels (jx) using PACKUSWB instruction. For 8-bit internal bit depth, the data packing isconducted to form 16-bit short data. For 10-bit internalbit depth, the data packing process is not required. Sixteenoriginal pixels and reference pixels are packed into two128-bit registers, and PSADBW is performed. The computed SAD from i0-j0 to i7-j7 is stored in the lower 16 bits,and the SAD from i8-j8 to i15-j15 is stored at bit position64 to 79. Acceleration of 4 4 to 64 64 SADcomputations can be achieved using the aforementionedinstructions based on instruction-level parallelism. The4 4 and 8 8 SATD operations are implemented usinginterleaving instructions, such as PUNPCKLQDQ (unpacklow-order quad-words), PUNPCKHWD (unpack highorder words), PUNPCKLWD (unpack low-order words),and arithmetic instructions, such as PADDW (add packedword integers), PSUBW (subtract packed word integers),and PABSW (packed absolute value).Not only the cost function but also the forward transform and inverse transform can be implemented withSIMD instructions. The forward transform and inversetransform in HEVC are implemented by partial butterflyor matrix multiplication. In this paper, the matrix multiplication is chosen due to its simplicity and regularity.Transform and inverse transform are accelerated usinginterleaving instructions such as PUNPCKLDQ (unpackTable 4 Normalized complexity for variable CU size andmodeCU sizeSkipInterIntra64 641097605232 32422801616 1697138 82191

Ahn et al. EURASIP Journal on Image and Video Processing 2014, 4/1/16Page 8 of 19(a)Slice 0Slice 1Slice 2Slice 30.5Ratio of actual encoding time0.40.30.20.10050100150200250Frame number300350400450500(b)Slice 0Slice 1Slice 2Slice 3Ratio of predicted encoding time0.50.40.30.20.10050100150200250Frame number300350400450Figure 6 Ratios of actual encoding time and predicted complexity for BasketballDrive sequence. (a) Ratios of actual encoding time forthe four slices. (b) Ratios of predicted complexity for four slices.500

Ahn et al. EURASIP Journal on Image and Video Processing 2014, 4/1/16low-order double words), PUNPCKHDQ (unpack highorder double words), PUNPCKLQDQ, PUNPCKHQDQ(unpack high-order quad words), and arithmetic instructions such as PMADDWD (packed multiply andadd), PADDD, and shift instruction such as PSRAD(packed shift right arithmetic). For HEVC forward andbackward transformation, we need to consider the datarange and the center value in computing matrix multiplications, unlike SAD and SATD implementations. Figure 5shows how to compute the HEVC inverse transform usingSIMD instructions. Data packing is conducted withsixteen 16-bit coefficients (cx) using PUNPCKLWDinstruction. The 16 coefficients are packed into two128-bit registers. For reordering coefficients, the packedcoefficient signals are repacked using PUNPCKLQDQ andPUNPCKHQDQ instructions. Repacked coefficients andthe kernel (kx) of the inverse transform are multipliedfor eight 16-bit data in 128-bit registers. Then, the results of multiplications are added into 128-bit registersusing PMADDWD instruction. Finally, the results ofPMADDWD are added into the 128-bit destinationregister to compute inverse-transformed residuals usingPHADD instruction. Input data for transformation rangefrom 255 to 255. As a result, the data should be represented by at least 9 bits. Data ranges of coefficients ofHEVC transform kernels depend on the size of the transform kernels. However, they can be represented in 8 bitsfor the 32 32 kernel because they range from 90 to 90[22]. For computation of one transform coefficient, the required number of addition and multiplication operationsis as many as the size of the transform kernel along thehorizontal and vertical directions. A downscale shouldbe employed to keep 16 bits in every operation for eachdirection. To avoid overflow and underflow, four 32bit data should be packed into the 128-bit integerregister of SSE2. In addition, the transform matrix istransposed in advance to reduce memory read/writeoperations.5 Proposed slice-level parallelism with loadbalanceTo reduce the computational load of the RD optimization,early termination and mode competition algorithms havebeen adopted in HM reference software [23-25]. However,these fast encoding algorithms cause different encodingcomplexities among different slices. To maximize parallelism of the data-level task partition, an accurate load balance for slice parallelization is required. Several works[26,27] have been conducted to achieve accurate load balance for slice parallelization. In Zhang's algorithm [26],the adaptive data partitioning for MPEG-2 video encoderswas proposed by adjusting computational loads based onthe complexity of a previously encoded frame of the samepicture type. In Jung's algorithm [27], the adaptive slicePage 9 of 19partition algorithm was proposed to use early-decidedcoding mode for macro-blocks in H.264/AVC. In the conventional algorithm, a quantitative model was designed toestimate the computational load associate

the number of redundant filtering. For data-level pa-rallelization, this paper demonstrates how to allocate encoding jobs to all the available cores through the use of complexity estimation. As a result, it is possible to achieve load-balanced slice parallelism in HEVC en-coders to significantly reduce the average encoding time.