Processor, compiler and compilation method Number:7,076,638 from the United States Patent and Trademark Office (PTO) owispatent

Title: Processor, compiler and compilation method

Abstract: In order to overcome the problem that conditionally executed instructions are executed as no-operation instructions if their condition is not fulfilled, leading to poor utilization efficiency of the hardware and lowering the effective performance, the processor decodes a number of instructions that is greater than the number of provided computing units and judges their execution conditions with an instruction issue control portion before the execution stage, Instructions for which the condition is false are invalidated, and subsequent valid instructions are assigned so that the computing units (hardware) is used efficiently. A compiler performs scheduling such that the number of instructions whose execution condition is true does not exceed the upper limit of the degree of parallelism of the hardware. The number of instructions arranged in parallel at each cycle may exceed the degree of parallelism of the hardware.

Patent Number: 7,076,638 Issued on 07/11/2006 to Heishi,   et al.

---

Inventors:	Heishi; Taketo (Osaka, JP); Takayama; Shuichi (Hyogo, JP); Tanaka; Tetsuya (Osaka, JP); Ogawa; Hajime (Kyoto, JP); Higaki; Nobuo (Hyogo, JP)
Assignee:	Matsushita Electric Industrial Co., Ltd. (Osaka, JP)
Appl. No.:	246482
Filed:	September 19, 2002

---

Foreign Application Priority Data

---

Sep 20, 2001 [JP]			2001-286393

Current U.S. Class:	712/214
Current International Class:	G06F 9/30 (20060101)
Field of Search:	712/214 717/154

---

References Cited [Referenced By]

---

U.S. Patent Documents

	5295249		March 1994		Blaner et al.
	5355460		October 1994		Eickemeyer et al.
	5440703		August 1995		Ray et al.
	5459844		October 1995		Eickemeyer et al.
	5598546		January 1997		Blomgren
	5600806		February 1997		Brown et al.
	5870582		February 1999		Cheong et al.
	5872990		February 1999		Luick et al.
	5961629		October 1999		Nguyen et al.
	6115806		September 2000		Yoshida
	6253371		June 2001		Iwasawa et al.
	6269439		July 2001		Hanaki
	6367070		April 2002		Haghighat et al.

Foreign Patent Documents

	1117166		Feb., 1996		CN
	1206145		Jan., 1999		CN
	1 011 052		Jun., 2000		EP
	62-65133		Mar., 1987		JP
	64-082131		Mar., 1989		JP
	09-265400		Oct., 1997		JP
	09-311786		Dec., 1997		JP
	10-27102		Jan., 1998		JP
	11-296377		Oct., 1999		JP
	2000-3279		Jan., 2000		JP
	2000-284970		Oct., 2000		JP
	2001-236227		Aug., 2001		JP

Other References

Suresh, P., et al., "PERL A Registerless Architecture", High Performance Computing, 1998, 5th International Confernce On Madras, India Dec. 17-20, 1998, Los Angeles, CA, USA, pp. 33-40, XP 010317631. cited by other . Sato, T., et al., "In Search Of Efficient Reliable Processor Design", Parallel Processing, International Conference, Sep. 3-7, 2001, Piscataway, NJ, USA, pp. 525-532, XP010558340. cited by other.

Primary Examiner: Coleman; Eric
Attorney, Agent or Firm: McDermott Will & Emery LLP

---

Claims

---

What is claimed is:

1. A processor comprising: a plurality of registers each for storing a flag designating true or false; an instruction fetching unit for fetching a plurality of instructions in parallel, each of the plurality of instructions fetched in the instruction fetching unit having an operation code field designating an operation to be executed and an execution condition field designating a register of the plurality of registers to be accessed by the operation, wherein an operation designated by an operation code field of a specific instruction fetched in the instruction fetching unit is executed only when a value determined in response to a flag stored in a specific register of the plurality of registers, the specific register designated by an execution condition field of the specific instruction, designates true; a plurality of decoders each for decoding an instruction of the plurality of instructions fetched in the instruction fetching unit; a first executing unit for executing an operation designated by an operation code field of an instruction of the plurality of instructions fetched in the instruction fetching unit in response to a decoded result in a decoder of the plurality of decoders; and an instruction issue controller for referencing a flag stored in a first register of the plurality of registers, the first register designated by an execution condition field of a first instruction of the plurality of instructions fetched in the instruction fetching unit, and for controlling the first executing unit to execute an operation designated by an operation code field of a second instruction of the plurality of instructions fetched in the instruction fetching unit instead of an operation designated by an operation code field of the first instruction in response to a decoded result of the second instruction when a value determined in response to the flag stored in the first register designates false before a decoded result of the first instruction is issued to the first executing unit by the instruction issue controller.

2. The processor according to claim 1, wherein the instruction issue controller controls the first executing unit to execute the operation designated by the operation code field of the first instruction in response to the decoded result of the first instruction when the value determined in response to the flag stored in the first register designates true or when the value determined in response to the flag stored in the first register has not been fixed before the decoded result of the first instruction is issued to the first executing unit by the instruction issue controller.

3. The processor according to claim 2, wherein an executed result of the first executing unit is invalidated when both the value determined in response to the flag stored in the first register has not been fixed before the decoded result of the first instruction is issued to the first executing unit by the instruction issue controller and the value determined in response to the flag stored in the first register designates false after the decoded result of the first instruction is issued to the first executing unit by the instruction issue controller.

