JPH0350295B2 - - Google Patents

Description

Claim 1: A method for implementing a conditional branch order of overlapping microcommands, comprising: starting execution of a first microcommand in an original order of microcommands during a first cycle; starting preparation for execution as a branch micro-instruction in the third and fourth cycle periods, respectively, starting execution of the second and third micro-instructions in the original order of said micro-instructions, and in the fifth cycle period beginning execution of a conditional branch micro-instruction; beginning execution of a micro-instruction ending in a sixth cycle period; and micro-instruction selected as the non-conditional branch micro-instruction during a seventh and eighth cycle period. initiating execution of the first and second microdirectives of the new sequence, respectively, and determining whether a condition of the conditional branch microdirective is true during the eighth cycle; initiating execution of a third micro-instruction in the new order of micro-instructions during a ninth cycle period if the condition is false; and canceling the new order of micro-instructions in the ninth cycle period if the condition is false; and then returning to the original order of the microinstructions.

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to information processing systems, and more particularly, to information processing systems in which the execution of a command is divided into a plurality of sub-operations that allow duplication without execution of consecutive commands; Concerning the pipelining of the implementation of the Directive. This technique is often used within information processing unit systems to increase the rate of command execution. The present invention reduces the delays encountered in executing conditional branch commands.

2 Description of Related Art Referring to FIG. 1, a typical information processing system is illustrated. The information processing system includes at least one central processing unit 10 (or 11).
and at least one input/output device 13 (or one
4), a memory unit 15, and a system bus 19 connecting a plurality of subsystems or units of the information processing system. A central processing unit processes the logic signals according to software and/or firmware instructions. The logic signals to be processed are typically stored in memory unit 1.
It is memorized in 5. Console unit 12
can be connected to a central processing unit, have a device and a storage command, initialize the system, and operate as a terminal during operation of the information processing system. The input/output unit interfaces the information handling unit to terminal units, mass storage units, communication units, and any other units coupled to the information handling system that exchange logic signals with the system. The present invention relates to the operation of a central processing unit, and to an apparatus and method for a more efficient implementation of a significant portion of a program for controlling the processing of information signals.

In an information processing system, such as the one shown in FIG. 1, the actual manipulation of information signals is performed under the control of a related set of instructions, commonly referred to as a program. These directives will be implemented in sequence. Turning now to FIG. 2a, the implementation of a series of commands in accordance with the related art is illustrated. first time range
During _T0 , instruction #1 is executed by the central processing unit subsystem. After the first command is executed, the next command in sequence, #2, is executed in the central processing unit subsystem during a second time period T ₀ .
After completion of command #2, the information processing unit executes within the third time range _T0 . In order to carry out the commands in sequence, the information processing unit requires a predetermined time range. If the length of execution time for a command is varied, a complex system within the central processing system is required to coordinate the exchange of information signals between the central processing system and other subsystems of the information processing system. equipment must be included. That is, the period of execution of the three commands is usually three times the basic time range. The basic time range must be sufficient to allow execution of the longest command in each command, unless implementation of the command is done using more elaborate techniques such as those described below. Must be. In order to quickly operate the information processing system,
Techniques have been devised to divide the execution of a command into multiple command segments. Command segments are components of micro-commands, and related groups of micro-commands execute macro-commands. If the devices executing the segments are properly organized, the execution of the commands can be performed in an overlapping manner. This technique is referred to as "pipelining" the execution of a set of instructions. Although execution of each pipelined command may take longer than execution of a non-pipelined command, the flow of commands is Executes faster than possible with non-pipelined directives. In Figure 2b, the division of the command into multiple segments is shown. It is to be understood that each segment relates to a group of independently operating elements within the central processing unit. Registers and gates enable the operations of groups of elements to perform particular segments according to principles well known in the art of information handling system design. Sub-time range t ₀ for each segment
must be long enough to allow all possible segments to be run in each device group.

