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

Slides:



Advertisements
Similar presentations
1 I/O 设备访问方式和类型. 2 Overview n The two main jobs of a computer: l I/O (Input/Output) l processing n The control of devices connneted to the computer is.
Advertisements

Welcome to the world of Computer Organization 计算机组成原理
程序的执行 程序执行和指令执行概述 数据通路基本结构和工作原理 流水线方式下指令的执行
第 2 章 中央處理單元.
多核结构与程序设计 杨全胜 东南大学成贤学院计算机系.
Chapter 10 效能測量與分析.
第二章 微型计算机系统 第一节 基本术语和基本概念 第二节 计算机系统的基本构成 第三节 微机系统的硬件组成 第四节 微机系统的软件组成.
Unit 9 Have you ever been to an amusement park? Section A.
He said: What is a team? Team is not to let the other person failed, and do not let any team member fail!
计算机组成原理 北京理工大学计算机科学工程系 赵清杰 北京理工大学计算机科学工程系.
第11章 计算机系统 计算机系统概述 分类方法、计算机系统性能评测方法 2. 微机系统 3. 他体系结构处理机
最新計算機概論 第3章 計算機組織.
新世代計算機概論 第3章 電腦的系統單元.
第四章 存储体系.
第一章 導論.
周学海 , 中国科学技术大学 2017/9/13 现代微处理器体系结构 周学海 , 中国科学技术大学 2017/9/13 计算机体系结构.
Unit 4 I used to be afraid of the dark.
Been During the Vacation?
Module 5.
Hardware Chen Ching-Jung
CH.2 Introduction to Microprocessor-Based Control
周学海 , 中国科学技术大学 2018/9/20 现代微处理器体系结构 周学海 , 中国科学技术大学 2018/9/20 计算机体系结构.
周学海 , 中国科学技术大学 2018/9/21 计算机体系结构 周学海 , 中国科学技术大学.
Chapter 5 電腦元件 目標---- 研讀完本章後,你應該可以: 閱讀有關電腦的廣告以及了解它的專業用語(行話)。
第 2 章 中央處理單元.
微处理器设计1 刘鹏 College of ISEE Zhejiang University
臺北市立大學 資訊科學系(含碩士班) 賴阿福 CS TEAM
高等计算机系统结构 VLIW/EPIC 基于静态调度的ILP (第五讲) 程 旭 2011年4月16日.
周学海 中国科学技术大学 2018/11/14 计算机体系结构 周学海 中国科学技术大学.
Quiz 3 假设各种分支占所有指令数的百分比如下表所示:
CPU資料處理 醫務管理暨醫療資訊學系 陳以德 副教授: 濟世CS 轉
周学海 中国科学技术大学 2018/11/16 计算机体系结构 周学海 中国科学技术大学.
周学海 , 中国科学技术大学 2018/11/16 计算机体系结构 周学海 , 中国科学技术大学.
電腦的種類 超級電腦 (supercomputer) 大型電腦 (Mainframe) 迷你電腦 ( Mini computer)
第4章 处理器(CPU) 4.1 引言 4.2 逻辑设计的一般方法 4.3 建立数据通路 4.4 一个简单的实现机制 4.5 多周期实现机制.
不断变迁的闪存行业形势 Memory has changed, especially serial - from a low cost, low pin count, slow memory to an advanced, high performance memory solution to save.
指令集架構 計算機也跟人類一樣,需要提供一套完整的語言讓人們跟它充分溝通,以完成正確的計算工作。
1-1 微電腦系統單元 1-2 微電腦系統架構 1-3 微控制器(單晶片微電腦) 1-4 類比與數位訊號介面
1-1 微電腦系統單元 1-2 微電腦系統架構 1-3 微控制器(單晶片微電腦) 1-4 類比與數位訊號介面
5 Computer Organization (計算機組織).
The Processor: Datapath and Control
微程序控制器 刘鹏 Dept. ISEE Zhejiang University
第三章 流水线技术.
計算機結構 – 概論 陳鍾誠 於金門大學.
嵌入式微处理器系统 第二章 处理器技术(1) 北京大学软件与微电子学院.
Ch 9: Input/Output System 输入/输出系统
周学海 中国科学技术大学 2018/12/3 计算机体系结构 周学海 中国科学技术大学.
胡維平 國立中正大學化學暨生物化學系 Aug. 30, 2017
重點 資料結構之選定會影響演算法 選擇對的資料結構讓您上天堂 程式.
JTAG INTERFACE SRAM TESTER WITH C-LCM
第4章(1) 空间数据库 —数据库理论基础 北京建筑工程学院 王文宇.
计算机系统结构 第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统** 第五章 标量处理机 第六章 向量处理机
Operating System Principles 作業系統原理
第6章 向量处理机 包仲贤 兰州兰州理工大学计算机与通信学院 2019年2月16日星期六 计算机系统结构 第六章 向量处理机.
第3章 流水线技术 曲冠南
第十五课:在医院看病.
計算機概論 第3章 計算機組織與結構概觀.
第四章 向量处理机 银河-I巨型计算机 银河-II巨型计算机
Architecture and Systems 研究群 報 告 人:單智君 陳昌居 鍾崇斌 中華民國95年11月30日
中国科学技术大学计算机系 陈香兰 2013Fall 第七讲 存储器管理 中国科学技术大学计算机系 陈香兰 2013Fall.
虚 拟 仪 器 virtual instrument
中国科学技术大学计算机系 陈香兰 Fall 2013 第三讲 线程 中国科学技术大学计算机系 陈香兰 Fall 2013.
中央社新聞— <LTTC:台灣學生英語聽說提升 讀寫相對下降>
计算机系统结构(2012年春) ----存储层次: Cache基本概念
第10章 存储器接口 罗文坚 中国科大 计算机学院
第六章 記憶體.
BiCuts: A fast packet classification algorithm using bit-level cutting
清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2005年5月
周学海 中国科学技术大学 2019/7/8 计算机体系结构 周学海 中国科学技术大学.
MATLAB 結構化財務程式之撰寫 MATLAB財務程式實作應用研習 主題五 資管所 陳竑廷
Presentation transcript:

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

