指令级并行性与利用：计算机体系结构中的关键概念

需积分: 14 45 浏览量更新于2024-07-14 收藏 1.44MB PDF 举报

"Computer Architecture A Quantitative Approach (5th edition) 的第201至400页内容涉及了指令级并行性和其利用方法。" 在计算机架构中，指令级并行性（Instruction-Level Parallelism, ILP）是提高处理器性能的关键技术之一。通过消除依赖关系，可以实现更高的并行度。本节主要讨论了如何处理和利用三种类型的依赖：数据依赖、控制依赖和地址生成依赖。其中，数据依赖是最常见的一种，它阻止了两个操作在同一时间对同一数据进行处理。书中举例说明了一个浮点除法、加法、存储、减法和乘法的序列，并指出这三种依赖都可以通过寄存器重命名（Register Renaming）来消除。寄存器重命名是一种优化技术，它通过创建临时寄存器（如S和T），使得原始序列中的依赖关系不再存在。这样，原本的指令序列可以被改写为无依赖的形式，从而允许并行执行。例如，通过将F8的结果暂存到T寄存器，可以避免在后续指令中直接引用F8，这样就消除了数据依赖。然而，为了找到所有需要替换F8的使用位置，可能需要复杂的编译器分析或者硬件支持，因为可能存在分支指令干扰。 Tomasulo算法是处理寄存器重命名的一种高效方法，特别是在存在分支指令的情况下。在Tomasulo的方案中，通过预订站（Reservation Stations）来实现寄存器重命名。预订站的作用是缓冲等待发出指令的操作数，一旦操作数可用，它就会立即获取并存储，这样就不必从寄存器中获取，从而减少了延迟。每个预订站可以存储即将执行的指令的运算符，这样就可以在指令发射之前预先准备它们，即使这些指令可能来自不同的分支。这种机制使得处理器能够在不影响正确性的前提下，有效地管理和调度跨分支的指令，从而最大化利用了指令级并行性。此外，Tomasulo算法还涉及到冲突检测和解决、资源分配以及操作数的早期计算等复杂问题，这些都是为了确保指令可以在适当的时间并行执行，提升处理器性能。通过这种方式，处理器设计者能够克服流水线中的障碍，实现更高效的计算。 "Computer Architecture A Quantitative Approach (5th edition)"的这一部分深入探讨了指令级并行性的重要概念和技术，包括寄存器重命名和Tomasulo算法，这些都是现代高性能处理器设计中的核心内容。通过理解并应用这些技术，可以显著提高处理器的计算效率和吞吐量。

3.6 Hardware-Based Speculation ■ 187

was wrong. The ROB is flushed and execution is restarted at the correct succes-

sor of the branch. If the branch was correctly predicted, the branch is finished.

Once an instruction commits, its entry in the ROB is reclaimed and the regis-

ter or memory destination is updated, eliminating the need for the ROB entry. If

the ROB fills, we simply stop issuing instructions until an entry is made free.

Now, let’s examine how this scheme would work with the same example we used

for Tomasulo’s algorithm.

Example Assume the same latencies for the floating-point functional units as in earlier exam-

ples: add is 2 clock cycles, multiply is 6 clock cycles, and divide is 12 clock cycles.

Using the code segment below, the same one we used to generate Figure 3.8, show

what the status tables look like when the MUL.D is ready to go to commit.

L.D F6,32(R2)

L.D F2,44(R3)

MUL.D F0,F2,F4

SUB.D F8,F2,F6

DIV.D F10,F0,F6

ADD.D F6,F8,F2

Answer Figure 3.12 shows the result in the three tables. Notice that although the SUB.D

instruction has completed execution, it does not commit until the MUL.D commits.

The reservation stations and register status field contain the same basic informa-

tion that they did for Tomasulo’s algorithm (see page 176 for a description of

those fields). The differences are that reservation station numbers are replaced

with ROB entry numbers in the Qj and Qk fields, as well as in the register status

fields, and we have added the Dest field to the reservation stations. The Dest field

designates the ROB entry that is the destination for the result produced by this

reservation station entry.

The above example illustrates the key important difference between a proces-

sor with speculation and a processor with dynamic scheduling. Compare the con-

tent of Figure 3.12 with that of Figure 3.8 on page 179, which shows the same

code sequence in operation on a processor with Tomasulo’s algorithm. The key

difference is that, in the example above, no instruction after the earliest uncom-

pleted instruction (MUL.D above) is allowed to complete. In contrast, in Figure 3.8

the SUB.D and ADD.D instructions have also completed.

One implication of this difference is that the processor with the ROB can

dynamically execute code while maintaining a precise interrupt model. For

example, if the MUL.D instruction caused an interrupt, we could simply wait until

it reached the head of the ROB and take the interrupt, flushing any other pending

instructions from the ROB. Because instruction commit happens in order, this

