Methods and apparatus for abbreviated instruction sets adaptable to configurable processor architecture

Abstract

An improved manifold array (ManArray) architecture addresses the problem of configurable application-spacific instruction set optimization and instruction memory reduction using an instruction abbreviation process thereby further optimizing the general ManArray architecture for application to high-volume and portablke battery-powered type of products. In the ManArray abbreviation process a standard 32-bit ManArray instruction is reduced to a smaller length instruction format, such as 14-bits. An application is first programmed using the full ManArray instruction set using the native 32-bit instructions. After the application program is completed and verified, an instruction-abbreviation tool analyzes the 32-bit application program and generates the abbreviated program using the abbreviated instructions. This instruction abbreviation process allows different program-reduction optimizations tailored for each application program. This process develops an optimized instruction set for the intended application. The abbreviated program, now located in a significantly smaller instruction memory, is functionally equivalent to the original native 32-bit application program. The abbreviated-instructions are fetched from this smaller memory and then dynamically translated into native ManArray instruction form in a sequence processor controller. Since the instruction set is now determined for the specific application. an optimized processor design can be easily produced. The system and process can be applied to native instructions having other numbers of bits and to other processing architectures.

1. A method for generating an abbreviated application specific program utilizing an abbreviated instruction set comprising the steps of:
 generating a native program for an application utilizing a set of native instructions having a first fixed  number of bits;  
 debugging the native program;  
 processing the debugged native program by analyzing the set of native instructions at a sub-instruction level with a processor to determine specific patterns of bits that do not change within groups of instructions mid  and utilizing the results of said analysis to determine an abbreviated instruction set having a second fixed  number of bits less than the first fixed  number of bits and corresponding to the set of native instructions; and  
 converting the native program to the abbreviated application specific program by replacing the set of native instructions with the abbreviated instruction set.  
 
     
     
       2. The method of  claim 1  wherein said step of processing further comprises:
 analyzing the set of native instructions to identify a first group of native instructions having a style pattern of bits which is defined as a specific pattern of bits that are constant for said group.  
 
     
     
       3. The method of  claim 2  further comprising the step of:
 storing the identified style pattern of bits in a translation memory.  
 
     
     
       4. The method of  claim 3  further comprising the step of:
 utilizing the identified style pattern of bits stored in said translation memory to recreate native instructions from the first group of native instruction by combining bits from corresponding abbreviated instructions with the identified style pattern of bits.  
 
     
     
       5. The method of  claim 1  wherein said step of processing further comprises:
 analyzing the set of native instructions to identify multiple groups of native instructions, each group having a style pattern of bits which is defined as a specific pattern of bits that are constant.  
 
     
     
       6. The method of  claim 5  further comprising the step of:
 storing the identified style patterns of bits in a translation memory.  
 
     
     
       7. The method of  claim 6  further comprising the step of:
 utilizing an identified style pattern of bits selected from said translation memory to recreate native instructions from one of said multiple groups of native instructions by combining bits from corresponding abbreviated instructions with the identified style pattern of bits.  
 
     
     
       8. The method of  claim 4  further comprising the step of:
 creating a one-to-one mapping between a program's native instruction and an abbreviated instruction by using a translation memory addressing mechanism to identify the style pattern of bits stored in said translation memory.  
 
     
     
       9. The method of  claim 7  further comprising the step of:
 creating a one-to-one mapping between a program's native instruction and an abbreviated instruction by using a translation memory addressing mechanism to identify the style pattern of bits stored in said translation memory.  
 
     
     
       10. The method of  claim 8  further comprising the translation memory addressing step of adding or concatenating an offset field contained in the abbreviated instruction with a translation memory base address stored in an internal machine register to form the address to select a specific pattern of bits from said translation memory. 
     
     
       11. The method of  claim 9  further comprising the translation memory addressing step of adding or concatenating an offset field contained in the abbreviated instruction with a translation memory base address stored in an internal machine register to form the address to select a specific pattern of bits from said translation memory. 
     
     
       12. The method of  claim 1  further comprising the step of:
 executing the application specific program on a simulator to verify its functional equivalence to the native program.  
 
     
     
       13. The method of  claim 12  further comprising the step of:
 determining a processor core specification tailored for use in implementing the application specific program utilizing the abbreviated instruction set.  
 
     
     
       14. The method of  claim 1  further comprising the step of executing the application specific program on a Manta-2 based simulator acting as an emulator. 
     
     
       15. The method of  claim 1  wherein the native instruction set is a manifold array (ManArray) instruction set. 
     
     
       16. The method of  claim 15  further comprising the step of translating abbreviated instructions back into a native ManArray format for decoding and execution in a ManArray sequence processor and processing elements. 
     
     
       17. The method of  claim 16  wherein the step of translating abbreviated instructions back is performed only by a sequence processor. 
     
     
       18. A method for generating an abbreviated instruction set corresponding to a set of native manifold array (ManArray) instructions for all  used in an application specific program comprising the steps of:
 separating the set of native ManArray instructions into groups of instructions;  
 identifying the  unique instructions within each group of instructions;  
 analyzing the unique instructions for common instruction characteristics;  
 determining at least one style pattern of bits which is defined as a specific pattern of bits that are constant; and  
 generating the abbreviated instruction set utilizing the at least one style by encoding the at least one style pattern of bits into a reduced number of bits utilizing a processor.  
 
     
     
       19. The method of  claim 18  wherein the set of native ManArray instructions are separated into groups by classifying said instructions by opcode. 
     
     
       20. The method of  claim 19  wherein at least the following groups are established: store and load instructions; MAU and ALU instructions; DSU instructions; and control flow instructions. 
     
     
       21. The method of  claim 19  wherein at least one of the common instruction characteristics is a relative bit-pattern usage in the application specific program for a given bit-pattern split in an abbreviated instruction format. 
     
     
       22. The method of  claim 18  further comprising the step of:
 storing the at least one style pattern of bits in a translation memory.  
 
     
     
       23. The method of  claim 22  further comprising the step of analyzing relative bit-pattern usage among groups of instructions that include a common style. 
     
     
       24. The method of  claim 22  further comprising the step of generating at least one translation management memory instruction. 
     
     
       25. The method of  claim 22  further comprising the step of:
 utilizing the identified style stored in the translation memory to recreate native instructions from a first group of native instruction by combining bits from corresponding abbreviated instructions with the at least one style pattern of bits.  
 
     
     
       26. A method for translating abbreviated instructions into a native instruction format comprising the steps of:
 fetching an abbreviated instruction having a first fixed  number of bits from a memory tailored to storage of abbreviated instructions;  
 dynamically translating the abbreviated instruction into the format of a native instruction by using a first bit field in the abbreviated instruction as an address reference to a first translation memory containing at least one specific sub-native instruction pattern of bits  for a sub- native instruction pattern ;  
 fetching a  the sub-native instruction pattern from the translation memory  using said address reference, said sub-native instruction pattern being based on a previous analysis of the  a set of native instructions on a sub-instruction level to determine patterns of bits that do not change within groups of instructions;  
 combining the sub-native instruction patterns with bits from the abbreviated instruction to create the native instruction in a sequence processor (SP) array controller said native instruction having a second fixed  number of bits greater than said first fixed  number; and  
 dispatching the native instruction to the sequence processor array controller or a processing element for execution.  
 
     
     
       27. The method of claim  26    59  wherein the abbreviated instruction includes at least one S/P bit, a multi-bit opcode field and a multi-bit translation memory address offset for use in the address reference to the first translation memory. 
     
     
       28. The method of  claim 27  wherein the step of dynamically translating further comprises the step of decoding the multi-bit opcode field. 
     
     
       29. The method of  claim 27  wherein the step of dynamically translating further comprises the steps of forming a translation memory address by adding the multi-bit translation memory address offset with a translation memory base address; and
 selecting a plurality of native instruction bits from a location in the translation memory corresponding to the formed translation memory address.  
 
     
     
       30. The method of  claim 27  further comprising the step of directly using the multi-bit translation memory address offset to select a plurality of native instruction bits from a location in a translation memory corresponding to the multi-bit translation memory address offset. 
     
     
       31. The method of  claim 26  wherein the abbreviated instruction includes at least one S/P bit, a multi-bit opcode field, a multi-bit translation memory address offset, and a plurality of bits which are to be directly loaded. 
     
     
       32. The method of  claim 31  wherein the step of dynamically translating further comprises the step of decoding the multi-bit opcode field. 
     
     
       33. The method of  claim 31  wherein the step of dynamically translating further comprises the steps of forming a translation memory address by adding the multi-bit translation memory offset with a translation memory base address; and
 selecting a plurality of native instruction bits from a location in the translation memory corresponding to the formed translation memory address.  
 
     
     
       34. The method of  claim 33  wherein the step of dynamically translating further comprises the step of combining the selected plurality of native instruction bits and the plurality of bits which are to be directly entered. 
     
     
       35. The method of  claim 26  wherein the abbreviated instruction includes at least one S/P bit, a multi-bit opcode field, a first multi-bit translation memory offset field and a second multi-bit translation memory offset field. 
     
     
       36. The method of  claim 35  wherein the step of dynamically translating further comprises the step of decoding the multi-bit opcode field. 
     
     
       37. The method of  claim 35  wherein the step of dynamically translating further comprises the steps of:
 selecting a first multi-bit portion of the native instruction from a first translation memory address utilizing the first multi-bit translation memory offset field; and  
 selecting a second multi-bit portion of the native instruction from a second translation memory address utilizing the second multi-bit translation memory offset field; and  
 combining both multi-bit portions into a native instruction format.  
 
     
     
       38. The method of  claim 37  wherein translation memory addresses are formed by concatenating base address register bits and translation memory offset field bits. 
     
     
       39. A system for translating abbreviated instructions into a native instruction format comprising:
 a memory storing an abbreviated instruction having a first fixed  number of hits  bits;  
 means for fetching the abbreviated instruction from the memory;  
 means for dynamically translating the abbreviated instruction into a native instruction using a translation memory storing at least one specific  a sub-native instruction pattern of bits, said sub-native instruction pattern being based on a previous analysis of the  a set of native instructions on a sub-instruction level to determine patterns of bits that do not change within groups of instructions;  
 an addressing mechanism using a first bit field in the abbreviated instruction as an address reference to the translation memory  for the sub- native instruction pattern ;  
 means for fetching the sub-native instruction pattern from the translation memory  utilizing the address reference; and  
 means for combining the sub-native instruction pattern with bits from the abbreviated instruction to create the native instruction in the native instruction format having a second fixed  number of bits greater than said first fixed  number.  
 
     
     
       40. The system of  claim 39  further comprising means for dispatching the native instruction to at least one processing element for execution. 
     
     
       41. The system of  claim 39  wherein the means for dynamically translating further comprises at least one translation memory for storing style pattern bits which are common to a group of native instructions. 
     
     
       42. A method fur  for translating abbreviated instructions into a native instruction format comprising the steps of:
 fetching an abbreviated instruction having a first fixed  number of bits from a memory tailored to storage of abbreviated instructions;  
 dynamically translating the abbreviated instruction into the format of a native instruction by using a first and a second bit field in the abbreviated instruction as address references to a first field and a second translation memory each containing at least one specific sub-native instruction patterns of bits  for at least two sub- native instruction patterns ;  
 fetching at least two a sub-native instruction pattern from each translation memory  patterns using said address references, each of said at least two sub-native instruction pattern  patterns being based on a previous analysis of the  a set of native instructions on a sub-instruction level to determine patterns of bits that do not change within groups of instructions;  
 combining the at least two sub-native instruction patterns to create the native instruction in a sequence processor (SP) array controller said native instruction having a second fixed  number of bits greater than said first fixed  number; and  
 dispatching the native instruction to the sequence processor array controller or a processing element for execution.  
 
     
     
       43. A system for translating abbreviated instructions into a native instruction format comprising:
 a memory storing an abbreviated instruction having a first fixed  number of bits;  
 means for fetching the abbreviated instruction from the memory;  
 means for dynamically translating the abbreviated instruction into a native instruction using two translation memories each storing  at least one specific sub-native instruction patterns of bits, each of said at least one sub-native instruction patterns being based on a previous analysis of the  a set of native instructions on a sub-instruction level to determine patterns of bits that do not change within groups of instructions;  
 two addressing mechanisms each using a bit field in the abbreviated instruction as an address reference to one of the two translation memories  for the at least one specific sub- native instruction patterns of bits ;  
 means for fetching the sub-native instruction patterns from each translation memory ; and  
 means for combining the sub-native instruction patterns to crate  create the native instruction in the native instruction format having a second fixed  number of bits greater than said first fixed  number.  
 
     
     
       44. The method of  claim 26  wherein the address reference used in the translating step is an address reference to a first translation memory containing at least one specific sub- native instruction pattern of bits.   
     
     
       45. The system of  claim 39  wherein the means for dynamically translating the abbreviated instruction into a native instruction further comprises:
   a translation memory for storing said sub - native instruction pattern of bits.     
     
     
       46. A system for controlling a translation process wherein a B- bit abbreviated instruction having B bits is translated into a native instruction format having C bits, where the value C is greater than the value B, the system comprising:      a B - bit instruction register for holding the B - bit abbreviated instruction;        a base register;        an adder; and        a native instruction register, wherein the base register output and a field of the B - bit abbreviated instruction in the B - bit instruction register are added by the adder to produce an output which selects native instruction bits for loading into the native instruction register, the selected native instruction bits are not found in the B - bit abbreviated instruction, the selected native instruction bits having been previously determined by analyzing a set of native instructions for specific patterns of bits that do not change within the set of native instructions.     
     
     
       47. The system of  claim 46  further comprising a decoder, the decoder receives opcode bits from the B- bit abbreviated instruction in the B - bit instruction register and decodes said opcode bits to generate group bits which are loaded into the native instruction register.   
     
     
       48. The system of  claim 46  wherein B is  12 ,  13 ,  14 ,  15 ,  16 , or some other integer value less than  30  and C is  32 ,  40 ,  48  or  64 . 
     
     
       49. A system for controlling a translation process wherein a B- bit abbreviated instruction having B bits is translated into a native instruction format having C bits, where the value C is greater than the value B, the system comprising:      a B - bit instruction register for holding the B - bit abbreviated instruction;        a base register;        an adder;        a native instruction register, wherein the native instruction register receives a plurality of direct load bits from a direct load field of the B - bit abbreviated instruction in the B - bit instruction register; and        a base register output and a field of the B - bit abbreviated instruction are added by the adder to produce an output which selects native instruction bits for loading in combination with the direct load bits into the native instruction register, the selected native instruction bits are not found in the B - bit abbreviated instruction, the selected native instruction bits having been previously determined by analyzing a set of native instructions for specific patterns of bits that do not change within the set of native instructions.     
     
     
       50. A system for controlling a translation process wherein a B- bit abbreviated instruction having B bits is translated into a native instruction format having B bits, where the value C is greater than the value B, the system comprising:      a B - bit instruction register for holding the B - bit abbreviated instruction;        two base registers, the two base register outputs and two fields of the B - bit abbreviated instruction are concatenated respectively to form at least two addresses to select at least two patterns of native instruction bits, the selected at least two patterns of native instruction bits having been previously determined by analyzing a set of native instructions for specific patterns of bits that do not change within the set of native instructions; and        a native instruction register for loading the native instruction, wherein the selected at least two patterns of native instruction bits are combined as specified by a style set of bits stored in the processor to form the native instruction.     
     
     
       51. A method for operating a processor utilizing an abbreviated instruction having a first number of bits, the method comprising:
   retrieving the abbreviated instruction;        generating an address reference for a native instruction pattern from combining a first bit field in the abbreviated instruction and a base address register;        retrieving the native instruction pattern of bits to be combined with the abbreviated instruction using the address reference, the native instruction pattern of bits being based on a previous analysis of a set of native instructions on a sub - instruction level to determine patterns of bits that do not change within groups of instructions;        combining the native instruction pattern of bits with the abbreviated instruction to create a native instruction, the native instruction having a second number of bits, the second number of bits is greater than the first number of bits; and        dispatching the native instruction to a processor for execution.     
     
     
       52. The method of  claim 51  wherein the retrieving the abbreviated instruction step retrieves the abbreviated instruction from instruction memory, the instruction memory dimension depends on the size of the abbreviated instruction rather than the size of a native instruction. 
     
     
       53. The method of  claim 51  further comprising the following steps, wherein the following steps occur before the retrieving the abbreviated instruction step, the following steps comprising:
   converting a set of native instructions defining an application program into the abbreviated instruction set; and        storing the abbreviated instruction set.     
     
     
       54. The method of  claim 51  wherein the retrieved bits are retrieved from a translation memory entry, wherein the combining step further comprises:
   applying a style to determine how to map bit positions in the abbreviated instruction to bit positions in the native instruction and how to map bit positions in the translation memory entry to bit positions in the native instruction.     
     
     
       55. The method of  claim 51  wherein the address reference is an address reference to a translation memory, an entry in the translation memory containing the native instruction pattern of bits to be combined with the abbreviated instruction. 
     
     
       56. The method of  claim 51  wherein the abbreviated instruction includes at least one S/P bit, a multi- bit opcode field and a multi - bit translation memory address offset.   
     
     
       57. The method of  claim 56  further comprising:
   decoding the multi - bit opcode field.