Selectively transforming a multi-dimensional array

1. A method for selectively transforming a multi-dimensional input array comprising D dimensions, said method comprising:

segmenting said input array into a number of sub-arrays with a computing system;

determining a D-dimensional convolution of said input array at only selected points in each said sub-array, said convolution being a function of a product of D one-dimensional kernels;

determining partial convolutions at each dimension iteratively, an iterative determination of one of said partial convolutions being determined, in part, from a previous iterative determination;

collecting transformed sub-array values to form a transformed input array; and

storing said transformed input array.

2. The method of claim 1 , wherein each said partial convolution is determined at points (j 1 , j 2 , . . . , j i , u i+1 , . . . , u D ) where point j p varies from u p -ceiling(n p /2)+1 to u p -ceiling(n p /2)+n p , and n p represents the length of a one dimension kernel.

3. The method of claim 1 , wherein determining a D-dimensional convolution of said input array at only selected points in each said sub-array further comprises processing said selected points of each sub-array in a linear scan order.

4. The method of claim 1 , wherein determining a D-dimensional convolution of said input array at only selected points in each said sub-array further comprises storing values for each partial convolution in an associated convolution cache.

5. The method of claim 4 , wherein said associated convolution cache comprises a tag array and a data array, said data array having said partial convolution values stored therein, each cache line of said convolution cache comprising a tag value associated with a data value of said data array.

6. The method claim 5 , wherein determining partial convolutions at each dimension iteratively further comprises previously determining a cache access status.

7. The method of claim 6 , wherein determining said cache access status comprises:

determining a linear position of said given point from a coordinate set of said given point;

converting said linear position to a line position in said cache; and

comparing said tag value corresponding to said line position with said linear position of said given point.

8. The method of claim 7 , wherein said cache access status is set to “hit” if said tag value corresponding to said line position matches said linear position of said given point, and said cache access status is set to “miss” if said tag value corresponding to said line position does not match said linear position of said given point.

9. The method of claim 8 , wherein determining partial convolutions at each dimension iteratively further comprises retrieving the partial convolution value from the cache and processing a next point in said sub-array if said cache access status is set to “hit.”

10. The method claim 8 , wherein determining partial convolutions at each dimension iteratively further comprises computing said partial convolution at said given point if said cache access status is set to “miss.”

11. The method of claim 10 , wherein computing said partial convolution at said given point comprises accessing a cache associated with a previously computed partial convolution.

12. The method of claim 1 , wherein segmenting said input array into a number of sub-arrays comprises:

dividing said input array into chunks of data;

labelling said chunks linearly; and

allocating chunk frames in a processor cache for each chunk.

13. The method of claim 12 , wherein determining partial convolutions at each dimension iteratively comprises accessing chunk frames using said linear position of said given point.

14. A computing system for selectively transforming a multi-dimensional input array comprising D dimensions, the system comprising:

a memory; and

a processor, said processor comprising a cache;

in which said processor is configured to:

segment said input array into a number of sub-arrays with a computing system;

determine a D-dimensional convolution of said input array at only selected points in each said sub-array, said convolution being a function of a product of D one-dimensional kernels;

determine partial convolutions at each dimension iteratively, an iterative determination of one of said partial convolutions being determined, in part, from a previous iterative determination;

collect transformed sub-array values to form a transformed input array; and

store said transformed input array.

15. The system of claim 14 , wherein to determine a D-dimensional convolution of said input array at only selected points in each said sub-array, said processor is further configured to process said points of each sub-array in a linear scan order.

16. The system of claim 14 , wherein to determine a D-dimensional convolution of said input array at only selected points in each said sub-array, said processor is further configured to store values for each partial convolution in an associated convolution cache.

17. The system of claim 16 , wherein said associated convolution cache comprises a tag array and a data array, said data array having said partial convolution values stored therein, each cache line of said convolution cache comprising a tag value associated with a data value of said data array.

18. The system of claim 17 , wherein to determine partial convolutions at each dimension iteratively, said processor is further configured to previously determine a cache access status.

19. The system of claim 18 , wherein to determine said cache access status, said processor is further configured to:

determine a linear position of said given point from a coordinate set of said point;

convert said linear position to a line position in said cache; and

compare said tag value corresponding to said line position with said linear position of said given point.

20. A computer program product for selectively transforming a multi-dimensional input array comprising D dimensions, said computer program product comprising:

a computer readable storage medium having computer readable code embodied therewith, said computer readable program code comprising:

computer readable program code configured to segment said input array into a number of sub-arrays with a computing system;

computer readable program code configured to determine a D-dimensional convolution of said input array at only selected points in each said sub-array, said convolution being a function of a product of D one-dimensional kernels;

computer readable program code configured to determine partial convolutions at each dimension iteratively, an iterative determination of one of said partial convolutions being determined, in part, from a previous iterative determination;

computer readable program code configured to collect transformed sub-array values to form a transformed input array; and

computer readable program code configured to store said transformed input array.