用硬件加速隐式差分格式

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Accelerating Implicit Finite Difference Schemes Using a Hardware
  Optimized Tridiagonal Solver for FPGAs》
---
作者：
Samuel Palmer
---
最新提交年份：
2015
---
英文摘要：
  We present a design and implementation of the Thomas algorithm optimized for hardware acceleration on an FPGA, the Thomas Core. The hardware-based algorithm combined with the custom data flow and low level parallelism available in an FPGA reduces the overall complexity from 8N down to 5N serial arithmetic operations, and almost halves the overall latency by parallelizing the two costly divisions. Combining this with a data streaming interface, we reduce memory overheads to 2 N-length vectors per N-tridiagonal system to be solved. The Thomas Core allows for multiple independent tridiagonal systems to be continuously solved in parallel, providing an efficient and scalable accelerator for many numerical computations. Finally we present applications for derivatives pricing problems using implicit finite difference schemes on an FPGA accelerated system and we investigate the use and limitations of fixed-point arithmetic in our algorithm.
---
中文摘要：
我们提出了一种在FPGA上优化硬件加速的Thomas算法的设计和实现，即Thomas Core。基于硬件的算法与FPGA中的自定义数据流和低级别并行相结合，将总体复杂度从8N降低到5N串行算术运算，并通过将两个代价高昂的分区并行化，将总体延迟几乎减半。将其与数据流接口相结合，我们将内存开销减少到每N个待解决的三对角系统2个N长度向量。Thomas Core允许多个独立的三对角系统连续并行求解，为许多数值计算提供了一个高效且可扩展的加速器。最后，我们在FPGA加速系统上展示了隐式有限差分格式在衍生品定价问题中的应用，并研究了不动点算法在我们算法中的使用和局限性。
---
分类信息：

一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--

---
PDF下载：
--> Accelerating_Implicit_Finite_Difference_Schemes_Using_a_Hardware_Optimized_Tridi.pdf (437.81 KB)

2022-5-5 19:51:46 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Applications Acceleration Accelerating computations Quantitative

计算经济学第号手稿（将由编辑插入）使用硬件优化的FPGAsSamuel PalmerReceived:date/Accept:dateAbstract三对角解算器加速隐式有限差分格式我们介绍了在FPGA上优化硬件加速的Thomas算法的设计和实现，即Thomas Core。基于硬件的算法与FPGA中提供的自定义数据流和低级别并行相结合，将总体复杂度从8N降低到5N串行算术运算，并通过将两个代价高昂的分区并行化，将总体延迟几乎减半。将其与数据流接口相结合，我们将内存开销减少到每N个待解决的三对角系统的2N个长度向量。Thomas Core允许多个独立的三对角系统连续并行求解，为许多数值计算提供了高效且可扩展的加速器。最后，我们介绍了在FPGA加速系统上使用隐式有限差分方案解决衍生品定价问题的应用，并研究了定点算法在我们算法中的使用和局限性。关键词高性能计算·并行计算·FPGA·三对角矩阵·导数感谢David Thomas对这项工作的支持。1.引言1。1 FPGA现场可编程门阵列（FPGA）提供了一种集成电路，可以在现场或“现场”以芯片的形式配置。FPGA为开发和实施定制硬件设计提供了一种灵活且经济高效的方法。允许FPGA重新配置的核心组件是查找表。伦敦大学学院计算机科学PalmerDepartment，伦敦高尔街，WC1E 6BTE邮箱：ucabsdp@ucl.ac.uk（LUT）。

LUT根据数字输入产生一个或多个输出。这些功能在配置FPGA时确定，并提供通过可编程单元控制的所需逻辑。另一个有助于提高FPGA性能的关键组件是片上块存储器（BRAM），它可以提供快速的本地内存缓存。一些FPGA芯片还提供其他功能，如高速数字信号处理器（DSP）和乘法器。然后，FPGA芯片通常被嵌入电路板，并连接到其他外围设备，如DDR内存、USB端口、以太网、PCI express和VGA端口，以提供完整的异构计算系统。1.2有限差分格式和三对角系统有限差分（FD）格式是数值求解抛物型偏微分方程（PDE）的重要工具。在金融工程中，通常使用FD方法来求解偏微分方程，该偏微分方程对衍生工具进行建模，例如著名的布莱克-斯科尔斯方程（BSE）（Tavella和Randall，2000）。有限差分格式首先将问题域离散为时间间隔[0,1]上的网格/网格，在基本情况下，是资产价格间隔[0,Smax]。有几个变体和增强，但是我们现在描述一维的基本隐式模式。该域被离散为N个资产价格步和Mtime步，如下所示： S=SmaxN（1） t=M（2）空间导数项用中心差分近似，时间导数用后向差分近似。然后将这些离散化替换为偏微分方程，生成离散差分方程。例如，BSE给出：Vmn=anVm-1n-1+bnVm-1n+cnVm-1n+1（3）与问题相关的模具系数值an、bn、cn。

