FPGA图像处理算法的编译与优化

SA-C语言可支持计算机视觉和图像处理,并可将程序快速编译到FPGA。在编译过程中,SA-C算法首先被转换成非递归的数据流图(DFG),然后再转换成VHSIC硬件描述语言(VHDL),最后借助商用编译器将VHDL转换成FPGA配置,为FPGA在图像处理领域的应用提供了一个设计平台。

最近,图像处理业界意识到现场可编程门阵列(FPGA)具有强大的并行处理和计算能力。例如,FPGA已用于实时特征点追踪和基于声音及色彩的目标检测中。然而,由于在电路设计语言中很难执行复杂的算法,因此许多计算机视觉研究员都不愿采用FPGA,少数采用了FPGA的设计师却在繁琐的修改或组合FPGA电路中屡屡受挫。可重配置系统通常从硬件电路设计开始,然后经过编程变为软件算法,为此,我们开发了SA-C语言。

SA-C语言是一个C语言变种,它的特点是每个变量只赋值一次,可在图像处理应用中同时进行中精级(循环级)和细精级(指令级)并行处理。简言之,SA-C语言和标准C语言之间有三点不同:1)SA-C比C语言中的数据类型多,以便开发各种比特位的精密逻辑电路；2) SA-C对C语言中的控制结构进行了扩展,可通过并行循环机制和真正的多维矩阵来支持图像处理；3)SA-C对C语言进行了约束,以避免编程者使用与FPGA无法完全映射的冯·诺伊曼结构存储器。经验表明,熟悉C语言的编程者会很快地学会SA-C语言。

SA-C数据类型

SA-C中的数据类型有符号整数、无符号整数和定点数等,用户可自行定义数据位长度。例如,unit8定义的是一个8位的无符号数,fix12.4则是一个定点数,它带有一个符号位、七个整数位和四个小数位。SA-C中也有浮点数和双精度型数,分别为32位和64位,逻辑值型(bool)和位(bit)型数则可以没有数字位。此外还可将这些基本的数据类型组合成为复杂的数据类型。SA-C是一种单赋值语言,它在定义变量的同时为变量赋值。例如,在uint12c=a+b这一语句中,既定义了数据类型又为它赋了值。

SA-C具有多维矩阵结构,矩阵长度在程序执行过程中动态定义(不过编程人员也可进行静态定义)。类型定义语句int14 M[:,6]表示矩阵M有14位符号整数。其中第一维长度是动态定义的,用户将第二维长度静态地定义为6。SA-C中的矩阵可通过程序语句进行分区或分段,这点与Fortran 90[6]相似。例如:表达式A[:i]返回矩阵A第i列的数据值。

SA-C中的循环

SA-C语言中最重要的部分是for循环语句。SA-C语言中的循环返回一个或多个值(当循环是一个表达式时),并包括三个部分:一个或多个生成器、一个循环体及一个或多个返回值。生成器生成矩阵访问表达式,这些表达式十分简洁,便于编译器分析。最为有趣的是窗口生成器,它可从源矩阵中提取出子矩阵。以下是用SA-C编写的中值滤波器例子:

uint8 R[:,:] =

for window W[3,3] in A {

uint8 med = array_median (W);

} return (array (med));

For循环由从矩阵A中提取出来的3×3子矩阵驱动。我们从A中提取所有可能的3×3子矩阵,每个子矩阵均执行一次循环。循环体使用SA-C内建的运算符来获取子矩阵的中值。循环返回一个由中值构成的矩阵,矩阵的长度由矩阵A的长度和循环生成器决定。SA-C的生成器可以从源矩阵中以任意大小的窗口抽取一块矩阵元素；以任意长度抽取一段矩阵元素或按任意间隔抽取一些矩阵元素,因此源代码通常无需执行任何矩阵索引。

SA-C对C语言的约束

与C语言相比,SA-C补充了单赋值语句,同时去除了指针和递归函数(自调用函数)。因为指针可以任意访问存储器,不利于编译时的分析。SA-C去除了指针,使数据的依赖关系更为清晰,同时编译器可以容易地确定指令级并行处理。此外它还清理了数据存取模式,因此更容易确定并支持循环级并行处理。

在图像处理中,指针最常用的功能是对大型矩阵进行迅速地存取,由于SA-C采用多维矩阵和并行循环机制,因此可以无需指针。SA-C还去除了递归函数。FPGA没有冯·诺伊曼结构的处理器,因此也没有调用堆栈；它采用的是一系列可编程逻辑模块,模块间可通过软件编程进行互联。因此,程序必须映射到逻辑电路中。尽管一些递归程序可嵌入到循环中,但SA-C仍禁用递归函数,以确保程序与电路的映射过程不致过于复杂。

