周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学 2019/7/8 计算机体系结构 周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学.

Presentation on theme: "周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学 2019/7/8 计算机体系结构 周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学."— Presentation transcript:

1 周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学
2019/7/8 计算机体系结构 周学海 中国科学技术大学

2 Review-05/08：向量体系结构 向量处理机基本概念 向量处理机基本特征 向量处理机基本结构 向量处理机性能评估 两个问题
基本思想：两个向量的对应分量进行运算，产生一个结果向量 向量处理机基本特征 VSIW-一条指令包含多个操作 单条向量指令内所包含的操作相互独立 以已知模式访问存储器-多体交叉存储系统 控制相关少 向量处理机基本结构 向量指令并行执行 向量运算部件的执行方式-流水线方式 向量部件结构-多“道”结构-多条运算流水线 向量处理机性能评估 向量指令流执行时间: Convey, Chimes, Start-up time 其他指标： R , N1/2 , NV 两个问题 向量处理机中的存储器访问 向量处理机中的优化技术 7/8/2019 中国科学技术大学

3 DAXPY (Y = a × X + Y) 7/8/2019 中国科学技术大学

4 Vector Stride 假设处理顺序相邻的元素在存储器中不顺序存储。例如 do 10 i = 1,100 do 10 j = 1,100
A(i,j) = 0.0 do 10 k = 1,100 10 A(i,j) = A(i,j)+B(i,k)*C(k,j) B 或 C 的两次访问不会相邻 (相隔800 bytes) stride: 向量中相邻元素间的距离 => LVWS (load vector with stride) instruction Strides => 会导致体冲突 (e.g., stride = 32 and 16 banks) 7/8/2019 中国科学技术大学

5 Memory operations Load/store 操作成组地在寄存器和存储器之间移动数据 三类寻址方式
Unit stride (单步长) Fastest LV V1,R1 //V1=M[R1..R1+63] load, stride=1 Non-unit (constant) stride (常数步长) LVWS V1,R1,R2 //V1=M[R1..R1+63*R2] load, stride=R2 Indexed (gather-scatter) (间接寻址) LVI V1,R1,V2 //V1=M[R1+V2i,i=0..63] indir.("gather") 等价于寄存器间接寻址方式 对稀疏矩阵有效 用于向量化操作的指令增多 7/8/2019 中国科学技术大学 32

6 Memory Banking 独立存储体方式：由多个相互独立的存储体（Bank) 构成存储器组织。可独立访问存储体，各存储体共享数据和地址总线 (minimize pin cost) 每个周期可以启动和完成一个bank的访问 如果N个存储器访问不同的bank可以并行执行 7/8/2019 中国科学技术大学

7 Interleaved Vector Memory System
Cray-1, 16 banks, 4 cycle bank busy time, 12 cycle latency Bank busy time: Time before bank ready to accept next request If stride = 1 & consecutive elements interleaved across banks & number of banks >= bank latency, then can sustain 1 element/cycle throughput 1 2 3 4 5 6 7 8 9 A B C D E F + Base Stride Vector Registers Memory Banks Address Generator 7/8/2019 中国科学技术大学

8 Example(AppF F-15) Suppose we want to fetch a vector of 64 elements starting at byte address 136,and a memory access takes 6 clocks. How many memory banks must we have to support one fetch per clock cycle? With what addresses are the banks accessed? When will the various elements arrive at the CPU? 7/8/2019 中国科学技术大学

9 Bank# = (address/8) mod 8 7/8/2019 中国科学技术大学

10 Vector Opt#1: Vector Chaining
寄存器定向路径的向量机版本 首次在Cray-1上使用 Memory V1 Load Unit Mult. V2 V3 Chain Add V4 V5 LV v1 MULV v3,v1,v2 ADDV v5, v3, v4 7/8/2019 中国科学技术大学

11 Vector Chaining Advantage
Load Mul Add Time 不采用链接技术，必须处理完前一条指令的最后一个元素，才能启动下一条相关的指令 采用链接技术，前一条指令的第一个结果出来后，就可以启动下一条相关指令的执行 Load Mul Add 7/8/2019 中国科学技术大学

12 Vector Instruction Parallelism
多条向量指令可重叠执行(链接技术) 例如：每个向量 32 个元素，8 lanes（车道） Load Unit Multiply Unit Add Unit load mul add time load mul add Instruction issue Complete 24 operations/cycle while issuing 1 short instruction/cycle 7/8/2019 中国科学技术大学

