计算机系统结构（1月28日）

cache结构和性能评价

CPU：Average time required per instruction

memory:quantity and organization affects data availability

Internal Communication & IO:Speed and organization affects data availability

Operating system efficiency: CPU devotes less time to dense OS code;OS manages tasks/threads to keep the CPU(CPUs) busy

compiler：converts high level language to machine code; optimized code runs faster

special hardware:dedicated processors(graphics,memory management) 异构多核，功耗，特殊需要

Application code:Efficient algorithms, data structures, parallelization

1990年以前：要求计算机语言

1、尽可能接近自然语言，semantic gap；2、编译调度能力差；3、memory很昂贵；4、implication for machine language

delay slot

指令系统的优化设计

优化指令系统设计的3个阶段：

CISC：复杂指令系统，60年代至70年代中期

RISC：精简指令系统，70年代后期至现在

VLIW：80年代初期至现在

关键在软硬件的功能分配，系统的综合性能，时间与空间，执行、编译、编写时间

复杂指令系统计算机 CISC Complex Instruction Set Computer

方法：用一条指令代替一串指令

增加新的指令

增强指令功能，设置功能复杂的指令

增加寻址方式

增加数据表示方式

优化的途径：

面向目标代码

面向高级语言

面向操作系统

精简指令系统计算机：

RISC（Reduced Instruction Set Computer）

只保留功能简单的指令

功能较复杂的指令用软件实现

提高流水线效率

超长指令字：

VLIW（Very long Instruction Word）

一种显式指令级并行指令系统

二维程序结构

指令级并行度高

RISC指令系统

二八法则

在CISC中，大约20%的指令占据了80%的处理机执行时间

例如：8088处理机的种类指令大约100种

前11种（11%）指令的使用频度已经超过80%

前8种（8%）指令的运行时间已经超过80%

前20种（20%）指令：使用频度达到91.1%；运行时间达到97.72%

其余80%的指令：使用频度只有8.9%,2.28%的处理机运行时间

RISC的定义与特点：

卡内基梅隆大学论述RISC的特点如下：

1、大多数指令在单周期内完成

2、LOAD/STORE结构

3、硬布线控制逻辑

4、减少指令和寻址方式的种类

5、固定的指令格式

6、注重编译的优化

90年代初，IEEE的Michael Slater对RISC描述：

（1）RISC为提高流水线效率，应具有下述特征：

简单而统一格式的指令译码

大部分指令可以单周期执行完成

只有LOAD和STORE指令可以访问存储器

简单的寻址方式

采用延迟转移技术

采用LOAD延迟技术

（2）为使编译器便于生成优化码，应具有：

三地址指令格式，较多的寄存器，对称的指令格式

RISC微处理器：1、简单的指令集；2、简化的硬件设计；3、高级语言编译成RISC；4、所有的处理器都采用RISC结构

硬件方面：

采用硬布线控制逻辑

减少指令和寻址方式的种类

使用固定的指令格式

采用LOAD/STORE结构

指令执行过程中设置多级流水线等

软件方面：

十分强调优化编译技术的作用

RISC设计思想也可以用于CISC中：

x86处理机的CPI在不断缩小

8088的CPI大于20

80286的CPI大约5.5

80386的CPI进一步减小到4左右

80486的CPI已经接近2

Pentium处理机的CPI已经与RISC十分接近

目前，超标量处理机、超流水线处理机的CPI已经达到0.5

实际上用IPC（Instruction Per Cycle）更确切

RISC的关键技术： 1、延时转移技术；2、指令取消技术；3、指令流调整技术；4、以硬件为主固件为辅；5、重叠寄存器窗口技术

VLIW的主要特点：

1、采用显式并行指令计算（EPIC：Explicitly Parallel Instruction Computing）方式

在VLIW处理机上运行的程序是一个二维指令矩阵，每一行上的所有操作组成一条超长指令，它们之间没有数据相关、控制相关和功能部件冲突，这些指令可以在VLIW处理机上同时执行

超标量处理机和超流水线处理机通常采用隐式并行指令方式。程序是一维线性的指令序列，每条指令中一般只包含一个操作

RISC思想：LOAD/STORE

无冲突访问存储器

1、一维数组（向量）的无冲突访问存储器

按连续地址访问，没有冲突

位移量为2的变址访问，速度降低一倍

2、二维数组无冲突访问

要求：一个n×n的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问

顺序存储：按行、对角线访问没有冲突，但按列访问每次冲突

n×n二维数组无冲突访问存储方案：（P Budnik和D J Kuck提出）

并行存储体的个数m大于等于n，并且取质数，同时还要在行、列方向上错开一定的距离存储数组元素

设同一列相邻元素在并行存储器中错开d1个存储体存放，同一行相邻元素在并行存储器中错开d2个存储体存放。当m=2的2p次方+1（p为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：d1=2的p次方，d2=1

n×n数组中的任意一个元素aij在无冲突并行存储器中的体号地址和体内地址的计算公式：

体号地址：（2的p次方 i+j+k）MOD m

体内地址：i

其中：,0<=i<=n-1，0<=j<=n-1

k是数组的第一个元素a00所在的体号地址，m是并行存储体的个数，要求m大于等于n且为质数

p是满足m=2的2p次方+1关系的任意自然数