Review 05/06: Multithreaded Categories Simultaneous Multithreading Superscalar Fine-Grained Coarse-Grained Multiprocessing Time (processor cycle) Thread 1 Thread 3 Thread 5 Thread 2 Thread 4 Idle slot 7/16/2019 2019/7/16 计算机体系结构 中国科学技术大学 2 2

第6章 Data-Level Parallelism in Vector, SIMD, and GPU Architectures 数据级并行的研究动机 传统指令级并行技术的问题 SIMD结构的优势 数据级并行的种类 向量体系结构 向量处理模型 起源-超级计算机 基本特性及结构 性能评估及优化 面向多媒体应用的SIMD指令集扩展 GPU GPU简介 GPU的编程模型 GPU的存储系统 7/16/2019 中国科学技术大学

动机:传统指令级并行技术的问题 提高性能的传统方法(挖掘ILP)的主要缺陷: 程序内在的并行性 提高流水线的时钟频率: 提高时钟频率,有时导致CPI随着增加 (branches, other hazards) 指令预取和译码: 有时在每个时钟周期很难预取和译码多条指令 提高Cache命中率 : 在有些计算量较大的应用中(科学计算)需要大量的数据,其局部性较差,有些程序处理的是连续的媒体流(multimedia),其局部性也较差。 7/16/2019 中国科学技术大学

动机:DLP的兴起 应用需求和技术发展推动着体系结构的发展 图形、机器视觉、语音识别、机器学习等新的应用均需要大量的数值计算,其算法通常具有数据并行特征 SIMD-based 结构 (vector-SIMD, subword-SIMD, SIMT/GPUs) 是执行这些算法的最有效途径 7/16/2019 中国科学技术大学

The University of Adelaide, School of Computer Science 16 July 2019 动机:SIMD结构的优势 SIMD 结构可有效地挖掘数据级并行: 基于矩阵运算的科学计算 图像和声音处理 SIMD比MIMD更节能 针对每组数据操作仅需要取指一次 SIMD对PMD( personal mobile devices)更具吸引力 SIMD 允许程序员继续以串行模式思维 7/16/2019 中国科学技术大学 Chapter 2 — Instructions: Language of the Computer

