Method and system for performing two-dimensional transform on data value array with reduced power consumption

• US 20080050036A1
• Filed: 08/25/2006
• Published: 02/28/2008
• Est. Priority Date: 08/25/2006
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: PortalPlayer USA, Inc. (NVIDIA Corporation)
• Inventors: Sriram, Partha, Bulusu, Ravi
• Granted Patent: US 8,660,380 B2
• Time in Patent Office: Days
• US Class Current: 382/281
• CPC Class Codes: G06F 17/145 Square transforms, e.g. Hadamard, Walsh, Haar, Hough, Slant transforms
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence

Abstract

In some embodiments, a method for performing and a system configured to perform a 2D transform (for example, an inverse discrete cosine transform) on each block of a sequence of data blocks, where the 2D transform includes a row transform and a column transform. To perform the row or column transform on a row or column of data, these embodiments determine whether each of different subsets of the data values comprising a partition of the row (column) includes at least one zero value, whether each of different subsets of a first subset of the partition includes at least one zero value, and whether each of different subsets of at least one other subset of the partition includes at least one zero value. When performing the row (column) transform on each row or column that includes at least one zero value and at least one non-zero value, at least one transformation operation on at least one zero value is bypassed or performed in a reduced-power manner, where such transformation operation would otherwise be performed in a manner consuming full power if the zero value were a non-zero value. In some embodiments, the system is a pipelined video decoding system or other video processing system (or a video processing subsystem of a portable media player or other system) including a transform engine implemented in accordance with the invention. Other aspects are transform engines and transform engine circuitry for use in any embodiment of the system.

Claims

1. A system configured to perform a 2D transform on each input data block of a sequence of input data blocks, wherein each said input data block comprises rows and columns of input data values and the 2D transform includes a row transform and a column transform, said system including:

row transform circuitry configured to generate a block of partially transformed data in response to each said input data block, by performing the row transform on each row of the input data block; and

column transform circuitry configured to perform the column transform on each column of the block of partially transformed data,

wherein the row transform circuitry is configured to determine, when performing the row transform on each said row, whether each of different subsets of the data values comprising a partition of the row includes at least one zero value, whether each of different subsets of a first one of the subsets of the partition of the row includes at least one zero value, and whether each of different subsets of a second one of the subsets of the partition of the row includes at least one zero value, and

the row transform circuitry is configured to bypass or perform in a reduced-power manner at least one transformation operation on at least one of the data values that is determined to be a zero value.

2. The system of claim 1, wherein the row transform circuitry is configured to bypass the at least one transformation operation on said at least one of the data values that is determined to be a zero value.

3. The system of claim 1, wherein the row transform circuitry is configured to perform in a reduced-power manner the at least one transformation operation on said at least one of the data values that is determined to be a zero value.

4. The system of claim 3, wherein the row transform circuitry includes at least one circuit having an input set, and the row transform circuitry is configured to perform the at least one transformation operation in the reduced-power manner by causing the circuit to operate without updating at least one input in said input set during the transformation operation on said one of the data values that is determined to be a zero value.

5. The system of claim 1, wherein the 2D transform is an inverse discrete cosine transform.

6. The system of claim 1, also including:

a buffer coupled to the row transform circuitry and to the column transform circuitry, wherein the row transform circuitry is configured to store the block of partially transformed data in the buffer and the column transform circuitry is configured to retrieve columns of the block of partially transformed data from the buffer.

7. The system of claim 6, wherein the column transform circuitry is configured to determine, when performing the column transform on each said column, whether each of different subsets of the data values comprising a first partition of the column includes at least one zero value, whether each of different subsets of a first one of the subsets of the first partition of the column includes at least one zero value, and whether each of different subsets of a second one of the subsets of the first partition of the column includes at least one zero value, and

the column transform circuitry is configured to bypass at least one transformation operation on at least one of the data values that is determined to be a zero value.

8. The system of claim 6, wherein the column transform circuitry is configured to determine, when performing the column transform on each said column, whether each of different subsets of the data values comprising a first partition of the column includes at least one zero value, whether each of different subsets of a first one of the subsets of the first partition of the column includes at least one zero value, and whether each of different subsets of a second one of the subsets of the first partition of the column includes at least one zero value, and

the column transform circuitry is configured to perform in a reduced-power manner at least one transformation operation on at least one of the data values that is determined to be a zero value.

