CN104320668B - HEVC/H.265 DCT Transformation and Inverse Transformation SIMD Optimization Method - Google Patents

Abstract

The present invention provides a HEVC/H.265 SIMD optimization method for DCT transformation and inverse transformation. First, preprocess the input data, load the data from the memory into the register, regard it as a data vector, and interleave and re-interleave the vector data. Permutation and combination, for the DCT transformation in the vertical direction, the data is shifted to the right and rounded to adapt to the limited register bit width and improve the parallelism of calculation; then the butterfly operation is performed on the preprocessed data, and the sum and difference of the corresponding data are calculated step by step ; Then perform dot multiplication, calculate the sum of the intermediate value obtained by the butterfly operation and the product of the corresponding transformation coefficient, and obtain the product of the input data and the transformation matrix; finally, round the result of the matrix product to meet the bit width of the output data Limit and output. The invention can effectively accelerate the DCT transform and inverse transform module of the HEVC/H.265 video encoder on the Tilera platform, and obtain better acceleration and optimization effects.

Description

HEVC/H.265 DCT Transformation and Inverse Transformation SIMD Optimization Method

technical field

The present invention relates to the technical field of video coding, in particular, to a SIMD accelerated optimization method (based on the Tilera platform) for DCT transformation and inverse transformation of the HEVC/H.265 video coding standard, using the SIMD instruction set of Tilera to realize the DCT transformation of HEVC And the inverse transformation module to improve the running speed.

Background technique

With the growth of video content and the rapid development of video products, the video content industry chain is facing greater pressure. At present, AVC (Advanced Video Coding) video compression technology can no longer meet the requirements of video transmission, and more efficient video compression technology has emerged . Not only that, the future video market tends to require higher levels, such as 3D TV and 4K TV, which have exceeded the scope of current AVC encoding capabilities. For 4K TV, even if the current H.264 encoding method is used, the code rate of 24-32M is still required. AVC has become the bottleneck of 4K TV business development. In this context, a new video coding standard called High Efficiency Video Coding (HEVC) emerged as the times require. The development of HEVC can be traced back to 2004. After nearly ten years of development, HEVC formed a complete committee standard draft in February 2012, and officially became an international standard in January 2013. The goal of HEVC is to increase the coding efficiency by 50% compared with AVC, and the complexity is 2 to 10 times more complex than AVC. The future business of HEVC is mainly for HD, UHD, and 3D TV. The data volume is much larger than that of previous videos. In addition, HEVC requires a greatly improved video compression ratio, and the high compression algorithm is at the cost of increasing algorithm complexity. Considering these two Due to these factors, the HEVC encoder puts forward higher requirements on the computing performance of the system.

In order to reduce the complexity of HEVC coding, there are usually methods such as algorithm optimization, instruction set optimization, and parallel optimization. Among them, instruction set optimization is to use the instruction set of the computing platform to realize the computing module. SIMD (single instruction multiple data) technology can be used in one The parallel processing of multiple data calculations in the instruction cycle can greatly reduce the instruction cycle and improve the running speed compared with the conventional implementation scheme, and at the same time ensure that the calculation results are accurate. In video coding, SIMD technology is widely used in intensive data calculations, such as sub-pixel interpolation, SAD, DCT/IDCT, computing residuals and other modules.

To implement the HEVC encoder on the Tilera platform, we transplanted the DCT/IDCT implementation method of the HEVC reference code HM. Compared with H.264, the DCT module of HEVC has greatly improved the complexity. The transformation coefficients of H.264 are 1 and 2, and the transformation of H.264 only needs simple shift and addition calculations. HEVC supports transform blocks from 4x4 to 32x32. In addition, the DCT coefficients of HEVC are larger and more complex, which means that the DCT change of HEVC needs to perform multiple multiplications, and the value of the intermediate variable is larger, requiring a larger bit width. When performing DCT transformation in the vertical direction, the value of the intermediate variable exceeds the storage range of 16bit, which is 17-19bit. If the intermediate variable is stored in 32bit, the parallel level of data processing will be greatly reduced. For some existing HEVC DCT and IDCT SIMD implementation methods on Intel and Arm, the speed of DCT transformation in the vertical direction is lower than that of DCT transformation in the horizontal direction.

