Instruction-Level Parallelism and it’s Exploitation

Reducing Branch Costs With Advanced Branch Prediction

182

Loop unrolling is one way to reduce the number of branch hazards; we can also reduce the performance losses of branches by predicting how they will behave

As the number of instructions in flight has increased with deeper pipelines and more issues per clock, the importance of more accurate branch prediction has grown

183

It may be possible to improve the prediction accuracy if we also look at the recent behavior of other branches rather than just the branch we are trying to predict

Branch predictors that use the behavior of other branches to make a prediction are called correlating predictors or two-level predictors.

In the general case, an (m,n) predictor uses the behavior of the last m branches to choose from 2^m branch predictors, each of which is an n-bit predictor for a single branch

The simplicity of the hardware comes from a simple observation: the global history of the most recent m branches can be recorded in an m-bit shift register, where each bit records whether the branch was taken or not taken. The branchprediction buffer can then be indexed using a concatenation of the low-order bits from the branch address with the m-bit global history

The attraction of this type of correlating branch predictor is that it can yield higher prediction rates than the 2-bit scheme and requires only a trivial amount of additional hardware.

trivial, P184’s example will show why

见山是熔岩巨兽，见海是潮汐海灵，见花是荆棘之兴。唯独见了你，是厄加特。

P184

How much better do the correlating branch predictors work when compared with the standard 2-bit scheme?

In gshare the index is formed by combining the address of the branch and the most recent conditional branch outcomes using an exclusiveOR, which essentially acts as a hash of the branch address and the branch history.

The hashed result is used to index a prediction array of 2-bit counters, as shown in Figure 3.4. The gshare predictor works remarkably well for a simple predictor, and is often used as the baseline for comparison with more sophisticated predictors.

Predictors that combine local branch information and global branch history are also called alloyed predictors or hybrid predictors.

if same history and address, we can refer to same to location, if different history, even same address, different place of course, interference is possible, but if data is

P185

Adding global history could help remedy this situation. Tournament predictors take this insight to the next level, by using multiple predictors, usually a global predictor and a local predictor, and choosing between them with a selector.

A global predictor uses the most recent branch history to index the predictor, while a local predictor uses the address of the branch as the index

existing tournament predictors use a 2-bit saturating counter per branch to choose among two different predictors based on which predictor (local, global, or even some timevarying mix) was most effective in recent predictions

P186

The number of bits of the branch address used to index the selector table and the local predictor table is equal to the length of the global branch history used to index the global prediction table.

Note that misprediction is a bit tricky because we need to change both the selector table and either the global or local predictor.

The local predictor consists of a two-level predictor. The top level is a local history table consisting of 1024 10-bit entries; each 10-bit entry corresponds to the most recent 10 branch outcomes for the entry. The selected entry from the local history table is used to index a table of 1K entries consisting of 3-bit saturating counters, which provide the local prediction. This combination, which uses a total of 29K bits,

why 29K bits, and use history to index 3-bit saturating counters is ridiculous

P188

The best performing branch prediction schemes as of 2017 involve combining multiple predictors that track whether a prediction is likely to be associated with the current branch

This class of branch predictors, which we call tagged hybrid predictors (see Seznec and Michaud, 2006), employs a series of global predictors indexed with different length histories.

P189

a five-component tagged hybrid predictor has five prediction tables: P(0), P(1), . . . P(4), where P(i) is accessed using a hash of the PC and the history of the most recent i branches (kept in a shift register, h, just as in gshare)

A prediction from P(1), . . . P(4) is used only if the tags match the hash of the branch address and global branch history.

The difference between gshare and tagged hybrid predictor:

The use of multiple history lengths to index separate predictors is the first critical difference.
The second critical difference is the use of tags in tables P(1) through P(4).

Each of the predictors in P(0…n) can be a standard 2-bit predictor. In practice a 3-bit counter, which requires three mispredictions to change a prediction, gives slightly better results than a 2-bit counter

The prediction for a given branch is the predictor with the longest branch history that also has matching tags.

so what is the fucking tags, tags is the part of history, whoes lenght vary from 4bit to 10 bits.

P(0) always matches because it uses no tags and becomes the default prediction if none of P(1) through P(n) match

The tagged hybrid version of this predictor also includes a 2-bit use field in each of the history-indexed predictors
The use field indicates whether a prediction was recently used and therefore likely to be more accurate;
the use field can be periodically reset in all entries so that old predictions are cleared

