CN103973600B - 用于分组处理旋转掩码合并和寄存字段指令的方法及装置 - Google Patents

Abstract

一种用于分组处理的旋转掩码合并和寄存字段指令。在本发明的一个实施例中，讨论了在计算机硬件上执行字节旋转合并的方法。字节旋转在第一和第二源操作数上执行，并目分别被按字节旋转第一和第二旋转常数。将第一字节旋转输出和第二字节旋转输出合并在一起。当来自字节掩码的控制比特是逻辑一时，将来自第一字节旋转输出的字节输出到字节旋转合并输出。当来自字节掩码的控制比特是逻辑零时，将来自第二字节旋转输出的字节输出到字节旋转合并输出。

Description

用于分组处理旋转掩码合并和寄存字段指令的方法及装置

本专利申请要求2013年2月2日提交的题为“Rotate-Mask-Merge and Deposit-Field Instructions for Packet Processing”的美国临时申请61/759,661(代理编号TI-73436PS)的优先权，其通过引用合并于此。

背景技术

计算机硬件可以拦截并记录通过数字网络或一部分数字网络的流量。例如，执行以太网分组交换的计算机硬件单元(通常被称为“交换机”)对于多种功能有要求。一类功能是通常基于将分组与流量表中的条目相匹配来修改分组。这种匹配动作是 OpenFlow标准的一部分。

存在许多类型的分组操作，这些分组操作是有用的，可能甚至是必需的功能，但未被OpenFlow标准所规定。试图呈现基于匹配动作的用户模型的交换的理想属性是它们能够执行通用的和不同类型的分组操作，以便它们能够实现编程这些交换机的用户所期望的动作。

高性能交换机具有有限的时间来处理每个分组。例如，64端口×10Gb每端口的交换机具有640Gb/秒的总带宽。以大小为64字节的最小以太网分组加上约16字节的分组间间隙，对于这样一个交换机的最大分组速率约为每秒960M分组。例如，以 1GHz运行的硬件分组处理流水线每个时钟周期看到一个分组流过流水线(连同约 40MHz的备用带宽)。结果，执行分组操作的硬件要么必须在单个时钟周期内完成其功能，要么该硬件必须流水线化。在任一种情况下，对于单独的分组，不能多次重用硬件进行多次计算。这使得有希望保持分组操作硬件简化。此外，在集成电路上可能存在这种硬件的许多拷贝，为保持硬件简化提供进一步的动机。

发明内容

本发明公开了一种用于在计算机硬件上执行字节旋转合并指令的方法，该方法包括：接收第一源操作数和第二源操作数；将第一源操作数按字节旋转由第一旋转常数指定的数个字节，从而得到第一字节旋转输出；将第二源操作数按字节旋转由第二旋转常数指定的数个字节，从而得到第二字节旋转输出；将第一字节旋转输出与第二字节旋转输出合并在一起而创建字节旋转合并输出，其中字节旋转合并输出包括多个字节，并且其中多个字节中的每个字节具有来自字节掩码的相应控制比特；当来自字节掩码的相应控制比特是逻辑一时，为字节旋转合并输出中的第一字节选择第一字节旋转输出；当来自字节掩码的相应控制比特是逻辑零时，为字节旋转合并输出中的第二字节选择第二字节旋转输出。

本发明公开一种在计算机硬件上执行寄存字段指令的方法，该方法包括：接收源操作数和后台操作数；以及用来自源操作数中指定位置的指定长度替换后台操作数中的指定位置，其中替换由第一移位常数、第二移位常数和第三移位常数确定，并且其中第一移位常数指定源旋转，第二移位常数指定由源操作数修改的后台操作数的最低有效比特边界，而第三移位常数指定由源操作数修改的后台操作数的最高有效比特边界。

