基于FPGA的实时金融指数行情并行计算

admin

一、立项依据
          （1）面临的问题与挑战
          中国金融市场已经是全球最大的金融市场之一，随着市场规模的不断扩大，金融市场的功能发挥日益明显，服务相关产业和国民经济的能力不断提高。金融是现代经济的核心，金融现代化、市场化和国际化程度不断提高，与社会主义市场经济体制相适应的金融体制初步建立，并在优化资源配置、支持经济改革、促进经济持续发展和维护社会经济稳定方面发挥了重要作用。
           
          金融交易系统（例如股票交易系统）具有交易时间相对集中、交易指令和数据密集的特点，对交易系统处理速度具有很高的要求。近年来，资本市场的快速发展和算法交易技术（尤其是高频交易）在全世界范围内的应用，使得交易所在低交易延时领域面临着巨大的技术挑战。
           
          交易所对于交易系统延时测量监控需求也越来越迫切，同时对于大规模数据密集型计算的实时性要求也越来越高。对于交易系统及环节的高精度延时测量，达到近实时的分析性能基本可以准确快速的监测股票交易系统性能和状态，但对于大规模实时交易数据分析，则需要达到更快的处理速度，实时性要求更高，直接关系到交易系统的服务质量（QoS）。传统的软件技术或以软件为核心的软硬件加速技术难以满足微秒级实时分析和实时响应的要求，采用FPGA专用硬件结构实现大规模数据密集型计算的并行加速称为提高交易系统服务质量的迫切需求。
           
          金融交易所通过加速应用软件来获得市场竞争优势.对金融应用软件加速,金融交易所能够比竞争对手更快更好地完成交易,更少出错,大幅度提高收益.要提升性能首先得提高处理能力,全面提升性能 要求处理能力至少提高一个数量级。中国股票交易系统的现状，本项目将围绕股票交易的规则和方法，以上证50指数的数据分析为典型应用场景，通过专用硬件平台实现大规模实时并行数据处理，根据特定计算模型实现快速进行股票信息接受、数据处理、指数计算、行情更新等功能。拟采用FPGA为核心器件，研究交易数据的并行调度策略和计算模型，将相应速度提升3-4个数量级，并给出FPGA随股票数据数量、计算模型复杂度提高的并行加速性能分析。
           
          （2）与系统建设长期规划的关系
          本项目的研究成果除股票交易的并行加速模型与系统设计外，还包括对股票交易系统其它业务处理的硬件加速论证方案，根据计算任务特点不同，给出合理的硬件加速平台建设方案，股票指数实时更新只是其中的一个应用场景。
           
          本项研究成果可以集成或独立应用与股票交易业务应用，具有理论研究价值和实际应用推广价值，同时将为股票交易所下一代交易系统核心撮合引擎在硬件并行加速方面的技术革新奠定基础。
           
          二、国内外研究现状
          在网络以及网络数据包处理相关问题上，链路带宽的剧增给高速网络数据包处理带来了极大的挑战。传统的纯软件网络数据包处理在性能上已不能满足需要。当前网络处理器、多核芯片等针对高性能网络数据包处理提供了硬件加速技术，对多数网络应用提供了高性能实现方法。 在对数据处理时延、 吞吐量、 丢包率等性能指标有更高要求的应用场合，还需要专用的加速硬件。目前基于现场可编程逻辑门阵列（FPGA）的通用高速网络数据包处理硬件加速架构对数据采集通路进行硬件加速，实现了高速链路数据报文的线速采集，通过专用硬件进行数据包转发和流量控制，针对后端多核服务器的并行处理进行优化，实现了控制和分析平面的高性能处理。该架构在流量采集、高精度时钟同步、高速包分类和流量控制等方面，充分卸载了服务器的处理负荷，能有效地提高应用系统的性能.
           
          针对金融网络数据处理的技术研究而言，国外已经预言或实现了很多相关硬件加速和并行计算的FPGA实现，其中Altera公司2008年面向蒙特卡罗算法（QMC）的FPGA加速模型建立，对价格衍生证券的实时精确估计判断做出了很大的促进作用。此外，2009年英国帝国理工学院和英国金融加速解决方案供应商Celoxica合作，提出实现了一种叫“低延迟交易数据反馈计算模型”。针对现在越来越大的交易市场的变化数据（甚至超过gigabit），他们为投资者提供了网络传输数据分析的FPGA加速处理方案，利用FGPA的可配置特点，可选择地实现对交易数据的压缩，过滤，筛选。其性能优越，每秒最多处理高达3.5M条信息，处理延迟也控制在微秒量级上。不但激活了投资者的投资热情，同时也极大促进了金融市场流动性。
         

       