Referring now to FIG. 2c, the resulting increase in the rate of execution of the order of instructions made possible through the use of pipelining techniques is illustrated.
Command #1 is now completed in a time span of T _{0 '} (as long as possible) equal to n times t 0, where t ₀ is the sub-interval required for the implementation of each command segment and n is the time span of each command. This is the number of command segments required for execution. The next order of commands, namely command #2, is
Starts after interval t ₀ after the start of command #1. The third command in the next sequence, command #3, begins at the subsequent interval t ₀ . Each command may incur an increase in time for its execution. However, once the first interval for completion of the first command is passed, the command is completed after each interval t ₀ .
Therefore, with respect to the order of commands, the implementation of the order can be accelerated, although each individual command will require additional time to implement.

Pipelining techniques can quickly implement an instruction sequence, but at the expense of conditionally occurring "branch" instructions within the instruction sequence. A branch command involves switching from one command sequence to a second command sequence. A conditionally occurring branch command involves testing a quantity for a predetermined condition. Based on the results of the test, the command sequence may continue in the current order, or the command sequence may jump, or bypass, to a new command sequence. Regarding the order of commands implemented as shown in Figure 2a,
Command #1 may be a command that tests a condition, and the particular next sequential command, illustrated by command #2, is determined by the result of command #1. In the case of pipeline execution of a command set as illustrated in FIG. 2c, results of conditional test execution cannot be obtained up to command segment D of command #1. However, command #2 has already begun to be executed under normal operating conditions, and command segments A and B of command #2 can be completed.

To address the problem of branching in a pipelining implementation of a command sequence, a typical approach is to suspend execution of the command sequence until the branch condition is known, or to use a method such as that disclosed in EP-A-162778. The first thing to do was to read the directives in advance before testing the branch conditions. Once the branch condition is tested, execution of the correct command sequence begins, either the original command sequence or a new command sequence. This scheme results in underutilization of the central processing unit and causes delays in the order of command implementation. Not only are there delays due to waiting for conditions to be tested, but multiple command segments are executed before the command completes, sometimes encountering another delay known as pipeline jamming.

Therefore, the pipe command sequence minimizes the effect of branch commands on system performance without any additional equipment on this, and with minimal compromise of improved command implementation from the use of pipelined command sequence implementation. A need was felt for operating procedures and equipment for line implementation.

SUMMARY OF THE INVENTION It is an object of the present invention to provide an improved information processing system.

It is another object of the present invention to provide an improved information processing unit for implementing command sequences.

It is a further object of the present invention to provide an improved information processing unit for implementing pipelining of command sequences.

It is a more specific object of the present invention to provide an information processing unit with a pipelined command sequence that can initiate either an initial command sequence or a branch command sequence before the determination of the truth of a condition is completed.
The above and other objects are accomplished according to the invention by providing an information processing unit having a device for recognizing the existence of a conditional branch instruction. Upon recognition of a conditional branch command, the information processing unit begins modifying the first command in the order in which it should be executed when the branch condition is determined to be true. The next command executed by the information handling system is the command to be executed when the branch condition is false, ie, the initial command sequence is continued. While this command (and subsequent commands in the initial command order) is being executed, the information processing system is preparing (when true) to implement the command order determined by the branch condition. If a true or false determination is made for the branch condition, the information processing unit may continue with the original command sequence that it was already executing when the condition was false. If the branch condition is true, the activity in the information processing unit that is preparing for execution of the true command sequence is used to cause the execution of the true command sequence to replace the execution of the first command sequence in progress. For selective conditional branch instructions, the branch condition is likely to occur, but the central processing unit executes the non-conditional branch instruction as a new order. After the preparation of the new directive order is completed, the conditions will be tested. If the condition (as originally interpreted) is true, the central processing unit continues executing the new command sequence. In the opposite case, execution of the command sequence is reversed to the original command sequence.

In this way, according to the present invention, when a conditional branch instruction is recognized, the preparation of a microinstruction for executing it as a non-conditional branch instruction to which no conditions are attached and the original order of instructions are continued. We are doing both with the preparation of micro-directives in case. and first starts executing the micro-instruction in the primitive order, then starts preparing the micro-instruction for execution as a non-conditional branch instruction, then starts executing the conditional branch instruction, and then starts executing the micro-instruction as a non-conditional branch instruction; While starting the execution of a new order of micro-instructions as a conditional branch instruction, at the same time determining the truth or falsehood of a condition of said conditional branch instruction, and then, if said condition is true, executing the new order of micro-instructions. and if the condition is false, cancel the new order and return to the original order microinstruction.