4. The processor according to claim 1, wherein the instruction issue controller further references a flag stored in a second register of the plurality of registers, the second register designated by an execution condition field of the second instruction, and an executed result of the first executing unit is invalidated when a value determined in response to the flag stored in the second register designates false after the decoded result of the second instruction is issued to the first executing unit by the instruction issue controller.

5. The processor according to claim 1, further comprising: a second executing unit for executing an operation designated by an operation code field of an instruction of the plurality of instructions fetched in the instruction fetching unit in response to a decoded result in a decoder of the plurality of decoders, wherein the number of the plurality of decoders is more than three, and wherein the instruction issue controller controls none of the first executing unit and the second executing unit to execute the operation designated by the operation code field of the first instruction when the value determined in response to the flag stored in the first register designates false before the decoded result of the first instruction is issued to the first executing unit by the instruction issue controller.

6. The processor according to claim 1, further comprising: a second executing unit for executing an operation designated by an operation code field of an instruction of the plurality of instructions fetched in the instruction fetching unit in response to a decoded result in a decoder of the plurality of decoders, wherein the number of the plurality of decoders is more than three, and wherein each of the plurality of instructions fetched in the instruction fetching unit further has a parallel execution boundary field designating an instruction group including at least one instruction of the plurality of instructions fetched in the instruction fetching unit to be executed in parallel, and a decoded result of a third instruction of the plurality of instructions fetched in the instruction fetching unit is issued to none of the first executing unit and the second executing unit by the instruction issue controller when a parallel execution boundary field of a fourth instruction designates a first instruction group which does not include the third instruction to be executed in parallel.

7. The processor according to claim 6, wherein the decoded result of the third instruction is issued to either the first executing unit or the second executing unit by the instruction issue controller when both each of at least one value determined in response to at least one flag stored in at least one register designated by execution condition fields of all instructions included in the first instruction group designates false before a decoded result of any instruction included in the first instruction group is issued to the first executing unit by the instruction issue controller and a parallel execution boundary field of a fifth instruction of the plurality of instructions fetched in the instruction fetching unit designates a second instruction group which includes the third instruction to be executed in parallel.

8. The processor according to claim 1, further comprising: a plurality of flag validity information units each for storing a value designating whether a flag stored in a corresponding one of the plurality of registers has been fixed or not, wherein the instruction issue controller controls the first executing unit to execute the operation designated by the operation code field of the second instruction both when the value determined in response to the flag stored in the first register designates false and when a value stored in a corresponding one of the plurality of flag validity information units to the first register designates that the flag stored in the first register has been fixed.

9. The processor according to claim 8, wherein the instruction issue controller controls the first executing unit to execute the operation designated by the operation code field of the first instruction both when the value determined in response to the flag stored in the first register designates true and when the value stored in the corresponding one of the plurality of flag validity information units to the first register designates that the flag stored in the first register has been fixed, or when the value stored in the corresponding one of the plurality of flag validity information units to the first register designates that the flag stored in the first register has not been fixed regardless of the value determined in response to the flag stored in the first register.

10. The processor according to claim 1, further comprising: a second executing unit for executing an operation in response to at least two operation code fields of at least two instructions of the plurality of instructions fetched in the instruction fetching unit; and an instruction linking unit for judging whether the at least two instructions can be replaced to a compound instruction or not, and for outputting a modified decoded result of the compound instruction instead of at least two decoded results of the at least two instructions when it is judged that the at least two instructions can be replaced to the compound instruction, wherein the number of the plurality of decoders is more than three, and wherein the instruction issue controller further references each of at least one flag stored in at least one register of the plurality of registers, the at least one register designated by at least two execution condition fields of the at least two instructions, and controls the second executing unit to execute an operation of the compound instruction in response to the modified decoded result and controls none of the first executing unit and the second executing unit to execute any operations designated by at least two operation code fields of the at least two instructions when each of at least one value determined in response to each of the at least one flag stored in each of the at least one register designates true before the modified decoded result is issued to the second executing unit by the instruction issue controller.

11. The processor according to claim 1, wherein the plurality of instructions fetched in the instruction fetching unit include a third instruction and a fourth instruction, both an execution condition field of the third instruction and an execution condition field of the fourth instruction designate a second register of the plurality of registers, and the instruction issue controller further references a flag stored in the second register only once in response to either a decoded result of the third instruction or a decoded result of the fourth instruction.

12. A processor comprising: a plurality of registers each for storing a flag designating true or false; an instruction fetching unit for fetching a plurality of instructions in parallel, each of the plurality of instructions fetched in the instruction fetching unit having an operation code field designating an operation to be executed and an execution condition field designating a register of the plurality of registers to be accessed by the operation, wherein an operation designated by an operation code field of a specific instruction fetched in the instruction fetching unit is executed only when a value determined in response to a flag stored in a specific register of the plurality of registers, the specific register designated by an execution condition field of the specific instruction, designates true; a plurality of decoders each for decoding an instruction of the plurality of instructions fetched in the instruction fetching unit; a first executing unit for executing an operation in response to at least two operation code fields of at least two instructions of the plurality of instructions fetched in the instruction fetching unit; an instruction linking unit for judging whether the at least two instructions can be replaced to a compound instruction or not, and for outputting a modified decoded result of the compound instruction instead of at least two decoded results of the at least two instructions when it is judged that the at least two instructions can be replaced to the compound instruction; and an instruction issue controller for referencing each of at least one flag stored in at least one register of the plurality of registers, the at least one register designated by at least two execution condition fields of the at least two instructions, and for controlling the first executing unit to execute an operation of the compound instruction in response to the modified decoded result and for controlling none of the first executing unit and the second executing unit to execute any operations designated by at least two operation code fields of the at least two instructions when each of at least one value determined in response to each of the at least one flag stored in each of the at least one register designates true before the modified decoded result is issued to the second executing unit by the instruction issue controller.

