画布 1
计算机系统结构
  基础知识
    基本概念
      层次结构
        L3以上机器通常用软件实现，称为虚拟机。L2是软硬件界面
        各机器级的实现主要靠翻译或解释或两者结合进行
          翻译（L4级以上）
            把高一级机器上的程序，转换为低一级机器上等效程序，在第一级机器上运行实现程序的功能
          解释（L3级以下）
            把高一级机器上程序的每一条语句，转换为低一级机器上一段等效程序并执行
            一条高级语句执行后再取下一条语句解释、执行
      定义
        概念性结构
          计算机系统中主要部件及逻辑连接结构
            CPU/存储系统/IO子系统/互联系统
          主要由硬件或固件完成
        计算机系统结构实质
          确定计算机系统中软硬件的界面，界面上是软件实现的功能，界面下是硬件和固件实现的功能
        功能特性
          1. 数据表示(硬件直接识别和处理的数据类型)；
          2. 寻址规则(最小寻址单元、寻址方式及表示)；
          3. 寄存器定义(各种寄存器的定义、数据及使用方式)；
          4. 指令集(指令类型和格式、指令间的排序和控制机构)
          5. 中断系统(中断类型、中断响应硬件的功能等)；
          6. 机器工作状态的定义和切换；
          7. 存储体系(主存容量、程序员可用的最大存储容量等)；
          8. 信息保护(信息保护方式、硬件对信息保护的支持)；
          9. I/O结构(I/O连接方式、处理机、存储器与I/O设备间数据传送方式 和格式等)。
      计算机实现与组成
        计算机组成
          计算机系统结构的逻辑实现
          物理机器级中的数据流和控制流的组成以及逻辑实现
        计算机实现
          计算机系统结构的物理实现
          器件的物理结构，器件的集成度和速度、具体电路等
        具有相同系统结构的计算机可以采用不同的计算机组成；同一种计算机组成又可以采用多种不同的计算机实现
      分类
        Flynn
          按照指令流和数据流的多倍性分类
            指令流
              计算机执行的指令序列
            数据流
              由指令流调用的数据序列
            多倍性
              在系统最受限的部件上，同时处于同一执行阶段的指令或数据的最大数目
          –单指令流单数据流（SISD）计算机系统
          –单指令流多数据流（SIMD）计算机系统（阵列处理机）
          –多指令流单数据流（MISD）计算机系统（流水结构处理机）
          –多指令流多数据流（MIMD）计算机系统（多处理机）
        Handler
          按照计算机并行度和流水线分类
            • 程序控制器PCU
            • 算术逻辑部件ALU(或运算部件PE)
            • 运算部件所包含的位级电路BLC的套数
          T(体系型号)=〈k×k′,d×d′,w×w′〉
        冯式分类法
          按照最大并行度分类
            最大并行度Pm
              在单位时间内能够处理的最大的二进制位数。
            平均并行度
                假设每个时钟周期内能同时处理的二进制位数为Pi，则T个时钟周期内的平均并行度
            平均利用率
          １字串位串WSBS(Word Serial and Bit Serial) n＝m＝1。
            纯串行处理机
          2 字串位并WSBP(Word Serial and Bit Parallel) n＝1,m＞1
            传统单处理机
          ３字并位串WPBS(Word Parallel and Bit Serial) n＞1,m＝1。
            同时处理多个字的 同一位。
          4 字并位并WPBP(Word Parallel and Bit Parallel) n，m＞1。
            同时处理多个字的 多个位
    计算机系统的设计
      大概率事件优先原理
        优先加速使用频率高的部件。对大概率
