Patent ID: 7979672

Claim:
A method of transposing a three-dimensional (3-D) data array for a multi-processor system having multiple processors and a main memory for storing the 3-D data array, the method comprising: logically dividing the 3-D data array into a number of equally sized consecutive 3-D first bar portions; determining distribution for each first 3-D bar portion evenly among a plurality of processors in the multi-processor system, and storing each first 3-D bar portion in a respective original storage location in the main memory; each of the plurality of processors, reading the respective first 3-D bar portion from the main memory to a local memory of the respective processor; logically dividing the first 3-D bar portion into multiple 3-D cube portions within the local memory of the respective processor, wherein the 3-D cube portions comprise plural data matrices including rows and columns; physically transposing elements of each 3-D cube portion by a sequence of interchanging of adjacent axes in a temporary storage location in the respective processor and storing the physically transposed cube elements in the local memory of the respective processor, wherein the 3-D cube portions remain in original physical storage locations with the elements of each 3-D cube portion physically transposed, then: combining the 3-D cube portions into a respective second 3-D bar portion in the local memory of the respective processor, wherein the second 3-D bar portion comprises a combined data matrix from the physically transposed matrices of the 3-D cube portions; and writing the respective second 3-D bar portions from the local memory of each respective processor to the respective original storage location in the main memory for which the respective first 3-D bar portion was originally stored; and obtaining elements of the transposed 3-D data array by logically transposing each 3-D cube portion via address mapping, wherein logically transposing includes: determining a 3-D cube address for a 3-D cube portion in the 3-D data array for a given element address; inverse transposing the 3-D cube address; determining a 3-D entry offset address within the 3-D cube portion; and accessing the given element within the 3-D cube portion directly without inversion using the determined 3-D entry offset address.