由此产生的方程组可以写成矩阵形式asAVt-1=Vt（4）这个矩阵求逆问题涉及求解价格向量Vt-1在当前时间步，向量vt已知于前一隐式步骤。系数矩阵A呈带状三对角形式，如下所示：=bc0。。。ABC00。。。0 abc0。。。0 abc0。。。。。。0 ... 0万亿（5） 或者更一般地写为矩阵求逆问题Ax=y。当Pricing多维导数（如篮子期权或随机波动率下）时，可以使用另一类称为交替方向隐式方案的有限差分方案（Peaceman和Rachford，1955）。这些方案在多个维度内以隐式方式解决PDEin问题。这些方法在计算上具有挑战性，因为它们需要在每个时间步求解多个三对角系统，因此，重要的研究工作已经投入到创建诸如GPU（Dang等人，2010）（Egloff，2011）等设备的快速并行求解器上。1.3 Thomas算法1 Thomas算法（a，b，c，y）伪编码[0]=b[0]z[0]=y[0]对于i=1到N doprev=i-1li=a[i]/d[i]=b[i]-li*c[prev]z[i]=y[i]-li*z[prev]end-forz[N]=d[N]=d[N]forreturn x[i]托马斯算法（Thomas，1949）是求解对角方程组的最简单方法，通常用于CPU等串行设备。Thomas算法是高斯消去法的一个特例，可以从矩阵a的LU分解中导出。这将系统简化为两个双对角系统的解，然后通过高斯消去法求解。第一个系统通过正向代换求解，第二个系统通过反向代换求解。这两个阶段将被称为正向迭代和反向迭代。

Thomas算法在算法1中给出，如图所示。1托马斯算法正向迭代的数据依赖图的复杂度为O（N），需要总共8N次算术运算来求解anN三对角系统。在并行计算中，与递归加倍（Stone，1973）、循环归约（Hockney，1965）和并行循环归约（Hockney和Jesshope，1981）等算法相比，Thomas算法通常不太受欢迎，而这些算法有更多的算术运算，一些操作可以在GPU等设备上并行（Zhang等人，2010），从而整体降低了算法复杂度。最近，随着人们对FPGA加速越来越感兴趣，人们尝试将三对角解算器移植到FPGA上（Oliveira等人，2008年；Warne等人，2012年，2014年；Chatziparaskevas等人，2012年）。在这种应用中，Thomas算法的简单性使其非常适合与循环减少相比的任务，循环减少对于高效的数据流FPGA实现来说可能过于复杂。2算法优化和低级并行图1和图2描述了Thomas算法的数据依赖性。我们观察到，在正向迭代中，有两个单独的计算分支要计算，这表明了一级并行性。奥利维拉等人（奥利维拉等人，2008年）和沃恩等人（沃恩等人，2012年）也采取了类似的方法。这种优化将有效的串行算术运算从8N减少到6N。这种简单优化的问题在于，虽然串行操作有所减少，但这些都是减法或乘法，与除法相比，它们是计算堆。因此，与CPU等快速锁定设备相比，可能无法获得具有竞争力的加速（Warne等人，2012年）。

因此，我们产生了一个简单的算法重排，可以允许向后和向前迭代的两个分区有效地并行。等式6显示了反向迭代计算的因式分解，我们现在在这里处理FIG。2托马斯算法向后迭代的数据依赖图Fig。3针对针对FPGA实现优化的拟议Thomas算法结构的数据依赖关系图。Zn和Cn的划分按Dn单独划分- cnVn+1dn=dnzn- （dncn）Vn+1。（6） 在串行实现中，这会给算术运算的总数增加一个额外的除法，这通常是不可取的，但如图3所示，在这个框架中，数据依赖性实际上减少了。事实上，我们现在可以并行处理这两个划分，也可以并行处理前向迭代计算。这将串行算术运算从原来的8N减少到5N。对于FPGA实现，这种重新排列的算法有两个优点：1。通过将两个长度分段并行化，该算法的总延迟几乎减少了一半。2.内存需求从需要保存三个中间数据向量（c、z和d）减少到两个（c/d和z/d）。2.1流水线进一步到低级算法优化高级并行可以通过两种方式实现：通过向前和向后迭代计算流水线数据；以及在向前和向后迭代之间对数据集进行管道化，这通常用于多个CPU版本，以并行化Thomas算法（Duff和van der Vorst，1999）。首先，计算单元本身可以进行深度流水线，Olivera等人（Oliveira等人，2008年）使用这种方法，允许在同一迭代周期内计算多个独立的三对角系统。