Many more details are involved in implementing this style of predictor, especially how to handle mispredictions. The search space for the optimal predictor is also very large because the number of predictors, the exact history used for indexing, and the size of each predictor are all variable

tune parameters ? deep learning ?

Another issue for larger predictors is how to initialize the predictor.
Some predictors (including many recent predictors) include a valid bit, indicating whether an entry in the predictor has been set or is in the “unused state.”
We could also set the initial prediction on the basis of the branch direction: forward going branches are initialized as not taken, while backward going branches, which are likely to be loop branches, are initialized as taken

3.4 Overcoming Data Hazard With Dynamic Scheduling

P191

bypassing and forwarding means the same technology ?

definition

P192

three advantages

the first two advantage is the same, why should sperate them into two pieces

one disadvantage : complexity

P193

why we need dynamic scheduling

define out-of-order-execution

out-of-order-execution introduce WAR and WAW hazard and both of them can be avoid by reg renaming

P194

major complication is handling exceptions

inprecise exception can be caused by two possibilities

inprecise exception make it difficult to restart execution after an exception. Section 3.6 and appendix J will handle this problem

split the ID pipe stage into Issue and Read Operand

what’s multiple function units and pipelined fucntional units ?

why we will assume the processor has multiple function units ?

Pipeline stage	Issue	Read Operand
Function	Decode instruction	Read operand
hazard	structural	data
order	in-order	out-of-order

P195

Scoreboarding is a technique for allowing instruction to execute out of order when there are sufficient resources and no data dependences

Tomasulo’s algorithm is more complex but more effcient

Two main principal of Tomasulo’s algorithm: dynamically determining when an instruction is ready to execute and renaming registers to avoid unnecessary hazards

the background of the invention of Tomasulo’s algorithm

how will we explain the algorithm

P196

Register renaming rename all the destination register, including those with a pending read or write for an earlier instruction.

Hazard	Explanation	Caused by
WAW	write too quickly, slow write override the result	out-of-order
WAR	write too quickly, slow read get the newer result than it should	out-of-order
RAW	read too quickly, former instruction haven’t get the correct result yet	in-order

Tomasulo’s algorithm can handle renaming across branches.

Tomasulo’s algorithm use resrevation stations for renaming which buffer the operands instruction waiting to issue and are associated with the functional units.

the basic idea of Tomasulo’s algorithm

P197

totally confused about how the algorithm worked

The use of reservation station, rather than a centralized register file, leads to two other important properties.

can’t understand these two important properties

describe basic structure of a Tomasulo-based processor

this structure is not lucid

review three steps instructions go through: issue, execute and write back

explain issue stage in detail

In Issue step, why it can eliminating WAR and WAW

P198

In execute stage, it can eliminate RAW hazard

when we define the effective address terminology

P199

In execute stage, several problems require special attention, including multiple instruction ready in same clock, Load and store require two-step execution process, how to preserve exception behavior

explain Write back stage in detail

tag field’s configuration and function

tag is not defined, and can not understand what it is ?

P200

Because there are more reservation station than actual register numbers, WWR and WAW hazard can be eliminated by renaming results using reservation station numbers.

can not understand the second paragraph totally ? what the fuck does it say ?

It is important to remember that the tags in Tomasulo scheme refer to the buffer or unit that will produce a result.

what is reservation station, no definition again ?

Each reservation has seven fields

The register file has a field

The load and store each have a field

Dynamic Scheduling: Example and the Algorithm

Dynamic Scheduling, out-of-ordre and speculation, they are the same thing or different ?

P201

show a example

Tomusulo’s scheme offers two major advamtages:

the distribution of the hazard detection logic
the elimination of stalls for WAW and WAR hazards

the first advantage arises from the distributed reservation stations and the use of CDB

3.6 Hardware-Based Speculation

P208

Branch prediction reduces the direct stalls attributable to branches, but for a processor executing multiple instructions per clock, just predicting branches accurately may not be sufficient to generate the desired amount of instruction-level parallelism

A wide-issue processor may need to execute a branch every clock cycle to maintain maximum performance

Hardware-based speculation combines three key ideas:

dynamic branch prediction to choose which instructions to execute,
speculation to allow the execution of instructions before the control dependences are resolved (with the ability to undo the effects of an incorrectly speculated sequence),
dynamic scheduling to deal with the scheduling of different combinations of basic blocks. (In comparison, dynamic scheduling without speculation only partially overlaps basic blocks because it requires that a branch be resolved before actually executing any instructions in the successor basic block.)

