RISC与CISC的区别

Reduced Instruction Set Computer，精简指令集计算机

Complex Instruction Set Computer，复杂指令集计算机

局部性原理

局部性原理的分类

时间局部性（Temporal Locality）

• 定义：如果一个数据或指令被访问过，那么它在不久的将来很可能再次被访问。

• 典型场景：

  循环结构：例如 for (int i=0; i<100; i++) sum += i;，变量 i 和 sum 会被反复访问。

  函数调用：同一个函数在短时间内可能被多次执行（如递归调用）。

• 优化应用：

  CPU缓存（Cache）：最近访问的数据会被保留在高速缓存中，以减少访问主存的延迟。

  TLB（快表）：加速虚拟地址到物理地址的转换。

空间局部性（Spatial Locality）

• 定义：如果一个数据被访问，那么其邻近的数据也很可能被访问。

• 典型场景：

  数组遍历：例如 int arr[100]; for (int i=0; i<100; i++) arr[i]++;，访问 arr[i] 后，arr[i+1] 很可能紧接着被访问。

  程序指令顺序执行：代码通常是顺序执行的，因此相邻的指令很可能被连续访问。

• 优化应用：

  缓存行（Cache Line）：CPU 读取数据时，会一次性加载一块连续内存（如 64B），而不仅仅是单个字节。

  预取（Prefetching）：CPU 预测未来可能访问的数据，提前加载到缓存。

局部性原理的应用

缓存设计（Cache）

时间局部性 → 缓存替换策略（如 LRU）：优先保留最近访问的数据。

空间局部性 → 缓存行（Cache Line）：一次加载多个相邻数据，减少访存次数。

虚拟存储（Paging）

• 页面置换算法（如 LRU、Clock）：基于时间局部性，优先保留最近使用的页面。

• 预取（Prefetching）：操作系统预测程序可能访问的页面，提前加载到内存。

数据库优化

• B+树索引：利用空间局部性，减少磁盘 I/O（相邻数据存储在同一个磁盘块）。

• 查询缓存：基于时间局部性，缓存最近执行的 SQL 查询结果。

如何编写具有良好局部性的代码？

提高时间局部性

减少循环内的重复计算：

1
2
3
4
5
6

// 差：每次循环都计算 strlen(str)
for (int i=0; i<strlen(str); i++) { ... }

// 好：预先计算长度
int len = strlen(str);
for (int i=0; i<len; i++) { ... }

提高空间局部性

• 顺序访问数组（避免随机访问）：

1
2
3
4
5

// 差：跳跃访问（缓存命中率低）
for (int i=0; i<100; i+=2) arr[i]++;

// 好：顺序访问（缓存命中率高）
for (int i=0; i<100; i++) arr[i]++;

• 优化数据结构布局：

  结构体对齐（减少缓存行浪费）。

  避免指针跳跃（如链表 vs 数组）。

流水线

性能指标公式

例题： 假设一个非流水线CPU执行指令需要 800ps，现将其改为 5级流> 水线，每级流水段耗时 200ps（含流水寄存器开销）。当处理 100 条指令时：

理论加速比 = 非流水线单指令时间 / 流水线单级时间 = 800ps / 200ps = 4倍

实际总时间 = (流水线级数 + 指令数 -1) × 单级时间 = (5 + 100 -1) × 200ps = 20,800ps

吞吐率 = 100 / 20,800ps ≈ 4.8 × 10^9 指令/秒

多级存储（Cache、内存、磁盘）

存储层次结构

核心设计原则：

局部性原理：利用时间局部性和空间局部性，将高频访问数据迁移到更高速存储层。

透明性：Cache和虚拟内存对应用程序透明，由硬件和操作系统自动管理。

各级存储核心机制

Cache

映射方式

替换算法

• LRU（最近最少使用）：维护访问时间戳，淘汰最久未使用的块（硬件实现复杂）。

• FIFO（先进先出）：简单但可能淘汰高频访问数据。

• 随机替换：硬件成本低，但性能不稳定。

写策略

