计算机系统结构 第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统** 第五章 标量处理机 第六章 向量处理机

Slides:



Advertisements
Similar presentations
第五节 函数的微分 一、微分的定义 二、微分的几何意义 三、基本初等函数的微分公式与微分运算 法则 四、微分形式不变性 五、微分在近似计算中的应用 六、小结.
Advertisements

2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
信息技术:硬件、软件、网络、数据库 计算机技术、多媒体技术、压缩技术...
计算机网络课程总结 一、计算机网络基础 计算机网络定义和功能、基本组成 OSI/RM参考模型(各层的功能,相关概念, 模型中数据传输 等)
LSF系统介绍 张焕杰 中国科学技术大学网络信息中心
将向量数据表示和流水线技术结合起来,构成向量流水处理机,简称向量处理机(Vector Processor)
2017年3月5日 单片机原理与应用 背景知识调查.
实验四 利用中规模芯片设计时序电路(二).
计算机组成与系统结构 主讲教师: 胡越明 课件下载: ftp://ftp.cs.sjtu.edu.cn /huym/计算机组成与系统结构
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
计算机基础知识 丁家营镇九年制学校 徐中先.
第3章 流水线技术 曲冠南
LSF系统介绍 张焕杰 中国科学技术大学网络信息中心
Hadoop I/O By ShiChaojie.
第三章 流水线技术.
存储系统.
SOA – Experiment 3: Web Services Composition Challenge
走进编程 程序的顺序结构(二).
Zhao4zhong1 (赵中) C语言指针与汇编语言地址.
Zhao4zhong1 (赵中) C语言指针与汇编语言地址.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
逆向工程-汇编语言
实验六 积分器、微分器.
动态规划(Dynamic Programming)
CPU结构和功能.
第6章 向量处理机 包仲贤 兰州兰州理工大学计算机与通信学院 2019年2月16日星期六 计算机系统结构 第六章 向量处理机.
第3章 流水线技术 曲冠南
宁波市高校慕课联盟课程 与 进行交互 Linux 系统管理.
内容摘要 ■ 课程概述 ■ 教学安排 ■ 什么是操作系统? ■ 为什么学习操作系统? ■ 如何学习操作系统? ■ 操作系统实例
C语言程序设计 主讲教师:陆幼利.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
微机系统的组成.
实数与向量的积.
第四章 MCS-51定时器/计数器 一、定时器结构 1.定时器结构框图
第四章 向量处理机 银河-I巨型计算机 银河-II巨型计算机
顺序表的删除.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
微机原理与接口技术 微机原理与接口技术 朱华贵 2015年11月13日.
复习.
第二章 补充知识 2.1 总线和三态门 一、总线(BUS) 三总线结构 数据总线DB(Data Bus)
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
实验三 16位算术逻辑运算实验 不带进位控制的算术运算 置AR=1: 设置开关CN 1 不带进位 0 带进位运算;
iSIGHT 基本培训 使用 Excel的栅栏问题
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
3.1.2 空间向量的数量积运算 1.了解空间向量夹角的概念及表示方法. 2.掌握空间向量数量积的计算方法及应用.
第八章 总线技术 8.1 概述 8.2 局部总线 8.3 系统总线 8.4 通信总线.
第三章 函数的微分学 第二节 导数的四则运算法则 一、导数的四则运算 二、偏导数的求法.
第六节 用频率特性法分析系统性能举例 一、单闭环有静差调速系统的性能分析 二、单闭环无静差调速系统的性能分析
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
HSC高速输出例程 HORNER APG.
2.2矩阵的代数运算.
临界区问题的硬件指令解决方案 (Synchronization Hardware)
GIS基本功能 数据存储 与管理 数据采集 数据处理 与编辑 空间查询 空间查询 GIS能做什么? 与分析 叠加分析 缓冲区分析 网络分析
第二节 C语言的特点.
滤波减速器的体积优化 仵凡 Advanced Design Group.
基于列存储的RDF数据管理 朱敏
微机原理与接口技术 西安邮电大学计算机学院 宁晓菊.
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
周学海 中国科学技术大学 2019/7/8 计算机体系结构 周学海 中国科学技术大学.
第三节 数量积 向量积 混合积 一、向量的数量积 二、向量的向量积 三、向量的混合积 四、小结 思考题.
第十七讲 密码执行(1).
FVX1100介绍 法视特(上海)图像科技有限公司 施 俊.
上节复习(11.7) 1、定时/计数器的基本原理? 2、定时/计数器的结构组成? 3、定时/计数器的控制关系?
学习目标 1、什么是列类型 2、列类型之数值类型.
Presentation transcript:

计算机系统结构 第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统** 第五章 标量处理机 第六章 向量处理机 第七章 互连网络 第八章 并行处理机 第九章 多处理机