13 Vector Opt #2: Conditional Execution
Suppose: do 100 i = 1, 64 if (A(i) .ne. 0) then A(i) = A(i) – B(i) endif 100 continue vector-mask control 使用长度为MVL的布尔向量控制向量指令的执行 当vector-mask register 使能时，向量指令操作仅对 vector-mask register中 对应位为1的分量起作用 7/8/2019 中国科学技术大学

14 Masked Vector Instructions
B[3] A[4] B[4] A[5] B[5] A[6] B[6] M[3]=0 M[4]=1 M[5]=1 M[6]=0 M[2]=0 M[1]=1 M[0]=0 Write data port Write Enable A[7] B[7] M[7]=1 Simple Implementation execute all N operations, turn off result writeback according to mask C[4] C[5] C[1] Write data port A[7] B[7] M[3]=0 M[4]=1 M[5]=1 M[6]=0 M[2]=0 M[1]=1 M[0]=0 M[7]=1 Density-Time Implementation scan mask vector and only execute elements with non-zero masks 7/8/2019 中国科学技术大学

15 使用vector-mask寄存器的缺陷 简单实现时，条件不满足时向量指令仍然需要花费时间
有些向量处理器带条件的向量执行仅控制向目标寄存器的写操作，可能会有除法错。 7/8/2019 中国科学技术大学

16 Vector Opt #3: Sparse Matrices
Suppose: do 100 i = 1,n 100 A(K(i)) = A(K(i)) + C(M(i)) gather (LVI) operation 使用index vector 中给出的偏移再加基址来读取 => a nonsparse vector in a vector register 这些元素以密集的方式操作完成后，再使用同样的index vector存储到稀疏矩阵的对应位置 这些操作编译时可能无法完成。主要原因：编译器无法预知K(i)以及是否有数据相关 使用CVI 设置步长（ index 0, 1xm, 2xm, ..., 63xm） CVI gets used under mask 7/8/2019 中国科学技术大学

17 Sparse Matrix Example Cache (1993) vs. Vector (1988)
IBM RS Cray YMP Clock MHz MHz Cache KB KB Linpack MFLOPS (1.1) Sparse Matrix 17 MFLOPS (7.3) (Cholesky Blocked ) Cache: 1 address per cache block (32B to 64B) Vector: 1 address per element (4B) 7/8/2019 中国科学技术大学

18 Automatic Code Vectorization
for (i=0; i < N; i++) C[i] = A[i] + B[i]; load add store Iter. 1 Iter. 2 Scalar Sequential Code Vectorized Code Vector Instruction load add store Iter. 1 Iter. 2 Time 向量化是指在编译期间对操作重定序 需要进行大量的循环相关分析 7/8/2019 中国科学技术大学

19 Vector/SIMD Processing Summary
同样的操作作用于不同的数据元素 向量内的元素操作独立，可有效提高性能，简化设计 性能的提升受限于代码的向量化 标量操作限制了向量机的性能 Amdahl’s Law 很多ISA包含SIMD操作指令 Intel MMX/SSEn/AVX, PowerPC AltiVec, ARM Advanced SIMD 7/8/2019 中国科学技术大学

20 Array vs. Vector Processors
Array processor：又称为并行处理机、SIMD处理器。其核心是一个由多个处理单元构成的阵列，用单一的控制部件来控制多个处理单元对各自的数据进行相同的运算和操作。 7/8/2019 中国科学技术大学

21 SIMD Array Processing vs. VLIW
7/8/2019 中国科学技术大学

22 SIMD Array Processing vs. VLIW
Array processor: 单个操作作用在多个不同的数据元素上 7/8/2019 中国科学技术大学

23 Summary：向量体系结构 向量处理机基本概念 向量处理机基本特征 向量处理机基本结构 向量处理机性能评估 向量处理机性能优化
基本思想：两个向量的对应分量进行运算，产生一个结果向量 向量处理机基本特征 VSIW-一条指令包含多个操作 单条向量指令内所包含的操作相互独立 以已知模式访问存储器-多体交叉存储系统 控制相关少 向量处理机基本结构 向量指令并行执行 向量运算部件的执行方式-流水线方式 向量部件结构-多“道”结构-多条运算流水线 向量处理机性能评估 向量指令流执行时间: Convey, Chimes, Start-up time 其他指标： R , N1/2 , NV 向量处理机性能优化 链接技术 条件执行 稀疏矩阵 7/8/2019 中国科学技术大学

24 Vector/SIMD Processing Summary
同样的操作作用于不同的数据元素 向量内的元素操作独立，可有效提高性能，简化设计 性能的提升受限于代码的向量化 标量操作限制了向量机的性能 Amdahl’s Law 很多ISA包含SIMD操作指令 Intel MMX/SSEn/AVX, PowerPC AltiVec, ARM Advanced SIMD 7/8/2019 中国科学技术大学

