系统结构复习

复习

考试题型

第一章 计算机系统结构导论

• 计算机系统由运算器 控制器 存储器 输入设备 输出设备五个不部件组成, 其中运算器和控制器合称中央处理器
• 1.3.1 七层, 五层, 虚拟机, 透明性, 系列机, 可移植, 兼容
  

  • 硬件: $CPU+MEM+I/O+BUS+外部设备$
    
  • 虚拟计算机就是由软件实现的机器
    
  • 计算机系统的功能

  
  

附: 计算机系统功能模型(洋葱模型)

• 系统结构:指计算机系统中对各级之间界面的定义及上下级的功能分配
• 透明性:一是指确实存在, 二是指无法监测和设置
• 计算机系统结构 , 组成 和实现 三者之间的联系
  

  系统结构是计算机系统软硬件界面
  计算机组成是计算机系统的逻辑实现
  计算机实现是计算机组成的物理实现

• 系列:系列机概念指先设计好一种系统结构, 而后就去按这种系统结构设计它的系统软件.按器件状况和硬件技术研究这种系统结构的实现方法. 并按照速度, 价格等不同要求, 分别提供不同速度, 不同配置的各种机器. 系列机必须保重用户看到的机器属性一致
• 兼容:指同一个软件可以不加修改地运行于系统结构相容的各个机器上

• 计算机系统设计的定量原则:

  1. 加快经常性事件的速度
     这是计算机设计中最重要且应用最广泛的设计原则. 使经常性事件的处理速度加快能明显提高整个系统的性能.

  2. 阿姆道定律:
     

     $$加速比 = \frac{采用改进措施后的性能}{未使用改进措施前的性能} = \frac{未采用改进措施前执行某任务的时间}{ 采用改进措施后执行某任务的时间}$$

     $T_n$: 改进后的执行时间
     $T_0$: 改进前的执行时间
     $F_e = \frac{可改进部分占用时间}{改进前整个任务直时间}$
     $S_e = \frac{改进前改进部分执行时间}{改进后改进部分执行时间}$

     • 改进后整个任务的执行时间
       $$T_n = T_0\left[{(1-F_e)}+\frac{F_e}{S_e}\right]$$
     • 改进后整个系统的加速比
       $$S_n = \frac{T_0}{T_n} = \frac{1}{(1-F_e)+\frac{F_e}{S_e}}$$
  3. CPU性能公式:
     $$CPI = \sum_{i=1}^n{CPI_i\times\frac{I_i}{I_c}}$$
     $\frac{I_i}{I_c}$表示i指令在程序中所占的比例

• SISD/SIMD/MISD/MIMD

• SISD(单指令流单数据流): 大多数串行计算机
• SIMD(单指令流多数据流): 以并行处理机(阵列处理机)为代表
  

  在同一个控制部件管理下, 有多个处理单元PU, 所有PU均接收从控制部件传来的同一条指令, 但操作对象却来自不同数据流的数据组, 共享存储器的子系统可以有多个模块, 这类计算机还包括相联处理机. 从处理数据的并行性角度分析, 开可分成位片式(位串行字并行)和字片式(位.字全并行)
  

• MISD(多指令流单数据流): 没有实用价值

• MIMD(多指令流多数据流): 大多数处理机系统和多计算机系统可以划归这一类结构

• 从系统结构角度提高系统性能

  1. 优化算法,用较少的指令完成同样的任务
  2. 在系统结构中增加硬件辅助部件
  3. 多条指令并发执行

• 三类计算机系统

  • 单处理系统
  • 并行与多处理系统
  • 分布式处理系统

第二章 计算机系统结构的合成

• 指令优化

  • 平均码长计算
    $$L =\sum P_il_i$$
    $P_i:$使用频率(就是题目给出的那几个数, 如果他们和刚好为1 的话)
    $l_i:$第i条指令的码长

• 数据表示: 能够由硬件直接辨认的数据类型