本发明公开一种在计算机硬件上执行寄存字段指令的方法，该方法包括：接收源自变量和后台自变量；接收目标位置自变量、源位置自变量和长度自变量；将源自变量旋转ROT自变量而得到字节旋转输出，其中ROT自变量等于目标位置自变量减去源位置自变量；将源位置自变量应用于第一温度计解码器，其中第一温度计解码器的输出使能来自源位置自变量的比特以及更高阶比特；将目标位置自变量加上长度自变量应用于第二温度计解码器，其中第二温度计解码器的输出使能来自目标位置自变量加上长度自变量的比特以及更低阶比特；将第一温度计解码器的输出和第二温度计解码器的输出应用于AND门，其中AND门的输出控制多路复用器。

本发明公开一种用于在计算机硬件上执行字节旋转合并指令的装置，该装置包括：第一旋转电路，其可操作以便将第一源操作数按字节旋转由第一旋转常数指定的数个字节，从而得到第一字节旋转输出；第二旋转电路，其可操作以便将第二源操作数按字节旋转由第二旋转常数指定的数个字节，从而得到第二字节旋转输出；用来确定字节旋转合并输出的字节掩码；多路复用器，其用于接收第一字节旋转输出和第二字节旋转输出、并且输出字节旋转合并输出，其中字节旋转合并输出包括多个字节，并且其中多个字节中的每个字节具有来自字节掩码的相应控制比特；其中，当字节掩码的输出是逻辑一时，来自第一字节旋转输出的第一字节呈现在字节旋转合并输出上；其中，当字节掩码的输出是逻辑零时，来自第二字节旋转输出的第二字节呈现在字节旋转合并输出上。

本发明公开一种用于在计算机硬件上执行寄存字段指令的装置，该装置包括：旋转电路，其可操作以便将源操作数按字节旋转ROT自变量，其中ROT自变量等于目标位置自变量减去源位置自变量；接收源位置自变量的第一温度计解码器；接收目标位置自变量加上长度操作数的第二温度计解码器； AND门，其接收来自第一温度计解码器的输出和来自第二温度计解码器的输出；多路复用器，其接收AND门的输出、旋转电路的输出和后台操作数；其中，第一温度计解码器的输出使来自源位置自变量的比特和更高阶比特能够呈现在多路复用器的输出上；其中，第二温度计解码器的输出使来自目标位置自变量加上长度操作数减去一的比特和更低阶比特能够呈现在多路复用器的输出上。

附图说明

图1A示出了从源操作数中任何位置处获取任何长度字段并将其下移到结果中的比特0的提取指令。(现有技术)

图1B示出了获取来自第一源操作数的低阶比特并替换第二(后台)源操作数的字段的寄存字节(deposit-bype)指令。(现有技术)

图1C根据本发明的一个实施例示出了能够从源操作数中的任何位置获取任何长度字段并将其寄存到后台操作数中的任何位置的寄存字段指令。

图2A是示出寄存字节硬件的框图。(现有技术)

图2B是根据本发明的一个实施例示出寄存字节硬件的框图。

图3A是根据本发明的一个实施例示出寄存字段硬件的框图。

图3B是根据本发明的一个实施例示出用于实现字节旋转合并操作的硬件的框图。

具体实施方式

在一个用于分组处理的体系结构的实施例中，其中在分组被解析之后，报头字段被寄存到由多个独立的8比特、16比特和32比特数据时隙组成的分组报头向量中，每个时隙具有一个伴随有效比特。此分组报头向量中的数据被顺序地发送到多个匹配动作处理级，其中在每一级中，分组报头向量中的字段可以用于匹配该级中的表项 (table entry)，而作为匹配的结果，可以指定能够修改该分组报头向量的内容的动作。动作引擎是VLIW(超长指令字)体系结构，其针对分组报头向量中的每个独立数据字段具有单独的数据处理单元。针对分组报头向量的每个数据时隙，引导动作引擎的操作的指令具有单独的指令字段。因此，对于分组报头向量的每个时隙，动作由单独的处理指令组成。