13. A processor comprising: a plurality of registers each for storing a flag designating true or false; an instruction fetching unit for fetching a plurality of instructions in parallel, each of the plurality of instructions fetched in the instruction fetching unit having an operation code field designating an operation to be executed and an execution condition field designating a register of the plurality of registers to be accessed by the operation, wherein an operation designated by an operation code field of a specific instruction fetched in the instruction fetching unit is executed only when a value determined in response to a flag stored in a specific register of the plurality of registers, the specific register designated by an execution condition field of the specific instruction, designates true; a plurality of decoders each for decoding an instruction of the plurality of instructions fetched in the instruction fetching unit; a plurality executing units each for executing an operation designated by an operation code field of an instruction of the plurality of instructions fetched in the instruction fetching unit in response to a decoded result in a decoder of the plurality of decoders, where the number of the plurality of decoders is greater than the number of the plurality of executing units; and an instruction issue controller for controlling the plurality of executing units to execute in parallel, operations designated by operation code fields of selected instructions of the plurality of instructions fetched in the instruction fetching unit in response to decoded results of the selected instructions decoded in decoders of the plurality of decoders respectively, where the number of the selected instructions is the same as the number of the plurality of executing units.

---

Description

---

BACKGROUND OF THE INVENTION

The present invention relates to processors, compilers and compilation methods, and in particular to technology for improving performance by using computing units efficiently in parallel processing.

In recent years, higher functionality and higher speeds of products with microprocessors have brought about a need for microprocessors (referred to simply as "processors" in the following) having a high processing performance. In general, in order to increase the throughput of instructions, the pipeline approach is adopted, in which one instruction is broken down into several processing units (here referred to as "stages"), and a plurality of instructions are processed in parallel by executing each stage with separate pieces of hardware. In addition to spatially parallel processing as with the pipeline approach, higher performance is achieved by the VLIW (very long instruction word) approach or the superscalar approach in which temporal parallel processing is performed at the instruction level.

One major factor obstructing performance increases in processors is the overhead for branching processes. With this overhead, the penalty for instruction supply is larger, the more stages there are in the pipeline process. Furthermore, in parallel processing of instructions, the higher the degree of parallelism becomes, the higher is the frequency of branching instructions and the more manifest becomes the overhead.

As a conventional technology for countering this overhead, there is a conditional execution approach, according to which information indicating execution conditions is added to the instructions, and the operations indicated by the instructions are executed only when those conditions are satisfied. With this approach, condition flags corresponding to the execution conditions added to the instructions are referenced at execution time, and if the conditions are not fulfilled, then the execution result of the instruction is invalidated, that is, it is executed as a no-operation instruction.

For example, when the process flow including the conditional branch shown in FIG. 10 is notated in a format adding to the instructions information indicating an execution condition, then a program as shown in FIG. 11 results. In FIG. 11, C0 and C1 represent the conditions that are added to the instructions, and if the value of the condition flags corresponding thereto is true, then the instructions are executed, whereas if it is false, then the instructions are executed as no-operation instructions. In this example, first the comparison result of instruction 1 (comparison instruction) is stored in C0. At the same time, C1 is set to a condition that is opposite that of C0. Consequently, the operation of either instruction 2 or instruction 3 is actually executed, whereas the other one is executed as a no-operation instruction. As a result, a branching process is unnecessary, and the overhead of the branching process is countered.

In the above-described conventional conditional execution approach, if the condition is not satisfied, the corresponding instruction is performed as a no-operation instruction, and the operation is effectively not executed. Consequently, even though the two instructions are notated in parallel and use two computing units, actually only one computing unit can be effectively utilized in practice. As a result, there is the problem that the effective performance is lower than one would expect for the degree of parallelism with which the program is notated.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide a processor in which an effective utilization of hardware is achieved and performance is improved.

To attain these objects, in one aspect of the present invention, a processor includes an instruction supply means for supplying a plurality of instructions, each instruction including information specifying the instruction's operation and execution condition information specifying a condition indicating whether the instruction is executed, a decoding means for decoding the plurality of instructions, an instruction issue control means which references the condition specified by the execution condition information to determine an instruction or a set of instructions whose valid operation is executed, and an execution means for executing one or a plurality of operations based on the information specifying the operation of the instructions, wherein the instruction issue control means has the function to decide, by referencing the condition specified by the execution condition information, whether an instruction is a valid instruction that needs to be executed or an invalid instruction that does not need to be executed, to cause the deletion of an instruction that has been decided to be an invalid instruction before it is issued to the execution means, and to issue a valid instruction following that invalid instruction to the execution means instead of the invalid instruction. With this configuration, non-operation instructions are not executed when the condition of conditional instructions are not fulfilled, and the computing units in the execution means are effectively utilized by the subsequent instructions, so that the utilization efficiency of the computing units can be increased and the effective performance can be improved.

