计算机系统结构
2024-03-23 09:22:12 2 举报
AI智能生成
登录查看完整内容
知识结构梳理, 考点整理
作者其他创作
大纲/内容
运算器
控制器
存储器
输入设备
输出设备
硬件
系统软件
决定系统的功能
应用软件
软件
计算机系统的组成
高级语言
汇编语言
机器语言
语言角度
被定义为 能 \"存储\" 和 \"执行\" 相应语言程序的 \"算法\" 和 \"数据结构\" 的 集合体
机器
计算机系统定义
经应用程序包翻译成高级语言程序
应用语言机器
第5级 虚拟机
高级语言程序经编译程序翻译成汇编语言程序
高级语言机器
第4级 虚拟机
经汇编程序翻译成机器语言程序
汇编语言机器(机器语言)
第3级 虚拟机
用机器语言程序解释作业控制语句
操作系统机器
第2级 虚拟机
用微指令程序解释机器指令
传统机器语言机器
第1级 实际机器
微指令 由硬件直接执行
微程序机器
第0级 实际机器
多级层级结构 (由高到低)
透明性定义
先行进位链
主存地址寄存器
浮点方式表示
乘法器
透明
中断字寄存器
通用寄存器
指令地址寄存器
条件码寄存器
程序性中断
访问方式保护
I/O方式中的 DMA 访问方式
不透明
对机器(汇编)语言程序员
Cache存储器
数据通路宽度
指令缓冲寄存器
虚拟存储器
程序状态字
对系统程序员
机器内部的数据流和控制流的组成
VLSI技术
存储器的模M交叉方式
数据总线宽度
阵列运算部件
计算机系统结构
分类
透明性
计算机系统的层次结构
对计算机系统中 \"各级界面\" 的定义 和其上下 \"功能分配\
系统结构定义
硬件能直接识别 和处理的数据类型及格式
数据表示
寻址方式
寄存器组织
指令系统
存储系统组织
中断机构
系统机器级的\"管态\" 和 \"用户态\" 的定义和切换
机器级I/O 结构
系统各部分的\"信息保护\" 方式和 \"保护机构\" 等属性
包含的属性
着眼与计算内部 \"事件的 \"排序方式\" 和 \"控制机构\" 以及 \"各部件的功能\" 和 \"各部件间的联系\"
计算机组成 向上 决定于 \"结构\" 向下 受限于 \"实现技术\"
专用部件的设置
各种操作对部件的共享程度
功能部件的并行度
控制机构的组成方式
缓冲和排队技术
可靠性技术
计算机组成设计要确定的方面
计算机组成
器件的集成度和速度
指的是计算机组成的 \"物理实现\
着眼 \"器件设计\" 和 \"微组装\" 技术
软件的功能 可以用 \"硬件\" 和 \"固件\
提高 \"硬件功能比例\
提高 \"软件功能比例\
软件的功能实现
计算机实现
尽可能的 加速处理高概率事件 远比 加速处理 低概率事件的 对性能提高要显著
1 哈夫曼(Huffman) 压缩原理
span style=\"font-size: inherit;\
2. Amdahl 阿姆达尔定律
程序访问的局部性包括了 \"时间\" 上和 \"空间\" 上的两个局部性
3. 程序访问的局部性定律
计算机系统 定量设计原理
计算机系统结构 设计
计算机组成 的设计
计算机实现 的设计
包括
计算机指令系统设计
功能组织
逻辑设计
集成电路设计
封装
电源
冷却
涉及
原则
要弄清楚其应用的领域是专用 还是通用的
要弄清楚 软件兼容是放在哪级层次
要弄清楚对操作系统有何种要求
要如何保证有高的保准化程度
标准
由上往下 设计 称为 由顶向底 设计
由下往上 设计 称为 由底向顶 设计
在传统机器语言机器 和 操作系统机器 之间
从\"中间开始 向两边设计\
方法
计算机设计的主要任务
包含 \"同时性\" 和 \"并发性\" 二重含义
时间重叠
资源重复
用 \"软件\
资源共享
开发的途径
一条指令内部各个微操作之间的并行执行
指令内部
多条指令的并行执行
指令之间
多个任务和程序段并行执行
任务或进程之间
多个作业或多到程序并行执行
作业或程序之间
从计算系统 \"执行程序\
没有并行性
位串字串
开始出现并行性
位并字串
位片串字并
同时对多个字段 全部或部分位进行处理
全并行
从计算机系统 \"处理数据\
存储器操作并行
处理器操作步骤并行
处理器操作并行
从\"信息加工\"的各个步骤和阶段的角度来看
角度分类
并行性
统一高级语言
只能应用在 \"结构相同\" 和 \"相似\" 的机器之间的汇编程序 的软件移植技术
采用系列机
模拟
存储系统
I/O 系统
控制台的操作
仿真目标机器
仿真
采用 \"模拟\" 和 \"仿真\"
实现软件移植性
软件发展对系统结构的影响
数据处理
信息处理
知识处理
\"知识库机\" 和 \"推理机\" 和 \"智能接口处理机\" 是必不可少的3个重要组成部分
智能机
智能处理
归纳为向上升级的4类
应用的发展对系统结构的影响
器件集成度的提高
保证流水技术的实现
器件可靠性提高
使解题速度得以提高的 高速缓冲存储器件 和 虚拟存储器的 概念 真正实现
使微程序技术得以实现
现场型 PROM器件
高速相联存储器的实现
器件的发展对系统结构的影响
结论
计算机的发展
并行性 主要表现在 \" 算术运算\" 的\"位并行\" 及 \"运算 和 输入/输出\" 操作的 并行
1960年以前
按 \"指令流\" 和 \"数据流\" 的多倍性 把计算机系统分成
单指令单数据流 SISD
并行处理机: 阵列机 和 相联处理机
单指令多数据流 SIMD
多指令单数据流 MISD
多处理机系统
多指令多数据流 MIMD
提出用 \"数据处理的并行度\" 来定量的描述个计算机系统特性的
称 位串处理方式.
字串位串 WSBS
称 字处理方式
字串位并 WSBP
称 位处理方式
字并位串 WPBS
称 全并行处理方式
字并位并 WPBP
提出 按 \"指令流\" 和 \"执行流\" 以及 \"多倍性\" 来描述计算系统\"总控制器\"的结构特点
典型的 单处理机系统
单指令流单执行流 SISE
带多操作部件的处理机
单指令流多执行流式 SIME
带指令级多道程序的单处理机
多指令流单执行流 MISE
典型的多处理机系统
多指令流多执行流 MIME
由控制驱动的 控制流方式
由数据驱动的 数据流方式
由需求驱动的 规约方式 Reduction
由模式驱动的 匹配方式 Matching
按 \"执行程序\" 或 \"指令的控制方式
计算机系统的分类
1章 计算机系统结构概念
指能由 计算机硬件 \"识别\" 和 \"引用\
和数据结构的关系
类型标志
数据值
简化指令系统和程序设计
简化编译程序
便于 实现一致性校验
能由硬件自动变换数据类型
支持 \"数据库系统\" 的 \"实现\" 和 \"数据类型\
为软件\" 调试\" 和应用软件 \"开发\" 提供了支持
可以缩短 高级语言 和机器语言的 语义差距
优点
增加程序多占用的主存空间
降低指令的执行速度
缺点
包括 \"标志符数据表示\"
地址
长度
各种标志位
描述符 101
数据
数据 000
\"数据描述符\" 两类
两者差别
自定义数据表示( Self-defining)
有堆栈数据表示的计算机称为堆栈计算机
有丰富的 \"堆栈操作指令\" 且 \"功能很强\
有力的支持了 高级语言程序的编译
有力的支持了 子程序的嵌套和递归调用
堆栈计算机表现(特点)
堆栈数据表示
原则1 看 \"系统的效率\
引入的基本原则
高级数据表示
数符 (-)
阶符 (+)
阶值 (4= 00000100)
小数点 .
尾数 (m个机器位置)
表示: -0.1010110 x 2^(+4)
p+1为阶码部分 只有p位 影响 阶值大小
阶码部分
基数
尾数的基数 10101110
rm
基数占用的位 8
log2^rm
尾数的位数 (二进制位数)
m
rm进制的尾数的位数
m' =m /log2^rm
浮点数 阶值的位数
p
rm^-1
最小尾数值
1-rm^-m'
最大尾数值
0
最小阶值
(2^p) -1
最大阶值
rm^-1
最小值
rm^最大阶值 x 最大尾数值
最大值
rm^m' x (1-1/rm)
尾数个数
2^p
阶的个数
阶的个数 x 尾数个数
数的个数
公式
计算
处理实现最简单
截断法
舍入法
恒置 \"1\" 法
采用ROM 或者PLA 存放下溢处理表
查表舍入法
优缺点
下溢处理方法
浮点数尾数基值
面向主存
面向寄存器
属于隐含寻址方式
面向堆栈
寻址目标
占用操作码中的某些位来指明.
指明方式
操作码 地址码
操作数隐含的由累加器给出
隐含寻址
指令中直接给出相应的操作数
立即寻址
指令中给出寄存器号R,操作数存放在R中
寄存器直接寻址
指令中给出寄存器号R,R中存放操作数的有效地址
寄存器间接寻址
以利于实现程序的 动态再定位
对逻辑地址空间到物理地址空间变换的支持
直接寻址
指令中给出存放有效地址E的存储单元地址。
间接寻址
指令中给出相对于PC的偏移量A
相对寻址
基址寻址
指令中给出相对变址寄存器R的偏移量
变地寻址
是程序员编码使用的地址
逻辑地址
是程序在主存中的实际地址
主存物理地址
基本概念
静态再定位
逻辑地址空间到物理地址空间变换的支持
数据块运算的支持
变址寻址
人们把在执行每条指令时才形成访问物理地址的方法称为动态再定位.
动态再定位
虚实地址映像表
定位技术
寻址
指令格式的设计
设计 包括
操作码
地址码
指令格式
算术逻辑运算
数据传送
浮点运算
字符串
十进制运算
控制转移
系统控制
非特权型
启动 1/O
停机等待
存储管理保护
控制系统状态
诊断
特权型
指令类型
零地址指令
一地址指令
二地址指令
三地址指令
按包含的地址码个数
指令分类
对象相识的操作做相同的规定
规整性
对称性
独立性 和全能性
正交性
让指令系统中所有操作对各种寻址方式和数据类型都能适用
可组合性
可扩充性
编译程序设计者对指令系统的要求
指令码密度适中
兼容性
适应性
系统结构设计者对指令系统的要求
设计基本原则
指令优化概念
哈夫曼算法构造哈夫曼树
扩展操作码编码
指令操作码的优化 方法
指令字格式优化
设计优化
以 \"不删改\
目的
复杂指令系统计算机 CISC (Complex Instruction Set Computer)
精简指令系统计算机 RISC (Reduced Instruction Set Computer)
途径和方向
1. 通过对大量已有机器的机器怨言程序机器执行情况的统计各个指令和指令串的使用频度来分析和改进
面向目标程序
1.通过对源程序中各种高级语言语句的使用频度进行统计 来分析改进
5.发展高级语言计算机
面向高级语言
1.通过操作系统中常用指令和指令串的使用频度进行统计分析来改进
2. 考虑如何增设专用于操作系统的新指令
4.发展让操作系统 由专门的处理机来执行的功能分布处理系统结构.
面向操作系统
发展的问题
CISC
3.让所有指令都在一个机器周期内完成
基本原则
按RISC一般原则来设计
逻辑实现采用硬联和微程序结合
在CPU中设置大量工作寄存器并采用重叠寄存器窗口
指令用流水和延迟转移
优化设计编译系统
采用的基本技术
提高计算机的执行速度和效率
3.RISC计算机的编译程序比CISC的难写
问题和不足
RISC
优化改进
发展和改进
大容量
高速度
低价格
基本要求
特点
存储器容器= 存储体字长 x 存储器字数 x 并行存储体数
存储器频宽
为给定指令的下条指令地址为非顺序地址的概率
转移概率
要求访存申请的K个地址中 没有两个或两个以上的地址处在同一分体重的最长序列
申请序列
概念
存储器 字长 和 CPU 所要访问的字的字长相同
Bw=W / Tw
单体单字存储器
Bw=Wx4 / Tw
单体多字存储器
分多分体并行存储器
单体多字相结合
多体多字交叉存储器
m: 主存的模数 (分体数)
W: 分体宽带 或者 字长
TM: 每个分体的存储周期 2us
主存最大频宽: 存储器连续访问时的频宽
λ: 访存申请队的转移概率
m: 主存的模数
B= 1- (1-λ) ^m / λ
每个存取周期内能访问的平均读取字数
并行主存系统
并行主存系统
内部中断
定时器中断
主要用于与掐计算机和系统的联系
外部信息中断
操作员对计算机的干预
中断键中断
外部中断
软件中断
中断分类
电源故障
运输电路的误操作
主存出错
通道动作故障
处理器的各种硬件故障
可用64位机器校验中断码指明故障原因和严重性
是告知程序发生了设备故障
机器校验中断
管理程序调用 (访管中断) (8位中断码)
程序性中断 (16位中断码)
外部中断 (16位中断码)
输入/输出 I/O 中断 (16位中断码)
是为操作员或另一台CPU要启动一个程序所用. CPU不能禁止这种中断
重新启动 中断
通道处理机IBM370系统中断分类
分类方法
机器校验 优先级最高
1级
程序性和管理程序调用中断为第2级
2级
3级
输入输出
4级
最低级
重新启动
中断的分级
中断处理次序
但中断实际处理完的次序是可以通过 \"系统软件\" 修改中断级处理程序 的 \"中断级屏蔽位\
中断响应次序
: 按照 \"中断处理程序软件\" 和 \"中断响应硬件\" 的功能来分配
分配原则
软件状态
硬件状态
中断现场
中断断点及现场的保存
对中断请求的分析和处理 以及 中断返回
功能
中断系统功能
中断系统
总线
总线和其相配合的附属控制电路系统 称为总线系统
总线系统
数据线
地址线
命令
时序
中断信号
控制状态线
CPU芯片内的总线
芯片级
板级
系统间或主机与IO接口或设备之间的总线
系统级
按在系统位置分3级
单向传输
半双向
全双向
双向传输
按传输方向
只链接一对物理部件的总线
总线数较多
专用
非专用
按用法
总线分类
集中式 串行链接
扩展性稍差
控制较为复杂
集中式 定时查询
集中式 独立请求
根据优先次序
控制线数目
总线分配速度
可靠性
灵活性
3种控制
部件之间的 信息传递 通过 \
信息传递
异步双向互锁方式
最广泛的通信方式
同步通信
单向源控制
请求/回答双向控制
异步通信
通信技术
位
字节
字
双字
数据宽度是指 IO设备取得 \"IO总线 \"后所传送数据总量
数据通路宽度是 \"数据总线\" 的物理宽度
数据宽度
线的组合
编码
并/串-- 串/并 转换
方式
在满足性能的前提下应尽量减少线数.
机械
电气
过程
总线标准 一般包括
总线线数
程序控制IO
直接存储器访问 (DMA)
通道方式
外围处理机方式
处理方式
IO处理机
3种控制方式 (发展3阶段)
磁盘
磁带
光盘
外存
鼠标
键盘
光笔
显示器
声音输入/输出
图形扫描器
网络驱动器
传输设备
广义指令 由 \"访管指令\" 和 \"若干参数\
工作原理
适合连接大量的像光电机 等 字符类低速设备
字节多路 通道
以成组方式轮流交叉的为多台高速设备服务
适合连接多台磁盘等高速设备
数组多路 通道
适合连接优先级别高的磁盘等高速设备
选择通道
按信息传输方式不同
最大流量称为 \"通道极限流量\"
IO系统的个各通道最大流量之和
最大流量
各通道实际流量之和
实际流量
fbyte.j=Σfi.j
f max.byte= 1 / Ts+Td
字节多路通道
f block.j=max fi.j
f max.block= K/Ts+KTd = 1/(Ts/k +Td)
数组多路通道
f select.j=max fi.j
f max.select= N/ Ts+ NTd = 1/ (Ts/N+Td)
Ts: 选择设备时间
Td: 传输一个字节数据需要的时间
通道极限流量
通道流量
通道处理机
I/O系统
存储体系
cache存储器
二级存储器
采用存储器的多体交叉并行存储来提高主存的等效速度
采用Cache存储器
解决主存和CPU之间的速度差
ci 为每位价格
Smi 以位计算的存储容量
Tmi 为CPU 访问到Mi 中的信息所需要的时间
c=(c1Sm1+c2Sm2) / (Sm1 +Sm2)
每位价格c
页地址流
页面调度策略
主存容量
影响命中率的的因素
命中率H
等效访问时间TA
性能评价指标
多级存储层次
程序特性
地址映像
将多用户程序执行时的虚地址变换成对应的实地址
地址变换
映像方式的选择标准
只能用于多道程序环境
作用
是一个主存块只能直接拷贝到 Cache 的一个固定的位置上去
直接映像
页式虚拟存储器采用此法
将主存中的一个块直接拷贝到 Cache 中任意一块上, Cache 的数据块大小与主存的数据块存储的数据量大小相等。
主存的块调入 Cache 中的位置不受限制,所以冲突率最低,空间利用率高
无法从主存地址中直接获得 Cache 的块号,地址变换复杂,速度较慢
全相联映射 (常用)
Cache 存储器使用此法
采用页表+按内容访问的相联存储器构成.
页表压缩成只存放已经装入主存中的虚页与实页对应关系.
目录表法
页面失效
页面争用
发生的时机
页面替换算法
程序的 主存页数 (实页数 /主存容量)
主存是否有高的 命中率
算法是否便于实现
算法选择指标
随机算法
选择最早装入主存中的页 作为替换页
需操作系统为主存中每个实页配一个计数器字段
实现方便
先进先出算法 FIFO
虚拟存储器使用此算法
信号需用 \"与门\
\"比较对法\
硬件实现
近期最少使用 LRU
最佳置换算法 OPT
算法分类
堆栈型替换算法
每个程序在系统中都有一个 段表(映像表) 来存放该程序各段转入主存的状况信息
每个段独立
每段只包含一种类型的对象
段式 管理
页式 管理
段表 + 页表
段页式 管理
根据存储映像算法
管理方式
地址的映像 和 变换
H 是主存的命中率
T1 是主存的访问时间
T2 是辅存的访问时间
等效访问时间 TA=HT1+(1-H)T2
可提高主存命中率的方法
当主存命中率H很高时
加快内部地址映像和变换速度
等效访问速度
提高虚拟存储 等效访问速度
问题
可以单用户环境也可以多用户环境
主存中任意一块都可以映像装入到Cache中任意一块位置
全相联映像
冲突率最高
空间利用率低
组相联映像
地址的映像和变换
抵触修改法
写回法
写直达法 (存直达法)
透明性和性能分析
恒预取法
不命中时预取
取算法
cache的速度 与容量都会影响Cache 存储器的等效访问速度.
性能分析
高速缓存存储器 Cache
Cache -- 主存
主存-- 辅存
物理地址Cache
Cache --主存---辅存 直接构成三级存储层次形式
虚地址Cache
Cache -- 辅存
全Cache
三级存储体系
4章. 存储体系
标量处理机
指令相关的处理
指令相关
会发生在 主存空间 和 通用寄存器 空间
由存储控制器给 读数 和写数 申请安排不同的访存优先级来解决
推后读常见的方法
主存空间数相关
变址值相关
基址值相关
发生在主存 和 通用寄存器
k条指令的结果地址和第k+1的源地址一样
操作数相关
通用寄存器组相关
是有存储控制器给 读数 和 写数 申请安排不同的访存优先级来解决的
推后分析 K+1
后者是以增加设备为代价
设置相关专用通路
解决方式
重叠方式相关处理
指令转移的处理
各种相关
取指
分析
执行
解释一条机器指令的操作
控制简单
转入下一条指令的 时间 易于控制
速度慢
计算机个部件的利用率低
顺序解释(流水)
一次重叠
指令解释方式
部件级 流水
取指令
指令译码
取操作数
执行指令
指令流水
处理机级 流水
构成计算机系统的多个处理机之间的 流水
系统级 流水 (宏流水)
按处理级别
线性流水线
单功能流水线
静态流水线
同一时间可按不同\"运算\"或\"功能\
动态流水线
根据各段是否允许同时使用多种不同功能连接流水
CRAY-1
多功能流水线
按功能多少
可以用循环方式来处理向量和数组
Amdahl 470 V/6 和 IBM 360/91
标量流水机
是 \"向量数据表示\" 和 \"流水技术\" 的结合
向量流水机
按数据表示角度
数据从流水线的一端流入 从另一端流出
一次运算中多次使用流水线中的某些功能段
非线性流水线
按功能段中间是否有反馈回路
流水线处理机的分类
流水线单位时间内能流出的任务数和结果数
流水线中 经过最长时间的子过程 称为 瓶颈子过程
瓶颈子过程再细分
多套并联
消除速度瓶颈方法
瓶颈
n :指令条数
m: 经历m过程
△tj 是m个过程中 瓶颈执行时间
∑m△t 是m个过程所用时间之和
Tp = n / ∑m△t +(n-1) △tj
吞吐率
连续流入的任务数 / 流水线子过程数
加速比SP
n: 指令条数
m: 经历的过程
△tj : 是m个过程中 瓶颈执行时间
∑m△t : 是m个过程所用时间之和
η=n∑m△t / m ( ∑m△t + (n-1)△tj )
设备的实际使用时间 / 整个运行时间之比
效率
标量处理机的性能表现
流水方式
机器在解释执行多条指令的时候出现了对同一主存单元 或寄存器 要求 \"先写后读\" 的情况
原因
主存操作数相关
通用寄存器组数相关
直到前指令写完成
推后后续指令对相关单元的读
\"公共数据总线\" 是一种总线方式的 \"相关直接通路\
将运算结果经相关直接通路直接送入所需部件
设置 \"相关直接通路\"
重叠机器对局部相关性处理
任务流出流水线的顺序和流出流水线的顺序一致
顺序流动方式 (同步流动方式)
任务流出流水线的顺序和流入流水线的顺序不同
会出现 \"写写\" 和 \"先读后写\" 问题
异步流动方式
任务在流水线中流动顺序的安排和控制
指令处理部件
主存控制部件
定点执行部件
浮点执行部件
组成
3.通过设置的站号来控制相关专用通路的链接
解决流水控制途径
IBM360/91 中央处理机
局部性相关
指的是已进入流水线的 转移指令(尤其是条件转移指令) 和 其后续指令相关
使用猜测法
加快 \"指令内条件码 \
加快\" 程序 段内条件码 \
加快和提前形成条件码
这是用软件方法进行静态指令调度的技术
采取延迟转移
加快短循环程序的处理
解决办法
全局性相关
中断处理原则
精确断点法
不精确断点法
处理方法
流水机器的中断处理
标量流水处理机的相关处理
非常适合求解稀疏向量和稀疏矩阵这类标量计算问题
超标量处理机
超长指令字处理机
着重开发时间 \"并行性\
超流水线处理机器
超标量超流水处理机
将 \"水平型微码\" 和 \"超标量处理\" 两者相结合
超长指令字结构
5章 标量处理机
向量处理机
同一个功能部件 被要求并行工作的 多条向量指令所使用.
功能部件冲突
1.由专门应对数组运算的处理单元阵列组成的处理机
2.专门从事处理单元阵列的控制和标量处理的处理机
3.专门从事系统 输入/输出及操作系统管理的处理机 组成的一个异构型多处理机系统
实质
采用逐个求解向量元素的方法
横向处理(水平处理) 方式
向量处理方式
对整个向量按相同操作执行完之后在转去执行别的操作
向量纵向处理
分组纵横处理
向量的流水处理方式
流水线处理机 利用的是 \"时间重叠'
开发途径
6拍
浮点加
7拍
浮点乘
访主存
1拍
写寄存器
算法举例
向量流水处理机
阵列处理机利用的是 \"资源重复\
差别主要在于 \"存储器的组成方式\" 和 \"互联网络的作用 \"不同
矩阵加
矩阵乘
累加和
ILLIAC IV并行算法举例
ILLIAC IV
MPP
DAP
CM-2
MP-1
DAP600
采用的是SIMD
\"分布式\" 存储器阵列处理机
BSP
\"集中式\" 共享存储器阵列处理机
有两种构形
阵列处理机
处理机分类
加快相邻向量指令的执行
循环向量量化
链接提高性能
提高性能
设计目标
定义
同步
异步
同步与异步组合
操作方式
线路交换
包交换
线路与包交换组合
交换方法
静态 拓扑结构
两个PE之间通过置定网络开关单元状态可以重新配置.
动态 拓扑结构
网络拓扑结构
集中控制策略
分布控制策略
单级
多级
动态网络
抉择的问题
互联网络
SIMD系统
Cube0
Cube1
Cube2
有3种互联函数
立方体单级网络 8个顶点
PM2 +i(j)= j+2^i mod N
PM2-i(j)=j-2^i mod N
N=8 只有 5个不同互联函数
共有2n-1个互联函数
PM2i单极网络最短距离为 log2N-1
采用PM2+-0 和 PM2+- n/2(PM2+-3) 4个互联函数
ILLIAC IV 处理单元的互联是PM2I的特例
PM2I单级网络( Plus-Minus 2i 单级网络的简称).
全混单极
全混 Prefect- Shuffle
交换 Exchange
混洗交换单级网络 (Shuffle_Exchange) 两个互联函数
Butterfly(Pn-1 Pn-2...P1P0= P0Pn-2...P1Pn-1
二进制最高位 和最低位 进行交换
蝶形单级网络 Butterfly
单级互联网
交换开关
是各级间 出端 和入端的 互联模式
拓扑结构
控制方式
不同互联网结构的3个参量
有 log2^8 个Cube函数
3维 立方体 8个顶点
级控制
直连
交换
二功能单元
上播
下播
四功能单元
比如 OMEGA网络
单元控制
部分级控制
交换开关 控制方式 (交换函数)
exchange1
exchange2
exchange3
交换函数 Exchange
移数网络的时候采用此算法
STARAN网络(交换网络) 采用
间接二进制n方体网络 采用
多级立方体网络
首位换到末尾
shuffle(K)
采用 单元控制
每一级 都包含一个 全混拓扑 和 随后一列2^(n-1)个 四功能交换单元
多级混洗交换网络 (OMEGA网络)
多级PM2I网络
shuffle(K)
=Exchange(1)
末尾左移1位
shuffle (k1)
基准网络
是一种非阻塞式网络
多级交叉开关网络
多级碟式网络
实现方式
Benes网络
可重排网络
非堵塞网络
全排列网络
级控制立方体
部分级控制立方体
间接二进制n立方体
omega
ADM
灵活性低到高 (复杂性和成本也响应增高)
多级互联网
互联网络方式
错误存活
结构
数据运算
脉动阵列流水处理机
共享主存阵列机
6章 向量处理机
在单程序多数据流的多处理机上运行的多个并行进程上采用
同构型
异构型
分布型
构造分类
与阵列处理机的区别
在硬件结构上
在算法上
在系统管理上
资源分配和调度
遇到的问题(特点)
层次型
非层次型
只适用于总线互联的多处理机 和少量的多处理机中
全映像目录表法
有限目录表法
链式目录表法
多处理机多Cache一致性问题
紧耦合
不同处理机间通过\"通道互联\
松耦合
硬件结构分类
环形互联
交叉开关
多端口存储器
蠕虫穿洞
开关枢纽结构形式
机间互联形式
一般采用多个模块构成的并行存储器
存储器的组织
数值型
非数值型
按运算基本对象
同步型
异步型
独立性
按并行进程间的操作顺序
该算法一般指向量或循环级的并行
细粒度
中粒度
一般是指子任务的并行
粗粒度
按任务大小
思路
p 表示并行处理机的数量
Tp 表示p 台处理机的 级数
Sp 处理机的加速比: Sp =T1/Tp
Ep 处理机的设备利用率 Ep= Sp/p
1. 将表达式 去掉嵌套括号
2.判断计算机执行步骤 T1
3.判断处理机数量 P
4.画图判断 表达式的 处理级数 Tp
5.计算 Sp 和 EP
霍纳法则
算法的研究
并行算法
数据相关
流水中发生 \"先写后读\" 只能串行运行
流水发生 \"先读后写\
数据反相关
数据输出相关
并行性分析
程序用于计算的执行时间 / 辅助开销时间的比值
粒度的衡量
任务粒度的大小会显著影响多处理机的性能和效率
性能
从处理机 明显低于主处理机的异构型多处理机
适用于
主从型
使用场景
各自独立型
设计困难
适用场景
浮动型
操作系统类型
将物理上分散的多台处理机拥有的 \"本地存储器\
分布式共享存储器多处理机
对称多处理机
多向量处理机
采用 纵横交叉开关 互联网络
并行向量处理机
大规模并行处理机 MPP
系统有高的性价比
系统开发周期短
系统可扩展性好
系统的资源利用率高
用户投资风险小
用户编程方便
机群系统
发展阶段
1 TFLOPS 的计算能力
1 TByte 的主存容量
1 TByte/s的 IO 带宽
性能3T指标
发展历史
7章 多处理机
数据令牌
异步性
函数性
活动默片表示法
归并门控结点
F门控结点
T门控结点
开关门控结点
控制类操作结点
该结点在 主要包括 算术运算 和 布尔逻辑 运算
算逻辑运算操作结点
可以是 数据 的多个复制 和 控制量 的多个复制
复制操作结点
判定操作结点
数据驱动
Von Neumann型 计算机的特点是在 \"程序计数器集中\
控制驱动
按数据需求所决定的次序进行
需求驱动
数据的驱动方式
静态
动态
按\"数据令牌\"的处理方式把数据流计算机的机构分类
采用提高并行等级的数据流计算机
采用控制流与数据流相结合的数据流计算机
进展
ID 语言
整型
实型
布尔型
字符型
基本数据类型
数组
记录
结构数据有
遵循单赋值规则
有丰富的数据类型
具有很强的类型性
具有模块化程序设计思想
没有全局存储器和状态的概念
程序不规定语句的执行顺序
单赋值语言
由所有的 函数表达式的集合 和 所有目标的集合 和 所有 函数表达式 到目标函数的 集合 三部分组成
函数程序设计语言
逻辑程序设计语言
PROLOG描述式语言
使用语言
存在的问题
数据流计算机
属于数据流\
是一种特殊的 \"符号串处理机\
串归约机
图归约机
采用 \
规约机
8章 数据流计算机和规约机
计算机设计原则
1章节
标识符数据和 数据描述的区别 和作用
浮点数尾数基值的计算
哈夫曼树的画法 和 平均码长 是 概率成 位数 之和
精简和复杂指令集的 设计基本原则
2章
= 1-(1-入)^m / 入
计算每个周期平均能访问到的字数
Bm= 实际比例 * m * 宽度 / 存储周期
计算主存最大频宽 Bm
实际频宽和模数m的关系
处理机全过程画图
串行链接
独立请求
定时查询
总线控制方式 优缺点
总流量计算, 工作周期计算
3章
LRU
标记上了就不会更改 (也就是哪怕刚刚使用了也会被移出)
FIFO
OPT
堆栈算法
命中率计算 和画图
组相联映像+命中率 画图
4章
延迟禁止表F
C= ( 1 00 11 001)
冲突向量C
流水线状态转移图
最佳调度方案
平均延迟
n= 1/平均延迟
最大吞吐率
Tp= n / 一条只能完成的所需At + (n-1)最长部件执行时间
n=n*一条指令完成需要的时间 / k个步骤* (一条指令所需时间+ (n-1)最长部件时间)
瓶颈子过程消除的 画法
流水处理机的 计算
两个指令之间 间隔 是 瓶颈子过程的时间
时空图
超标量流水处理器 的画法
5章
浮点加 6拍
浮点乘 7拍
访主存 6拍
写寄存器 1拍
启动访存 1拍
送浮乘 1拍
123 串行 22+3N拍
12并行 15+2N 拍
123 链接 16+N 拍
向量浮点数计算多多少拍
设置活跃状态
1.置全部PEi为活跃状态 0<i<=15
加载元素数据到RGAi中
2.置全部A(i) 从PEi 的a 单元读取到相应 PEi的累加寄存器RGAi 中 0<i<=15
传送到RGR
4.将全部的PEi的 RGAi 转送到从传送寄存器RGRi (0<i<=15)
6.令 j=2^k-1
7.设置 PE0-PEj为不活跃状态
9 K:=K+1
11.置全部PEi为活跃状态 0<i<=15
ILLAIC IV 成对递归相加求累加和
SIMD 设计目标
PM2+0(j)=j+1 mode 16
PM2-0(j)=j-1 mode 16
PM2+1(j)=j+2 mode 16
PM2-1(j)=j-2 mode 16
PM2I 互联函数一般式
Cube0(b2b1b0) = b2b1b0
Cube1(b2b1b0) = b2b1b0
Cube2(b2b1b0) = b2b1b0
Cube函数一般式
f(P2P1P0) = P0P1P2
ButtleFly函数一般式
同一列相邻两个元素地址错开的距离为S1
S1=2^p
同一行两个相邻元素地址错开的距离S2
S2=1
M=2^2p+1
阵列处理机PE M的取质数
对于 4*4 的二维数组
错误存放 满足 j= 2a+b+3 mod 5
6章
T1 TP P SP EP
霍纳表达式的计算
fork join的时间资源图
表达式 转换 fork join
7章
将数据封装陈给一个 数据令牌的方式 传递到下一个处理结点
采用需求驱动
8章
9. 计算题汇总
0 条评论
回复 删除
下一页