• 写直达（Write-Through）：同时写入Cache和内存，保证一致性但速度慢。

• 写回（Write-Back）：仅修改Cache，淘汰时写回内存（需脏位标记）。

内存（DRAM）

• 刷新机制：DRAM需定期刷新（典型周期64ms）防止电荷泄漏。

• 虚拟内存：

  分页管理：页面大小通常4KB（Linux）/2MB（大页），通过页表转换虚拟地址。

  TLB（快表）：缓存常用页表项，加速地址转换。

磁盘（HDD/SSD）

• HDD性能关键参数：

  寻道时间（磁头移动）：5~10ms

  旋转延迟（盘片旋转）：7200 RPM → 平均4.16ms

  传输时间：与接口速率相关（SATA 6Gbps）

• SSD特性：

  磨损均衡：延长寿命，避免频繁擦写同一区块。

  FTL（闪存转换层）：模拟机械硬盘接口，管理物理块映射。

多级存储协同工作

数据流动示例（读操作）

CPU请求数据 → 检查寄存器 → 未命中

检查Cache（L1→L2→L3） → 未命中

访问内存 → 未命中（触发缺页中断）

从磁盘加载数据到内存 → 更新页表

内存数据加载到Cache → CPU获取数据

性能计算（平均访问时间）

假设：

Cache命中率 = 90%，访问时间 = 5ns

内存访问时间 = 100ns

磁盘访问时间 = 10ms（需折算为纳秒：10^7ns）

平均访问时间： 0.9×5ns + 0.1×(0.9×100ns + 0.1×10^7ns) ≈ 5.45ns + 0.1×100,000ns = 10,045ns （若缺页率为10%，性能急剧下降！体现Cache和内存的重要性）

优化策略与案例分析

Cache优化

增大块大小：提升空间局部性，但可能增加失效代价。

预取（Prefetching）：预测未来访问模式，提前加载数据。

内存优化

NUMA架构：多CPU节点就近访问本地内存，减少远程访问延迟。

透明大页（THP）：合并小页减少TLB缺失。

磁盘优化

RAID技术：

IO调度算法：

CFQ（完全公平队列）：均衡各进程磁盘访问。

Deadline：优先处理即将超时的请求（减少饥饿）。

校验码

常见校验码对比

核心校验码原理与计算

奇偶校验（Parity Check）

• 原理：添加1位校验位，使数据中1的个数为奇数（奇校验）或偶数（偶校验）。

• 示例：

数据 1010001（含4个1）：

o 偶校验：添加校验位 0 → 10100010（总共有4个1，偶数）

o 奇校验：添加校验位 1 → 10100011（总共有5个1，奇数）

• 局限性：只能检测奇数位错误，无法定位错误位置。

CRC（循环冗余校验）

• 核心步骤：

1. 选择生成多项式（如CRC-32：x32+x26+x23+⋯+1x32+x26+x23+⋯+1）。

2. 数据位补0：在原始数据后补 rr 个0（rr 为多项式最高次幂）。

3. 模2除法：用补0后的数据除以生成多项式，得到余数作为校验码。

• 计算示例：

数据：110101，多项式：x3+x+1x3+x+1（二进制 1011）

1. 数据补3个0 → 110101000

2. 进行模2除法，余数为 110

3. 最终发送数据：110101110

海明码（Hamming Code）

• 冗余位计算：

o 确定冗余位数 rr：满足 2r≥k+r+12r≥k+r+1（kk 为数据位长度）。

o 冗余位位置：位于 2i2i 位（如 1,2,4,8…1,2,4,8…）。

• 编码步骤：

1. 将数据位填入非冗余位。

2. 计算每个冗余位的值（通过对应数据位的奇偶性）。

• 纠错：接收方重新计算校验位，根据差异定位错误位置。

应用场景与案例分析

内存校验（ECC内存）

技术：使用海明码或更复杂的BCH码，可纠正单比特错误，检测双比特错误。

意义：避免服务器因内存位翻转导致数据错误（尤其在金融交易系统中）。

网络传输（TCP/IP协议）

