Abstract:
Many video processing applications, such as the decoding and encoding standards promulgated by the moving picture experts group (MPEG), are time constrained applications with multiple complex compute intensive algorithms such as the two-dimensional 8×8 IDCT. In addition, for encoding applications, cost, performance, and programming flexibility for algorithm optimizations are important design requirements. Consequently, it is of great advantage to meeting performance requirements to have a programmable processor that can achieve extremely high performance on the 2D 8×8 IDCT function. The ManArray 2×2 processor is able to process the 2D 8×8 IDCT in 34-cycles and meet the IEEE standard 1180-1990 for precision of the IDCT. A unique distributed 2D 8×8 IDCT process is presented along with the unique data placement supporting the high performance algorithm. In addition, a scalable 2D 8×8 IDCT algorithm that is operable on a 1×0, 1×1, 1×2, 2×2, 2×3, and further arrays of greater numbers of processors is presented that minimizes the VIM memory size by reuse of VLIWs and streamlines further application processing by having the IDCT results output in a standard row-major order. The techniques are applicable to cosine transforms more generally, such as discrete cosine transforms (DCTs).

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     The present application claims the benefit of U.S. Provisional Application Serial No. 60/165,337 entitled “Methods and Apparatus for Efficient Cosine Transform Implementations” filed Nov. 12, 1999 which is herein incorporated by reference in its entirety. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates generally to improvements in parallel processing, and more particularly to methods and apparatus for efficient cosine transform implementations on the manifold array (“ManArray”) processing architecture. 
     BACKGROUND OF THE INVENTION 
     Many video processing applications, such as the moving picture experts group (MPEG) decoding and encoding standards, use a discrete cosine transform (DCT) and its inverse, the indirect discrete cosine transform (IDCT), in their compression algorithms. The compression standards are typically complex and specify that a high data rate must be handled. For example, MPEG at Main Profile and Main Level specifies 720×576 picture elements (pels) per frame at 30 frames per second and up to 15 Mbits per second. The MPEG Main Profile at High Level specifies 1920×1152 pels per frame at 60 frames per second and up to 80 Mbits per second. Video processing is a time constrained application with multiple complex compute intensive algorithms such as the two dimensional (2D) 8×8 IDCT. The consequence is that processors with high clock rates, fixed function application specific integrated circuits (ASICs), or combinations of fast processors and ASICs are typically used to meet the high processing load. Having efficient 2D 8×8 DCT and IDCT implementations is of great advantage to providing a low cost solution. 
     Prior art approaches, such as Pechanek et al. U.S. Pat. No. 5,546,336, used a specialized folded memory array with embedded arithmetic elements to achieve high performance with 16 processing elements. The folded memory array and large number of processing elements do not map well to a low cost regular silicon implementation. It will be shown in the present invention that high performance cosine transforms can be achieved with one quarter of the processing elements as compared to the 16 PE Mfast design in a regular array structure without need of a folded memory array. In addition, the unique instructions, indirect VLIW capability, and use of the ManArray network communication instructions allow a general programmable solution of very high performance. 
     SUMMARY OF THE INVENTION 
     To this end, the ManArray processor as adapted as further described herein provides efficient software implementations of the IDCT using the ManArray indirect very long instruction word (iVLIW) architecture and a unique data-placement that supports software pipelining between processor elements (PEs) in the 2×2 ManArray processor. For example, a two-dimensional (2D) 8×8 IDCT, used in many video compression algorithms such as MPEG, can be processed in 34-cycles on a 2×2 ManArray processor and meets IEEE Standard 1180-1990 for precision of the IDCT. The 2D 8×8 DCT algorithm, using the same distributed principles covered in the distributed 2D 8×8 IDCT, can be processed in 35-cycles on the same 2×2 ManArray processor. With this level of performance, the clock rate can be much lower than is typically used in MPEG processing chips thereby lowering overall power usage. 
     An alternative software process for implementing the cosine transforms on the ManArray processor provides a scalable algorithm that can be executed on various arrays, such as a 1×1, a 1×2, a 2×2, a 2×3, a 2×4, and so on allowing scalable performance. Among its other aspects, this new software process makes use of the scalable characteristics of the ManArray architecture, unique ManArray instructions, and a data placement optimized for the MPEG application. In addition, due to the symmetry of the algorithm, the number of VLIWs is minimized through reuse of VLIWs in the processing of both dimensions of the 2D computation. 
     The present invention defines a collection of eight hardware ManArray instructions that use the ManArray iVLIW architecture and communications network to efficiently calculate the distributed two-dimensional 8×8 IDCT. In one aspect of the present invention, appropriate data distribution and software pipeline techniques are provided to achieve a 34-cycle distributed two-dimensional 8×8 IDCT on a 2×2 ManArray processor that meets IEEE Standard 1180-1990 for precision of the IDCT. In another aspect of the present invention, appropriate data distribution patterns are used in local processor element memory in conjunction with a scalable algorithm to effectively and efficiently reuse VLIW instructions in the processing of both dimensions of the two dimensional algorithm. 
    
    
     These and other advantages of the present invention will be apparent from the drawings and the Detailed Description which follow. 
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates an exemplary 2×2 ManArray iVLIW processor; 
     FIG. 2 illustrates an IDCT signal flow graph; 
     FIG. 3A illustrates input data in 8×8 matrix form; 
     FIG. 3B illustrates reordered input 8×8 data matrix per the signal flow graph of FIG. 2; 
     FIG. 3C illustrates the input 8×8 data matrix after it has been folded on the vertical axis; 
     FIG. 3D illustrates the input 8×8 data matrix after it has been folded on the horizontal axis with data placement per PE in the 2×2 ManArray iVLIW processor of FIG. 1; 
     FIG. 3E illustrates an example of data placement into the ManArray PE compute register files; 
     FIG. 4 illustrates the data of FIG. 3D as loaded into the four PEs&#39; registers; 
     FIG. 5A illustrates a presently preferred execute VLIW instruction, XV; 
     FIG. 5B illustrates the syntax and operation of the XV instruction of FIG. 5A; 
     FIG. 6A illustrates a presently preferred sum of two products instruction, SUM2P; 
     FIG. 6B illustrates the syntax and operation of the SUM2P instruction of FIG. 6A; 
     FIG. 7A illustrates a presently preferred sum of two products accumulate instruction, SUM2PA; 
     FIG. 7B illustrates the syntax and operation of the SUM2PA instruction of FIG. 7A; 
     FIG. 8A illustrates a presently preferred butterfly with saturate instruction, BFLYS; 
     FIG. 8B illustrates the syntax and operation of the BFLYS instruction of FIG. 8A; 
     FIG. 9A illustrates a presently preferred addition instruction, ADD; 
     FIG. 9B illustrates the syntax and operation of the ADD instruction of FIG. 9A; 
     FIG. 10A illustrates a presently preferred permute instruction, PERM; 
     FIG. 10B illustrates the syntax and operation of the PERM instruction of FIG. 10A; 
     FIG. 10C illustrates one example of an 8-byte to 4-byte permute operation; 
     FIG. 10D illustrates another example of an 8-byte to 4-byte permute operation; 
     FIG. 10E illustrates one example of an 8-byte to 8-byte permute operation; 
     FIG. 11A illustrates a presently preferred PE to PE exchange instruction, PEXCHG; 
     FIG. 11B illustrates the syntax and operation of the PEXCHG instruction of FIG. 11A; 
     FIG. 11C illustrates a 2×2 cluster switch arrangement showing PE and cluster switch notation; 
     FIG. 11D illustrates a key to PEXCHG 2×2 Operation Table with an example path highlighted; 
     FIG. 11E illustrates the PEXCHG 1×1 Operation Table; 
     FIG. 11F illustrates the PEXCHG 1×2 Operation Table; 
     FIG. 11G illustrates the PEXCHG 2×2 Operation Table; 
     FIG. 11H illustrates a 2×2 PEXCHG operation; 
     FIG. 12A illustrates a presently preferred load modulo indexed with scaled update instruction, LMX; 
     FIG. 12B illustrates the syntax and operation of the LMX instruction of FIG. 12A; 
     FIG. 13A illustrates the first 18-cycles of ManArray 8×8 2D IDCT program code and the VLIWs associated with each XV program instruction; and 
     FIG. 13B illustrates cycles  19 - 34  of the ManArray 8×8 2D IDCT program code; 
     FIG. 14 illustrates an 8×8 input data matrix; 
     FIG. 15 illustrates the intermediate 8×8 results after processing the first dimension of the 8×8 IDCT algorithm; 
     FIG. 16 illustrates the 8×8 output pixel results after processing of both dimensions of the 8×8 IDCT algorithm; 
     FIG. 17 illustrates a 1×8 IDCT algorithm in VLIW coding format; 
     FIGS. 18A-M illustrate 2D 8×8 IDCT ManArray code; 
     FIG. 19A illustrates a load indirect with scaled immediate update instruction, LII; 
     FIG. 19B illustrates the syntax and operation of the LII instruction of FIG. 19A; 
     FIG. 20A illustrates a subtract instruction, SUB; 
     FIG. 20B illustrates the syntax and operation of the SUB instruction of FIG. 20A; 
     FIG. 21A illustrates a shift right immediate instruction, SHRI; 
     FIG. 21B illustrates the syntax and operation of the SHRI instruction of FIG. 21A; 
     FIG. 22A illustrates a store indirect with scaled immediate update instruction, SII; 
     FIG. 22B illustrates the syntax and operation of the SII instruction of FIG. 22A; 
     FIG. 23 illustrates exemplary 2D 8×8 IDCT code showing the software pipeline operation; and 
     FIG. 24 illustrates an exemplary process for a 2×2 DCT. 
    
    
     DETAILED DESCRIPTION 
     Further details of a presently preferred ManArray architecture for use in conjunction with the present invention are found in 
     U.S. patent application Ser. No. 08/885,310 filed Jun. 30, 1997, now U.S. Pat. No. 6,023,753, 
     U.S. patent application Ser. No. 08/949,122 filed Oct. 10, 1997, now U.S. Pat. No. 6,167,502, 
     U.S. patent application Ser. No. 09/169,255 filed Oct. 9, 1998, now U.S. Pat. No. 6,343,356, 
     U.S. patent application Ser. No. 09/169,256 filed Oct. 9, 1998, now U.S. Pat. No. 6,167,501, 
     U.S. patent application Ser. No. 09/169,072, filed Oct. 9, 1998, now U.S. Pat. No. 6,219,776, 
     U.S. patent application Ser. No. 09/187,539 filed Nov. 6, 1998, now U.S. Pat. No. 6,151,668, 
     U.S. patent application Ser. No. 09/205,588 filed Dec. 4, 1998, now U.S. Pat. No. 6,173,389, 
     U.S. patent application Ser. No. 09/215,081 filed Dec. 18, 1998, now U.S. Pat. No. 6,101,592, 
     U.S. patent application Ser. No. 09/228,374 filed Jan. 12, 1999 now U.S. Pat. No. 6,216,223, 
     U.S. patent application Ser. No. 09/238,446 filed Jan. 28, 1999, now U.S. Pat. No. 6,366,999, 
     U.S. patent application Ser. No. 09/267,570 filed Mar. 12, 1999, now U.S. Pat. No. 6,446,190, 
     U.S. patent application Ser. No. 09/350,191 filed Jul. 9, 1999, now U.S. Pat. No. 6,356,994, 
     U.S. patent application Ser. No. 09/422,015 filed Oct. 21, 1999 now U.S. Pat. No. 6,408,382, 
     U.S. patent application Ser. No. 09/432,705 filed Nov. 2, 1999 entitled “Methods and Apparatus for Improved Motion Estimation for Video Encoding”, 
     U.S. patent application Ser. No. 09/471,217 filed Dec. 23, 1999 entitled “Methods and Apparatus for Providing Data Transfer Control”, 
     U.S. patent application Ser. No. 09/472,372 filed Dec. 23, 1999, now U.S. Pat. No. 6,256,683, 
     U.S. patent application Ser. No. 09/596,103 filed Jun. 16, 2000, now U.S. Pat. No. 6,397,324, 
     U.S. patent application Ser. No. 09/598,567 entitled “Methods and Apparatus for Improved Efficiency in Pipeline Simulation and Emulation” filed Jun. 21, 2000, 
     U.S. patent application Ser. No. 09/598,564 filed Jun. 21, 2000, now U.S. Pat. No. 6,622,238, 
     U.S. patent application Ser. No. 09/598,566 entitled “Methods and Apparatus for Generalized Event Detection and Action Specification in a Processor” filed Jun. 21, 2000, 
     and U.S. patent application Ser. No. 09/599,980 entitled “Methods and Apparatus for Parallel Processing Utilizing a Manifold Array (ManArray) Architecture and Instruction Syntax” filed Jun. 2, 2000, as well as, 
     Provisional Application Serial No. 60/113,637 entitled “Methods and Apparatus for Providing Direct Memory Access (DMA) Engine” filed Dec. 23, 1998, 
     Provisional Application Serial No. 60/113,555 entitled “Methods and Apparatus Providing Transfer Control” filed Dec. 23, 1998, 
     Provisional Application Serial No. 60/139,946 entitled “Methods and Apparatus for Data Dependent Address Operations and Efficient Variable Length Code Decoding in a VLIW Processor” filed Jun. 18, 1999, 
     Provisional Application Serial No. 60/140,245 entitled “Methods and Apparatus for Generalized Event Detection and Action Specification in a Processor” filed Jun. 21, 1999, 
     Provisional Application Serial No. 60/140,163 entitled “Methods and Apparatus for Improved Efficiency in Pipeline Simulation and Emulation” filed Jun. 21, 1999, 
     Provisional Application Serial No. 60/140,162 entitled “Methods and Apparatus for Initiating and Re-Synchronizing Multi-Cycle SIMD Instructions” filed Jun. 21, 1999, 
     Provisional Application Serial No. 60/140,244 entitled “Methods and Apparatus for Providing One-By-One Manifold Array (1×1 ManArray) Program Context Control” filed Jun. 21, 1999, 
     Provisional Application Serial No. 60/140,325 entitled “Methods and Apparatus for Establishing Port Priority Function in a VLIW Processor” filed Jun. 21, 1999, 
     Provisional Application Serial No. 60/140,425 entitled “Methods and Apparatus for Parallel Processing Utilizing a Manifold Array (ManArray) Architecture and Instruction Syntax” filed Jun. 22, 1999, 
     Provisional Application Serial No. 60/165,337 entitled “Efficient Cosine Transform Implementations on the ManArray Architecture” filed Nov. 12, 1999, and 
     Provisional Application Serial No. 60/171,911 entitled “Methods and Apparatus for DMA Loading of Very Long Instruction Word Memory” filed Dec. 23, 1999, 
     Provisional Application Serial No. 60/184,668 entitled “Methods and Apparatus for Providing Bit-Reversal and Multicast Functions Utilizing DMA Controller” filed Feb. 24, 2000, 
     Provisional Application Serial No. 60/184,529 entitled “Methods and Apparatus for Scalable Array Processor Interrupt Detection and Response” filed Feb. 24, 2000, 
     Provisional Application Serial No. 60/184,560 entitled “Methods and Apparatus for Flexible Strength Coprocessing Interface” filed Feb. 24, 2000, Provisional Application Serial No. 60/203,629 entitled “Methods and Apparatus for Power Control in a Scalable Array of Processor Elements” filed May 12, 2000, respectively, all of which are assigned to the assignee of the present invention and incorporated by reference herein in their entirety. 
     In a presently preferred embodiment of the present invention, a ManArray 2×2 iVLIW single instruction multiple data stream (SIMD) processor  100  shown in FIG. 1 comprises a sequence processor (SP) controller combined with a processing element- 0  (PE 0 ) SP/PE 0   101 , as described in further detail in U.S. patent application Ser. No. 09/169,072 entitled “Methods and Apparatus for Dynamically Merging an Array Controller with an Array Processing Element”. Three additional PEs  151 ,  153 , and  155 , are also utilized to demonstrate the efficient algorithm and mechanisms for fast cosine transforms on the ManArray architecture in accordance with the present invention. It is noted that PEs can also be labeled with their matrix positions as shown in parenthesis for PE 0  (PE 00 )  101 , PE 1  (PE 01 )  151 , PE 2  (PE 10 )  153 , and PE 3  (PE 11 )  155 . The SP/PE 0   101  contains the fetch controller  103  to allow the fetching of short instruction words (SIWs) from a 32-bit instruction memory  105 . The fetch controller  103  provides the typical functions needed in a programmable processor such as a program counter (PC), branch capability, event point (EP) loop operations (see U.S. application Ser. No. 09/598,556 entitled “Methods and Apparatus for Generalized Event Detection and Action Specification in a Processor” filed Jun. 21, 2000 and claiming the benefit of U.S. Provisional Application Serial No. 60/140,245 for further details), and support for interrupts. It also provides the instruction memory control which could include an instruction cache if needed by an application. In addition, the SIW I-Fetch controller  103  dispatches 32-bit SIWs to the other PEs in the system by means of the 32-bit instruction bus  102 . 
     In this exemplary system, common elements are used throughout to simplify the explanation, though actual implementations are not limited to this restriction. For example, the execution units  131  in the combined SP/PE 0   101  can be separated into a set of execution units optimized for the control function, e.g., fixed point execution units, and the PE 0  as well as the other PEs can be optimized for a floating point application. For the purposes of this description, it is assumed that the execution units  131  are of the same type in the SP/PE 0  and the PEs. In a similar manner, SP/PE 0  and the other PEs use a five instruction slot iVLIW architecture which contains a very long instruction word memory (VIM)  109  and an instruction decode and VIM controller function unit  107  which receives instructions as dispatched from the SP/PE 0 &#39;s I-Fetch unit  103  and generates the VIM addresses-and-control signals  108  required to access the iVLIWs stored in VIM. Referenced instruction types are identified by the letters SLAMD in VIM  109 , where the letters are matched up with instruction types as follows: Store (S), Load (L), ALU (A), MAU (M), and DSU (D). The basic concept of loading of the iVLIWs is described in greater detail in U.S. patent application Ser. No. 09/187,539 entitled “Methods and Apparatus for Efficient Synchronous MIMD Operations with iVLIW PE-to-PE Communication”. Also contained in the SP/PE 0  and the other PEs is a common PE configurable register file  127  which is described in further detail in U.S. patent application Ser. No. 09/169,255 entitled “Methods and Apparatus for Dynamic Instruction Controlled Reconfiguration Register File with Extended Precision”. 
     Due to the combined nature of the SP/PE 0 , the data memory interface controller  125  must handle the data processing needs of both the SP controller, with SP data in memory  121 , and PE 0 , with PE 0  data in memory  123 . The SP/PE 0  controller  125  also is the controlling point of the data that is sent over the  32 -bit broadcast data bus  126 . The other PEs,  151 ,  153 , and  155  contain common physical data memory units  123 ′,  123 ″, and  123 ′″ though the data stored in them is generally different as required by the local processing done on each PE. The interface to these PE data memories is also a common design in PEs  1 ,  2 , and  3  and indicated by PE local memory and data bus interface logic  157 ,  157 ′ and  157 ″. Interconnecting the PEs for data transfer communications is the cluster switch  171  various aspects of which are described in greater detail in U.S. patent application Ser. No. 08/885,310 entitled “Manifold Array Processor”, U.S. application Ser. No. 09/949,122 entitled “Methods and Apparatus for Manifold Array Processing”, and U.S. application Ser. No. 09/169,256 entitled “Methods and Apparatus for ManArray PE-to-PE Switch Control”. The interface to a host processor, other peripheral devices, and/or external memory can be done in many ways. For completeness, a primary interface mechanism is contained in a direct memory access (DMA) control unit  181  that provides a scalable ManArray data bus  183  that connects to devices and interface units external to the ManArray core. The DMA control unit  181  provides the data flow and bus arbitration mechanisms needed for these external devices to interface to the ManArray core memories via the multiplexed bus interface symbolically represented by  185 . A high level view of the ManArray Control Bus (MCB)  191  is also shown in FIG.  1 . 
     All of the above noted patents are assigned to the assignee of the present invention and incorporated herein by reference in their entirety. 
     Inverse Discrete Cosine Transform          p                   (     x   ,   y     )       =       ∑     u   =   0     7                       ∑     v   =   0     7                         C                   (   u   )       2                       C                   (   v   )       2                   f                   (     u   ,   v     )                     cos        [       (       2      x     +   1     )                   u                   π   16       ]                       cos        [       (       2      y     +   1     )                   v                   π   16       ]                                    
     The 2D 8×8 IDCT equation is given as: 
     
       
         Where:  C ( u )=1/{square root over (2)} for  u =0 
       
     
     
       
           C ( u )=1 for  u &gt;0 
       
     
     
       
           C ( v )=1/{square root over (2)} for  v =0 
       
     
     
       
           C ( v )=1 for  v &gt;0 
       
     
     
       
           f ( u,v )=2D DCT coefficient 
       
     
     
       
           p ( x,y )=2D result value 
       
     
     This 2D 8×8 IDCT matrix can be separated into 1D 1×8 IDCTs on the rows and columns. The ManArray 2D 8×8 IDCT uses this property and applies the following 1D 1×8 IDCT on all eight rows (columns) followed by applying it to all eight columns (rows).          p                   (   x   )       =       ∑     u   =   0     7                         C                   (   u   )       2                   f                   (   u   )                     cos        [       (       2      x     +   1     )                   u                   π   16       ]                                  
     Where:          C                   (   u   )       =         1   /     2          ⋮                 for                 u     =   0               C                   (   u   )       =       1                 for                 u     &gt;   0               F                   (   u   )       =     1      D                 DCT                 coefficient               P                   (   x   )       =     1      D                 result                 value                            
     The calculation of the 2D 8×8 IDCT in 34-cycles does not include the loading of data into the processing elements of the array since the equation does not account for a data loading function and there are many methods to accomplish the data loading such as direct memory access (DMA) and other means as dictated by the application program. For example, in an MPEG decoders compressed encoded data is received and sequentially preprocessed by variable length decoding, run length and inverse scan steps and then placed in the PEs after which the data is further processed by an inverse quantization step prior to using the IDCT processing step. This IDCT algorithm can also be used in an MPEG encoder and other applications requiring an IDCT function. 
     For the fast IDCT ManArray 2×2 approach of the present invention, the data is uniquely placed in the four PEs based upon symmetric properties of the IDCT signal flow graph as shown in FIG.  2 . The present approach separates the 2-dimensional 8×8 IDCT into 1-dimensional 1×8 IDCTs on the rows and then on the columns. The symmetric form of the 1×8 IDCT was used in a prior art processor further described in a paper “M.F.A.S.T.: A Highly Parallel Single Chip DSP with a 2D IDCT Example”, by G. Pechanek, C. W. Kurak., C. J. Glossner, C. H. L. Moller, and S. J. Walsh. The approach described in the M.F.A.S.T. article required a special folding of the data on the diagonal of the data matrix to determine the data placement for the diagonally folded 4×4 M.F.A.S.T. array of 16-processing elements to accomplish the 2D 8×8 IDCT processing in 18-22 cycles. The present invention describes a 2D 8×8 IDCT algorithm on a 4-processing element array in 34-cycles, a performance that is less than twice the processing time with only one quarter of the processing elements as compared to the M.F.A.S.T. processor. In addition, no special folding of the data matrix on the diagonal is required. The present ManArray™ approach uses a data placement that matches the signal flow graph directly. 
     FIG. 2 illustrates a signal flow graph  200  for a symmetric 1×8 IDCT operation in accordance with the present invention in which the input data elements are row elements given as f zj  where z={0,1, . . . ,7}=row identifier and j={0,1, . . . ,7}=column identifier. The 1×8 IDCT is composed of a sum of products stage-1  210  and a butterfly stage-2  220 . The stage-1 operation consists of 32 multiply operations indicated by the input being multiplied (*) by cosine coefficients indicated by a “pc#” where p indicates a positive value or “mc#” where m indicates a negative value. Groups of four multiplied values are then summed as indicated in the signal flow graph by the eight 4-input adders  211 - 218 . The sum of product results are identified by the letters A-H. These values are then processed by butterfly operations in stage  220  to generate the output values P zj  where z={0,1, . . . ,7}=row identifier and j={0,1, . . . ,7}=column identifier. This 1×8 IDCT operation is performed on each row of the 8×8 input data followed by the 1×8 IDCT operation on each column to form the final two-dimensional result. 
     The input data is shown in FIG. 3A in a row-major matrix  300  where in an MPEG decoder each element represents a DCT coefficient as processed through the variable length decoder. The data types are assumed to be greater than 8-bits at this stage and for ManArray processing 16-bit data types are used for each element. The data elements are identified in both a linear numeric ordering from M 0  to M 63 , and a row and column matrix form corresponding to the input notation used in the signal flow graph  200  of FIG.  2 . The data is to be distributed to the PEs of the 2×2 ManArray processor  100  appropriately to allow fast execution as a distributed 2D 8×8 IDCT. Consequently, the data should be distributed among the four PEs to minimize communication operations between the PEs. To discover an appropriate data distribution pattern, it is noted that the input data of the FIG. 2 signal flow graph separates the even data elements from the odd data elements. This even and odd arrangement  310  of the data is shown graphically in FIG. 3B where the rows and columns are ordered in the same even and odd arrangement used in FIG.  2 . 
     It is next noted that the second stage  220  of the signal flow graph  200  of FIG. 2 is a butterfly operation. For example, P z,1 =B+G while P z,6 =B−G. The butterfly processing requires A and H, B and G, C and F, D and E values to be located locally on a PE. This is equivalent to folding the signal flow graph and is further equivalent to folding the input data matrix. Since the 2D 8×8 IDCT operation first operates on the rows (columns) and then the columns (rows), two folds on two different axis must be accounted for. A vertical axis data fold  320  is illustrated in FIG. 3C, while FIG. 3D shows data  330  corresponding to the data of FIG. 3C folded again on the horizontal axis. FIG. 3D further shows how the data would be assigned to the 4 PEs, PE 0 -PE 3 , of the 2×2 ManArray processor  100  of FIG.  1 . There are a number of ways the data can be loaded into the PEs. For example, in an MPEG decoder, the output of the variable length decoder (VLD) could be in a linear order of 64 packed halfword data elements, two DCT coefficients per word. This packed format is organized to match the packed format required in the IDCT step. The data is then loaded via DMA operation or by using ManArray load instructions. The data is loaded into the PE configurable compute register file which is used in a 16×64 configuration for high performance packed data operations. Such a data placement  340  is shown in FIG. 3E for each PE and the registers chosen for this description. Within each PE, the even-indexed 16-bit data values are placed together in a compute register file (CRF) high halfword (H 1 ) and low halfword (H 0 ) 32-bit register, for example, register blocks  350  and  352  of FIG.  3 E. In the same manner, the odd-indexed 16-bit data values are placed together in a CRF high halfword (H 1 ) and low halfword (H 0 ) 32-bit register, for example, register blocks  360  and  362  of FIG.  3 E. This data placement supports the signal flow graph of FIG. 2 where the even-indexed input values and odd-indexed input values provide two independent sets of inputs for the sum of product operations. For example, the four sum of product values A, B, C and D are generated from only the even-indexed input values. The register data placement of FIG. 3E is shown in a compute register file format  400  in FIG.  4 . It is noted that a number of different register choices are possible while still achieving the same performance and using the same processing approach. It is further noted that different data orderings that allow the same efficient sum of four products operation are also possible while still achieving the same performance and using the inventive approach. 
     In a presently preferred embodiment, the strategy for processing the IDCT algorithm is implemented using a number of features of the ManArray processor to provide a unique software pipeline employing indirect VLIWs operating in multiple PEs. For example, the indirect execute VLIW (XV) instruction  500  shown in FIG. 5A has a unique enable feature, E=SLAMD specified in bits  14 - 10 , which allows a software pipeline to be built up or torn down without creating new VLIWs. A syntax/operation table  510  for the XV instruction  500  is shown in FIG.  5 B. 
     Quad 16×16 multiplications are used in the sum of two products with and without accumulate instructions to produce two 32-bit results. These instructions  600  and  700  are shown in FIGS. 6A and 7A. Their syntax/operation tables  610  and  710  are shown in FIGS. 6B and 7B. The use of common instructions that can execute in either the ALU or MAU or both, for example the butterfly with saturate instruction  800  of FIG. 8, improves performance. A syntax/operation table  810  for BFLYS instruction  800  is shown in FIG.  8 B. Other instructions common to the MAU and ALU include ADD instruction  900  of FIG. 9A having syntax/operation table  910  of FIG. 9B, add immediate (ADDI), add with saturate (ADDS), butterfly divide by 2 (BFLYD2), butterfly with saturate (BFLYS), the mean of two numbers (MEAN 2 ), subtract (SUB), subtract immediate (SUBI), and subtract with saturate (SUBS). In addition, the DSU supports permute instructions  1000  (PERM) of FIG. 10A having syntax/operation  1010  of FIG. 10B to aid in organizing the data prior to processing and communicating between PEs by use of the PEXCHG instruction  1100  of FIG. 11A having syntax/operation table  1110  of FIG.  11 B. The PEXCHG instruction  1100  used in the IDCT algorithm swaps two data items between two PEs. The loading of the cosine coefficients is accomplished with a load modulo indexed with scaled update instruction  1200  (LMX) of FIG. 12 having syntax/operation table  1210  of FIG.  12 B. 
     As addressed further below, additional aspects of the present invention are illustrated in FIGS. 10C-10E and FIGS. 11C-11H as follows. FIG. 10C illustrates one example of an 8-byte to 4-byte permute operation  1020 . FIG. 10D illustrates another example of an 8-byte to 4-byte permute operation  1030 . FIG. 10E illustrates an example of an 8-byte to 8-byte permute operation  1040 . FIG. 11C illustrates a 2×2 cluster switch arrangement  1130  showing PE and cluster switch notation. FIG. 11D illustrates a key to PEXCHG 2×2 operation table  1140 . FIGS. 11E-11G illustrates PEXCHG 1×1, 1×2 and 2×2 operation tables,  1160 ,  1170  and  1180 , respectively. FIG. 11H illustrates a 2×2 PEXCHG operation  1150 . 
     Prior to beginning the IDCT process, the frequency or DCT coefficient data and the first set of cosine coefficients are loaded onto the four PEs, some pointers and control values are initialized, and a rounding bit is used to enhance the precision of the results is loaded. The IDCT signal flow graph  200  for each row (column), FIG. 2, begins with a sum of products operation consisting of thirty-two 16×16 multiplications and twenty-four 2-to-1 32-bit additions for each row (column) processed. The ManArray IDCT algorithm maintains maximum precision through the sum-of-products operation. The second stage of the ID IDCT signal flow graph for each of the eight rows (columns) of processing illustrated in FIG. 2 uses four butterfly operations where each butterfly operation consists of a separate add and subtract on 16-bit data. At this point in the ManArray IDCT process, the most significant 16-bits of the 32-bit sum-of-product data are operated on producing the final 1×8 IDCT results in 16-bit form. A total of 32 butterfly operations are required for the eight rows (columns) which is accomplished in four cycles on the 2×2 array using the BFLYS instruction since its execution produces two butterfly operations per PE. Many of these butterfly operations are overlapped by use of VLIWs with other IDCT computation to improve performance. The 1×8 IDCT operations are now repeated on the columns (rows) to complete the 2D 8×8 IDCT. The load unit (LU) is also busy supporting the IDCT computations by loading the appropriate data cycle by cycle. 
     To provide further details of these operations, the 8×8 2D IDCT program  1300  shown in FIGS. 13A and 13B is discussed below. The first column  1305  labeled Clk indicates the program instruction execution cycle counts. FIG. 13A depicts steps or cycles  1 - 18  for the program  1300  and FIG. 13B depicts steps or cycles  19 - 34  of that program. These illustrated steps are made up primarily of 32-bit XV instructions listed under the column  1310  titled 8×8 2D IDCT program. For VLIW slot instructions, such as instruction  1341  in column  1340  of FIG. 13A or instruction  1342  in column  1340  of FIG. 13B, the instructions are struck out or crossed through. In these instances, the instructions shown are located in VLIW memory, but are not enabled by the E=parameter of the XV instruction that selects that VLIW for execution. Column  1310  lists the actual program stored in 32-bit instruction memory. The VLIWs which the XVs indirectly selected for execution are stored in the local PE VIMs. The other columns  1320 ,  1330 ,  1340 ,  1350  and  1360  represent the SLAMD VLIWs that are indirectly executed with each XV instruction. The XV syntax  510  of FIG.  5 B and used in column  1310  of FIGS. 13A and 13B is as follows: XV is the base mnemonic, p indicates this is a PE instruction, V 0  selects the V 0  VIM base address register, # represents the VIM offset value added to V 0  to create the VIM VLIW address, the E=SLAMD indicates which execution units are enabled for that execution cycle, and F=AMD indicates the unit affecting flags selection option. Note that with the E=SLAMD option VLIWs can sometimes be reused as in this IDCT algorithm where the first six XVs Clk=1, 2, . . . 6 are repeated in XVs Clk=9, 10, . . . 14 respectively and differ in use by appropriate choice of the E=enabled unit. For the anticipated use of this ManArray IDCT algorithm, no store operations are required and all store units have a no operation (nop) indicated in each VLIW. 
     The instructions used in the program are described in further detail as follows: 
     The XV instruction  500  is used to execute an indirect VLIW (iVLIW). The iVLIWs that are available for execution by the XV instruction are stored at individual addresses of the specified SP or PE VLIW memory (VIM). The VIM address is computed as the sum of a base VIM address register Vb (V 0  or V 1 ) plus an unsigned 8-bit offset VIMOFFS. The VIM address must be in the valid range for the hardware configuration otherwise the operation of this instruction is undefined. Any combination of individual instruction slots may be executed via the execute slot parameter ‘E={SLAMD}’, where S=store unit (SU), L=load unit (LU), A=arithmetic logic unit (ALU), M=multiply accumulate unit (MAU), D=data select unit (DSU). A blank ‘E=’ parameter does not execute any slots. The unit affecting flags (UAF) parameter ‘F=[AMDN]’ overrides the UAF specified for the VLIW when it was loaded via the LV instruction. The override selects which arithmetic instruction slot (A=ALU, M=MAU, D=DSU) or none (N=NONE) is allowed to set condition flags for this execution of the VLIW. The override does not affect the UAF setting specified via the LV instruction. A blank ‘F=’ selects the UAF specified when the VLIW was loaded. 
     The SUM2P instruction  600  operation version  610 : The product of the high halfwords of the even and odd source registers (Rxe, Rxo) and (Rye, Ryo) are added to the product of the low halfwords of the even and odd source registers (Rxe, Rxo) and (Rye, Ryo) and the results are stored in the even and odd target register (Rte, Rto). 
     The SUM2PA instruction  700  operation version  710 : The product of the high halfwords of the even and odd source registers (Rxe, Rxo) and (Rye, Ryo) are added to the product of the low halfwords of the even and odd source registers (Rxe, Rxo) and (Rye, Ryo) and the results are added to the even and odd target register (Rte, Rto) prior to storing the results in (Rte, Rto). 
     The BFLYS instruction  800 : Results of a butterfly operation consisting of a sum and a difference of source registers Rx and Ry are stored in odd/even target register pair Rto∥Rte. Saturated arithmetic is performed such that if a result does not fit within the target format, it is clipped to a minimum or maximum as necessary. 
     The ADD instruction  900 : The sum of source registers Rx and Ry is stored in target register Rt. Multiple packed data type operations are defined in syntax/operation table  910 . 
     The PERM instruction  1000 : Bytes from the source register pair Rxo∥Rxe are placed into the target register RI or Rto∥Rte based on corresponding 4-bit indices in permute control word Ry. FIGS. 10C,  10 D, and  10 E depict three exemplary operations  1020 ,  1030 , and  1040  of this instruction. 
     The PEXCHG instruction  1100 : A PE&#39;s target register receives data from its input port. FIG. 11C illustrates a 2×2 cluster switch diagram  1110  and four PEs  1112 ,  1114 ,  1116  and  1118  arranged in a 2×2 array. The PE&#39;s source register is made available on its output port. The PE&#39;s input and output ports are connected to a cluster switch  1120  as depicted in FIG.  11 C. The cluster switch is made up of multiplexers  1122 ,  1124 ,  1126  and  1128  (muxes), whose switching is controlled by individual PEs. The combination of the PeXchgCSctrl and the PE&#39;s ID controls the PE&#39;s mux in the cluster switch. The PEXCHG table specifies how the muxes are controlled as illustrated in the key to PEXCHG 2×2 operation table  1140  shown in FIG.  11 D. Each PE&#39;s mux control, in conjunction with its partner&#39;s mux control, determines how the specified source data is routed to the PE&#39;s input port. Each PE also contains a 4-bit hardware physical identification (PID) stored in a special purpose PID register. The 2×2 array uses two bits of the PID. The PID of a PE is unique and never changes. Each PE can take an identity associated with a virtual organization of PEs. This virtual ID (VID) consists of a Gray encoded row and column value. For the allowed virtual organization of PEs  1150 , shown in FIG. 11H, the last 2 digits of the VID match the last 2 digits of the PID. Tables  1160 ,  1170  and  1180  of FIGS.  11 E,  11 F and  11 G, respectively, show the control settings for a 1×1, 1×2, and a 2×2 configuration of PEs, respectively. 
     The LMX instruction  1200 : Loads a byte, halfword, word, or doubleword operand into an SP target register from SP memory or into a PE target register from PE local memory. Even address register Ae contains a 32-bit base address of a memory buffer. The high halfword of odd address register Ao contains an unsigned 16-bit value representing the memory buffer size in bytes. This value is the modulo value. The low halfword of Ao is an unsigned 16-bit index loaded into the buffer. The index value is updated prior to (pre-decrement) or after (post-increment) its use in forming the operand effective address. A pre-decrement update involves subtracting the unsigned 7-bit update value UPDATE 7  scaled by the size of the operand being loaded (i.e. no scale for a byte, 2 for a halfword, 4 for a word, or 8 for a doubleword) from the index. If the resulting index becomes negative, the modulo value is added to the index. A post-increment update involves adding the scaled UPDATE 7  to the index. If the resulting index is greater than or equal to the memory buffer size (modulo value), the memory buffer size is subtracted from the index. The effect of the index update is that the index moves a scaled UPDATE 7  bytes forward or backward within the memory buffer. The operand effective address is the sum of the base address and the index. Byte and halfword operands can be sign-extended to 32-bits. 
     An alternate implementation of the 8×8 2D IDCT of the present invention that is scalable so that it is operable on arrays of different numbers of PEs, such as 1×0, 1×1, 1×2, 2×2, 2×3, and so on, is described below. This alternate approach makes efficient use of the SUM2PA ManArray instructions as well as the indirect VLIW architecture. FIG. 14 is a logical representation  1400  in two-dimensional form of the 8×8 IDCT input data, F i w ,j z , as required for this scalable approach. The ordering shown maintains a relationship of the rows and columns given by the following formula that allows the reuse of the VLIWs and cosine coefficient table without modification for each dimension (rows or columns). By reuse of the VLIWs, the VIM memory is minimized and by common use of the cosine coefficient tables, the local PE data memory is minimized. The relationship between the different matrix elements as shown in FIG. 14 is specified as follows: 
     Where a selected subscript “i w ” is even or odd, and 
     If i w  is even then 
     j z  is odd, 
     matrix elements x a , x b , x c , x d  are non-repeating members of {0,2,4,6}, and 
     matrix elements y m , y n , y o , y p  are non-repeating members of { 1,3,5,7} 
     else 
     j z  is even, 
     matrix elements x a , x b , x c , x d  are non-repeating members of {1,3,5,7}, and matrix elements y m , y n , y o , y p  are non-repeating members of {0,2,4,6}. 
     For this approach, four 16-bit values are loaded into the CRF by use of a double-word load instruction. In the current implementation of the ManArray™ architecture termed Manta™ which has a fixed endianess ordering for memory accesses the values are loaded “reverse-order” into a register pair. For example, the four memory values: 
     {F x a ,x a , F x a ,x b , F x a ,x c , F x a ,x d } 
     are loaded into a register pair as: 
     { F x a ,x d , F x a ,x c , F x a ,x b , F x a ,x a }. 
     Note that if the endianess of a processor core changes, the only change needed to the process is the arrangement of the cosine coefficients in the static table stored in memory. The orderings of x a , x b , x c , x d  and y m , y n , y o , y p  will determine the ordering of the static cosine coefficient table. The groupings of even and odd indices allow efficient use of the SUM2PA instruction in the ManArray architecture. The outputs are determined by the internal workings of the algorithm itself and are in the subscript order 0,1,2,3,4,5,6,7. 
     FIG. 15 illustrates the intermediate output table  1500  after the completion of the first dimension of processing. Note that the input row I x a , j z  (x a  subscripts are common across the first row) is processed and stored in a transpose position as column I x a , j z  in FIG. 15 (x a  subscripts are common across the first column). Likewise row I x b , j z  (x b  subscripts are common across the second row) is processed and stored in column I x b , j z  in FIG. 15 (x b  subscripts are common across the second column), etc. The post-increment/decrement feature of the LII instruction allow for easy and efficient address generation supporting the stores to memory in the specified memory organization. 
     During the second pass through the array, the incoming rows are again processed and stored in the transpose positions as columns. The result is a complete 8×8 2D IDCT stored in row-major order. The logical matrix organization of the pixel results, P ij , is shown in table  1600  of FIG.  16 . In the present implementation, the output is in 16-bit format. However, if it is known that the output values can be represented as 8-bit values, the code can be modified to store 8-bit data elements instead of 16-bit data elements. 
     Since the 8×8 IDCT is linearly separable, the code for a 1×8 IDCT is shown in table  1700  of FIG. 17, and then expanded into the full 8×8 IDCT, code listings  1800 ,  1805 ,  1810 ,  1815 ,  1820 ,  1825 ,  1830 ,  1835 ,  1840 ,  1845 ,  1850 ,  1855  and  1860  of FIGS. 18A-M, respectively. 
     In the code table  1700  for a 1×8 IDCT, FIG. 17, note that AO holds the address of the incoming data that has been properly arranged, A 1  holds the address of the cosine coefficient table, and A 2  holds the address of the output data. R 30  holds a special rounding value (where needed, 0 otherwise). R 26  holds the permute control word (value 0x32107654). All incoming and outgoing values are 16-bit signed data. Internal working values use 16- and 32-bit signed data types. 
     The special ordering of the input data can be incorporated as part of a de-zigzag scan ordering in a video decompression scheme (e.g. MPEG-1, MPEG-2, H.263, etc.). The output data is in row-major order. The 1×8 code for any row in FIG. 17 will output values 0, 1, 2, 3, 4, 5, 6, and 7. The incoming data is loaded into registers R 0 -R 3  of a processing element&#39;s CRF, packing two data values in each register, as follows:                           
     The construction of the complete 2D 8×8 IDCT is accomplished by performing a series of 8 1×8 IDCTs on the rows in a pipelined fashion, storing the output values in a second memory storage area in transpose format, performing a second series of 8 1×8 IDCTs on the rows of the transposed array (these are the columns of the original data), then storing the output values in a new storage area in transposed format. Exemplary ManArray 2D 8×8 IDCT code is shown in FIGS. 18 A-M. The scalable algorithm uses four additional instructions. FIG. 19A shows a load indirect with scaled immediate update (LII) instruction  1900  and FIG. 19B shows a syntax operation table  1910  for the LII instruction  1900  of FIG.  19 A. LII instruction  1900  loads a byte, halfword, word, or doubleword operand into an SP target register from SP memory or into a PE target register from PE local memory. Source address register An is updated prior to (pre-decrement/pre-increment) or after (post-decrement/post-increment) its use as the operand effective address. The update to An is an addition or subtraction of the unsigned 7-bit update value UPDATE 7 scaled by the size of the operand being loaded. In other words, no scale for a byte, 2 for a halfword, 4 for a word, or 8 for a doubleword. Byte and halfword operands can be sign-extended to 32-bits. 
     FIG. 20A shows a subtract (SUB) instruction  2000  and FIG. 20B shows a syntax operation table  2010  for the SUB instruction  2000  of FIG.  20 A. Utilizing SUB instruction  2000 , the difference of source register Rx and Ry stored in target register Rt. 
     FIG. 21A shows a shift right immediate (SHRI) instruction  2100 , and FIG. 21B shows a syntax/operation table  2110  for the SHRI instruction  2100  of FIG.  21 A. Utilizing instruction  2100 , each source register element is shifted right by the specified number of bits Nbits. The range of Nbits is 1-32. For signed (arithmetic) shifts, vacated bit positions are filled with the value of the most significant bit of the element. For unsigned (logical) shifts, vacated bit positions are filled with zeroes. Each result is copied to the corresponding target register element. 
     FIG. 22A illustrates a store indirect with scaled immediate update (SII) instruction  2200 , and FIG. 22B shows a syntax/operation table  2210  for the SII instruction  2200  of FIG.  22 A. SII instruction  2200  stores a byte, halfword, word, or doubleword operand to SP memory from an SP source register or to PE local memory from a PE source register. Source address register An is updated prior to (pre-decrement/pre-increment) or after (post-decrement/post-increment) its use as the operand effective address. The update to An is an addition or subtract of the unsigned 7-bit update value UPDATE 7  scaled by the size of the operand being loaded. In other words, no scaleing is done for a byte, 2 for a halfword, 4 for a word, or 8 for a doubleword. 
     To realize the storage of the transpose values, the storage instructions of the 1×8 IDCT code table  1700  of FIG. 17, are modified as shown in code table  2300  of FIG.  23 . Note the storage offsets in the SII instructions. The “+8” updates the address pointer so that an element is stored in the transpose format. The “−55” resets the address pointer to the beginning of the next column. 
     After the 8 rows of the first dimension are completed, the intermediate output is stored in transpose format. A 0  is loaded with the address of the intermediate data, A 1  is loaded with the start of the cosine coefficient table again, and A 2  is loaded with the address of the final output data&#39;s destination. R 30  is again loaded with either the rounding constant or 0. R 26  is loaded with the permute control word (0x32107654). 
     By pipelining the rows (then the columns) a portion of the code, FIGS. 18D-M, is shown in FIG. 23 for a sample set of VLIWs progressing through rows of the 8×8, i.e. 1×8 IDCTs in succession. Entry  2302  indicates the start of next row processing and entry  2304  indicates the finish of the previous row processing. The VLIW number (VIM address) and the execution slot enable controls, #,E=execution unit, are given in a first column  2310 . First shown are the VLIW loads (VIM intialization), FIGS. 18A-C, then the actual execution code for the first dimension, FIGS. 18D-H and then the code for the processing of the second dimension, FIGS. 18I-M. The final output is stored in row major order at location specified by output_buffer. The total cycle count is 202 cycles for a single 2D 8×8 IDCT. 
     It is noted that while this version of the IDCT is not as fast as the 34-cycle IDCT on a 2×2, there are several differences and advantages. First, it is scalable. That is, the scalable algorithm runs on a single processing element. In the code discussed above, the IDCT runs on a single SP. On a ManArray 2×2, four 8×8 IDCTs can be performed at once. Thus, the effective cycle count is about 50 cycles per IDCT, as the 202 cycles are divided by the total number of PEs. If a 2×4 array were to be used for video decompression, the effective cycle count would be only 25 cycles. These improvements are made without any change to the process and minimum change to the code. For example, for the exemplary code given in FIGS. 17-23, the .s is changed to a .p meaning the .p instructions are to be executed in the PEs. In addition, the cosine coefficients, a relatively small table, are replicated in each PE&#39;s local memory and the 8×8 data for each locally computed 8×8 2D IDCT is stored in each local PE memory. After the data is distributed, the process is then run in SIMD mode on an array of PEs. 
     Second, the output of each IDCT is in row-major order. No further data manipulation is required as in the 34-cycle version. While the cycle count for this IDCT is slightly higher, the effective throughput of a video decompression engine is reduced. 
     Third, the VIM resources for this process are less. By using a more regular pattern, this approach uses only 11 VLIW locations instead of the 27 required for the 34-cycle version. 
     Further optimization of the cycle count may be possible with this approach, but could result in a corresponding increase in other areas, such as VIM size for example. 
     While the present invention has been disclosed in a presently preferred context, it will be recognized that the present teachings may be adapted to a variety of contexts consistent with this disclosure and the claims that follow. By way of example, while the present invention is principally disclosed in the context of specific IDCT implementations, it will be recognized that the present teachings can be applied to more effective implementations of variety of cosine transforms, such as discrete cosine transforms (DCTs), for example. As one example of such an implementation, FIG. 24 shows an exemplary process  2400  for a 2×2 DCT implementation expected to take 35 cycles to run. The illustrated process  2400  starts with input data already loaded on the PEs of a 2×2 array such as that of FIG.  1 . It ends with the data across the 2×2 array, but not in row-major order. Actual coding and testing of the process has not been completed and various adaptations and adjustments should be expected to optimize the final process for a desired end application.