The University of Adelaide, School of Computer Science 16 July 2019 SIMD 结构的种类 向量体系结构 多媒体SIMD指令集 扩展 Graphics Processor Units (GPUs) For x86 processors: 每年增加2cores/chip SIMD 宽度每4年翻一番 SIMD潜在加速比是MIMD的2倍 7/16/2019 中国科学技术大学 Chapter 2 — Instructions: Language of the Computer

7/16/2019 中国科学技术大学

向量处理模型 + r1 r2 r3 SCALAR (1 operation) v1 v2 v3 VECTOR (N operations) 向量处理机具有更高层次的操作,一条向量指令可以处理N个或N对操作数(处理对象是向量) + r1 r2 r3 add r3, r1, r2 SCALAR (1 operation) v1 v2 v3 vector length add.vv v3, v1, v2 VECTOR (N operations) 7/16/2019 中国科学技术大学 25

起源:Supercomputers Supercomputer的定义: 由Seymour Cray设计的机器 对于给定任务而言世界上最快的机器 任何造价超过3千万美元的机器 计算能力达到每秒万亿次的机器 由Seymour Cray设计的机器 CDC6600 (Cray, 1964) 被认为是第一台超级计算机 7/16/2019 中国科学技术大学

CDC 6600 Seymour Cray, 1963 A fast pipelined machine with 60-bit words 128 Kword main memory capacity, 32 banks Ten functional units (parallel, unpipelined) Floating Point: adder, 2 multipliers, divider Integer: adder, 2 incrementers, ... Hardwired control (no microcoding) Scoreboard for dynamic scheduling of instructions Ten Peripheral Processors for Input/Output a fast multi-threaded 12-bit integer ALU Very fast clock, 10 MHz (FP add in 4 clocks) >400,000 transistors, 750 sq. ft., 5 tons, 150 kW, novel freon-based technology for cooling Fastest machine in world for 5 years (until 7600) over 100 sold ($7-10M each) 新颖的制冷技术:弗里昂制冷 第一次使用:动态调度技术 7/16/2019 中国科学技术大学 CS252 S05

IBM Memo on CDC6600 Thomas Watson Jr., IBM CEO, August 1963: “Last week, Control Data ... announced the 6600 system. I understand that in the laboratory developing the system there are only 34 people including the janitor. Of these, 14 are engineers and 4 are programmers... Contrasting this modest effort with our vast development activities, I fail to understand why we have lost our industry leadership position by letting someone else offer the world's most powerful computer.” To which Cray replied: “It seems like Mr. Watson has answered his own question.” 7/16/2019 中国科学技术大学 CS252 S05

Supercomputer Applications 典型应用领域 军事研究领域(核武器研制、密码学) 科学研究 天气预报 石油勘探 工业设计 (car crash simulation) 生物信息学 密码学 均涉及大量的数据集处理 70-80年代Supercomputer = Vector Machine 7/16/2019 中国科学技术大学

向量处理机的基本特性 基本思想:两个向量的对应分量进行运算,产生一个结果向量。 简单的一条向量指令包含了多个操作=> fewer instruction fetches 每一结果独立于前面的结果 长流水线,编译器保证操作间没有相关性 硬件仅需检测两条向量指令间的相关性 较高的时钟频率 向量指令以已知的模式访问存储器 可有效发挥多体交叉存储器的优势 可通过重叠减少存储器操作的延时 ­ 64 elements 不需要数据Cache! (仅使用指令cache) 在流水线控制中减少了控制相关 7/16/2019 中国科学技术大学

向量处理机的基本结构 向量机的Load/Store结构 memory-memory vector processors: 所有的向量操作是存储器到存储器 vector-register processors: 除了load 和store操作外,所有的操作是向量寄存器与向量寄存器间的操作 向量机的Load/Store结构 1980年以后的所有的向量处理机都是这种结构: Cray, Convex, Fujitsu, Hitachi, NEC 我们也主要针对这种结构 7/16/2019 中国科学技术大学