9. The system of claim 8, wherein the column transform circuitry includes at least one circuit having an input set, and the column transform circuitry is configured to perform the at least one transformation operation in the reduced-power manner by causing the circuit to operate without updating at least one input in said input set during the transformation operation on said one of the data values that is determined to be a zero value.

10. The system of claim 1, wherein each said row comprises values x_i, where i is an integer in the range 0≦

i≦

N−

1, and N is an even integer, the partition of the row includes a first subset of data values and a second subset of data values distinct from the first subset, a partition of the first subset includes a third subset of data values and a fourth subset distinct from the third subset, and a partition of the second subset includes a fifth subset of data values and a sixth subset distinct from the fifth subset, and

wherein the row transform circuitry is configured to determine when performing the row transform on each said row whether the first subset consists entirely of zero values and whether the second subset consists entirely of zero values, and upon determining that the first subset consists entirely of zero values to bypass at least one said transformation operation on the data values in the first subset, and upon determining that the second subset consists entirely of zero values, to bypass at least one said transformation operation on the data values in the second subset.

11. The system of claim 10, wherein the row transform circuitry is configured to determine, upon determining that each of the first subset and the second subset includes at least one non-zero value when performing the row transform on each said row, whether each of the third subset, the fourth subset, the fifth subset, and the sixth subset consists entirely of zero values.

12. The system of claim 11, wherein the third subset consists of even values of the first subset, the fourth subset consists of odd values of the first subset, the fifth subset consists of even values of the second subset, and the sixth subset consists of odd values of the second subset.

13. The system of claim 1, wherein the row transform circuitry is configured to perform a reordering operation when performing the row transform on each said row, wherein the reordering operation generates reordered data values by reordering data values of the row, and the row transform circuitry is configured to determine whether a first subset of the reordered data includes at least one zero value and whether a second subset of the reordered data includes at least one zero value, wherein the second subset of the reordered data is distinct from the first subset of said reordered data.

14. A system configured to perform a 2D transform on each input data block of a sequence of input data blocks, wherein each said input data block comprises rows and columns of input data values and the 2D transform includes a row transform and a column transform, said system including:

column transform circuitry configured to generate a block of partially transformed data in response to each said input data block, by performing the column transform on each column of the input data block; and

row transform circuitry configured to perform the row transform on each row of the block of partially transformed data,

wherein the column transform circuitry is configured to determine, when performing the column transform on each said column, whether each of different subsets of the data values comprising a partition of the column includes at least one zero value, whether each of different subsets of a first one of the subsets of the partition of the column includes at least one zero value, and whether each of different subsets of a second one of the subsets of the partition of the column includes at least one zero value, and

the column transform circuitry is configured to bypass or perform in a reduced-power manner at least one transformation operation on at least one of the data values that is determined to be a zero value.

15. The system of claim 14, wherein the column transform circuitry is configured to bypass the at least one transformation operation on said at least one of the data values that is determined to be a zero value.

16. The system of claim 14, wherein the column transform circuitry is configured to perform in a reduced-power manner the at least one transformation operation on said at least one of the data values that is determined to be a zero value.

17. The system of claim 16, wherein the column transform circuitry includes at least one circuit having an input set, and the column transform circuitry is configured to perform the at least one transformation operation in the reduced-power manner by causing the circuit to operate without updating at least one input in said input set during the transformation operation on said one of the data values that is determined to be a zero value.

18. The system of claim 14, wherein the 2D transform is an inverse discrete cosine transform.

19. The system of claim 14, also including:

a buffer coupled to the row transform circuitry and to the column transform circuitry, wherein the column transform circuitry is configured to store the block of partially transformed data in the buffer and the row transform circuitry is configured to retrieve columns of the block of partially transformed data from the buffer.

20. The system of claim 14, wherein each said column comprises values x_i, where i is an integer in the range 0≦

i≦

N−

1, and N is an even integer, the partition of the column includes a first subset of data values and a second subset of data values distinct from the first subset, a partition of the first subset includes a third subset of data values and a fourth subset distinct from the third subset, and a partition of the second subset includes a fifth subset of data values and a sixth subset distinct from the fifth subset, and

wherein the column transform circuitry is configured to determine when performing the column transform on each said column whether the first subset consists entirely of zero values and whether the second subset consists entirely of zero values, and upon determining that the first subset consists entirely of zero values to bypass at least one said transformation operation on the data values in the first subset, and upon determining that the second subset consists entirely of zero values, to bypass at least one said transformation operation on the data values in the second subset.