在包含IPV4(互联网协议版本4)报头的以太网分组中，32比特IP(互联网协议)的源地址和目的地址通常将各自得到分组报头向量中的一个32比特时隙，而分析器将那些时隙中的值寄存为解析该分组的结果。在包含IPV6(互联网协议版本6) 报头的以太网分组中，128比特的IPV6源地址和目的地址将各自保留在分组报头向量的四个32比特的时隙中。

128比特的IPV6被引入是由于IPV4地址的32比特地址空间即将耗尽。在互联网工程任务组IETF RFC6052中给出了用于在IPV4和IPV6格式之间转换地址的一个标准。它规定了用于在IPV4和IPV6之间转换地址的多个安排，如下面来自RFC6052 的表1中所示：

大字节序：

表1：IPV4嵌入式IPV6地址格式

该表规定了如何使用不同长度的前缀(表中PL代表前缀长度)来使IPV6地址能够代表IPV4地址的多种选择。在该表中，u位必须为0，并且后缀位也应该是0。假定一个已知的特定前缀长度，有可能从IPV6地址恢复IPV4地址，而假定一个前缀长度和前缀，有可能将IPV4地址转换成IPV6地址。当然，并不是所有IPV6地址都能够转换成IPV4地址，但如果已知该IPV6地址是以此方式使用特定的前缀长度从IPV4地址创建的，则有可能恢复该IPV4地址。

虽然上述表1以大字节序(big-endian)格式指定，但当后面讨论硬件时，小字节序(little-endian)是优选的，其中比特0始终是lsb(最低有效比特)。下面以小字节序表示来重现上表：

小字节序：

表2：小字节序的IPV4嵌入式IPV6地址格式

在分组报头向量V6[3:0]的四个32比特时隙阵列中将包含一个128比特的IPV6 地址，其中v6[3]包含最高有效32比特，而v6[0]包含最低有效32比特，如下表3所示：

表3：IPV6分组报头向量字段

为了根据本发明执行IPV6到IPV4的转换，对于前缀长度(PL)的每个选择，从IPV6地址中抽出多组不同比特并连接在一起，如表4所示。这里，信号<bh:bl>代表从高比特bh(高位)到低比特bl(低位)的信号。如果这些比特是原始信号的完整比特宽度的子集，则这种标记法可以被视为从原始完整信号中提取期望的比特字段。下面的符号“::”表示连接两个向量，较高有效的向量在左侧。例如，#xabcd::#xef 是#xabcdef。

表4：IPV6到IPV4的提取和合并操作

如果上表中的v6IPV6地址字段被表示为它们的32比特分组报头向量字V6 [3:0]，则操作变为：

表5：对分组报头向量字的提取和合并操作

虽然对于PL＝32或96不需要操作，但来自不同分组报头向量字的其他PL的两个字段必须被提取和合并。

在本发明的这个实施例中，合并可以被描述为两个操作的序列。在第一操作中，两个数据源被分别独立地移入输出字中它们正确的结束位位置，然后在第二操作中，掩码为该输出的每个比特选择这些源的一个或另一个(即逐比特选择)。对于本讨论，按照惯例，两个源中的第一个将最终形成该输出的较高有效部分，而第二个将形成该输出的较低有效部分。第一个源将被左移以使其比特与正确的输出位置对齐，而第二个源将被右移。对于字节中的每一比特，选择一个源或另一个源的掩码具有相同的值，因此它可以被指定为一个4比特的向量，每个字节对应1比特，如#b1110，这意味着二进制的1110。每个掩码比特的解释是：如果它是1，则选择第一个源，而如果它是 0，则选择第二个源。这些操作可以由移位和掩码运算符来表示。使用移位运算符句法是(移位数据移位量)，其中数据是一个32比特的字，移位量是以字节为单位，并且移位运算符是shlb(左移一定数量的字节)和shrb(右移一定数量的字节)。掩码运算符句法是(掩码掩码值源1源2)，其中对于这些32比特的数字，掩码值是 4比特宽，并且这两个源是32比特宽。在表6中功能性地描述了对于每个PL的计算的移位和掩码操作：