第六章 向量处理机 6.1 向量处理的基本概念 6.2 向量处理机的结构 6.3 向量处理机的存取模式和数据结构** 6.4 提高向量处理机性能的方法 6.5 向量处理机实例 6.6 向量处理机的性能评价 6.7 关于向量处理机的几点看法

6.1 向量处理的基本概念 向量处理机 解决数值计算问题的一种高性能计算机结构 一般采用流水线结构,有多条流水线并行工作 通常属大型或巨型机,也可微机加一台向量协处理器组成 一般包括有一台高性能标量处理机 把问题转化为向量运算,向量处理机才能充分发挥作用

6.1.1什么是向量处理 从标量到向量 一个简单的C语言程序 for (i = 10; i <= 1010; i++) c[i] = a[i] + b[i+5] ; 在向量处理机上,可以只用一条指令: C(10:1010)=A(10:1010) + B(15 :1015) 一条向量指令可处理N个或N对操作数 标量处理机上用10多条机器指令,其中8条指令循环1000次 向量指令的处理效率比标量指令的处理效率高得多

一般标量处理机中实现(A、B、C分别是向量a、b、c在内存中的起始地址) 标量处理方式 一般标量处理机中实现(A、B、C分别是向量a、b、c在内存中的起始地址) START: LOAD R0, ST ;读循环初值,10 LOAD R1, ED ;读循环终值,1010 LOAD R2, L ;读内存地址增量, ;常数4 MOVE R3, R2 MUL R3, R0 ;向量偏移量, ;初始值为40 LOOP: LOAD R4, A(R3) ;读A向量的 ;一个元素 LOAD R5, B(R3) ;读B向量的一个元素 ADD R4, R5 STORE R4, C(R3) ;写C向量的一个元素 ADD R3, R2 ;改变向量偏移量 INC R0 ;循环次数增1 CMP R0, R1 ;循环是否结束 BLE LOOP ;循环未结束转LOOP, ;否则继续 HALT ST: 10 ;循环初值 ED: 1010 ;循环终值 L: 4 ;内存地址增量

6.1.2 向量处理方式 根据向量运算的特点和向量处理机类型选择向量处理方式 三种处理方式 1.横向处理方式,又称水平处理方式,横向加工方式 向量计算是按行的方式从左至右横向地进行 2.纵向处理方式,又称垂直处理方式,纵向加工方式 向量计算是按列的方式自上而下纵向地进行 3.纵横处理方式,又称分组处理方式,纵横向加工方式 横向处理和纵向处理相结合的方式 以一个简单的C语言编写的程序为例,说明向量的三种处理方式的工作原理 for (i = 1;i <= n;i++) y[i] = a[i] ×( b[i] + c[i] );

1 横向处理方式 也称水平处理方式,横向加工方式 逐个分量进行处理 假设中间结果为T(I) 计算第1个分量: T(1) =B(1)+C(1) Y(1) =A(1)×T(1) 计算第2个分量: T(2) =B(2)+C(2) Y(2) =A(2)×T(2) …… 最后一个分量: T(N) =B(N)+C(N) Y(N)=A(N)×T(N) 存在问题 计算向量的每个分量,都发生写读数据相关。流水线效率低 如果采用多功能流水线,须频繁进行流水线切换 横向处理方式对向量处理机不适合 标量处理机中,经常通过编译器进行指令流调度

2 纵向处理方式 也称垂直处理方式,纵向加工方式 T(1) = B(1) + C(1) T(2) = B(2) + C(2) …… T(n) = B(n) + C(n) Y(1) = A(1)×T(1) Y(2) = A(2)×T(2) …… Y(N) = A(N)×T(N) 向量指令只需2条: VADD B, C, T VMUL A, T, Y 这种处理方式适用于向量处理机 数据相关不影响流水线连续工作 不同的运算操作只需切换1次

3 纵横处理方式 寄存器-寄存器结构的向量处理机中向量寄存器的长度有限 如每个向量寄存器有64个标量寄存器 当向量长度N大于向量寄存器长度n时,需要分组处理 分组方法 N=K*n+r,其中:r为余数 共分K+1组 组内采用纵向处理方式 组间采用横向处理方式 因此,也称为分组处理方式,纵横向加工方式

纵横处理方式 运算过程为 第1组 T(1,n) = B(1,n) + C(1,n) Y(1,n) = A(1,n)×T(1,n) 第2组 T(n+1,2n) = B(n+1,2n)+C(n+1,2n) Y(n+1,2n) = A(n+1,2n)×T(n+1,2n) …… 最后第k+1组 T(kn+1,N) = B(kn+1,N) + C(kn+1,N) Y(kn+1,N) = A(kn+1,N) × T(kn+1,N) 每组用两条向量指令,每组发生数据相关两次 组内发生数据相关一次(T(n)写后读) 组间切换时发生数据相关一次(B(n+1), C(n+1) LOAD相关) 优点:减少访问主存储器的次数(中间变量T不写入主存储器)

