一种针对GPU加速多步长前缀树的更新序列维护方法

摘要

本发明涉及一种针对GPU加速多步长前缀树的更新序列维护方法，该方法包括以下步骤：创建第一数组和第二数组，以及设置第一变量；所述第一数组第i号单元初始化为i，所述第二数组则全置为0；所述第一变量，用来记录目前更新操作的次数，并且会初始化为0；当CPU收到一个针对GAMT第x号单元执行更新的操作，CPU则调整所述第一数组上的位置。本发明可以针对GAMT更新序列排序问题，将其排序时间复杂度降低到最差情况下O(n/8)，并且往第一数组中插入新元素的时间复杂度为O(1)。

说明书

技术领域

本发明涉GPU加速的多步长前缀树更新技术，特别涉及一种针对GPU加速多步长前缀树的更新序列维护方法。

背景技术

传统软件路由器的性能已经面临严峻的性能挑战。而他们的性能瓶颈又主要源自一些基本的包处理操作，比如IP查找，需根据目的IP地址在转发信息表中进行最长前缀匹配(LPM)。主流的LPM解决方案分为两大类。一般情况下，基于哈希的方案能实现相对较高的查找吞吐率，但是他们对高速存储资源的需求，以及由哈希冲突、假阳性带来的一系列问题制约了他们在大规模数据集或者新场景的应用。另一类则是通过引入树型结构(比如前缀树、平衡树等) 来维护转发信息表，以提升方案的灵活性。虽然已经涌现出很多优化方案，但这类方案的性能依然难以与基于TCAM的快速查找表，或基于FPGA实现的查找流水线相提并论。幸运的是，GPU正逐渐发展成为新型的通用高性能计算平台。一些基于GPU加速的软件路由器可以实现非常高的吞吐率。要在这样的平台上工作并充分利用平台优势，IP查找引擎还面临着一系列挑战。比如性能、对大规模数据集或者是新协议、新应用的支持。然而现有工作要么是针对路由器的整体框架进行探索，要么就是研究多种包处理操作的综合性能提升。都没有讨论路由更新的处理。而实际应用种路由更新的峰值频率已超过每秒2万条1，且还在持续增长。如此高频的更新势必会与查找模块竞争资源进而影响查找性能。特别是在一些新型应用场景，比如虚拟化路由器、OpenFlow交换机等，更新都更加频繁。因此，在查找引擎的设计中不得不考虑更新开销。发表于 ANCS-2013的文章《GAMT：A Fast andScalable IP Lookup Engine for GPU-based Software Routers》提出了一种基于GPU加速的多步长前缀树(GPU-Accelerated Multi-bit Trie，GAMT)，通过引入一种新型编码方案将多步长前缀树编码为一个二维数组形式的状态跳转表，并基于GPU的访存特点来进行结构优化。不仅能实现比GALE和TSET更快的IPv4地址查找，同时还支持高速IPv6地址查找。但是，在更新性能方面，GAMT还存在不足，没有根据GPU 访问显存的特殊方式进行优化设计。因此，在实际部署中，即使查找性能达到较好的性能水平，但是面对规则频繁更新的场景，GAMT的整体性能将受限于其更新方式的不足。

GPU在进行大规模并行计算时，采用的是一种叫做“单指令多线程”(即 SIMT)模式，即将数据划分为多个部分，每个部分由一个线程负责。当线程在计算时，采用完全相同的计算函数(即核函数)，以此达到并行计算的效果。此外，GPU将32个线程归为一组(即warp)，因此GPU在进行计算的任务调度时，warp是最小的调度单元，总是以一个warp为单位进行计算任务分配和显存访问。不同于CPU的访问主存的模式，GPU中一个warp访问显存时，是以一种称之为存储事务(即Memory Transaction)的形式进行的。具体而言，一个warp 发起访存请求时，GPU会读入连续的若干字节显存数据。如果warp每个线程所分配的数据刚好位于连续存放，1次存储事务就能将warp中所有线程需要的数据都读取完毕，这将达到最佳的访存性能。