表6：移位和掩码操作

一般而言，左移或右移在输入数据字的一端或另一端上执行符号或零扩展。该复杂化是不必要的，因为在移位之后，没有零或符号扩展比特被掩码选择。所以可以通过更简单的旋转操作替换该移位：rotlb(循环左移一定数量的字节)或rotrb(循环右移一定数量的字节)，如表7所示：

表7：旋转和掩码操作

最后，应认识到，将32比特源循环左移以比特为单位的旋转计数与将该源循环右移32减去该旋转计数之差(模32)相同，或等价地，将32比特源循环左移以字节为单位的旋转计数与将该源循环右移4减去该字节旋转计数之差(模4)相同。所有旋转功能可被改变成在单一方向上旋转，如表8所示：

表8：右旋和掩码功能

本发明的这个实施例被称为字节旋转合并(byte-rotate-merge)。在提供通用比特操作能力的第二创造性指令的描述之后，将讨论该指令的硬件成本。

作为字节旋转合并实施例的一种替代实施方式，应该认识到的是：如果两个源操作数是等同的和可互换的，亦即两个操作数都能够来源于相同的输入，则第一源可以被用作向较高有效的一半输出进行输出的源，第二源可以被用作向较低有效的一半输出进行输出的源，并且在那些情况下，为了生成IPV4地址，掩码常数将始终是较高有效部分中的多个1，后面跟着较低有效部分中的多个0。然后可以将掩码常数可替换地编码成两比特作为最低有效1的位置。为了普遍性，也可能具有带有多个较高有效0和较高有效1的掩码，并且可替换地将该掩码常数编码为最低有效零的位置。这两种方法在逻辑上是等效的，所以可以被视为相同的方法。与此等效的是将该掩码编码为来自同一来源的多个最低有效字节。