Conditional branch microdirectives are processed generally in the order listed above. The details of this processing order are specified in, for example, the scope of claims.

In this way, in the present invention, when executing a conditional branch micro-instruction, the micro-instruction in the original order when not branching and the micro-instruction in the new order when branching are executed in parallel, and the truth or falsity of the condition is determined. Once determined, the new order is continued or the original order is returned.

For this reason, the present invention includes a step of calculating in advance the probability that a branch in a conditional branch macro command will succeed and a probability that it will not succeed, and comparing the probability that the branch will succeed and the probability that it will not succeed when this command is decoded. , there is no process to select the command order with the highest probability.

Therefore, according to the method for implementing a conditional branch microcommand according to the present invention, each cycle period of the control timing is fixed from the first to the ninth period, and each processing step to be executed corresponding to each cycle period is predetermined. Because it is fixed, effects such as simplification of processing logic, simplification of logic circuits, and lower cost of equipment can be obtained.

These and other features of the invention will be understood from the following description in conjunction with the drawings.

[Brief explanation of drawings]

FIG. 1 is a block diagram of the elements of an information handling system in which the present invention can be used.

FIG. 2a is a diagram illustrating the execution of a command sequence according to the related art; FIG. 2b is a diagram illustrating how a command is divided into multiple command segments; and FIG. 2c is a diagram illustrating the execution of a pipelined command. It illustrates that performance can be increased by a central processing unit.

FIG. 3 is a block diagram of an information processing system that implements pipelined execution of command sequences.

FIG. 4 is a diagram illustrating execution of a non-conditional branch command.

FIG. 5 is a diagram illustrating execution of a conditional branch command in which processing of another command is halted until the determination of the condition is completed.

FIG. 6 is a diagram illustrating execution of a conditional branch instruction according to the present invention.

FIG. 7 is a diagram illustrating the execution of a conditional branch command with a high probability of branching to a new command order, in accordance with the present invention.

FIG. 8a shows a block diagram of the central processing unit with accompanying signals to illustrate the operation of some of the conditional branch macro commands.

FIG. 8b is a block diagram of the central processing unit with accompanying signals indicating the remaining operation of the conditional branch macro command.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 1 DETAILED DESCRIPTION OF THE DRAWINGS FIGS. 1 and 2 have been described in connection with the related art.

Referring now to FIG. 3, the organization of a central processing unit that performs pipeline implementation of command sequences is shown. The central processing unit includes a command subunit 31, an attached control unit 32, and an execution unit 33.
and a cache (or local) memory subunit 34. The memory subunit 34 is connected to the system bus 19 and exchanges logic signals with other subsystems of the information handling system via the system bus under the control of the control unit 32. The execution unit 33, also under the control of the central unit 32, performs the manipulation of information signals defined by the command being executed. The command unit receives commands to be executed and reorganizes the commands for use in controlling the operation of the central processing unit. This reorganized command or part of it is transmitted to the control unit 3.
2, it creates an array of logic elements in the information processing unit and executes the operation specified by the command.

The structure described above supports the use of micro-instructions to execute macro-instructions. A macroinstruction may be implemented by a single microinstruction or multiple microinstructions, depending on its complexity, the nature of the central processing unit equipment, and other parameters. It is the microcommand that is divided into microcommand segments as shown in Figure 2b.
Each microinstruction contains "microinstructions" that control a group of command segments.

Referring to the simplified division of the information processing unit shown in FIG. They will be taken equally. That is, the execution of a set of instructions for instructions to be executed by the information processing unit is shown in FIG. 2c. The first command is made by the command unit during the first period t ₀ . Third
During period _t0 , the cash memory unit can execute command #1, the execution unit can execute command #2, and the command unit can execute command #3. This three-level pipeline continues as long as commands arrive at the command unit.

