The present invention provides single-cycle instructions, which can be used to construct any type of permutations needed in two-dimensional (2-D) multimedia processing. The instructions can be used in a programmable processor, such as a digital signal processor, video signal processors, media processors, multimedia processors, cryptographic processors and programmable Systemon-a-Chips (SOCs).

The method and system provides a set of permutation primitives for current and future 2-D multimedia programs which are based on decomposing images and objects into atomic units, then finding the permutations desired for the atomic units. The subword permutation instructions for these 2-D building blocks are also defined for larger subword sizes at successively higher hierarchical levels. The atomic unit can be a 2×2 matrix and four triangles contained within the 2×2 matrix. Each of the elements in the matrix can represent a subword of one or more bits. The permutations provide vertical, horizontal, diagonal, rotational, and other rearrangements of the elements in the atomic unit.

The subword permutation primitives of the present invention include: CHECK, EXCHANGE, EXCHECK CCHECK, CEXCHANGE, CEXCHECK, CMIX and PERMSET instructions. The CHECK instruction provides downward and upward swapping of elements. The CCHECK instruction provides conditional downward and upward swapping of elements dependant on permutation control bits. The EXCHANGE instruction provides right and left movement. The CEXCHANGE instruction provides conditional right and left movement. The EXCHECK instruction provides rotation of triangles of the matrix. The CEXCHECK instruction provides conditional rotation of triangles. CMIX provides conditional selection of elements from two source registers in predetermined ways. The Permset instruction allows the permutation of a smaller set of subwords to be repeated on other subwords in the source register, enabling symmetric permutations to be specified on many more elements, without increasing the number of permutation control bits. EXCHANGE instruction is one example of the PERMSET instruction.

An initial alphabet (Alphabet A) of subword permutations is determined which comprises CMIX, PERMSET, CHECK and EXCHECK. Processors designed for high performance can implement Alphabet A, while very cost sensitive processors can choose to implement a smaller set of instructions in a minimal alphabet, such alphabet can include the CMIX and PERMSET instructions. The omitted instructions, CHECK and EXCHECK in Alphabet A, can be composed from CMIX and PERMSET. All the 24 permutations of a 2×2 matrix can be obtained using only instructions from Alphabet A, in a single cycle, in a processor with at least two permutation units.

The subword permutation primitives of the present invention enhance the use of subword parallelism by allowing in-place rearrangement of packed subwords across multiple registers, reducing the need for memory accesses with potentially costly cache misses. The alphabet of permutation primitives is easy to implement and is useful for 2-D multimedia processing and for other data-parallel computations using subword parallelism.