图1给出了存储事务的示意图，图中我们假设一个warp包含3个线程(实际中包含32个线程)，一次存储事务读取3个存储单元(实际中则是若干字节，如GAMT论文中采用的GPU设备一次存储事务读取128字节)。每个正方形块对应着一个显存单元，A1、A2、A3正方形块表示warp中线程需要访问的显存单元，其他正方形块则表示其他显存单元。左图可以看出，warp中3个线程所访问的显存单元刚好在显存上是连续分布的，一次存储事务(即图上的MTO)就可以读取完毕；而右图中，warp中3个线程所访问的显存单元并未集中分布，最终需要3个存储事务(即MT0，MT1和MT2)才能读取完毕，这样一来，左边的warp 访存性能将明显优于右边，处理速度将明显快于右边的warp。考虑到访存位置对GPU处理速度的性能，GAMT目前的更新方式还存在以下不足，具体分析如下。

GAMT的核心数据结构是多个长度相等的数组(一种数据连续存放的数据结构，如图1中的正方形块所示)，而更新操作则是对数组上的某个或者多个存储单元进行数值。当运行在GPU上时，将有若干个warp执行这项操作，warp中每个线程负责修改一个GAMT存储单元。而具体要修改哪些存储单元，则是由CPU 在GPU以外计算好并保存成一个数组，数组中每个存储单元里面存放的数值，对应中GAMT数组需要被修改的某个存储单元的索引号。换言之CPU将需要更新的GAMT存储单元序列传递GPU以便于后者执行更新。而这个序列是否排序，对 GAMT的更新性能好坏至关重要。以图2为例，这里依然假设一个warp包含了3 个线程，一个存储事务可以读取连续3个显存单元。假设CPU上不对更新序列进行排序操作，直接按更新发生的先后顺序发送给GPU，即GAMT更新序列是“0， 5，8，1，2，7”，那么GAMT更新时warp的访存顺序如左图所示。首先，warp 按照CPU发送的更系序列，需要更新“0，5，8”三个位置(即A正方形块对应的位置)，这3个位置相对位置较远，需要3次存储事务才能读取完毕；接下来， warp需要更新“1，2，7”三个位置(即B正方形块对应的位置)，如左图所示需要2次存储事务才能读取完毕。这样，左图中对应的更新方式需要总共5次存储事务。接下来看右图，它和左图需要更新的位置是一致的，但是在发送给GPU 之前进行了排序，GAMT更新序列变为“0，1，2，5，7，8”。首先，如左图所示，warp 首先处理“0，1，2”三个位置，容易发现这三个位置是连续的，一次存储事务刚好读取完毕。接下来更新“5，7，8”三个位置，容易发现需要2次存储事务。这样，为GAMT执行同样的更新，右图的更新方式需要3次存储事务，比左图少了 2次，大幅度减少了存储事务的次数，这有利于整体性能的提升，可见排序操作对GAMT的更新性能有很大的影响。GAMT并未对更新方法设计高效的排序方法，因此当更新序列很长的时候，CPU将花费大量的时间去维护更新序列的顺序，这会带来很大的时间开销，这是GAMT更新方法最大的不足之处，这是本发明技术方案的所要解决的问题。

发明内容

本发明的目的，在于解决现有GAMT更新方法存在的上述所述的技术问题。

为实现上述目的，本发明提供一种针对GPU加速多步长前缀树的更新序列维护方法，该方法包括以下步骤：

创建第一数组和第二数组，以及设置第一变量；所述第一数组第i号单元初始化为i，所述第二数组则全置为0；所述第一变量，用来记录目前更新操作的次数，并且初始化为0；

当CPU收到一个针对GAMT第x号单元执行更新的操作，CPU需要调整所述第一数组上的位置，具体调整方法的流程如下：

根据i＝x/8，得到x对应的bitmap比特位于第二数组的i号单元里面，再用j＝x％8，判断第二数组[i]中的第j个比特是否是1；如果该比特是1，那么表示前面已经收到过了一个针对GAMT的x号单元的更新操作，因此这个更新操作会被忽略；否则，说明之前没有收到过针对GAMT数组x号单元的更新操作，进入以下步骤；