事件，赋予优先处理权和资源使用权
        最重要和最广泛采用的计算机设计准则
      程序的局部性原理
        时间局部性
          程序很可能即将用到目前正使用的信息。
        空间局部性
          程序将用到的信息很可能与正在使用的信息在空间上相邻或临近
        Amdahl定律
          加快某部件执行速度所获得的系统性能(加速比)，与该部件在系统中总执行时间的比例有关。
          系统加速比
            单部件加速
              部件加速比（Se）
                部件改进前的执行时间与改进后执行时间的比值 。 Se 通常大于1。
              可改进比例（Fe）
                可改部件的执行时间在总的执行时间中的比例总是小于等于1。
            当系统中的某个部分进行改进后，所获得的系统加速比Sn
              T0：改进前整个系统执行时间
              1－Fe：不可改进比例
            改进后程序的总执行时间Tn
          拓展Amdahl公式
      主要方法
        “由上往下”（top-down）设计
          从层次结构的最上一级开始，逐层往下设计各层的机器
          常用于专用机设计
        “由下往上”（bottom-up）设计
        从中间开始设计方法
          先进行软、硬件功能分配，确定好这个界面
            软件设计者往上设计操作系统、汇编、编译系统等。
            硬件设计者往下设计传统机器级、微程序机器级等。
    性能评测
      CPU性能公式
        CPU时间 = 执行程序所需的时钟周期数×时钟周期时间
        执行程序所需的时钟周期数 = IC ×CPI
          IC：执行程序的指令条数
          CPI是指令的平均时钟周期数
          CPI = 执行程序所需的时钟周期数／IC
        CPU时间 = IC ×CPI × t = IC ×CPI /f
          f=1/t 系统时钟频率f (MHz)
          • 时钟周期时间t ：取决于硬件实现技术和计算机组成；
          • CPI：取决于计算机组成和指令系统的结构；
          • IC：取决于指令系统的结构和编译技术。
      执行时间（执行单个程序的时间）
        --CPU时间：CPU执行给定的程序所花费的时间。
        --用户CPU时间：用户程序所耗费的CPU时间。
        --系统CPU时间：程序运行期间操作系统耗费的CPU时间
      速度性能
        每秒（百万条）指令数MIPS
          1. 依赖指令系统。
          2. 同一台机器，MIPS依程序不同而变化。
          3. 适于评估标量计算机
        每秒（百万次）浮点运算MFLOPS
          1）MFLOPS基于操作而非指令的，用来比较不同机器。
          2）衡量机器浮点操作性能，非整体性能，如编译程序
      测试程序
        1.真实程序
        2.核心程序
        3.小测试程序
        4.综合测试程序
      性能比较
        平均执行时间
          Ti：第i个测试程序的执行时间
          n：测试程序组中程序的个数
        加权执行时间
          Wi：第i个测试程序在测试程序组中所占的比重
          Ti：该程序的执行时间
        调和平均值法（性能是速度 R）
          速度Ri(如MFLOPS）代替时间Ti
        几何平均值法（性能是速度 R）
          Ri表示（由n个程序组成的工作负荷中）执行第i个程序的速度，Ri=1/T i，∏表示连乘符号。
    发展
      冯·诺依曼结构
        特点
          存储程序原理及指令驱动
            程序预先存放在存储器，机器启动按照程序指定的逻辑顺序执行，自动完成由程序所描述的处理工作。
          运算器为中心。
          存储器中指令和数据同等对待。存储器按地址访问。
          存储器是按顺序线性编址的一维结构，每个单元位数固定。
          指令顺序执行。程序分支由转移指令实现
            • 一般按照指令在存储器中存放的顺序执行。
            • 由指令计数器PC指明当前执行指令的地址。
          指令由操作码和地址码组成。
          指令和数据均以二进制编码表示，采用二进制运算。
        改进
          并行处理技术
          指令系统发展
          存储器组织结构的发展
          输入/输出方式的改进
      软件对系统结构的影响
        软件移植
          采用统一的高级语言：实现软件移植的一种理想的方法，但较难实现。
          系列机（兼容机）：同一个厂家生产的具有相同系统结构，不同的组成和实现技术的一系列不同型号的机器。
        兼容
          向上（下）兼容
            按某档机器编制的程序，不修改就能运行于比它高（低）档的机器。
          向前（后）兼容
            按某个时期投入市场的某种型号机器编制的程序，不修改地就能运行于在它之前（后）投入市场的机器。
            向后兼容是系列机的根本特征。
        模拟（机器语言解释）
          用软件方法在一台机器（宿主机）上实现另一台机器（虚拟机）的指令集（在一种系统结构上虚拟实现另一种系统结构）。
        仿真（微程序解释）
          用微程序直接解释另一台机器的指令系统。
          需要较多的硬件（包括控制存储器）
      器件发展对系统结构的影响
        摩尔定律
          集成电路芯片上集成的晶体管数目每隔18个月翻一番
        器件速度提高→机器主频提高
        –器件可靠性提高→流水部件实现
        –微处理器性能提高、价格下降→多处理机系统产生
        器件的发展→并行结构的实现→并行算法/语言/操作系统的研制
      应用对系统结构的影响
        专门为某领域设计的专用计算机通常比通用型计算机更有效率和价格优势
    并行性的发展
      计算机在同一时刻或同一时间间隔内进行多种运算或操作，称为并行性。
        同时性：两个或两个以上的事件在同一时刻发生。
        并发性：两个或多个事件在同一时间间隔内发生
      并行性等级
        处理数据
          字串位串：每次只对一个字的一位进行处理。
          字串位并：同时对一个字的全部位进行处理，不同字之间是串行的（开始出现并行性）。
          字并位串：同时对许多字的同一位（位片）进行处理（有较高的并行性）。
          全并行：同时对许多字的全部位或部分位进行处理。最高一级并行。
        执行程序
          指令内部并行：单条指令中各微操作之间的并行。
          指令级并行：并行执行两条或两条以上的指令。
          线程级并行：并行执行两个或两个以上的线程。通常是以一个进程内派生的多个线程为调度单位。
          任务级或过程级并行：并行执行两个或多个任务或过程（程序段），通常以子程序或进程为调度单元。
          作业或程序级并行：并行执行两个或多个作业或程序。
      提高并行性的技术途径
        时间重叠
          让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转或速度。
        资源重复
          通过重复设置硬件资源，提高系统的性能
        资源共享
          多个任务按一定时间顺序轮流使用同一套硬件设备
      单机系统中并行性的发展
        时间重叠
          部件功能专用化
             把一件工作按功能分割为若干相互联系的部分；
             把每一部分指定给专门的部件完成；
             按时间重叠原理把各部分的执行过程在时间上重叠起来使所有部件依次分工完成一组同样的工作
        资源重复
           多体存储器：实现访问级并行
           多操作部件：实现指令级并行
        资源共享
          分时系统
      多机系统中并行性的发展
        同构型多处理机、异构型多处理机、分布式系统
        耦合度
          紧密耦合系统（直接耦合）
            计算机之间物理连接的频带较高，一般通过总线或高速开关互连，共享主存。
          松散耦合系统（间接耦合）
            一般通过通道或通信线路实现计算机之间的互连，可共享外存设备（磁盘、磁带等）。机器之间的相互作用在文件或数据集一级上进行
  流水线技术
    分类
      按流水线等级
        运算操作流水线（操作部件流水线）
          如：浮点加法器
          把处理机中的部件分段，使各类型的运算操作按流水方式进行
        处理级流水线（指令流水线）
          把一条指令的执行过程分解为若干子过程，每个子过程在独立的功能 部件中执行。
        访存部件流水器
        系统级流水线（宏流水线）
          多计算机通过存储器连接构成流水线
      按流水线所完成的功能分类
        单功能流水线
          只能完成一种固定功能的流水线
        多功能流水线
          流水线的各段可以进行不同的连接，以实现不同的功能
          静态流水线
            在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作
            静态流水线功能切换时，要等前一种运算全部流出流水线
          动态流水线
            在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能
      按照流水线中是否有反馈回路来进行分类
        线性流水线
          流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次
        非线性流水线
          流水线中除有串行连接外，还有反馈回路
      按照任务流入和流出的顺序是否相同来分类
        顺序流水线
          流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同
        乱序（异步）流水线
          流水线输出端任务流出的顺序与输 入端任务流入的顺序可以不同
    经典5段流水线
      IF（取指令）
        从存储器中取出指令放入指令寄存器。PC值加4（每条指令占4个字节），顺序指向下一条指令。
      ID（指令译码、读寄存器）
        译码并访问通用寄存器，读出存放在寄存器中的操作数。
      EX（执行、有效地址计算）
        • ALU指令（寄存器－寄存器）：执行运算
        • load和store指令：计算并形成访存有效地址
        • 分支指令：计算并形成转移目标地址（不确定是否转移）
      MEM(存储器访问、分支完成)
        • store指令：把指定的数据写入存储器单元。
        • load指令：从存储器中读出相应的数据；
        • 分支指令：若分支成功，把转移目标地址送入PC
        ALU类指令在此周期为空操作
      WB（写回）
        • ALU运算指令：结果数据来自ALU。
        • load指令：结果数据来自存储器。
        • 分支指令（或store指令）：空操作
      不同类指令中各流水段的具体操作
        分支指令、ALU指令有一个（ME）周期的空操作
        LOAD、STORE指令没有空操作
    技术基础
      部件功能专用化
        一件工作按功能分割为若干相互联系的部分
        每部分指定给专用部件完成
        各部件执行过程进行时间重叠
          各流水段时间尽可能相等
          时间最长的段为流水线瓶颈
          每段流水线后面有一个缓冲寄存器,称为流水寄存器。在相邻两段间传送数据，有缓冲、隔离、同步作用
        所有部件依次序分工完成一件工作
    流水线表示
      连接图
        流水线各段依次相连。
        每个流水段完成一条指令的同一部分。
        从流水线左端进入，向右经流水线，从另一端流出。
        不同阶段并行完成流水线中不同指令的不同部分
      时空图
        从时间和空间两个方面描述流水线工作过程。
        通过（装入）时间
          第一个任务从进入流水线到流出结果所需的时间
        排空时间
          最后一个任务从进入流水线到流出结果所需的时间
    性能指标
      吞吐率
        单位时间内流水线所完成的任务数量或输出结果的数量
        最大吞吐率
        瓶颈
          解决流水线瓶颈
            重复设置瓶颈段
              让多个瓶颈流水段并行工作
              时空图
            瓶颈段再细分
              细分为多个子流水段——超流水线
      加速比
        完成同样一批任务，不使用流水线所用的时间Ts与使用流水线所用的时间Tk之比
        最大加速比
          等于流水线的段数
      流水线效率（流水线设备利用率）
        流水线中的设备实际使用时间与整个运行时间的比值
        各段时间相等,各段的效率ei相同
        通过时空图计算
          时空区总面积：总时间与k个流水段所围成的矩形
      最佳段数
        求导
    流水线的相关与冲突
      相关
        数据相关（真数据相关）
          流水线中多条指令并行执行时 ，指令读／写操作数顺序可能改变，称为数据相关
          后一条指令直接读前一条指令的写结果
          后一条指令间接读前一条指令的写结果
        名相关
          如果两条指令使用相同的名，但它们之间并没有数据流动，则称这两条指令存在名相关
            反相关
              指令i读的寄存器名＝指令j写的寄存器名
            输出相关
              指令i写的寄存器名＝指令j写的寄存器名
          名相关可以通过寄存器换名来消除
          名
            指令所访问的寄存器或存储器单元的名称
        控制相关
          分支指令引起的相关。包括（无）条件转移、中断等，又称全局相关。控制相关能改变程序方向，造成流水线断流
          特点
            与分支指令控制相关的指令不能移到分支之前。否则就不受分支控制
            如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。否则就受该分支控制了
            分支指令通常在流水线末端时转移条件才建立，对流水线性能影响大
          结果
            发生转移
            不发生转移
      冲突
        结构冲突
          硬件资源不满足指令重叠执行的要求
          解决方法
            插入暂停周期
            设置相互独立的指令存储器和数据存储器
或设置相互独立的指令Cache和数据Cache
        数据冲突
          指令在流水线中重叠执行时，需要用到前面指令的执行结果而发生的冲突
            RAW（写后读冲突）\ WR
              指令j在指令i写之前就读出
            WAW（写后写冲突）\ WW
              指令j在指令i写入前就写入
              在五段流水中一般不发生此冲突
                – 流水线中不只一个段可以进行写操作；
                – 指令被重新排序了
            WAR（写后读冲突）\ RW
              指令j在指令i读出前就写入
              五段流水中一般不发生此冲突
                – 有些指令的写结果操作提前了
                – 有些指令 的读操作滞后了
                – 指令被重新排序了
          解决方法
            定向技术
              通过专用通路将前指令结果提前送往后续指令
                当检测到前一个ALU运算结果写入的寄存器是当前ALU操作的源寄存器时，就选择定向的数据作为ALU的输入
            停顿
              检测发现数据冲突，流水线停顿，直至冲突消失
            编译器解决（指令调度）
              编译器重新组织指令顺序来消除冲突
        控制冲突
          分支指令和其它会改变PC值的指令所引起的冲突
          解决方法（减少分支延迟）
            “冻结”或“排空”流水线
            流水线中尽早判断出分支转移是否成功
            尽早计算出分支目标地址
            编译器优化
              预测分支失败
                总预测分支失败，并按失败的分支路径处理
                预测正确
                  流水线正常流动
                  无延迟
                预测错误
                  把分支指令后取出的所有指令转化为空操作，并按分支目地址重新取指令执行
                  分支结果出来之前不能改变处理机的状态，以
便猜错时处理机能够回退到原先的状态
                  有延迟
              预测分支成功
                总预测分支成功，并按成功的分支路径处理
              延迟分支
                顺序执行延迟槽中指令
                  延迟槽
                    一条或几条与转移指令结果无关而有用的指令
                  主要思想
                    编译器通过重排指令序列，在分支指令后紧跟一条或几条延迟槽指令，不管分支是否成功，都顺序执行延迟槽中的指令。从而逻辑上“延长”分支指令的执行时间
                    在执行完延迟槽的指令就知道分支结果
                      延迟槽中的指令“替换”了流水线原来必需插入的“暂停”周期
                  延迟槽指令的调度策略
                    从前调度
                      被调度的指令必须与分支无关，适合任何情况
                    从目标处调度
                      分支成功时起作用。分支成功概率高时采用
                    从失败处调度
                      分支失败时起作用。不能从前调度时可用
              分支取消机制
                当分支的实际执行方向和事先所预测的一样时，
执行分支延迟槽中的指令
                否则,将分支延迟槽中的指令转化成空操作
            提前到ID段完成，分支延迟为一个时钟周期
          转移指令对性能的影响
            一条k段流水线，执行n条指令，其中转移指令占比为p，转移成功的概率为q
              最坏情况，一次转移造成k-1时钟周期的断流
              总执行时间
              流水线吞吐率
                最大吞吐率
              流水线吞吐率下降
    流水线的实现
      MIPS
        时钟周期
          • 取指令
            NPC←PC+4（NPC：下一条程序计数器）
          • 指令译码/读寄存器
            指令译码和读寄存器操作并行进行
          • 执行/有效地址计算
            load指令和store指令：计算访存地址
            寄存器－寄存器ALU指令：产生运算结果
            分支指令： 计算转移地址 ( if cond =0 )
          • 存储器访问/分支完成
            所有指令在该周期对PC进行更新
              分支成功： PC ←ALUo
                分支指令： if （cond） PC ←ALUo else PC←NPC
              其它指令：PC←NPC
            load指令:LMD←Mem[ALUo]
              把Mem中读出的数据存放在LMD
            store指令：Mem[ALUo]←B
              把B中数据存放在Mem
          • 写回
            寄存器－寄存器ALU指令
              Regs[rd]← ALUo
                ALUo：存放ALU的运算结果
            寄存器－立即数ALU指令
              Regs[rt]← ALUo
            load指令
              Regs[rt]← LMD
                LMD：存放load指令从存储器读出的数据
            store指令
              空操作
        临时寄存器
          • PC：程序计数器，存放当前指令的地址。
          • NPC：下一条程序计数器，存放下一条指令的地址。
          • IR：指令寄存器，存放当前正在处理的指令。
          • A：第一操作数寄存器，存放从通用寄存器组读出来的数。
          • B：第二操作数寄存器，存放从通用寄存器组读出来的数。
          • Imm：存放符号扩展后的立即数操作数。
          • Cond：存放条件判定的结果。“真”表示分支成功。
          • ALUo：存放ALU的运算结果。
          • LMD：存放load指令从数据存储器（DM）读出的数据。
        指令
          操作码字段及rs、rt字段都在固定位置
          I类指令
          R类指令
        改进
          段与段之间设置流水寄存器
            流水寄存器名称：用其相邻的两个段的名称拼合而成
            流水寄存器由若干个寄存器构成
          向后传递
            增加了向后传递IR等指令信息到寄存器组的连接
或数据通路
          将PC的修改移到了IF段
          MUX1由MEM段移到IF段.提前得到分支目标地址
        解决数据冲突问题
          所有数据冲突均在ID段检测到
            如果存在数据冲突，就在相应的指令流出ID段之
前将之暂停。完成该工作的硬件称为流水线的互锁机制。
          在ID段确定需要什么样的定向，并设置相应的控制
          检测冲突是通过比较寄存器地址是否相等来实现的
        定向逻辑
        控制冲突
          分支指令的条件测试和分支目标地址计算是在EX段完成对PC的修改是在MEM段完成。分支延迟是3个时钟周期。
  向量处理机（指令级并行）
    向量的处理方式
      向量处理
        一条向量指令可以处理n个或n对操作数。对这组数的运算叫做向量处理。相应指令叫向量指令。
      基本格式
        参加运算的每个向量都需指明其基地址、位移量和向量长度
      横向处理
        计算按行方式从左至右横向进行，逐个求向量中的每个分量
        横向处理不适合于向量流水处理
      纵向处理
        计算按列方式自上而下纵向地进行
        向量长度N超过向量寄存器限度时，可分组处理
      纵横处理（分组处理）
        组内采用纵向处理，组间采用横向处理
        纵横方法适合寄存器-寄存器工作的向量处理机
    向量处理机结构
      存储器-存储器型结构
        流水线运算部件的输入和输出端都直接（或经缓冲器）与存储器相连
        源向量和目的向量都存放在存储器中，运算的中间结果需要送回存储器
        普通存储器的3倍带宽：一个时钟周期内读出两个操作数并写回一个结果
          存储器采用多个存储器模块组成的结构方式
          运算器与主存间有3条相互独立的数据通路
          3条数据通路可并行工作，但一个存储器模块在同一时刻只为一个通路服务
        带有可变延迟缓冲器的向量流水处理机
          地址生成器形成指令执行过程中需要的数据地址
          延迟时间根据输入向量和结果向量第一个元素的位置及运算器操作来设置
          输入、输出端增加缓冲器，与在流水线内部加缓冲器以消除内部冲突的思想一致
      寄存器-寄存器型结构
        特点
          访问中间存储器更快
          通过中间存储器形成新的数据结构，以满足流水线高效处理的要求
          中间存储器提供高带宽及多种寻址方式。支持多个功能部件的并行操作和流水线结构的重叠进行，支持流水线链接技术
        CRAY-1向量处理机
          向量运算
            主存储器与V寄存器之间数据传送以成组传送方式进行
            向量指令能对向量寄存器的分量进行连续处理
              6个单功能流水部件：进行向量运算
              向量运算流水线，满足一定条件，可并行工作
                1）功能部件不冲突： 例如 V0←V1＋V2 和 V6←V4*V5
                2）源寄存器不冲突：如 V3←V1＋V2 和 V6←V5*V4
                3）结果寄存器不冲突：如 V4←V1＋V2 和 V6 ←V3*V5
                4）数据不相关：： 例如 V0←V1＋V2 和 V6←V4*V5
          标量运算
            B寄存器与主存间数据传送以成组传送方式(相当于A寄存器组的Cache)
            指令缓冲器预取指令,并存放主要程序段
          指令类型
            • Vk ← Vi op Vj
            • Vk ← Si op Vj
            • Vk ← 主存
            • 主存 ← Vi
            只要不出现向量Vi和功能部件冲突，各Vi之间和各功能部件之间都能并行工作
    提高向量流水处理机性能的方法
      多功能部件的并行操作
        向量寄存器使用冲突
          并行工作的向量指令中，源向量或结果向量使用相同的向量寄存器
        功能部件使用冲突
          多条并行工作的向量指令所使用同一功能部件
      链接技术
        结果寄存器立即成为后继指令操作数寄存器（先写后读的数据相关性）
        链接条件
          空间方面
            无向量寄存器和功能部件使用冲突
            向量指令的两个源操作数分别是两条先行指令
的结果寄存器时，两条向量指令的向量长度也须相等
          时间方面
            只有前一条指令的第1个结果分量送入结果向
量寄存器的那一个时钟周期方可链接
            向量指令的两个源操作数分别是两条先行指令
的结果寄存器时，先行两条指令产生运算结果
的时间必须相等
      分段开采技术
        向量长度大于向量寄存器长度时，向量须分段
处理，即一次处理一个向量段
        向量分段由系统硬件和软件控制完成，对程序
员透明
        进入循环前，系统会根据向量长度计算出循环
的次数
        分段需一定时间开销，包括流水线启动开销
      多处理机体系结构
    性能评价
      标量处理指令
        一条指令得到一个运算结果
          指令平均时钟周期（CPI）
          每秒执行指令数
      向量处理指令
        一条向量指令可得到几十或更多个运算结果
          一条向量指令的处理时间Tvp
            Tstart：向量指令启动时间（周期数）
              从向量指令开始执行到还差一个时钟周期就产生
第一个结果所需的时钟周期数
          每秒浮点运算数目MFLOP
            MFLOPS的倒数---每次浮点运算所需的时间
            MFLOPS衡量机器浮点操作性能，不体现整体性能
            程序在不同机器上执行的指令数目可能不同，但执行的浮点运算总次数相同
          一组向量指令的处理时间
            编队
              能在一个同一时间或时间段并行或链接执行的
一条（或多条）向量指令，称为一个编队
                并行编队
                  同一编队中的多条向量指令能并行执行
                链接编队
                  同一编队中的多条向量指令能链接执行
            m个编队顺序执行
              并行编队
                多条指令的执行时间取该编队中各指令的执行时间的最大值
              链接编队
                编队的启动时间为链接各部件启动时间之和
            分段开采
          向量流水线的最大性能R∞（峰值性能）
            向量长度为无穷大时，向量处理机的最高性能
          半性能向量长度n1/2
            向量处理机性能为其最大性能的一半时所需的向量长度
            反映为建立流水线而导致的性能损失
              n1/2越小，流水线建立的时间越少。 性能越好
              若向量长度n＝n1/2
                表明这时整个向量流水处理中有一半时间是在做有效操作，一半时间被浪费
          向量长度临界值
            是指对于某一计算任务而言，向量方式的处理速度优于标量串行方式处理速度时所需的最小向量长度
    向量处理机实例
      CRAY Y-MP 816处理机
      CRAY C90处理机
      NECSX-X系列 处理机
  指令级并行及其开发——硬件方法
    概念
      指令级并行（ILP）
        细粒度并行性
          处理机指令一级或操作一级的并行处理
        降低指令平均周期数CPI
        主要途径
          资源重复（空间并行）
            重复设置多个处理部件
          流水线技术（时间并行）
            使指令重叠并行执行
        主要方法
          基于硬件的动态开发
          基于软件的静态开发
      流水线实际CPI
      IPC（每周期指令数）
        一个时钟周期里流水线完成的指令条数
        IPC = 1 / CPI
      基本程序块
        基本程序块内并行性低，必须跨越程序块开发ILP
      循环级并行
    相关
      保持异常行为
        改变指令执行顺序，不改变程序中异常的发生情况
        原来程序中的异常怎么发生，改变执行顺序后还是怎么发生
      数据流
        数据值从生产者到消费者的实际流动
          分支指令使数据流有动态性
          分支指令的执行结果决定哪条指令才是所需数据的生产者
      只要保持异常行为也不改变数据流。就可以不遵守控制相关，并进行指令调度
    动态调度
      概念
        程序执行过程中，依赖专门硬件和算法对代码进行调度
        通过配置多个资源（功能部件），允许多条指令同时动态的处于执行阶段
        能处理一些编译器情况不明的相关
        以硬件复杂性增加为代价
      特点
        调度策略
          乱序执行、乱序完成
        具有多个功能部件，或功能部件流水化
      结构冲突、数据冲突的检测均在ID阶段进行
        乱序执行
          ID阶段分为两段
            流出IS
              指令译码，检查是否存在结构冲突
              没有结果冲突就让指令流出
            读操作数RO
              检测数据冲突
              等待数据冲突消失（操作数就绪），读操作数
          ID阶段和执行阶段间新增新的指令窗口
            译码段与执行段有指令窗口，存放译码信息
            允许窗口中不冲突的后续指令提前执行
      带来的问题
        WAR、WAW冲突
        异常处理复杂化
          不精确异常
            异常处理时现场与严格按程序顺序执行时的现场不同
          保持正确异常行为
            对于一条产生异常的指令，只有确定该条指令会被执行，才允许它产生异常
            只有那些严格按程序顺序执行时发生的异常才会真正发生
      动态调度算法
        记分牌算法（浮点部件）
          基本思想
            将ID段分为流出、读操作数两个段
            执行段采用多功能部件，允许多条指令在执行段并行操作
            尽早执行没有结构冲突、数据冲突的指令
            实施判断是否有WR、RW、WW相关存在
            通过互锁机制，阻止数据冲突发生
            由记分牌硬件实现对指令的动态调度
          硬件表格
            表格
              指令执行状态表
                记录已取指的指令的执行状态
                  流出
                  读操作数
                  执行
                  写回
              功能部件状态表
                记录各功能部件状态
                  Busy
                    功能部件是否忙
                  Op
                    正在或将要执行的操作
                  Fi
                    目的寄存器编号
                  Fj、Fk
                    源寄存器编号
                  Qj、Qk
                    向源寄存器Fj、Fk写数据的功能部件
                  Rj、Rk
                    标志位
                      yes：Fj、Fk的操作数可用（就绪且未被取走）
                记录数据相关关系
              寄存器状态表
                指出哪个功能部件将把结果写入该目标寄存器
                如果正执行的指令都不以它为目的寄存器，相应项置为”no“
          执行过程
            流出（解决WW冲突）
              当功能部件空闲，目的寄存器可用（无WW冲突），流出指令
              修改记分牌记录
            读操作数（解决WR冲突）
              源操作数可用，读出并执行
              否则，等待写完成后读出
            执行
              功能部件开始执行
              产生结果后，通知记分牌已完成执行
              可能占用多个时钟周期
              其他不与正在执行或被锁定指令相关的指令，可以同时执行
            写结果（避免RW冲突）
              执行部件完成后，检测目标寄存器
                如果检测RW冲突
                  不许该指令将结果写道目标寄存器，等待直到冲突消失
                如果不存在RW冲突
                  将结果写入目的寄存器，释放该指令使用的所有资源
          冲突分析
            WW冲突导致流出阶段停顿
            RW冲突导致写结果阶段停顿
            WR冲突导致读操作数阶段停顿
            资源冲突导致流出阶段停顿
          具体算法
            约定
              Result：寄存器状态表
            指令流出
              进入条件
              内容修改
            读操作数
              进入条件
              内容修改
            执行
              结束条件
                功能部件操作结束
            写结果
              进入条件
              内容修改
          性能分析
            性能受限因素
              通过停顿解决WW、RW、WR冲突
              记分牌容量决定流水线可以同时容纳的指令数量
              功能部件总数决定结构冲突的严重程度
              程序代码中可开发的并行性
              反相关、输出相关
                引起记分牌的WW、RW冲突
        Tomasulo算法（公共数据总线法）
          基本思想
            通过分散控制处理数据相关和乱序执行，记录和检测指令相关，把发生WR冲突可能性降到最小
            通过寄存器换名消除WAR冲突和WAW冲突
              寄存器换名通过保留站和流出逻辑共同完成
                如数据已就绪，其操作数寄存器号换成 数据本身
                如果其操作数还未计算出来，则将该指令中相应寄存器号换名为将产生该操作数的保留站标识
            更多依赖硬件
          主要结构
            指令队列
              存放指令部件送来指令
              先进先出、顺序流出
            保留站
              保存流出到本功能部件执行的指令信息
                每个保留站有一个标识字段：唯一的标识该保留站
                记录：操作码、操作数、用于检测和解决冲突的信息
                浮点加法器：3个保留站
                浮点乘法器：2个保留站
            访存部件缓冲器
              存放读/写存储器的数据或地址
              load缓冲器、store缓冲器
            公共数据总线（CDB）
              所有计算结果送到CDB，由CDB直接播送到各个需要的地方（无需经过寄存器）
              有多个执行部件且采用多流出的流水线，采用多条CDB
            浮点寄存器FP
              通过总线连接到各功能部件
              通过CDB连接到store缓冲器
            运算部件
              浮点加法器
              浮点乘法器
          执行过程
            流出
              从指令队列头部取一条指令
                如果该指令对应的保留站空闲，就把该指令送到保留站r
                  如果操作数已就绪，把操作数送到保留站r
                  如果操作数未就绪，将产生操作数的保留站标识送到保留站r（寄存器换名，消除RW冲突）
                如果保留站不空闲，指令不流出
              目的寄存器预约
                指定将接收哪个保留站的结果
                消除WW冲突
            执行
              通过保留站执行指令规定的操作
                如果两个操作数已就绪，相应的执行部件执行规定的操作
                如果某个操作数没有计算出来，保留站监视CDB，并等待计算结果
                一旦记录的保留站完成计算，直接将数据送给保留站r
                如果多条指令在同一周期操作数均就绪，不同部件可以并行执行
              load、store指令分两步执行
                计算有效地址（等待基地址寄存器就绪）
                将有效地址送往load、store缓冲器
            写结果
              功能部件计算完成后，将计算结果放到CDB
              寄存器、保留站、store缓冲器从CDB上获取值
          保留站
            字段
              Op
                对源操作数进行的操作
              Qj、Qk
                将产生源操作数的保留站号
                  0表示操作数已就绪且已在Vj、Vk中，或者不需要操作数
              Vj、Vk
                源操作数的值
              Busy
                yes：表示本保留站或缓冲单元忙
              A（load、store缓冲器有该字段）
                先存放指令中的立即数字段
                地址计算后存放有效地址
              对于一个源操作数来说，二者只能有一个有效
            每条指令流出后的状态保留在保留站内
          特点
            冲突检测和指令执行控制是分布的
              每个功能部件的保留站的信息决定什么时候指令可以开始执行
              计算结果通过CDB直接从生产它的保留站传送到所有需要它的功能部件
            通过寄存器换名和对操作数进行缓冲，消除RW冲突
            通过对目标寄存器的顺序预约，消除WW冲突
            通过延迟执行解决WR冲突
            保留站、寄存器组均有附加信息，用于检测和消除冲突
          具体算法
            约定
            流出
              浮点运算
                进入条件
                  有空闲保留站
                内容修改
            执行
              进入条件
            写结果
              进入条件
                保留站r执行结束，且CDB就绪
              需要该操作数的保留站读取数据，Qk（Qj）置0；Vk(Vj)置为该数据
              数据写入寄存器组中，将Qi置0
    静态调度
      依靠编译器进行指令调度和优化
      通过把相关的指令拉开距离来减少可能产生的停顿
      编译期间进行
    动态分支预测
      根据分支指令过去的表现来动态地预测下一次转移的方向
        预测技术
          分支历史表（BHT）
            使用BHT记录分支指令最近几次的执行情况，并以此来进行预测
            BHT格式
              转移指令、历史表信息、转移目标指令
            逻辑结构
            使用两位二进制来记录历史（预测状态转移图）
            步骤
              分支预测
                当分支指令达到ID段时，从BHT读出信息进行分支预测
                预测正确
                  继续处理后续指令
                预测错误
                  作废已预取和分析的指令，恢复现场，并从另一条分支路径重新取指令
                  清除预取队列缓冲器，产生延迟
              状态修改
                根据预测状态转移图
            只能提供转移目标指令信息，不提供转移目标指令地址信息
          分支目标缓冲器（BTB）
            将分支成功的分支指令的地址和它的分支目标地址放到一个缓冲区中保存
            缓冲区以分支指令的地址作为标识，得到转移目标指令地址信息
            IF段访问BTB，分支开销降为0
            BTB格式
              使用专门硬件实现的表格
              添加至少两位的分支历史表
                BTB转换图
            BTB结构
            操作
            BTIB（适合多流出处理器）
              在表中对于每条分支指令都存放若干条分支目标处指令，形成分支目标指令缓冲器
          基于硬件的前瞻执行
    多指令流出技术
      超标量
        基于静态调度的多流出技术
          指令按序流出
          流出时由硬件进行冲突检测
            流出包（流水线从取值部件收到的指令）内部是否有冲突，选择可以流出的指令
            流出指令与正在执行的指令是否有冲突
          性能限制
            load指令
              后续三条指令不能使用其结果
            分支延迟
              流出包中的第一条指令，延迟三个时钟周期
              流出包的第二条指令，延迟两个时钟周期
        基于动态调度的多流出技术
          拓展Tomasulo算法:支持双流出超标量流水线
            每个时钟周期流出两条指令（一条整数指令，一条浮点操作指令）
            实现方法
              半个时钟周期完成流出步骤，一个时钟周期处理两条指令
              设置一次能够处理两条指令的逻辑电路
              现代四条或以上的超标量流水处理机，两种方法同时使用
            性能限制
              整数部件、浮点部件负载不均衡
              循环迭代控制开销大
              处理机必须在分支结果出来后开始下一条L.D指令执行
      超长指令字
        特点
          将能并行执行的指令拼接在一条指令中
          超长指令字的生成由编译器完成、冲突避免也由编译器处理
          每个时钟周期启动一条超长指令
          超长指令字包含多个控制字段
            每个字段独立地控制每个不同的功能部件，称为操作槽
          有大量数据通路和功能部件
        问题
          程序代码长度增加
          锁步机制
            任何一个操作部件出现停顿，整个处理机都要停顿
          机器代码不兼容
        经典结构
        超长指令子处理
      超流水处理机
        在一个时钟周期能够分时流出n条指令（每隔1/n时钟周期流出一条指令 ）
        R4000流水线
  互连网络
    一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。
      三要素
        开关元件
        互连结构
          节点对应开关元件或处理机。边对应通信链路
        控制方式
          网络中各种开关的控制方法
      基本特征
        拓扑结构
          静态网（直接网络）
            各节点间有专用通信线路（链路），运行间不改变或重新组合
          动态网（间接网络）
            各节点间有专用通信线路（链路）,可通过网络中开关重新组合。节点与节点的连接由程序或控制信号动态地改变
        控制策略
          集中控制
            全局控制器接收所有通信请求，设置互连网络的开关连接
          分散控制
            通信请求和开关设置由互连网络分散地进行
        定时方式
          同步系统
            系统使用一个集中的统一时钟
          异步系统
            无统一时钟，节点根据各自情况独立工作
        交换方法
          线路交换
            源结点和目的结点间的物理通路在整个数据传送期间一直保持连接
          分组交换
            信息分割成组(包)，各组(包)通过多个不同路径传分别送入互连网络。传送不存在一个实际连接的固定通路
    互连函数
      表示方法
        函数表示法（排列函数）
          变量x表示输入，函数f(x)表示输出
          自变量和函数常用二进制、十进制表示
          互连函数反映网络输入数组和输出数组之间对应的排列关系
        输入输出对应表示法
        图形表示法
        循环表示法
      基本互连函数
        恒等函数
        交换函数
          主要用于构造立方体和各种超立方体互连网络
            当N＝8，n＝3时可得到常用的立方体互连函数
          它共有n＝log2N种互连函数（N节点个数）
        均匀洗牌函数
        逆均匀洗牌函数
        碟式函数
        反位序函数
        移数函数
        PM2I函数
          各输入端都错开2i个位置（模N）后连到输出端
          PM2I互连网络共有2n个互连函数
    互连网络的结构参数与性能指标
      结构参数
        网络规模N
          网络中结点的个数（表示该网络所能连接的部件的数量）
        结点度d
          与结点相连接的边数（通道数）包括入度和出度
            进入结点的边数叫入度。
            从结点出来的边数叫出度。
        结点距离
          对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值
        网络直径D
          网络中任意两个结点之间距离的最大值
          网络直径应当尽可能地小
        等分宽度b
          把由N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值
          线等分宽度：B＝b×w
            其中：w为通道宽度（用位表示）
            该参数主要反映了网络最大流量
        对称性
          从任何结点看到的拓扑结构都是相同的网络称为对称网络
      性能指标
        通信时延
          从源结点到目的结点传送一条消息所需的总时间
            软件开销
              在源结点和目的结点用于收发消息的软件所需的执行时间
              主要取决于两端端结点处理消息的软件内核
            通道时延
              通过通道传送消息所花的时间
              通路时延 = 消息长度/通道带宽
              通常由瓶颈链路的通道带宽决定
            选路时延
              消息在传送路径上所需的一系列选路决策所需的时间开销
              与传送路径上的结点数成正比
            竞争时延
              多个消息同时在网络中传送时，会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间就是竞争时延
            网络时延
        端口带宽
          单位时间内从该端口传送到其他端口最大信息量
            在对称网络中，端口带宽与端口位置无关。网络的端口带宽与各端口的端口带宽相同
            非对称网络的端口带宽则是指所有端口带宽的最小值
        聚集带宽
          网络从一半结点到另一半结点，单位时间内
能够传送的最大信息量
        等分带宽
          与等分宽度对应的切平面中，所有边合起来
单位时间所能传送的最大信息量
    静态互连网络
      线性阵列
        结构参数
          非对称
          端结点的度：1
          其余结点的度：2
          直径：N－1
          等分宽度b=1
      环和带弦环
        环
          结构参数
            对称
            结点度：2
            双向环的直径：N/2
            单向环的直径：N
            环的等分宽度b=2
        带弦环
          增加的链路愈多，结点度愈高，网络直径就愈小
        全连接网络
          网络直径为1
      循环移数网络
        环上每个结点到所有与其距离为2的整数幂的结
点之间都有一条链路（网络直径为2）
      树形和星形
        结构参数
          最大结点度：3
          直径：2(k-1)
          等分宽度b=1
      星形
        结构参数
          •最大结点度：N－1
          •直径：2
          •等分宽度
        •可靠性较差，中心结点出故障，整个系会瘫痪
      胖树形
        叶节点到根节点链路（通道宽度）逐渐增多
      网格形和环网形
        网格形
          一个规模为N=n×n的2维网格形网络
            内部结点的度d=4
            边结点的度d=3
            角结点的度d=2
            网络直径D= 2（n-1）
            等分宽度b=n
          一个由N=n^k 个结点构成的k维网格形网络（每维n个结点）
            内部结点度d=2k
            网络直径D=k(n-1)
        Illiac网络
          一个规模为n×n的Illiac网络
            所有结点的度d=4
            网络直径D=n-1
              直径只有纯网格形网络直径的一半。
            等分宽度：2n
          把2维网格形网络的每一列的两个端结点连接起来，再把每一行的尾结点与下一行的头结点连接起来，并把最后一行的尾结点与第一行的头结点连接起来。
        环网形
          一个n×n的环网形网
            结点度：4
            网络直径：
            等分宽度b=2n
          把2维网格形网络的每一行的两个端结点连接起来，把每一列的两个端结点也连接起来
          将环形和网格形组合在一起，并能向高维扩展
      超立方体
        n-立方体由
          对称
          2^n个结点构成
          直径：n
          节点度：n
      带环立方体 （简称3-CCC）
        3-立方体的每个结点换成一个由3个结点构成的环而形成
          网络规模：N=3×2^3=24
          网络直径：7
          等分宽度: 4
        带环k-立方体（简称k-CCC）
          k个结点构成的环取代k-立方体中
的每个结点
          网络规模：N=k×2^k
          网络直径：
          等分宽度为b=N/（2k）
    动态互连网络
      总线结构网络
        由一组导线和插座构成，经常用来实现计算机系统中处理机模块、存储模块和外围设备等之间的互连
          每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送
          多个功能模块之间的争用总线或时分总线
          结构简单、实现成本低、带宽较窄
        一种由总线连接的多处理机系统
          Ø 系统总线与处理机、存储模块和外围设备相连，处理机能分时访问总线。
          Ø 每台处理机有局部catch。通过请求访问全局存储器。
          Ø 多请求下由总线仲裁逻辑将总线分配给一个请求。
          Ø 存在总线和共享存储器两大瓶颈。
          Ø 总线复杂性由总线上连接的分接头数n与数据通路宽度w的和w+n决定
        解决总线带宽较窄问题
          多总线
            为不同的功能设置专门的总线
            重复设置相同功能的总线
          多层次总线
            按层次的架构设置速度不同的总线,使得不同速度的模块有较适合的总线连接。
      多级网络(MIMD和SIMD计算机)
        构成
          通用结构
            由a×b开关模块和级间连接构成的通用多级互连网络结构
            每一级都用了多个a×b开关
              a个输入和b个输出
              在理论上，a和b不一定相等，然而实际上a和b经常选为2的整数幂，即a＝b＝2k，k≥1
              相邻各级开关之间都有固定的级间连接
          2×2开关
          控制方式
            级控制
              每一级的所有开关只用一个控制信号
控制，只能同时处于同一种状态
            单元控制
              每一个开关都有一个独立的控制信
号，可各自处于不同的状态。
            部分级控制
              第i级的所有开关分别用i＋1个信
号控制，0≤i≤n－1，n为级数
          级间互连模式
            均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等
        多级立方体网络
          特点
            采用二功能（直送和交换）的2×2开关
            当第i级（0≤i≤n-1）交换开关处于交换状态时，实现的是Cubei互连函数
            一个N输入的多级立方体网络有log2N级，每级用、N/2个2×2开关模块，共需要log2N×N/2个开关
          STARAN网络
            采用级控制时，所实现的是交换功能
            采用部分级控制时，则能实现移数功能
          间接二进制n方体网络
            采用单元控制，具有更大的灵活性
        Omega网络
          每级由n/2个4功能的2×2开关构成
          级间互连采用均匀洗牌连接方式
          一个N输入的Omega网络
            有log2N级，每级用N/2个2×2开关模块，共需要Nlog2N/2个开关。
            每个开关模块均采用单元控制方式。
            不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接。
      交叉开关网络
        单级开关网络
          Ø 交叉点开关在对偶节点(源，目的)之间动态连接
          Ø 一个n×n的交叉开关网络，可以无阻塞地实现n!种置换。
          Ø 一个n×n的交叉开关网络，需要n2 套交叉点开关及大量连线
        多处理机中处理机-存储器间的交叉开关网络
          Ø 可构成共享存储型多处理机,支持并行(或交叉)存储器访问
          Ø 每个存储模块一次只满足一台处理机的请求。每列只接通一个交叉点开关
          Ø 为支持并行（或交叉）存储器访问，允许每台处理机同时访问不同的存储模块。即同一行中接通多个交叉点开关
        向量并行处理机
          采用大型交叉开关网络。PE为处理机，CP代表控制处理机
          网络中每一行和一列只能接通一个交叉点开关。交叉开关实现处理机之间的置换连接（一对一）
          n*n交叉开关网络一次最多可连通n个(源，目的)处理机对
    消息传递机制
      消息寻径方案
        消息的格式
          消息
            节点之间通讯的逻辑单位
          包
            含有寻径地址的基本单位，包含一个标识数（ID）
          片
            通路所能处理的最小单位
      信息传递方式
        线路交换
          传输时延
            L：信息包的长度（位数）
            Lt ：建立路径所需的小信息包的长度
            D：经过的中间结点个数
            B：带宽
            当L>>Lt T ≈ L/B时，时延与结点数无关
        分组交换
          存储转发
            包经过的每个中间结点都要设置一个包缓冲器。当一个包到达某个中间结点时，该结点先把这个包全部存储起来。
            在出口链路可用、而且下一个结点的包缓冲器也可用的情况下，传递给下一个结点。
            传输时延
              • L为消息包的长度
              • 网络时延与源和目的地距离成正比
              D：经过的中间结点个数
              B：带宽
          虚拟直通
            只要接收到寻径信息（头部），即进行路由选择
            如果结点的输出链路空闲，包立即转送到下一个结点。如果整个通路都空闲，包直达目的结点，如同线路交换
            如果没有空闲链路时或出现寻径阻塞时，须将整个信息全部存储在寻径结点中。等同存储转发
            传输时延
              Lh是信息包寻径头部的长度
          虫孔(wormhole)方式
            将包分为片，使信息包中各片的传送按
流水方式进行
              当一个结点把头片送到下一个结点后，就可以把后面的各个片也依次送出
            当输出通路忙时，结点是把一个片存储到缓冲器中
            当消息的一片被阻塞时，整个消息的所有片都
将被阻塞在所在结点，占用了结点资源
            传输时延
              Lf：“片”的长度
              Tf：片经过一个结点所需时间，L>>Lf×D
      虚拟通道
        两个结点间的逻辑链接，由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成
      死锁
        路由死锁
          缓冲区或通道上的循环等待
        迎面死锁
          两个结点间都向对方发送消息，两个结点之间抢占共享物理链路而导致死锁
      流控制策略
        包冲突的解决
          两个包到达同一个结点时，可能都请求同一个接收缓冲器或者输出通道，这时须对两个请求进行仲裁
          解决方案
            后一个包暂存(在缓冲区)
              要求结点中有一个大的缓冲器来存放整
个信息包
            阻塞后一个包
            丢弃后一个包
            后一个包绕道
        寻径算法（路径选择）
          确定性寻径
            X-Y寻径算法（用于二维网络）
            E-立方寻径算法（用于超立方互连网络）
            通信路径完全由源结点地址和目的地址来决
定
          自适应寻径
            通信路径要根据资源或者网络的情况来选择
          选播和广播寻径算法
            单播
            选播
            广播
            会议
  MIMD(多处理机)
    并行向量多处理机（PVP）
      共享存储器
    大规模并行处理机（MPP)
      处理器数目很多的多处理机系统。计算机模块为一个结点。通过专门结点接口连接到互连网络上。
      每个结点有一台处理机、局部Catch、存储器、结点接口(NIC)，甚至I/O设备，通过结点内总线相连。
    工作站机群(COW)
      多个完整的计算机，通过商品化互连网络相连
      每个节点由一台处理机、局部Catch和局部存储、主存总线、I/O总线的桥（BRIDGE）及结点接口(NIC)组成。
      机群系统中的主机和网络可以同构，也可以异构
    集中式共享存储器多处理机(SMP)
      多个处理器共享一个存储器
      Cache的一致性问题
        Cache功能
          共享数据的迁移
            把远程共享数据的拷贝一份，迁入
