嵌入式系统设计|程序设计与分析(上)
2021/6/5 20:21:38
本文主要是介绍嵌入式系统设计|程序设计与分析(上),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 嵌入式程序组件
- 状态机
- 循环缓冲区和面向流的程序设计
- FIR滤波器
- C编写的数字滤波器
- II型IIR 滤波器
- 队列和生产者 / 消费者系统
- 程序的模型
- 数据流图(DFG,Data flow graph)
- 控制/数据流图(CDFG)
- 汇编、连接和装载
- 汇编程序
- 连接
- 装载
- 目标代码设计
- 编译技术
- 编译一个算术表达式
- 为一个条件结构创建代码
- 数据结构
- 编译器优化
- 表达式简化
- 过程内联
- 循环的转换
- 循环展开
- 循环合并(loop fusion)
- 循环分块(loop tiling)
- 死代码删除
- 寄存器的分配
- 操作调度(operator scheduling)
- 预约表(reservation table)
- 软件流水(software pipelining)
- 模板匹配(template matching)
嵌入式程序组件
考虑三种广泛应用于嵌入式软件的结构或组件的代码,这三种结构或组件分别是:状态机,循环缓冲器,队列。
状态机
- 状态机通过状态来表示系统的内部特性,
状态的变化是基于输入的变化。
- 应用:
- 面向控制的代码;
- 响应式系统;
- 非周期性采样作为输入
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)
- 是一种有用的代码创建技术
- 有几种方式来完成一个操作或一系列操作
- 可用图表示操作,图上匹配可能的指令
这篇关于嵌入式系统设计|程序设计与分析(上)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)