所述第一数组[x]＝x，假如第一数组[第一变量]＝y，则交换第一数组[x]和第一数组[第一变量]的位置，使第一数组[x]＝y，第一数组[第一变量]＝x，接着进入以下步骤；

因为第一数组上的单元位置发生了变化，则调整第二数组[i]上的j比特为 1，进入以下步骤；

更新第一变量的数值，使第一变量＝第一变量+1，表示当前增加了一次更新操作。

优选地，本发明实施例创建辅助表，该辅助表是把1个8bit的bitmap所有可能的数值，对应的GAMT索引信息；所述第一数组元素都是一个小bitmap，第一数组[i]对应着GAMT的i*8到i*8+7号单元的更新情况。

优选地，第一数组中每个单元可以共用所述辅助表，每个第一数组[i]在根据所述辅助表得出GAMT索引号之后，还需要在每个索引号的基础上偏移获取正确的GAMT索引号。

优选地，根据所述辅助表，更新序列的具体计算方法如下：

步骤一、创建一个计数器cnt，表示目前加入到更新序列中的数字个数，初始化cnt＝0；以及维护一个更新序列update_array，里面存放的是排序后的GAMT 待更新单元的序号；

步骤二、令i＝0，以及第一数组的长度为n，开始扫描第一数组；

步骤三、若i＜n，判断第一数组[i]与0的数值大小：如果第一数组[i]＝0，则第一数组[i]对应范围内上没有GAMT单元需要更新，进入步骤四；否则，根据第一数组[i]的数值去辅助表查询对应的索引号序列，并将索引号序列中每个索引号加上一个偏移量i*8后得出真正的GAMT单元索引号，再全部加入到 update_array中，并且根据新加入的GAMT单元索引号的数量调整计数器cnt的数值，表示更新序列update_array中加入了若干个新成员；

步骤四、比较cnt和第一变量的大小：若cnt＜第一变量，说明还有针对GAMT 其他单元的更新操作还没有加入到更新序列update_array中，因此令i＝i+1，表示要接着查看第二数组后续的单元，并进入步骤三；否则，表示所有待更新的GAMT单元已经被更新序列update_array记录到了，因此结束遍历，进入步骤五；

步骤五、CPU把更新序列update_array，以及update_array上各个GAMT 单元索引号对应的GAMT单元的更新值一起发送到GPU，后者对GAMT各个待更新位置执行更新操作。

本发明针对GAMT这一GPU加速的IP查找算法的更新方法进行优化改进，使得CPU在维护GAMT更新序列的有序性时需要时间开销更小。

附图说明

图1为现有存储事务示意图；

图2为GAMT不同更新顺序的访存方式示意图；

图3为本发明实施例提供的第一数组和第二数组结构示意图；

图4为第一数组和第二数组更新示意图；

图5为第一数组单元和GAMT序号对照表；

图6为本发明实施例提供的更新序列流程示意图；

图7为本发明实施例提供的一种针对GPU加速多步长前缀树的更新序列维护方法流程示意图。

具体实施方式

下面结合附图与具体实施方式对本发明作进一步详细描述。

本发明实施例主要是针对GAMT这一GPU加速的IP查找算法的更新方法进行优化改进，使得CPU在维护GAMT更新序列的有序性时需要时间开销更小。

图3为本发明实施例提供的第一数组和第二数组结构示意图。GAMT在CPU 上维护更新序列时，会创建第一数组(locations数组)，locations数组和GPU 上的GAMT数组长度相等。locations数组保存的是GAMT数组上需要执行更新的位置，根据更新操作到来的先后顺序依次从左至右存放在locations数组中。假设GAMT要更新“6，3，9”三个位置，那么locations的排列顺序就是“6，3，9，...”。假设设定m为更新阈值，即当接收到m个更新操作后，程序需要更新GPU上的GAMT数组了，会取出locations数组的前m个单元组成更新序列发送给GPU执行更新操作(如图7所示)。为了结合GPU存储事务的特点， CPU会在更新序列发送给GPU之前对其进行排序。