例如，如果前向迭代计算单元具有PFpipeline阶段，则在一次迭代中，可以为管道的每一阶段填充一个计算，从而计算出独立于PFpipeline的三对角系统。第二种类型的流水线是，对于任一迭代，给定一组流水线三对角系统，如上所述，我们可以在一个Thomas解算器中独立地同时计算两个不同集合（第一个集合已经通过正向迭代）的正向和反向迭代。在（Warne等人，2014年）中，作者研究了使用OpenCL和Xilinix HLS来建造Thomassolvers，但由于涉及复杂的管道调度，因此没有获得这种水平的并行性。为了实现所需的低电平控制，我们用VHDL实现了这种设计。2.2硬件架构解算器核心的输入由5个数据项a、b、c、y和id组成，其中id是待解算系统的本地标识符。这起到线程标识符的作用，对于在解算器中寻址正确的内存堆栈非常重要。硬件架构由四个主要组件组成：正向迭代核心、d除法器、反向迭代核心和堆栈阵列。前向和后向核包含算法各阶段的流水线算法，d除法器由两个除法器组成，用于执行c/d和z/d计算。堆栈数组用于存储中间变量c/d和z/d。由于问题的性质，可以使用堆栈，因为向后迭代首先需要d除法器计算的最后一个值，这节省了内存寻址的不必要复杂性。将正向迭代连接到反向迭代是一个队列。

该队列允许将问题索引传递到向后核心进行计算。一旦向前迭代完成，该系统允许向前和向后迭代的有效独立操作。向后核心检查管道中的空间，如果有空间，则读入问题以开始计算，否则它将保持排队状态。除了主要的Thomas算法核心，核心还被放在一个包装中，以便于使用。包装器由输入数据和输出结果的先进先出（FIFO）队列组成，允许从核心到核心的可变写入和读取时间，以及用于输入数据的浮点到定点转换器选项，反之亦然，用于结果。当改变算法时，只改变算法核心，结构保持不变。由于延迟不同，算术核的唯一变化是管道，但这是通过解算器VHDL中的可调参数来管理的。3设计分析我们从理论上分析了求解多个独立三对角系统T={TN，TN，。

..，TNmM}，其中M是要求解的独立三对角系统的总数，Nm是mth系统的大小。本工作中使用的符号如下：–tnmm是要求解的第m个三对角系统的大小，为Nm，–tn是一个特例，其中对于所有Tm∈ T、 Nm=N，–CD{，-,/,×}是使用数据格式D进行算术运算的时钟周期数，-CF，B，Ais是单个正向（F）和反向（B）迭代和管理成本（a）的时钟周期数f是FPGA系统的时钟频率。迭代阶段的循环次数为：CF=CD/+CD×+CD-（7） CB=CD×+CD++CD/，（8），其中Cai是由算法编程确定的常数。为了充分利用流水线设计的能力，需要通过调度独立计算组来实现最大吞吐量。定义1计算块B的数量定义为待求解的独立三对角系统的子集数量。由b={bm，bm，…，bmBB}给出的块集，其中bmi T的尺寸为：∪Bi=1bmii=T∩Bi=1bmii=/0。因此，对于给定的M，计算tn的时间由以下公式给出：tTN=NB（CF+CA）+BC/+NCB+2∑Bb=1（mb）- 1） f.（9）将T划分为块B的集合可能会受到解算器和主机系统之间的数据传输速率的影响。THOMAS解算器的计算速率rc由以下公式给出：rc=5Df，（10），其中D是用于表示给定格式的数字的位数。该值是Thomas solver可以处理数据的速率，它需要5个输入a、b、c、y和id，并且可以在每个时钟周期处理一行。如果传输速率快于计算速率，即。

解算器可以在一个时钟周期或更短的时间内接收所有5个值：Bopt=FLOORMCF, 研发部≥ rc（11）数据传输速率可能低于计算速率，因此求解器必须暂停等待数据。因此，希望在不暂停数据的情况下，计算管道b区中三对角系统的最大数量。B区的数量由以下公式给出：mopt=ceil（rcrd），rd<rc（12）B=FLOORMmopt（13） 如果要求解的一组三对角系统完全填满了求解器的管道，则可以获得求解器的最大吞吐量：M mod CF=0（14）B>1。（15） 4定点算法分析4。1数字边界为了最大限度地提高性能，FPGA设计中可能需要使用自定义数据格式。例如，定点算法通常提供更快、更小的FPG设计（Jin等人，2012年；Tian和Benkrid，2010年），但其代价是结果中的一些精度损失，以及算法过流的风险更高。因此，了解解算器在算法中预期使用的值范围非常重要，以允许针对问题优化自定义数据格式。前面的结果要求b（n）是行索引n的正单调递增函数，即bn<bn+1和| an |<1和| cn |<1我≤ N.这些定理将有助于以后确定隐含定价问题的范围。在以下结果中`∞-系数a、b或c集合的范数，用kxk表示∞, 如果使用，该范数的值是集合中最大的绝对值。定理1：设A为对角占优的行或列，并设A具有Lufactoriation A=LU。然后kdk∞≤ 3kbk∞证明我们使用的结果是：|lncn-1 |+| dn |≤ 3 | bn |（16）见（海厄姆，2002年，第175页）。