SAL3 off-campus storage. E Available. More options. Find it at other libraries via WorldCat Limited preview. Bibliography Includes bibliographical references p. Contents Preface. About the Author. Chapter 1. Computer Systems. Chapter 2. Number Systems. Chapter 3. Data Formats. Chapter 4. Representing Integer Data. Chapter 5. Floating Point Numbers. Chapter 6.
The Little Man Computer. Chapter 7. The CPU and Memory. Chapter 8. Chapter 9. Chapter Computer Peripherals. Modern Computer Systems, Clusters, and Networks. Three System Examples. Operating Systems: An Overview. The User View of Operating Systems. The Internal Operating System. File Management. Programming Tools. Three Operating Systems. Supplementary Chapter 1. An Introduction to Digital Computer Logic. Supplementary Chapter 2. Instruction Addressing Modes.
Supplementary Chapter 3. Communication Channel Technology. Most computer architecture books are just too technical and complex. Register renaming can be done either statically by a compiler or dynamically by the hardware. A control dependence determines the ordering of an instruction, i, with respect to a branch instruction so that the instruction i is executed in correct program order. Every instruction, except for those in the first basic block of the program, is control dependent on some set of branches, and, in general, these control dependences must be preserved to preserve program order.
For example, in the co de segment:. S1 is control dependent on p1, and S2is control dependent on p2 but not on p1. In general, there are two constraints imposed by control dependences:. An instruction that is control dependent on a branch cannot be moved before the branch so that its execution is no longer controlled by the branch. For example, we cannot take an instruction from the then-portion of an if-statement and move it before the if- statement.
An instruction that is not control dependent on a branch cannot be moved after the branch so that its execution is controlled by the branch. For example, we cannot take a statement before the if-statement and move it into the then-portion. Control dependence is preserved by two properties in a simple pipeline, First, instructions execute in program order.
This ordering ensures that an instruction that occurs before a branch is executed before the branch. Second, the detection of control or branch hazards ensures that an instruction that is control dependent on a branch is not executed until the branch direction is known.
A hazard is created whenever there is a dependence between instructions, and they are close. Because of the dependence, preserve order that the instructions would execute in, if executed sequentially one at a time as determined by the original source program. The goal of both our software and hardware techniques is to exploit parallelism by preserving program order only where it affects the outcome of the program.
Detecting and avoiding hazards ensures that necessary program order is preserved. Data hazards may be classified as one of three types, depending on the order of read and write accesses in the instructions. Consider two instructions i and j, with i occurring before j in program order. The possible data hazards are RAW read after write — j tries to read a source before i writes it, so j incorrectly gets the old value.
This hazard is the most common type and corresponds to a true data dependence. Program order must be preserved to ensure that j receives the value from i.
In the simple common five-stage static pipeline a load instruction followed by an integer ALU instruction that directly uses the load result will lead to a RAW hazard. WAW write after write — j tries to write an operand before it is written by i. The writes end up being performed in the wrong order, leaving the value written by i rather than the value written by j in the destination. This hazard corresponds to an output dependence.
WAW hazards are present only in pipelines that write in more than one pipe stage or allow an instruction to. The classic five-stage integer pipeline writes a register only in the WB stage and avoids this class of hazards. WAR write after read — j tries to write a destination before it is read by i, so i incorrectly gets the new value. This hazard arises from an antidependence.
WAR hazards cannot occur in most static issue pipelines even deeper pipelines or floating point pipelines because all reads are early in ID and all writes are late in WB. A WAR hazard occurs either when there are some instructions that write results early in the instruction pipeline, and other instructions that read a source late in the pipeline or when instructions are reordered.
The Dynamic Scheduling is used handle some cases when dependences are unknown at a compile time. In which the hardware rearranges the instruction execution to reduce the stalls while maintaining data flow and exception behavior. It also allows code that was compiled with one pipeline in mind to run efficiently on a different pipeline. Although a dynamically scheduled processor cannot change the data flow, it tries to avoid stalling when dependences, which could generate hazards, are present.
A major limitation of the simple pipelining techniques is that they all use in -order instruction issue and execution: Instructions are issued in program order and if an instruct ion is stalled in the pipeline, no later instructions can proceed. Thus, if there is a dependence between two closely spaced instructions in the pipeline, this will lead to a hazard and a stall. If there are multiple functional units, these units could lie idle.
If instruction j depends on a long-running instruction i, currently in execution in the pipeline, then all instructions after j must be stalled until i is finished and j can execute. For example, consider this code:. Out-of-order execution introduces the possibility of WAR and WAW hazards, which do not exist in the five-stage integer pipeline and its logical extension to an in-order floating-point pipeline. Out-of-order completion also creates major complications in handling exceptions.
Dynamic scheduling with out-of-order completion must preserve exception behavior in the sense that e x a c tly those exceptions that would arise if the program were executed in strict program order a c tually do arise.
The pipeline may have already c ompleted instructions that are later in program order than the instruction causing the exception, and. The pipeline may have not yet completed some instructions that are e ar lier in program order than the instruction causing the exception. To allow out-of-order execution, we essentially split the ID pipe stage of our simple five -stage pipeline into two stages:. In a dynamically scheduled pipeline, all instructions pass through the issue stage in order in - order issue ; however, they can be stalled or bypass each other in the second stage read operands and thus enter execution out of order.
S c ore-boarding is a technique for allowing instructions to execute out-of-order when there are sufficient resources and no data dependences; it is named after the CDC scoreboard, which developed this capability. Output and anti-dependencies are just name dependencies, there is no actual data dependence.
Tomasulo's algorithm implements register renaming through the use of what are called reservation stations. Reservation stations are buffers which fetch and store instruction operands as soon as they are available.
In addition, pending instructions designate the reservation station that will provide their input. Finally, when successive writes to a register overlap in execution, only the last one is actually used to update the register. As instructions are issued, the register specifies for pending operands are renamed to the names of the reservation station, which provides register renaming. Instructions are sent from the instruction unit into the instruction queue from which they are issued in FIFO order.
The reservation stations include the operation and the actual operands, as well as information used for detecting and resolving hazards. Load buffers have three functions: hold the components of the effective address until it is computed, track outstanding loads that are waiting on the memory, and hold the results of completed loads that are waiting for the CDB.
Similarly, store buffers have three functions: hold the components of the effective addr ess until it is computed, hold the destination memory addresses of outstanding stores that are waiting for the data value to store, and hold the address and value to store until the memory unit is available.
All results from either the FP units or the load unit are put on the CDB, which goes to the FP register file as well as to the reservation stations and store buffers. The FP adders implement addition and subtraction, and the FP multipliers do multiplication and division.
Issue —Get the next instruction from the head of the instruction queue. If there is a matching reservation station that is empty, issue the instruction to the station with the operand values renames registers. E xecute EX — When all the operands are available, place into the corresponding. If operands are not yet available, monitor the common data bus CDB while waiting for it to be computed.
W r ite result WB — When the result is available, write it on the CDB and from there into the registers and into any reservation stations including store buffers waiting for this result. Stores also write data to memory during this step: When both the address and data value are available, they are sent to the memory unit and the store completes.
Note that only one of the V field or the Q field is valid for each operand. For loads, the Vk field is used to the offset from the instruction.
If the hint turns out to be wrong, the prediction bit is inverted and stored back. The two bits are used to encode the four states in the system. In a counter implementation, the counters are incremented when a branch is taken and decremented when it is not taken; the counters saturate at 00 or One complication of the two-bit scheme is that it updates the prediction bits more often than a one-bit predictor, which only updates the prediction bit on a mispredict.
Since we typically read the prediction bits on every cycle, a two-bit predictor will typically need both a read and a write access port. The two-bit scheme is actually a specialization of a more general scheme that has an n -bit saturating counter for each entry in the prediction buffer.
With an n -bit counter, the counter can n take on values between 0 and 2 n — 1 : when the counter is greater than or equal to one half of its maximum value 2 , the branch is predicted as taken; otherwise, it is predicted untaken. To exploit more ILP, the accuracy of our branch prediction becomes critical, this problem in two ways: by increasing the size of the buffer and by increasing the accuracy of the scheme we use for each prediction. These two-bit predictor schemes use only the recent behavior of a single branch to predict the future behavior of that branch.
It may be possible to improve the prediction accuracy if we also. Consider a small code fragment from the SPEC92 benchmark. Here is the MIPS code that we would typically generate for this code fragment assuming that aa and bb are assigned to registers R1 and R The key observation is that the behavior of branch b3 is correlated with the behavior of branches b1 and b2.
Clearly, if branches b1 and b2 are both not taken i. A predictor that uses only the behavior of a single branch to predict the outcome of that branch can never capture this behavior. Branch predictors that use the behavior of other branches to make a prediction are called c orrelating predictors or two-level predictors. The primary motivation for correlating branch predictors came from the observation that the standard 2-bit predictor using only local information failed on some important branches and that by adding global information, the performance could be improved.
0コメント