6.2 向量处理机的结构 向量处理机的最关键问题是存储器系统能够满足运算部件的带宽要求 主要采用两种方法 1. 存储器-存储器结构 多个独立的存储器模块并行工作 处理机结构简单,对存储系统的访问速度要求很高 2. 寄存器-寄存器结构 运算通过向量寄存器进行 需要大量高速寄存器,对存储系统访问速度的要求降低

6.2.1 存储器-存储器结构 向量处理机中有多个高速流水线运算部件,存储器的访问速度是关键 采用多个存储体交叉和并行访问来提高存储器速度 Cray 1有64个存储体,每个处理机访问4个存储体 STAR-100采用32个存储体交叉,每个存储体并行读出8个64位数据 我国研制的YH-1向量计算机有37个存储体

图6.2 一个具有8个存储体的向量处理机 三条互相独立的数据通路,可并行工作,同一个存储模块同时只能为一个通路服务 存储周期为2 流水结构加法器为4周期流水 M 流水结构加法器 A B C=A+B

存储器-存储器结构 操作数缓冲栈和写结果缓冲栈主要用于解决访问存储器冲突 采用质数个存储体能消除访问存储器的冲突 数据经过多次运算之后,在存储体中分布必然发生改变 主要优缺点 硬件结构简单, 造价低 速度相对较低 主存 储器 操作数缓冲栈 流水线 运算 部件 写结果缓冲栈

向量处理示例:求C=A+B 图6.3 A、B、C在主存储器中的存放情况 A[0] …… C[4] B[6] C[5] B[7] A[1] C[6] B[0] A[2] C[7] B[1] A[3] C[0] B[2] A[4] C[1] B[3] A[5] C[2] B[4] A[6] C[3] B[5] A[7] 模块0 模块1 模块2 模块3 模块4 模块5 模块6 模块7

图6.4 两个向量在流水线方式下分量相加的时序图 流水段1 流水段2 流水段3 流水段4 W4 RB6 RA0 W5 RB7 RA1 W6 RA2 RB0 RA3 RB1 W0 RA4 RB2 W1 RA5 RB3 W2 RA6 RB4 W3 RA7 RB5 7 6 5 4 3 2 1 M0 M1 M2 M3 M4 M5 M6 M7 0 1 2 3 4 5 6 7 8 9 10 11 12 时间(时钟周期)

在流水线的输入端和输出端增加缓冲器 流水线的输入端和输出端增加缓冲器可消除争用存储器现象 图6.5 可变延迟器 主存 储器 流水 结构 加法 器 A B C 延迟4个时钟周期 延迟2个时钟周期

在流水线的输入端和输出端增加缓冲器后,运算时间延长6T A延迟2个周期进入流水结构加法器 存储器发生冲突时两个向量相加的时序图 在流水线的输入端和输出端增加缓冲器后,运算时间延长6T A延迟2个周期进入流水结构加法器 C延迟4个周期写存储器(避免与RA8--RB8冲突) 图6.6 存储器发生冲突时两个向量相加的时序图 W0 RB8 RA8 RB0 RA0 RB9 RA9 RB1 RA1 RB10 RA10 RB2 RA2 RA11 RB3 RA3 RA12 RB4 RA4 RB5 RA5 RB6 RA6 RB7 RA7 7 6 5 4 3 2 1 M0 M1 M2 M3 M4 M5 M6 M7 0 1 2 3 4 5 6 7 8 9 10 11 12 流水段1 流水段2 流水段3 流水段4

6.2.2 寄存器-寄存器结构 存储器-存储器结构中的缓冲栈改为向量寄存器 运算部件需要的操作数从向量寄存器中读取,运算的中间结果也写到向量寄存器 向量寄存器与标量寄存器的主要差别 一个向量寄存器能够保存一个向量 连续访问一个向量的各个分量 寄存器-寄存器结构的主要优点: 降低主存储器的流量 寄存器-寄存器结构的Cray 1与存储器-存储器结构的STAR-100相比,运算速度高3倍多,主存流量低2.5倍 STAR-100的主存储器流量:2x8W/1.28us=200MW/s Cray 1的主存储器流量: 4W/50ns=80MW/s

图6.10 Cray 1向量处理机结构 8个向量寄存器V 8×64×64 主存 储器 8MB 64个 存储体 12个 流水 线结 构的 运算 部件 缓冲寄存器T 64×64 标量寄存器S 8×64 缓冲寄存器B 64×24 地址寄存器A 8×24 指令缓冲寄存器 256×16

6.3 向量处理机的存取模式和数据结构 略

6.3.1 数值算法的存取模式 略