yields a precise exception.

By contrast, in the example using Tomasulo’s algorithm, the SUB.D and

ADD.D instructions could both complete before the MUL.D raised the exception.

188 ■ Chapter Three Instruction-Level Parallelism and Its Exploitation

The result is that the registers F8 and F6 (destinations of the SUB.D and ADD.D

instructions) could be overwritten, and the interrupt would be imprecise.

Some users and architects have decided that imprecise floating-point excep-

tions are acceptable in high-performance processors, since the program will

likely terminate; see Appendix J for further discussion of this topic. Other types

of exceptions, such as page faults, are much more difficult to accommodate if

they are imprecise, since the program must transparently resume execution after

handling such an exception.

The use of a ROB with in-order instruction commit provides precise excep-

tions, in addition to supporting speculative execution, as the next example shows.

Reorder buffer

Entry Busy Instruction State Destination Value

1NoL.D F6,32(R2) Commit F6 Mem[32 + Regs[R2]]

2NoL.D F2,44(R3) Commit F2 Mem[44 + Regs[R3]]

3YesMUL.D F0,F2,F4 Write result F0 #2 × Regs[F4]

4YesSUB.D F8,F2,F6 Write result F8 #2 – #1

5YesDIV.D F10,F0,F6 Execute F10

6YesADD.D F6,F8,F2 Write result F6 #4 + #2

Reservation stations

Name Busy Op Vj Vk Qj Qk Dest A

Load1 No

Load2 No

Add1 No

Add2 No

Add3 No

Mult1 No MUL.D Mem[44 + Regs[R3]] Regs[F4] #3

Mult2 Yes DIV.D Mem[32 + Regs[R2]] #3 #5

FP register status

Field F0F1F2F3F4F5 F6F7 F8F10

Reorder # 3 6 4 5

Busy YesNoNoNoNoNoYes. . . YesYes

Figure 3.12 At the time the MUL.D is ready to commit, only the two L.D instructions have committed, although

several others have completed execution. The MUL.D is at the head of the ROB, and the two L.D instructions are

there only to ease understanding. The SUB.D and ADD.D instructions will not commit until the MUL.D instruction

commits, although the results of the instructions are available and can be used as sources for other instructions.

The DIV.D is in execution, but has not completed solely due to its longer latency than MUL.D. The Value column

indicates the value being held; the format #X is used to refer to a value field of ROB entry X. Reorder buffers 1 and

2 are actually completed but are shown for informational purposes. We do not show the entries fo

r the load/store

queue, but thes

e entries are kept in order.

190 ■ Chapter Three Instruction-Level Parallelism and Its Exploitation

Because neither the register values nor any memory values are actually writ-

ten until an instruction commits, the processor can easily undo its speculative

actions when a branch is found to be mispredicted. Suppose that the branch BNE

is not taken the first time in Figure 3.13. The instructions prior to the branch will

simply commit when each reaches the head of the ROB; when the branch reaches

the head of that buffer, the buffer is simply cleared and the processor begins

fetching instructions from the other path.

In practice, processors that speculate try to recover as early as possible

after a branch is mispredicted. This recovery can be done by clearing the ROB

for all entries that appear after the mispredicted branch, allowing those that

are before the branch in the ROB to continue, and restarting the fetch at the

correct branch successor. In speculative processors, performance is more sen-

sitive to the branch prediction, since the impact of a misprediction will be

higher. Thus, all the aspects of handling branches—prediction accuracy,

latency of misprediction detection, and misprediction recovery time—increase

in importance.

Exceptions are handled by not recognizing the exception until it is ready to

commit. If a speculated instruction raises an exception, the exception is recorded

in the ROB. If a branch misprediction arises and the instruction should not have

been executed, the exception is flushed along with the instruction when the ROB

is cleared. If the instruction reaches the head of the ROB, then we know it is no

longer speculative and the exception should really be taken. We can also try to

handle exceptions as soon as they arise and all earlier branches are resolved, but

this is more challenging in the case of exceptions than for branch mispredict and,

because it occurs less frequently, not as critical.

Figure 3.14 shows the steps of execution for an instruction, as well as the

conditions that must be satisfied to proceed to the step and the actions taken. We

show the case where mispredicted branches are not resolved until commit.

Although speculation seems like a simple addition to dynamic scheduling, a

comparison of Figure 3.14 with the comparable figure for Tomasulo’s algorithm

in Figure 3.9 shows that speculation adds significant complications to the con-

trol. In addition, remember that branch mispredictions are somewhat more com-

plex as well.

There is an important difference in how stores are handled in a speculative

processor versus in Tomasulo’s algorithm. In Tomasulo’s algorithm, a store can

update memory when it reaches write result (which ensures that the effective

address has been calculated) and the data value to store is available. In a specula-

tive processor, a store updates memory only when it reaches the head of the