In another aspect of the present invention, a processor includes an instruction supply means for supplying a plurality of instructions, each instruction including information specifying an operation of the instruction, a decoding means for decoding the plurality of instructions, an instruction issue control means which determines an instruction or a set of instructions whose valid operation is executed, and an execution means for executing one or a plurality of operations based on the information specifying the operation of the instructions, wherein the instruction issue control means has the function to detect, from an instruction group decoded by the decoding means, a combination of a plurality of instructions whose function may be executable as a single instruction, and to link this plurality of instructions so that they are treated as a single instruction. Thus, instructions that were originally supposed to use a plurality of computing units in the execution means can be executed by a single computing unit, so that the utilization efficiency of the computing units can be increased and the effective performance can be improved.

In another aspect of the present invention, a compiler for converting source code of a program notated in a high-level language into executable code includes an instruction scheduling means for rearranging instructions in the source code such that a plurality of instructions to be executed in parallel are adjacent to one another, the instruction scheduling means including a condition exclusivity analysis means for analyzing whether it is possible that conditions for the execution of valid operations specified in each instruction are simultaneously satisfied, and an instruction rearrangement means for rearranging instructions such that a set of parallel executable instructions can be delimited for each cycle, wherein the instruction rearrangement means judges whether computation resources used by those of the instructions placed in one cycle whose valid operation is executed do not exceed a restriction of computing units with which a target machine is provided, and if the condition exclusivity analysis means has judged that the execution conditions of two instructions placed in that cycle cannot be satisfied simultaneously, then the instruction rearrangement means treats the two instructions as if only one of the two instructions uses the computation resources under a given condition. Thus, by considering the deletion of instructions, it becomes possible to arrange a number of instructions per cycle that is greater than the number of provided computing units, so that the effective performance can be improved.

In yet another aspect of the present invention, a compiler for converting source code of a program notated in a high-level language into executable code includes an instruction scheduling means for rearranging instructions in the source code such that a plurality of instructions to be executed in parallel are adjacent to one another, the instruction scheduling means including an instruction rearrangement means for rearranging instructions such that a set of parallel executable instructions can be delimited for each cycle, wherein the instruction rearrangement means detects a combination of instructions by which the function of a plurality of instructions can be executed in a single instruction, and treats this plurality of instructions as a single instruction that has bee linked together, to judge whether placement is possible in that cycle. Thus, by considering the deletion of instructions, it becomes possible to arrange a number of instructions per cycle that is greater than the number of provided computing units, so that the effective performance can be improved.

In yet another aspect of the present invention, a compiler for converting source code of a program notated in a high-level language into executable code includes an instruction scheduling means for rearranging instructions in the source code such that a plurality of instructions to be executed in parallel are adjacent to one another, the instruction scheduling means including a condition exclusivity analysis means for analyzing whether it is possible that conditions for the execution of valid operations specified in each instruction are simultaneously satisfied, and an instruction rearrangement means for rearranging instructions such that a set of parallel executable instructions can be delimited for each cycle, wherein the condition exclusivity analysis means generates, for instructions at the beginning each basic block and instructions that update any condition affecting validity of operation execution, tables that indicate the possibilities that condition flags are satisfied simultaneously at the respective times. Thus, the exclusivity of execution conditions among instructions can be analyzed by generating the necessary minimum information, and a reduction of the memory used by the compiler as well as the effect of a higher compilation speed can be achieved.

In yet another aspect of the present invention, a compilation method for converting source code of a program notated in a high-level language into executable code includes an instruction scheduling step for rearranging instructions in the source code such that a plurality of instructions to be executed in parallel are adjacent to one another, the instruction scheduling step including a condition exclusivity analysis step for analyzing whether it is possible that conditions for the execution of valid operations specified in each instruction are simultaneously satisfied, and an instruction rearrangement step for rearranging instructions such that a set of parallel executable instructions can be delimited for each cycle, wherein the instruction rearrangement step comprises an arrangement possibility judgment step that judges whether computation resources used by those of the instructions placed in one cycle whose valid operation is executed do not exceed a restriction of computing units with which a target machine is provided, and if the condition exclusivity analysis step has judged that the execution conditions of two instructions placed in that cycle cannot be satisfied simultaneously, then the arrangement possibility judgment step treats the two instructions as if only one of the two instructions uses the computation resources.

In yet another aspect of the present invention, a recording medium storing a program for converting source code of a program notated in a high-level language into executable code including an instruction scheduling step for rearranging instructions in the source code such that a plurality of instructions to be executed in parallel are adjacent to one another, the instruction scheduling step including a condition exclusivity analysis step for analyzing whether it is possible that conditions for the execution of valid operations added to each instruction are simultaneously satisfied, and an instruction rearrangement step for rearranging instructions such that a set of parallel executable instructions can be delimited for each cycle, wherein the instruction rearrangement step comprises an arrangement possibility judgment step that judges whether computation resources used by those of the instructions placed in one cycle whose valid operation is executed do not exceed a restriction of computing units with which a target machine is provided, and if the condition exclusivity analysis step has judged that the execution conditions of two instructions placed in that cycle cannot be satisfied simultaneously, then the arrangement possibility judgment step treats the two instructions as if only one of the two instructions uses the computation resources.