本地Cache供处理器使用
          共享数据的复制
            把多个处理器需要的共享数据在各
本地Cache中存放一个副本
        Cache一致性协议
          目录式协议
            协议内容
              主存中设置一个目录表，存放每个数据块(行)状态位和若干指针位（位向量），指针位对应处理机Cache
                状态位指示数据块状态
                指针位指出哪些处理机Cache中有数据块副本
                  位向量长度与处理器的个数成正比
                  由位向量指定的处理机的集合称为共享集S。
              一个处理机访问本身Cache时，根据目录表，有选择地通知存有数据块的处理机Cache
            存储块的状态
              未缓冲
                该块尚未被调入Cache(所有处理器的Cache中都没有这个块的副本)
              共享
                该块在一个或多个处理机上有这个块的副
本，且副本与存储器中的该块相同
              独占
                仅有一个处理机有这个块的副本，且该处理机已经对其进行了写操作，其内容是最新的，而存储器中该块的数据已过时
                这个处理机称为该块的拥有者
              宿主结点
                对于任何一个数据块，都可以快速地在唯一的一个处理机位置（宿主结点）中找到记录该块状态的相关信息。这使一致性协议避免了广播操作。
              本地结点
                发出访问请求的结点 , 假设访问的地址为K
              远程结点
                拥有存储块副本的结点.
            消息传递
              本地结点发给宿主结点（目录）的消息
                RdMiss（P，K）
                  处理机P读取地址为K 的数据时不命中，请求宿主结点提供数据（块），并要求把P加入共享集。
                WtMiss（P，K）
                  处理机P对地址K进行写入时不命中，请求宿主结点提供数据，并使P成为所访问数据块的独占者
                Invalidate（K）
                  向所有拥有相应数据块副本（包含地址K）的远程Cache发Invalidate消息，作废这些副本。
              宿主结点发送给本地结点的消息
                DReply（D）
                  把数据D返回给本地Cache。
              宿主结点（目录）发送给远程结点的消息