IP头校验和：16位校验和，覆盖IP头部所有字段，检测传输错误。

局限性：仅校验头部，不校验数据部分（依赖上层协议如TCP的校验）。

存储系统（RAID 6）

技术：使用里德-所罗门码，允许两块磁盘同时故障时恢复数据。

数学原理：基于伽罗华域（Galois Field）运算，生成两个独立校验块。

校验码性能权衡

Flynn

Flynn分类法的四种架构类型

架构特性深度解析

SISD（Single Instruction Single Data）

特点：

顺序执行指令，无并行性。

通过流水线技术提升吞吐率（如Intel Pentium 4的超流水线设计）。

优化方向：提高主频、优化分支预测。

SIMD（Single Instruction Multiple Data）

核心机制：

向量处理器：一条指令操作向量寄存器中的多个数据（如Intel AVX-512指令集）。

数据级并行：适用于规则数据计算（如矩阵乘法、图像滤波）。

应用案例：

图像处理：同时对像素进行RGB通道调整。

深度学习：GPU加速矩阵运算（如Tensor Core）。

MIMD（Multiple Instruction Multiple Data）

子类型：

共享内存MIMD：多核CPU通过总线/互连共享内存（如OpenMP编程）。

分布式内存MIMD：集群节点通过消息传递通信（如MPI编程）。

设计挑战：

数据一致性（缓存一致性协议如MESI）。

负载均衡（动态任务分配算法）。

MISD（Multiple Instruction Single Data）

理论意义：

多处理器对同一数据执行不同操作，用于冗余校验（如航天器容错系统）。

实际中常被归入其他架构的混合模式。

现代架构的混合模式

真题实战示例

题目（2021年湖北卷）：

某气象局需处理TB级气象数据，要求实时模拟台风路径，应选择哪种Flynn架构？说明理由。

参考答案：

架构选择：MIMD（分布式内存） + SIMD

理由：

MIMD：多节点并行处理不同区域数据（如台风分区模拟）。

SIMD：单节点内利用GPU加速矩阵运算（如流体力学方程求解）。

多处理机

多处理机系统的核心概念

定义与分类

定义：由**多个独立处理器（CPU）**通过互连网络共享内存、总线或I/O设备，协同完成任务的系统。

分类维度：

Flynn架构关联

多处理机系统通常属于MIMD架构（多指令流多数据流），可进一步细分为：

共享内存MIMD：处理器通过共享内存通信（如OpenMP编程）。

分布式内存MIMD：处理器通过消息传递通信（如MPI编程）。

多处理机体系结构

共享内存架构

• 核心组件：

  统一内存空间：所有处理器访问同一物理内存（需缓存一致性协议）。

  互连网络：总线、交叉开关（Crossbar）、多级互连网络（MIN）。

• 关键技术：

  缓存一致性协议（如MESI、MOESI）：解决多处理器缓存数据一致性问题。

  原子操作（如CAS指令）：实现互斥锁（Mutex）和信号量（Semaphore）。

分布式内存架构

• 核心组件：

  独立内存：每个处理器拥有本地内存，通过消息传递通信。

  高速网络：InfiniBand、以太网（RDMA技术）。

• 关键技术：

  消息传递接口（MPI）：标准化通信库（如MPI_Send/MPI_Recv）。

  负载均衡算法：动态任务分配（如Work Stealing）。

多处理机性能优化

加速比与扩展性

Amdahl定律：

$$ S=\frac{1}{(1−P)+\frac{P}{N}} $$

S：加速比

P：可并行部分比例

N：处理器数量

关键结论：串行部分（1−P1−P）是性能提升的瓶颈。 • Gustafson定律： $$ S=N−α(N−1) $$ α：串行部分比例

适用场景：问题规模随处理器数量增加（如大数据处理）。

通信开销优化

• 数据本地化：将计算任务分配给数据所在的节点（如MapReduce中的Mapper本地化）。

• 通信隐藏：重叠计算与通信（如异步I/O、双缓冲技术）。

多处理机应用场景

多处理机设计挑战