BRIEF DESCRIPTION OF THE DRAWINGS

FIGS. 1A, 1B and 1C illustrate the structure of instructions executed by a processor in accordance with Embodiment 1 of the present invention.

FIGS. 2A and 2B illustrate the principle of how instructions are supplied and issued in that processor.

FIG. 3 is a block diagram illustrating the hardware configuration of the processor.

FIG. 4 is a block diagram illustrating the instructions register of the processor and its environs.

FIG. 5 illustrates the circuit configuration of the instruction issue control portion of the processor and its environs.

FIG. 6 illustrates the timing of the pipeline when a sequence of instructions is executed on the processor.

FIG. 7 shows a portion of a program including conditionally executed instructions.

FIG. 8 is a block diagram showing the instruction register environs of a processor having a conventional instruction issue control portion.

FIG. 9 illustrates shows the program when the process of the program in FIG. 7 is carried out on a processor having a conventional instruction issue control portion.

FIG. 10 shows a process flow including a conditional branch.

FIG. 11 shows a program in which the process flow in FIG. 10 is annotated in conditional execution format.

FIG. 12 is a block diagram illustrating the configuration of a compiler according to Embodiment 2 of the present invention and related data.

FIG. 13 is a flowchart of the procedure performed by the condition exclusivity analysis portion of that compiler.

FIG. 14 is a flowchart of the procedure performed by the compiler to detect execution condition exclusivity between two instructions.

FIG. 15 shows an example of assembler code.

FIG. 16 shows a condition exclusivity information table corresponding to instruction 2 in the assembler code of FIG. 15.

FIG. 17 is a dependency graph corresponding to FIG. 15.

FIG. 18 is a flowchart of the procedure performed by the instruction rearrangement portion in the compiler.

FIG. 19 shows an example of assembler code.

FIG. 20 is a dependency graph corresponding to FIG. 19.

FIG. 21 shows the executable code corresponding to FIG. 19.

FIG. 22 shows an example of executable code resulting when the code in FIG. 19 is scheduled with a conventional compiler.

FIG. 23 illustrates the circuit configuration of the instruction issue control portion and environs of a processor according to Embodiment 3 of the present invention.

FIG. 24 shows a portion of a program including conditional instructions.

FIG. 25 is a flowchart of the procedure performed by the instruction rearrangement portion in a compiler according to Embodiment 4 of the present invention.

FIG. 26 shows an example of assembler code.

DETAILED DESCRIPTION OF THE INVENTION

Referring to the accompanying drawings, the following is a detailed explanation of embodiments of processors, compilers and compilation methods in accordance with the present invention.

EMBODIMENT 1

Processor

Outline of Instruction Format and Architecture

First, the structure of instructions decoded and executed by the processor in accordance with the present invention is explained with FIG. 1A, 1B and 1C. FIGS. 1A to 1C illustrate the instruction format of the processor. The instructions for this processor have a fixed length of 32 bit, and each instruction includes one bit of parallel execution boundary information (E: end bit) 10. This information indicates whether there is a boundary of parallel execution between that instruction and the instruction that follows. More specifically, if the parallel execution boundary information E is "1," then there is a boundary of parallel execution between that instruction and the instruction that follows, and if the parallel execution boundary information E is "0," then there is no boundary of parallel execution between that instruction and the instruction that follows. An explanation about how this information is utilized follows below.

Each instruction also has three bits of execution condition information (P: predicate) 11. This execution condition information P specifies one of the eight condition flags C0 to C7 (311) in FIG. 5 (explained below) as the condition flag storing the condition for executing that instruction. If the value of the condition flag specified by the execution condition information P is "1," then the operation specified by that instruction is executed, and if the value of the condition flag is "0," then the operation is not executed.

The operation is specified by the remaining 28 bits, that is, the entire length of the instructions except the parallel execution boundary information E and the execution condition information P. More specifically, the fields "Op1," "Op2," and "Op3" specify an operation code indicating the kind of operation, the field "Rs" specifies the register number of the register serving as the source operand, and "Rd" specifies the register number of the register serving as the destination operand. Moreover, the field "imm" specifies a constant operand for computation. The field "disp" specifies a displacement.

Next, using FIG. 2A and FIG. 2B, an outline of the architecture of the processor is explained. The processor is based on the premise of static parallel scheduling.

As shown in FIG. 2A, instructions are supplied in packets of four instructions, each with a fixed length of 128 bit per cycle, as instruction supply portions (referred to as "packets" in the following). As shown in FIG. 2B, in one cycle, the instructions up to a boundary for parallel execution (referred to as "execution units" in the following) are executed simultaneously. That is to say, in each cycle, the instructions up to the instruction whose parallel execution boundary information E is "1" are executed in parallel. Instructions that have been supplied but not executed remain in the instruction buffer, and are executed in one of the following cycles.

That is to say, with this architecture, instructions are supplied in packet units of fixed length, and based on statically determined information, a suitable number of instructions corresponding to the degree of parallelism is issued in each cycle. With this approach, the no-operation instructions (nop instructions) that occurred with the VLIW approach of ordinary fixed length instructions are completely eliminated, and the code size can be reduced.