（目录控制器有选择地向远程结点发出相应的消息）
                Invalidate（K）
                  作废远程Cache中包含地址K的数据块。
                Fetch（K）
                  从远程Cache中取出包含地址K的数据块(到宿主结点)。并把远程Cache中那个块的状态改为“共享”
                Fetch& Invalidate （K）
                  从远程Cache中取出包含地址K的数据块到宿主结点。并作废远程Cache中的那个块。
              远程结点发送给宿主结点的消息
                WtBack（K，D）
                  把远程Cache中包含地址K的数据块D写回到宿主结点。远程结点对宿主结点“取数据”或“取/作废”消息的响应。
            目录结构
              全映象目录
                每一个目录项都包含一个N位的位向量，对应N个处理机个数
              有限映象目录
                限制同一数据块X在所有Cache中的副本总数
                新的Cache存放X时，原有某个Cache放弃存放X
              链式目录
                用一个目录指针链表来表示共享集合。主存只存一个指针位，指向一个处理机Cache 。
                最后一个Cache（指针位指明“链路终止(CT)”）
          监听式协议
            协议内容
              Cache通常连在共享存储器的总线上
              Cache包含物理存储器中数据块的拷贝，也保存
着各个块的共享状态信息。
              当某个Cache需要访问时，它会把请求放到