21. The system of claim 20, wherein the column transform circuitry is configured to determine, upon determining that each of the first subset and the second subset includes at least one non-zero value when performing the column transform on each said column, whether each of the third subset, the fourth subset, the fifth subset, and the sixth subset consists entirely of zero values.

22. The system of claim 21, wherein the third subset consists of even values of the first subset, the fourth subset consists of odd values of the first subset, the fifth subset consists of even values of the second subset, and the sixth subset consists of odd values of the second subset.

23. The system of claim 14, wherein the column transform circuitry is configured to perform a reordering operation when performing the column transform on each said column, wherein the reordering operation generates reordered data values by reordering data values of the column, and the column transform circuitry is configured to determine whether a first subset of the reordered data includes at least one zero value and whether a second subset of the reordered data includes at least one zero value, wherein the second subset of the reordered data is distinct from the first subset of said reordered data.

24. A method for performing a 2D transform on a sequence of input data blocks, wherein each of the blocks comprises rows and columns of input data values, and the 2D transform includes a row transform and a column transform, said method including the steps of:

(a) performing the row transform on each row of one of the input data blocks, including by performing transformation operations on input data values of each said row, to generate a partially transformed data block; and

(b) performing the column transform on each column of the partially transformed data block, including by performing additional transformation operations on data values of each said column, wherein step (a) includes the steps of;

(c) determining whether each of different subsets of the data values comprising a partition of each said row includes at least one zero value, determining whether each of different subsets of a first subset of the partition includes at least one zero value, and determining whether each of different subsets of at least one other subset of the partition includes at least one zero value; and

(d) when performing the row transform on each said row that is determined to include at least one zero value and at least one non-zero value, bypassing or performing in a reduced-power manner at least one of the transformation operations on at least one of the input data values that is determined to be a zero value, where said one of the transformation operations would otherwise be performed in a manner consuming full power if the zero value were a non-zero value.

25. The method of claim 24, wherein step (a) includes the step of operating a multiplication circuit having a first input and a second input to perform a multiplication operation in which a first value asserted to the first input is multiplied by a second value asserted to the second input, and wherein step (d) includes the step of performing the multiplication operation for said at least one of the input data values that is determined to be a zero value in a reduced-power manner, by preventing toggling of at least one of the first input and the second input.

26. The method of claim 24, wherein step (d) includes the step of, when performing the row transform on each said row that is determined to include at least one zero value and at least one non-zero value, bypassing said at least one of the transformation operations on said at least one of the input data values that is determined to be a zero value.

27. The method of claim 24, wherein step (b) includes the steps of:

determining whether each of different subsets of the data values comprising a first partition of each said column includes at least one zero value, determining whether each of different subsets of a first subset of the first partition includes at least one zero value, and determining whether each of different subsets of at least one other subset of the first partition includes at least one zero value; and

when performing the column transform on each said column that is determined to include at least one zero value and at least one non-zero value, bypassing at least one of the additional transformation operations on at least one of the data values that is determined to be a zero value, where said one of the additional transformation operations would otherwise be performed in a manner consuming full power if the zero value were a non-zero value.

28. The method of claim 24, wherein step (b) includes the steps of:

determining whether each of different subsets of the data values comprising a first partition of each said column includes at least one zero value, determining whether each of different subsets of a first subset of the first partition includes at least one zero value, and determining whether each of different subsets of at least one other subset of the first partition includes at least one zero value; and

when performing the column transform on each said column that is determined to include at least one zero value and at least one non-zero value, performing in a reduced-power manner at least one of the additional transformation operations on at least one of the data values that is determined to be a zero value, where said one of the additional transformation operations would otherwise be performed in a manner consuming full power if the zero value were a non-zero value.

29. The method of claim 24, wherein each said block is a block of DCT coefficients that have been generated by performing a DCT on video data and the 2D transform is an inverse discrete cosine transform.

30. The method of claim 24, wherein at least substantially all of the blocks in the sequence are blocks of sparse data.

31. A method for performing a 2D transform on a sequence of input data blocks, wherein each of the blocks comprises rows and columns of input data values, and the 2D transform includes a row transform and a column transform, said method including the steps of:

(a) performing the row transform on each row of one of the input data blocks, including by performing transformation operations on input data values of each said row, to generate a partially transformed data block; and

