Methods and apparatus for efficient synchronous MIMD operations with IVLIW PE-TO-PE communication

Abstract

A SIMD machine employing a plurality of parallel processor (PEs) in which communications hazards are eliminated in an efficient manner. An indirect Very Long Instruction Word instruction memory (VIM) is employed along with execute and delimiter instructions. A masking mechanism may be employed to control which PEs have their VIMs loaded. Further, a receive model of operation is preferably employed. In one aspect, each PE operates to control a switch that selects from which PE it receives. The present invention addresses a better machine organization for execution of parallel algorithms that reduces hardware cost and complexity while maintaining the best characteristics of both SIMD and MIMD machines and minimizing communication latency. This invention brings a level of MIMD computational autonomy to SIMD indirect Very Long Instruction Word (iVLIW) processing elements while maintaining the single thread of control used in the SIMD machine organization. Consequently, the term Synchronous-MIMD (SMIMD) is used to describe the present approach.

1. An indirect very long instruction word (VLIW) processing system comprising:
 a first processing element (PE) having a VLIW instruction memory (VIM) for storing function instructions in slots within a VIM memory location;  
 a first register for storing a control instruction and a function instruction, the function instruction having a plurality of definition bits defining both a  the control instruction type and an execution unit type of the function instruction;  
 a predecoder for decoding the plurality of definition bits; and  
 a load mechanism for loading the function instruction in one of said slots in VIM based upon both said decoding, and a control instruction defining a load operation.  
 
     
     
       2. The system of  claim 1  wherein the predecoder is for decoding an execute VLIW control instruction containing an address offset and a pointer to a base address register for indirectly exeucting VLIWs. 
     
     
       3. The system of  claim 1  wherein the predecoder is for decoding said control instruction defining a load operation containing an address offset and pointer to a base address register for loading the function instruction. 
     
     
       4. The system of  claim 1  wherein the definition bits are removed from the function instruction before the function instruction is stored in VIM. 
     
     
       5. The system of  claim 1  wherein the definition bits are removed from the function instruction and at least one simplex control bit is added to the fucntion instruction before the function instruction is stored in VIM. 
     
     
       6. The system of  claim 5  wherein the at least one simplex control bit includes an enable/disable bit. 
     
     
       7. The system of  claim 5  wherein the at least one simplex control bit includes an operation code extension bit. 
     
     
       8. The system of  claim 5  wherein the at least one simplex control bit includes a register file extension bit. 
     
     
       9. The system of  claim 5  wherein the at least one simplex control bit includes a conditional execution extension bit. 
     
     
       10. The system of  claim 9  further comprising a plurality of execution units, and first and second banks of registers, and the register file extension bit is utilized to determine whether the plurality of execution units read from or write to the first bank of registers or the second bank of registers. 
     
     
       11. The system of  claim 1  further comprising a second register for storing the function instruction; a bypass path for connecting an output of the first register to an input of the second register; and a selection mechanism for selecting a bypass operation in which the function instruction is passed from the first register to the second register without being loaded into VIM. 
     
     
       12. The system of  claim 1  further comprising at least one additional PE connected through a network interface connection to the first PE, and each PE has an associated cluster switch connected to a receive port such that each PE controls a portion of the cluster switch. 
     
     
       13. The system of  claim 12  wherein the associated cluster switch comprises at least one multiplexer per PE interconnected to provide independent paths between the PEs in a cluster of PEs. 
     
     
       14. The system of  claim 1  further comprising a sequence processor (SP) connected to the first PE and providing both said control instruction and said function instruction to the first PE, the control instruction containing an address offset and a ponter to a base address register for loading the function instruction. 
     
     
       15. The system of  claim 14  further comprising at least one additional PE connected to the SP and said control instruction is provided synchronously to both the first PE and said at least one additional PE. 
     
     
       16. The system of  claim 15  wherein a plurality of PEs are connected to the SP and the plurality of PEs is organized into first and second groups of one or more PEs. 
     
     
       17. The system of  claim 16  wherein the first group of PEs indirectly operate on a VLIW instruction ata first VIM address during a cycle of operation and the second group of PEs indirectly operate on a different VLIW instruction at the same first VIM address during the cycle of operation. 
     
     
       18. The system of  claim 16  wherein the plurality of PEs operate following a receive model of communication control in which each PE has a receive port and controls whether data is received at the receive port. 
     
     
       19. The system of  claim 18  wherein each PE has a output port for making data available in the cluster switch. 
     
     
       20. The system of  claim 18  whereby each PE has an input multiplexer connected to the receive port and controls communication by controlling said input multiplexer. 
     
     
       21. The system of  claim 18  wherein the plurality of PEs are programmed to cooperate by storing a cooperating instruction so that one PE has a receive instruction specifying the path that the other PE is making data available on in the same location in VIM for each of said plurality of PEs. 
     
     
       22. The system of  claim 16  further comprising a masking mechanism for masking individual PEs ON or OFF. 
     
     
       23. The system of  claim 22  in which VIMs for PEs masked ON are loaded and VIMs for PEs masked OFF are not loaded during al oad VLIW operation. 
     
     
       24. The system of  claim 16  wherein different PEs execute different VLIWs at the same VIM address during the same cycle. 
     
     
       25. The system of  claim 1  wherein the VIM comprises slots for storing function instructions of the following type: store unit instructions; load unit instructions; arithmetic logic unit instructions; mulitply-accumulate unit instructions; or data select unit instructions. 
     
     
       26. A processing system comprising:
   a plurality of processing elements  ( PEs )  communicatively connected to each other, each of said PEs including a very long instruction word  ( VLIW )  memory  ( VIM )  for storing VLIWs to be executed by each PE; and        a sequence processor  ( SP )  operable for concurrently initiating indirect execution of a VLIW stored at a first address in the VIM of each PE, in response to the SP issuing an indirect instruction to initiate concurrent execution by each PE, each PE of said plurality of PEs concurrently executing the VLIW stored at the first address in the VIM associated with each PE, and        at least one of said plurality of PEs concurrently executing a VLIW at the first address of its VIM which defines a different operation from a VLIW concurrently executed by another PE of said plurality of PEs.      
     
     
       27. The processing system of  claim 26  wherein the SP is further operable for concurrently initiating the execution of instructions stored in a VLIW at a second address in the VIM of each PE wherein each PE concurrently executes an instruction stored in a VLIW at the second address in the instruction memory associated with each PE, and
   the plurality of PEs execute instructions which define the same operation.      
     
     
       28. The processing system of  claim 27  wherein the plurality of PEs include a first PE and a second PE and the SP is further operable for:
   concurrently initiating the execution of instructions stored in a VLIW at a third address in the VIMs such that the first PE executes a first instruction stored in a VLIW at the third address in the VIM associated with the first PE, and the second PE executes a second instruction stored in a VLIW at the third address in the VIM associated with the second PE.      
     
     
       29. The processing system of  claim 28  wherein:
   the first instruction and the second instruction define different operations.      
     
     
       30. The processing system of  claim 28  wherein:
   the first instruction and the second instruction define the same operation.      
     
     
       31. The processing system of  claim 26  wherein the SP is further operable for executing an instruction stored in a VLIW at the first address in the VIM of one of said plurality of PEs.  
     
     
       32. The processing system of  claim 26  wherein each PE includes a base address register, and wherein the first address in each PE is determined utilizing the base address register and an offset value contained in an indirect instruction issued by the SP.  
     
     
       33. The processing system of  claim 26  wherein the instruction to be executed by the PEs comprises at least one very long instruction word ( VLIW ).  
     
     
       34. The processing system of  claim 26  wherein the indirect instruction to initiate concurrent execution by each PE is an execute VLIW instruction.  
     
     
       35. The processing system of  claim 34  wherein the execute VLIW instruction is operable to enable each of at least two instructions comprising a VLIW for execution.  
     
     
       36. The processing system of  claim 35  wherein:
   each PE includes a base address register; and        each PE determines the first address utilizing the base address register associated with each PE and an offset value contained in the execute VLIW instruction.      
     
     
       37. The processing system of  claim 26  wherein:
   each PE is operable to receive data from other PEs; and        each PE is operable to control from which PE data is received.      
     
     
       38. A processing system comprising:
   a first processing element  ( PE )  including a first instruction memory for storing a first very long instruction word  ( VLIW )  to be executed by said first PE; and        a second processing element  ( PE )  including a second instruction memory for storing a second VLIW to be executed by said second PE, said second VLIW and said first VLIW defining different operations;        wherein the first VLIW and the second VLIW are both stored at the same address location in each memory;        wherein the first PE and the second PE are operable for simultaneously executing the first VLIW and the second VLIW, respectively, in response to each PE receiving an execute very long instruction word  ( VLIW )  instruction.      
     
     
       39. The processing system of  claim 38  further comprising a sequencing processor ( SP )  which initiates the concurrent execution of the first instruction and the second instruction by issuing the VLIW instruction.    
     
     
       40. The processing system of  claim 38  wherein
   each PE includes a base address register; and        each PE determines the first address utilizing both the base address register associated with each PE and an offset value contained in the execute VLIW instruction.      
     
     
       41. The processing system of  claim 38  wherein:
   the first and second instructions comprise very long instruction word  ( VLIW )  instructions; and        each VLIW instruction comprises a plurality of simplex instructions.      
     
     
       42. The processing system of  claim 41  wherein:
   each PE comprises a plurality of execution units; and        each simplex instruction is adapted for being executed by at least one of the execution units.      
     
     
       43. The processing system of  claim 38  wherein each PE further comprises:
   an instruction register for storing the execute VLIW instruction; and        a predecoder for decoding if the instruction stored in the instruction register in an execute VLIW instruction.      
     
     
       44. The processing system of  claim 43  wherein the predecoder of the first PE generates a first signal which is used to initiate the load of the first instruction into the first PE, and wherein the predecoder of the second PE generates a second signal which is used to initiate the load of the second instruction into the second PE.  
     
     
       45. A processing method for a processing system comprising a first processing element ( PE )  including a first very long instruction word memory  ( VIM ) , the first PE communicatively connected to a second PE including a second VIM, the method comprising:      loading a first function instruction in the first VIM at a first address;        loading a second function instruction in the second VIM at the first address;        receiving an execute VLIW instruction; and        concurrently executing the first function instruction by the first PE and the second function instruction by the second PE, in response to the received execute VLIW instruction;        wherein the first function instruction stored in the first VIM at the first address and the second function instruction stored in the second VIM at the first address define different operations.      
     
     
       46. The method of  claim 45  wherein the first PE includes a base address register and the method further comprising, before the step of loading the first function instruction:
   receiving a load VLIW instruction which contains an address offset;        predecoding the load VLIW instruction; and        determining the first address utilizing the address offset and the base address register.      
     
     
       47. The method of  claim 45  wherein the first address of the first VIM includes a plurality of slots and wherein the step of loading the first function instruction further comprises:
   receiving the first function instruction; and        predecoding the first function instruction to determine into which slot the first instruction is to be loaded.      
     
     
       48. The method of  claim 47  wherein the step of predecoding the first function instruction further comprises:
   determining if any of said plurality of slots are to be disabled; and        if any of said plurality of slots are to be disabled, loading a disable bit in a storage bit for each slot which is to be disabled.      
     
     
       49. The method of  claim 47  wherein the first function instruction includes at least one group bit defining an instruction type and at least one unit field bit defining an execution unit type, and the step of predecoding the first function instruction utilizes both the instruction type and the execution unit type to determine which slot the first function instruction should be loaded.  
     
     
       50. The method of  claim 49  further comprising:
   removing the at least one group bit and the at least one unit field bit from the first function instruction before the first function instruction is loaded into the first VIM; and        adding at least one replacement bit to the first function instruction.      
     
     
       51. The method of  claim 45  wherein the first PE includes a base address register, wherein the execute VLIW instruction includes an address offset, and wherein the step of receiving the execute VLIW instruction further comprises:
   predecoding the execute VLIW instruction; and        determining the first address utilizing the address offset and the base address register.      
     
     
       52. The processing method of  claim 45  wherein the step of loading a first function instruction in the first VIM at a first address further comprises:
   masking the first PE to be enabled; and        masking the second PE to be disabled.      
     
     
       53. The processing method of  claim 45  wherein the step of loading a second function instruction in the second VIM at the first address further comprises:
   masking the first PE to be disabled; and        masking the second PE to be enabled.