Vector Memory-Memory versus Vector Register Machines 存储器-存储器型向量机所有指令操作的操作数来源于存储器 第一台向量机 CDC Star-100 (‘73) and TI ASC (‘71), 是存储器-存储器型机器 Cray-1 (’76) 是第一台寄存器型向量机 ADDV C, A, B SUBV D, A, B Vector Memory-Memory Code for (i=0; i<N; i++) { C[i] = A[i] + B[i]; D[i] = A[i] - B[i]; } Example Source Code LV V1, A LV V2, B ADDV V3, V1, V2 SV V3, C SUBV V4, V1, V2 SV V4, D Vector Register Code 7/16/2019 中国科学技术大学

Vector Memory-Memory vs. Vector Register Machines 存储器-存储器型向量机 (VMMA) 需要更高的存储器带宽 All operands must be read in and out of memory VMMA结构使得多个向量操作重叠执行较困难 Must check dependencies on memory addresses VMMA启动时间更长 CDC Star-100 在向量元素小于100时,标量代码的性能高于向量化代码 CDC Cray-1后续的机器 (Cyber-205, ETA-10) 都是寄存器型向量机 7/16/2019 中国科学技术大学

Vector Supercomputers Cray-1的变体(1976): Scalar Unit:Load/Store Architecture Vector Extension Vector Registers Vector Instructions Implementation 硬布线逻辑控制 高效流水化的功能部件 多体交叉存储系统 无Data Cache 不支持 Virtual Memory 7/16/2019 中国科学技术大学

Vector Instruction Set Advantages 格式紧凑 一条指令包含N个操作 表达能力强, 一条指令能告诉硬件: N个操作之间无相关性 使用同样的功能部件 访问不相交的寄存器 与前面的操作以相同模式访问寄存器 访问存储器中的连续块 (unit-stride load/store) 以已知的模式访问存储器 (strided load/store) 可扩展性好 可以在多个并行的流水线上运行同样的代码 (lanes) 7/16/2019 中国科学技术大学

Vector Instructions 7/16/2019 中国科学技术大学

向量处理机的基本组成单元 Vector Register: 固定长度的一块区域,存放单个向量 至少2个读端口和一个写端口(一般最少16个读端口,8个写端口) 典型的有8-32 向量寄存器,每个寄存器存放64到128个64位元素 Vector Functional Units (FUs): 全流水化的,每一个clock启动一个新的操作 一般4到8个FUs: FP add, FP mult, FP reciprocal (1/X), integer add, logical, shift; 可能有些重复设置的部件 Vector Load-Store Units (LSUs): 全流水化地load 或store一个向量,可能会配置多个LSU部件 Scalar registers: 存放单个元素用于标量处理或存储地址 用交叉开关连接(Cross-bar) FUs , LSUs, registers 7/16/2019 中国科学技术大学

7/16/2019 中国科学技术大学

Vector Arithmetic Execution 使用较深的流水线(=> fast clock) 执行向量元素的操作 由于向量元素相互独立,简化了深度流水线的控制 (=> no hazards!) V1 V2 V3 Six stage multiply pipeline V3 <- v1 * v2 7/16/2019 中国科学技术大学

Vector Unit Structure Functional Unit Vector Registers Lane Memory Subsystem Elements 0, 4, 8, Elements 1, 5, 9, Elements 2, 6, 10, Elements 3, 7, 11, … 7/16/2019 中国科学技术大学

Vector Instruction Execution ADDV C,A,B C[1] C[2] C[0] A[3] B[3] A[4] B[4] A[5] B[5] A[6] B[6] 使用一条流水化的功能部件执行 C[4] C[8] C[0] A[12] B[12] A[16] B[16] A[20] B[20] A[24] B[24] C[5] C[9] C[1] A[13] B[13] A[17] B[17] A[21] B[21] A[25] B[25] C[6] C[10] C[2] A[14] B[14] A[18] B[18] A[22] B[22] A[26] B[26] C[7] C[11] C[3] A[15] B[15] A[19] B[19] A[23] B[23] A[27] B[27] 使用4条流水化的功能部件执行 7/16/2019 中国科学技术大学

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 1 2 3 4 5 6 7 8 9 A B C D E F + Base Stride Vector Registers Memory Banks Address Generator 7/16/2019 中国科学技术大学