6.3.2 向量处理机的数据结构 略

6.4 提高向量处理机性能的方法 向量处理机的关键技术 向量与标量性能的平衡 向量链接技术

6.4.1 向量处理机系统结构的设计目标 1 较好地维持向量/标量性能平衡 实际的应用问题中既有向量计算又有标量计算,两类计算有一定的比例 向量平衡点(vector balance point) 为使向量硬件设备和标量硬件设备的利用率相等,一个程序中向量代码所占的百分比 关键问题 希望向量硬件和标量硬件都能够充分利用,不要空闲 如一个系统的向量运算速度为90Mflops,标量运算速度为 10Mflops 如果程序的90%是向量运算,10%是标量运算。则向量平衡点为0.9。此时,硬件利用率最高 向量处理机的向量平衡点须与用户程序向量化程度相匹配 IBM向量计算机的设计思想与上述方法不同 维持较低的向量与标量比例,定在3~5的范围之间 这种做法能够适应通用应用问题对标量和向量处理要求

表6.1 几种超级计算机的向量性能和标量性能 机器型号 Fujitsu VP400 Cray IS Cray 2S Cray X-MP Cray Y-MP Hitachi S820 NEC SX2 向量性能 Mflops 标量性能 Mflops 向量平衡点 85.0 9.8 0.90 151.5 11.2 0.93 143.3 13.1 0.92 201.6 17.0 737.3 17.8 0.98 424.2 9.5 207.1 6.6 0.97 疯狂的小日本

6.4.1 向量处理机系统结构的设计目标 2 可扩展性随处理机数目的增加而提高 规模可扩展性:资源部件个数从小到大可扩展 换代可扩展性:要求与新硬件系统兼容和可移植的软件/算法也是可扩展的 问题可扩展性:问题规模扩大时仍然高效地运行 3 增加存储器系统的容量和性能 4 提供高性能的I/O和易访问的网络

6.4.2 提高向量处理机性能的常用技术 1 链接技术 寄存器-寄存器系统结构中,向量操作数在送入流水线前,要先装入向量寄存器中;中间和最后结果也要先装入向量寄存器中,再存入主存储器 1)向量指令的类型 Cray 1向量处理机有四类指令,两种指令格式 (1) 向量与向量操作,Vi <-- Vj OP Vk (2) 向量与标量操作,Vi <-- Sj OP Vk (3) 向量取, Vi <-- 存储器 (4) 向量存, 存储器 <-- Vi 2)向量运算中的相关和冲突 向量运算中的数据相关和功能部件冲突 采用顺序发射顺序完成方式时 (1) 写读数据相关 (2) 读读数据相关,或向量寄存器冲突 (3) 运算部件冲突

图6.18 Cray 1向量指令的类型 n … 4 3 2 1 Vj Vk Vi 第一类向量指令 n … 4 3 2 1 Sj Vk Vi Vj, Vk 各取第1个分量进入段1,隔1T进入段2,Vj, Vk 各取第2个分量进入段1, ...... 每隔1T,Vj, Vk 各取1个分量进入段1,读取第1个分量后还有63个分量,还需63T, ...... (n+2)T, Vi写入第1个分量,每隔1T,Vi写入1个分量,写入第1个分量后还有63个分量,还需63T,总时间(n+2)T+ 63T n … 4 3 2 1 Vj Vk Vi 第一类向量指令 n … 4 3 2 1 Sj Vk Vi 第二类向量指令 Vj, Vk 各取第1个分量进入段1,隔1T进入段2, Vj, Vk 各取第2个分量进入段1, ...... 每隔1T,Vj, Vk 各取1个分量进入段1,读取第1个分量后还有63个分量,还需63T , ...... (n+2)T, Vi写入第1个分量, 每隔1T,Vi写入1个分量,写入第1个分量后还有63个分量,还需63T 总时间(n+2)T+ 63T

图6.18 Cray 1向量指令的类型 存储器 7 6 5 4 3 2 1 Vi 第四类向量指令 存储器 7 6 5 4 3 2 1 Vi 第三类向量指令

图6.19 向量运算中的功能部件和操作数寄存器预定 V0 <-- V1 + V2 V3 <-- V1 + V2 V3 <-- V4 * V5 V6 <-- V4 + V5 (a)不相关的指令 (b)功能部件的预定 V3 <-- V1 + V2 V0 <-- V1 + V2 V6 <-- V1 * V5 V3 <-- V1 + V5 (c)操作数寄存器的预定 (d)功能部件和操作数寄存器的预定

3 向量链接技术(chaining) 结果寄存器可能成为后继指令的操作数寄存器 分量进入结果向量寄存器同时送出 两条有数据相关的向量指令并行执行,称为两条流水线的链接技术