在GAMT中，CPU上维护的locations数组存放的是位置信息(即GAMT数组上需要被更新的单元位置)，那么它里面各个数组单元的取值范围应该就是GAMT 数组存储单元的索引取值范围。例如，GAMT数组长度为n(locations数组的长度也将是n)，那么locations数组上各个数组单元的取值范围就是[0，n-1]。利用这一特性，我们可以再额外创建第二数组比特位图(bitmap)。Bitmap的第i号比特为1，表示i被插入了locations数组。bitmap在实际实现时，也是一个数组，每个数组元素一个字节(8比特)，bitmap[0]对应着GAMT上0到 7号单元的插入情况，bitmap[1]对应着GAMT上8到15号单元的插入情况，以此类推。因此，假设locations数组长度为N，bitmap数组的长度则为N/8，其中bitmap[i]对应着GAMT上i*8到i*8+7号单元的的插入情况。举例说明，如图3所示：locations数组依次插入了3和2，那么3和2将为了loctions数组的最前两个位置，同时bitmap的3号和2号比特为1，其余比特则为0。接下来详细介绍如何使用这样设计完成高效的更新序列维护。

步骤一、初始化

将locations数组第i号单元均初始化为i，bitmap数组则全置为0。此外，还会额外创建一个变量nLoc，用来记录目前更新操作的次数，并且会初始化为 0。

步骤二、CPU收到新的更新请求：

当CPU收到一个针对GAMT第x号单元执行更新的操作，CPU需要调整 locations数组上的位置，具体调整方法的流程如下：

(1)根据i＝x/8，可以得到x对应的bitmap比特位于bitmap数组的i号单元里面，再用j＝x％8，判断bitmap[i]中的第j个比特是否是1。如果该比特的确是1，那么表示前面已经收到过了一个针对GAMT的x号单元的更新操作，因此这个更新操作会被忽略，因为GAMT会拒绝重复更新同一个单元；否则，说明之前没有收到过针对GAMT数组x号单元的更新操作，进入步骤(2)。

(2)因为没有收到过针对x单元的更新请求，那么此时locations[x]＝x。此时假如locations[nLoc]＝y，我们交换loctions[x]和locations[nLoc]的位置，使locations[x]＝y，locations[nLoc]＝x，接着进入步骤(3)。

(3)因为locations数组上的单元位置发生了变化，我们调整bitmap[i] 上的j好比特为1，进入步骤(4)。

(4)locations数组和bitmap数组的调整到此结束，我们更新nLoc的数值，使nLoc＝nLoc+1，表示当前增加了一次更新操作。

根据以上的插入操作步骤，很容易发现，每次插入进来一个数字x，需要调整的locations数组单元和bitmap数组单元都是直接计算出来的，不需要在数组上执行任何的搜索遍历，因此这个操作的时间复杂度是O(1)的，为了更直观地解释调整方法，图4展示了依次收到针对GAMT第7，9，5号单元的更新操作后，对locations数组和bitmap数组的影响。

步骤三、CPU需要提交更新到GPU：

此时，CPU需要根据locations和bitmap数组计算出更新序列，本发明实施例可以通过扫描一遍bitmap数组，得出有序的更细序列。在此之前，我们还需要维护一个如图5所示的辅助表mapToNodes。mapToNodes是把1个8bit的 bitmap所有可能的数值，对应的GAMT索引信息，例如bitmap＝00000001对应着 0号单元需要更新，bitmap＝00001001表示0号和3号单元需要更新。如前文所示，bitmap是个数组，每个数组元素都是一个小bitmap，bitmap[i]对应着GAMT 的i*8到i*8+7号单元的更新情况。因为每个小bitmap是8比特长度，那么mapToNodes表总共有2的8次方(即256)个表项。此外，还需要注意的是， bitmap数组中每个单元可以共用这一份mapToNodes表，每个bitmap[i]在根据 mapToNodes表得出GAMT索引号之后，还需要在每个索引号的基础上加上图4中描述的偏移才能获取正确的GAMT索引号，如图6所示。