• 浮点数的下溢处理:

  截断法:简单的将下溢部分截去(舍入法)
  舍入法:被截尾数为1进1. 平均误差比截断法小, 最大误差小于一半
  恒置"1"法:和截断法一样不需要额外处理时间, 最大误差比截断法还大
  ROM或PLA舍入法

• 存储系统的容量数量级和性能变化很大, 但三项基本要求--大容量 高速度 低成本始终未变

• 存储器容量,速度,与价格的关系
  

  $$S_m = Wlm$$

  $S_m: 存储容量$
  $W: 存储器字长$
  $l: 存储器字数$
  $m: 并行工作的存储器个数$

• 图2.20 存储系统的层次结构

• 存储系统的性能参数:

$c_i$ : $M_i$的每位价格
$T_{A_i}$ : $M_i$的访问时间
$S_{M_i}$ : $M_i$的存储容量,
则$M_{i+1}$与$M_i$存在如下关系:

每位价格: $c_i>c_{i+1}$
访问时间: $T_{A_i} < T_{A_{i+1}}$
存储容量: $S_{M_i} < S_{M_{i+1}}$

第三章 存储系统结构

• 地址映像与变换

  全相联
  组相联
  直接映射

• 替换算法

  随机算法
  先进先出算法
  近期最少使用算法
  优化算法

第四章 流水线结构

• 流水线处理机(4.1.3)

• 线性流水线技术指标:

  • 吞吐率$(TP)$

    • 单位时间内流水线能够处理的任务数(指令数)或流水线输出的结果的数量
    • 最大吞吐率: 流水线到达稳定状态后得到的吞吐率
      各段时间相等
      $$TP_{max} = \frac{1}{\Delta t_0}$$
      各段时间不等
      $$TP_{max} = \frac{1}{max\{\Delta t_i\}}$$
      $\Delta t_i$: 第$i$个功能段所花的时间
      即: 最大吞吐率取决于流水线中最慢的那个功能段
    • 实际吞吐率
      各段时间相等
      $$TP=\frac{n}{T}=\frac{TP_{max}}{1+\frac{m-1}{n}}$$
      各段时间不等
      $$TP=\frac{n}{\sum_{i=1}^m\Delta t_i+(n-1)\Delta t_j}$$
      $n$: 任务条数
      $m$: 每个任务执行 段数
      $\Delta t_j$: 最慢的一段时间

  • 加速比$(S)$

    • m段流水线的速度与非流水线的速度之比
      各段时间相等:
      $$S = \frac{T_{非流水}}{T_{流水}} = \frac{mn\Delta t_0}{(m+n-1)\Delta t_0} = \frac{m}{1+\frac{m-1}{n}}$$
      各段时间不相等
      $$S=\frac{n\bullet\sum_{i=1}^m \Delta t_i}{\sum_{i=1}^m \Delta t_i+(n-1)\Delta t_j}$$

  • 效率$(E)$

    • 流水线上各段有通过时间和排空时间, 即并不都是满负荷工作的, 流水线上的设备的利用效率就是效率(Efficiency)
      各段时间相等
      每段的效率$e_i = \frac{n \Delta t_0}{T} = \frac{n}{m+n-1}$
      $$E = \frac{e_1+e_2+...+e_m}{m} = \frac{me_0}{m} = \frac{mn\Delta t+0}{m}$$
      式子看不懂没关系
      $$E = \frac{n个任务实际占用的面积(时间)}{m个段和T时间所围成的面积(时间)}$$

• 流水线相关处理(4.4)

• 超标量处理机: 超标量机器是为改善标量指令执行性能而设计的机器, 是高性能通用处理机发展的一个方向, 其本质是在不同流水线中执行不相关指令的能力
• P180公式

第五章 并行处理机

• 并行性:在同一时刻或同一时间间隔内完成两种或两种以上的性质相同或不同 的工作,只在时间上互相重叠, 君存在并行性, 并行性又可分为同时性和并发性