问题: t0从存储器读,第一个结果 在时钟周期t23时形成, 为什么? 例6.1 四条向量指令链接 V0<- 存储器 V2<- V0+V1 V3<- V2 leftshift X V5<- V3 and V4 图6.20 Cray 1的流水线链接 问题: t0从存储器读,第一个结果 在时钟周期t23时形成, 为什么? 1 1 1 1 1 1 1 1

例6.1 四条向量指令链接

例6.2 向量运算:D=A*(B+C),假设向量长度≤64,且B和C已由存储器取至V0和V1 3条向量指令完成上述运算 V3 <- A V2 <- V0+V1 V4 <- V2*V3 第一、二条指令没有数据相关和功能部件冲突,可同时开始执行 第三条指令与第一、二条指令均存在写读数据相关,可链接执行

例6.2 浮点加 7 1 2 3 4 5 6 Mem V0 V1 V2 V3 V4 浮点乘

三种执行方式比较 (1) 向量长度为N,三条指令采用串行方法执行的时间为 [(1+6+1)+N-1]+[(1+6+1)+N-1]+[(1+7+1)+N-1] = 3N+22 拍 (1+6+1)+N-1 浮点加 7 1 2 3 4 5 6 Mem V0 V1 V2 V3 V4 浮点乘 1 1 (1+7+1)+N-1 1 1 (1+6+1)+N-1 1 1 第1个分量流出(1+6+1),其后N-1个分量一拍流出一个

(2) 前两条指令并行执行,第三条指令串行执行,执行时间 [(1+6+1)+N-1]+[(1+7+1)+N-1] = 2N+15 拍 三种执行方式比较 (2) 前两条指令并行执行,第三条指令串行执行,执行时间 [(1+6+1)+N-1]+[(1+7+1)+N-1] = 2N+15 拍 (1+6+1)+N-1 (1+6+1)+N-1 浮点加 7 1 2 3 4 5 6 Mem V0 V1 V2 V3 V4 浮点乘 1 1 (1+7+1)+N-1 1 1 1 1 (1+6+1)+N-1

(3) 采用链接技术,执行时间 (1+6+1)+(1+7+1)+(N-1)=17+N-1=N+16 拍 三种执行方式比较 (3) 采用链接技术,执行时间 (1+6+1)+(1+7+1)+(N-1)=17+N-1=N+16 拍 浮点加 7 1 2 3 4 5 6 Mem V0 V1 V2 V3 V4 浮点乘 第1个分量流出(1+6+1) 第1个分量流出(1+7+1) 其后N-1个分量一拍流出一个

实现链接的条件 (1) 没有向量寄存器冲突和运算部件冲突 (2) 只有第一个结果送入向量寄存器的那一个周期可以链接 (3) 先行的两条指令产生运算结果的时间必须相等 浮点加改成5段则例6.2不能链接 (4) 两条向量指令的向量长度必须相等

2 向量循环或分段开采技术 向量的长度大于向量寄存器的长度时,须把长向量分成长度固定的段,采用循环结构处理这个长向量,这种技术称为向量循环开采技术,也称向量分段开采技术 例6.3:A和B为长度N的向量 for (i=1; i<N; i++) a[i]=5*b(i)+c; 当N为当N为64或更小时,产生A数组的7条指令序列是: 1:S1¬5.0 在标量寄存器内设置常数 2:S2¬C 将常数C装入标量寄存器 3:VL¬N 在VL寄存器内设置向量长度 4:Vo¬B 将B向量读入向量寄存器 5:V1¬S1 * Vo B数组的每个分量和常数相乘 6:V2¬S2+V1 C和5 ´ B(x)相加 7:A¬V2 将结果向量存入A数组 当N大于64时? 当N超过64时,就需要采用向量循环 在进入循环以前,把N除以64,以确定循环次数。如果有余数,则在第一次循环中首先计算余数个分量 循环由第4条到第7条指令组成 当N超过64时,就需要采用向量循环。 在进入循环以前,把N除以64,以确定循环次数。 如果有余数,则在第一次循环中首先计算余数个分量。 循环由第4条到第7条指令组成。

3 向量递归技术 一般情况下,向量操作必须采用三地址结构 向量递归运算中,实际上采用两地址结构 流水线功能部件的输出要回送到它的一个源向量寄存器 向量的点积A·B=ai·bI, , 在Cray 1中用两个向量操作链接实现 V1V3  V4 V0V0+V1

用浮点加法流水线完成递归向量求和V0V0+V1 令C0和C1分别是与向量寄存器V0和V1相关的分量计数器 初始时,计数器C0和C1都置成0,V0的第一个分量寄存器V00中的初始值也置成0 通过浮点加法流水线共需要8个时钟周期,其中数据往返传送各需要1个时钟周期(6段) 假定向量长度寄存器的值为64,只作一个向量循环 在开始的8个周期,计数器Co一直为0,在此之后,每个周期后都加1。C1每个周期后都加1