•                 FPGA的特点与应用
  

          FPGA是20世纪80年代中期出现的一种新型的现场可编程逻辑器件，用户可以自己编写程序配置FPGA，从而实现预定的逻辑功能。因为FPGA具有大规模数据并行处理能力、开发周期短、可靠性高和现场可配置等特点，所以在短短的几十年里，现场可编程逻辑嵌入式系统设计技术已经成为信息产业最热门的技术之一，应用范围遍及金融、航空航天、医疗、网络通讯、安防、汽车电子、工业等多个热门领域。在特定领域与传统PC机相比，FPGA能够将处理速度提高几个数量级。
           
          如图1所示，FPGA主要由逻辑控制块（CLB）、输入输出控制块（IOB）和内部连线三大部分组成，同时芯片内部集成块状存储器（BlockRAM）以及数字信号处理单元DSP以满足高速数据处理应用环境的需求。
           

       

        图1  FPGA内部原理图

         

          三、项目内容与研究目标
          3.1研究内容

       

•                 实时金融指数行情计算模型与并行调度策略
  

          研究实时金融指数（本计划书以股票ETF50为例）股票推导的计算模型与计算方法，根据数据计算类型的特点设计专用硬件处理单元的结构模型；
           
          研究有限计算资源条件下的行情数据缓存与并行调度策略，研究硬件计算资源划分与共享技术；
          研究透明数据接口技术，包括输入端旁路高速数据获取技术与实现方法以及输出端的应用接口技术。
           

       