Hardware Configuration of the Processor

FIG. 3 is a block diagram illustrating the hardware configuration of a processor in accordance with the present invention. This processor is a parallel execution processor having two computing units, and is broadly speaking configured of an instruction supply portion 20, a decoding portion 30 and an execution portion 40.

The instruction supply portion 20 supplies groups of instructions from an external memory (not shown in the drawings), which it outputs to the decoding portion 30, and includes an instruction fetching portion 21, an instruction buffer 22 and an instruction register 23.

The instruction fetching portion 21 fetches blocks of instructions from the external memory (not shown in the drawings) via a 32 bit IA (instruction address) bus and a 128 bit ID (instruction data) bus, and holds them in an internal instruction cash, while it supplies the instruction group corresponding to the address given out by the PC (program counter) portion 42 to the instruction buffer 22.

The instruction buffer 22 is provided with two buffers of 128 bit, and is used to accumulate the instructions supplied by the instruction fetching portion 21. Packets are supplied from the instruction fetching portion 21 to the instruction buffer 22 in units of 128 bit. The instructions accumulated in the instruction buffer 22 are output to the appropriate registers of the instruction register 23.

The instruction register 23 is made of four 32 bit registers 231 to 234, and its purpose is to hold the instructions that are sent from the instruction buffer 22. The instruction register 23 and its environs are shown in more detail in another drawing.

The decoding portion 30 decodes the instructions held by the instruction register 23 and outputs a control signal depending on the decoding result to the execution portion 40. Broadly speaking, the decoding portion 30 is made of an instruction issue control portion 31, an instruction decoder 32 and an instruction invalidation method selection portion 38.

The instruction issue control portion 31 references the execution condition information P in the instructions held in the four registers 231 to 234 of the instruction register 23 as well as the corresponding condition flags, and performs a process of effectively deleting the instructions for which the value of the condition flag is false. However, this is limited to those cases in which the decoding portion 30 is selected by the invalidation method selection portion 38. Furthermore, the instruction issue control portion 31 references the parallel execution boundary information E in the instructions, and performs a control to the effect that for those instructions that exceed the boundary of a parallel execution, an invalidation of that instruction is issued. The operation of the instruction issue control portion 31 is explained in more detail further below with reference to another drawing.

The instruction decoder 32 is a device that decodes the instruction group stored in the instruction register 23, and is made of a first instruction decoder 33, a second instruction decoder 34, a third instruction decoder 35 and a fourth instruction decoder 36. These decoders 33 to 36 in principle decode one instruction per cycle, and give out control signals to the execution portion 40. Furthermore, constant operands placed inside instructions are transferred from the instruction decoders to the data bus 48 of the execution portion 40.

The instruction invalidation method selection portion 38 selects whether instructions for which the condition flag is false and whose execution is not necessary are invalidated by the decoding portion 30 or whether they are invalidated by the execution portion 40. More specifically, if in the condition flag validity information 312 (see FIG. 5) of the later-explained instruction issue control portion 31 the condition flag of that instruction is valid, that is, it is indicated as finalized, then the deletion of invalid instructions is performed with the decoding portion 30, and if not, then the writing of the execution result of that instruction is invalidated with the write control portion 46 of the execution portion 40.

The execution portion 40 is a circuit unit that executes maximally two operations in parallel, based on the decoding result of the decoding portion 30, and includes an execution control portion 41, a PC portion 42, a register file 43, a first computing unit 44, a second computing unit 45, a write control portion 46, an operand access portion 47, and data buses 48 and 49.

The execution control portion 41 is the generic term for all control circuitry and wiring that control the structural elements 42 to 49 of the execution portion 40 based on the decoding result of the decoding portion 30, and includes circuitry for timing control, operation enable/disable control, status management and interrupt control.

The PC portion 42 outputs the address of the external memory (not shown in the drawings) at which the next instruction to be decoded and executed is located to the instruction fetching portion 21 in the instruction supply portion 20.

The register file 43 is made of sixty-four 32-bit registers (R0 to R63). The values stored in these registers are transferred over the data bus 48 to the first computing unit 44 and the second computing unit 45, based on the decoding result of the instruction decoder 32, and after they have been used there for computation or merely passed through, they are sent over the data bus 49 to the register file 43 or the operand access portion 47.

The first computing unit 44 and the second computing unit 45 each incorporate a multiplier or an ALU for performing an arithmetic or logical computation on two 32-bit words, and a barrel shifter for shifting operations, and perform computations under the control of the execution control portion 41.

If the instruction invalidation method selection portion 38 has selected invalidation of an instruction with the execution portion 40, then the write control portion 46 performs a control to the effect that the execution result of that instruction is not written into the register file 43 when the condition flag of that instruction is false. Thus, the result is the same as if that instruction had been executed as a no-operation instruction (nop instruction).

The operand access portion 47 is the circuitry for the transfer of operands between the register file 43 and the external memory (not shown in the drawings). More specifically, when for example "ld" (load) is put in an instruction as the operation code, then the data of one word (32 bit) placed in the external memory is loaded through the operand access portion 47 to the register specified by the register file 43, or when "st" (store) is put as the operation code, then the storage value of the register specified by the register file 43 is stored in the external memory.

