文章目录
嵌入式程序组件
考虑三种广泛应用于嵌入式软件的结构或组件的代码,这三种结构或组件分别是:状态机,循环缓冲器,队列。
状态机
- 状态机通过状态来表示系统的内部特性,
状态的变化是基于输入的变化。
- 应用:
- 面向控制的代码;
- 响应式系统;
- 非周期性采样作为输入
C语言实现的一个软件状态机——座位安全带控制器
- 需求:有人坐到座椅上,在规定时间内若没有系好安全带,就启动蜂鸣器。
- 输入:
- seat: 是否有人坐;
- belt: 是否系安全带;
- timer: 定长计时器;
- 输出:蜂鸣器。
- 状态:state: 机器当前状态
#define IDLE 0 #define SEATED 1 #define BELTED 2 #define BUZZER 3 switch (state) { case IDLE: if (seat) { state = SEATED; timer_on = TRUE; } break; case SEATED: if (belt) state = BELTED; else if (timer) state = BUZZER; break; case BELTED: if (!seat) state = IDLE; else if (!belt) state = SEATED; break; case BUZZER: if (belt) state = BELTED; else if (!seat) state = IDLE; break; } ```
循环缓冲区和面向流的程序设计
-
数据流形式表示按规律到达并需要立即处理的数据
- FIR滤波器是一个典型的面向流处理的例子:对每一个采样,滤波器必须有一个输出,这个输出依赖于之前到达的n个输入。
- FIR滤波器是一个典型的面向流处理的例子:对每一个采样,滤波器必须有一个输出,这个输出依赖于之前到达的n个输入。
-
循环缓冲区(circular buffer) 是便于我们处理流数据的一种数据结构。
- 使用一个
固定大小
的缓冲区来保存当前数据,按时序移动缓冲区的头部,缓冲区的指针指向下一个采样数据被替换的位置。每添加一个采样就覆盖原先要剔除的数据,当指针移动到缓冲区的末端,则自动回到顶部。- use:数据替换位置的前一个位置
- Input:输入数据指针
C语言实现的循环缓冲区
#define CMAX 6 /* filter order */ int circ[CMAX]; /* circular buffer */ int pos; /* position of current sample */
- 变量pos保存当前采样位置,向缓冲区添加值时,变量位置移动
//向缓冲区中添加新值 void circ_update(int xnew) { /* compute the new head value with wrap around; the pos pointer moves from 0 to CMAX-1 */ pos = ((pos == CMAX-1) ? 0 : (pos+1)); /* insert the new value at the new head */ circ[pos] = xnew; }
- pos指向数组末尾时返回0。
//初始化函数 void circ_init() { int i; for (i=0; i<CMAX; i++) /* set values to 0 */ circ[i] = 0; pos=CMAX-1; /* startat tail so first element will be at 0 */ }
- 为了使第一个数据元素进入circ[0],设置pos指到数组末尾,再添加第一个元素前,它的值会变为0。
int circ_get(int i) { int ii; /* compute the buffer position */ ii = (pos - i) % CMAX; return circ[ii]; /* return the value */ }
FIR滤波器
- 表示为 z-1 的方框代表延迟运算符
- z符号来源于数字信号处理中的z变换
- 上标-1都表示操作执行一个采样周期的时间延迟。
- b1 意味着延迟运算符的输出要乘以b1
- 生成FIR滤波器输出的代码为:
for(i=0,y=0.0;i<N;i++)
y+=x[i]*b[i];
C编写的数字滤波器
- 延迟元素在垂直方向运行,在顶端保存最近采样的输入样本,在低端保持最早的输入样本。
- x值随时间变化
- 用循环缓冲区保存x值
- 缓冲区头部从高值向低值移动
- b值不变:使用标准数组来保存
//修改后的update函数,按照既定顺序将新值放入缓冲区
void circ_update(int xnew) {
/* add the new sample and push off the oldest one */
/* compute the new head value with wraparound; the
pos pointer moves from CMAX-1 down to 0 */
pos = ((pos == 0) ? CMAX-1 : (pos-1));
/* insert the new value at the new head */
circ[pos] = xnew;
}
- 改变 circ_init() 函数初始化 pos = 0 。circ_get() 函数不需要改变
- FIR滤波器函数代码如下:
int fir(int xnew) {
/* given a new sample value, update the queue and
compute the filter output */
int i;
int result; /* holds the filter output */
circ_update(xnew); /* put the new value in */
for (i=0, result=0; i<CMAX; i++)
result += b[i] * circ_get(i);
return result;
}
II型IIR 滤波器
- v表示输入与右边的参数的乘积
- a、b是固定不变的,
- 标准数组存储。
- 先计算,然后把新输入压入缓冲区
int iir2(int xnew) {
int i, aside, bside, result;
//ZMAX-1 :最陈数据不适用
for (i=0, aside=0; i<ZMAX-1; i++)
aside += -a[i+1] * circ_get(i);
for (i=0, bside=0; i<ZMAX-1; i++)
bside += b[i+1] * circ_get(i);
result = b[0] * (xnew + aside) + bside;
circ_update(xnew);
/* put the new value in */
return result;
}
队列和生产者 / 消费者系统
-
数据在无法预料的时刻到达和离开,或者在某时刻有不同数目的数据到达
可以用队列来描述 - 队列常被视为弹性缓冲区
- 构建队列的方式:链表、数组
- 具体代码就不用我贴了叭
- 生产者 / 消费者系统
- p1,p2是两个算法处理块
- 数据从单行缓存区的队列中发送到处理块中
- 数据q12是p1产生的数据,p2消费的数据
程序的模型
- 源代码不是一种很好的表示形式
- 源代码多样性:C语言、汇编语言
- 有很多隐含的信息
- 基本程序模型:控制/数据流图(CDFG)
数据流图(DFG,Data flow graph)
- 数据流图是
一个无条件程序模型
- 基本语句块:
- 无条件代码段
- 只有一个入口和出口
- 可操作的最大
顺序语句
序列
- 单赋值形式:一个变量只能在赋值运算符左边出现一次
- 它允许我们在每一个计算命名地址的代码中标识一个唯一地址
- 单赋值意味着数据流图是非循环的
- 两类结点:
- 圆形结点:表示操作
- 方形结点:表示值
- 数据流图在基本语句块中定义了操作的部分顺序
- 可以用它来确定对操作顺序重排是否可行
- a+b, c-d; b+d, x*y
- 可以用任何顺序执行
- 可以用它来确定对操作顺序重排是否可行
控制/数据流图(CDFG)
- CDFG:表示控制与数据的图
- 用数据流表示组件,添加控制部分
- CDFG有两种类型的节点:
-
判决节点:描述的全部控制类型
- 描述控制类型
- 描述控制类型
-
数据流节点:一个完整的表示基本语句块的数据流图
- 封装一个数据流图
- 在节点中完成写操作
-
- CDFG是一种
分层表述形式
,可以对一个数据流CDFG进行扩展来展现完整的数据流图
- CDFG例子:选择分支
if (cond1) bb1(); else bb2(); bb3(); switch (test1) { case c1: bb4(); break; case c2: bb5(); break; case c3: bb6(); break; }
- CDFG例子:循环
//for循环 for (i=0; i<N; i++) loop_body(); //while循环 i=0; while (i<N) { loop_body(); i++; }
汇编、连接和装载
- 汇编和链接是编译处理过程的最后一步,它们将一系列指令转换成程序的片段在内存中的映像。
- 装载将程序放入程序中,使得程序能够执行。
- 多模块程序:
- 程序由多个文件构成,决定指令和操作数地址的最后一步由连接器完成
- 地址类型:
- 相对地址:从一个模块的开始编址
- 绝对地址:按照CPU地址空间编址
汇编程序
-
主要任务:
- 为符号指令产生二进制代码
- 把标签变为地址
- 处理伪操作 (data, etc.)
-
标签让编译器不用担心指令和操作数的位置
- 标签处理过程:两次扫描
- 第一次扫描处理决定每个标记的地址,并生成符号表
- 在第二次扫描过程中,用第一次计算的标记值汇编指令,产生二进制指令
- 第一次扫描处理决定每个标记的地址,并生成符号表
- 标签处理过程:两次扫描
-
第一次扫描过程:
- 在扫描过程中,内存中的当前地址保存在程序
位置计数器(PLC)
中- PLC和PC的区别:PLC不用于程序的执行,只对程序进行一次扫描处理。PC在一个循环中对程序要扫描多次。
- 如果指令一个标签开始,符号表中添加一个新元素,包括标记名称和标记值。
标记值即为PLC当前值。
- 相对地址的产生
- 标签值在汇编时可能并不能知道
- 标签以相对地址的形式保留
- 对外部标签的跟踪——使用外部标签不能产生完全的二进制指令
- 伪指令:不能产生指令
- ORG 设置程序位置
- EQU 将标记添加到符号表而不占用程序的内存空间
- 例如以下代码:
ADD r0,r1,r2 FOO EQU 5 BAZ SUB r3,r4,#FOO
- EQU伪操作添加一个名为FOO的值为5的标记到符号表中
- EQU没有使PLC向前移动,因此BAZ标记的值不变
- EQU能够用于定义符号化的值
- 例如以下代码:
- Data statements 定义数据块
- 在扫描过程中,内存中的当前地址保存在程序
示例:创建一个符号表
使用如下简单的ARM汇编代码ORG 100 label1 ADR r4, c LDR r0,[r4] label2 ADR r4,d LDR r1,[r4] label3 SUB r0,r0,r1
- 一开始的ORG语句告诉我们程序开始地址
- 处理下一条语句只需要移动PLC,
由于上一条语句是一个位操作没有内存值
,PLC的值不变
- 由于ARM指令是4个字长,所以PLC将每次增加4个单位
连接
- 将几个目标模块连接成一个可执行模块。连接器允许通过几个程序片段来组成一个程序
- 任务:
- 形成模块顺序
- 解决模块之间的标签
- 外部引用和入口点
- 入口点:定义标签的位置
- 外部引用:使用标签的位置
- 装载器的主要工作是根据入口点解析外部引用。
- 动态连接:
- 在运行程序时动态连接模块
- 所有执行程序共享一个库拷贝;
- 程序运行之前运行短的链接,把代码中用到的函数找到,并链接到程序中;
- 允许程序用新版本的库.
- 问题:引起程序启动的延迟
- 在运行程序时动态连接模块
装载
- 代码块必须放到内存中的绝对位置
- 首先,它要确定每个目标文件的开始地址。目标文件的
装载次序
由用户给定。给定了每个文件放入内存的次序和每个目标文件的长度,就可以计算出每个文件的开始地址 - 加载映射(Load map) 文件或者是连接器标记控制了模块的顺序
- 装载器将来自全部目标文件的符号表合并成一个大的符号表,然后编辑目标文件,把相对地址转成绝对地址。
- 首先,它要确定每个目标文件的开始地址。目标文件的
目标代码设计
- 嵌入式程序设计有些问题需要开发者解决
- I/O设备的中断向量表应放在特定位置;
- 设置内存管理表
- 全局变量必须放在所有用户都可访问的位置
- 为这些位置命名符号名称
- 连接器根据硬件平台给定绝对地址,修改程序的引用
- 解决可重入问题,许多程序应被设计为
可重入的
- 函数执行中被打断,打断者又调用该函数,应不改变打断的函数的返回值
- 一个函数在执行过程中被打断,并且打断者又一次调用此函数,这种打断和重复执行不改变这这些函数调用的返回结果,则这个函数就是可重入的。
- 如果程序改变了全局变量的值,发生递归时它可能会给出不同的答案
//不可重入的
int foo=1;
Int task( )
{
foo=foo+1;
return foo;
}
//可重入的
int task(int foo )
{
foo=foo+1;
return foo;
}
- 若一个程序置于内存不同位置据可执行,那么称之为
可重定位的
编译技术
- 编译策略:
编译=翻译+优化
- 编译决定了代码的质量
- 对CPU资源的应用
- 内存的调度
- 代码的大小
- APCS(ARM过程调用标准)
- r0-r3传递参数给过程,额外的参数放到栈中
- r0保持返回的值
- r4-r7保留寄存器的值
- r11是帧指针fp,指向栈底;r13是栈指针sp
- r10是指示栈界限的寄存器,以判断栈是否溢出。
// 编译调用过程的代码:y=p1(a,b,c,d,x)
ldr r3, [fp, #-32] ; get x, the fifth parameter
str r3, [sp, #0] ; put into p1()’s stack frame
ldr r0, [fp, #-16] ; put a into r0
ldr r1, [fp, #-20] ; put b into r1
ldr r2, [fp, #-24] ; put c into r2
ldr r3, [fp, #-28] ; put d into r3
bl p1 ; call p1()
mov r3, r0 ; move return value into r3
str r3, [fp, #-36] ; store into y in stack frame
- 语句的翻译和优化:
- 源代码翻译成中间格式,如CDFG;
- CDFG被转换和优化;
- CDFG在优化的基础上被翻译成指令;
- 指令被更进一步优化。
编译一个算术表达式
- 对于ARM:
- 寄存器选择
- 变量放入寄存器
- 存放中间结果的寄存器
a × b + 5 × ( c − d ) a\times b + 5\times (c-d) a×b+5×(c−d)
- 遍历节点即可得到ARM代码:
; operator 1 (*)
ADR r4,a
LDR r1,[r4]
ADR r4,b
LDR r2,[r4]
MUL r3,r1,r2
; operator 2 (-)
ADR r4,c
LDR r1,[r4]
ADR r4,d
LDR r5,[r4]
SUB r6,r4,r5
; operator 3 (*)
MUL r7,r6,#5
; operator 4 (+)
ADD r8,r7,r3
- 可以优化用过不会再用的寄存器,对其进行重用。ARM gcc编译器生成的代码如下:
ldr r2, [fp, #-16]
ldr r3, [fp, #-20]
mul r1, r3, r2 ; multiply
ldr r2, [fp, #-24]
ldr r3, [fp, #-28]
rsb r2, r3, r2 ; subtract
mov r3, r2
mov r3, r3, asl #2
add r3, r3, r2 ; add
add r3, r1, r3 ; add
str r3, [fp, #-32]
; assign
为一个条件结构创建代码
if (a+b > 0)
x = 5;
else
x = 7;
- 以上代码的CDFG如下:
- 可以通过
遍历CDFG创建控制流代码
,一个有序的CDFG遍历如下:
- 通过1-2-3遍历可得到如下ARM代码
ADR r5,a
LDR r1,[r5]
ADR r5,b
LDR r2,[r5]
ADDS r3,r1,r2
BLE l3 ;<=
LDR r3,#5
ADR r5,x
STR r3,[r5]
B stmtent
l3 LDR r3,#7
ADR r5,x
STR r3,[r5]
stmtend ...
- 1-2和3-4边不需要分支和标记,因为他们是直线型代码。
- 编译器生成的控制代码如下:
ldr r2, [fp, #-16]
ldr r3, [fp, #-20]
add r3, r2, r3
cmp r3, #0
;test the branch condition
ble .L3
; branch to false block if <=
mov r3, #5 ; true block
str r3, [fp, #-32]
b .L4
; go to end of if statement
.L3:
; false block
mov r3, #7
str r3, [fp, #-32]
.L4:
数据结构
- 不同的数据结构类型有不同的数据结构布局
- 编译器要将数据结构的索引翻译成对原始内存的索引。一些数据结构的地址计算
在编译时进行
,其它的则在运行时进行 - 数组下标可变,因此数组元素的地址一般要在运行时计算
- 考虑一维数组 a[i] ,可以创建一个指向数组头部的指针 aptr ,那么对于 a[i] 的读取可以写为*(aptr+i)
- 二维数组一般采用行优先的排列形式,要求更复杂的寻址。如果数组 a[ ] 的大小时N * M ,那么我们可以
将二维数组的访问转化为对一维数组的访问
。即 a[i,j] 变成 a[i*M+j] ,其中 j 的最大值为 M-1
- 结构体中的每个数据域都是静态偏移
struct {
int field1;
char field2;
} mystruct;
struct mystruct a, *aptr = &a;
编译器优化
表达式简化
- 常数求解
- 8+1=9
- 算术表达式
- ab+ac=a*(a+b)
- 强度化简
- a*2=a<<1
过程内联
- 删除内联函数
// old
int foo(a,b,c) { return a + b - c;}
z = foo(w,x,y);
//new
z = w + x - y;
循环的转换
- 目的:
- 减少变量迭代和循环条件测试次数,减少循环的开销
- 为流水增加机会
- 提高内存系统的性能
循环展开
- 减少循环开销,增强优化的可能性
for (i=0; i<4; i++)
a[i] = b[i] * c[i];
- 若N=4,则可展开为:
a[0] = b[0] * c[0];
a[1] = b[1] * c[1];
a[2] = b[2] * c[2];
a[3] = b[3] * c[3];
- 不将循环完全展开,只展开两次:
for (i=0; i<2; i++) {
a[i*2] = b[i*2] * c[i*2];
a[i*2+1] = b[i*2+1] * c[i*2+1];
}
- 此时循环体两行内的所有操作都是独立的,在编译的后期可以创建在CPU流水线上有效执行的代码。
循环合并(loop fusion)
- 将两个或多个循环合并成一个循环
- 循环次数必须相同
- 循环体之间不能有在一起执行时可能会冲突的依赖性。
// old
for (i=0; i<N; i++) a[i] = b[i] * 5;
for (j=0; j<N; j++) w[j] = c[j] * d[j];
//new
for (i=0; i<N; i++) {
a[i] = b[i] * 5; w[i] = c[i] * d[i];
}
- 循环分解(loop distribution) 与循环合并相反,它把一个循环分解为多个循环。
循环分块(loop tiling)
- 将一个循环拆分成一系列嵌套的循环。
- 循环分块改变了数组元素访问次序,可以更好地控制cache的行为。
-
数据填充(array padding) 向循环中添加填充数据以改变数据在高速缓存中的布局。
- 在循环执行过程中可以减少高速缓存冲突的次数
死代码删除
- 死代码 就是永远都不会被执行的代码
#define DEBUG 0
if (DEBUG) dbg(p1);
- 死代码可以通过可达性分析(寻找可到达的其他语句或指令)来确定。
寄存器的分配
- 目标:
- 选择变量(包括声明的和临时变量)在寄存器上的分配以减少所需的寄存器数
- 确定变量在寄存器中的时间
- 基本情况
- 生命周期图
- 寄存器数目
w = a + b;
x = c + w;
y = c + d;
- 可以通过画一个冲突图(conflict graph) 并解决一个着色问题来解决寄存器分配问题。
- 不同的装载、存储和算术操作次序可能在流水线上导致不同的执行时间。
操作调度(operator scheduling)
- 操作调度目的是改善寄存器分配
- 考虑如下代码:
w=a+b;
x=c+d;
y=x+e;
z=a-b;
- 它的生命周期图如下:
- 重新排序后所需寄存器的数目减少到三个:
w=a+b;
z=a-b;
x=c+d;
y=x+e;
- 指令的调度
- 非流水线机器不需要指令的调度:
- 以任何满足指令依赖行的指令顺序执行
- 在流水线机器里,一条指令的执行时间与就近指令有关(包括指令的操作数、操作码)
- 非流水线机器不需要指令的调度:
预约表(reservation table)
- 用于追踪CPU的资源使用
- 行:指令执行时间
- 列:被调度的资源
- 调度可使用多种不同的算法
- 依赖于资源和指令的类型
软件流水(software pipelining)
- 若指令比正常的时间周期多的时间完成,出
现延迟而降低性能。 - 软件流水是一种对指令重新排序的技术
- 向循环体内添加下一次迭代的指令
- 选择实现每一条操作的指令
- 通过循环迭代减少流水线中的延迟
模板匹配(template matching)
- 是一种有用的代码创建技术
- 有几种方式来完成一个操作或一系列操作
- 可用图表示操作,图上匹配可能的指令