Abstract:
A method and system for decoding and modifying processor instructions in runtime according to certain rules in order to separately control processing elements embedded within a multi-processor array using a single instruction. The present invention allows multiple processing elements and/or execution units in a multi-processor array to perform different operations, based upon a variable or variables such as their location in the multi-processor array, while accepting a single instruction as an input.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates generally to multi-processor array for executing instructions, and more particularly to runtime processor instructions decoding modification to control the multi-processor array. 
       BACKGROUND OF THE INVENTION 
       [0002]    The present invention allows instruction code reduction since one instruction can result in many different operations. Also, as a lot of mathematic algorithms (especially vector and/or matrix arithmetic) rely on topology (location) of each element in the vector/matrix, the invention allows very efficient execution of numerical algorithms. Several other advantages of the present invention over existing arts include, 
         [0003]    power saving: in cases where not all the PEs are required, a NOP modifier can be used to shut them down, saving power consumption; 
         [0004]    non-SIMD based algorithms: in cases where the underlying algorithm is not a pure SIMD algorithm (for example, a filter operation or a transform operation), a SIMD implementation will not be efficient. Using the PE-grouping method provides much more flexibility, which results in a more efficient implementation; 
         [0005]    multiple data set operations: in cases where the underlying algorithm operates on a data set smaller than the size of the PE-array, some of the PEs will not be utilize and the efficiency of the implementation will be low (consider a 2×2 matrix multiply on a 4×4 PE array). Using the PE-grouping method allows the implementation on multiple data set in parallel (four 2×2 matrix multiply executing at the same time); 
         [0006]    unaligned loading: allowing a construction of non-align data elements (from memory) to be loaded to the same register (for example, register “r0”) of the PE-array, the PE-grouping method can be used to load multiple consecutive data elements (for example, two consecutive data element vectors: [v0, v1, . . . , v15] and [u0, u1, . . . , u15]) such that a subset is store in the same register (using the operand modifiers, for example, first half of the V vector is saved in r0, second half in r1, first half of the U vector in r1 and second in r0. This will result in the elements [v8, v9, . . . , v15, u0, u1, . . . , u7] stored in r1 register). 
       SUMMARY OF THE INVENTION 
       [0007]    A method and system for decoding and modifying processor instructions in runtime according to certain rules in order to separately control processing elements embedded within a multi-processor array using a single instruction. The present invention allows multiple processing elements in a multi-processor array to perform different operations, based upon a variable or variables such as their location in the multi-processor array, while accepting a single instruction as an input. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    These and other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures, wherein: 
           [0009]      FIG. 1  illustrates a first embodiment of the present invention; 
           [0010]      FIG. 2  illustrates a secondary instruction decoder according to the present invention; and 
           [0011]      FIGS. 3 and 4  illustrate an example implementation according to the present invention. 
           [0012]      FIG. 5  illustrates an example of four quadrants grouping according to the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0013]    The present invention will now be described in detail with reference to the drawings, which are provided as illustrative examples of the invention so as to enable those skilled in the art to practice the invention. Notably, the figures and examples below are not meant to limit the scope of the present invention to a single embodiment, but other embodiments are possible by way of interchange of some or all of the described or illustrated elements. Moreover, where certain elements of the present invention can be partially or fully implemented using known components, only those portions of such known components that are necessary for an understanding of the present invention will be described, and detailed descriptions of other portions of such known components will be omitted so as not to obscure the invention. In the present specification, an embodiment showing a singular component should not be considered limiting; rather, the invention is intended to encompass other embodiments including a plurality of the same component, and vice-versa, unless explicitly stated otherwise herein. Moreover, applicants do not intend for any term in the specification or claims to be ascribed an uncommon or special meaning unless explicitly set forth as such. Further, the present invention encompasses present and future known equivalents to the known components referred to herein by way of illustration. 
         [0014]    One embodiment of the present invention is illustrated in  FIG. 1 . A Multi-Processor array  100  includes several independent and separate Processing Elements (PE)  110 , that are connected to a central Control Unit (CU)  120 . The CU accepts instructions from the instruction memory  130  and then distributes control signals to each PE  110  according to the instructions. A Primary Instruction Decoder (PID)  140  located in the CU  120  decodes the instruction supplied to the CU  120 , and a Secondary Instruction Decoder (SID)  150  located in each PE  110  decodes control signals distributed from the PID  140 . The SID  150  modifies the control signals based on the location of the corresponding PE, in the multi-processing array. In another embodiment, not shown, the SID&#39;s  150  are each located within the central control unit  120 , rather than in the corresponding PE  110 , though the complexity of this embodiment is substantially increased, since in order for the distribution of control signal to occur within required periods, the CU  120  needs to perform the SID  150  operations in parallel. 
         [0015]    It is also understood that the PID  140  performs the decoding according to PE location. Meaning, each PE  110  gets its own modification signals based on its location (which group it belongs to) from the PID  140 . Then, SID  150  performs the modification decoding (for example, it get the original instruction and an inverse operation modification signal, which tell it to inverse the operation). SID  150  does not preferably deal with the PE location any more, since this was handled by PID  140 . So, again, PID  140  gets the instruction from instruction memory and looks at the Location ID Register, which indicates to the PID  140  to which group each PE belongs and what are the modifications per group. Then, PID  140  sends the relevant modification signals to each PE  110  based on its group. SID  150  then performs the modifications to its operation, source operands and destination operands and executes the (modified) instruction. As an example, assume that PE 3  belongs to Group 1. The Location ID register also specifies the modification (operation and operands) for each group (lets assume there are 3 groups—meaning there are 3 sets of modifiers, one for each group). In that case, PID  140  will send to PE 3 &#39;s SID  150  only the modifiers (operation and operands) relevant to Group 1 (one of the 3 modifiers set). All the SID  150  needs to do is to perform the relevant modification (inverse of the operation, for example) and execute the (modified) instruction. 
         [0016]    The Primary Instruction Decoder (PID)  140  performs a first level instruction decoding using the instructions fetched form Instruction Memory  130  to the CU  120  and generates control signals, which in turn are fed to all of the PE  110  collection. Each PE 110  contains a Secondary Instruction Decoder (SID)  150 , which consists of decode logic  160 , as shown in  FIG. 2 . The location ID resides in PID  140 . 
         [0017]    The Location ID Register  170  holds identifying information that uniquely identifies each PE  110  to which group it belongs to, together with modification information per group (meaning, how to modify the operation, source operands and destination operands for each group). This grouping identity can be generated according to location within the array (a special instruction, which defines the grouping at run-time), some serial ID, or any other identification method. The modification information can also be generated at run-time using an instruction. Based on the content of the Location ID Register, the PID sends the modification signals to each PE, based on which group it belongs to (together with the original instruction). Thus, the same instruction supplying form the PID  140  to all PE collection can be understood differently by each PE, according to the modification signals that PID  140  sends to each PE, and as a result, each PE  110  can react differently to the same instruction. For example, an ADD instruction can be interpreted as ADD by some PEs and SUBTRACT by some other PEs. 
         [0018]    Table 1 below shows an example of opcode (operation) modifier where the first column shows the original opcodes, and the second column shows the modified opcodes, which in this case is the complement of the original. The PE executes the “original opcode” or the “modified opcode” or performs a “no-operation” according to the modification signals. For example, when receiving an ADD/ADDU instruction from PID  140 , the PE will perform an ADD/ADDU operation if the modification signals indicate “original opcode”, a SUB/SUBU operation if “modified opcode”, and no operation if “no-op”. Table 2 below shows an example of single register operand modifier, where the first column shows the original operand, the second column shows modification 1, the third column shows modification 2, and the last column shows modification 3. For example, suppose that the original instruction asks for R7 as the operand, the PE will locate R7 if the modification signals indicate “original operand”, R6 if “modification 1,” R5 if “modification 2,” and R4 if “modification 3”. 
         [0019]    One example implementation of the present invention is shown in  FIG. 3 , where the CU  120  is omitted from this drawing for clarity. The system  100  contains 16 Processing Elements (PE)  110 , arranged as a 4×4 matrix  200 . Here, it is assumed that the 4×4 PE matrix  200  is divided into 4 groups of 2×2 PE matrix  210 ,  220 ,  230 ,  240 , by writing proper information into the Location ID Register  170 , as shown in  FIG. 4 . It should be noted that the matrix dimension and the divided group amount applied here are for illustration purposes, and it should be clear that any dimension and groups amount applicable can be applied to matrix  200 . 
         [0020]    Suppose an ADD instruction “ADD R0, R1, R2” is fed from the CU  120  to the entire PE matrix  200 . The original ADD instruction “ADD R0, R1, R2” performs the operation: R0→R1+R2, where the values stored in R1 and R2 are added together, and the resulting value is stored in R0 register. However, based upon the decode logic in each SID, (as described above in Table 1 and 2,) every PE can interpret the instruction differently. A possible parameter implementation of Location ID Register  170  can provide the following functionality: group  210  performs R0←R1+R2, group  220  performs R0←R1 31  R2, group  230  performs R3←R2−R1, and group  240  performs no-operation. All four different operations are resulted from the same original instruction. 
         [0021]    Below is the Opcode (operation) modification Table 1: 
         [0000]                                  TABLE 1                   Opcode Modifiers                Original Opcode   Modified Opcode                       or   nor           and   nand           add   sub           sub   add           max   min           min   max                        