递归向量求和 + V00 =V00 + V10 =0 +V10 (8T后流入V00) V01 =V00 + V11 =0 +V11 …… + V00 =V00 + V10 =0 +V10 (8T后流入V00) V01 =V00 + V11 =0 +V11 …… V07 =V00 + V17 =0 +V17 V08 =V00 + V18 =V10+V18 V09 =V01 + V19 =V11+V19 V015=V07 + V115 =V17+V115 V016=V08 + V116 =V10+V18+V116 V056=V048 + V156 =V10+V18+V116+V124+V132+V140+V148+V156 V063=V055 + V163 =V17+V115+V123+V131+V139+V147+V155+V163 8T 绿线: 加的两个数 红线: 和的存放位置 7 8 + 16T 15 组0 16 + 24T 23 组1 24 + 32T 31 t 组7 1T送一个分量 (8+63)T 除8余7 除8余0

控制计数器C0和C1,V00的初始值,可实现多种递归运算 对递归向量乘法运算,V00的初始值要设置为1 递归向量求和 控制计数器C0和C1,V00的初始值,可实现多种递归运算 对递归向量乘法运算,V00的初始值要设置为1 (8+63)T的递归运算后,点积可以从64个加法减少到8个加法 向量的递归运算在科学计算中非常有用 V00,V10 V00=V10 V00,V11 V01=V11 V00,V17 V07=V17 V00,V18 V08=V10+V18 V01,V19 V09=V11+V19 V07,V115 V015=V17+V115 V048,V156 V056=V10+V18+…+V156 V049,V157 V057=V11+V19+…+V157 V055,V163 V063=V17+V115+…+V163 … t0 t8 t16 t63

递归向量求和

4 稀疏矩阵的处理技术 略 当N超过64时,就需要采用向量循环。 在进入循环以前,把N除以64,以确定循环次数。 如果有余数,则在第一次循环中首先计算余数个分量。 循环由第4条到第7条指令组成。

6.5 向量处理机实例 向量处理机主要出自美国和日本 美国著名的向量计算机公司有:Cray、CDC、TI等 日本公司有:NEC、Fujitsu、Hitachi等

6.5.1 向量处理机的历史与现状 美国和日本制造的向量处理机 机器型号 配置 特点 Cray IS 有10条流水线的单处理机,12.5ns, COS/CF7 2.1 第一台基于ECL的超级计算机,1976年 Cray 2S/4-256 256M字存储器的4台处理机,4.1ns, COS或UNIX/CF77 3.0 16K字的本地存储器,移植了UNIX V,1985年 Cray X-MP 416 16M字存储器的4台处理机,128M字SSD, 8.5ns, COS CF77 5.0 使用共享寄存器组用于IPC,1983年 Cray Y-MP 832 128M字存储器的8台处理机, 6ns, CF77 5.0 X-MP的改进型,1988年 Cray Y-MP C-90 每台处理机2条向量流水线, 16台处理机, 4.2ns, Unicos/CF77 5.0 最大的Cray机器,1991年 CDC Cyber 205 有4条流水线的单处理机, 20ns, 虚拟OS/FTN200 存储器到存储器系统结构,1982年 ETA 10E 单处理机, 10.5ns, ETAV/FTN 200 Cyber 205的后继型号,1985年 NEC SX-X/44 每台处理机4组流水线, 4台处理机, 2.9ns, F77SX, 22Gflops 1991年 Fujitsu VP2600/10 5条流水线的单处理机和双标量处理机, 3.2ns,MSP. EX/F77 EX/VP 使用可重构微向量寄存器和屏蔽,1991年 Hitachi 820/80 512MB存储器,18条流水线的单处理机,4ns,FORT77/HAP V23-OC 64个通道,最大传输速率288MB/S,1988年

6.5.2 Cray Y-MP向量处理机 Cray Y-MP 816由1至8台处理机组成,多个处理机共享中央存储器、I/O子系统、处理机通信子系统和实时钟 中央存储器由256个交叉访问的存储体组成。每个处理机对4个存储器端口的交叉访问。CPU的时钟周期为6ns 4个存储器端口允许处理机同时执行两个标量和向量取操作、一个存储操作和一个独立的I/O操作 每个CPU由14个功能部件组成,分为向量、标量、地址和控制四个子系统 使用了大量地址寄存器、标量寄存器、向量寄存器、中间寄存器和临时寄存器 可以实现功能流水线灵活的链接 I/O子系统支持三类通道,传输速率分别为6兆字节/秒,100兆字节/秒和1G字节/秒

Cray Y-MP向量处理机

6.5.3 Fujitsu VP2000和VPP500

