英语原文共 6 页
摘要：
基于SQL的语言广泛用于基于软件的复杂事件处理（CEP）系统。本文提出了一种基于FPGA加速框架，将基于SQL的事件处理语言（基于支持事件处理的ANSI标准提案）编译成一个基于FPGA的高性能CEP引擎。除了SQL的原语，如分区，窗口，聚合和模式匹配，所提出的框架允许C/C 功能实现复杂的算法所需的现实世界的应用。CEP引擎还可以利用便宜的块存储器非常有效地并行处理多个流。实验结果表明，我们提出的CEP引擎，是为财务分析应用程序编译的，它计算了一个流行的交易基准，以捕捉有意义的市场趋势，在超过16000个流中达到了1.5亿个事件/秒（20Gbps）的处理性能。
发表于：第22届国际现场可编程逻辑与应用会议（FPL）
会议日期：2012年8月29日至31日
加入IEEE Xplore的日期：2012年10月25日
ISBN信息：
ISSN信息：
检验检疫局注册号：13113541
内政部：10.1109/fpl.2012.6339187
出版商：IEEE
会议地点：挪威奥斯陆
广告
目录
第1节。
介绍
复杂事件处理（CEP）的目标是从大量的小数据片段中提取有意义的信息[1]。许多基于软件的CEP（流）系统支持自己的新事件语言，作为数据库管理系统（DBMS）中使用的结构化查询语言（SQL）的扩展[2][3][4][5][6][7][8][9][10]。这些事件语言的基本功能，除了SQL的原语外，还包括：分区，按字段对流内容进行分类；窗口化，指定处理事件的范围（窗口）；聚合，执行输入指定事件字段的函数（如求和或平均值）；模式匹配，它检测指定的事件序列。Kleene闭包（例如，正则表达式中的*或 ）是CEP系统中处理有限但无边界的时间序列事件数最强大的操作。
虽然现有的基于软件的CEP系统使用基于SQL的声明性语言实现复杂的事件处理功能，但这些系统的处理性能较差（至多为500k个事件/秒[11]）。克服基于软件的CEP系统缺点的一种有希望的方法是使用可重新配置的硬件，例如现场可编程门阵列（fpgas），以加速事件处理。[21][22]的作者提出了一个划时代的、基于FPGA的CEP系统和一个基于SQL的编译器框架。[17]的作者还提出了一种C-to-FPGA编译器，该编译器支持基于C函数的正则表达式，并实现了20Gbps的事件处理性能。然而，他们的硬件加速CEP系统仍然面临以下两个问题：
问题1：
实际CEP应用程序的可编程性有限。金融应用程序通常使用交易基准，如交易量加权平均价格（vwap）来准确分析市场信息。计算出的基准也用于捕捉有意义的市场趋势。尽管SQL实现应用程序处理大量数据的效率很高，但它不足以描述复杂的算法，如交易基准。对于基于软件的CEP，例如，IBM SpAD[6 ]用于允许用C 内置的运算符执行用户定义的C 或Java中的操作符。但是，基于SQL的硬件加速引擎[21][22]无法支持任何用户定义的函数，因为它们的硬件复杂性很容易导致吞吐量严重下降。虽然[17]中提出的语言能够描述所使用的定义函数，但被认为很难被普通用户（如财务分析师）采用，因为它与他们熟悉的语言相差甚远。其他最先进的高级合成工具[12][13][14][15][16]也不支持SQL。这表明需要可编程性来描述结合了基于SQL的查询和用户定义函数的应用程序。
问题2：
多个事件流的可扩展性有限。基于SQL的事件语言中最重要的原语之一是分区。现实世界中的事件流通常由多个在高速网络链路上交错的流组成。例如，财务应用程序需要跟踪其投资组合中超过1000只股票，并对每只股票分别执行特定的查询。然而，之前引用的工作主要集中在一次只处理单个流的查询上。虽然[19]中的工作提出了一种优雅的上下文切换机制来多路复用单流解决方案，但流的数量不到1000。[21]中介绍的工作还支持少于800个流。这种限制的主要原因是所有中间信息都存储在昂贵的触发器和分布式内存中，以满足严格的延迟限制。这表明需要一种新的体系结构来利用区域高效的资源，如块内存来支持大量的多流，而不会降低性能。
这项工作提出了一个综合框架，合成高性能CEP引擎上的FPGA从查询中描述的SQL为基础的语言与用户定义的C/C 功能。它建立在最先进的高级合成引擎[23][24]和FPGA供应商的工具之上。我们工作的主要贡献包括：
从基于sol的查询到FPGA上的CEP引擎的合成框架：
我们已经实现了一个sol-to-fpga编译器，它将基于SQL的查询转换为fpgas上的事件处理引擎。输入语言基于2007年的ANSI标准建议[20]，该建议扩展了SQL，以便对事件序列执行模式匹配。该语言被进一步扩展以允许用户定义的C/C 功能来检测感兴趣的事件并在无界匹配事件上执行复杂的聚合，称为传播聚合。这两种语言的混搭提供了描述实际应用程序的可编程性。表1总结了与我们相比的相关工作。从作者的知识来看，这是第一个基于支持C/C 功能的SQL语言将CEP引擎集成到FPGA上的框架。
表1.与相关工程的比较
可扩展到16K事件流的流水线结构：
我们提出了一个支持多个流的流水线CEP引擎。通过将多个流的上下文交织成单个引擎来隐藏事件处理，以隐藏复杂C/C 功能的传播聚合所引入的等待时间。上下文切换也采用流水线方式，以避免由于块存储器的长接线延迟而降低时钟速率。由于采用了流水线结构，我们的引擎在16K流中达到了20Gbps的事件处理性能。
本文的其余部分结构如下：
第2节描述了一个激励示例，第3节介绍了我们提出的基于SQL的事件语言，第4节介绍了合成流程，第5节介绍了CEP系统，第6节介绍了我们的评估结果，第7节总结了结果。 第2节。
激励性例子
我们的目标应用之一是金融交易，它需要对从证券交易所收到的市场信息进行实时处理。 图1显示了使用财务基准从多个子流检测有意义模式的交易应用程序示例。市场数据流包含许多子流的交错联合。在本例中，市场流包含每个股票的一个子流。首先，它被划分为子流，因为分析是独立地对每个股票的子流执行的。对于每一个提取的子流，其大众AP[26]计算以独立捕捉市场趋势。基于VWAP，对检测指定模式的多个查询进行处理，以提取有意义的信息。然后利用提取的信息进行进一步的分析，以便交易员做出决策。
图1。激励的例子。
全部查看
图2显示了这样的查询的一个例子，它是由SASE [18]中的查询3启发而来的，使用我们的基于SQL的事件处理语言。它捕捉到了一个复杂的趋势：成交量开始走高，但在股价上涨或保持相对稳定的一段时间后，成交量骤降。我们假设事件包含时间戳、股票ID、价格和数量。在查询中，输入流根据stock_uid划分为子流。使用正则表达式表示要观察的趋势。在这个阶段使用vwap来准确分析市场。为了实现这种复杂的算法，需要SQL／C 函数，因为SQL的内置运算符没有足够的可编程性。
图2。使用我们的语言的查询示例。
全部查看
图3显示了查询A中使用的函数。每个函数有两个参数和一个返回值：一个输入事件（ev）、一个指向共享数据的指针（evarg）和一个匹配结果。输入事件具有时间戳、股票ID和卷。共享数据具有中间值，如卷和、vwap等。函数vol_uuh（）通过检查当前卷是否大于阈值来检测“卷高”的事件。它的价格、体积保留下来以备将来计算。还计算了初始的vwap。pri_uustbl（）函数通过将vwap更新为当前事件并与当前价格进行比较，检查当前事件的顺序是否为“价格上涨或保持相对稳定”。如果当前音量比初始音量减少80%，vol_uudown（）函数将触发。一旦检测到匹配序列，将返回最新的卷、价格和计算出的带有库存ID的vwap。注意，计算的vwap在函数之间传播，用于检测要观察的事件。
图3。查询A中使用的函数。
查看全部
第3节。
基于SQL的连续查询语言
图4描述了我们基于SQL的事件语言的概述。它包括：1）select子句，它丢弃事件中的指定字段；2）from子句，它指定处理的事件流；3）where子句，它选择字段至少包含一个匹配项的事件；4）窗口定义，它指定处理的事件的范围（窗口）。select子句的select列表和where子句的搜索条件中提供了内置运算符，如 /-/ave（）/max（）/min（）。
图4。基于SQL的事件语言概述。
查看全部
除了上面提到的原语外，本文最重要的贡献之一就是支持两个子句，匹配识别和划分。match recognize子句用于查找模式。PARTIONBY子句根据字段对流内容进行分类。 3.1。
匹配识别子句
关于向SQL添加匹配识别的2007年ANSI标准建议[20]为查找定义为正则表达式的模式提出了一个新功能。我们已经扩展了它以允许C/C 功能来检测特定事件。并介绍了它的传播聚合。
匹配识别有四个主要部分：输入规范、输出规范、模式组件和事件定义。输入规范（From和PartitionBy）指定将在其中搜索模式的流。输出规范（度量）指定匹配模式的导出列。查询A从股票中获取事件，并在指定的模式匹配时以其股票ID作为输出，生成最新的数量、价格和计算出的vwap。模式组件（模式）将要查找的模式定义为正则表达式。正则表达式中的每个变量都对应于基于给定运算符的一个或多个事件。与传统的正则表达式语法一样，我们的语法有四个基本规则：变量v、分组（）、序列r1 r2、选项r1 r2和（kleene）闭包r 。在查询A中，A表示一个事件，B 表示一个或多个事件，C也表示一个事件，并且这些事件是按给定顺序连续的。
事件定义（define）指定用于定义模式中声明的变量名的布尔条件。在最初的提议中，一个条件是通过字段上的谓词来描述的。与之不同的是，我们的语言能够使用用户定义的C/C 函数来代替。在查询A中，函数vol_high（）、pri_stbl（）、vol_down（）分别与变量A、B和C关联。每个函数都有两个参数和一个返回值：一个输入事件（ev）、一个指向共享数据（arg）的指针，以及当两个参数满足指定条件时为真的匹配结果。同时为所有函数提供输入事件。当被调用函数的所有返回值都为真时，整个正则表达式都是匹配的。这里我们的语言的重要方面是传播聚合，其中更改的arg值沿着正则表达式传播，链中的每个函数（从第二个函数开始）都接收由前一个函数修改的值。如图5所示，输入事件按顺序提供给每个函数。在事件检测期间，每个函数都会更新共享数据（例如arg中的vwap）。如果所有函数的返回值（例如vol_high（）pri_stbl（）pri_stbl（）pri_stbl（）pri_stbl（）vol_down（））都为真，则正则表达式是匹配的。然后，根据函数序列vol_h（）pri_stbl（）pri_stbl（）pri_stbl（）pri_stbl（）vol_down（）修改的值获取最终数据（arg中的stock_id、price、volume和vwap）。
图5。查询A中传播聚合的示例。
查看全部
3.2。按子句划分
现实世界中的流（如市场数据）通常包含许多子流的交错联合。根据指定字段的值（类似于SQL的group by）将原始流划分为不同的子流。它与窗口或匹配识别一起使用。通过窗口，它通过单独滑动每个子流上最后n个事件的窗口来定义其随时间的输出关系。例如，窗口“stock[partition by stock_id rows 3]”在流stock上创建子流，并生成一个滑动窗口，其中每个stock_u id有三个事件。通过匹配识别，它还独立地对每个分区的子流执行模式匹配。注意，每个子流都需要维护一个包含最新n个事件（对于窗口）或匹配状态（对于匹配识别
资料编号：[3939]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
