海风 的blog

FPGA上如何求32个输入的最大值和次大值:分治

上午在论坛看到个热帖,里头的题目挺有意思的,简单的记录了一下。

0. 题目
在FPGA上实现一个模块,求32个输入中的最大值和次大值,32个输入由一个时钟周期给出。(题目来自论坛,面试题,如果觉得不合适请留言删除)

从我个人的观点来看,这是一道很好的面试题目:

其一是这大概是某些机器学习算法实现过程中遇到的问题的简化,是很有意义的一道题目;
其二是这道题目不仅要求FPGA代码能力,还有很多可以在算法上优化的可能;

当然,输入的位宽可能会影响最终的解题思路和最终的实现可能性。但位宽在一定范围内,譬如8或者32,解题的方案应该都是一致的,只是会影响最终的频率。后文针对这一题目做具体分析。(题目没有说明重复元素如何处理,这里认为最大值和次大值可以是一样的,即计算重复元素)

1. 解法
从算法本身来看,找最大值和次大值的过程很简单;通过两次遍历:第一次求最大值,第二次求次大值; 算法复杂度是O(2n)。FPGA显然不可能在一个周期内完成如此复杂的操作,一般需要流水设计。这一方法下,整个结构是这样的
1. 通过比较,求最大值,通过流水线实现两两之间的比较,32-16-8-4-2-1通过5个clk的延迟可以求得最大值;

MATLAB调用C程序、调试和LDPC译码

MATLAB是一个很好用的工具。利用MATLAB脚本进行科学计算也特别方便快捷。但是代码存在较多循环时,MATLAB运行速度极慢。如果不想放弃MATLAB中大量方便使用的库,又希望代码能迅速快捷的运行,可以考虑将循环较多的功能采用C编写,MATLAB调用。本文将概述这一过程。虽然本文以LDPC译码算法为例,但不懂该算法不影响本文阅读。

1. 起因
最开始用MATLAB写的LDPC译码算法中,其中一个版本是这里,里面有三重循环,运行速度极慢。后来考虑了MATLAB的向量化操作,通过算法的合理划分以及内置函数调用,成功将三重循环修改为1层,具体这一版本的代码可见这里。通过这一手段,函数的运行速度提高了几倍乃至几十倍。虽然这一方法下运行速度依旧比不过MATLAB工具箱中的comm.LDPCDecoder,远比不上利用GPU的comm.gpu.LDPCDecoder,但胜在可明确算法并具有一定扩展性。

起初也注意到可以通过MATLAB调用C程序来加速程序运行,但向量化后的代码凑活能用,加上有时也可调用更为强大的内置函数,这一想法一直没有付诸实践。这几天想好好整理一下代码,遂萌发了写一个C版本译码算法的想法。代码现在的状态是“能用”,这里把相关经验总结分析在此。

FPGA中的INOUT接口和高阻态

除了输入输出端口,FPGA中还有另一种端口叫做inout端口。如果需要进行全双工通信,是需要两条信道的,也就是说需要使用两个FPGA管脚和外部器件连接。但是,有时候半双工通信就能满足我们的要求,理论上来说只需要一条信道就足够了,而FPGA上实现这一功能的管脚就是inout端口。管脚相连时,input对应output,因此inout只能和inout连接(否则就不是inout了)。本文将概述FPGA的inout端口。

Exponential family: 指数分布族

Exponential family(指数分布族)是一个经常出现的概念,但是对其定义并不是特别的清晰,今天好好看了看WIKI上的内容,有了一个大致的了解,先和大家分享下。本文基本是WIKI上部分内容的翻译。

1. 几个问题

什么是指数分布族?

既然是”族“,那么族内的共同特点是什么?

为何指数分布族被广泛应用?是指数分布族选择了我们,还是我们选择了指数分布族?(这个问题没有回答,需要结合具体实例分析)

2. 参考
Exponential family. (2015, February 26). In Wikipedia, The Free Encyclopedia. Retrieved 05:00, April 3, 2015, from http://en.wikipedia.org/w/index.php?title=Exponential_family&oldid=64898...

3. 指数分布族: 定义
指数分布族指概率分布满足以下形式的分布

OFFSET IN使用举例

本文将结合具体实例阐述OFFSET IN的使用方法。注意:这是我第一次写OFFSET IN约束,本文仅供参考。阅读本文前需要了解时序收敛的基本概念,OFFSET IN和Period的相关知识,可先阅读时序收敛:基本概念,OFFSET约束(OFFSET IN 和OFFSET OUT)这两篇内容。