•                 基于FPGA的并行加速技术
  

          研究基于FPGA的硬件千兆以太网数据获取技术，实现完全硬件的TCP/IP协议栈解析和数据包过滤；
          研究行情驱动的大规模专用套利数据处理单元结构、数据缓存与并行分发机制以及数据流水调度算法。
          研究面向同构计算单元（同种计算模型）和异构计算单元（异种推导模型）协同的FPGA资源划分技术，对资源进行优化配置，在有限计算资源条件下获得最高的并行加速性价比。
          实时金融指数行情的可配置与可扩展技术，充分考虑FPGA专用逻辑特点提供计算模型的配置与合约推导的扩展方案。
          研究实时金融指数行情数据的高速分发及应用接口技术，采用高速传输总线结构实现实时金融指数行情数据的提取和管理。
           
           
        3.2研究目标

          （1）实现实时金融指数的大规模硬件并行加速，将数据处理的性能提升3-4个数量级。给出数据获取、数据分析、数据发布的总时间开销的最大加速比以及资源扩展性价比分析。
           
          （2）实现基于FPGA的千兆以太网数据获取与硬件协议栈解析，突破软件协议栈解析的性能瓶颈；设计并实现行情驱动的硬件数据缓存、数据分发、并行调度与管理；实现基于FPGA的异构与同构计算单元相结合的大规模数据并行处理，实现多粒度流水控制和资源复用。
           
          （3）提出加速平台集成方法，设计集成平台的芯片级与板级的动态扩展结构；给出FPGA并行处理性能随计算模型复杂度、股票信息数量、数据传输速率变化的评测分析报告，以及股票交易系统业务类型的硬件加速适应性分析报告。
           
          四、实施方案与技术路线
          本项目实施首先分别采用FPGA设计实时金融指数行情的并行处理结构，并通过测试数据和简化计算模型验证系统的可用性，对比分析硬件并行的加速比并给出随输入条件变化的性能提升分析，然后设计基于FPGA加速平台的系统结构和核心调度策略。
           
          本项目的主要目标是降低“实时金融指数行情”的计算和传输延迟，达到实时的指标数据分析，因此性能评价是对数据获取时间Tg、数据处理时间Ta、数据发布时间Ts的总时间Tt的评价公式（1）所示：

                                     (1)

              其中，基于FPGA的设计方案除采用并行结构降低Ta，还实现硬件的协议栈解析，从而大大降低Tg，同时也采用硬核方式降低Ts的延迟；而FPGA在内存交换的优势将有效降低Ts。
         
          4.1基于FPGA的并行加速技术方案
          （1）基于FPGA的并行加速总体结构
          图3-1为系统结构图，主要由数据接收模块、股票信息并行处理模块、数据发送模块组成。数据接收模块主要负责协议包的跨层解析以及包过滤。股票信息并行处理模块是整个系统的算法核心，采用高速并行方式分析股票信息，计算相关指数，并通过数据发送模块快速发布。在股票信息并行处理模块中，算法定向单元负责调度下层的异构逻辑块，异构逻辑块通过同构逻辑晶格完成最基础的数据计算。在股票信息并行处理模块中，将所有的数据存储于FPGA内部的分布式RAM中，突破了IO传输的瓶颈。
           

       

        图7 FPGA计算系统结构图

         

          对于数据计算，每一种股票指数都有自己的指数计算的方法（本计划书以上证50指数为例）：

        上证 50 指数采用派许加权方法，按照样本股的调整股本数为权数进行加权计算。计

        算公式为：

        Ip = Pa / base * 1000                                                      （1）

        Ip:报告期指数    Pa:报告期成份股的调整市值    base:基 期

        其中，Pa ＝ Σ（Pi× St）                                                    （2）

        Pi:市价   St:调整股数。

        调整股本数采用分级靠档的方法对成份股股本进行调整。

        上证50 指数的分级靠档方

        法如下表所示。

        流通比例(%) ≤10 (10，20] (20，30] (30，40] (40，50] (50，60] (60，70] (70，80] >80

          加权比例(%) 流通比例 20    30      40      50      60       70     80  100
          将上面计算方法进行抽象可以得到：
                                         (2)
          其中xn为从股票信息中抽象出的向量，即为Pa。 为多项式系数，将 表示为如公式（3）所示的向量形式:

                                                        (3)

          对于向量 以及 ( )，定义如果其中 ，则 同构算法，否则异构算法。对所有的异构算法进行等价类划分得到m个集合 。如图2所示，在用FPGA实现时，对m个异构算法采用并行实现方式。对于同构算法，在各异构结构中实现多个同构的计算晶格来提高同构算法的并行处理能力。若用[Tm]表示集合Tm中元素的数量，用 表示各异构结构中同构结构的实现数量，用 表示每一种同构计算晶格计算一次的时间，用ta表示分配k个计算序列所消耗的时间，那么整个计算过程所需时间tlogic如公式（4）所示：

                                        (4)

         
          （2）可配置性与可扩展性设计
          为了便于用户自定义计算规则和业务扩展，从设计架构上采用读入配置文件的方式并且提供扩展空间，实现配置性和扩展性。
           
          可配置性：为用户设计图形化的配置界面软件，当软件接受用户计算请求后会自动生成相应的配置文件，来配置FPGA中的配置寄存器，实现不同要求不同需求、不同用途的运算。
           
          可扩展性：在系统设计中，预留新合约扩展空间，以哈希表等数据结构存储运算。运算过程中，行情数据包到来时，FPGA会通过哈希函数查找哈希表，确定数据的有效性和计算规则，进行逻辑判断进行选择。
           
          （3）基于FPGA的硬件以太网协议跨层解析
          在数据分析获取过程中，以太网的协议解析占据了很大的时间比例。如果采用一般的软件解包方法，时间一般延迟包括每一网络层的解包时间和中间数据的传输时间，时间延迟可达毫秒级甚至更高。考虑到降低整个系统的数据传输延迟，进而提升处理性能，提出以下两种解决方案。
           
          1）使用FPGA集成的可配置IP核。FPGA的IP核基于硬件原理实现，在数据传输延迟和网络数据解包能力上都大大优于传统的软件处理过程，而且极大缩短了开发周期，其可靠性，可配置性，通用性都相当出色。适合在项目的中前期作为数据输入的模拟测试。但是具体面向此项目IP核也会有自身的冗余，在MAC层不能进行自定义的协议解析，总的延迟大约在几十微秒至几百微秒。
           
          2）针对本应用设计基于跨层解析的以太网数据分析模型。由于套利计算的数据源的包格式固定，封装简单，而且属于旁路数据，完全可以自行设计针对本应用的专用数据解析功能部分，方案优势和创新点在于在MAC层跨层解析数据以及包过滤，数据接收与解析时间重叠。采用状态机逐层进行包过滤，在有限机器周期内便可获得需要计算的数据，时间延迟可控制在微秒级。
           
          基于FPGA的硬件以太网协议跨层解析能够降低传统软件协议栈的数据包处理固有延迟（可能占据整个延迟的80%以上开销），大大提高数据获取和预处理效率。
           
          （4）高速应用接口设计方案
          板级数据输出采用PCI-Express接口，PCI-Express接口具有扩展性强、低成本、低延迟、高速率等显著优点。单根链路速率为2.5Gb/s，为了解决本系统的IO瓶颈，在系统输出端拟采用8根链路与PC机通信。那么理论上速度可达到20Gb/s，能够满足系统的速度要求，同时也可以满足系统升级后的速率要求。PCI-Express与PC机连接方式由图8所示，可见PCI-Express的扩展性极强。
           

       

        图8  PCI-Express拓扑图

         

          在本系统中主要采用单点的PCI-Express Endpoint与PC机通信，PCI-Express Endpoint功能结构与接口如图9所示，数据主要依次通过Transaction Layer、Data Link           LayerPhysical Layer三层传输到另一端。用户可以通过Configuration Interface对PCI-Express进行配置。

       

        图9  PCI-Express

         
          在数据传输密集时，可以配置PCI-Express为突发传输模式，这样，只需经过起始的握手后，便可快速的进行数据传输。如图10所示，在PC机端拟采用乒乓数据缓冲池作为PCI-Express的数据接收缓冲区，当其中一个缓冲区满时，会产生DMA中断通知PC机操作系统，PC机即可对数据进行处理。这种乒乓缓冲池可以在突破PC机处理速度与本系统传输速度不一致的IO瓶颈的同时，减少本系统的IO传输延迟等待。
           

       

        图10  PC端PCI-Express乒乓数据缓冲池

         

          4.2关键技术与创新点
          （1）基于FPGA的实时金融指数并行分析技术
          基于FPGA的硬件跨层协议解析与包过滤技术，在接收缓冲网络数据包的同时完成期货套利信息提取，大大降低软件协议栈数据包解析的固有延迟。
           
          行情驱动的专用异构与同构计算单元的协同计算模型，充分挖掘信息计算的并行性，并具有可扩展性和可配置性。
           
          灵活高速的套利合约发布应用接口技术，有效保证信息发布的实时性。