As shown in FIG. 3, the PC portion 42, the register file 43, the first computing unit 44, the second computing unit 45, the write control portion 46 and the operand access portion 47 are connected by a data bus 48 (L1 bus, R1 bus, L2 bus and R2 bus) and a data bus 49 (D1 bus and D2 bus). It should be noted that the L1 bus and the R1 bus are connected to the two input ports of the first computing unit 44, the L2 bus and the R2 bus are connected to the two input ports of the second computing unit 45, and the D1 bus and the D2 bus are respectively connected to the output ports of the first computing unit 44 and the second computing unit 45.

Configuration of the Instruction Register 23 and its Environs and Operation of the Instruction Issue Control Portion 31

FIG. 4 is a block diagram illustrating the configuration of the configuration of the instruction register 23 and its environs. In FIG. 4, the dotted arrows represent control signals.

The instruction register 23 is made of four 32-bit registers, namely an A register 231, a B register 232, a C register 233 and a D register 234. The instruction register 23 supplies the instructions from the instruction buffer 22.

The first to fourth instruction decoders 33, 34, 35 and 36 respectively receive 32-bit instructions as input, decode them, and output control signals regarding the operation of the instructions, and output constant operands put into the instructions. The numerals 50 and 51 in FIG. 4 denote constant operands of instructions whose execution has been finalized.

Furthermore, 1-bit no-operation instruction flags are input into the second to fourth instruction decoders 34, 35 and 36 as control signals. When these flags are set to "1," the decoders output control signals corresponding to a no-operation instruction. That is to say, by setting the no-operation instruction flags, the decoding with the corresponding instruction decoder can be invalidated.

The instruction issue control portion 31 references the information in the instructions stored in the instruction register 23, and performs the generation of the no-operation instruction flags for invalidating the decoding of the instructions beyond the boundary of parallel execution, the control of the execution instruction selectors 371 and 372 for selecting the valid instructions for which the execution condition is true and whose operation should be executed with the execution portion 40, and the control of the execution instruction selectors 373 and 374 for selecting the control signals corresponding thereto.

FIG. 5 illustrates the configuration of the command issue control portion 31 of this processor and peripheral circuitry thereof The command issue control portion 31 references the parallel execution boundary information E in the instructions, and decides up to which instruction should be issued in that cycle. Then, by setting the no-operation command flag of the instruction decoder corresponding to the instructions that are not issued during that cycle to "1," the output to that decoder is set to a control signal corresponding to a no-operation instruction. The generation of the no-operation instruction flag can be realized by simple logical circuits (OR gates) 314 and 315 as shown on the right-hand side of the instruction issue control portion 31 in FIG. 5. At the same time, information about how many instructions have remained without being issued is transmitted to the instruction buffer 22.

Explaining this in more detail, if the parallel execution boundary information E of the instruction in the A register 231 is "1," then the decoding of the second, third and fourth instruction decoders 34, 35 and 36 is invalidated, If the parallel execution boundary information E of the instruction in the B register 232 is "1," then the decoding of the third and fourth instruction decoders 35 and 36 is invalidated. And if the parallel execution boundary information E of the instruction in the C register 233 is "1," then the decoding of the fourth instruction decoders 36 is invalidated.

Furthermore, the instruction issue control portion 31 references the execution condition information P in each instruction, and controls the execution instruction selectors 371 to 374 in FIG. 4 such that instructions for which the condition flag is false, that is, instructions that need not be executed, are effectively deleted. In this processor, a maximum of four instructions are decoded in each cycle, but in practice, it is mostly two instructions at best whose operations are executed. Thus, the problem that if the execution condition is false, a no-operation command is executed by the execution portion 40, leading to poor utilization efficiency of the computing units 44 and 45, can be solved.

In order to realize this, the instruction issue control portion 31 is provided with an execution instruction selection control portion 313. The execution instruction selection control portion 313 looks up to which of the eight condition flags (C0 to C7) 311 the execution condition information P specified in the instruction corresponds, and thus detects the instructions for which it is not necessary to execute the operation, and not selecting these instructions, controls the execution instruction selectors 371 to 374 such that the next valid instruction is selected. The not selected instructions are effectively deleted. The condition flags 311 include eight 1-bit registers C0 to C7, which are specified by decoding the 3-bit execution condition information P within each instruction. It should be noted that the value of the condition flag C7 is always "1," and for instructions that are always executed, C7 is specified as the execution condition. The specification of C7 can be left out in the notation of the program.

However, in instructions in which the condition flag is updated, the execution stage, that is, the execution portion 40, is where the condition flag is finalized, so that if in the previous cycle an instruction is executed in which a certain condition flag is updated, this condition flag is not finalized in the decoding stage, that is, the decoding portion 30, of the following cycle, and it cannot be judged whether the instruction can be deleted or not. The condition flag validity information 312 is provided in order to detect this situation.

The condition flag validity information 312 holds for each condition flag one bit indicating whether the value of that condition flag is valid or not. When it is judged by the decoding portion 30 that an instruction is executed that updates a certain condition flag, then the validity information for that condition flag is set to "0," and when the value of that condition flag has been updated by the execution portion 40, then the validity information of that condition flag is set to "1."