总线上广播出去
              其他Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。如果有，就进行相应的操作。
            技术关键
              处理器之间通过一个可以实现广播的互连机制（总线）
              Cache的标识（tag）可直接用来实现监听
            Cache
              发往总线的消息
                RdMiss——读不命中
                WtMiss——写不命中
                Invalidate ——作废，通知其他各处理器作废其Cache中的副本
                需要通过总线找到相应数据块的最
新副本，然后调入本地Cache中
              修改位
                记录该块是否比修改过，作废一个块只需将其有效位置为无效
              共享位
                1”：该块是被多个处理器所共享
                “0”：仅被某个处理器所独占
              状态
                无效（简称I）
                  Cache中该块的内容为无效。该块尚未在本Cache中，发生不命中 。
                共享（简称S，只读）
                  在一个或多个处理器中都有副本。且与存储器中相应的块相同
                已修改（简称M，可读写）
                  块中的内容是最新的，系统中唯一的最新副本）
            Cache状态转移
              响应来自处理器的请求
              响应来自总线的请求
        解决方案
          写作废
            在处理器对某个数据项进行写入之前，作废其它的副本，以保证它拥有对该数据项的唯一的访问权
          写更新
            当一个处理器对某数据项进行写入时，（通过广播）更新其它Cache中所有对应于该数据项的副本。
          性能比较
            写作废所消耗的总线和存储器带宽较少，多在基于总线的多处理机中采用
            写更新协议的延迟时间较小。适合在处理器个数不多的多处理机中采用
      存储器的一致性
        如果对存储器中某个数据项的任何读操作均可得到其最新写入的值，则这个存储系统是一致的
          直到所有的处理器均看到了写的结果，这个写操作才算完成
          处理器的任何访存操作均不改变写的顺序
    分布式存储器多处理机(DSM)
      存储器系统结构
        共享地址空间(每个结点存储器统一编址)
          物理上分离的所有存储器作为统一的共享逻辑空间进行编址。
          任一处理器可访问共享空间中任何一个单元（如果有访问权）
          不同处理器上的同一个物理地址指向的是同一个存储单元。
        独立的地址空间(结点中的存储器编址相互独立)
          系统的地址空间由多个独立的地址空间构成
          每个结点的存储器只能由本地处理器访问，远程处理器不能直接进行访问。
          每一个处理器-存储器模块是一台单独的计算机
      通信机制
        共享存储器通信机制
          共享地址空间的计算机系统采用
          处理器间通过访存类指令(load和store)对相同存储器地址进行读/写来实现
          优点
            与对称式多处理机使用的通信机制兼容。
            当通信数据量较小时，通信开销较低，带宽利用较好。
            可通过Cache技术来减少远程通信的频度，延迟以及对共享数据的访问冲突。
            易于编程和简化编译器
          在共享存储器上支持消息传递相对简单
        消息传递通信机制
          多个独立地址空间的计算机采用
          通过处理器间显式地传递消息来完成通信这些消息请求进行某些操作或者传送数据
          优点
            硬件较简单。
            显式通信:清楚何时发生通信以及通信开销是多少。
            编程者通过重点注意并行计算的主要通信开销，有可能开发出结构更好、性能更高的并行程序。
          在消息传递的硬件上支持共享存储器相对困难
  SIMD(阵列处理机)
    操作模型
      一个控制部件CU同时管理多个处理单元PE
      CU对指令进行译码，把指令播送到各处理单元
      所有处理单元均接收并执行从CU广播来的同一条