6.5.4 向量协处理器 以通用中小型机,或微机作为主机;向量处理部件作为外围设备,加速向量的处理速度 向量协处理器是为中小型用户设计的,解决科学计算中大量向量处理任务的一种装置 与各种不同主机相连的向量协处理器,价格和功能的变化范围很大 FPS-164是最典型的向量协处理器,美国浮点系统公司生产。每个向量处理器有两个乘加部件,两组向量寄存器,两组标量寄存器

6.5.4 向量协处理器 每个乘加部件每个周期能输出一个结果 向量寄存器:2组x4个x2K=16K个操作数,每操作数4个字节 运算过程:标量处理器把原始数据装入向量寄存器,把标量数据和指令播送到全部向量处理器。向量处理器就同步地运算,但它们处理的数据是各不相同的 向量操作可以和标量处理器中的标量操作同时进行 向量协处理器特别适合于大规模的数值处理,用户购买需要台数的向量处理器,使用现有的处理机作为主机

FPS-164向量协处理器结构图 标量运算部件 协处理器 主存储器 120 MB 地址寄存器 间址寄存器 向量处理器 标量寄存器 X寄存器组 Y寄存器组 向量 寄存器 乘法流水线 加法流水线 与主计算 机连接 FPS-164向 量协处理 器结构图

6.6 向量处理机的性能评价 衡量向量处理机性能的主要指标: 向量指令处理时间Tvp、 最大性能R ¥ 、半性能向量长度n1/2 1、向量指令处理时间Tvp 执行一条向量长度为n的向量指令的时间Tvp Tvp=Ts + Tvf + (n - 1) Tc 其中 Ts为向量流水线的建立时间 Tvf为向量流水线的流过时间 Tc为流水线“瓶颈”段的执行时间 如果每段执行时间都等于一个时钟周期,则有 Tvp=[s + e + (n - 1)] t s为向量流水线建立时间所需的时钟周期数 e为向量流水线流过时间所需的时钟周期数 n为向量长度 t为时钟周期长度

编队 把几条能在一个时钟周期内同时开始执行的向量指令称为一个编队 同一个编队中的指令一定不存在功能部件冲突和数据相关 一个链接是一个编队 一个编队意味着加一次n-1

例6.4,6.5 假设一台向量处理机中功能部件的启动开销为:取数和存数部件为12个时钟周期、乘法部件为7个时钟周期、加法部件为6个时钟周期。先把序列向量操作分成编队,然后计算每个编队的开始时间、获得第一个结果元素的时间和获得最后一个结果元素的时间。 LV V1, Rx ;取向量x MULTSV V2, F0, V1 ;向量和标量相乘 LV V3, Ry ;取向量Y ADDV V4, V2, V3 ;加法 SV Ry, V4 ;存结果 解:指令1与2之间关于V1相关、指令3与4之间关于V3相关、指令4与5之间关于V4相关,所以它们必须分在不同的编队。 第一个编队 第一条指令LV 第二个编队 MULTSV指令和第二条LV指令 第三个编队 ADDV指令 第四个编队 SV指令

例6.4,6.5 不使用链接技术的时空图与各编队时间 编队1 编队2 编队3 编队4 访存 12段 指令1 指令3 指令5 乘法 7段 编队1 编队2 编队3 编队4 访存 12段 指令1 指令3 指令5 乘法 7段 指令2 加法 6段 指令4 时间 12 n-1 12 n-1 6 n-1 12 n-1

采用向量链接技术(不考虑访问存储器的冲突),需要 12 + 7 + 6 + 12 + n – 1=(36 + n)个周期 例6.4,6.5 -------------------------------------------------------------------------- 编队 开始时间 第一个 最后一个 结果时间 结果时间 ------------------------------------------------------------------------- (1)LV 0 12 11+n (2)MULTSV LV 12+n 12+n+12 23+2n (3)ADDV 24+2n 24+2n+6 29+3n (4)SV 30+3n 30+3n+12 41+4n 采用向量链接技术(不考虑访问存储器的冲突),需要 12 + 7 + 6 + 12 + n – 1=(36 + n)个周期

分段开采 向量长度大于向量寄存器长度时,则需要分段开采 向量长度为n的一组向量操作的整个执行时间 段数 每段启动时间 N-1 N-1重复次数 段数 所有独立斜线之和 所有独立水平线之和 其中 Tloop为执行标量代码的开销 Tloop可以看作是一个常数,Cray 1机的 Tloop 约等于15 Tstart为每个编队的向量启动开销 等于流水功能部件的流水段数,即流水线深度, 与向量流水线的流过时间几乎相等 Tchime为一个编队的执行时间 MVL为向量寄存器的长度 每段N-1重复Tchime 次,64 *Tchime 共(64+64+...+k) *Tchime =n*Tchime