Contents of the invention

In view of the defects in the prior art, the purpose of the present invention is to provide a SIMD optimization method for DCT transformation and inverse transformation of HEVC/H.265, said method is aimed at the DCT and IDCT of HEVC realized by the conventional C language on the Tilera platform To solve the problems of high computational complexity and slow encoding speed of the module, the DCT transformation and inverse transformation modules of HEVC are implemented by using Tilera's SIMD instruction set to improve the running speed.

To achieve the above object, the present invention provides a SIMD optimization method for DCT transformation and inverse transformation of HEVC/H.265, comprising the following steps:

In the first step, the one-dimensional DCT input data is loaded into the register from the memory and regarded as vector data;

The second step is to rearrange and combine the vector data, perform butterfly operation, add and subtract the input data step by step, and calculate the intermediate variable vector;

In the third step, if the one-dimensional DCT transformation is a horizontal direction transformation, skip directly to the fifth step;

The fourth step is to perform right-shift rounding operation on the intermediate variable to limit its bit width;

The fifth step is to perform dot multiplication between the intermediate variable vector and the corresponding coefficient vector;

The sixth step is to rearrange and combine the results of the dot multiplication operation, perform right shift rounding, and save the output result to the target memory.

Preferably, in the second step, the parallel addition and subtraction of the input data is performed, the butterfly operation is performed, and the parallel addition and subtraction is performed step by step multiple times to calculate the intermediate variable vector used for the dot product calculation.

Preferably, in the fourth step, the one-dimensional DCT transform performs rounding preprocessing on the intermediate variable. In order to maintain parallelism and achieve a better acceleration effect, for the one-dimensional DCT transform in the vertical direction, the intermediate variable is shifted to the right Rounding makes the bit width within 16 bits; the specific right shift calculation is as formula (1):

y=(x+(1<<(MIVO-1)))>>MIVO (1)

Among them: x is the data that needs to be rounded to the right, MIVO is the maximum order of the intermediate variable, and y is the result after performing the rounding to the right;

At the same time, the shift value of the input variable should be adjusted accordingly according to MIVO, so that it can offset the right shift and rounding of the intermediate variable. The shift value is the number of bits that need to be shifted to the right and rounded when the DCT outputs.

Preferably, in the fifth step, a dot product calculation instruction is used to replace multiple multiplication and addition operations, effectively accelerating the process of product summation of intermediate variables and corresponding coefficients. Further, for calculating the dot product of four intermediate variables and corresponding coefficients, it can be completed by directly executing the quaternary vector dot product with one instruction; for the dot product of more than four intermediate variables and corresponding coefficients, multiple quaternary vector The multiplication is completed; for calculating the dot product of two intermediate variables and corresponding coefficients, it is completed by using parallel multiplication and addition instructions.

Preferably, in the sixth step, parallel addition and right shift operations and data reorganization are used to complete the right shift and round operation of the dot product calculation results in parallel; the right shift and round calculation is as formula (2):

y=(x+offset)>>shift

offset=(1<<(shift-1))

error=2 ^shift-1

In the formula: x is the data that needs to be rounded to the right, y is the result of rounding to the right; offset is the compensation value used for rounding, derived from the right shift number shift, and the shift value is determined by the DCT transform block The size N (4, 8, 16, 32) and the data bit width B (8bit, 10bit) are derived. The shift value in the horizontal direction (horizontal) is related to N and B, while the shift value in the vertical direction (vertical) It is related to N. According to the shift value, it can be used to judge the direction of one-dimensional DCT transformation: horizontal or vertical; error is the maximum error caused by the right-shift rounding operation.

Compared with the prior art, the present invention has the following beneficial effects:

The method provided by the present invention uses the instruction set of the Tilera platform to perform SIMD optimization on the DCT and IDCT modules of the Tilera, so as to effectively accelerate the DCT and IDCT modules of the HEVC on the Tilera platform under the condition of slight performance loss. It has been verified that compared with the common C code implementation method, after using this invention, the DCT and IDCT modules of HEVC on the Tilera platform can reduce the number of instruction cycles by an average of 40%-70%, while BD-PSNR (under the same quality PSNR) has a loss of less than 0.003.

Description of drawings

Other characteristics, objects and advantages of the present invention will become more apparent by reading the detailed description of non-limiting embodiments made with reference to the following drawings:

Fig. 1 is the flow chart of one-dimensional DCT transformation of a preferred embodiment of the present invention;

Fig. 2 is the flow chart of one-dimensional IDCT transformation of a preferred embodiment of the present invention;

Fig. 3 is a schematic diagram of intermediate variables calculated by butterfly operation in a preferred embodiment of the present invention;

Fig. 4 is the flow chart that a preferred embodiment of the present invention carries out pretreatment to intermediate variable;

Fig. 5 is a schematic diagram of performing vector dot multiplication in a butterfly operation of a preferred embodiment of the present invention, wherein: (a) is a schematic diagram of four-element vector dot multiplication, and (b) is a schematic diagram of two-element vector dot multiplication;

6 is a schematic diagram of a subsequent rounding operation performed on the butterfly operation result in a preferred embodiment of the present invention;

Fig. 7 is a schematic diagram of transposing and transforming data in one-dimensional IDCT in a preferred embodiment of the present invention.

detailed description

The present invention will be described in detail below in conjunction with specific embodiments. The following examples will help those skilled in the art to further understand the present invention, but do not limit the present invention in any form. It should be noted that those skilled in the art can make several modifications and improvements without departing from the concept of the present invention. These all belong to the protection scope of the present invention.

As shown in Figures 1 and 2, the present embodiment provides a SIMD optimization method (based on the Tilera platform) for DCT transformation and inverse transformation of HEVC/H.265, and the specific implementation steps are as follows:

Step (1), load the one-dimensional DCT input data into the register from the memory, and regard it as vector data; specifically:

Read data in batches from the memory block where the input data is located, load multiple adjacent low-bit-width input data into a 64bit register, and load it into a data vector.

Step (2), rearrange and combine the vector data, perform butterfly operation, add and subtract the input data step by step, and calculate the intermediate variable vector, as shown in Figure 3; specifically:

The DCT transform coefficients of HEVC have strong odd-even symmetry. Using this symmetry, the data is firstly added and subtracted step by step, and then multiplied by the corresponding coefficients, which can effectively reduce multiplication operations. This is the butterfly The principle of shape operation. The data vector loaded from the memory into the register cannot be directly added or subtracted. The vector data needs to be rearranged and combined to make it conform to the required operation rules, and then the subsequent calculation process is executed. There are corresponding instructions on the Tilera platform, which support the permutation and combination of any byte in two 64bit data.

In the subsequent steps, the data needs to be continuously arranged and combined to meet the corresponding operation rules.

Then use the parallel addition and subtraction instructions to complete the addition and subtraction of the vector, so that one instruction can complete the addition and subtraction of multiple data at the same time, reducing the instruction cycle and realizing acceleration. With the increase of the DCT transform block, the calculation stages of the intermediate variables will also increase. In the process of calculating the intermediate variables step by step, the calculation results need to be rearranged and combined to meet the subsequent operation rules.

Step (3), if the horizontal direction transformation during the one-dimensional DCT transformation, directly jump to step (5), as shown in Figure 4; specifically:

The input variable shift of the one-dimensional DCT transformation in the horizontal direction and the vertical direction is different. By judging the value of the input variable shift, it can be judged whether it is a one-dimensional DCT transformation in the horizontal direction or in the vertical direction.

Step (4), performing right-shift rounding operation on the intermediate variable, limiting its bit width, as shown in Figure 4; specifically:

The two-dimensional DCT transform consists of two-dimensional one-dimensional DCT transforms: the horizontal DCT transform and the vertical DCT transform. In HEVC, the one-dimensional DCT transformation in the horizontal direction is first performed, and the input data is the residual of the pixel value, which is a signed number with a 9-bit width. During the step-by-step calculation of the intermediate variables by the butterfly operation, the bit width of the intermediate variables can be guaranteed to be within 16 bits. However, when performing the vertical one-dimensional DCT transformation, the input is the output of the horizontal DCT transformation, and the bit width is 16 bits, so the intermediate variable of the butterfly operation cannot be saved with a 16-bit bit width, otherwise a serious overflow error will occur. If it is stored in 32 bits, the parallelism will decrease and it will not be able to achieve a good acceleration effect. In order to solve this problem, the intermediate variable is right-shifted and rounded, and the low-order bits are discarded, so that it can be saved with a 16-bit bit width, and parallelism is exchanged for a certain bit error cost.

The specific right shift calculation is as formula (1):

y=(x+(1<<(MIVO-1)))>>MIVO (1)

Among them: x is the data that needs to be rounded to the right, MIVO is the maximum order of the intermediate variable, and y is the result after the rounding to the right is performed.

In addition, the value of the input variable shift should be adjusted accordingly according to MIVO, so that it can offset the right-shift rounding of the intermediate variable.

Step (5), carry out dot multiplication operation with intermediate variable vector and corresponding coefficient vector, as shown in (a) and (b) among Fig. 5; Concrete:

The Tilera platform provides vector point multiplication instructions. One instruction can perform point multiplication and summation of multiple data, which has a good acceleration effect.

For calculating the dot product of four intermediate variables and corresponding coefficients, it can be completed by directly executing the quaternary vector dot product with one instruction; for the dot product of more than four intermediate variables and corresponding coefficients, it can be completed by multiple quaternary vector dot multiplication ; For calculating the dot product of two intermediate variables and corresponding coefficients, Tilera has no direct instructions, and the present invention uses parallel multiplication and addition instructions to complete.

The dot product calculation of intermediate variables is the core calculation part of the DCT transformation, and the multiplication complexity is high. The operations before performing the dot product calculation are all to prepare data and adapt to the calculation rules of the dot product instruction.

Step (6), rearrange and combine the results of the point multiplication operation, perform right shift rounding, and save the output result to the target memory, as shown in Figure 6; specifically:

Based on the regulations of HEVC, the output bit width of one-dimensional DCT transformation is 16 bits, and the result of the point multiplication calculation is 32 bits, which needs to be rounded and saved as 16 bits; the rounding calculation of HEVC is shown in formula (2):

y=(x+offset)>>shift

offset=(1<<(shift-1))

error=2 ^shift-1

In the formula: x is the data that needs to be rounded to the right, y is the result of rounding to the right; offset is the compensation value used for rounding, derived from the right shift number shift, and the shift value is determined by the DCT transform block The size N (4, 8, 16, 32) and the data bit width B (8bit, 10bit) are derived. The shift value in the horizontal direction (horizontal) is related to N and B, while the shift value in the vertical direction (vertical) It is related to N. According to the shift value, it can be used to judge the direction of one-dimensional DCT transformation: horizontal or vertical; error is the maximum error caused by the right-shift rounding operation.

Save the dot product result obtained in step (5) as 32bit data, and store two dot product results in a 64bit register, first add the offset value offset to the dot product result in parallel, and then shift right in parallel to get the 16bit output result . The output results are rearranged and combined, and finally saved to the output memory space to complete the output.

The above are the detailed steps of one-dimensional DCT transformation. One-dimensional IDCT is the reverse operation of one-dimensional DCT. The specific process is similar to that of DCT transformation. The difference is that the input data needs to be transposed, as shown in Figure 7. The data used for a point multiplication calculation in one-dimensional DCT is continuous in memory distribution, so it can be directly loaded into registers for calculation; while the input data for one point multiplication calculation in one-dimensional IDCT is discontinuous in memory distribution , can not be directly used for calculation after being loaded into the register; the present invention will be loaded into the memory distribution adjacent vector data of the register and interweave two by two, and finally achieve the effect of transposition, that is, the nth (1, 2, 3, 4) elements form the nth new quaternary vector, and the transposed data vector can be directly used for subsequent calculations.