主要缺点：浪费存储单元

对于n×n数组，有（m-n）×m个存储单元浪费

主要优点：实现简单

列元素顺序存储，行元素按地址取模顺序存储

二维数组的无冲突访问存储器

规则：对于任意一个n×n的数组，如果能够找到满足n=2的2p次方关系的任意自然数p，则这个二维数组就能够使用n个并行存储体实现按行、列、对角线和反对角线的无冲突访问

实现方法：

假设aij是4*4数组中的任意一个元素，下标i和j都可以用两位二进制表示。假设i和j的高位和低位分别为iH、iL、jH和jL，则aij在无冲突并行存储器中的体号地址和体内地址如下：

体号地址：2（iL异或jH）+（iH异或iL异或jL）

体内地址：j

其中：0<=i<=3，0<=j<=3

主要优点：没有浪费的存储单元

主要缺点：在执行并行读和写操作时需要借助比较复杂的对准网络

低位高位交叉存储器

CACHE

存储系统：用软件和硬件的办法，将速度、容量和价格不同的存储器有机地结合起来，对用户看来，价格最便宜，速度最快，容量最大

存储器的性能影响到整个计算机的性能

动态RAM，通过电容保存一个值，还需要不断地刷新，需要多步访问，密度比较大，速度相对慢

静态RAM，价格昂贵，速度快，密度小，片内

时间局部性和空间局部性

关于cache和内存之间的交互

提高存储器性能方式：1、存储器系统包括寄存器、cache、内存、磁盘，整个构成一个存储系统，采取预取的技术；2、缓冲技术；3、层次存储技术（1、cache-主存构成二级存储系统；2、虚存，内存-磁盘构成的二级存储系统）

outline：

1、Memory hierarchy

2、Four Questions for Memory Hierarchy

3、Cache Performance （Reduce the miss rate; reduce the miss penalty, reduce the time to hit in the cache）

Memory hierarchy

Memory locations outside CPU and RAM: Stores data and instructions of all programs Organized by OS

Memory location outside CPU : stores all data and instructions of running programs Organized by addresses

Memory location in or near CPU: Fast access to important data and instructions from RAM Copy of RAM section

Memory location inside CPU: Fast access to small amount of information Organized by CPU

register(current data)、Cache（next few instructions and data）、Main Memory（RAM， Running Programs and Data）、Long Term Storage（All files and Data）

影响计算机性能两个因素：带宽（bandwidth，单位时间读了多少位）和延迟（latency，发出指令到执行之间的时间）

空间局部性原理：对于一个程序空间来说，程序90%的时间在访问10%的区域

时间局部性：一个数据被访问了，再被访问的概率非常大

程序的局部性、数据局部性

cache：命中率 缺失率

缺失代价

Average memory-access time = Hit time + miss rate× miss penalty（ns or clocks）

4个问题：

1、块的定位、地址映射问题

2、地址如何查找

3、cache满时，如何替换

4、写命中时怎么样，不命中时怎么样

全相联映射

直接映射：Direct-Mapped Cache：each memory address is associated with one possible block within the cache

组相联映射

Direct-Mapped example：

Conditions：32-bit architecture(word=32bits),address unit is byte;8KB direct-mapped cache with 4 words blocks

Determine the size of the Tag, Index, and Offset fields

offset （specifies correct byte within block）: cache block contains 4 words = 16 字节，= 2的4次方，offset=4bits

32-4 = 28 = size（tag）+size（index）

Index：

cache 8KB，= 2的13次幂B，而cache block 是2的4次幂

Rows in cache (1 block = 1 row): 2的13次幂/2的4次幂=2的9次幂 9bits

tag：28-9 =19bits

如何找数据？

In a direct mapped cache,Cache Block is available before hit/miss

possible to assume a hit and continue. recover later if miss

替换策略：随机、LRU（两路左右比较方便，组路比较少的情况下）、FIFO（简单，但效率比较差）...

写不命中的时候，什么情况？

写命中，write through（写cache时写主存）、write back（块被替换出去时，才更新主存，惰性修改法）

读缺失的时候，直接上内存读

写主存是耗时的，因此需要CPU停下来，这个时候CPU叫write stall

写cache的时候写主存，加个buffer，数据放到cache也同时放到write buffer（FIFO栈）里面，然后CPUf干自己的事情，后台再将buffer里面的数据写到主存里面

写不命中，写的地址在cache里面找不到，写分配方法write-allocate（or fetch on write）,写到主存时，同时也写到cache中

写不分配法：No-write allocate（or write around）

write back caches generally use write allocate and write through often use no-write allocate

cache性能：

平均存储器访问时间Average memory access time（AMAT）= Hit time +Miss Rate * Miss Penalty

= %instructions * (Hit time inst + Miss Rate inst * Miss Penalty inst) + %data * (Hit time data + Miss Rate data * Miss Penalty data)

cache performance

虚存：一个很大的程序可以在一个很小的内存空间运行

内存的一块可以放到cache的任意一块

Load/Store 指令占36% 平均每条指令访存多少次？ RISC计算机，至少有1条取指令 1+0.36

两个存储器的组织方式：

局部性原理

cache缺失分成3类：1、强制缺失；2、容量缺失；3、冲突缺失

块的容量、