计算机原理与嵌入式系统笔记：第十二篇
程序组件与程序模型
- 嵌入式软件常用的三个组件结构：
- 状态机（State machine）
- 循环缓冲区（Circular buffer）
- 队列（Queue）
状态机适合于交互式系统，循环缓冲区和队列应用于数字信号处理系统。
状态机
有限状态机是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型，分为两种：
- Moore机：输出只由当前状态确定
- Mealy机：输出依赖于当前状态和输入
循环缓冲区
流数据通常用于信号处理领域的程序设计中，数据定期传送，新数据按规律到达，且每个数据生命周期有限，需要程序立即处理。循环缓冲区是便于程序高效处理流数据的一种数据结构。数据窗口尺寸不变，只是随时间滑动。
索引指向循环缓冲区的下一个被替换的数据位置（input）和当前使用的数据位置（use）。
1 |
|
这段代码实现了一个循环缓冲区（circular buffer）的基本操作。循环缓冲区是一种数据结构，它在内存中形成一个循环，当数据到达缓冲区的末尾时，下一个数据将回到缓冲区的开始。
首先，
#define CMAX 6定义了缓冲区的大小为6。int circ[CMAX];声明了一个名为circ的整数数组，用作循环缓冲区。int pos;声明了一个名为pos的整数，用于跟踪当前样本的位置。
void circ_update(int xnew)函数用于更新缓冲区。它首先计算新的头部值，并处理回绕（wraparound）。如果pos等于CMAX - 1（即，已经到达缓冲区的末尾），则pos被设置为0；否则，pos增加1。然后，新值xnew被插入到新的头部位置。
void circ_init()函数用于初始化缓冲区。它通过一个for循环将circ数组的所有元素设置为0，然后将pos设置为CMAX - 1，这样第一个元素将在位置0。
int circ_get(int i)函数用于获取缓冲区中的值。它首先计算缓冲区的位置。如果pos大于或等于i，则位置ii为(pos - i) % CMAX；否则，位置ii为(CMAX + pos - i) % CMAX。然后，返回circ[ii]的值。
循环缓冲区实现FIR
FIR滤波器的功能代码：for (i=0, y=0; i<N; i++) y += x[i]*b[i];
- 随时间改变的输入信号x存储在循环缓冲区中
- 不随时间改变的信号b存储在标准数组中
1 | int fir(int xnew) |
队列
队列也应用于信号处理领域的程序设计中。与元素数量固定的循环缓冲区相比，队列中的元素数量是可变的。
基于数组的队列
1 |
|
这段代码实现了一个循环队列（circular queue）的基本操作。循环队列是一种线性数据结构，它在内存中形成一个循环，当数据到达队列的末尾时，下一个数据将回到队列的开始。
首先，
#define Q_SIZE 5定义了队列的大小为5。#define Q_MAX (Q_SIZE - 1)定义了队列的最大索引值。int q[Q_SIZE];声明了一个名为q的整数数组，用作队列。int head, tail;声明了两个名为head和tail的整数，用于跟踪队列的头部和尾部。
void queue_init()函数用于初始化队列。它将head和tail都设置为0。
void enqueue(int val)函数用于将一个值添加到队列的尾部。它首先检查队列是否已满，如果((tail + 1) % Q_SIZE) == head，则队列已满，调用error函数报错。然后，将值val添加到队列的尾部。最后，更新tail的值，如果tail等于Q_MAX，则tail被设置为0；否则，tail增加1。
int dequeue()函数用于从队列的头部删除一个值。它首先检查队列是否为空，如果head == tail，则队列为空，调用error函数报错。然后，从队列的头部取出一个值。最后，更新head的值，如果head等于Q_MAX，则head被设置为0；否则，head增加1。函数返回取出的值。
程序模型
源代码并不是好的程序表示方式，我们使用程序模型来让程序变得更加直观：
程序模型就是控制/数据流图（ Control/Data Flow Graph, CDFG ）。
数据流图
数据流图（data flow graph, DFG）是不包含条件判断的程序模型。它不能表示控制，因为在高级语言中，没有条件判断相关的代码。
上网查了下，只查到数据流图不能表示控制。后面一句未找到出处。
基本语句块是一个无条件式的代码段，也就是说代码只有一个入口和一个出口。，程序从入口处进入该基本语句块并执行全部语句。
单赋值形式：变量在赋值语句左侧仅出现一次。
1 | x = a + b; | x = a + b; |
单赋值形式不会在DFG中形成环（比如包含y的变量值和计算y的运算），保持数据流图是无环图在很多图的分析方法中很重要。
数据流图使代码中的操作执行顺序不明显,优势是可以改变执行顺序，优化流水线或缓存冲突。
控制/数据流图
控制/数据流图（CDFG） 用数据流图作为一个基础元素，添加描述控制的结构。
基本的CDFG有两种节点：
- 判定节点：描述控制逻辑
- 数据流节点：包括一个完整的表示基本语句块的数据流图
判定节点用菱形等节点表示，节点的判定条件由标签给出，边被标记为评估判定条件的可能结果。
数据流节点用矩形节点表示基本语句块，为了简便，C代码中的基本语句块被表示为函数调用的形式。
程序编译方法
汇编、连接和装载
汇编和连接是编译处理过程的最后几步:
汇编程序的地址有两种类型：
- 绝对地址（absolute addresses）是汇编语言程序在内存中的地址；
- 相对地址（relative addresses）是相对于模块内部的起始地址。
连接器负责把相对地址译成绝对地址。
标记的处理
标记处理要求汇编器对汇编源代码进行两遍扫描。第一遍扫描处理决定每个标记的地址，第二遍扫描处理用第一遍计算的标记值汇编指令。
在第一遍扫描过程中，会创建符号表（symbol table），在扫描过程中，程序位置计数器（Program Location Counter，PLC） 为标签分配存储位置。
伪操作ORG语句可以指定程序的起始地址位置，且这个语句不占据PLC。汇编程序允许一个程序有多个ORG语句。
- 汇编中对伪操作（伪指令）的处理：
- ORG：设置语句的起点。
- EQU：常量定义，允许将标记添加到符号表，而不增加PLC。
- DCD：数据声明，定义数据块。
- ADR：在寄存器中创建地址。
汇编器生成的目标文件是以二进制形式描述的指令和数据。目标文件必须描述指令、数据和相关地址信息，并且通常带有符号表。
连接
汇编语言程序通常有几个较小的部分组成，而不是一个单一的大文件。 连接是将多个汇编程序生成的目标代码模块组成一个可执行文件的过程。 连接完成的工作有解决跨模块跨文件的标记问题和确定模块间的顺序。
- 第一个阶段：要确定每个目标文件的开始地址
- 第二个阶段：生成绝对地址
动态链接库
动态链接库（dynamically linked library，DLL）一般用于工作站和PC，有些嵌入式计算环境也支持。
动态链接库不是将一个通用例程连接到系统中的每一个可执行程序，而是允许他们**在程序执行的开始被连接。**这可以使库文件被复用，并且易于更新，但是会在程序开始执行前引入延迟。
入口点与外部引用
一些标签在同一个文件中定义并使用；也有一些标签在一个文件中定义，但是在其他文件中使用。
- 程序中定义标记的地方称为入口点（entry point）
- 程序中使用标记的地方称为外部引用（external reference）
可重入代码
如果程序执行一个函数时被另一个执行该函数的调用中断而不改变函数结果，则该函数是可重入的。
若一个程序置于内存不同位置均可执行，则称之为可重定位。
有时候需要使用不可重定位地址，如I/O设备寻址。
编译
编译 = 翻译 + 优化
过程链接
过程链接机制允许参数和返回值传递，并保护和恢复修改过的寄存器。过程的参数和返回值主要通过栈（stack）来传递。
过程栈将调用过程的信息按帧存储在栈上，用于跟踪调用过的过程序列。当新过程被调用时，sp和fp都会被修改，使新的一帧入栈。
结构体
结构体（structure）由一个连续的存储块来实现。对结构体内字段的访问可以通过结构体基地址+偏移量来访问，地址计算可以在编译时完成，执行期间只需要获取内存位置。
优化方法
必考
基本的编译方法只能生成低效的代码，编译器使用多种算法来优化生成的代码。
- 表达式简化
- 无效代码的清除
- 过程内嵌
- 循环变换
- 寄存器分配
- 调度
- 指令选择
表达式简化
-
利用代数法则：
a*b + a*c = a*(b+c) -
常量叠算（constants folding）：
1
28 + 1 = 9
for (i=0; i<8+1; i++) -
运算强度化简：a*2 = a<<1
无效代码清除
1 | #define DEBUG 0 |
这个优化是编译器层面的而非用户代码层面的。并不是说你不能在程序里这么书写。对于后续调试，这样子写是很有帮助的。
过程内嵌
过程内嵌（procedure inlining） 属于独立于机器的变换，将函数的子程序调用过程替换为与函数体等效的代码。
是否使用过程内嵌需要评估，代价在于：
- 函数的多份拷贝可能造成缓存冲突，减慢指令存取速度
- 增大代码量，增加存储器开销
循环变换
循环虽然在源代码中描述的很紧凑，但通常在执行时会占用大量的计算时间。
循环展开（loop unrolling） 对于固定次数的循环可以直接生成代码。这可以：
- 减少循环的开销，提高代码并行度。
- 可能会扰乱缓存并增加代码量。
循环融合（loop fusion） 将两个或多个循环合成一个：
- 两个循环必须遍历相同的值
- 循环体之间不存在数据依赖
循环分解（loop distribution） 将一个循环分解成多个。
寄存器分配与生命周期图
寄存器分配是非常重要的编译阶段，目标：
- 选择寄存器来保存每个变量
- 决定变量在寄存器中的生命周期
- 选择变量（包括声明的和临时的）在寄存器上的分配以最小化所需的寄存器总数。
寄存器的生命周期图（lifetime graph） 用于显示每个变量在语句中的使用情况。
如果一段代码所需的寄存器数目超过可用的寄存器数，必须临时将一些值溢出（spill） 到内存，将其写入内存的临时存储单元；在其他计算中可以重用这些寄存器，然后重新从临时存储单元读入保存的数值恢复计算。
上面的例子中如果不使用reload方法多次读取a和b，需要使用5个寄存器。
1 | LDR r0,a |
软件流水线
程序的性能分析优化和测试
程序性能 ≠ CPU性能
如何评估程序性能，有三种不同类型的指标：
- 平均执行时间（average-case execution time）
- 最坏执行时间（worst-case execution time）
- 最佳执行时间（best-case execution time）
软件性能优化
优化软件性能的方法：
- 带有循环结构的程序需要花费较长的执行时间，因此循环是优化的重要对象。基本的循环优化技术：
- 代码移出（code motion）
- 归纳变量消除（induction-variable elimination）
- 强度削减（strength reduction）
- 访问存储器的延时也是制约软件性能的主要因素，因此对高速缓存的优化能够提高缓存性能：
- 通过数组重排和数组填充来优化循环嵌套（loop nest）
- 分块循环（loop tiling）
- 其他通用的性能优化策略
代码移出
代码移出技术将不必要的代码移动到循环体外，避免不必要的执行。如下面的代码：
1 | for (i=0; i<N*M; i++){ |
N*M可以被移出。
归纳变量消除
利用数组的步进顺序遍历，消除了乘法运算：
强度削减
如：利用左移代替乘法
循环嵌套与缓存冲突
理解方法，很可能考察计算（因为作业中有）
考虑下面的循环嵌套示例：
1 | for (j=0; j<M; j++){ |
对于a，a[0]=[1024, 1025,1026, 1027]，第一次进行运算时将a[0]取入直接映射缓存。
对于b，b[0]=[4096,4097,4098,4099]，映射的缓存块与a[0]一致，因此会覆盖a[0]的缓存，导致冲突未命中。
针对循环嵌套中的数组冲突的优化方法：
- 数组重排：将b的起始地址移到4100，可以消除冲突。
- 数组填充：向循环中添加哑数据元素，改变数组在高速缓存中的布局，降低高速缓存冲突。
- 复杂情况下，对数组既进行移动又进行填充。
循环分块
程序验证与测试
主要关注功能验证，有两种主要的测试策略：
- 黑盒测试（black box）：测试方法的产生无需了解程序的内容结构。
- 白盒测试（clear box or white box）：测试方法的产生要以程序结构为基础。
下一次应该是最后的内容了，讲讲进程和操作系统