• 并行性等级从低到高划分为:

  • 从执行角度

    1. 指令内部并行, 即指令内部的微操作之间的并行
    2. 指令间并行, 即并行执行两条或者多条指令
    3. 任务级或过程级并行, 即并行执行两个或多个任务(程序段)
    4. 作业或程序级并行, 即在多个作业或程序间并行

  • 从处理数据角度

    1. 字串位串
    2. 字串位并
    3. 字并位串
    4. 字并位并

• 提高并行性的措施

  • 时间重叠
  • 资源重复
  • 资源共享

• 并行处理机也称SIMD计算机

• 目前的SIMD计算机几乎都是基于分布式存储器结构的系统, 主要差别在于互联网络不同
  

  SIMD计算机的主要特点
  

  • SIMD计算机利用大量PE对向量的各分量同时进行计算, 可获得很高的处理速度, 所依靠的并行措施是资源重复而不是时间重叠
  • SIMD计算机最有特色的组成部分是它的互联网络(ICN)
  • SIMD计算机适合于高速数值计算, 类同于流水线向量处理机
  • SIMD计算机除向量运算速度以外, 整个系统的实际有效速度还在相当程度上取决于标量运算和编译过程的开销
  • SIMD计算机基本上是一台向量处理的专用计算机, 它必须和一台高性能的单处理器主机配合工作, 有主机承担系统的全部管理功能.

• 共享式存储器结构(5.2.2)
• 互连网络基本概念(5.3.1)
  
  • 互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络, 用于计算机系统内部多个处理机或多个功能部件之间的相互连接
  • 衡量互连网络性能主要取决于结点的度 网络直径 网络带宽 可靠性 成本 等
  • 设计互联网络准则
    

• 单级互连函数(P204)

• 基本互联函数及函数表达式

  • 恒等互联网络 : 相同编号的输入端和输出端一一对应
    $$I(X_{n-1}X_{n-2}...X_1X_0) = X_{n-1}X_{n-2}...X_1X_0$$
  • 交换互联网络 : 二进制地址编码中第0位位值不同的输入端与输出端互连
    $$E(X_{n-1}X_{n-2}...X_1X_0) = X_{n-1}X_{n-2}...X_1\overline{X_0}$$
  • 三维立方体单级互连网络 : Cube函数下标表示的输入端和输出端只在其位互为反码, 其他各位相同
    
    • 最大寻径距离: n
      $$Cube_i(P_{n-1}P_{n-2}...P_i...P_1P_0)=P_{n-1}P_{n-2}...\overline{P_i}...P_1P_0$$
  • 加减2单级互连网络
  • 混洗单级互连网络
    将输入端分成相等的两半, 前一半和后一半按序一个隔一个地从头到尾一次与输出端相连, 如洗扑克牌
    
    • 最大寻径距离: 2n-1
      $Shuffle(P_{n-1}P_{n-2}...P_1P_0) = P_{n-2}...P_1P_0P_{n-1}$

• 静态互联网络:指各结点间有专用的链路, 且在运用中不能嫩改变的网络

• 动态互联网络:动态互联网络可以达到多种用途和通用目的, 它能根据程序要求实现所有通信模式, 它使用开关或仲裁器以提供动态连接特性
• 多级互联网络>多立方体网络(P218) + 多级混洗交换网络(P221)

第六章 多处理机系统

• 多处理机系统的定义:

  1. 包含两个或两个以上功能大致相同处理器
  2. 所有处理器共享一个公共内存
  3. 所有处理器共享IO通道 控制器 和外围设备
  4. 整个系统由同意的操作系统控制, 在处理器和程序之间实现作业, 任务,程序段,数组和数组元素之间的全面并行程序

• 优点

  1. 很高的性能价格比
  2. 很高的可靠性
  3. 很高的处理速度
  4. 很好的模块化

• 全面并行是多处理机系统最根本的特征, 统一操作是决定因素
• 多处理机软件--> OPENMPI编程
• OPENMP 示例程序