(b) performing the column transform on each column of the partially transformed data block, including by performing additional transformation operations on data values of each said column, wherein step (b) includes the steps of;

(c) determining whether each of different subsets of the data values comprising a partition of each said column includes at least one zero value, determining whether each of different subsets of a first subset of the partition includes at least one zero value, and determining whether each of different subsets of at least one other subset of the partition includes at least one zero value; and

(d) when performing the column transform on each said column that is determined to include at least one zero value and at least one non-zero value, bypassing or performing in a reduced-power manner at least one of the additional transformation operations on at least one of the data values that is determined to be a zero value, where said one of the additional transformation operations would otherwise be performed in a manner consuming full power if the zero value were a non-zero value.

32. The method of claim 31, wherein step (b) includes the step of operating a multiplication circuit having a first input and a second input to perform a multiplication operation in which a first value asserted to the first input is multiplied by a second value asserted to the second input, and wherein step (d) includes the step of performing the multiplication operation for said at least one of the input data values that is determined to be a zero value in a reduced-power manner, by preventing toggling of at least one of the first input and the second input.

33. The method of claim 31, wherein step (d) includes the step of, when performing the column transform on each said column that is determined to include at least one zero value and at least one non-zero value, bypassing said at least one of the additional transformation operations on said at least one of the data values that is determined to be a zero value.

34. The method of claim 31, wherein each said block is a block of DCT coefficients that have been generated by performing a DCT on video data and the 2D transform is an inverse discrete cosine transform.

35. The method of claim 31, wherein at least substantially all of the blocks in the sequence are blocks of sparse data.

36. A video processing system, including a transform engine configured to perform a 2D transform on each input data block of a sequence of input data blocks, wherein each said input data block comprises rows and columns of input data values and the 2D transform includes a row transform and a column transform, said transform engine including:

row transform circuitry configured to generate a block of partially transformed data in response to each said input data block, by performing the row transform on each row of the input data block; and

column transform circuitry configured to perform the column transform on each column of the block of partially transformed data,

wherein the row transform circuitry is configured to determine, when performing the row transform on each said row, whether each of different subsets of the data values comprising a partition of the row includes at least one zero value, whether each of different subsets of a first subset of the partition of the row includes at least one zero value, and whether each of different subsets of at least one other subset of the partition of the row includes at least one zero value, and

the row transform circuitry is configured to bypass or perform in a reduced-power manner at least one transformation operation on at least one of the data values that is determined to be a zero value.

37. The system of claim 36, wherein the row transform circuitry is configured to bypass the at least one transformation operation on said at least one of the data values that is determined to be a zero value.

38. The system of claim 36, wherein the row transform circuitry is configured to perform in a reduced-power manner the at least one transformation operation on said at least one of the data values that is determined to be a zero value.

39. The system of claim 38, wherein the row transform circuitry includes at least one circuit having an input set, and the row transform circuitry is configured to perform the at least one transformation operation in the reduced-power manner by causing the circuit to operate without updating at least one input in said input set during the transformation operation on said one of the data values that is determined to be a zero value.

40. The system of claim 36, wherein the 2D transform is an inverse discrete cosine transform.

41. The system of claim 36, wherein the transform engine also includes:

a buffer coupled to the row transform circuitry and to the column transform circuitry, wherein the row transform circuitry is configured to store the block of partially transformed data in the buffer and the column transform circuitry is configured to retrieve columns of the block of partially transformed data from the buffer.

42. The system of claim 41, wherein the column transform circuitry is configured to determine, when performing the column transform on each said column, whether each of different subsets of the data values comprising a first partition of the column includes at least one zero value, whether each of different subsets of a first subset of the first partition of the column includes at least one zero value, and whether each of different subsets of at least one other subset of the first partition of the column includes at least one zero value, and

the column transform circuitry is configured to bypass at least one transformation operation on at least one of the data values that is determined to be a zero value.

43. The system of claim 42, wherein the column transform circuitry is configured to determine, when performing the column transform on each said column, whether each of different subsets of the data values comprising a first partition of the column includes at least one zero value, whether each of different subsets of a first subset of the first partition of the column includes at least one zero value, and whether each of different subsets of at least one other subset of the first partition of the column includes at least one zero value, and

the column transform circuitry is configured to perform in a reduced-power manner at least one transformation operation on at least one of the data values that is determined to be a zero value.