The illustrated division of the information processing unit into functional units is generally not sufficient to provide an operational pipeline configuration. Each of the functional units described above requires multiple sub-operations to complete the execution of each command. For purposes of illustration, a pipeline having four segments will be used to illustrate the invention, rather than the three segments described with reference to FIG.

Referring now to FIG. 4, execution of a non-conditional branch instruction is illustrated. A non-conditional branch command forces the central processing unit to implement a new order of instructions starting with the command specified by the non-conditional branch command. As seen in FIG. 4, a non-conditional branch macro command 4010 is initiated and the first corresponding micro command causes the central processing unit to restore the target order of commands. The next three commands in the sequential commands, namely 4011, 4012, and 4013, are "no action" commands in which the signal from the control unit does not perform any action that contributes to the execution of the command. Microinstruction 4014 includes an "end instruction" microinstruction that completes execution of the non-conditional branch macroinstruction and causes execution of the macroinstruction's target sequence to begin.

Referring now to FIG. 5, a conditional branch macro directive that does not utilize the present invention is illustrated. In this process, the microdirective that executes the macrodirective is the condition test microdirective 5.
010. Tests the condition of this directive conditional branch directive. Since the result of the condition is unknown until the end of this command, execution of the above process is halted until the result of the test is determined. That is,
Microcommands 5011, 5012 and 5013 are "no action" commands. A conditional branch directive makes a true or false conditional determination. If the condition is true, the branch is taken and the new instruction sequence is executed. Fifth
In the illustrated example, non-conditional branch command 5016 is executed and the command sequence of FIG. 4 is executed. If the condition is false, the original order of commands continues. As shown in FIG. 5, commands 5015, etc. are now executed in the order of the first command.

Referring now to FIG. 6, a conditional branch instruction in accordance with the present invention is illustrated. Although this inventive command order implements conditional branch macro commands, the individual micro commands are not equivalent to the conditional branch commands of FIG. The first microinstruction 6010 in the sequence includes a conditional branch microinstruction. In addition to testing the condition, command 6010 provides an address in the first command's cache memory unit in the new order of commands so that the non-conditional branch command is executed. 3 "no action" after branch command
Unlike non-conditional branch directives where the directive is seen, in the present invention three
Two micro-directives are being executed. At the end of the first segment of the third primitive order command, a determination is made as to whether the condition is true or false, as shown by the arrow of command 6010 in FIG. 6, for example. When the condition is false, command 6014
The initial microcommand sequence continues as shown in .
When the condition is true, a one microcommand branch trap routine 6015 is executed to change the command order to execute the new order as shown by command 6016. Furthermore, directives 6011, 6012, and 6013 are
When a new order is selected based on a condition, it is deemed inappropriate and is discarded.

Referring now to FIG. 7, the execution of a type of conditional branch instruction in which branching to a new order is considered likely is illustrated. This type of macro command involves control of a command loop in which a plurality of macro commands are typically executed repeatedly before the macro command sequence is continued in a subsequent command sequence. Commands 7010 and 7011 are parameters that determine micro commands. Directive 7012 determines the destination address when the condition is determined to be true. Upon determination of this destination address, command 7012 is a non-conditional branch command that causes execution of a new or target command sequence. However, this conditional branch command stores the next address in the old order. As shown in FIG. 4, the fourth command from non-conditional branch command 7013, command 7016, includes a termination command microinstruction. Therefore, the next command 7017 is:
This is the first directive of the new order. Unlike the three "no action" commands in the non-conditional command branch order,
One of the instructions, 7015, is a conditional branch instruction of the type shown in FIG. Additionally, Directive 7013
and 7014 are part of the microcommand sequence that implements the macrocommand. The situation for conditions is now reversed, and the non-conditional branch command causes the potential new command sequence to become the active command sequence.
However, if a relatively rare situation in which the original order should be continued is identified in a conditional branch directive, the address of that directive is directive 7012.
stored inside. Furthermore, if the original command order is to be continued, the executed new order command, 701
7, 7018 and 7019 will not be used.