例6.6 在Cray 1上实现A=B×s操作,其中A和B是长度为200的向量,s是一个标量。向量寄存器长度为64。各功能部件的启动时间与上例相同。求总的执行时间。 解: 向量长度超过了向量寄存器的长度,采取分段开采方法 每次循环主要由下面三条向量指令组成: LV V1, Rb ;取向量B MULTVS V2, V1, Fs ;向量和标量相乘 SV Ra, V2 ;存向量 假设A和B的分别放在Ra和Rb之中,s在Fs中 三条指令之间存在有写读数据相关 须分成3个编队,Tchime= 3, Cray 1机 Tloop为15, n=200 Tstart=12 + 7 + 12 = 31 T200 = 4×(Tloop + Tstart) + 200× Tchime = 4×(15 + 31) + 200× 3 =784 每个结果元素的平均执行时间为:784/200 =3.9个周期

例6.7 同例6.4,6.5, 在某台向量处理机上执行代码代码如下: 1:LV V1, Rx ;取向量x 2:MULTSV V2, F0, V1 ;向量和标量相乘 3:LV V3, Ry ;取向量Y 4:ADDV V4, V2, V3 ;加法 5:SV Ry, V4 ;存结果 考虑访问存储器冲突,向量寄存器长度为n、各功能部件的启动时间与上例相同。求总的执行时间。

例6.7 解: 由于使用链接技术,编队结果与例6.4不同。即指令1与2链接在同一编队,指令3与1冲突要分开,指令3与4链接在同一编队,指令5与3冲突要分开 指令1、2,指令3、4和指令5分成三个编队,前两个编队中两条指令采用向链接技术执行。 Tchime=3 Tloop=15 Tstart= (12+7) + (12+6) + 12 = 49 MVL=64 尾数一组

指令之间只有存在冲突关系时,才不能编入同一编队。相关指令可通过链接技术编入同一编队。 使用链接技术的时空图与各编队时间(设n < 64,即不分段。) 编队1 编队2 编队3 访存 12段 指令1 指令3 指令5 乘法 7段 指令2 加法 6段 指令4 时间 12 7 n-1 12 6 n-1 12 n-1 总时间 = 3n + 46

2、最大性能R¥ R¥表示当向量长度为无穷大时的向量流水线的最大性能 单位为MFLOPS,常在评价峰值性能时使用 最大性能R¥ 表示 其中:n为向量长度 Tn为一组向量操作的整个执行时间 每个T所完成的运算次数 对例6.7,假设时钟频率为200MHz。每个循环有2个浮点操作

为达到一半R¥值所需的向量长度称为半性能向量长度n1/2 主要评价向量流水线建立时间对性能的影响 由MFLOPS定义可知 Cray 1的n1/2=10~20,Cyber 205的n1/2=100 由MFLOPS定义可知 对例6.7,向量处理机的时钟频率为200MHz。 R ¥ =100MFLOPS,每个循环有2个浮点操作, 有 100/2 = 2 n1/2/Tn1/2 * 200, 令n1/2<= 64 由Tloop=15, Tstart=12+7+12+6+12=49, Tchime=3得 Tn1/2=1×(Tloop+Tstart)+n×Tchime =1*(15+49)+n1/2*3 =64+3 n1/2 代入得:100/2 = 2 n1/2/(64 + 3 n1/2) *200 n1/2=12.8 所以:n1/2=13

6.7 关于向量处理机的几点看法 1、向量计算机系统结构的发展趋势 (1) 提供多种向量运算指令 (2) 除具有向量处理功能外还有其它功能 (3) 采用多层次的存储器系统 (4) 流水线技术与并行技术相结合

2、向量计算机系统结构要解决的六个技术问题 (1) 处理机带宽,两种方法 运算部件采用流水线结构 用多个运算器构成并行系统 (2) 存储器带宽,多种解决方法 采用多个独立的存储体构造一个大容量的存储器系统 采用多层次的存储器系统提高访问速度 采用高速缓冲存储器和可寻址的寄存器组效果最好 采用流水线技术,存储系统的访问速度快5~20倍 (3) 输入/输出带宽 许多高性能向量处理机配备10 ~ 29个DMA通道 (4) 通信带宽。共享存储器或互连网络 (5) 同步。多流水线结构通过控制程序使所有流水线同步工作 Cray 1系统采用流水线互锁来控制向量操作,不冲突的操作可以并行地执行,相关的操作尽可能链接起来重叠地进行 (6) 多用途。非数值计算问题

3、向量计算机系统结构的主要优点 (1) 通过流水线存取方式有效地提高了存储器的带宽 (2) 流水结构的运算器有很高的性能价格比 (3) 非常简单的机制就能满足通信和同步的要求 向量处理机以MFLOPS (Million floating-point operations per second)作为速度单位 一般认为,标量计算机中执行一次浮点运算需2~5条指令,平均需3条指令