44. A video processing system, including a transform engine configured to perform a 2D transform on each input data block of a sequence of input data blocks, wherein each said input data block comprises rows and columns of input data values and the 2D transform includes a row transform and a column transform, said transform engine including:

column transform circuitry configured to generate a block of partially transformed data in response to each said input data block, by performing the column transform on each column of the input data block; and

row transform circuitry configured to perform the row transform on each row of the block of partially transformed data,

wherein the column transform circuitry is configured to determine, when performing the column transform on each said column, whether each of different subsets of the data values comprising a partition of the column includes at least one zero value, whether each of different subsets of a first subset of the partition of the column includes at least one zero value, and whether each of different subsets of at least one other subset of the partition of the column includes at least one zero value, and

the column transform circuitry is configured to bypass or perform in a reduced-power manner at least one transformation operation on at least one of the data values that is determined to be a zero value.

45. The system of claim 44, wherein the column transform circuitry is configured to bypass the at least one transformation operation on said at least one of the data values that is determined to be a zero value.

46. The system of claim 44, wherein the column transform circuitry is configured to perform in a reduced-power manner the at least one transformation operation on said at least one of the data values that is determined to be a zero value.

47. The system of claim 46, wherein the column transform circuitry includes at least one circuit having an input set, and the column transform circuitry is configured to perform the at least one transformation operation in the reduced-power manner by causing the circuit to operate without updating at least one input in said input set during the transformation operation on said one of the data values that is determined to be a zero value.

48. The system of claim 44, wherein the 2D transform is an inverse discrete cosine transform.

49. The system of claim 44, also including:

a buffer coupled to the row transform circuitry and to the column transform circuitry, wherein the column transform circuitry is configured to store the block of partially transformed data in the buffer and the row transform circuitry is configured to retrieve columns of the block of partially transformed data from the buffer.

50. A transform engine configured to perform a row transform of a 2D transform on each input data block of a sequence of input data blocks, wherein each said input data block comprises rows and columns of input data values and the 2D transform includes the row transform and a column transform, said transform engine including:

first circuitry coupled to receive each row of each said input data block and configured to determine whether each of different subsets of the data values comprising a partition of each said row includes at least one zero value, whether each of different subsets of a first one of the subsets of the partition of the row includes at least one zero value, and whether each of different subsets of at least one other one of the subsets of the partition of the row includes at least one zero value; and

transform circuitry coupled to the first circuitry and configured to perform the row transform on the data values of each said row, wherein the transform circuitry is configured to operate under control of the first circuitry to bypass or perform in a reduced-power manner at least one transformation operation on at least one of the data values that is determined by the first circuitry to be a zero value.

51. The transform engine of claim 50, wherein the transform circuitry is configured to bypass the at least one transformation operation on said at least one of the data values that is determined by the first circuitry to be a zero value.

52. The transform engine of claim 50, wherein the transform circuitry is configured to perform in a reduced-power manner the at least one transformation operation on said at least one of the data values that is determined by the first circuitry to be a zero value.

53. The transform engine of claim 50, wherein the 2D transform is an inverse discrete cosine transform.

54. A transform engine configured to perform a column transform of a 2D transform on each input data block of a sequence of input data blocks, wherein each said input data block comprises rows and columns of input data values and the 2D transform includes the column transform and a row transform, said transform engine including:

first circuitry coupled to receive each column of each said input data block and configured to determine whether each of different subsets of the data values comprising a partition of each said column includes at least one zero value, whether each of different subsets of a first one of the subsets of the partition of the column includes at least one zero value, and whether each of different subsets of at least one other one of the subsets of the partition of the column includes at least one zero value; and

transform circuitry coupled to the first circuitry and configured to perform the column transform on the data values of each said column, wherein the transform circuitry is configured to operate under control of the first circuitry to bypass or perform in a reduced-power manner at least one transformation operation on at least one of the data values that is determined by the first circuitry to be a zero value.

55. The transform engine of claim 54, wherein the transform circuitry is configured to bypass the at least one transformation operation on said at least one of the data values that is determined by the first circuitry to be a zero value.

56. The transform engine of claim 54, wherein the transform circuitry is configured to perform in a reduced-power manner the at least one transformation operation on said at least one of the data values that is determined by the first circuitry to be a zero value.

57. The transform engine of claim 54, wherein the 2D transform is an inverse discrete cosine transform.