#计组学习笔记0
计算机软件
系统软件
- 操作系统：硬件资源管理，用户接口
- 语言处理系统：翻译程序+链接器，调试器等
- 翻译程序
- 汇编程序：汇编语言源程序->机器语言程序，如MASM、NASM
- 编译程序：高级语言源程序->汇编/机器语言程序，如GCC、Clang
- 解释程序：将高级语言语句逐条翻译成机器语言并执行，不生成目标文件，如Python解释器
- 其他程序，如：磁盘碎片整理、备份程序等
应用软件
- 各类媒体处理程序：Word/Image/Video等
- 管理信息系统
- 游戏等
计算机系统层次结构
软硬件的界面是指令集体系结构，即 ISA
早期
- 第一代：只提供了指令集，应用程序必须使用指令集编写程序
- 第二代：提供了操作系统和汇编程序，应用程序可以使用汇编语言编写程序
现代
- 第三代程序设计语言：过程式语言，编写代码需要描述实现过程，即如何做
- 第四代程序设计语言：非过程是语言，编码时只需要说明做什么，不需要描述细节
抽象层的转换
功能转换：上层是下层的抽象，下层是上层的实现，底层为上层提供服务/支撑环境
程序执行的结果取决于算法、程序、语言处理系统、操作系统、ISA、微体系结构等
ISA 可以看成软件和硬件之间最重要的分界面，但这个边界不是绝对的。同一功能可以放在软件里完成，也可以下沉到硬件中完成。硬件实现通常速度更快，但设计、验证和兼容成本更高；软件实现更灵活，修改代价低，但性能可能差很多。
Amdahl定律
加快某部件执行速度所能获得的系统性能加速比，受限于该部件的执行时间占系统中总执行时间的百分比。
加速比公式 \[ 加速比=\frac{系统性能_{改进后}}{系统性能_{改进前}}=\frac{总执行时间_{改进前}}{总执行时间_{改进后}} \] 加速比依赖于以下两个因素：
- 可改进比例：在改进前的系统中，可改进部分的执行时间在总执行时间中所占比例
- 部件加速比：可改进部分改进后性能提高的倍数，是改进前所需时间和改进后执行时间的比
一个需运行60秒的程序中有20秒的运算可以加速，那么这个比例就是20/60
若系统改进后，可改进部分的执行时间是2秒，而改进前其执行时间为5秒，则部件加速比为5/2
改进后的总执行时间： \[ 总执行时间_{改进后} = (1 - 可改进比例) \times 总执行时间_{改进前} + \frac{可改进比例 \times 总执行时间_{改进前}}{部件加速比} \\ = [(1 - 可改进比例 + \frac{可改进比例}{部件加速比}) \times 总执行时间_{改进前}] \] 系统加速比： \[ 加速比 = \frac{总执行时间_{改进前}}{总执行时间_{改进后}} = \frac{1}{(1 - 可改进比例 + \frac{可改进比例}{部件加速比})} \]
Amdahl定律的启示
如果仅仅对计算任务中的一部分做性能改进，则改进得越多，所得到的总体性能的提升就越有限。
也就是说存在边际效益递减
如果只针对整个任务的一部分进行改进和优化，那么所获得的加速比不超过 \(\frac{1}{可改进比例}\)
实际使用 Amdahl 定律时，第一步不是直接代公式，而是先分析时间花在哪里。若某个部件只占总执行时间的 5%，即使把它优化到不耗时，总体提升也很有限。优先优化的应该是执行时间占比最高的路径，也就是程序或系统中的主要瓶颈。
计算机系统性能评测
执行时间和吞吐率
用户关心的是：单个程序的执行时间（执行单个程序所花的时间很少）
数据处理中心的管理员关心的是吞吐率（在单位时间里能够完成的任务很多 ）
用户感觉到的时间实际上是响应时间
响应时间：表示完成某项任务所需的总时间，包括了磁盘访问、内存访问、内存活动和操作系统开销等一切时间
CPU时间：CPU执行所给定的程序所花费的时间，包含I/O等待时间和其他程序的时间。包括两个部分，分别是：
- 用户CPU时间：用来运行用户代码的时间
- 系统CPU时间：为了执行用户程序而需要运行操作系统程序的时间
CPU 性能公式
\[ CPU 执行时间 = 程序时钟周期数 \times 时钟周期长度 \\ = 程序的时钟周期数 \div 时钟频率 \]
指令性能
指令的性能通过指令平均时钟周期数 CPI 来衡量 \[ CPI = 程序的时钟周期数 \div IC \] IC 是执行的指令条数
那么 CPU 性能公式可以改写为： \[ CPU 时间 = IC \times CPI \times T \] 这里的：
IC取决于指令集结构、编译技术、编程技术CPI取决于指令集结构、计算机组成、编译技术和编程技术T取决于计算机组成和硬件实现技术
这三个量不能完全独立看。提高主频会减小周期时间 T，但更深的流水线、更复杂的 cache 或控制逻辑也可能让 CPI 增大。评价 CPU 性能时不能只看主频，而要看指令数、平均 CPI 和周期时间的综合结果。
指令性能
假设系统有 \(n\) 类指令，第 \(i\) 类指令的指令数和 CPI 分别为 \(IC_i\) 和 \(CPI_i\)，则程序的总时钟周期数为： \[ CPU 执行时间 = 时钟周数 \times 时钟周期时间 \\ = \sum_{i=1}^{n} (IC_i \times CPI_i) \times T \] 这里 CPI 可以表示为： \[ CPI = = \frac{时钟周期数}{IC} = \sum_{i=1}^{n} (CPI_i \times \frac{IC_i}{IC}) \] 其中 \(\frac{IC_i}{IC}\) 反映了第 \(i\) 类指令在程序中所占的比例
一个程序通常只会使用 ISA 中的一部分指令，而且不同类型指令的动态出现频率不同。因此程序 CPI 是按执行比例加权得到的平均值。比如图形和游戏程序可能浮点指令占比较高，而字符串处理程序可能整数、访存和分支指令更多。
功耗
功耗是 CPU 性能的一部分，并且越来越重要，一般来说，Intel 的 CPU功耗高，而 ARM 的 CPU 功耗低
集成电路的主流技术是 CMOS，能耗主要来源是动态能耗
动态能耗可以表示为 \[ 能耗 \propto 负载电容 \times 电压^2 \\ 功耗 \propto \frac{1}{2} \times 电压^2 \times 开关频率 \]
现代处理器不能无限提高主频，一个重要原因就是功耗和散热成为瓶颈。CMOS 动态功耗与电压平方和开关频率相关，频率提高往往伴随明显能耗上升。移动设备更重视能效，所以 ARM 类处理器在手机、手表等场景中更常见。
产品指标
通常用 MIPS（每秒百万条指令）来衡量 CPU 的性能，MIPS 可以表示为： \[ MIPS = \frac{指令数}{执行时间 \times 10^6} \] MIPS 通常是平均值，原因如下：
- 不同机器的指令集不同
- 程序由不同的指令混合而成
- 指令使用的频度动态变化
MIPS 数不能说明性能的好坏
MIPS 只反映每秒执行多少条指令，不能直接等价于真实程序性能。不同程序的指令混合不同，某些 benchmark 也可能被厂商专门优化，从而得到很高但不具代表性的分数。因此性能评测应结合真实工作负载，而不是只看峰值指标。
能耗比
\[ 能耗比 = \frac{1}{执行时间 \times 能耗} \]
数据的机器级表示
常用的数值数据的表示不再赘述，包含 BCD 等基础编码
逻辑数据的表示
逻辑数据的表示通常使用布尔代数，布尔代数中的变量只能取两个值：真（True）和假（False）。在计算机中，通常用 1 表示真，0 表示假。
比如 x86 中标志寄存器 FLAG 中的每一位都表示一个特定的状态，如零标志（ZF）、进位标志（CF）等，这些标志位可以用来控制程序的流程。
西文字符
传统上，所有字符总数不超过128个(7位ASCII)或256个(8位扩展ASCII)，分别使用7位或8位二进制表示
- 10进制数字：0/1/2…/9
- 英文字母 ： A/B/…/Z/a/b/…/z
- 专用符号 ： +/-/%/*/&/……
- 控制符号(不可打印或显示) ：
七位 ASCII 使用7比特二进制编码，定义128个字符
八位 ASCII 前128个字符(0~127)与7位ASCII完全相同，后128个字符为扩展部分。增加了特殊符号、带音标字母、图形字母和非英语西文字符
具体字符集因编码标准而异:
ISO 8859-1：西欧扩展语言，支持带音标的字母(ä、ö)；
Code Page 437：IBM PC的默认扩展ASCII，含框线字符(┌、└)
同一个代码值(如128)在不同系统中可能代表不同字符
汉字
GB2312(1980年)：收录6763个汉字，覆盖简体中文；
GBK(1995年) ： 扩展到21886个字符，包括简体和部分繁体字；
Unicode(最新版本16.0, 2024年)：收录超过97000个汉字(CJK统一汉字区)，包括简体、繁体和日韩汉字。
汉字的编码形式主要可以分为以下几类，分别应用于不同的场景：
汉字输入码（外码）
用于在计算机上输入汉字，是用户通过键盘输入的编码
- 音码：基于汉字的读音，如全拼、双拼、搜狗拼音等。
- 形码：基于汉字的字形结构，如五笔字型、郑码等。
- 音形码：结合了字音和字形，如自然码。
汉字交换码
用于不同计算机系统或设备之间进行汉字信息交换的编码，要求统一标准
- GB2312-80：中国国家标准简体中文字符集，包含6763个常用汉字。
- ① 字母、数字和各种符号，包括英文、俄文、日文平假名与片假名、罗马字母、汉语拼音等，共682个（常记为687个）。
- ② 一级常用汉字，共3,755个，按汉语拼音排列。
- ③ 二级常用汉字，共3,008个，不太常用，按偏旁部首排列。
- GBK：GB2312的扩展，包含了更多的简体字、繁体字及符号，向下兼容GB2312。
- GB18030：最新的国家标准，支持中日韩统一表意文字（CJK）字符，兼容GBK。
- BIG5：繁体中文字符集标准，主要在台湾、香港等地使用。
汉字区位码
码表由94行、94列组成，行号为区号，列号为位号
以十进制表示汉字在码表中的位置，区号在前，位号在后（如1601）
汉字国标码
每个汉字的区号和位号各自加上32（0x20），得到其国标码。
国标码用2字节表示，每字节7位有效位（范围33-126），高位补0构成8位
汉字机内码（内码）
计算机系统内部处理和存储汉字时使用的编码。为了区分汉字与ASCII码（西文字符），通常将交换码的每个字节的最高位设为1（高位为1的字节），或者在国标码的基础上加上特定数值（如8080H或A0A0H）形成
有时会把国标码+0x8080
汉字字形码（字模码）
用于在显示器或打印机上输出汉字。它描述了汉字的具体形状
- 点阵字形：用黑白像素点阵来表示汉字，如16×16、24×24点阵。优点是显示速度快，缺点是缩放时会产生锯齿。
- 矢量字形：用数学曲线（如贝塞尔曲线）来描述汉字的轮廓。优点是缩放平滑不失真，如TrueType字体。
国际字符集
为实现国际字符互换，必须创建涵盖所有字符的统一多字符集
- 国际多字符集（如 ISO/IEC 10646 和 Unicode）的核心思想：通过为所有字符分配唯一的编码（码点），实现跨地区字符的统一表示，目标是涵盖所有书面语言的字符。
早期提供 UCS-4（4字节）和 UCS-2（2字节），现演进为 UTF-32 和 UTF-16
- CJK（Chinese, Japanese, Korean）是ISO/IEC 10646和Unicode中的一个重要部分，由中、日、韩等国合作制定，统一汉字编码，避免重复。
收集了中、日、韩共20,902个常用汉字，采用2字节UCS-2编码，纳入国家标准GB13000，后续扩展超9万字。
- Windows（从Windows NT开始，尤其是中文版）采用Unicode作为内部编码，支持CJK汉字。
早期使用UCS-2，收录BMP内的20,902个CJK汉字，现使用UTF-16支持更多字符。
数据的宽度和存储
比特、字节、字、双子、四字略
容量、频率和通信带宽里的单位含义不完全相同。存储容量常按二进制幂计量，如 KB、MB、GB 常对应 \(2^{10}\)、\(2^{20}\)、\(2^{30}\) 字节；频率通常按十进制幂计量，如 GHz 是 \(10^9\) Hz。通信带宽中小写 b 表示 bit，大写 B 表示 byte，二者相差 8 倍。
字长
字长是定点运算数据通路的宽度
数据通路指CPU内部数据流经的路径以及路径上的部件，主要是CPU内部进行数据运算、存储和传送的部件，这些部件的宽度基本上要一致，才能相互匹配。因此，字长等于CPU内部总线的宽度、运算器的位数、通用寄存器的宽度等
数据类型存储在不同机器上的不同，大端小端双端，略
高级语言中的数据类型需要映射到机器级宽度和相应指令上。像 int、long 这类类型在不同平台上的宽度可能不同，跨平台代码更适合使用 int32_t、uint64_t 等固定宽度类型。整数和浮点数不仅存储格式不同，底层使用的运算部件和指令也不同。
大端和小端只在一个对象需要多个字节表示时才有意义，单字节数据不存在端序问题。小地址存最高有效字节称为大端，小地址存最低有效字节称为小端。网络通信和文件格式通常会规定自己的字节序，跨平台读写时需要显式转换。
字节交换是由于端序不一致导致的多字节数据解释错误
字节对齐
计算机理论上可以从任意地址访问基本数据类型，但实际上计算机通常以2、4或8字节的块读写内存，以提高效率
各种数据类型需按一定规则在内存中排列，这就是字节对齐。未对齐可能导致性能下降或硬件异常
内存虽然按字节编址，但 CPU 访问内存时通常按固定宽度的数据块读取。若一个 4 字节整数跨越两个访问块，CPU 可能需要读两次再拼接。结构体填充看似浪费空间，但能让成员和整体大小满足对齐规则，从而简化硬件访问并提高速度。
对齐准则：
- 准则1：结构体变量的首地址必须是其最大对齐要求的整数倍；
- 准则2：结构体每个成员相对首地址的偏移量是其对齐要求的整数倍。如不满足，在前一成员后填充字节；
- 准则3：结构体的总大小是其最大对齐要求的整数倍。如不满足，在末尾填充字节。
数据校验码
数据校验码的核心思想是冗余
发送端不只发送原始信息 \(M\)，还会根据某个双方约定的函数 \(f\) 计算校验信息： \[ P=f(M) \] 然后把 \((M,P)\) 一起传输
接收端收到 \((M',P'')\) 后，再计算： \[ P'=f(M') \] 如果 \(P'=P''\)，则认为没有发现错误；
如果二者不同，则说明发生了错误。某些校验码只能检错，某些校验码还能根据校验结果定位并纠错
错误模型
错误通常分为两类：
- 单比特错误：一个数据单元中只有 1 位出错
- 突发错误：一个数据单元中至少有 2 位出错，而且错误可能连续出现
在存储器和总线传输中，单比特错误比较常见；在通信信道和外存读写中，突发错误更常见。
码字和码距
由若干代码构成的一个字称为码字
两个码字之间不同位的个数称为这两个码字之间的距离
一个编码系统中，任意两个合法码字之间距离的最小值称为码距，记作 \(d\)
码距越大，合法码字之间隔得越远，越不容易把一个合法码字误认为另一个合法码字
一般有：
- 检测 \(t\) 位错误需要 \(d \ge t+1\)
- 纠正 \(t\) 位错误需要 \(d \ge 2t+1\)
比如码距为 2 的编码，能发现 1 位错误，但不能确定到底是哪一位错了
常见校验码包括：
- 奇偶校验码
- 海明校验码
- 循环冗余校验码 CRC
奇偶校验码
奇偶校验码是在数据后面增加 1 位校验位，使整个码字中 1 的个数满足奇偶性要求。
假设数据为： \[ B=b_{n-1}b_{n-2}\cdots b_1b_0 \]
偶校验要求整个码字中 1 的个数为偶数，因此校验位为： \[ P=b_{n-1}\oplus b_{n-2}\oplus \cdots \oplus b_1 \oplus b_0 \]
奇校验要求整个码字中 1 的个数为奇数，因此校验位为： \[ P=b_{n-1}\oplus b_{n-2}\oplus \cdots \oplus b_1 \oplus b_0 \oplus 1 \]
接收端重新计算校验位 \(P'\)，再和收到的校验位 \(P''\) 异或： \[ P^*=P'\oplus P'' \]
- 若 \(P^*=1\)，说明发现奇数位错误
- 若 \(P^*=0\)，说明没有发现错误，或者发生了偶数位错误
奇偶校验的码距为 2，只能发现奇数位错误，不能发现偶数位错误，也不能纠错
它的好处是开销小，所以适合用于字节级传输或存储器读写检查
海明校验码
海明校验码的目标是用多位校验位定位错误位置，从而实现纠错
如果有 \(m\) 位数据，增加 \(r\) 位校验位，要能纠正 1 位错误，则至少要满足： \[ 2^r \ge m+r+1 \]
原因是：
- \(m+r\) 个位置都可能出错
- 还需要一种状态表示没有出错
- 因此综合症至少要能表示 \(m+r+1\) 种情况
海明码通常把校验位放在编号为 \(1,2,4,8,\cdots\) 的位置，也就是 \(2^k\) 位置。每个校验位负责检查若干个固定位置。
接收端重新计算所有校验位，得到的结果称为综合症。
如果综合症为 0，则没有发现错误；
如果综合症不为 0，其二进制值就是出错位的位置编号
如果再额外加一位总奇偶校验位，就可以构成 SECDED：
- Single Error Correction：纠正 1 位错误
- Double Error Detection：检测 2 位错误
内存 ECC 常用的就是这类思想
循环冗余校验码
循环冗余校验码 CRC（Cyclic Redundancy Check）适用于大批量数据存储和传输中的检错
它把二进制数据看成一个多项式，通过模 2 除法得到余数，余数就是校验位
设数据信息为 \(M(x)\)，位数为 \(n\)；生成多项式为 \(G(x)\)，位数为 \(k+1\)。CRC 的生成过程为：
- 将 \(M(x)\) 左移 \(k\) 位，相当于在数据后补 \(k\) 个 0
- 用 \(G(x)\) 对左移后的数据做模 2 除法
- 得到 \(k\) 位余数 \(R(x)\)
- 把余数拼到原始数据后面，得到 CRC 码
模 2 运算没有进位和借位： \[ 0+0=0,\quad 0+1=1,\quad 1+0=1,\quad 1+1=0 \]
这里加法和减法都等价于异或
CRC 例子
假设要传输的数据为： \[ M=100011 \]
生成多项式为： \[ G=1001 \]
因为生成多项式有 4 位，所以校验位为 3 位。先在 \(M\) 后补 3 个 0： \[ 100011000 \]
然后用 \(1001\) 做模 2 除法，得到余数： \[ 111 \]
所以最终发送的 CRC 码为： \[ 100011111 \]
接收端收到数据后，用同一个生成多项式 \(1001\) 去除
如果余数为 0，则没有发现错误；
如果余数不为 0，则说明一定发生了错误
CRC 的检错能力很强，特别适合检测突发错误，所以常用于网络通信、磁盘、压缩文件等场景
不过 CRC 通常只用于检错，在发现错误后，一般通过重传解决，而不是在本地直接纠错