Below is Table 2 which describe the operands modifiers:
 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Single Registers operand modifiers 
               
             
          
           
               
                 Original Operand 
                 Modification 1 
                 Modification 2 
                 Modification 3 
               
               
                   
               
               
                 R0 
                 R1 
                 R2 
                 R3 
               
               
                 R1 
                 R0 
                 R3 
                 R2 
               
               
                 R2 
                 R3 
                 R0 
                 R1 
               
               
                 R3 
                 R2 
                 R1 
                 R0 
               
               
                 R4 
                 R5 
                 R6 
                 R7 
               
               
                 R5 
                 R4 
                 R7 
                 R6 
               
               
                 R6 
                 R7 
                 R4 
                 R5 
               
               
                 R7 
                 R6 
                 R5 
                 R4 
               
               
                 XN0 
                 XS0 
                 XE0 
                 XW0 
               
               
                 XS0 
                 XN0 
                 XW0 
                 XE0 
               
               
                 XE0 
                 XW0 
                 XS0 
                 XN0 
               
               
                 XW0 
                 XE0 
                 XN0 
                 XS0 
               
               
                 XN1 
                 XS1 
                 XE1 
                 XW1 
               
               
                 XS1 
                 XN1 
                 XW1 
                 XE1 
               
               
                 XE1 
                 XW1 
                 XS1 
                 XN1 
               
               
                 XW1 
                 XE1 
                 XN1 
                 XS1 
               
               
                   
               
             
          
         
       
     
         [0022]    The different types of grouping are, in general, derived from the underlying algorithms. As an example, we can consider a Hadamard transform algorithm, which uses as its basic operations an addition and subtraction operations. If we consider a 4×4 two-dimensional Hadamard transform implemented on a 4×4 PE array, then, due to the 4×4 Hadamard matrix, we will have to define both rows and columns grouping (some parts of the algorithm will use rows grouping while other parts will use columns grouping). 
         [0023]    As another example, we can consider four 2×2 matrices multiply implemented on the same 4×4 PE array. In order to implement the four matrices multiply in parallel, a quadrant-corner grouping is needed as illustrated in the  FIG. 5 . 
         [0024]    In general, grouping of rows, columns (not necessarily 4 groups, as we can define two groups where the first two rows/columns belong to Group 0 and the next two rows/columns belong to Group 1), quadrants and quadrant-corners (as shown in  FIG. 5 ) can be used to implement a wide variety of algorithms, although other types of grouping may be need as well. 
         [0025]    Although the present invention has been particularly described with reference to the preferred embodiments thereof, it should be readily apparent to those of ordinary skill in the art that changes and modifications in the form and details may be made without departing from the spirit and scope of the invention. It is intended that the appended claims encompass such changes and modifications.