人们往往会错误地理解SA-C的单赋值概念,至少那些对功能性语言不太熟悉的读者会如此。在SA-C中,每个变量只能进行一次赋值。SA-C中的变量可重复使用,因此,表达式b=b+1是正确的；这个表达式创建了一个新的变量b,它的初始值是原来的变量b加上1,两个变量b的类型一致。

对单赋值概念而言,最无法理解的是其控制语句。由于变量不能重新赋值,如果在某个条件语句中对一个变量赋值的话,就有可能出现引用未初始化变量的错误。为了弥补这一点缺陷,所有的控制语句(if,for等)都有返回值,而且可能是多个返回值。因此,编程者无需在条件语句中为变量赋值,而是通过创建一个条件判断语句来返回计算值或缺省值,或将条件语句的结果指定为一个变量。不过SA-C中有一种下传(nextified)变量,它可将一次循环中的值代入下一次循环中。

单赋值可在程序的变量和电路的连线间建立一一对应的关系,这便是SA-C中增加这一限制的原因。变量的值不会改变,也就无需为它们分配存储器。每个运算符都是一个子电路,它们运算的变量则是输入连线。因此,我们很容易从SA-C中生成VHDL电路,编程者也易于理解这种映射关系,然后编写可迅速转换成电路的SA-C程序。

编译器架构

SA-C编译器既可用于传统的处理器(用于调试)或传统主机处理器和可重配置处理器的组合。当用于可重配置系统时,SA-C将并行的循环编译成FPGA的逻辑电路。不在循环中的序列码则编译成C语言用于主机处理器,SA-C编译器还可以生成C语言代码,将FPGA的配置和数据下载到处理器中,再从处理器中读回结果。将循环编译成电路时,它先将SA-C代码转换成数据流图,然后转换成用VHDL描述的逻辑电路。我们可通过商用VHDL编译器将这些电路映射到FPGA配置中。

数据流图

SA-C编译器将for循环和while循环转换成数据流图,这些数据流图可视为不包含时序信息的硬件电路提取图。数据图中的节点通常是算法节点、低级控制(如选择合并)节点或阵列访问/存储节点；边缘则是与变量相对应的数据路径。我们可采用数据流图仿真器进行验证和调试。

以下的SA-C程序块将一个图形与一个3×3的Prewitt垂直边缘检测掩码进行卷积运算:

int16[:,:] main(uint8 Image[:,:])

int16 H[3,3] = { {-1, 0, 1},

{-1, 0, 1},

{-1, 0, 1}} ;

int16 R[:,:] =

for window W[3,3] in Image {

int16 iph = for h in H dot w in W

return( sum(h*(int16)w) );

} return( array(iph) );

return R;

这些代码的数据流图如图1所示。因为内部循环可以展开,SA-C编译器将这个嵌套结构中的两个循环转换成一个数据流图。每次循环时,靠近图形顶部的窗口生成器节点从Image矩阵的3×3窗口中读取元素,当这个数据窗口流经图形时,便执行与H的卷积运算。值得注意的是,代码中的乘法运算要么通过与0或1相乘被编译器去除了,要么通过乘以-1转换成了否定运算符。这便是传播常数和常量折叠(constant folding)的结果。因此,每次循环中的九次乘法运算和八次加法运算被三次否定运算符和五次加法运算取代了。

SA-C编译器

SA-C编译器可进行各种数据流图优化,其中一些方法是传统的,一些则是专门设计用于优化可重配置硬件中的SA-C程序。

传统的优化方法包括通用子表达式删除、常量折叠、常量移动及死码删除。专用优化方法是从循环分段、矩阵值传播、循环融合和循环展开、功能内联、查找表、矩阵分块和循环下传(Loop Nextification)以及循环和矩阵长度传播分析中变化而来的。其中一些方法关系密切,在此作简单描述。由于SA-C主要用于FPGA,编译器会将所有的内循环展开,获得非重复代码模块,更易于转换成数据流图(DFG)并最终转换成逻辑电路。编译器通过DFG传播矩阵长度,并在可能的时候推断长度,以便帮助确定展开的时机。由于SA-C与矩阵和循环的密切关系,这样是可行的。由于编译器仅将底层的循环转换成DFG,通过全循环展开可将高级循环变成低级循环,以便转换成DFG。

SA-C编译器还进行循环分段,然后进行全循环展开,产生多维局部循环展开的效果。例如,我们可在中值滤波器中加入一个循环分段程序:

uint8 R[:,:] =

// PRAGMA (stripmine (6,4))

for window W[3,3] in A {

uint8 med = array_median (W);

} return (array (med));

这个程序将已有的循环嵌入到一个带有6×4窗口生成器的新循环中。然后用循环展开取代了含有八个中值代码块的内部循环,得到一个包括了6×4个子矩阵的循环。这个循环并行地计算八个3×3中值。SA-C编译器可融合一些带有生产者/消费者(producer/consumer)关系的循环。例如,在下列的代码中,中值滤波器后面带有一个边缘检测器。

第二列为FPGA的时钟速率(与电路有关)。第三列是处理速度,不包括数据传输时间,单位为兆像素/秒。第四列是包括了数据传输时间的处理速度。第五列是可重配置逻辑模块(CLB)的用量。

uint8 R[:,:] =

for window W[3,3] in A {

uint8 med = array_median (W);

} return (array (med));

uint8 S[:,:] =

for window W[3,3] in R {

uint8 pix = prewitt (W);

} return (array (pix));

其中,prewitt被用户定义为一个单独的功能。编译器会嵌入这个功能调用,并将这一循环融合到一个单循环中,后者在矩阵A中对5×5窗口进行运算(值得注意的是,5×5窗口应提供必要的元素,用来计算S的一个值)。新的循环体有九个中值代码体和一个prewitt代码体。融合的主要目的是减少协处理器的局部存储器和FPGA之间的数据通信。

上面所述的循环融合进行中值的冗余计算。由于中值计算是并行处理的,因此如果FPGA有足够空间,这并不成问题。在空间紧缺时,循环下传便会将一次循环中计算所得的中值传到下一次循环,将行的冗余计算省略掉。在上述例子中,执行这一操作可将循环体减少到三个中值和一个prewitt。在经过循环下传后,如果FPGA空间足够,融合的循环便会进行分段,以减少循环次数。

VHDL提取架构

传统的处理器通常给用户提供一个经过严格定义的小型指令集,而FPGA等可重配置处理器却由大量无规律的逻辑单元组成,逻辑单元间可通过各种方式进行互联。为了控制编译器需要适应的硬件环境种类,我们定义了一个抽象计算机结构,它可提供与硬件无关的目标模型。

如图2所示,SA-C程序的数据流图有三个部分。第一部分是一个或多个数据生成器,它们从协处理器的局部存储器中读取数据,并按一定的顺序将其置于循环体中。第二部分是程序的主要计算区,称为内部循环体(ILB)。第三部分有一个或多个数据收集器,对ILB的计算值进行缓存并将其写入到存储器中。

由于生成器和收集器均可对数据进行缓存,整个系统就相当于一个三级流水线。在生成器从存储器读取新的数据时,ILB处理来自上一个时序的数据,而采集器则将再上一个时序的结果写入存储器。目前,ILB是完全可以组合的；所有的时序都由数据生成器负责产生,它的输入则来自采集器。不过,今后计划要对ILB进行流水线优化。

从DFG到VHDL的转化包括两个主要步骤。穿过DFG后,ILB的每个节点都转换成VHDL。多数DFG节点执行简单的运算,如数学或逻辑运算。这些DFG节点与VHDL语句有着一一对应的关系。在矩阵加法(array sum)等更为复杂的运算中,转换器产生一个与预定义VHDL元件之间的连接。这些VHDL元件库使SA-C编译器可以快速直接地访问硬件进行复杂的运算。当ILB完全转换成VHDL后,用循环生成器和提取到的节点从元件库中选择正确的元件,并用DFG中提取的数据进行赋值。ILB和生成器/收集元件间的互联关系由顶层VHDL模块生成,这个模块也由转换器产生。

循环生成器的作用是将数据以正确的顺序置入ILB中,并提供必要的信号来控制收集器中的结果缓存中的运算。从存储器中读出的数据放置在移位寄存器中。每执行一次循环,最旧的一列数据便从移位寄存器中移出,同时移入一列新数据。这些移位寄存器提供了一个数据“滑行窗”,而这些数据可作为ILB的输入。反之,收集器接受ILB的输出,将其按字进行缓存,然后写入结果存储器中。当所有DFG全都转换成VHDL后,便可采用商用VHDL编译器和布局布线工具对代码进行处理。这些工具生成最终FPGA配置文件,然后下载到可重配置处理器中进行执行。

图像处理运算器