举例说明，bitmap[3]的数值为00001001，查询mapToNodes表后可知对应的GAMT单元索引号是0和3，然后我们知道bitmap[3]对应的偏移是3x8＝24，因此实际需要更新的GAMT单元索引号是0+24＝24和3+24＝27。

借助mapToNodes表，更新序列的具体计算方法如下：

创建一个计数器cnt，表示目前加入到更新序列中的数字个数，初始化 cnt＝0。此外，创建一个更新序列update_array，里面存放的是排序后的GAMT 待更新单元的序号。

令i＝0，以及bitmap数组的长度为n，开始扫描bitmap数组。

若i＜n，判断bitmap[i]与0的数值大小：如果bitmap[i]＝0，则bitmap[i] 对应范围内上没有GAMT单元需要更新，进入步骤(4)；否则，根据bitmap[i] 的数值去mapToNodes表查询对应的索引号序列，并将索引号序列中每个索引号加上一个偏移量i*8后得出真正的GAMT单元索引号，再全部加入到 update_array中，并且根据新加入的GAMT单元索引号的数量调整计数器cnt的数值，表示更新序列update_array中加入了若干个新成员。

比较cnt和nLoc的大小：若cnt＜nLoc，说明还有针对GAMT其他单元的更新操作还没有加入到更新序列update_array中，因此令i＝i+1，表示要接着查看bitmap数组后续的单元，并进入步骤(3)；否则，表示所有待更新的GAMT 单元已经被更新序列update_array记录到了，因此结束遍历，进入步骤(5)。

CPU把更新序列update_array，以及update_array上各个GAMT单元索引号对应的GAMT单元的更新值一起发送到GPU，后者对GAMT各个待更新位置执行更新操作。

为了便于理解，我们以图6为例，并且假设CPU记录到3个更新操作了就要提交给GPU，看看这种情况下更新序列将是什么内容，其中，locations数组前3个单元就是待更新的GAMT单元序列号，即7，9，5，此时他们是未排序状态。同时，nLoc＝3表示待更新GAMT单元的数量是3，cnt初始化为0。我们从bitmap[0] 开始遍历，bitmap[0]＝00000101，查询mapToNodes表后得到索引号序列[5，7]，之后我们为每个索引号加上偏移量i*8＝0*8＝0，因此实际待更新的GAMT单元索引号是[5，7]，加入update_array中，并且令cnt＝cnt+2＝2。我们比较cnt和 nLoc的大小，发现cnt＜nLoc，说明后续还有待更新节点没有记录到，继续遍历 bitmap数组。接下来查看bitmap[1]，根据其数值01000000可得到索引号序列 [1]，同样我们加上偏移量i*8＝1*8＝8，得到实际需要更新的GAMT单元索引号是 [9]，加入update_array中，并且令cnt＝cnt+1＝3。之后，我们依然比较cnt和 nLoc大小，发现cnt和nLoc相等了，说明所有的待更新单元索引号都被记录到了，因此结束遍历，得到最终的更新序列updare_array＝[5，7，9]，此时我们发现，更新序列应是排序后的状态了。从以上的示例中我们可以发现，最坏情况下我们需要访问bitmap数组的每一个单元，而建设locations数组的长度(也就是GAMT数组的长度)为N，那么bitmap数组的长度就是N/8，因此最坏情况下的时间复杂度是O(N/8)。

本发明实施例可以针对GAMT更新序列排序问题，将其排序时间复杂度降低到最差情况下O(n/8)，并且往第一数组中插入新元素的时间复杂度为O(1)。

显而易见，在不偏离本发明的真实精神和范围的前提下，在此描述的本发明可以有许多变化。因此，所有对于本领域技术人员来说显而易见的改变，都应包括在本权利要求书所涵盖的范围之内。本发明所要求保护的范围仅由所述的权利要求书进行限定。