Abstract:
A LIW processor comprises multiple execution units. The multiple execution units of the processor are divided into groups, and an input instruction word can contain instructions for one execution unit in each of the groups. The processor is optimized for use in signal processing operations, in that the multiple execution units of the processor are divided into groups which do not place significant restrictions on the desirable uses of the processor, because it has been determined that, in signal processing applications, it is not usually necessary for certain execution units to operate simultaneously. These execution units can therefore be grouped together, in such a way that only one of them can operate at a particular time, without significantly impacting on the operation of the device. An array is formed from multiple interconnected processors of this type.

Description:
This application is a continuation of and claims priority from U.S. patent application Ser. No. 11/293,845 filed Dec. 2, 2005 now abandoned which claims priority from British Patent Application No. 0426606.0 filed on Dec. 3, 2004, the subject matter of these applications are herein incorporated by reference in their entirety. 
    
    
     BACKGROUND 
     This invention relates to a processor architecture, and in particular to a processor architecture which is particularly useful in signal processing applications. 
     Modern high-performance wireless communications systems require digital processors which can provide billions of compute operations per second to achieve acceptable performance, for example to carry out operations such as filtering, equalisation and decoding functions. Increasingly these very high processing demands are satisfied by the use of multiple execution units (such as arithmetic logic units (ALUs), multipliers, address generators etc.) which can operate in parallel within a single processor cycle, and can thus increase the aggregate number of operations which can be completed per cycle. 
     One architectural approach which has been developed, in order to allow parallel operation of multiple execution units, is the Long Instruction Word (LIW) architecture. In this approach, instructions for each of a number of execution units are concatenated into one “long instruction word” which can be executed in a single processor cycle. Typically, in implementations of this approach, a bit field within the long instruction is reserved for an instruction for each of the execution units, regardless of whether a particular execution unit will be active within any one processor cycle. This has the disadvantageous effect that it creates excessively long instruction words, which can contain a lot of redundant information for execution units that are not active. The end result is a larger and more costly design. 
     SUMMARY OF THE INVENTION 
     The present invention relates to an alternative implementation of an LIW processor. 
     According to a preferred embodiment of the present invention, there is provided a processor which comprises multiple execution units. The multiple execution units of the processor are divided into groups, and an input instruction word can contain instructions for one execution unit in each of the groups. 
     In a further preferred embodiment of the invention, the processor is optimised for use in signal processing operations, in that the multiple execution units of the processor are divided into groups which do not place significant restrictions on the desirable uses of the processor. That is, it has been determined that, in signal processing applications, it is not usually necessary for certain execution units to operate simultaneously. 
     These execution units can therefore be grouped together, in such a way that only one of them can operate at a particular time, without significantly impacting on the operation of the device. 
     According to a further aspect of the present invention, there is provided an array, comprising a plurality of interconnected processors, wherein each of the processors comprises multiple execution units as defined above. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       For a better understanding of the present invention, and to show how it may be put into effect, reference will now be made to the accompanying drawings, in which: 
         FIG. 1  is a block schematic diagram of a processor array according to an aspect of the present invention; 
         FIG. 2  is a block schematic diagram of a processor within the processor array of  FIG. 1 , according to another aspect of the present invention; 
         FIG. 3  is an overview of the format of an instruction word for use in the processor of  FIG. 2 ; 
         FIG. 4  illustrates in more detail the format of a part of the instruction word shown in  FIG. 3 ; 
         FIG. 5  illustrates the operation of a second part of the instruction word shown in  FIG. 3 ; 
         FIG. 6  illustrates the operation of a third part of the instruction word shown in  FIG. 3 . 
         FIG. 7  illustrates operand values and actions. 
         FIG. 8  illustrates a branch destination instruction at a word boundary. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  is a block schematic diagram of a processor array, as generally described in WO02/50624. The array is made up of array elements  20 , which are interconnected by buses and switches. 
     The array architecture includes first bus pairs  30 , shown running horizontally in  FIG. 1 , each pair including a respective first bus  32  carrying data from left to right in  FIG. 1  and a respective second bus  36  carrying data from right to left. 
     The array architecture includes second bus pairs  40 , shown running vertically in  FIG. 1 , each pair including a respective third bus  42  carrying data upwards in  FIG. 1  and a respective fourth bus  46  carrying data downwards. 
     In  FIG. 1 , each diamond connection  50  represents a switch, which connects an array element  20  to a respective bus  32 ,  36 . The array further includes a switch matrix  55  at each intersection of a first and second bus pair  30 ,  40 . The data buses, and the switches and switch matrices, therefore allow data to be switched from one array element to another for processing, as required. 
     In this embodiment of the invention, at least some of the array elements  20  take the form of processors, as shown in more detail in  FIG. 2 . In accordance with this illustrated embodiment of the present invention, the processors  20  are adapted to make them particularly suitable for use as array elements, although the invention is also applicable to individual processors. 
     The processor  20  includes a 64×64 bit instruction memory  60 , which contains instructions loaded into the memory to control the operation of the processor. In operation of the device, instructions are fetched from the instruction memory  60 , and passed to an instruction decoder  62 , where they are decoded to configure the datapaths and execution units in the processor. 
     In this illustrated embodiment, the processor comprises six execution units. The first available execution unit is a first Arithmetic Logic Unit (ALU)  64 , which can perform a number of arithmetic and logical operations. 
     The second available execution unit is a communications unit  66 , which is connected to the input communications bus  68  and the output communications bus  70 , and is able to perform “put” and “get” operations to move data to and from the external communications buses  68 ,  70 , and is also able to move data to and from the 15×16 bit data registers  84 . The registers  84  are connected to the execution units by means of a data bus  85 . 
     In this illustrated embodiment, the communications unit  66  is thereby optimised to support the processing performed in the array, whereby data flows from one processor  20  to another, with parts of the processing being performed at each stage. 
     The third available execution unit is a combined Memory Access Unit (MAU)/second ALU  72 , which performs a variety of load and store operations over a bus  74  to a 64×32 bit data memory  76 , and also provides a subset of the ALU operations performed by the first ALU  64 . 
     The fourth available execution unit is a branch unit  78 , which performs a number of conditional and unconditional branch operations. 
     The fifth available execution unit is a Multiplier Accumulator (MAC) Unit  80 , which performs a variety of multiply and multiply accumulate operations with various bit widths. In an alternative embodiment of the invention, this unit may be replaced by a simpler Multiply unit. 
     In this illustrated embodiment of the invention, there is a sixth available execution unit in the form of an Application Specific Unit (ASU)  82 . More specifically, the ASU  82  is adapted to perform a number of highly specialised operations for wireless signal processing applications, such as complex spread and complex despread, in order to support CDMA transmit and receive functionality. In an alternative embodiment of the invention, this unit may be omitted. 
     As is conventional, in general each execution unit is able to perform one operation in one clock cycle. However, The first ALU  64  is also able to perform a shift operation on the first operand of the basic arithmetic or logical operations. Thus, in this special case, two instructions can effectively execute simultaneously on that one execution unit. 
     Analysis of a wide range of signal processing applications has now led to the conclusion that it is not necessary for all of the execution units to be able to operate simultaneously. In this illustrated embodiment of the invention, the execution units are clustered into three groups, each controlled by a separate instruction in a LIW instruction. 
     Specifically, in this illustrated embodiment, the first group  86  includes only the first Arithmetic Logic Unit (ALU)  64 ; the second group  88  is made up of the communications unit  66 , and the combined Memory Access Unit (MAU)/second ALU  72 ; and the third group  90  is made up the branch unit  78 , the Multiplier Accumulator (MAC) Unit  80 , and the Application Specific Unit (ASU)  82 . 
     According to this preferred embodiment of the invention, the device is then controlled such that any one, any two, or all three of the groups  86 ,  88 ,  90  can be active at any one time, but such that no more than one of the execution units within a group can be active at any one time. Further, the instruction format is such that this can be achieved efficiently in each case. 
     Specifically, a long instruction word can include an instruction LIW# 1  for the first group  86 , an instruction LIW# 2  for the second group  88 , and an instruction LIW# 3  for the third group  90 . 
       FIG. 3  shows the basic structure of a long instruction word instruction, which is also explained in more detail in  FIGS. 4 ,  5  and  6 . 
     Thus, the long instruction word first contains a short, 3 bit, bit sequence, which indicates whether the first group  86  is active in that processor cycle and, if so, indicates what class of operation is to be performed, so that execution units and datapaths can be configured. 
     As shown in  FIG. 4 , except in the case where the first three bits of byte  0  are 000, the first group  86  is active in that processor cycle and that three bit sequence indicates what operation is to be performed by the first Arithmetic Logic Unit (ALU)  64 . 
     Thus, when the value of the first three bits is within the range 001-100, the operation is an ALU operation with three operands, for example adding two values to give a result, with the three operands then being the register addresses of the two values to be added plus the register address in which the result is to be stored. 
     When the value of the first three bits is within the range 101-110, the operation is a load or store operation between the data memory and a nominated register or register pair. 
     When the value of the first three bits is 111, the operation is an ALU operation with two operands, one operand, or no operands, for example nop. 
     In any of these cases, the fourth bit then indicates whether an extension byte is to be used, as will be described in more detail below. The remaining four bits of byte  0 , and the eight bits of byte  1 , then indicate the operands or opcode values, depending on the value of the first three bits of byte  0 , as shown in  FIG. 4 . More specifically, where  FIG. 4  says that four of these bits represent an operand, they define the address, within the registers  84 , from which the first ALU  64  should retrieve the respective operand on which it will perform the defined operation. 
     When the first three bits of byte  0  are not 000, and thus the first group  86  is active in that processor cycle, the fourth bit must be set to “1”, and the extension byte must be used, if either the second group  88  or the third group  90  is active. 
     In the case where the first three bits of byte  0  are 000, the first group  86  is not active in that processor cycle, and byte  0  of the long instruction word then contains further short bit sequences, which indicate whether the second group  88  and third group  90  are active and, if so, what class of operation is to be performed. 
     Thus, there is a 3 bit sequence Lcode  2  relating to the second group  88 , as shown in  FIG. 5 , and a 2 bit sequence Lcode  3  relating to the second group  90 , as shown in  FIG. 6 . 
     If either or both of the second group  88  and third group  90  is active, then additional bytes LIW# 2   108  provide required information to allow the second group  88  to perform the intended function, and additional bytes LIW# 3   110  provide required information to allow the third group  90  to perform the intended function. 
     In the case where the first three bits of byte  0  are not 000, and an LIW# 1  instruction or “short” Memory Access operation is to be executed, the extension byte must be used if either or both of the second group  88  and third group  90  is active. If so, the extension byte carries Lcode 2  and Lcode 3 , and additional bytes LIW# 2   108  and LIW# 3   110  contain the required information to allow the relevant group to perform the intended function. 
     The extension byte also carries a 2-bit extension opcode “ex op”, which allows more possible instructions for ALU# 0 . The extension byte also includes a 1 bit flag, S. If set, the flag S indicates the presence of a shift operation on the ALU first operand. In that case, an additional byte following the extension byte is used to define whether the shift is logical or arithmetic, to the left or right, and how many bits are shifted (4-bit value). 
     The instruction set architecture supports the use of short constants (which, in this illustrated embodiment, are 4 bits long) and long constants (which, in this illustrated embodiment, are 16 bits long). As shown in  FIG. 4 , operands are generally 4 bits long, and one of these 4-bit operands normally refers to one of the registers  84 , but it can alternatively be used to indicate a 4-bit constant value. As illustrated in  FIG. 7 , where it is required to use a longer constant value, the operand value ‘15’ is used to direct the instruction decoder  62  to take the value in the 16-bit field  112 , which in that case appears at the end of the long instruction word instruction, as a 16-bit constant value. No useful information is therefore stored at the register address “15” (RI  5 ). Thus, writing to R 15  is used to indicate that an operation result should be discarded. 
     It can therefore be seen that the encoded instruction word is organized on byte boundaries. It can further be seen from  FIGS. 3-6  that an individual LIW instruction can be between 1 byte (the special case where none of the groups is active, and there are no LIW# 1 , no LIW# 2  and no LIW# 3  instructions) and 9 bytes in length. The instruction decoder  62  can therefore support any combination of instruction lengths within a single 64-bit instruction word and can tolerate LIW instructions which are contained in successive 64-bit instruction words. 
     In one embodiment of the invention, the length of any single LIW instruction cannot exceed 8 bytes. However, in other embodiments of the invention, this maximum length can be set to any desired value. This restriction results in a small number of combinations of LIW# 1 , LIW# 2  and LIW# 3  instructions which cannot be supported because they exceed this length. These illegal combinations are trapped by the Instruction Decode block  62 , resulting in the setting of an Illegal Instruction flag. Preferably, a compiler and assembler operating to support the processor architecture should also intercept disallowed instruction combinations at compile time. 
     There is one situation where alignment of LIW instructions must be restricted further, and that is in the case of branch destinations. The architecture relies on an instruction being decoded every processor cycle and therefore it is necessary that a branch destination is aligned at the beginning of a 64-bit instruction word. The instruction decoder  62  interprets an all-0 byte instruction (equivalent to “no LIW# 1 , no LIW# 2 , no LIW# 3 ”) as a “new line” and will fetch the next 64-bit instruction word. Thus the compiler and assembler can use the “new line” instruction at the end of an instruction sequence immediately prior to a branch destination, as illustrated in  FIG. 8 , in order to ensure 64-bit alignment of the instruction at the branch destination. 
     The long instruction word format therefore has the property that the length LIW inst  of the long instruction word is independent of the total number of execution units. Rather, it is determined by the maximum number of execution units which can be active in a single processor cycle. In the illustrated embodiment, a maximum of three execution units out of the six available can be active in a single LIW instruction/processor cycle, and the maximum length of a single LIW instruction is limited to 64 bits. 
     Further, the length LIW inst  of the long instruction word can vary, from one instruction to the next, depending on the number of active execution units within a given cycle. Thus, in many instruction cycles, it is likely that LIW inst  will be less than 64 bits. 
     Also, multiple instructions can be packed into the 64 bit wide instruction memory  60 , usually without the need for alignment to word boundaries, and the instructions can overrun a 64-bit instruction word boundary into the following instruction word. 
     Taken together, these factors mean that the result is object code which is compact and highly efficient in both high-throughput signal processing applications with multiple parallel operations per cycle and lower-throughput, more complex control operations. 
     This reduces hardware complexity significantly and, more importantly, reduces the complexity of the compiler/assembler required to support the architecture.