The present invention can effectively accelerate the DCT transformation and inverse transformation module of the HEVC/H.265 video encoder on the Tilera platform, obtain better acceleration and optimization effects, and reduce HEVC coding complexity.

Specific embodiments of the present invention have been described above. It should be understood that the present invention is not limited to the specific embodiments described above, and those skilled in the art may make various changes or modifications within the scope of the claims, which do not affect the essence of the present invention.

Claims (6)

1. the dct transform of HEVC/H.265 a kind of and the SIMD optimization methods of inverse transformation, it is characterised in that comprise the following steps：

The first step, enters register from memory loading by one-dimensional DCT input datas, is considered as vector data；

Second step, combination is rearranged to vector data, performs butterfly computation, input data is added and subtracted step by step, centre is calculated Variable vector；

3rd step, if the one-dimensional dct transform is horizontally oriented conversion, leaps to the 5th step；

4th step, carries out moving to right rounding-off computing, to limit its bit wide to intermediate variable；

5th step, point multiplication operation is carried out by the corresponding coefficient vector of intermediate variable vector；For calculate four intermediate variables and The dot product of corresponding coefficient, directly performing four-vector point using an instruction can complete at convenience；For anaplasia in more than four The dot product of amount and corresponding coefficient, is completed by multiple four-vector dot product；For calculating two intermediate variables and corresponding coefficient Dot product, completed using parallel multiplication and addition instruction；

6th step, the result of point multiplication operation is carried out to rearrange combination, execution moves to right rounding-off, and output result is preserved to target Deposit.

2. a kind of HEVC/H.265 according to claim 1 dct transform and the SIMD optimization methods of inverse transformation, its feature It is, in the second step, to the parallel plus-minus of input data, completes butterfly computation, carry out parallel addition and subtraction multiple step by step, Calculate the intermediate variable vector calculated for dot product.

3. a kind of HEVC/H.265 according to claim 1 dct transform and the SIMD optimization methods of inverse transformation, its feature It is, in the 4th step, one-dimensional dct transform carries out rounding-off pretreatment to intermediate variable, becomes for the one-dimensional DCT of vertical direction Change, intermediate variable is moved to right into rounding-off makes its bit wide in 16bit.

4. a kind of HEVC/H.265 according to claim 3 dct transform and the SIMD optimization methods of inverse transformation, its feature It is, in the 4th step, specifically moves to right calculating such as formula (1)：

Y=(x+ (1 ＜ ＜ (MIVO-1))) ＞ ＞ MIVO (1)

Wherein：X is needs the data for carrying out moving to right rounding-off, and MIVO is intermediate variable maximum order, and y is to have performed to move to right after rounding-off Result；

Meanwhile, input variable shift values will also do corresponding adjustment according to MIVO, and can offset intermediate variable moves to right house Enter, shift values need the digit for being rounded data shift right when being DCT outputs.

5. a kind of HEVC/H.265 according to claim 1 dct transform and the SIMD optimization methods of inverse transformation, its feature It is, in the 6th step, using parallel addition and shift right operation and data recombination, completes parallel to dot product result of calculation Progress moves to right rounding-off operation.

6. a kind of HEVC/H.265 according to claim 5 dct transform and the SIMD optimization methods of inverse transformation, its feature It is, in the 6th step, moves to right rounding-off and calculate such as formula (2)：

In formula：X is to need to perform the data for moving to right rounding-off, and y is to have performed the result for moving to right rounding-off；Offset is to be used for four houses five The offset entered, by move to right digit shift derive, shift values by discrete cosine transform block size N (4,8,16,32) and data Bit wide B (8bit, 10bit) is derived, and horizontal direction horizontal shift values and N, B is relevant, and vertical direction Vertical shift values are relevant with N, and the direction of one-dimensional dct transform is judged according to the difference of shift values：Level is still erected Directly；Error is to perform to move to right the worst error that rounding-off operation is produced.