Computer systems are capable of executing various arithmetic and logic operations on data. The particular arithmetic or logic operation to be executed is indicated by an "instruction" that is typically retrieved from a memory of the computer system, decoded in an instruction decode block, and then transmitted to an execution block of the computer for execution. Computer programs comprise a set of instructions that, when taken from memory, decoded and transmitted to the execution block in a certain sequence, cause the computer system to execute a series of operations that achieve the objective of the program.
There are computer systems designed to implement a variable length instruction architecture, wherein instructions can vary in length from, for example, one byte to eleven bytes or more. However, memory systems, and in particular the cache memory used to store instructions prior to execution, typically store data in fixed sized blocks such as, for example, sixteen byte blocks. In such a system, instruction data is fetched in sixteen byte lines aligned on sixteen byte boundaries. Accordingly, in a variable length instruction architecture, each fixed sized line fetched from memory contains instructions of various lengths that may start anywhere within the line and may even cross a line boundary into a succeeding line of memory.
An instruction marking circuit is typically implemented in the instruction decode block of a computer having a variable length instruction architecture in order to mark the beginning of each instruction in a line fetched from a fixed sized line memory system. The instruction marking circuit includes length decoders, which process a selected byte or number of bytes of the fetched line to determine a length for the instruction containing the bytes. Once instruction lengths are determined and first instruction bytes are marked, the instructions of the fetched line can be transmitted to an instruction decoding circuit within the decode block.
Instruction marking is, by nature, a serial operation, since the beginning of a particular instruction can be determined with certainty only after the beginning and length of a previous instruction have been determined. In present instruction marking circuits, the serial nature of instruction marking is accommodated by performing the marking operation according to an externally-timed scheme that controls and synchronizes circuit operations by a system clock. Marking information is propagated through the marking circuit in synchronization with the system clock. The length decoders that are typically used in marking circuits, however, comprise combinational logic circuits that perform length decodes in varying amounts of time depending upon the particular instruction being processed. To assure that all possible instructions found in an instruction line fetched from memory will be marked, the timing of the clock signals must be sufficient to process a "worst case" decode time for an instruction. That is, the timing must be sufficient to permit signals to traverse the longest path through the combinational logic of the length decoder, thus delaying the propagation of marking signals through the marking circuit when the instruction is not a "worst case" instruction.
Only a limited subset of instructions are of the "worst case" instruction type. Thus the time required for processing this relatively small subset of instructions is imposed on all marking operations such that the overall time needed for instruction marking is longer than actually required in most instances. As a result, the known scheme for marking instructions in a variable length instruction architecture incurs wasteful delay in the instruction execution process, decreasing system performance.
The U.S. patent application Ser. No. 08/997,457, entitled "Parallel Processing and Self-Timed Serial Marking of Variable Length Instructions" (filed on even date herewith), provides for fast and efficient instruction decoding through the self-timed length decoding, marking, and steering of instructions. An exemplary embodiment of a computer system according to the teachings of the aforementioned application is shown in FIG. 1 (and described in more detail by the aforementioned application). As shown in FIG. 1, an instruction fetch, decode, and execute pipeline 1 is implemented in a computer system. An instruction cache 10 is a memory used to store a set of instructions that are most likely required by the computer for execution in the near future, in accordance with known caching techniques. The instructions are stored in and fetched from the instruction cache 10 in instruction lines, each comprising a fixed sized block of bytes, for example, sixteen bytes. Each instruction line stored in the instruction cache 10 is aligned within the memory along a sixteen byte boundary. Each instruction contained in a line can vary in length from one byte to the maximum byte length used in the computer system, and any particular line of instructions can contain instructions of any combination of byte lengths.
An instruction fetch block 12 operates to fetch a line of instructions for input to an instruction decode block 14. The instruction decode block 14 decodes the instructions within the line fetched from the instruction cache 10 for input to an execution block 16 for execution, as is generally known. An instruction issue block 18 can be implemented to receive decoded instructions from the instruction decode block 14 for transfer to the execution block 16.
As noted above, the instructions stored in the instruction cache 10 can vary in length and instructions of any combination of lengths can be found in any particular instruction line fetched from the instruction cache 10. Accordingly, the instruction decode block 14 includes an instruction marking circuit 20 that operates to mark the first byte of each instruction contained in a fetched line. Once marked, the instructions are transferred, for example, to an instruction steering circuit 22 to await transfer to an instruction decode circuit 24. The instruction decode circuit 24 decodes the instructions and outputs decoded instructions to the instruction issue block 18.
FIG. 2 shows an exemplary embodiment of an instruction decode block 14 using the self-timed techniques of the aforementioned application. Instruction lines fetched from the instruction cache 10 by instruction fetch block 12 are received by an instruction line buffer 26 of the instruction marking circuit 20. Instruction line buffer 26 may be implemented as a FIFO, such that multiple instruction lines can be stored in anticipation of the marking process.
The instruction marking circuit 20 can be described for illustrative purposes as being arranged in "columns" corresponding to each byte position of the instruction line buffer 26. Thus, a column "contains" those functional units used to process a byte for the particular byte position in the instruction line. For an instruction line width of, for example, sixteen bytes, the instruction marking circuit 20 can be described as having sixteen columns, each containing the functional units used in byte processing. Those columns corresponding to the first byte positions of the instruction line buffer (i.e. lower memory addresses) are considered the "front" of the instruction marking circuit, while those columns corresponding to the last byte positions of the instruction line buffer (i.e. higher memory addresses) are considered the "end" of the instruction marking circuit. Relative to each other, columns associated with lower memory addresses are considered "upstream" columns, while columns associated with higher memory addresses are considered "downstream" columns.
Each byte of the instruction line is separately sent to a respective byte latch 28 in each column of the instruction marking circuit 20. The byte is processed by a length decoder 30 for that same column of the instruction marking circuit 20, together with any additional downstream bytes in byte latches 28 of downstream columns, as may be required by the length decoding algorithm used in the variable instruction length architecture. The combinational logic implemented in the length decoder 30 produces a signal indicating the computed length of the instruction, under the assumption that the byte being processed is the first byte of an instruction.
To indicate instruction length, each length decoder 30 has a number of length signal outputs. The length signal outputs are coupled to length signal output lines 38, which are further coupled to other functional units in the instruction marking circuit 20, as described below. The number of length signal outputs (and, therefore, length signal outputs lines 38) is dependent on the maximum possible instruction length and the encoding scheme used for length signals. For the example of FIG. 2, the maximum possible number of bytes in an instruction is four, and the length signals are implemented as "one-hot" signals, i.e., only one signal is provided as active for each byte length. As a result, each length decoder 30 shown in FIG. 2 has four length signal outputs, one for a one byte instruction, one for a two byte instruction, and so on. Each length decoder 30 asserts a "one-hot" signal on the length signal output line 38 corresponding to the length determined by the length decoder 30 for the current byte being processed in that column.
Since each length decoder 30 asserts the appropriate length signal as soon as it completes the length decode for the current byte, length information may be available much earlier than under the "worst-case" decode time.
A plurality of marking units 34 is also provided, one in each column of the instruction marking circuit 20. The instruction length output lines 38 coupled to each length decoder 30 are also coupled to the marking unit 34 for the same column. Each marking unit 34 is further coupled to a number of marking lines 35 used to carry marking signals to mark a subsequent byte as the first byte of the next instruction. The number of marking lines 35 corresponds to the maximum number of bytes possible in the variable length instruction architecture. Thus, as shown in FIG. 2 for a maximum instruction length of four bytes, each marking unit 34 is coupled to four marking lines 35, one corresponding to each byte length available in the variable length instruction architecture. Accordingly, each marking unit 34 is also coupled to four marking lines 35 carrying marking signals generated by four upstream marking units 34.
Based on the length signals provided by the length decoder 30, the marking unit 34 determines the column containing the first byte of the next instruction in the instruction line. The marking unit 34 indicates the first byte of the next instruction by directly signaling a subsequent marking unit 34 in a downstream column via a marking signal over the appropriate marking line 35. Marking may be achieved, for example, by sending a "one-hot" signal over the appropriate marking line 35 to a downstream marking unit 34. Each marking line 35 is coupled between the marking unit 34 of the present column and a marking unit 34 for a subsequent column: the marking line 35 used to signal a one byte length instruction is coupled to the marking unit 34 for the next column of the instruction marking circuit 20; the marking line 35 used to signal a two byte length instruction is coupled to the marking unit 34 two columns away, and so on. The marking unit 34 asserting a marking output thereby directly marks the first byte of the next instruction of the fetched line.
For those marking units 34 at the end of the instruction marking circuit 20, the marking lines 35 used to mark a column beyond the end of the instruction marking circuit 20 are "wrapped around" to the marking units 34 at the front of the instruction marking circuit 20. The marking information transmitted via the wrapped-around marking lines 35 therefore marks the first byte of the first instruction on the next fetched instruction line.
Activation of a marking output of a marking unit 34 is controlled by satisfaction of certain system conditions. For example, a marking unit 34 waits for an indication that its column contains the first byte of an instruction, as provided by the marking signal received over the marking lines 35 from upstream marking units 34. A marking unit 34 also waits for an indication that the bytes that comprise the instruction have been loaded into their respective byte latches 28 and are ready for transmission, for example, as provided by an INSTRUCTION.sub.-- READY signal provided by length decoder 30 and carried by length decoder handshaking lines 37. A marking unit 34 also waits for an indication that the instruction steering circuit 22 is available to receive an instruction for decoding and execution, for example, as provided by a BUFFER.sub.-- AVAILABLE signal produced by instruction steering circuit 22 and carried by output buffer handshaking lines 36. These signals can arrive in any order.
Once these conditions have been satisfied, the instruction bytes are transmitted from the byte latches 28 to the instruction decode circuit 24 over byte latch output lines 29 and via a crossbar switch and output buffer within the instruction steering circuit 22. Instruction length data is also transmitted from the length decoder to the instruction decode circuit 24 via the crossbar switch and output buffer. The byte latches 28 are then loaded with new bytes from the next instruction line in instruction line buffer 26. A marking signal is concurrently sent over a marking line 35 to the marking unit 34 in the downstream column containing the first byte of the next instruction. The marking unit 34 in that downstream column may then perform a similar marking and transfer operation.
As a result of the above, the generation and transmission of all instruction bytes and marking information flows through the length decoders 30 and marking units 34 in a self-timed manner, and at an average speed that is faster than clocked circuits. To further increase the throughput of the instruction length decoding and marking process, processing of the bytes in a next instruction line can begin as soon as the individual byte latches 28 processing previous instruction bytes become available. The wrap around marking information generated during a current instruction line remains available to mark the first byte of the first instruction in the next instruction line.
In a second exemplary embodiment of an instruction decode block 14 implementing self-timed instruction length decoding, marking, and steering, as described in the aforementioned patent application, multiple self-timed marking units 34 are employed to increase the throughput capabilities of the instruction decode block 114. FIG. 3 shows such an embodiment, wherein the instruction decode block 114 is implemented having sixteen columns and is capable of processing instructions up to 4 bytes in length. As shown in FIG. 3, instruction marking circuit 120 is implemented using multiple marking units 34 in each column, with each marking unit 34 of the column given a different "row" designation for descriptive purposes. Marking signals are propagated through the marking circuit by sending the marking signals to the marking unit 34 of the next higher row in the column to be marked. The number of rows to be implemented in an instruction marking circuit 20 can be determined based on a calculation of the speed of instruction marking in relation to the speed of the steering function. For the embodiment shown in FIG. 3, three rows (row 0, row 1, and row 2) are implemented in instruction marking circuit 120, although other quantities can be implemented.
The instruction steering circuit 122 is implemented to mirror the instruction marking circuit 120, such that instruction steering circuit 122 contains a crossbar switch 62 having a number of rows equal to the number of rows in the instruction marking circuit 120, and a number of output buffers 64 equal to the number of rows in the instruction marking circuit 120. Instruction bytes are transferred, via the row of the crossbar switch 62 that is the same row as the row of marking unit 34 that has processed those instruction bytes, the output buffer 64 of the same row designation as the row of the marking unit 34. Instructions are therefore incrementally spread across each output buffer, allowing the instruction decode circuit 124 to fetch instructions sequentially from each output buffer using, for example, a row pointer 301.
A more detailed description of the self-timed length decoding, marking, and steering of instructions may be found in the aforementioned patent application, which is expressly incorporated herein by reference.
As described above, modern computer systems are typically implemented with an instruction pipeline, where a "stream" of instruction bytes is directed through the functional elements of the pipeline. For example, referring to FIG. 1, instruction bytes are supplied to the instruction cache 10 of the instruction pipeline 1, which are then directed through each subsequent functional block of the instruction pipeline 1. A pipelined system architecture can increase the overall throughput of the computer system by performing instruction overhead functions in advance of the actual execution time of the instruction.
Branch instructions, however, pose a special problem in instruction pipelining, since branch instructions allow program execution to jump to another location in the program, possibly outside of the instruction stream of the pipeline. Without contingencies for branches, the instruction pipeline would need to be "flushed" of its contents and reloaded with a new instruction stream containing the target instruction whenever a branch occurred. In order to avoid the delays that would occur if the instruction pipeline were "flushed" on a taken branch, branch instructions are typically evaluated prior to or during processing in the instruction pipeline. The instruction stream can then be adjusted to contain the targeted instruction of the branch and those instructions following that targeted instruction. For example, in the typical computer system having a memory system that stores data in fixed-size lines, such as in FIG. 1, the instruction line containing the targeted instruction can be supplied to the instruction cache 10 immediately following the instruction line containing the branch instruction, thus avoiding a pipeline flush.
Some branch instructions, however, are "conditional branches"--branches that are taken only when certain conditions based on run-time data are satisfied (such as in a program loop). Thus conditional branches cannot be accurately evaluated while being processed in the instruction pipeline. In order to mitigate this problem, modern computer systems employ a branch prediction function that evaluates conditional branches based on various prior events. Based on the evaluation of the branch predictor, the instruction stream can be adjusted to include the instruction line containing the predicted target instruction. If the branch has been correctly predicted, processing of the instruction stream in the instruction pipeline can continue without delay. If the branch has not been correctly predicted, then the instruction pipeline is flushed and loaded with the appropriate instruction bytes.
Branch instructions present a special problem for a self-timed length decoding, marking, and steering system such as previously described. The system is expecting the next instruction to be found immediately following the presently marked instruction. Accordingly, the system will send a marking signal to the byte immediately following the last byte of the present instruction, regardless of whether a branch has been predicted. Thus, a branch instruction in a self-timed marking system may cause the pipeline to be flushed, incurring wasteful delay.