#include <omp.h>
#include <stdio.h>
int main()
{
    int nthreads;
    int tid;
    omp_set_num_threads(8); //设置线程数
    //编译制导语句, 按多线程执行, 每个线程有自己的nthreads 和 tid
    #pragma omp prarallel private(nthreads,tid)
    {
        tid = omp_get_thread_num();//当前线程的tid
        printf("Hello World from Thread %d \n", tid);
        if(tid == 0)
        {
            nthreads = omp_get_num_threads();//总线程数
            printf("Number of threads is %d \n", nthreads);
        }
    }
}

• 利用OPENMP进行矩阵计算

#include <stdio.h>
#include <omp.h>
#include <time.h>
//两个矩阵相乘的传统方法 
void comput(float *A, float *B, float *C){
  int x, y;
  for(y=0; y<4; y++){
    for(x=0; x<4; x++){
      C[4*y+x] = A[4*y+0]*B[4*0+x]
                +A[4*y+1]*B[4*1+x]
                +A[4*y+2]*B[4*2+x]
                +A[4*y+3]*B[4*3+x];
    }
  }
}
int main(){
  double duration;//执行时间
  clock_t s,f;
  int x = 0;
  int y = 0;
  int n = 0;
  int k = 0;
  float A[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
  float B[] = {0.1f,0.2f,0.3f,0.4f,0.5f,0.6f,0.7f,0.8f,0.9f,0.10f,0.11f,0.12f,0.13f,0.14f,0.15f,0.16f}
  float C[16];
//------------------串行计算----------------------------
  s = clock();//计时开始
  for(n=0; n<1000000; n++){
    comput(A,B,C);
  }
  f = clock();//计时结束
  duration = (double)(f-s)/CLOCK_PER_SEC;
  printf("s---1,000,000: %f\n",duration);
  for(y=0; y<4; y++){
    for(x=0; x<4; x++){
      printf("%f ",C[y*4+x]);
    }
    printf("\n");
  }
  printf("----------------------------------------------\n");
//------------------------------并行执行--------------------
//===== 1. 一条线程  相当于串行  ============================
  s = clock();
  #pragma omp parallel for
  for (n = 0; n<1000000; n++){
    comput(A, B, C);
  }
  f = clock();
  duration = (double)(f - s) / CLOCKS_PER_SEC;
  printf("p1-  1,000,000 :%f\n", duration);
//===== 1. 两条线程  ============================
  s=clock();
  #pragma omp parallel for
  for (n = 0; n<2; n++){//CPU是核线程的
    for (k = 0; k<500000; k++){//每个线程管个循环
      comput(A, B, C);
    }
  }
  f = clock();
  duration = (double)(f - s) / CLOCKS_PER_SEC;
  printf("p2- 1,000,000:%f\n", duration);
//===== 1. 四条线程  ============================
  s = clock();
  #pragma omp parallel for
  for (n = 0; n<4; n++){ //CPU是核线程的
    for (k = 0; k<250000; k++){//每个线程管个循环
      comput(A, B, C);
    }
  }
  f = clock();
  duration = (double)(f - s) / CLOCKS_PER_SEC;
  printf("p3- 1,000,000:%f\n", duration);
//-----------------------------------------------------------
  for (y = 0; y<4; y++){
    for (x = 0; x<4; x++){
      printf("%f,", C[y * 4 + x]);
    }
    printf("\n");
  }
  return 0;
}

第十一章 现代计算机系统结构的发展

• 集群(Cluster)计算机能够以较短 的研制周期,集成最新技术,汇集多台计算机的力量, 达到较高的性能价格比, 其技术发展在国际上受到重视.
  

  • 它通过高速互联网络吧通用计算机(如高档计算机,工作站或pc)连接起来, 采用消息传递机制(MPI PVM等)向最终用户提供单一并行编程环境和计算机资源, 因此它通常也称为"计算机群", "工作站群", "工作站网络" 或"网络并行计算"等`