T0 Vector Microprocessor (UCB/ICSI, 1995) Vector register elements striped over lanes [0] [8] [16] [24] [1] [9] [17] [25] [2] [10] [18] [26] [3] [11] [19] [27] [4] [12] [20] [28] [5] [13] [21] [29] [6] [14] [22] [30] [7] [15] [23] [31] Lane 7/16/2019 中国科学技术大学

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/16/2019 中国科学技术大学

Vector Execution Time 4 convoys, 1 lane, VL=64 Time = f(vector length, data dependencies, struct. hazards) Initiation rate: 功能部件消耗向量元素的速率 Convoy: 可在同一时钟周期开始执行的指令集合 (no structural or data hazards) Chime: 执行一个convoy所花费的大致时间(approx. time) m convoys take m chimes; 如果每个向量长度为n, 那么m个convoys 所花费的时间是m个chimes 每个chime所花费的时间是n个clocks,该程序所花费的总时间大约为m x n clock cycles (忽略额外开销; 当向量长度较长时这种近似是合理的) 1: LV V1,Rx ;load vector X 2: MULV V2,F0,V1 ;vector-scalar mult. LV V3,Ry ;load vector Y 3: ADDV V4,V2,V3 ;add 4: SV Ry,V4 ;store the result 4 convoys, 1 lane, VL=64 => 4 x 64 = 256 clocks (or 4 clocks per result) 7/16/2019 中国科学技术大学

Vector Startup R X W R X W R X W R X W R X W R X W R X W R X W R X W 向量启动时间由两部分构成 功能部件延时:一个操作通过功能部件的时间 截止时间或恢复时间(dead time or recovery time ):运行下一条向量指令的间隔时间 Functional Unit Latency R X W R X W First Vector Instruction R X W R X W R X W Dead Time R X W R X W R X W Dead Time Second Vector Instruction R X W R X W 7/16/2019 中国科学技术大学

VMIPS Start-up Time 7/16/2019 中国科学技术大学

Vector Length 当向量的长度不是64时(假设向量寄存器的长度是64)怎么办? vector-length register (VLR) 控制特定向量操作的长度, 包括向量的load/store. (当然一次操作的向量的长度不能 > 向量寄存器的长度) 例如: do 10 i = 1, n 10 Y(i) = a * X(i) + Y(i) n的值只有在运行时才能知道 n > Max. Vector Length (MVL)怎么办? 7/16/2019 中国科学技术大学

Strip Mining(分段开采) 假设Vector Length > Max. Vector Length (MVL)? Strip mining: 产生新的代码,使得每个向量操作的元素数  MVL 第一次循环做最小片(n mod MVL), 以后按VL = MVL操作 low = 1 VL = (n mod MVL) /*find the odd size piece*/ do 1 j = 0, (n / MVL) /*outer loop*/ do 10 i = low, low+VL-1 /*runs for length VL*/ Y(i) = a*X(i) + Y(i) /*main operation*/ 10 continue low = low+VL /*start of next vector*/ VL = MVL /*reset the length to max*/ 1 continue 7/16/2019 中国科学技术大学

Strip Mining的向量执行时间计算 试计算A=B×s,其中A,B为长度为200的向量(每个向量元素占8个字节),s是一个标量。向量寄存器长度为64。各功能部件的启动时间如前所述,求总的执行时间,(Tloop = 15) 7/16/2019 中国科学技术大学

7/16/2019 中国科学技术大学

Tstart = 12 + 7 + 12 = 31 T200 = 660+4*31 = 784 每一元素的执行时间 = 784/200 = 3.9 7/16/2019 中国科学技术大学

7/16/2019 中国科学技术大学

Common Vector Metrics R: 当向量长度为无穷大时的向量流水线的最大性能。常在评价峰值性能时使用,单位为MFLOPS 实际问题是向量长度不会无穷大,start-up的开销还是比较大的 Rn 表示向量长度为n时的向量流水线的性能 N1/2: 达到R 一半的值所需的向量长度,是评价向量流水线start-up 时间对性能的影响。 NV:向量流水线方式的工作速度优于标量串行方式工作时所需的向量长度临界值。 该参数既衡量建立时间,也衡量标量、向量速度比对性能的影响 7/16/2019 中国科学技术大学

