METHOD AND SYSTEM FOR IMPLEMENTING DATA MANIPULATION OPERATIONS

摘要

A method and system for performing arbitrary permutations of sequences of elements. In the general case, the method of the present invention processes the elements to be permuted as a multi-dimensional array, where each element in the array corresponds to one of the elments to be permuted. The permutation is achieved by performing a sequence of sets of permutations, where each set of permutations in the sequence independently permutes the elements within each one-dimensional slice through the array, along some particular dimension of the array. The total number of sets of permutations, or stages, is one less than twice the number of dimensions in the array. An extension to the general method allows some extensions of permutations which involve the copying of individual elements. A system based on the extended general method implements a large class of operations which involve copying and/or permuting elements, where the sequence of elements is a word of data and the elements are bits of data. An efficient control structure for the system permits control signals to be shared across slices of the array. A version of the system based on a two-dimensional array includes three multiplex stages, where the first stage multiplexes along the rows, the second stage multiplexes along the columns, and the third stage multiplexes across the rows once again. Several classes of computer instructions which generally involve the copying and/or permuting of data are also described.