Patent ID: 7398484

Claim:
A method of creating a schedule for transposing an array structure of one or more dimensions in a hierarchical computer memory, the method comprising: constructing a first representation of the array structure comprising a plurality of dimensions, wherein respective count and stride values are associated with respective dimensions of the plurality of dimensions; permuting the representation according to a permutation; determining that the permuted representation describes a non-canonical-order layout; as a result of the determination, tiling the permuted representation based on one or more attributes of a target memory architecture, wherein tiling the permuted representation comprises: calculating for one of the plurality of dimensions of the first representation a largest count value compatible with a goal of memory efficiency; creating a second representation of the array structure and a third representation of the array structure; adding to the second representation a first new dimension comprising the largest count value and the respective stride value of the one of the plurality of dimensions; adding to the third representation a second new dimension comprising a new count value and a new stride value, wherein the new stride value is equivalent to a memory span of the first new dimension; repeating the above steps until the representation describes a desired rearrangement of the array structure; and emitting the tiled representation to the schedule for transposing an array structure of one or more dimensions in a hierarchical computer memory.