dynamic scheduling to deal with the scheduling of different combinations of basic blocks. so what is basic blocks

P209

To extend Tomasulo’s algorithm to support speculation, we must separate the bypassing of results among instructions, which is needed to execute an instruction speculatively, from the actual completion of an instruction

separate, how, and separate what

When an instruction is no longer speculative, we allow it to update the register file or memory; we call this additional step in the instruction execution sequence instruction commit.

The key idea behind implementing speculation is to allow instructions to execute out of order but to force them to commit in order and to prevent any irrevocable action (such as updating state or taking an exception) until an instruction commits

can you prove this

Adding this commit phase to the instruction execution sequence requires an additional set of hardware buffers that hold the results of instructions that have finished execution but have not committed. This hardware buffer, which we call the reorder buffer, is also used to pass results among instructions that may be speculated

The ROB holds the result of an instruction between the time the operation associated with the instruction completes and the time the instruction commits

With speculation, the register file is not updated until the instruction commits (and we know definitively that the instruction should execute)

The ROB is similar to the store buffer in Tomasulo’s algorithm, and we integrate the function of the store buffer into the ROB for simplicity

similarity, maybe can register file and memory are similar

Each entry in the ROB contains four fields:

the instruction type The instruction type field indicates whether the instruction is a branch (and has no destination result), a store (which has a memory address destination), or a register operation (ALU operation or load, which has register destinations).
the destination field The destination field supplies the register number (for loads and ALU operations) or the memory address (for stores) where the instruction result should be written.
the value field The value field is used to hold the value of the instruction result until the instruction commits. We will see an example of ROB entries shortly.
the ready field Finally, the ready field indicates that the instruction has completed execution, and the value is ready.

P210

Stores still execute in two steps, but the second step is performed by instruction commit.

Although the renaming function of the reservation stations is replaced by the ROB, we still need a place to buffer operations (and operands) between the time they issue and the time they begin execution

Because every instruction has a positioninthe ROB until it commits,we tag a result using the ROB entry number rather than using the reservation station number.This tagging requires that the ROB assigned for an instruction must be tracked in the reservation station.

Later in this section, wewill explore an alternative implementation that uses extra registers for renaming and a queue that replaces the ROB to decide when instructions can commit great, some familiar

P211

Here are the four steps involved in instruction execution

Stage	trigger requirement	action
Issue	Issue the instruction if there is an empty reservation station and an empty slot in the ROB.	0. send the operands to the reservation station if they are available in either the registers or the ROB. 1. Update the control entries to indicate the buffers are in use. 2.The number of the ROB entry allocated for the result is also sent to the reservation station so that the number can be used to tag the result when it is placed on the CDB.
Execute	If one or more of the operands is not yet available, monitor the CDB while waiting for the register to be computed.	Instructions may take multiple clock cycles in this stage, and loads still require two steps in this stage. Stores only need the base register at this step, because execution for a store at this point is only effective address calculation.
Write result	When the result is available, write it on the CDB (with the ROB tag sent when the instruction issued) and from the CDB into the ROB, as well as to any reservation stations waiting for this result.	Mark the reservation station as available.
Commit		The normal commit case occurs when an instruction reaches the head of the ROB and its result is present in the buffer; at this point, the processor updates the register with the result and removes the instruction from the ROB. Committing a store is similar except that memory is updated rather than a result register. When a branch with incorrect prediction reaches the head of the ROB, it indicates that the speculation was wrong. The ROB is flushed and execution is restarted at the correct successor of the branch. If the branch was correctly predicted, the branch is finished

Special actions are required for store instructions. If the value to be stored is available, it is written into the Value field of the ROB entry for the store. If the value to be stored is not available yet, the CDB must be monitored until that value is broadcast, at which time the Value field of the ROB entry of the store is updated. For simplicity we assume that this occurs during the Write Result stage of a store; we discuss relaxing this requirement later. what is meaning of update, as i think, store value is as simple as write to register, available then write or just wait.

P212

skip next part, becaues we don’t have time to cover the example. No !!!!!!!!!!!!!, you will regret for it

3.7 Exploiting ILP Using Multiple Issue and Static Scheduling

P218

Multiple-issue processors come in three major flavors:

Statically scheduled superscalar processors
VLIW (very long instruction word) processors
Dynamically scheduled superscalar processors

