当前位置: 首页 > >

高等计算机体系结构-课件-Lect10

发布时间:

高等计算机体系结构 (Advanced Computer Architecture)

(Instruction-Level Parallelism: Static Scheduling and Limits on ILP
李险峰 (lixianfeng@pkusz.edu.cn) 北京大学深圳研究生院

第八讲 指令级并行: 静态调度与 ILP 限制 静态调度与ILP ILP限制

ILP 的两种途径 挖掘 挖掘ILP ILP的两种途径
?硬件方法
? 指令的动态调度(dynamic scheduling) ? 代表性技术: 流水线(pipelining)、超标量 (superscalar)、推测式执行(speculative execution)

?软件方法
? 指令的静态调度(static scheduling) ? 代表性技术: 超长指令字技术(VLIW)、向量计算 (vector computation)、软件流水(software pipelining)

2

非相关性 ISA ISA非相关性
?传统ISA
? 指令以按顺序、非重叠方式执行

?未提供任何关于指令A和B是否相关的信息
? 需要在执行过程中依靠硬件动态发现:时间短、能力和范围有限、 复杂度高

?改进想法:
? 在ISA层面改变指令的执行模型 ? 允许显式说明指令间的非相关性

?VLIW的目标:
? 能灵活表达指令非相关性方面 ? 能克服硬件技术发展所遇到的*

?Vectors 和 SIMD
? 针对特定类型的计算非常有效,但对该类型之外的计算无能为力

3

高等计算机体系结构 (Advanced Computer Architecture)

1. VLIW / EPIC Processors

VLIW
?超长指令字VLIW: Very Long Instruction Word
Instruction format ALU1 ALU2 MEM1 control

?该指令中的四个操作是 非相关的 ?通过这种方式,指令级并行ILP得以显式表达

5

指令与资源分配 VLIW VLIW指令与资源分配
?VLIW指令格式同时也暗示了资源的分配
? 例如,如下的VLIW指令格式所对应在资源分配为: ALU1 ALU ALU2 ALU cache MEM1 control Control Flow Unit

6

VLIW: 定义
? 存在着多个非相关的功能单元Functional Units ? 指令有多个非相关的操作组成 ? 每个操作对应一个功能单元 ? 操作的延迟是固定的,而且是体系结构可见的(程序员非透明) ? 由编译器负责将多个操作封装成一条VLIW指令,并制定相应的硬件资源 调度 ? 整个VLIW作为一个整体同时发射 ? 益处: 通过简单的硬件即可获得ILP,同时也利于实现较高的时钟主频

7

VLIW Example
FU I-fetch & Issue FU
Memory Port Memory Port

Multi-ported Register File

8

VLIW Example
Instruction format ALU1 ALU2 MEM1 control

Program order and execution order ALU1 ALU2 MEM1 ALU1 ALU2 MEM1 ALU1 ALU2 MEM1

control control control

?VLIW中的指令是非相关的 ?各操作的延迟是固定的 ?硬件不做任何检查 ?软件负责指令的调度
9

“王” 编译器为 编译器为“
?VLIW的哲学:
? “dumb” hardware ? “intelligent” compiler

?面向VLIW的基础性软件调度技术
? 循环展开(Loop Unrolling) ? 判定执行(Predicated Execution) ? 踪迹调度(Trace Scheduling) ? 软件流水线(Software Pipelining)

10

“循环级”并行
?循环体是程序的核心部分, 程序执行的绝大部分时间耗费在 循环体上 ?“循环级”并行
? 跨越单次循环的指令并发执行机会(parallelism across loop iterations) ? 通过发掘循环级并行,可有效加速程序的执行

?为了将循环级并行转化为指令级并行,需要将循环“展开” (unroll),以便将更多指令“暴露”于调度算法视野之中,3种方法:
? 由硬件动态调度 (tomasulo算法中的寄存器重命名 + 推测式执行) ? 有编译器静态调度 ? 采用向量化指令 (对向量或数组中多个元素同时进行同样的操作)
11

支撑例子
for (i = 1000; i > 0; i--) x[i] = x[i] + s; LOOP: LOOP: L.D L.D ADD.D ADD.D S.D S.D DADDUI DADDUI BNEZ BNEZ NOP NOP
1 F

, F0 F0, , 0(R1) 0(R1) F0 F0, , , F4 F4, F0 F0, F4 , F0 , F2 F2 F4, F0, 0(R1), 0(R1), F4 F4 , R1 R1, , R1, R1, -8 -8 R1 R1, , LOOP R1 R1, , LOOP R1 R1,

几个假设 ?标量 s 对应寄存器 F2 ?向量 x 起始地址为0 ?分支延迟为1个时钟周期 ?不存在结构冒险
6 E F 7 E D F 8 E X D 9 M M X F 10 11 12 13 14 15 W W M D -

L.D ADD.D S.D DADDUI BNEZ NOP L.D

2 D -

3 X F

4 M D -

5 W E -

W X F

M D

W X M W

10 cycles per iteration
12

一些观察
?5条指令中,有3条是浮点运算,另外2条是与循环有 关的开销 ?是否可通过循环展开(loop unrolling)改善性能?
? 加上循环次数为4N次,将循环展开4次,得到一个新的N 次大循环体(实际当中,如果循环次数不是4的倍数,还 要进行一些特殊处理)

13

Unrolling: Take 1
LOOP: LOOP: L.D L.D ADD.D ADD.D S.D S.D DADDUI DADDUI L.D L.D ADD.D ADD.D S.D S.D DADDUI DADDUI L.D L.D ADD.D ADD.D S.D S.D DADDUI DADDUI L.D L.D ADD.D ADD.D S.D S.D DADDUI DADDUI BNEZ BNEZ NOP NOP , F0 F0, , 0(R1) 0(R1) F0 F0, , , F4 F4, F0 F0, , F0 , F2 F2 F4 F4, F0, 0(R1), F4 0(R1), F4 , R1 R1, , R1, R1, -8 -8 R1 R1, , 0( R1 ) F0 F0, 0(R1 R1) , 0( R1 ) F0 F0, 0(R1 R1) , , F2 F4 F4, F0 F0, , F0 , F2 F4 F4, F0, R1 ), 0( 0(R1 R1), 0( R1 ), F4 F4 0(R1 R1), , R1 R1, , R1, R1, -8 -8 R1 R1, F0 , 0( R1 ) F0, R1) , 0(R1 0( R1 ) F0 F0, 0(R1 R1) , , F2 F4 F4, F0 F0, , F0 , F2 F4 F4, F0, R1 ), 0( 0(R1 R1), 0( R1 ), F4 F4 0(R1 R1), , R1 R1, , R1, R1, -8 -8 R1 R1, , R1 ) F0 F0, 0(R1 R1) , 0( 0( R1 ) F0 F0, 0(R1 R1) , , F2 F4 F4, F0 F0, , F0 , F2 F4 F4, F0, R1 ), 0( 0(R1 R1), R1 ), F4 0( 0(R1 R1), F4 , R1, R1 R1, , R1, -8 -8 R1 R1, , R1 R1, , LOOP LOOP R1 R1,

? 展开后,尽管这连续4次循环执行之间的 控制依赖已经消除,但通过R1产生的数 据相关并未消除 ? 进一步观察,R1只是一个每次值减8的循 环变量,因此这种特殊的数据相关也可 以消除掉
? 调整两条访存指令L.D和S.D的地址表达方 式, ? 删去前面3条DADDUI指令 ? 将第4条DADDUI指令中的常量变为32 (一次性减去4次循环的改变)

? 对编译器来说,这种“推导”并不是轻 而易举的
14

Unrolling: Take 2
LOOP: LOOP: L.D L.D ADD.D ADD.D S.D S.D L.D L.D ADD.D ADD.D S.D S.D L.D L.D ADD.D ADD.D S.D S.D L.D L.D ADD.D ADD.D S.D S.D DADDUI DADDUI BNEZ BNEZ NOP NOP , F0 F0, F0 , 0(R1) 0(R1) F0, , , F4 F4, F0, , F0 , F2 F2 F4 F4, F0 F0, 0(R1), 0(R1), F4 F4 , -8(R1) F0 F0, , -8(R1) F0 F0, , , F4 F4, F0, , F0 , F2 F2 F4 F4, F0 F0, -8(R1), -8(R1), F4 F4 , F0 F0, , -16(R1) -16(R1) F0 F0, , , F4 F4, F0 F0, , F0 , F2 F2 F4 F4, F0, -16(R1), -16(R1), F4 F4 , -24(R1) F0 F0, F0 , -24(R1) F0, , , F4 F4, F0, , F0 , F2 F2 F4 F4, F0 F0, -24(R1), -24(R1), F4 F4 , R1, -32 R1 R1, , R1, -32 R1 R1, , R1 R1, , LOOP LOOP R1 R1,

?到目前为止,除了不能消除的 数据真相关之外,性能还受限 于与F0有关的WAR相关 ?这种相关是可通过寄存器重命 名消除的伪相关

15

Unrolling: Take 3
LOOP: LOOP: L.D L.D ADD.D ADD.D S.D S.D L.D L.D ADD.D ADD.D S.D S.D L.D L.D ADD.D ADD.D S.D S.D L.D L.D ADD.D ADD.D S.D S.D DADDUI DADDUI BNEZ BNEZ NOP NOP , F0 F0, F0 , 0(R1) 0(R1) F0, , , F4 F4, F0, , F0 , F2 F2 F4 F4, F0 F0, 0(R1), 0(R1), F4 F4 , -8(R1) F6 F6, , -8(R1) F6 F6, , , F8 F8, F6, , F6 , F2 F2 F8 F8, F6 F6, -8(R1), F8 -8(R1), F8 , F10 F10, , -16(R1) -16(R1) F10 F10, , , F12 F12, F10 F10, , F10 , F2 F2 F12 F12, F10, -16(R1), F12 -16(R1), F12 , F14 F14, F14 , -24(R1) -24(R1) F14, , , F16 F16, F14, , F14 , F2 F2 F16 F16, F14 F14, -24(R1), F16 -24(R1), F16 , R1 R1, , R1, R1, -32 -32 R1 R1, , LOOP R1 R1, , LOOP R1 R1,

?现在,执行4次循环的时间计 算:
? 14 instruction cycles ? 4 L.D→ADD.D stalls ? 8 ADD.D→S.D stalls ? 1 DADDUI→BNEZ stall ? 1 branch delay stall (NOP)

?4次循环总共需要执行28个时 钟周期,*均每次循环执行7 个时钟周期 ?还可进一步对这个循环展开后 的代码进行调度优化
16

Unrolling: Take 4
LOOP: LOOP: L.D L.D L.D L.D L.D L.D L.D L.D ADD.D ADD.D ADD.D ADD.D ADD.D ADD.D ADD.D ADD.D S.D S.D S.D S.D DADDUI DADDUI S.D S.D BNEZ BNEZ S.D S.D F0, F0, 0(R1) 0(R1) F6, -8(R1) F6, -8(R1) F10, F10, -16(R1) -16(R1) F14, -24(R1) F14, -24(R1) F4, F4, F0, F0, F2 F2 F8, F8, F6, F6, F2 F2 F12, F10, F12, F10, F2 F2 F16, F14, F2 F16, F14, F2 0(R1), 0(R1), F4 F4 -8(R1), -8(R1), F8 F8 R1, R1, -32 R1, R1, -32 16(R1), 16(R1), F12 F12 R1, LOOP R1, LOOP 8(R1), 8(R1), F16 F16

? 这个重新调度后的代码没有停顿
? 14 cycles for 4 iterations ? 3.5 cycles per iteration ? 循环控制开销 = 每4次循环有一次开销

? 循环展开有效的将来自于不同循环次 中的非相关指令暴露于调度之下 ? 如果继续循环展开下去,理论上可达 到 3 cycles per instruction
? 但实际上除了受限于可供展开的循环次 数外,还受限于可用的寄存器

17

循环展开的受益限制
?循环开销降低的效果随着循环展开的次数增加迅速 衰减 ?代码增加的负面影响
? 随着循环展开的次数增加,静态代码的增加逐渐成为一个 负面因素,尤其对内存资源较受限的嵌入式处理器来说 ? 指令cache失效率上升

?体系结构和编译器限制
? 寄存器压力:需要许多体系结构寄存器来发掘ILP
18

“王” 编译器为 编译器为“
?VLIW的哲学:
? “dumb” hardware ? “intelligent” compiler

?面向VLIW的基础性软件调度技术
? 循环展开(Loop Unrolling) ? 判定执行(Predicated Execution) ? 踪迹调度(Trace Scheduling) ? 软件流水线(Software Pipelining)

19

判定执行
?条件执行指令
? if (cond) then perform instruction

?判定执行(Predicated execution)
? 将控制相关转换为数据相关

?if ( a == 0) b = 1; else b = 2; true; pred = (a == 0) pred; b=1 !pred; b = 2
20

判定化指令
?将一个条件测试结果保存在一个1-bit的判断寄存器中 ?判定化指令(Predicated instrs)使用一个判定寄存器作为 一个额外的输入操作数 ?判断化指令象普通指令一样被取指、译码和进入指令窗口中 ?至于判定化指令在其判定结果出来之前,会在流水线中前行 多久,则取决于具体的体系结构: ? 一种情况:一个判断化指令,只有在其判定词结果为真时 才被真正执行,否则将被丢弃 ? 另一种情况:判断化指令可在未得到判定词结果之前被执 行,但只有在判定词为真的情况下才能提交 (Intel IA-64)
21

判定的利弊
?分支以及与分支有关的预测被消除 ?基本块大小增加的增加,有利于编译器调度 ?对于一些小的if-then控*峁固乇鹩行В蛭ü卸ㄏ 控制相关,可使得if-then结构之后的指令能尽早被调度执行

?判定改变了指令系统,需要增加一个额外的寄存器端口,指 令的执行(在语义上)变得更加复杂 ?被丢弃的判定化指令仍然消耗了处理器资源,例如取指带宽

22

Prediction vs Predication
?Prediction
? 推测一个分支方向,并沿着该方向推测式执行 ? 如果推测错误,取消推测执行的效果,然后重新沿着正 确方向执行 ? 有效性与分支预测技术的正确率和从分支预测错误中及 时恢复的能力密切相关

?Predication
? 两个分支方向的指令分别由两个相反的判定词保护,他 们在分支结果出来之前,都有机会获得判定式执行 ? 分支结果出来之后,由判定词为真保护的指令获得回写 结果的机会,另一方指令的结果被丢弃 ? 有效性与是否有足够的能并发执行指令的功能单元有关
23

“王” 编译器为 编译器为“
?VLIW的哲学:
? “dumb” hardware ? “intelligent” compiler

?面向VLIW的基础性软件调度技术
? 循环展开(Loop Unrolling) ? 判定执行(Predicated Execution) ? 踪迹调度(Trace Scheduling) ? 软件流水线(Software Pipelining)

24

踪迹调度
?编译器调度的一个困境:
? 大多数基本块都过小 ? 跨基本块调度很困难

?目标: 创建一个足够大的连续代码段,在该代码段中指令可自由调度 ?观察: 尽管存在这许多控制流路径,但只有少数路径是“热 径”(hot path) ?踪迹调度
? 通过静态控制推测形成具体的热径 ? 对热径进行指令调度 ? 需要有检验机制和修复代码,在程序实际未沿热径执行时确保正确 性
25

1 踪迹调度示例 踪迹调度示例1
A
Assume A?C is the common path le u ed A h sc

A&C

B

C
Repair

C B

Expand the scope/flexibility of code motion
26

2 踪迹调度示例 踪迹调度示例2
A B C D E A B C D check

repair C D

repair E all OK

27

踪迹调度代码示例
test = a[i] + 20; If (test > 0) then sum = sum + 10 else sum = sum + c[i] c[x] = c[y] + 10 assume delay

Straight code

test = a[i] + 20 sum = sum + 10 c[x] = c[y] + 10 if (test <= 0) then goto repair

repair: sum = sum – 10 sum = sum + c[i]



28

另一种踪迹调度 : 另一种踪迹调度: If-Conversion ?If-conversion: 将踪迹调度与判定式执行结合起来 ?为避免产生修复代码,可对较大一段代码路径进行 判定,形成一个单一的、消除了分支的调度踪迹 ?调度时,代码可在踪迹内自由移动,不再受控制流 的制约,而只受限与数据相关

29

“王” 编译器为 编译器为“
?VLIW的哲学:
? “dumb” hardware ? “intelligent” compiler

?面向VLIW的基础性软件调度技术
? 循环展开(Loop Unrolling) ? 判定执行(Predicated Execution) ? 踪迹调度(Trace Scheduling) ? 软件流水线(Software Pipelining)

30

软件流水线
象征性循环展开 ?既有循环展开的好处,又不明显增加代码体积 ?转换后的循环体为原循环体中不同循环次数的指令的组合
? 客观上增加了相关指令间的距离,减少了数据冒险机会

31

软件流水例子

软件流水(循环体)

32

软件流水完整构成

33

软件流水 vs 循环展开
?循环展开 减少了循环的开销,且提供了更多指令用于调度 ?软件流水 循环次数间的重叠更加充分,从而有更高的ILP

34

历史 VLIW VLIW历史
?与超标量技术相比,VLIW的发展要曲折的多
? Floating Point Systems Array Processor ? 二十世纪七十年代期间曾非常成功 ? 所有的延迟都是固定不变值; 快速存储器

?Multiflow
? 1980年代初的小型超级计算机,由Josh Fisher提出

?Cydrome
? 1980年代初的小型超级计算机,由Bob Rau提出

?Tera
? 1990年代初的超级计算机,由Burton Smith提出

?Intel IA-64 (Intel & HP)
? Intel称其为“EPIC”体系结构,是VLIW与Superscalar的结合 ? EPIC: Explicitly Parallel Instruction Computing
35

IA-64 ISA 与Itanium ISA与
?由HP和Intel自1994年开始联合研发 ?该体系结构被称为EPIC(VLIW +Superscalar): ? 在指令系统中显式指明ILP(继承了VLIW) ? 一套完全可判定化的指令系统(继承了VLIW) ? 可扩展的ISA (可扩展到很多功能单元) ? 丰富的体系结构寄存器

36

Intel's IA-64 ISA
?128个64位通用寄存器 GR0-GR127,保存整型计算和多媒 体计算结果 ?128个82位浮点寄存器FR0-FR127 ? 其中寄存器f0和f1为只读寄存器,分别为固定值 +0.0 和 +1.0 ?64个1位判定寄存器 PR0-PR63 ? 其中寄存器PR0是只读寄存器,值总是为1(true) ?8个64位分支寄存器BR0-BR7,用来指明间接分支指令的目 标地址
37

IA-64 的大寄存器堆 IA-64的大寄存器堆
Integer Registers 63 0 GR0 GR1 GR31 GR32 0 Floating-Point Registers 81 0 GR0 GR1 GR31 GR32 0.0 BR0 BR7 Branch Registers 63 0 Predicate Registers bit 0 PR0 1 PR1 PR15 PR16 PR63 32 Static 96 Rotating 16 Static 48 Rotating

GR127 NaT 32 Static

GR127

96 Stacked, Rotating

38

Intel's IA-64 ISA
? IA-64 指令 字长为41位,包含如下几个域 ? op-code, ? predicate field (6 bits), ? two source register addresses (7 bits each), ? destination register address (7 bits), and ? special fields (includes integer and floating-point arithmetic). ? 其中,6位的predicate field是访问64个判定寄存器的寄存器号 ? 6 种指令类型 ? A: Integer ALU ? I-unit or M-unit ? I-unit ? I: Non-ALU integer ? M-unit ? M: Memory ? B-unit ? B: Branch ? F: Floating-point ? F-unit ? I-unit ? L: Long Immediate ? IA-64指令由编译器打包形成一个簇(bundle),作为最小可调度单位
39

IA-64 bundles
? 一个bundle 为一个128位的长指令字 (LIW),包含3个41位的IA-64指 令和一个5位的模板(template),指明指令组合信息 ? 一个模板指明的信息包括: ? 前4位: 组成bundle的指令类型 ? 最后一位 (stop bit): 该bundle是否可与下一个bundle并发执行 ? 同一个bundle中的指令不一定按原程序顺序形成bundle,它们甚至可 来源于不同的分支路径 ? 而且,编译器还可以就爱那个相关和非相关指令都混合在一个 bundle 中,因为模板可跟踪相关信息

40

IA-64 bundles
128 bits (bundle)
Instruction 2 41 bits Instruction 1 41 bits Instruction 0 41 bits Template 5 bits

Memory (M)

Memory (M)

Integer (I)

(MMI)

? IA-64指令模板指出 ? 每一个指令的类型 ? MFI, MMI, MII, MLI, MIB, MMF, MFB, MMB, MBB, BBB ? bundle内指令关系 ? M / MI or MI / I ? bundle间关系 ? 仍有空间预留给将来的模板

M=Memory F=Floating-point I=Integer L=Long Immediate B=Branch
41

IA-64 ISA 中的判定执行 ISA中的判定执行
?为避免分支预测错误的高昂代价,编译器寻找分支 指令,并为各分支路径上的指令赋予响应的判定寄 存器
? 6位寄存器,定位IA-64体系结构中64个判定寄存器

?位于通用分支路径上的指令共享同一个判定寄存器 对于有些不能消除的分支指令,IA-64也提供一种 先进的分支预测技术
42

If-then-else statement

43

IA-64 ISA 的判定执行 ISA的判定执行
?程序运行时,CPU扫描模板,根据模板信息,从中挑选出非 相关指令并行发射到功能单元中 ?判定化分支指令: 不同分支方向的指令都得到机会执行,但 在未检验判定寄存器之前,任何分支上的指令结果都还不能 被保存 ?处理器检查这些指令的判定寄存器 ? 如果判定寄存器值为1,则该指令在正确路径上,处理器 让该指令正常“退休“,并保存结果 ? 如果判定寄存器值为0,
?

则该指令为错误指令,处理器丢弃该指令和相应结果
44

通过轮转寄存器( rotating register ) 通过轮转寄存器(rotating register) 实现软件流水
?软件流水 - 通过重叠循环体不同执行次中的指令提高性能
Sequential Loop Execution Software Pipelining Loop Execution

Time

Time

45

rotating register ) 通过轮转寄存器( 通过轮转寄存器(rotating register) 实现软件流水
?轮转寄存器 ? Floating-point: f32-f127 ? General-purpose: g32-g127; ? Predicate: p16-p63 ?其它需要的寄存器: ? 轮转寄存器指针寄存器 ?rr.pr (6 bit) ?rr.fr (7 bit) ?rr.gr (7 bit) ? 。。。
46

概念 结构 Itanium Itanium概念 概念结构

47

处理器流水线 Itanium Itanium处理器流水线

ROT: instruction rotation pipelined access of the large register file: WDL: word line decode: REG: register read DET: exception detection (~retire stage)
48

流水线前端 Itanium Itanium流水线前端

49

处理器 Itanium Itanium处理器

50

高等计算机体系结构 (Advanced Computer Architecture)

Vector Processors ) 2. 向量处理器( 向量处理器(Vector Processors)

传统超级计算机应用
? 典型应用领域
? ? ? ? ? 军事研究 (核武器, 密码) 科学研究(分子计算,化学反应,流体力学,。。。) 天气预报 石油勘探 工业设计 (汽车撞击模拟,。。。)

?所有这些都需要对海量数据的复杂加工计算 ?1970s-1980s, Supercomputer ≡ Vector Machine

52

向量超级计算机
?Epitomized by Cray-1, 1976:
? Scalar Unit + Vector Extensions
? Load/Store Architecture ? Vector Registers ? Vector Instructions ? Hardwired Control ? Highly Pipelined Functional Units ? Interleaved Memory System ? No Data Caches ? No Virtual Memory

53

Vector Programming Model
Scalar Registers Vector Registers

r15

v15

r0

v0

[0]

[1]

[2] VLR

[VLRMAX-1]

Vector Length Register

Vector Arithmetic Instructions ADDV v3, v1, v2 Vector Load and Store Instructions LV v1, r1, r2 Base, r1

v1 v2
+ + + + + +

v3 [0] v1 [1]
Vector Register

[VLR-1]

Stride, r2

Memory

54

Vector Code Example
# Vector Code # Scalar Code # C code LI VLR, 64 LI R4, 64 for (i=0; i<64; i++) LV V1, R1 C[i] = A[i] + B[i]; loop: LV V2, R2 L.D F0, 0(R1) ADDV.D V3, V1, V2 L.D F2, 0(R2) SV V3, R3 ADD.D F4, F2, F0 S.D F4, 0(R3) DADDIU R1, 8 DADDIU R2, 8 DADDIU R3, 8 DSUBIU R4, 1 BNEZ R4, loop

55

Vector Instruction Execution
ADDV C,A,B
Execution using one pipelined functional unit Execution using four pipelined functional units

A[6] A[5] A[4] A[3]

B[6] B[5] B[4] B[3]

A[24] A[20] A[16] A[12]

B[24] B[20] B[16] B[12]

A[25] A[21] A[17] A[13]

B[25] B[21] B[17] B[13]

A[26] A[22] A[18] A[14]

B[26] B[22] B[18] B[14]

A[27] A[23] A[19] A[15]

B[27] B[23] B[19] B[15]

C[2] C[1]

C[8] C[4]

C[9] C[5]

C[10] C[6]

C[11] C[7]

C[0]

C[0]

C[1]

C[2]

C[3]
56

Vector Unit Structure
Functional Unit

Vector Registers

Elements 0, 4, 8, …

Elements 1, 5, 9, …

Elements 2, 6, 10, …

Elements 3, 7, 11, …

Lane Memory Subsystem
57

Automatic Code Vectorization
for (i=0; i < N; i++) C[i] = A[i] + B[i]; Scalar Sequential Code
Vectorized Code
load load Iter. 1 add store store load Iter. 2 add store load Iter. 1 Iter. 2 store load load load add load

Time

add

Vector Instruction

Vectorization is a massive compile-time reordering of operation sequencing ? requires extensive loop dependence analysis
58

Older Vector Machines
Machine Cray 1 Cray XMP Cray YMP Cray C-90 Cray T-90 Convex C-1 Convex C-4 Fuj. VP200 Fuj. VP300 NEC SX/2 NEC SX/3 Year Clock 1976 80 MHz 1983 120 MHz 1988 166 MHz 1991 240 MHz 1996 455 MHz 1984 10 MHz 1994 133 MHz 1982 133 MHz 1996 100 MHz 1984 160 MHz 1995 400 MHz Regs Elements 8 64 8 64 8 64 8 128 8 128 8 128 16 128 8-256 32-1024 8-256 32-1024 8+8K 256+var 8+8K 256+var FUs 6 8 8 8 8 4 3 3 3 16 16

59

Newer Vector Computers
?Cray X1 & X1E
? MIPS like ISA + Vector in CMOS

?NEC Earth Simulator
? Fastest computer in world for 3 years; 40 TFLOPS ? 640 CMOS vector nodes

60

核心体系结构特点 X1 X1核心体系结构特点
? 新的向量指令系统设计 ? 更大的寄存器堆 (32x64 vector, 64+64 scalar) ? 基于在Cray1 ISA积累的25年的编译经验 ? 解耦执行(Decoupled Execution) ? 标量单元在向量单元前面执行,主要负责地址计算与控制流 ? 硬件动态进行循环展开,将来自多次循环的指令同时发射执行 ? 可扩展的分布式共享存储体系结构(distributed shared memory architecture,DSM) ? 存储体系: caches, local memory, remote memory ? 低延迟、可对整个机器实现访问的load/store架构 (tens of TBs) ? 处理器支持高达1000个在途(outstanding)访存请求 ? 高带宽网络连接各个处理器

61

多媒体扩展 ISA ISA多媒体扩展
? 在目前主流通用计算处理器ISA中增加一些较短的向量支持,对小的向 量数据进行加工(e.g., array of pixels) ? 通常将64位的寄存器划分2x32b、4x16b或8x8b ? 一些新的设计中,寄存器已扩展为28位(Altivec, SSE2) ? 目前的发展趋势是在微处理器中实现更加全面的向量计算支持(多媒体 应用比例的日益上升),甚至出现了图形图像处理器 GPU向通用计算处 理器发展的趋势
? GPGPU概念:面向通用计算的GPU ? nVidia的CUDA(Compute Unified Device Architecture,统一计算架构)

62

: 操作与指令数 操作与指令数: RISC v. Vector Processor
Spec92fp Program R/V swim256 hydro2d nasa7 su2cor tomcatv wave5 mdljdp2 Operations (Millions) Instructions (Millions) RISC Vector R/V RISC Vector 115 58 69 51 15 27 32 95 40 41 35 10 25 52 1.1x 1.4x 1.7x 1.4x 1.4x 1.1x 0.6x 115 58 69 51 15 27 32 0.8 0.8 2.2 1.8 1.3 7.2 15.8 142x 71x 31x 29x 11x 4x 2x

Vector reduces ops by 1.2X, instructions by 20X
63

向量应用现状与发展
? Limited to scientific computing? No!
? Multimedia Processing (compress, graphics, audio synth, image proc.) ? Standard benchmark kernels (Matrix Multiply, FFT, Convolution, Sort) ? Lossy Compression (JPEG, MPEG video and audio) ? Lossless Compression (Zero removal, RLE, Differencing, LZW) ? Cryptography (RSA, DES/IDEA, SHA/MD5) ? Speech and handwriting recognition ? Operating systems/Networking (memcpy, memset, parity, checksum) ? Databases (hash/join, data mining, image/video serving) ? Language run-time support (stdlib, garbage collection)

64

向量总结
? 向量计算是另一种挖掘ILP档有效途径 ? 如果代码可向量化,那么获得同样的性能将比乱序执行的超标量机器所 需要的硬件复杂度低、能耗低、且有更好的实时保证 ? 设计要点包括lane的数量, 功能单元的数量, 向量寄存器的大小与数量, 条件操作的处理等 ? 最易造成性能瓶颈的设计部分在于访存带宽 ? 多媒体的日益普及,似乎正在使得向量体系结构重新焕发生机 ?

65

高等计算机体系结构 (Advanced Computer Architecture)

3. Limits to ILP

回顾 ILP ILP回顾
?在不影响程序顺序语义所要求结果的前提下,尽量找到更 多的指令同时发射执行 ?利用ILP改善性能在概念上看似简单,但在实践中却是非常 复杂的问题 ?一些现代处理器 (Pentium 4, IBM Power 5, AMD Opteron) 在结构原理上相似,也大致能维持相似的发射率 (每时钟周期3 到 4 条指令) ?峰值(Peak)性能与可交付(delivered )性能之间的差 价在拉大
67

Limits to ILP
?如果可以继续增加硬件资源的投资,到底在理论上还有多 少ILP可供挖掘呢? ?是否需要发明新的HW/SW机制来维持过去以来的性能改善 曲线?
? Intel MMX, SSE (Streaming SIMD Extensions): 64 bit ints ? Intel SSE2: 128 bit, including 2 64-bit Fl. Pt. per clock ? Motorola AltaVec: 128 bit ints and FPs ? Supersparc Multimedia ops, etc.

68

限制因素考察 ILP ILP限制因素考察
? 初始硬件模型: MIPS compilers. ? 初始理想化的机器:
1. 寄存器重命名 – 无穷多的物理寄存器资源 => 所有WAW & WAR冒险均可消除 2. 分支预测 – 完美、没有任何预测错误 3. 无条件跳转预测 – 所有跳转也是完美的 (returns, case statements)
? 2 & 3 ? 完全没有控制相关影响

4. 访存地址的获得不产生地址计算等待延迟,而且如果load操作和store操 作的地址不一样,则在后面的load指令可以被提早到前面的store指令之 前执行
? 1 & 4 彻底消除RAW之外的所有数据冒险

? 此外: 完美的cache; 所有访存操作在1个时钟周期完成; 每周期所能发 射的指令数不受硬件条件制约;
69

限制比较 ILP ILP限制比较
Model
Instructions Issued per clock Instruction Window Size Renaming Registers Branch Prediction Infinite Infinite Infinite Perfect

Power 5
4 200 48 integer + 40 Fl. Pt. 2% to 6% misprediction (Tournament Branch Predictor) 64KI, 32KD, 1.92MB L2, 36 MB L3 ??

Cache Memory Alias Analysis

Perfect Perfect

70

Upper Limit to ILP: Ideal Machine
SPEC92 Benchmarks
160 140 150.1

FP: 75 - 150
118.7

Instructions Per Clock

Instruction Issues per cycle

120 100 80

Integer: 18 - 60
75.2 62.6 54.8

60 40

17.9 20 0 gcc espresso li fpppp Programs 71 doducd tomcatv

Bit More Realistic
?一些理想化的因素显然是永远也不可能实现的 ? 硬件可在任意大范围内寻找可发射指令(无穷大指令窗 口) ? 完美的分支预测 ? 任意多的功能单元 ? 能对任意多的指令同时进行彼此间相关性检查 ? 例如,检查2000条指令直接的数据相关,所需要4百万 个比较操作 ?首先看看限制指令窗口大小所带来的影响
72

限制比较 ILP ILP限制比较
New Model
Instructions Issued per clock Instruction Window Size Renaming Registers Branch Prediction Cache Memory Alias Infinite Infinite, 2K, 512, 128, 32 Infinite Perfect

Model
Infinite Infinite Infinite Perfect

Power 5
4 200 48 integer + 40 Fl. Pt. 2% to 6% misprediction (Tournament Branch Predictor) 64KI, 32KD, 1.92MB L2, 36 MB L3 ??

Perfect Perfect

Perfect Perfect

73

More Realistic HW: Window Impact
FP: 9 - 150
160 150

I n s tr u c ti o n s P e r C l o c k

140 120 100 80

Integer: 8 - 63

FP parallelism is in loops. Good compiler may be able to schedule and do better than this.
75 61 49 35 1 81 5 1 21 1 9 14 1 61 5 59 60 45 34 9 14

119

63 60 40 20 0 gc c es pres s o In f in ite li 2048 55 36 1 01 0 8 41 1 51 3

8

fpppp 512 128

doduc 32

to m c a tv

74

现实制约 ? 下一步 下一步现实制约 现实制约?
?假设指令窗口为2K,最大发射宽度为每周期64条 指令 ?如果分支预测不能达到百分百正确,会有什么影 响?

75

分支预测机制
1. Perfect 2. Tournament – 基本上是目前最好的预测器.假设预测器 采用8K项大小的buffer, 2-bit协同预测器和2-bit非协同 预测器, 根据两者之间谁在历史上正确率更高进行选择 3. 512表项的2-bit预测器 4. 基于剖视信息的静态预测器 5. None

76

限制比较 ILP ILP限制比较
New Model
Instructions Issued per clock Instruction Window Size Renaming Registers Branch Prediction Cache Memory Alias 64

Model
Infinite

Power 5
4

2048 Infinite

Infinite Infinite

200 48 integer + 40 Fl. Pt. 2% to 6% misprediction (Tournament Branch Predictor) 64KI, 32KD, 1.92MB L2, 36 MB L3 ??

Perfect vs. 8K Perfect Tournament vs. 512 2bit vs. profile vs. none Perfect Perfect Perfect Perfect

77

More Realistic HW: Branch Impact
61 60 58

60

FP: 15 - 45
50
48 46 45 46 45 45

41

40
35

Integer: 6 - 12
30
29

Huge impact on integer ILP!
20
16 12 10 15 13 14 19

10

9 6 6 2 7 6 2 6 7 4 2

0 gcc espresso li Program Perfect Selective predic tor Standard 2-bit No Static None prediction Profile BHT (512) Perfect Tournament fpppp doducd tomcatv

78

Next?
?How about effect of finite registers?

79

限制比较 ILP ILP限制比较
New Model
Instructions Issued per clock Instruction Window Size Renaming Registers Branch Prediction Cache Memory Alias 64

Model
Infinite

Power 5
4

2048 Infinite v. 256, 128, 64, 32, none 8K 2-bit Perfect Perfect

Infinite Infinite Perfect Perfect Perfect

200 48 integer + 40 Fl. Pt. Tournament Branch Predictor 64KI, 32KD, 1.92MB L2, 36 MB L3 Perfect

80

More Realistic HW: Renaming Register Impact (N int + N fp)
70

No limit seen for FP.
60

50

There is a min of ~64 needed for integer benchmarks

59 54 49 45 44

FP: 11-45

40
35

Integer: 5 - 15
30
20

29

28

20
15 15 13 11 10 10 9 5 4 10 5 4 12 12 12 11 6 5 5 4

16

15 11 5 7 5 5

10

0 gcc espresso li Program Infinite 256 128 64 32 None fpppp doducd tomcatv

81

限制比较 ILP ILP限制比较
New Model
Instructions Issued per clock Instruction Window Size Renaming Registers Branch Prediction Cache Memory Alias 64 (no restrictions)

Model
Infinite

Power 5
4

Infinite vs. 256, 128, 64, 32 64 Int + 64 FP 1K 2-bit Perfect HW disambiguation

Infinite Infinite Perfect Perfect Perfect

200 48 integer + 40 Fl. Pt. Tournament 64KI, 32KD, 1.92MB L2, 36 MB L3 Perfect

82

Realistic HW: Window Impact
60
56

50

Ins truct ion iss ues per c yc le

40

Note that the ILP available in integer programs is very limited!

52 47

FP: 8 - 45
35

45

34

30

IPC

20

Integer: 6 - 12
15 15 10 10 10 9 13 10 8 6 4 3 8 6 4 2 12 12 11 11 9 6 4 3

22 17 16 14 8 5 3

22

15 12 9 7 4 3

14 9 6 3

10

0 gcc expresso li Program Infinite 256 128 64 32 16 8 4 fpppp doducd tomcatv

83

? 现在的模型 现在的模型?
?截止目前,得到了在今后多年内不太可能实现突破 的限制条件下,我们在理论上所能获得的最大ILP 情况 ?即便如此,仍然没有考虑到一些其它不可能实现的 理想化假设
? 内存歧义(memory aliasing)的消除是非常困难的 ? 64发射是难以实现的,不受限制的指令组合的发射就更 难以实现 ? 假设cache是完美的,没有任何失效!!!

84

是否有可能突破所观察到的限制 ? 是否有可能突破所观察到的限制?
?这些限制都受制于物理规律,如果在使用的基础材 料上获得突破,也许有可能突破这些限制(量子计 算?) ?编译器与指令系统ISA的革命性进步,有可能会改变 这个研究结果 ?WAR 和 WAW 冒险的消除,目前还只局限于寄存 器,是否可以对内存的WAR和WAW冒险也进行消 除呢?

85

ILP :HW vs. SW 改善 改善ILP ILP:
? 调度范围: 软件可查看更大的指令窗口来寻找可并发执行的指令 ? 推测执行:
? 通常由硬件做出的动态分支预测要优于由编译器做出的静态预测 ? 硬件更擅长对发生例外时的处理 ? 硬件不需要维持一段补偿代码来进行错误恢复

? 代码可移植性
? 硬件调度对程序员透明,根据不同机器的配置动态做出相应调度决策,可 移植性完全不受影响 ? 软件调度对程序员不透明,且常常对机器体系结构与配置参数存在假设或 依赖,可移植性较受影响

? 复杂度
? 硬件调度的硬件实现复杂度高,实现代价高,功耗高 ? 软件调度在编译时刻复杂度高,但运行时刻的硬件复杂度要求低,实现代价 低,运行时刻功耗低
86




友情链接: 高中资料网 职业教育网 成人教育网 理学 大学工学资料