嵌入式系统设计|程序设计与分析(上)

文章目录

嵌入式程序组件

考虑三种广泛应用于嵌入式软件的结构或组件的代码,这三种结构或组件分别是:状态机,循环缓冲器,队列。

状态机

  • 状态机通过状态来表示系统的内部特性,状态的变化是基于输入的变化。
  • 应用:
    • 面向控制的代码;
    • 响应式系统;
    • 非周期性采样作为输入

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个输入。
      嵌入式系统设计|程序设计与分析(上)
  • 循环缓冲区(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)

  • 是一种有用的代码创建技术

嵌入式系统设计|程序设计与分析(上)

  • 有几种方式来完成一个操作或一系列操作
  • 可用图表示操作,图上匹配可能的指令
上一篇:C程序的内部机制


下一篇:mysql视图和临时表的区别