ROB. This difference ensures that memory is not updated until an instruction is

no longer speculative.

Figure 3.14 has one significant simplification for stores, which is unneeded

in practice. Figure 3.14 requires stores to wait in the write result stage for the

from the Vk field of the store’s reservation station to the Value field of the

store’s ROB entry. In reality, however, the value to be stored need not arrive

3.6 Hardware-Based Speculation ■ 191

Status Wait until Action or bookkeeping

Issue

all

instructions

Reservation

station (r)

and

ROB (b)

both available

if (RegisterStat[rs].Busy)/*in-flight instr. writes rs*/

{h ← RegisterStat[rs].Reorder;

if (ROB[h].Ready)/* Instr completed already */

{RS[r].Vj ← ROB[h].Value; RS[r].Qj ← 0;}

else {RS[r].Qj ← h;} /* wait for instruction */

} else {RS[r].Vj ← Regs[rs]; RS[r].Qj ← 0;};

RS[r].Busy ← yes; RS[r].Dest ← b;

ROB[b].Instruction ← opcode; ROB[b].Dest ← rd;ROB[b].Ready ← no;

operations

and stores

if (RegisterStat[rt].Busy) /*in-flight instr writes rt*/

{h ← RegisterStat[rt].Reorder;

if (ROB[h].Ready)/* Instr completed already */

{RS[r].Vk ← ROB[h].Value; RS[r].Qk ← 0;}

else {RS[r].Qk ← h;} /* wait for instruction */

} else {RS[r].Vk ← Regs[rt]; RS[r].Qk ← 0;};

FP operations RegisterStat[rd].Reorder ← b; RegisterStat[rd].Busy ← yes;

ROB[b].Dest ← rd;

Loads RS[r].A ← imm; RegisterStat[rt].Reorder ← b;

RegisterStat[rt].Busy ← yes; ROB[b].Dest ← rt;

Stores RS[r].A ← imm;

Execute

FP op

(RS[r].Qj == 0) and

(RS[r].Qk == 0)

Compute results—operands are in Vj and Vk

Load step 1 (RS[r].Qj == 0) and

there are no stores

earlier in the queue

RS[r].A ← RS[r].Vj + RS[r].A;

Load step 2 Load step 1 done and

all stores earlier in

ROB have different

address

Read from Mem[RS[r].A]

Store (RS[r].Qj == 0) and

store at queue head

ROB[h].Address ← RS[r].Vj + RS[r].A;

Write result

all but store

Execution done at r

and CDB available

b ← RS[r].Dest; RS[r].Busy ← no;

∀x(if (RS[x].Qj==b) {RS[x].Vj ← result; RS[x].Qj ← 0});

∀x(if (RS[x].Qk==b) {RS[x].Vk ← result; RS[x].Qk ← 0});

ROB[b].Value ← result; ROB[b].Ready ← yes;

Store Execution done at r

and (RS[r].Qk == 0)

ROB[h].Value ← RS[r].Vk;

Commit Instruction is at the

head of the ROB

(entry h) and

ROB[h].ready ==

yes

d ← ROB[h].Dest; /* register dest, if exists */

if (ROB[h].Instruction==Branch)

{if (branch is mispredicted)

{clear ROB[h], RegisterStat; fetch branch dest;};}

else if (ROB[h].Instruction==Store)

{Mem[ROB[h].Destination] ← ROB[h].Value;}

else /* put the result in the register destination */

{Regs[d] ← ROB[h].Value;};

ROB[h].Busy ← no; /* free up ROB entry */

/* free up dest register if no one else writing it */

if (RegisterStat[d].Reorder==h) {RegisterStat[d].Busy ← no;};

Figure 3.14 Steps in the algorithm and what is required for each step. For the issuing instruction, rd is the destina-

tion, rs and rt are the sources, r is the reservation station allocated, b is the assigned ROB entry, and h is the head entry

of the RO

B. RS is the res

ervation station data structure. The value returned by a reservation station is called the result.

RegisterStat is the registe r data structure, Regs represents the actual registers, and ROB is the reorder buffer data

structure.

剩余199页未读，继续阅读

baidu_34653586

粉丝: 0
资源: 6

指令级并行性与利用：计算机体系结构中的关键概念

计算机体系结构课后答案：Computer Architecture 3rd E解析

"计算机体系结构中期复习：定量方法与流水线设计"。

Computer Architecture第三版课后答案全解

Computer Architecture A Quantitative Approach (5th edition)-441-460.pdf

Computer Architecture A Quantitative Approach (5th edition)-421-440.pdf

Computer Architecture A Quantitative Approach (5th edition)-1-200.pdf

Computer Architecture A Quantitative Approach (5th edition)-401-420.pdf

computer architecture a quantitative approach 5th edition

Computer Architecture A Quantitative Approach 5th Edition

Computer Architecture A Quantitative Approach 5th

最新资源