Referring now to FIG. 8a, an apparatus for executing conditional branch macro instructions is illustrated. A plurality of macro commands are added to command subunit 31. Each macro command is decoded and applied to the address signal control unit 32 which is to execute the macro command. Based on the applied address signals, microcode control signals from control unit 32 are applied to execution subunit 33, cache memory subunit 34, and conditional branch logic 81. Conditional branch logic 81 receives condition signals from execution subunit 33 and generates one of two output signals depending on the condition signal and the applied microcode control signal. The microcode control signals generate data signals in execution subunit 33 and condition signals applied to conditional branch logic 81. The applied condition signals and microcode control signals cause the resulting output signal(s) to be generated from the conditional branch logic unit 81. In the present invention, when a condition is true (i.e., a branch occurs),
Signals are applied to selected locations of microtrap logic unit 82. If the condition is false (ie, do not branch), a signal is applied to the cache memory subunit 34 and initiates a data read operation in the control unit 32 in response to the discard signal from the command subunit 31.

Referring to FIG. 8b, the result of applying a signal to the microtrap logic, eg, branch implementation, is illustrated. Microtrap logic unit 82 sends global trap signals to command subunit 31, execution subunit 33, cutter subunit 34, and control unit 32. The effect of sending a global trap signal to command subunit 31, execution subunit 33, and cache memory subunit 34 is to discard the results of microinstructions executed after the conditional branch microinstruction. The effect of the global trap signal on the control unit 32 is as a result of the ``condition is true'' signal applied to the microtrap logic unit 82 and from the microtrap logic to the control unit 32 to be used. It is to address (trap vector). The result of the trap vector is, first and foremost, to provide a trap release signal to the microtrap logic unit 82, thereby allowing the execution by the microtrap logic unit as a result of the application of the ``condition is true'' signal. Abort the routine being executed.

2 Operation of the Preferred Embodiment There are two delays included within the conditional branch command. First, execution of the proper order of commands cannot be ensured until determining the truth or falsity of a condition. Second, even once a decision is made to satisfy a condition, the various command segments must be executed before the advantage of rapid execution by the processor pipeline can be realized. To avoid the delays involved in conditional commands within a pipelined information processing environment, the present invention classifies conditional branch commands into two groups.

In the first group of conditional branch directives, the most likely outcome of the test of the condition is unknown. In the present invention, this type of conditional branch command is handled by retrieving information at the address that will result in the actual branch in the program as the result of the next command. Since this search will execute multiple microinstruction cycles, the instructions executed at this time are instructions from the original order that would have been executed if the program branch had not occurred as a result of condition testing. . That is, when the test result of the condition is determined and the condition is false, i.e., the original program order should be continued, the information of the search process is discarded and the original command that is already being executed is discarded. The order continues. In fact, only one microcommand cycle is required to execute FIG. Conversely, when the condition is true and a new command sequence should be executed, the first
The signal group search process continues over three microcommand cycles, and the execution of this command sequence is improved compared to waiting for condition test results before the next processor activity. It is clear that if the condition is true, the result of the original program's instruction execution order that occurs during the test of the condition will be inappropriate and must be discarded. That is,
The speed of the conditional branch command of the present invention is that it uses only one system clock cycle when the condition is false, and it is not possible to execute the command as fast as a non-conditional branch command when the condition is true. It should be obvious.

For the second group of commands illustrated in Figure 7, branching to a new command sequence is the most likely outcome of testing the condition, subject to confirmation of the conditional branching commands attached to this second group. Assume that As a result of this assumption, conditional branch directives are evaluated as non-conditional branch directives, and the activities necessary to perform the branch operation are performed even if the condition is not tested. After the new command sequence is prepared for execution, the commands that test the conditions are executed. However, the condition testing means is now reversed and the condition for continuation becomes a condition for execution of the new command order, even if the command order was actually the original command order. Execution of a conditional branch command occurs in a manner similar to the execution of a conditional branch command illustrated in FIG. It should be clear that the assumption that a branch is the most likely outcome of testing a condition is in fact true in most cases. This result, as is clear from FIG. 7, has the consequence that if the original condition is false, two changes in the order of commands should occur. Conditional branch directives cause non-conditional micro-orders to be executed as soon as the second (branch) address is known, and the use of the conditional branch directives described above improves the execution of instructions by: Reduces the impact of a (rare) reversion to the original command order.