电子工程专辑
UBM China

运用SAD算法降低FPGA资源利用率

上网日期: 2011年08月03日 ?? 作者: Sharad Sinha ?? 我来评论 字号:放大 | 缩小 分享到:sina weibo tencent weibo tencent weibo


打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

1.扫描左侧二维码
2.点击右上角的分享按钮
3.选择分享给朋友

关键字:FPGA? SAD? RTL?

比RTL更胜一筹

“更高层次的抽象概念”是指比RTL更高级别的设计描述,可在RTL准备好前对要实施的应用进行分析。如果可以通过分析应用来了解其内在并行性,则在RTL设计中也可以这样做。此外,对应用的数据流程图进行分析有助于设计资源共享的实施。

数据流程图能提供关于应用数据流的信息。数据从一个运算流向另一个运算,因此在运算之间可能存在着数据依赖关系。不相互依赖的运算可以并行执行。不过并行执行几乎总是造成很高的资源占用率,而目标是降低资源占用率,所以暂不讨论并行执行这种模式。

下面将以绝对差值和(SAD)算法为例,介绍如何从比RTL更高层次的抽象层分析资源共享,让资源占用率比依赖RTL设计中的互斥任务的方法更低。

SAD是MPEG-4解码器动作估计部分中的一种重要算法,也能用于物体识别。在这种以像素为基础的方法中,图像区块中每个像素的值都与另一幅图像中相应像素的值相减,以确定该图像的哪些部分从一帧移到了另一帧。如果图像区块大小为4x4,则最后会将全部16个绝对差值相加。在开源xvid解码器的sad.c文件末尾有代码示例。

图3显示了用这一算法处理一个4x4图像区块时的数据流图(DFG)。这些减法运算可以并行,因为其中的减法运算不依赖于其它任何减法运算。但由于目的在于降低资源占用率,所以并不采用并行执行模式。而是采用一种称为基于扩展兼容路径(ECPB)硬件绑定的资源分配和绑定算法。

运用SAD算法降低FPGA资源利用率(电子工程专辑)
图3:SAD算法的数据流图。

资源的分配和绑定主要是指为DFG中的运算分配加号、乘号等资源,然后将这些资源绑定到运算,以便降低器件的资源占用率、提高最大时钟频率,或同时实现两者。原则是在最终设计符合功能限制的前提下缩小面积。此算法可以检测已调度的DFG(即其运算已在不同步骤或时钟周期中进行了调度)中各运算间流程的依存关系,并分析出运算内部(intra-operation)流程的依存关系。

此算法将可并行的运算调度在同一时间步骤中,并将需要依赖于其它运算数据的运算调度到不同的时间步骤中。它为已调度DFG中的每种运算都建立了一个加权的有序相容图(WOCG)。因此,减法运算有一个WOCG,加法运算则有另外一个WOCG。这种方法使用了加权关系Wij =1+α×Fij +β×Nij +y ×Rij来为WOCG中的各边(edges)分配权重。在这里,Wij即同类型的i和j运算之间的权重值。Fij是流程依存关系的权重值,而Nij是运算i和j之间的共模输入数量。如果运算i和j的输出结果可以存入同一个寄存器,则Rji的值为1,否则即为0。在本例中,将调整参数数α、β和γ的值分别设为1、1和2。

接下来的步骤是用最长路径算法找出WOCG中使用的最长路径。该最长路径中的全部运算都被映射到同一运算器。将绑定运算从WOCG中移除后,重复最长路径和映射流程,直到处理完所有WOCG。由于这种算法会将多个运算映射到同一资源或运算器,所以运算器的容量相当大,足以满足最大规模的运算。在实施SAD方法的例子中,8位数据(灰度图像)处理了全部减法运算,因此,减法运算器的输入宽度是8位。我们将负责迭代计算SAD和的累加运算器位宽设定为23位和8位。

图4显示了实施的SAD算法的数据路径。在这个设计中只使用了一个减法器和一个加法器/累加器。各个运算之间有着非常多的资源共享。如果直接在RTL行为层描述设计,这种资源共享将不可能实现,因为SAD算法中不存在互斥的任务。生成这个数据路径后,可用加法器、减法器和乘法器模块分层实施设计。这一包含模块实例化的实施方法比行为化的方法结构更为明晰,并且与后者的数据路径非常相似。

运用SAD算法降低FPGA资源利用率(电子工程专辑)
图4:采用SAD算法的数据路径。

在以数据为主导的大型应用中,在更高层次进行此类预处理有助于降低资源占用率。此外,这种方法也很容易实现自动化。


?第一页?上一页 1???2???3?下一页?最后一页





我来评论 - 运用SAD算法降低FPGA资源利用率
评论:
*? 您还能输入[0]字
分享到: 新浪微博 qq空间
验证码:
????????????????
?

关注电子工程专辑微信
扫描以下二维码或添加微信号“eet-china”

访问电子工程专辑手机网站
随时把握电子产业动态,请扫描以下二维码

?

5G网络在提供1Gbps至10Gbps吞吐量方面具有很好的前途, 并且功耗要求比今天的网络和手机都要低,同时还能为关键应用提供严格的延时性能。本期封面故事将会与您分享5G的关键技术发展,以及在4G网络上有怎样的进步。

?
?
有问题请反馈
推荐到论坛,赢取4积分X