After the execution condition information P of each instruction has been referenced, the instruction issue control portion 31 references the condition flag validity information 312, and detects whether the values of the condition flags corresponding to the execution conditions are valid or not. Then, if they are not valid, that is, if the corresponding bit of the condition flag validity information 312 is "0," then the corresponding instruction is not deleted. The corresponding instruction is issued to the execution portion 40 as it is, and the writing of the execution result of that instruction is invalidated if necessary, after the condition flag has been finalized.

If the value of the condition flag is valid, that is, if the corresponding bit of the condition flag validity information 312 is "1," then the one bit in the condition flags 311 specified by the execution condition information P of that instruction is referenced, and if that value is "1," then that instruction is issued as it is to the execution portion 40, and if that value is "0," then the execution instruction selectors 371 to 374 are controlled such that the instruction is effectively deleted.

This means, that if the execution condition information P of a certain instruction is "0," and if the corresponding condition flag is updated in the directly preceding instruction, then the execution result of that instruction is invalidated in the execution portion 40, and if not, then the instruction is effectively deleted in the decoding portion 30.

FIG. 6 shows the timing of the pipeline process when executing a specific sequence of instructions. Here, it is assumed that, starting at the top, three instructions are executed one by one. The first instruction is a comparison instruction that compares the content of register R0 with the content of register R1, and sets the condition flag C0 to "1" if the two are identical, and sets it to "0" if not. The next instruction is a subtraction instruction that subtracts the content of register R2 from the content of register R3 if the content of the condition flag C0 is "1," and writes the result into register R3. The last instruction is an addition instruction that adds the content of register R4 to the content of register R5 if the content of the condition flag C0 is "1," and writes the result into register R5.

In FIG. 6, the timing of the instruction fetch stage (IF), the decoding stage (DEC) and the execution stage (EX) of the various instructions is shown to the right of the instructions. Here, it is assumed that the result of the first comparison instruction is false, that is, that C0 has turned "0."

As can be seen in FIG. 6, the decoding stage (DEC) of the first comparison instruction detects that it is an instruction that updates C0, the validity information of C0 is set to "0," and after the comparison result has been finalized, the execution stage (EX) sets the validity information of C0 to "1."

The subsequent subtraction instruction and addition instruction are both instructions that are executed with C0 as the condition, but because for the subtraction instruction that immediately follows the comparison instruction the value of C0 is not valid at the decoding stage (DEC), the instruction is not deleted, but is issued to the execution stage (EX), and the execution result is invalidated at that stage. On the other hand, for the addition instruction, the value of C0 has been finalized at the decoding stage (DEC), so that the instruction is effectively deleted by the decoding stage (DEC), and is not issued to the execution stage (EX). In this case, the empty computing unit can be utilized for the instruction following the addition instruction.

If instructions are not issued and remain after the invalidation of the instruction by the above-described control, then the instruction issue control portion 31 transmits the number of remaining instructions to the instruction buffer 22, and these instructions are not invalidated in the instruction buffer 22, but transferred again to the instruction register 23 in the next cycle.

Thus, taking an instruction format as shown in FIG. 1, and adopting the configuration shown in FIG. 4 and FIG. 5, an instruction issue control that advantageously utilizes the computing units can be carried out.

Operation of the Processor

The following is an explanation of the operation of the processor of the present embodiment for the decoding and execution of specific instructions.

FIG. 7 shows a portion of a program including conditional execution. This program has five instructions, whose content is given in mnemonic notation. In particular, the mnemonic "add" represents the addition of a constant or the storage value of a register to the storage value of a register, the mnemonic "sub" represents the subtraction of a constant or the storage value of a register from the storage value of a register, the mnemonic "st" represents the transfer of the storage value of a register into memory, and the mnemonic "mov" represents the transfer of a constant or the storage value of a register into a register.

Furthermore, "Rn (n=0 . . . 63)" indicates one of the registers in the register file 43. The parallel execution boundary information E of each instruction is given as "0" or "1." Moreover, condition flags specified by the execution condition information P are given in square brackets "[ ]" preceding the instructions. Instructions for which no condition flags are given are always executed.

The following is an explanation of the operation of this processor for each execution unit. It is assumed that at the beginning, the value of the condition flag C0 has been finalized to "1" and the value of C1 to "0."

Execution Unit 1

A packet including instruction 1, instruction 2, instruction 3 and instruction 4 is supplied from the external memory, and the instructions are transferred to the instruction register 23. Then, the instruction issue control portion 31 references the parallel execution boundary information E of each instruction. In this case, the parallel execution boundary information of instruction 3 is "1," so that the decoding result of the fourth instruction decoder 36 is invalidated, that is, it is set to a no-operation instruction.

Next, the instruction issue control portion 31 references the execution condition information P of each instruction. The execution condition flag of instruction 1 is C0, and the value of C0 has been finalized to "1," so that the selection of the operands is controlled by the execution instruction selector 371 such that instruction 1 is executed as the first instruction, and the execution instruction selector 373 is controlled such that the decoding result is selected. Next, the execution condition flag of instruction 2 is C1, and the value of C1 has been finalized to "0," so that instruction 2 is effectively deleted, and its operation is not executed. Then, since the following instruction 3 is always executed, the selection of the operand is controlled by the execution instruction selec