我们用一个包含22个图像处理程序的库来演示SA-C语言及其最优化的编译器。选用这些程序并没有什么特殊目的,不过通过它们可了解矢量、信号和图像处理库VSIPL()和英特尔图像处理库(IPL;； s/libraries/)。

表1所示为包括或未包括主机到可重配置处理器间的数据传输时间时,每个程序的处理速率(以兆像素/秒为单位)。值得注意的是,当在图像流中使用图像处理运算器时,数据传输会与处理交迭进行,从而得到最大的持续吞吐率,如第三列中所示。当运算器用于隔离图像时,必须包括数据传输时间,此时的吞吐率如第四列所示。表1还给出了电路的尺寸(以逻辑模块的数量来计算),如第五列所示。以及FPGA的时钟速率,这是一项关于电路关键路径长度的功能,如第二列所示。所有的时序均与一个300×198的8位测试图像有关。

表1中的多数程序都应该是自注释的。双值运算符(dyadic operator)的输入为两个图像,而单值运算符需要一个图像和一个常量。标注有“window sum of diffs”的程序是双值运算,它的输入为两个图像,它计算两个图像的宽度差别,将这些差值相加后与一个门限比较。这一程序取自MP4图像压缩标准的一个应用。

许多程序都是相互之间的变体。例如,卷积程序将一个图像和一个尺寸已知的未知掩码进行卷积运算。卷积的源代码已知如下。它返回一个无符号的20位数,以便保证不会溢出。将掩码的尺寸限制为已知是必要的,这样SA-C就知道应生成一个多大的电路。同时它还可展开内部循环(内循环执行图像窗口和掩模的点积运算)。如表1所示,卷积程序可以每秒9.7兆像素的速率将一个8位的图像与一个3×3的8位掩模进行卷积运算,并产生一个20位的结果。

========================

.uint20 [:,:] main (uint8 image[:,:], uint8

kernel[:,:])

{ // ***** computes the gradient for the image

*****

uint20 res[:,:] =

for window win[3,3] in image

{ uint20 val =

for elem1 in win dot elem2 in kernel

return(sum((uint20)elem1*elem2));

}

return(array(val));

} return (res);

========================

高斯滤波器便是一个与固定掩码的卷积运算,因此编译器可使用传播常数和折叠常数。通过这些优化,可去除循环中的许多数学运算并生成更小的电路。这些优化将高斯滤波器的尺寸减少到725个逻辑模块(通常的卷积运算会有1,333个)。但由于两种运算都与I/O口有关,因此这些优化并没有显著地增加吞吐量。不过,由于电路尺寸变小,高斯滤波器可进行分段,增加了并行处理量并减少了从存储器读取的总字节数。通过分段,高斯滤波器的吞吐量每秒增加了2到18兆像素。表1中的数据是在没有分段的情况下获取的。

另一种常见关系是先后顺序。从形态学上来说,开(open)和闭(close)运算符是简单的腐蚀(erode)和膨胀(dilate)运算符的组合。例如,开运算符的定义是先执行膨胀运算,然后执行腐蚀运算。而闭运算符正好相反。因此,在某种情况下可用开运算符来取代循环融合:膨胀循环可以与腐蚀组合。

通过每次更为频繁地读取一个数值,垂直矩阵分段可减少输入。例如,在3×3滑动窗口中,每个像素点读三次；如果将同一个程序分段成4×3的窗口,则每个像素只需对其后的循环读两次。因此,开运算所用时间仅为膨胀运算的79%,然后再单独做一次腐蚀运算。当一个循环可以简化另一个循环时,循环融合的效果更为显著。

表1中的prewitt运算符不仅仅包含卷积运算,它将图像与垂直和水平的边缘掩码同时做卷积运算,然后计算平方根。事实证明,prewitt运算中大部分成本用于最后的平方根计算上。当prewitt后面为门限运算符时,循环便可融合。当prewitt后接的门限集用来传输通过大于或等于128的值时,仅需要保留平方根结果的最高位。因此,我们可去除大部分平方根电路,使电路更小,运行更快。这一优化可将“prewitt+门限”的吞吐量提高56%。

本文小结

通过修改C语言并创造出SA-C语言,我们获得了一种更高级的数学编程语言,并可直接映射到现场可编程门阵列(FPGA)中。在用数据流图进行中值计算的演示中,我们采用了许多有效的优化方法。最终获得的系统使得编程者可以迅速地编写图像处理算法,并将它们映射到可重配置计算机中,通过简化传统的高级编程来实现专用硬件的性能。

作者:Bruce Draper, Walid Najjar

科罗拉多大学计算机科学系

Email: draper@, najjar@