Original Publication Date: 2004-May-25
Included in the Prior Art Database: 2004-May-25
Conditional branches are important instructions that can have a significant impact on the performance of conventional and future pipelined and superscalar processor architectures. In contrast to a lot of recent research, which has been focussed on efficient branch prediction schemes, the presented concept addresses the performance impact of condition branch instructions in a more fundamental way through a tighter integration of condition evaluation functionality into the processor architecture.
In conventional processor architectures (e.g., "von Neumann"), instructions are selected for execution based on their addresses using a program counter. Since by default the program counter is incremented after an instruction has been executed, the "instruction execution flow" has a sequential nature, which is only changed by a branch, call or return instruction. This is shown in Figure 1 (a). Conditional branches can be used to change the instruction execution flow based on the evaluation of one relatively simple condition (e.g., less than, greater than, or equal to). If a more complex condition (e.g., "is a given character a legal name character in a given programming language") or multiple conditions need to be evaluated, then these have to be "mapped on" sequences of several instructions and conditional branch instructions.
Figure 1 (b) illustrates the proposed concept in a general form: A processor model in which instructions are associated with sets of multiple conditions. In each instruction cycle, the conditions associated with all instructions in a "current" instruction group are evaluated, and the instruction for which all conditions match is selected for execution. Special "branch" instructions are used to select a different group of instructions as the current instruction group. Because the execution of the instructions can and usually will affect the evaluation of the conditions in subsequent cycles, this will influence and determine the actual instruction execution flow. This is shown in Figure 1 (c), which illustrates an example of an embodiment of this concept in the form of an extended state transition diagram, which comprises a...