Method and system for fast 90 degree rotation of arrays
First Claim
Patent Images
1. A computer-implemented method to rotate a 2N by 2N array in the counter-clockwise direction, the computer-implemented method comprising:
- loading 2N elements of each row of the array into vector registers of a SIMD unit;
interleaving the 2N elements of each row in the top half of the array with the 2N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array;
storing the results of the interleaving operation in vector registers;
repeating said loading and interleaving operations a total of N times, wherein a result of said loading and said interleaving is stored for further processing; and
after N loading and N interleaving operations, writing the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2N elements written to memory representing the bottom row of the rotated array.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and system to rotate a 2N by 2N array are described. Consistent with one embodiment of the present invention, the 2N elements of the 2N rows of a 2N by 2N array are loaded from memory into the vector registers of a processor'"'"'s single instruction multiple data (SIMD) unit. Next, the elements of the rows in the top half of the array are interleaved with corresponding elements from a corresponding row in the bottom half of the array. The loading and interleaving operations are repeated N times before the results, stored in the vector registers, are written back to memory.
-
Citations
30 Claims
-
1. A computer-implemented method to rotate a 2N by 2N array in the counter-clockwise direction, the computer-implemented method comprising:
-
loading 2N elements of each row of the array into vector registers of a SIMD unit; interleaving the 2N elements of each row in the top half of the array with the 2N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array; storing the results of the interleaving operation in vector registers; repeating said loading and interleaving operations a total of N times, wherein a result of said loading and said interleaving is stored for further processing; and after N loading and N interleaving operations, writing the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2N elements written to memory representing the bottom row of the rotated array. - View Dependent Claims (2, 3, 4)
-
-
5. A computer-implemented method to rotate a 2N by 2N array in the clockwise direction, the computer-implemented method comprising:
-
loading 2N elements of each row of the array into vector registers of a SIMD unit; interleaving the 2N elements of each row in the top half of the array with the 2N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array follows an element from a corresponding row in the bottom half of the array; storing the results of the interleaving operation in vector registers; repeating said loading and interleaving operations a total of N times, wherein a result of said loading and said interleaving is stored for further processing; and after N loading and N interleaving operations, writing the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2N elements written to memory representing the bottom row of the rotated array. - View Dependent Claims (6, 7, 8)
-
-
9. A computer-readable medium storing instructions, which, when executed, cause a computer to perform a method to rotate a 2N by 2N array in the counter-clockwise direction, the method comprising:
-
loading 2N elements of each row of the array into vector registers of a SIMD unit; interleaving the 2N elements of each row in the top half of the array with the 2N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array; storing the results of the interleaving operation in vector registers; repeating said loading and interleaving operations a total of N times, wherein a result of said loading and said interleaving is stored for further processing; and after N loading and N interleaving operations, writing the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2N elements written to memory representing the bottom row of the rotated array. - View Dependent Claims (10, 11, 12)
-
-
13. A computer-readable medium storing instructions, which, when executed, cause a computer to perform a method to rotate a 2N by 2N array in the clockwise direction, the method comprising:
-
loading 2N elements of each row of the array into vector registers of a SIMD unit; interleaving the 2N elements of each row in the top half of the array with the 2N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array follow an element from a corresponding row in the bottom half of the array; storing the results of the interleaving operation in vector registers; repeating said loading and interleaving operations a total of N times, wherein a result of said loading and said interleaving is stored for further processing; and after N loading and N interleaving operations, writing the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2N elements written to memory representing the bottom row of the rotated array. - View Dependent Claims (14, 15, 16)
-
-
17. An apparatus for rotating a 2N by 2N array in the counter-clockwise direction, the apparatus comprising:
-
a memory device to store the 2N by 2N array; a processor connected to the memory device, the processor including a SIMD unit having vector registers capable of storing and processing 2N elements, wherein the processor is to; load the 2N elements of each row into the vector registers of the SIMD unit; interleave the 2N elements of each row in the top half of the array with the 2N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array; store the results of the interleaving operation in vector registers; repeat said loading and interleaving operations a total of N times, wherein a result of said loading and said interleaving is stored for further processing; and after N loading and N interleaving operations, the processor to write the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2N elements written to memory representing the bottom row of the rotated array. - View Dependent Claims (18, 19, 20)
-
-
21. An apparatus for rotating a 2N by 2N array in the clockwise direction, the apparatus comprising:
-
a memory device to store the 2N by 2N array; a processor connected to the memory device, the processor including a SIMD unit having vector registers capable of storing and processing 2N elements, wherein the processor is to; load the 2N elements of each row into the vector registers of the SIMD unit; interleave the 2N elements of each row in the top half of the array with the 2N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array; store the results of the interleaving operation in vector registers; repeat said loading and interleaving operations a total of N times, wherein a result of said loading and said interleaving is stored for further processing; and after N loading and N interleaving operations, the processor to write the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2N elements written to memory representing the bottom row of the rotated array. - View Dependent Claims (22, 23, 24)
-
-
25. An apparatus for rotating a 2N by 2N array in the counter-clockwise direction, the apparatus comprising:
-
storage means to store the 2N by 2N array; and means to load the 2N by 2N array from said storage means into means to interleave the 2N elements of each row in the top half of the array with the 2N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array, wherein said means to interleave is to iteratively perform an interleave operation a total of N times, and wherein a result of said loading and said interleaving is stored for further processing; and after N loading and N interleaving operations, means to write the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2N elements written to memory representing the bottom row of the rotated array. - View Dependent Claims (26, 27)
-
-
28. An apparatus for rotating a 2N by 2N array in the clockwise direction, the apparatus comprising:
-
storage means to store the 2N by 2N array; and means to load the 2N by 2N array from said storage means into means to interleave the 2N elements of each row in the top half of the array with the 2N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array follows an element from a corresponding row in the bottom half of the array, wherein said means to interleave is to iteratively perform an interleave operation a total of N times, wherein a result of said loading and said interleaving is stored in a temporary storage means for further processing; and after N loading and N interleaving operations, means to write the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2N elements written to memory representing the bottom row of the rotated array. - View Dependent Claims (29, 30)
-
Specification