指令，但所操作的对象是不同的数据(所有处理单元同时对不同的数据进行相同的操作)
      控制器实质上是一台标量处理机，为完成I/O操作
以及操作系统的管理，尚需一个前端机。各处理单元间通讯可通过控制存储器完成
      互连网络设计是阵列机的重点和特点。互连网络
实现处理单元间连接.
    阵列处理机＝（N，C，I，M，R）
      N：机器的处理单元（PE）数。
      C：控制部件直接执行的指令集，包括标量指令
和程序流控制指令
      I：由CU广播至所有PE进行并行执行的指令集。
        包括算术运算、逻辑运算、数据寻径、屏蔽以及其他由每个PE对它的数据所执行的局部操作。
      M：屏蔽方案集
        将PE划分成允许和禁止操作两种工作模式。
      R：数据寻径功能集
        说明互连网络中PE间通信需要的各种设置模式。包括置换、广播、选播、多种循环和移数操作
    屏蔽方案
      地址屏蔽方案
        地址由0,1,X三字符组成 ( X 相当于通用符).由地址屏蔽字直接指出活动的PE
      数据条件屏蔽
        根据PE中执行内容(数据而非地址)或条件进行屏蔽，直接决定PE的“活动”状态。
    基本结构
      分布式存储器的阵列机
        结构
          有多个相同的处理单元PE，PE有各自的本地存储器LM。
          指令的执行顺序基本上是串行进行的
          处理机－处理机结构
        主机
          安装操作系统，程序的编辑、编译和调试及程序和数据的装入(控制存储器)
        控制部件(指令译码)
          标量指令
            直接由标量处理机执行。
          向量指令
            通过广播总线播到所有PE中并行执行。
          通过执行程序来控制数据寻径网络
        程序所需的数据集
          经划分后通过数据总线分布存放到各PE的本地存储器LM
        PE
          PE间通过数据寻径网络以一定方式互相连接
            各种阵列处理机的主要差别在于数据寻径网络的