25 Array vs. Vector Processors
Array processor：又称为并行处理机、SIMD处理器。其核心是一个由多个处理单元构成的阵列，用单一的控制部件来控制多个处理单元对各自的数据进行相同的运算和操作。 7/8/2019 中国科学技术大学

26 SIMD Array Processing vs. VLIW
7/8/2019 中国科学技术大学

27 SIMD Array Processing vs. VLIW
Array processor: 单个操作作用在多个不同的数据元素上 7/8/2019 中国科学技术大学

28 Multimedia Extensions (aka SIMD extensions)
在已有的ISA中添加一些向量长度很短的向量操作指令 将已有的 64-bit 寄存器拆分为 2x32b or 4x16b or 8x8b 1957年，Lincoln Labs TX-2 将36bit datapath 拆分为2x18b or 4x9b 新的设计具有较宽的寄存器 128b for PowerPC Altivec, Intel SSE2/3/4 256b for Intel AVX (Advanced Vector Extensions) 单条指令可实现寄存器中所有向量元素的操作 7/8/2019 中国科学技术大学

29 Multimedia Extensions (aka SIMD extensions)
64b 32b 16b 8b 16b + 4x16b adds 7/8/2019 中国科学技术大学

30 Intel Pentium MMX Operations
idea: 一条指令操作同时作用于不同的数据元 全阵列处理 用于多媒体操作 No VLEN register Opcode determines data type: 8 8-bit bytes 4 16-bit words 2 32-bit doublewords 1 64-bit quadword Stride always equal to 1. 7/8/2019 中国科学技术大学

31 MMX Example: Image Overlaying (I)
7/8/2019 中国科学技术大学

32 MMX Example: Image Overlaying (II)
7/8/2019 中国科学技术大学

33 Multimedia Extensions versus Vectors
受限的指令集: 无向量长度控制 Load/store操作无 常数步长寻址和 scatter/gather操作 loads 操作必须64/128-bit 边界对齐 受限的向量寄存器长度: 需要超标量发射以保持multiply/add/load 部件忙 通过循环展开隐藏延迟增加了寄存器读写压力 在微处理器设计中向全向量化发展 更好地支持非对齐存储器访问 支持双精度浮点数操作 (64-bit floating-point) Intel AVX spec (announced April 2008), 256b vector registers (expandable up to 1024b) 7/8/2019 中国科学技术大学

34 -Review 向量处理机性能评估 向量机的存储器访问 基于向量机模型的优化 多媒体扩展指令 GPU
向量指令流执行时间: Convey, Chimes, Start-up time 其他指标： R , N1/2 , NV 向量机的存储器访问 存储器组织：独立存储体、多体交叉方式 Stride : 固定步长（1 or 常数）, 非固定步长（index） 基于向量机模型的优化 链接技术 有条件执行 稀疏矩阵的操作 多媒体扩展指令 扩展的指令类型较少 向量寄存器长度较短 GPU 7/8/2019 中国科学技术大学

35 Recap: Vector/SIMD Processing Summary
同样的操作作用在许多数据元素上 提高性能、设计简单（向量内的操作相互独立） 性能的提升受限于代码的向量化 标量操作限制着向量机的性能 很多已有的ISA扩展了一些SIMD操作 Intel MMX/SSEn/AVX, PowerPC AltiVec, ARM Advanced SIMD 7/8/2019 中国科学技术大学

36 Acknowledgements These slides contain material developed and copyright by: John Kubiatowicz (UCB) Krste Asanovic (UCB) John Hennessy (Standford)and David Patterson (UCB) Chenxi Zhang (Tongji) Muhamed Mudawar (KFUPM) UCB material derived from course CS152、CS252、CS61C KFUPM material derived from course COE501、COE502 7/8/2019 中国科学技术大学

37 并行的类型 指令级并行(ILP) 线程级并行 (TLP) 数据级并行(DLP) Which is easiest to program?
以并行方式执行某个指令流中的独立无关的指令 (pipelining, superscalar, VLIW) 线程级并行 (TLP) 以并行方式执行多个独立的指令流 (multithreading, multiple cores) 数据级并行(DLP) 以并行方式执行多个相同类型的操作 (vector/SIMD execution) Array Processor 、Vector Processor Which is easiest to program? Which is most flexible form of parallelism? i.e., can be used in more situations Which is most efficient? i.e., greatest tasks/second/area, lowest energy/task 7/8/2019 中国科学技术大学