现在将讨论本发明的第二实施例。处理器有一个提取指令是很常见的，它将之前描述的运算执行为提取；它从一个完整的字中获取特定字段，将该特定字段向下移位至比特位置零，并清除(或符号扩展)高于其定义长度的所有比特，如图1A中所示。例如，从32比特信号sig<31:0>中提取的sig<23:16>是通过如下来执行：将该信号向右移位16比特，并且归零在字段长度之上的所有比特，在这种情况下字段长度是8 比特(从23到16)，所以归零比特31到8。如果提取被描述为一个函数(提取数据字lobit(低阶比特)长度)，则数据向右移位lobit，并且除了<长度>低比特之外的所有比特都归零(或符号扩展)。例如，(提取#x12345678 16 8)是#x34，即源数据的比特<23:16>。

第二个现有技术指令是寄存字节，其中第一源操作数的低阶比特替换第二(后台)源操作数的字段，如图1B中所示。第二操作数中要被替换的字段由高比特H和低比特L定义，并且替换该字段的比特是第一操作数的lsb。该字段具有宽度H-L+1。以低比特和长度编码而不是高比特和低比特编码是等价的。如果寄存字节指令的句法是 (寄存字节源数据后台数据位置长度)，则(寄存字节#x12345678#xbbbbbbbb 16 8)是#xbb78bbbb；第一源操作数#x12345678的低8比特已经替换了第二(后台)操作数xbbbbbbbb的比特<23:16>。

本发明的第二实施例提供了更强大和任意的比特操作能力。提取指令可以从源操作数中任何位置处取得任何长度字段，并将其向下移动到结果中的比特0，如图1A 所示。寄存字节指令可以在后台操作数中任何位置处取得任何长度的目标字段，并用源操作数的低阶比特将其替换，如图1B所示。本发明的一个实施例提供了一种寄存字段指令，该寄存字段指令可以从源操作数中任何位置处取得任何长度字段，并将它寄存入后台操作数中的任何位置，如图1C所示。

除了源数据操作数和后台数据操作数之外，该寄存字段指令还需要三个移位常数：源位置、目标位置和长度。三个移位常数的可替换编码是可能的和等效的，例如，使用源位置、目标位置和目标高比特。该指令不同于传统的提取和寄存字节指令，传统的提取和寄存字节指令仅需要两个移位常数：一个位置和长度。该寄存字段指令提供了一种更通用的能力，用以从任何地方提取字段并将其寄存到任何地方。在缺少该指令的情况下，该通用操作将需要两个指令，即，加载字节(load-byte)指令后跟寄存字节指令，其中第一指令提取要寄存的字段，第二指令将该字段寄存到后台字中。在没有寄存字段指令的情况下，表8的4个操作与旋转和掩码功能性描述将都需要两个操作而不是一个(除了PL 56，其中一个旋转计数为0，并且一个寄存字节指令即可完成)。

与常规寄存字节指令相比，该寄存字段指令可以用最小的额外成本来实现。常规寄存字节硬件200在图2A中示出。旋转器电路204将源数据201循环左移(ROTL) 源位置自变量202的值。由多路复用器(MUX)210选择旋转器数据214而不是后台数据215，其中多路复用器210的每个比特被独立地控制(即逐比特选择)。由使能信号216选择旋转器数据214。该使能信号216是通过分别对两个温度计解码器(TH)206和208的结果218和220执行AND功能212而产生的，其中一个温度计解码器使能来自源位置以及更高位置的比特，而另一个温度计解码器使能来自目标位置+长度-1以及更低位置的比特。多路复用器210的输出是节点209。

图2B示出了根据本发明的实施例实现寄存字段指令所需的硬件222。旋转器计数从源位置自变量202变化到新旋转自变量ROT。该ROT自变量等于目标位置减去源位置(针对以旋转计数自变量循环左移的旋转器)。注意，由于所有的移位常数仅仅是常数，它们可以使用可替换的编码来降低复杂性，应该认识到最终需要三个5 比特常数。可以指定旋转计数、第二目标位置和第三位置+长度。结果，无需硬件来增加或减去移位常数。对于寄存字段指令，无需多于寄存字节指令的额外的数据通路硬件，而唯一的改变是，该旋转器由新的附加自变量ROT控制。

执行字节旋转合并指令的额外成本可以通过检查图3A的简化寄存字段示意图来理解。此处多路复用器210的控制信号216的控制逻辑已经被合并到掩码块302中，且两个温度计解码器218和220的结果被馈送到掩码块302中。图3B也示出了执行字节旋转合并所需要的增强。现在后台数据215具有在它与多路复用器210之间的字节旋转器312。掩码块302具有额外的输入字节掩码310，其控制多路复用器210基于每个字节而选择字节旋转合并指令。图3B中的输出209是字节旋转合并输出。字节旋转器312例如一个32比特的4输入多路复用器是主要的附加硬件，字节旋转器 312连同一些小的附加逻辑来控制掩码块302。注意，附加的旋转器312是字节旋转器，仅旋转0比特、8比特、16比特或24比特，而先前存在的旋转器能够旋转所有 32比特的位置。

为了图示说明和描述的目的，已经展示了前面的描述。它并非意图是穷尽的或将本发明限制为所公开的精确形式，并且根据上述教导的其他修改和变化是可能的。选择和描述这些实施例是为了最好地解释适用的原则及其实际应用，从而使本领域技术人员能够最佳地利用各种实施例和适合于预期的特定用途的各种修改。旨在将所附权利要求解释为包括其他可选的实施例，除了由现有技术所限定的范围。

Claims (7)

1.一种用于在计算机硬件上执行字节旋转合并指令的方法，所述方法包括：

接收第一源操作数和第二源操作数；

将所述第一源操作数按字节旋转由第一旋转常数指定的数个字节，从而得到第一字节旋转输出；

将所述第二源操作数按字节旋转由第二旋转常数指定的数个字节，从而得到第二字节旋转输出；

将所述第一字节旋转输出与所述第二字节旋转输出合并在一起而创建字节旋转合并输出，其中所述字节旋转合并输出包括多个字节，并且其中所述多个字节中的每个字节具有来自字节掩码的相应控制比特；

当来自所述字节掩码的相应控制比特是逻辑一时，为所述字节旋转合并输出中的第一字节选择所述第一字节旋转输出；

当来自所述字节掩码的相应控制比特是逻辑零时，为所述字节旋转合并输出中的第二字节选择所述第二字节旋转输出。

2.根据权利要求1所述的方法，其中所述字节掩码被编码为来源于供应低阶字节的操作数的输出字节的数量。

3.一种在计算机硬件上执行寄存字段指令的方法，所述方法包括：

接收源操作数和后台操作数；以及

用来自所述源操作数中指定位置的指定长度替换所述后台操作数中的指定位置，其中所述替换由第一移位常数、第二移位常数和第三移位常数确定，并且其中所述第一移位常数指定源旋转，所述第二移位常数指定由所述源操作数修改的所述后台操作数的最低有效比特边界，而所述第三移位常数指定由所述源操作数修改的所述后台操作数的最高有效比特边界。

4.一种在计算机硬件上执行寄存字段指令的方法，所述方法包括：

接收源自变量和后台自变量；

接收目标位置自变量、源位置自变量和长度自变量；

将所述源自变量旋转ROT自变量而得到字节旋转输出，其中所述ROT自变量等于所述目标位置自变量减去所述源位置自变量；

将所述源位置自变量应用于第一温度计解码器，其中所述第一温度计解码器的输出使能：来自所述源位置自变量的比特；以及更高阶比特；

将所述目标位置自变量加上所述长度自变量应用于第二温度计解码器，其中所述第二温度计解码器的输出使能：来自所述目标位置自变量加上所述长度自变量的比特；以及更低阶比特；

将所述第一温度计解码器的输出和所述第二温度计解码器的输出应用于AND门，其中所述AND门的输出控制多路复用器。

5.一种用于在计算机硬件上执行字节旋转合并指令的装置，所述装置包括：

第一旋转电路，其可操作以便将第一源操作数按字节旋转由第一旋转常数指定的数个字节，从而得到第一字节旋转输出；

第二旋转电路，其可操作以便将第二源操作数按字节旋转由第二旋转常数指定的数个字节，从而得到第二字节旋转输出；

用来确定字节旋转合并输出的字节掩码；

多路复用器，其用于：接收所述第一字节旋转输出和所述第二字节旋转输出；并且输出所述字节旋转合并输出，其中所述字节旋转合并输出包括多个字节，并且其中所述多个字节中的每个字节具有来自所述字节掩码的相应控制比特；

其中，当所述字节掩码的输出是逻辑一时，来自所述第一字节旋转输出的第一字节呈现在所述字节旋转合并输出上；

其中，当所述字节掩码的输出是逻辑零时，来自所述第二字节旋转输出的第二字节呈现在所述字节旋转合并输出上。

6.根据权利要求5所述的装置，其中所述字节掩码被编码为来源于供应低阶字节的操作数的输出字节的数量。

7.一种用于在计算机硬件上执行寄存字段指令的装置，所述装置包括：

旋转电路，其可操作以便将源操作数按字节旋转ROT自变量，其中所述ROT自变量等于目标位置自变量减去源位置自变量；

接收所述源位置自变量的第一温度计解码器；

接收所述目标位置自变量加上长度操作数的第二温度计解码器；

AND门，其接收来自所述第一温度计解码器的输出和来自所述第二温度计解码器的输出；

多路复用器，其接收所述AND门的输出、所述旋转电路的输出和后台操作数；

其中，所述第一温度计解码器的输出使来自所述源位置自变量的比特和更高阶比特能够呈现在所述多路复用器的输出上；

其中，所述第二温度计解码器的输出使来自所述目标位置自变量加上所述长度操作数减去一的比特和更低阶比特能够呈现在所述多路复用器的输出上。