Example Vector Machines Year Clock(MHZ) Regs Elements Fus LSUs Cray 1 1976 80 8 64 6 1 Cray XMP 1983 120 2L, 1S Cray YMP 1988 166 Cray C-90 1991 240 128 4 Cray T-90 1996 455 Conv. C-1 1984 10 Conv. C-4 1994 133 16 3 Fuj. VP200 1982 8-256 32-1024 2 Fuj. VP300 100 NEC SX/2 160 8+8K 256+var NEC SX/3 1995 400 Cray 1; fastest scalar computer + 1st commercially successful vector computer, offered another 10X 6600 1st scoreboard Cray XMP: 3 LSUs, Multiprocessor 4 way (not by Cray) => YMP, C-90, T-90; 2X processors, 1.5X clock Cray 2 went to DRAM to get more memory, not so great Like parallel teams as Intel (486, PPro, Pentium, next one) Japan Fujitsu, vary number of registers elements (8x1024 or 32x256) NEC, 8x256 + 8K of varying elements 7/16/2019 中国科学技术大学

A Modern Vector Super: NEC SX-9 (2008) 65nm CMOS technology Vector unit (3.2 GHz) 8 foreground VRegs + 64 background VRegs (256x64-bit elements/VReg) 64-bit functional units: 2 multiply, 2 add, 1 divide/sqrt, 1 logical, 1 mask unit 8 lanes (32+ FLOPS/cycle, 100+ GFLOPS peak per CPU) 1 load or store unit (8 x 8-byte accesses/cycle) Scalar unit (1.6 GHz) 4-way superscalar with out-of-order and speculative execution 64KB I-cache and 64KB data cache Memory system provides 256GB/s DRAM bandwidth per CPU Up to 16 CPUs and up to 1TB DRAM form shared-memory node total of 4TB/s bandwidth to shared DRAM memory Up to 512 nodes connected via 128GB/s network links (message passing between nodes) Picture from NEC article “A hardware overview of SX-6 and SX-7 supercomputer” 7/16/2019 中国科学技术大学

Vector Linpack Performance (MFLOPS) Matrix Inverse (gaussian elimination) Machine Year Clock(Mhz) 100x100 1kx1k Peak(Procs) Cray 1 1976 80 12 110 160(1) Cray XMP 1983 120 121 218 940(4) Cray YMP 1988 166 150 307 2,667(8) Cray C-90 1991 240 387 902 15,238(16) Cray T-90 1996 455 705 1603 57,600(32) Conv. C-1 1984 10 3 -- 20(1) Conv. C-4 1994 136 160 2531 3,240(4) Fuj. VP200 1982 133 18 422 533(1) NEC SX/2 43 885 1,300(1) NEC SX/3 1995 400 368 2757 25,600(4) 6X in 20 years; 32X in 20 years; Peak is 360X speedup Weighed tons 7/16/2019 中国科学技术大学

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/16/2019 中国科学技术大学

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/16/2019 中国科学技术大学

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

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/16/2019 中国科学技术大学

Memory operations Load/store 操作成组地在寄存器和存储器之间移动数据 三类寻址方式 Unit stride (单步长) Fastest Non-unit (constant) stride (常数步长) Indexed (gather-scatter) (间接寻址) 等价于寄存器间接寻址方式 对稀疏矩阵有效 用于向量化操作的指令增多 7/16/2019 中国科学技术大学 32 32

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

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

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

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/16/2019 中国科学技术大学

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/16/2019 中国科学技术大学

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/16/2019 中国科学技术大学

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

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存储到稀疏矩阵的对应位置 这些操作编译时可能无法完成。主要原因:编译器无法预知Ki以及是否有数据相关 使用CVI 设置步长( index 0, 1xm, 2xm, ..., 63xm) CVI gets used under mask 7/16/2019 中国科学技术大学

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

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 Vector Instruction load add store Iter. 1 Iter. 2 Vectorized Code Time 向量化是指在编译期间对操作重定序 需要进行大量的循环相关分析 7/16/2019 中国科学技术大学

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

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

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

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

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

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/16/2019 中国科学技术大学