不同
          PE的同步是在控制部件的控制下由硬件实现
      共享存储器的阵列机
        结构
          集中设置存储器
            共享多体并行存储器SM通过对准网络与各处理单元PE相连。
            存储模块的数目等于或略大于处理单元的数目。
          适合处理单元数目不太多的情况
          处理机－存储器结构
    Illiac Ⅳ阵列（闭合螺线阵列）（分布式存储器）
      由64个处理单元（PE）、64个本地存储器（PEM）和存储器逻辑部件（MLU）组成
        每个PE和PEM对看成是一个处理部件PU
        PE和PEM之间经过存储器逻辑部件MLU相连。
      一般情况，n×n个单元组成的阵列中，任意两个处理单元之间的最短距离不会超过（n－1）步。
      阵列控制器CU
        指令流控制和译码，包括执行一整套标量指令；
        向各处理单元发出执行数组操作指令所需的控制信号；
        产生并向所有处理单元广播公共的地址部分；
        产生并向所有处理单元广播公共的数据；
        接收和处理由各PE计算出错、系统I/O操作以及B6700所产生的陷阱中断信号。
      信息通路（阵列控制器CU与处理单元之间）
        CU总线
          把本地存储器（PEM）中分散存放的指令或数据送往阵列控制器CU
        公共数据总线CDB
          向本地存储器（PEM）广播公共数据
        模式位线
          将PE的状态传送至CU
        指令控制线 （大约有200根
          控制PE
      输入输出系统
        磁盘文件系统DFS
        I/O系统
          输入/输出开关IOS
            作DFS和PEM之间缓冲，平衡两边不同数据宽度。
          控制描述字控制器CDC
            对阵列控制器CU的I/O请求进行管理
          BIOM （I/O缓冲存储器）
            在DFS和B6700之间，是为了取得二者之间传送