1. 分析

某器件(Device)有信号RXD0-RXD15,RKLSB,RKMSB需要输入到FPGA内,同时有与数据同步的RXCLK,数据为SDR输入。如下图所示,这是一个典型的源同步输入方式,需要给出OFFSET IN约束。

OFFSET IN的相关参数可以到与器件对应的Datasheet内寻找,该器件的输入满足以下关系。RXD0-RXD15,RKLSB,RKMSB在RXCLK上升沿到达前3ns有效,同时在上升沿之后保持3ns。(这一情况对应TXCLK=80MHz,TXCLK = RXCLK)

特殊约束From To

“A timing exception is needed when the logic behaves in a way that is not timed correctly by default.”

前面谈时序约束的时候,略去了Path specific exceptions。'Path specific exceptions'可以直接理解为特别指定的路径例外。我们自然希望软件帮我们做好绝大多数事情,既然存在这个例外,那么说明软件在知道了OFFSET 和 PERIOD之后,还有并不知晓的时序要求。所以这个时序要求需要我们人为指定。这可能有多种情况,一下分别说明(注意,From to 我也没用过,所以可能不对……)

多周期(Multi-Cycle)约束

Clock Skew , Clock uncertainly 和 Period

Intel 4790K的主频是4.0GHz,高通801的单核频率可达2.5GHz,A8处理器在1.2GHz,MSP430可以工作在几十MHz……这里的频率的意思都是类似的,这些处理器的频率都是厂商给定的。但是对于FPGA的工作频率而言却往往需要我们自己决定,在产品的设计初始就需要考虑FPGA工作在哪个频率,譬如250MHz。这个取值并不是瞎确定的,譬如如果定在1GHz,那显然是不可能的,有一本叫《XXXXX FPGA Data Sheet DC and Switch Characteristics》的手册给出了FPGA各个模块的直流供电特性和最高工作频率。这里给出的是理论工作上限制,Virtex-5各个模块工作频率最高大概在400-500MHz之间。当然还要考虑FPGA的输入clk了,即使有DCM等模块分频倍频,一般也不会选择一个很奇怪的分频比。

一旦工作频率确定下来之后,问题就来了。你所建立的工程是否能在这一要求的工作频率下正常工作?只需要在UCF文件内添加时钟的周期约束,Place & Route之后就可以得到结果了。约束满足了,很好;没有满足,可以改,如何修改将在Achieving Timing Closure中介绍。

谈到这里,有一个问题呼之欲出:除了器件本身的限制,还有什么会影响工作频率?下文将介绍相关概念。

OFFSET约束的写法(OFFSET IN和OFFSET OUT)

1. OFFSET约束的写法

Offset 约束定义了外部时钟pad和与之相关的输入、输出pad之间的相对关系。这是一个基础的时序约束。Offset定义的是外部之间的关系,不能用在内部信号上。

建立时间和保持时间(setup time 和 hold time)

建立时间和保持时间贯穿了整个时序分析过程。只要涉及到同步时序电路,那么必然有上升沿、下降沿采样,那么无法避免setup-time 和 hold-time这两个概念。

1. 什么是setup-time 和 hold-time
不论是在输入,输出或是寄存器-寄存器之间,只要设计到时钟上升沿/下降沿的采样,就会提到setup time 和 hold time。这两个指标说明器件本身不是理想的(时延等),正是这个不理想的特性,限制了工作时钟等。

Setup time is the minimum amount of time the data signal should be held steady before the clock event so that the data is reliably sampled by the clock. This applies to synchronous input signals to the flip-flop.

时序收敛基本概念

对于FPGA而言,时序收敛是一个很重要的概念。在我看来,时序约束是必要的,但不是在最重要的,我们应该在设计初始就考虑到时序问题,而不是完全的靠约束来获得一个好的结果。但我认为,对FPGA时序的分析能力是理解其运行机制的必要条件。之前也简单看过这方面的内容,却没有很正确的认识。这两天看了看UG612和相关内容,记录在此,这应该有一系列文章,希望不要烂尾。

1. FPGA时序的基本概念
FPGA器件的需求取决于系统和上下游(upstream and downstrem)设备。我们的设计需要和其他的devices进行数据的交互,其他的devices可能是FPGA外部的芯片,可能是FPGA内部的硬核(是否还能是其他的FPGA design?我的理解是,如果两个FPGA design和成了一个,那么ucf内的时序约束是要修改的)。

同步内容