The two types of superscalar processors issue varying numbers of instructions per clock and use in-order execution if they are statically scheduled or out-of-order execution if they are dynamically scheduled.

Although statically scheduled superscalars issue a varying rather than a fixed number of instructions per clock, they are actually closer in concept to VLIWs because both approaches rely on the compiler to schedule code for the processor

Because of the diminishing advantages of a statically scheduled superscalar as the issue width grows, statically scheduled superscalars are used primarily for narrow issue widths, normally just two instructions

P219

as we will see later in this chapter, the growth in overhead is a major factor limiting wider issue processors

3.8 Exploiting ILP Using Dynamic Scheduling, Multiple Issue, and Speculation

P222

Two different approaches have been used to issue multiple instructions per clock in a dynamically scheduled processor, and both rely on the observation that the key is assigning a reservation station and updating the pipeline control tables.

One approach is to run this step in half a clock cycle so that two instructions can be processed in one clock cycle;
A second alternative is to build the logic necessary to handle two or more instructions at once, including any possible dependences between the instructions.

P223

A key observation is that we cannot simply pipeline away the problem pipeline away the porblem is what ?

Modern superscalar processors that issue four or more instructions per clock may include both approaches: They both pipeline and widen the issue logic

By making instruction issues take multiple clocks because new instructions are issuing every clock cycle, we must be able to assign the reservation station and to update the pipeline tables so that a dependent instruction issuing on the next clock can use the updated information

where is the pipeline table, no definition at all

P224

In a modern superscalar, every possible combination of dependent instructions that is allowed to issue in the same clock cycle must be considered. Because the number of possibilities climbs as the square of the number of instructions that can be issued in a clock, the issue step is a likely bottleneck for attempts to go beyond four instructions per clock.

Assign a reservation station and a reorder buffer for every instruction that might be issued in the next issue bundle
Analyze all the dependences among the instructions in the issue bundle
If an instruction in the bundle depends on an earlier instruction in the bundle, use the assigned reorder buffer number to update the reservation table for the dependent instruction

Of course, what makes the preceding very complicated is that it is all done in parallel in a single clock cycle!

if we keep dependences, we can issue multiple instructions at the same time

P225

To illustrate the complexity of this process, Figure 3.22 shows the issue logic for one case: issuing a load followed by a dependent FP operation.

For the issuing instructions, rd1 and rd2 are the destinations; rs1, rs2, and rt2 are the sources (the load has only one source); x1 and x2 are the reservation stations allocated; and b1 and b2 are the assigned ROB entries. RS is the reservation station data structure. RegisterStat is the register data structure, Regs represents the actual registers, and ROB is the reorder buffer data structure.

Notice that we need to have assigned reorder buffer entries for this logic to operate properly, and recall that all these updates happen in a single clock cycle in parallel, not sequentiall

if (RegisterStat[rs1].Busy){ /*in-flight instr. writes rs*/
  h = RegisterStat[rs1].Reorder;
  if (ROB[h].Ready){ /* Instr completed already */
    RS[x1].Vj = ROB[h].Value;
    RS[x1].Qj = 0;
  } else {
    RS[x1].Qj = h;
  }
} else { /* wait for instruction */
  RS[x1].Vj = Regs[rs];
  RS[x1].Qj = 0;
};

RS[x1].Busy = yes;
RS[x1].Dest = b1;

ROB[b1].Instruction = Load;
ROB[b1].Dest = rd1;
ROB[b1].Ready = no;

RS[r].A = imm1;

RegisterStat[rt1].Reorder = b1;
RegisterStat[rt1].Busy = yes;

ROB[b1].Dest = rt1; // this line should be a mistake

if benefit is of sequensial issue is keeping the dependence if there is !

P226

A example show the speculation is important for efficiency cover this soon

3.9 Advanced Techniques for Instruction Delivery and Speculation

P228

In a high-performance pipeline, especially one with multiple issues, predicting branches well is not enough; we actually have to be able to deliver a high-bandwidth instruction stream

Branch-Targe Buffers Of course, fetching these instructions requires wide enough paths to the instruction cache, but the most difficult aspect is handling branches

I can not feel the difficult at all, just fetch as many instruction as cache supply, so what ?

A branch-prediction cache that stores the predicted address for the next instruction after a branch is called a branch-target buffer or branch-target cache

If a matching entry is found in the branch-target buffer, fetching begins immediately at the predicted PC