带宽上的匹配
        B6700管理计算机
          管理全部系统资源，完成用户程序的编译或汇编
          进行作业调度、存储分配、产生I/O控制描述字送
至CDC、处理中断、提供操作系统所具备的其他服务
    BSP计算机（共享存储器）
      并行处理机
        包含16个算术单元AE、由17个存储体组成的并行存储器和两套对准网络（分别为入口和出口对准网络）
        由17个存储体组成并行存储器 可以实现无冲突访问
      控制处理机
        控制并行处理机，提供与系统管理机相连的接口
          标量处理单元
          并行处理机控制器
          指令/控制存储器
          控制维护单元
      文件存储器系统
        文件存储器
        文件存储控制器
    阵列处理机与流水线向量处理机对比
      阵列处理机
        阵列处理机用大量处理单元对各分量进行运算，各单元同时进行相同操作，依赖空间并行技术，并行化程度高。潜力大
        阵列处理机每个处理单元要负担多种处理功能
        互连网络是阵列处理机的特点
        阵列处理机有固定结构，与一定算法相联系
      向量处理机
        向量处理机基于流水线技术和时间并行性或并发性。
    典型算法
      tong'g
IS：指令流
DS：数据流
CS：控制流
CU：控制部件
PU：处理部件
MM和SM：存储器
k ——控制器数目；
k′——控制器流水线中控制部件的数目；
d ——ALU(或PE)数目；
d′——指令流水线中的ALU部件的数目；
w ——ALU或PE的字长；
w′——操作流水线中基本逻辑线路数目。
IN----程序的指令总数 ；
TE--- 执行程序的时间 ；
t---时钟周期；
f---频率；
CPI ----程序中指令的平均时钟周期数。
IFN--程序中的浮点运算次数；
TE---执行程序的时间
n：任务数
Tk：处理完成n个任务所用的时间
Ts：不用流水线所用的时间（顺序执行）
Tk ：使用K段流水线后所用的时间
Ts ：流水线的建立时间。流水线开始工作需要准备时间。
Te ：第一个（对）向量元素通过流水线的时间 。
Tc ：流水线的时钟周期时间
n : 向量长度
IFN ——程序中浮点运算总次数
Tp—— 执行程序时间
• T(i)vp ：第i个编队的执行时间
• m：编队的个数
1 ) 与分段有关
2) 向量长度有关 mnTc （与分段无关)
粗粒度并行：进程、任务、程序一级的并行处理
P：发出请求的处理机编号
K：所要访问的地址