Note that unlike a branch-prediction buffer, the predictive entry must be matched to this instruction because the predicted PC will be sent out before it is known whether this instruction is even a branch. If the processor did not check whether the entry matched this PC, then the wrong PC would be sent out for instructions that were not branches, resulting in worse performance.

unlike branch-prediction buffer, so how branch-prediction works ? check whether the entry matched this PC, check what ?

P229

Dealing with the mispredictions and misses is a significant challenge because we typically will have to halt instruction fetch while we rewrite the buffer entry

P231

One variation on the branch-target buffer is to store one or more target instructions instead of, or in addition to, the predicted target address.

First, it allows the branch-target buffer access to take longer than the time between successive instruction fetches, possibly allowing a larger branch-target buffer
Second, buffering the actual target instructions allows us to perform an optimization called branch folding. Branch folding can be used to obtain 0-cycle unconditional branches and sometimes 0-cycle conditional branches

the first reason seems stupid, not it allow, it’s it made have to

P232

As we try to increase the opportunity and accuracy of speculation, we face the challenge of predicting indirect jumps, that is, jumps whose destination address varies at runtime.

To overcome this problem, some designs use a small buffer of return addresses operating as a stack

In large server applications, indirect jumps also occur for various function calls and control transfers

control transfer is what ? any differences ?

Although a simple predictor like gshare does a good job of predicting many conditional branches, it is not tailored to predicting loop branches, especially for long running loops

With the emergence of tagged hybrid predictors, which are as good at predicting loop branches, some recent designers have opted to put the resources into larger tagged hybrid predictors rather than a separate loop branch predictor.

P233

Integrated Instruction Fetch Units

Essentially, this amounts to recognizing that characterizing instruction fetch as a simple single pipe stage given the complexities of multiple issue is no longer valid.

本质上来说，这相当于认识到将指令读取作为一个简单的流水线阶段让多发射不在复杂。

Instead, recent designs have used an integrated instruction fetch unit that integrates several functions:

Integrated branch prediction
Instruction prefetch
Instruction memory access and buffering

P234

Speculation Support: Register Renaming Versus Reorder Buffers

who can tell me, what is register rename ?

key: think of architectural registers as names, not locations 0. can have more locations than names

dynamically map names to locations
map table holds the current mappings (name→location)
write: allocate new location and record it in map table
read: find location of most recent write by name lookup in map table
minor detail: must de-allocate locations appropriately

P236

Without speculation, there is little motivation to try to increase the issue rate beyond two, three, or possibly four issues per clock because resolving branches would limit the average issue rate to a smaller number.

All the dependences must be detected the physical registers must be assigned, and the instructions must be rewritten using the physical register numbers: in one clock.

The difficulty is that all this renaming and replacement of architectural registers by physical renaming registers happens effectively in 1 cycle, not sequentially. The issue logic must find all the dependences and “rewrite” the instruction in parallel

where and when pysical register, map, architectural register are introduce in register renaming ? but it din’t explained clearly at all

The Commit step is the dual of the issue step, and the requirements are similar, so let’s take a look at what has to happen for a six-issue processor using register renaming.

dual, how, can’t follow author’s idea at all

P237

How much to speculate To maintain most of the advantage while minimizing the disadvantages, most pipelines with speculation will allow only low-cost exceptional events (such as a first-level cache miss) to be handled in speculative mode.

P238

Speculating Through Multiple Branches In the examples we have considered in this chapter, it has been possible to resolve a branch before having to speculate on another. Three different situations can benefit from speculating on multiple branches simultaneously:

a very high branch frequency,
significant clustering of branches, and
long delays in functional units

Speculation and the Challenge of Energy Efficiency At first glance, one might argue that using speculation always decreases energy efficiency because whenever speculation is wrong, it consumes excess energy in two ways:

Instructions that are speculated and whose results are not needed generate excess work for the processor, wasting energy.
Undoing the speculation and restoring the state of the processor to continue execution at the appropriate address consumes additional energy that would not be needed without speculation

Figure 3.30 if 164.gzip and other integer program can cause up to 40% extra misspeculation instruction, how can the rate of misspeculation is only 3% as Figure 3.6 suggests.

P239

Address Aliasing Prediction Address aliasing prediction is a technique that predicts whether two stores or a load and a store refer to the same memory address

Address prediction relies on the ability of a speculative processor to recover after a misprediction;

Appendix

https://en.wikipedia.org/wiki/Branch_predictor

本站所有文章转发 CSDN 将按侵权追究法律责任，其它情况随意。