执行串匹配的装置和方法

摘要

各种实施例一般目的在于克服矢量寄存器在它们在位并行串匹配算法的情况下的使用中的限制。一种装置包括：处理器元件；以及逻辑，所述逻辑用以接收包括第一串元素的型式以用在串匹配操作中，在处理器元件的第一矢量寄存器中实例化测试位掩码，所述第一矢量寄存器包括多个分道，将第一矢量寄存器的多个分道的MSB位位置处的位值拷贝到第一矢量掩码作为矢量值，作为标量值而位移位矢量值，位移位第一矢量寄存器，采用第一矢量掩码的矢量值以选择性地填充处理器元件的第二矢量寄存器的分道的LSB位位置；并且将第二矢量寄存器向第一矢量寄存器中进行“或”运算。描述和要求保护其它实施例。

权利要求

1.一种执行串匹配的装置，包括：

处理器元件；以及

逻辑，用以：

接收包括第一串元素的型式，以用在串匹配操作中；

在处理器元件的第一矢量寄存器中实例化测试位掩码，所述第一矢量寄存器包括多个分道；

将第一矢量寄存器的多个分道的最高有效位(MSB)位置处的位值拷贝到第一矢量掩码，作为矢量值；

位移位矢量值作为标量值；

位移位第一矢量寄存器；

采用第一矢量掩码的矢量值，以选择性地填充处理器元件的第二矢量寄存器的分道的最低有效位(LSB)位置；以及在按位逻辑或运算中将第二矢量寄存器组合到第一矢量寄存器中。

2.根据权利要求1所述的装置，所述逻辑用以接收包括第二串元素的序列，以用在串匹配操作中，所述串匹配操作标识序列内型式的出现。

3.根据权利要求2所述的装置，包括显示器，所述逻辑用以视觉地呈现是否在序列内发现型式的指示。

4.根据权利要求2所述的装置，所述逻辑用以向计算设备传输对是否在序列内发现型式进行指示的结果数据，从所述计算设备经由网络而接收型式和序列中的至少一个。

5.根据权利要求1所述的装置，处理器元件基于单指令多数据(SIMD)架构。

6.根据权利要求1所述的装置，所述逻辑用以：在按位逻辑与运算中组合第一矢量寄存器与充当MSB掩码的第三矢量寄存器，以将第一矢量寄存器的多个分道的MSB位位置处的位值拷贝到第一矢量掩码；

采用矢量值，以用1选择性地填充第二矢量寄存器的分道的位；以及在按位逻辑与运算中组合第二矢量寄存器与充当LSB掩码的第四矢量寄存器，以选择性地填充第二矢量寄存器的分道的LSB位位置。

7.根据权利要求1所述的装置，所述逻辑用以：计算存储测试位掩码所需的第一矢量寄存器的分道的数量，所述测试位掩码具有等于第一串的元素数量的位长度；

采用第二矢量掩码，以选择性填充对于存储测试位掩码所需的第一矢量寄存器的所述数量的分道；以及右移位所述数量的分道的最高有效分道，以将跨所述数量的分道的全部而填充的位数调整成等于测试位掩码的位长度。

8.根据权利要求7所述的装置，所述逻辑用以用1选择性地填充第一矢量寄存器的所述数量的分道的所有位。

9.根据权利要求1所述的装置，所述逻辑用以：在处理器元件的第三矢量寄存器中初始化指示元素出现于的第一串内的位置的位掩码；

在按位逻辑与运算中组合第三矢量寄存器与第一矢量寄存器；以及确定测试位掩码的MSB位处的位值，以确定是否在序列内发现型式。

10.一种执行串匹配的装置，包括：

处理器元件；以及

逻辑，用以：

接收包括第一串元素的型式，以用在串匹配操作中；

计算存储测试位掩码所需的处理器元件的第一矢量寄存器的分道的数量，所述测试位掩码具有等于第一串的元素数量的位长度；

采用第一矢量掩码，以选择性填充对于存储测试位掩码所需的第一矢量寄存器的所述数量的分道；以及右移位所述数量的分道的最高有效分道，以将跨所述数量的分道的全部而填充的位数调整成等于测试位掩码的位长度。

11.根据权利要求10所述的装置，所述逻辑用以用1选择性地填充第一矢量寄存器的所述数量的分道的所有位。

12.根据权利要求10所述的装置，所述逻辑用以：接收包括第二串元素的序列，以用在串匹配操作中，所述串匹配操作标识在序列内型式的出现；

在处理器元件的第三矢量寄存器中初始化指示元素出现于的第一串内的位置的位掩码；

在按位逻辑与运算中组合第三矢量寄存器与第一矢量寄存器；以及确定测试位掩码的最高有效位(MSB)处的位值，以确定是否在序列内发现型式。

13.根据权利要求12所述的装置，包括显示器，所述逻辑用以视觉地呈现是否在序列内发现型式的指示。

14.根据权利要求12所述的装置，所述逻辑用以向计算设备传输对是否在序列内发现型式进行指示的结果数据，从所述计算设备经由网络而接收型式和序列中的至少一个。

15.根据权利要求10所述的装置，所述逻辑用以：将第一矢量寄存器的多个分道的MSB位位置处的位值拷贝到第二矢量掩码，作为矢量值；位移位矢量值作为标量值；

位移位第一矢量寄存器；

采用第二矢量掩码的矢量值，以选择性地填充处理器元件的第二矢量寄存器的分道的LSB位位置；以及在按位逻辑或运算中将第二矢量寄存器组合到第一矢量寄存器中。

16.根据权利要求15所述的装置，所述逻辑用以：在按位逻辑与运算中组合第一矢量寄存器与充当MSB掩码的第三矢量寄存器，以将第一矢量寄存器的所述数量的分道的MSB位位置处的位值拷贝到第二矢量掩码；

采用矢量值，以用1选择性地填充第二矢量寄存器的分道的位；以及在按位逻辑与运算中组合第二矢量寄存器与充当LSB掩码的第四矢量寄存器，以选择性地填充第二矢量寄存器的分道的LSB位位置。

17.一种执行串匹配的计算机实现的方法，包括：接收包括第一串元素的型式以及包括第二串元素的序列以用在串匹配操作中，以确定型式是否存在于序列内；

在处理器元件的第一矢量寄存器中实例化测试位掩码，所述第一矢量寄存器包括多个分道；将第一矢量寄存器的多个分道的最高有效位(MSB)位置处的位值拷贝到第一矢量掩码，作为矢量值；

位移位矢量值作为标量值；

位移位第一矢量寄存器；

采用第一矢量掩码的矢量值，以选择性地填充处理器元件的第二矢量寄存器的分道的最低有效位(LSB)位位置；以及将第二矢量寄存器向第一矢量寄存器中进行“或”运算。

18.根据权利要求17所述的计算机实现的方法，第一和第二串包括文本或DNA序列中之一的串。

19.根据权利要求17所述的计算机实现的方法，包括：从控制装置或网络中的至少一个接收信号，所述信号传送型式和序列中的至少一个。

20.根据权利要求17所述的计算机实现的方法，包括：在显示器上视觉地呈现是否在序列内发现型式的指示。

21.根据权利要求17所述的计算机实现的方法，包括：向计算设备传输对是否在序列内发现型式进行指示的结果数据，从所述计算设备经由网络而接收型式和序列中的至少一个。

22.根据权利要求17所述的计算机实现的方法，包括：在串匹配操作中采用后向非确定性DAWG匹配(BNDM)算法。

23.根据权利要求17所述的计算机实现的方法，包括：在处理器元件的第三矢量寄存器中初始化指示元素出现于的第一串内的位置的位掩码；

将第三矢量寄存器与第一矢量寄存器进行“与”运算；以及确定测试位掩码的MSB位处的位值，以确定是否在序列内发现型式。

24.包括指令的至少一个机器可读介质，所述指令在由计算设备执行时使得计算设备执行权利要求17-23中任一项的方法。

说明书

执行串匹配的装置和方法

技术领域

[0001] 本文所述的实施例一般涉及使能在位并行匹配中SIMD寄存器的全宽度的高效使用。

背景技术

[0002] 串匹配算法广泛用于网络安全、加密、商业分析、脚本和标记语言的处理、搜索引擎的领域中，并且用作软件编译器和解释器的组件。作为其普遍使用的结果，众多情形下的可用计算能力的相当大比例致力于执行这些算法。

[0003] 在串匹配算法中，搜索一个较大的串，为的是在其中另一个较小的串的出现。被搜索的较大的串经常被称为“序列”，而较小的串(为了其出现而搜索较大的串)经常被称为“型式(pattern)”。这两个串都可以由字符、表示诸如DNA序列元素之类的信息的符号或各种类型的数据中的任一个组成。本质上，串是数据元素的一维阵列，一个数据元素用于阵列中的每个位置。用于阵列中每个元素的可能值的集合经常被称为“字母表(alphabet)”。

[0004] 随着时间的推移，已经设计出串匹配算法的许多变型。在较新近的变型之中是位并行串匹配算法，所述算法采用位值和位掩码(bitmask)来表示在型式和/或序列中每个位
置处特定数据值的出现。这些位并行变型中的许多实现相当大的效率，其中型式的长度(即组成型式的一维阵列中的位置的数量)小于或等于处理器的一个或多个寄存器中位的数
量。在型式的长度大于处理器的寄存器中位的数量的情况下仍然可以使用这些位并行变
型，但是这导致需要在存储器中创建数据结构，以提供更宽的处理器寄存器的等效物。

[0005] 具有32位或64位宽度的寄存器的处理器久已常见，并且由于许多目的而采用高效地适应位并行串匹配算法的现今足够宽的寄存器。此外，处理器架构中的新近进展已经使
得能够引进具有128位、256位和512位寄存器的处理器，因而潜在地以相当大的效率而适应日益更大的型式。然而，考虑到数值数据的典型片段往往需要不多于64位来被表示，更大宽度的寄存器倾向于被细分为64位宽度或更少的两个或更多个分道(lane)，以使得能够并排
保持多个数据值。这样的处理器的指令集还利用这样的指令被扩充：所述指令使得能够并
行地同时执行那些并排的值上的按位逻辑、算术和其它指令。这样的寄存器和指令往往分
别被称为“矢量寄存器”和“矢量指令”。此外，实现具有矢量指令的矢量寄存器的处理器架构被称为SIMD(单指令多数据)架构。细分这样的宽寄存器的方式和实现支持其使用的指令
集的方式的一个副产物是仅仅为位的移位操作提供支持的倾向，其中在这些寄存器之一内
的分道的一端或两端处的位值丢失。这一个实现细节在支持更长的型式中呈现对于使用这
样的非常宽的寄存器的全宽度的阻碍。是关于这些和其它考虑而需要本文所述的实施例的

发明内容

[0006] 根据一个实施例，执行串匹配的装置包括：处理器元件；以及逻辑，用以：接收包括第一串元素的型式，以用在串匹配操作中；在处理器元件的第一矢量寄存器中实例化测试位掩码，所述第一矢量寄存器包括多个分道；将第一矢量寄存器的多个分道的最高有效位 (MSB)位置处的位值拷贝到第一矢量掩码，作为矢量值；位移位矢量值作为标量值；位移位第一矢量寄存器；采用第一矢量掩码的矢量值，以选择性地填充处理器元件的第二矢量寄
存器的分道的最低有效位(LSB)位置；以及在按位逻辑或运算中将第二矢量寄存器组合到
第一矢量寄存器中。

附图说明

[0007] 图1图示在设备之间的交互的实施例的方面。

[0008] 图2图示图1的实施例的变型的方面。

[0009] 图3图示图1的实施例中的串匹配的概念方面。

[0010] 图4a-c图示图3的概念方面的进一步的细节。

[0011] 图5a-b图示图1的实施例中的串匹配的按位实现的方面。

[0012] 图6a-e图示图5a-b的实现的另外的方面。

[0013] 图7图示图1的实施例的一部分的框图。

[0014] 图8图示第一逻辑流的实施例。

[0015] 图9图示第二逻辑流的实施例。

[0016] 图10图示处理架构的实施例。

具体实施方式

[0017] 各种实施例一般目的在于增强位并行串匹配算法来克服SIMD架构的矢量寄存器的位的移位限制，以使得能够在那些寄存器的情况下使用这样的算法。更具体地，位并行串匹配算法被增强以利用矢量指令来克服位的移位操作中的分道到分道限制，其中在用于一
个或多个宽的位掩码的矢量寄存器的分道之间不进位(carry)位值。

[0018] 这样的矢量寄存器可以用来存储由各种位并行串匹配算法采用的、在那些算法的执行期间频繁被进行位的移位的类型的测试位掩码。如将更详细地描述的，克服进位位值
丢失的技术可以包括：通过按位操作将MSB位的位置处的位值的拷贝保存为矢量掩码
（vector mask）中的矢量值，作为标量值而对矢量值进行位的移位。现在经移位的矢量值然后用于控制充当位进位掩码的另一个矢量寄存器的LSB位的填充，并且在已经对测试位掩
码进行了位的移位以还原以其它方式缺失的位值之后，位进位掩码与存储了测试位掩码的
矢量寄存器进行“或”运算。

[0019] 这样的矢量寄存器的初始化可能需要首先选择性地填充在其中存储测试位掩码的矢量寄存器的分道，并且然后将其中存储测试位掩码的那些分道中的最高有效的一个分
道位移位到右边以调整填充值（被预想为全1，但可以是不同的填充值）的总体长度，以匹配测试位掩码型式的位长度。不同的位并行串匹配算法用不同程度的频率来移位和/或重新
初始化测试位掩码型式。然而，二者足够频繁地发生，以使得位并行匹配算法的执行的效率可以通过使用本文所述的技术而显著增强。

[0020] 一般参照本文所用的记号和命名法，可以在计算机或计算机网络上执行的程序过程的方面呈现随后的具体实施方式的部分。这些过程性描述和表示由本领域技术人员用来
将其工作的实质最有效地传达给本领域其他技术人员。过程在这里并且一般被设想为导致
期望的结果的操作的自相一致序列。这些操作是需要物理量的物理操纵的那些操作。通常，虽然不是必要地，这些量采取能够被存储、传递、组合、比较和以其它方式操纵的电学、磁性或光学信号的形式。主要由于常见使用的原因，将这些信号称为位、值、元素、符号、字符、项、数字等等有时证明​​是方便的。然而，应当注意的是：所有这些和类似的术语将与适当的物理量相关联，并且仅仅是应用于那些量的方便的标签。

[0021] 此外，经常在通常与由人类操作员执行的智力操作相关联的术语（诸如添加或比较）中提及这些操纵。然而，在形成一个或多个实施例的部分的本文所述的任何操作中，没有任何这样的人类操作员能力是必要的，或在大多数情况下是合期望的。相反，这些操作是机器操作。用于执行各种实施例的操作的有用机器包括如由存储在内的根据本文教导所编
写的计算机程序而被选择性地激活或配置的通用数字计算机，和/或包括为了所需目的而
特别地构造的装置。各种实施例还涉及用于执行这些操作的装置或系统。这些装置可以为
了所需目的而被特别地构造，或者可以合并通用计算机。用于各种各样的这些机器的所需
结构将从给出的描述中显现。

[0022] 现在对附图作出参考，其中同样的参考标号贯穿全文用于指代同样的元件。在下面的描述中，为了解释的目的，阐述许多具体细节，以便提供对其的透彻理解。然而，可以实践新颖的实施例而没有这些具体细节可以是显而易见的。在其它实例中，以框图形式示出
公知的结构和设备，以使得便于其描述。意图是覆盖权利要求的范围内的所有修改、等同物和替代方案。

[0023] 图1和2一起描绘在串匹配系统1000的两个可能的变型的计算设备之间的交互的方面的框图。每个变型包括一个或多个搜索设备100和交互设备300，搜索设备100利用SIMD架构的矢量寄存器而执行位并行串匹配，交互设备300可以为搜索设备100所执行的串匹配
提供型式和/或序列。这些计算设备100和300中的每一个可以是各种类型的计算设备中的
任一个，包括而不限于：台式计算机系统、数据录入终端、膝上型计算机、上网本计算机、超级本计算机、平板计算机、手持式个人数据助理、智能电话、数码相机、移动设备、合并到服装中的身体佩带的计算设备、集成到车辆中的计算设备、服务器、服务器集群、服务器农场等。

[0024] 如针对两个变型所描绘的，这些计算设备100和300可以交换信号，其传送包括用于位并行匹配操作的执行的序列和/或型式的数据和/或包括这样的操作的结果的指示的
数据。然而，这些计算设备中的一个或多个可以交换其它不同的和完全无关的数据。在各种实施例中，网络999可以是可能限于在单个建筑物或其它相对有限的区域内扩展的单个网
络、可能扩展相当大距离的连接的网络的组合，和/或可以包括因特网。因而，网络999可以基于可以通过其而交换信号的各种通信技术（或其组合）中的任一个，包括而不限于：采用电学和/或光学传导的线缆敷设的有线技术，以及采用红外、射频或其它形式的无线传输的无线技术。还应当注意的是：可以替代地在这些计算设备中的两个多个之间经由可移除存
储装置（例如基于FLASH（闪速）存储器技术的固态存储装置、光盘介质等）交换这样的数据。

[0025] 在图1的变型的各种实施例中，搜索设备100合并处理器元件150、存储装置160、控制装置120、显示器180和将搜索设备100耦合到网络999的接口190中的一个或多个。存储装置160存储控制例程140、序列531、型式532和结果数据539中的一个或多个。在图2的变型的各种实施例中，搜索设备100另外合并控制器200，控制器200本身合并处理器元件250和存储装置260。存储装置160存储控制例程140，并且存储装置260存储控制例程240、序列531、型式532和结果数据539中的一个或多个。

[0026] 在图2的变型中，预想的是：控制器200和与处理器150和存储装置160完全分离的处理器元件200和存储装置260的合并可以被视为合期望的，以提供第二和完全分离的操作
环境。换句话说，处理器元件250和存储装置260定义与至少由处理器元件150和存储装置
160定义的操作环境基本上分离的操作环境的部分。控制器200内的该分离的操作环境使得
能够在大大降低的被可以由处理器元件150执行的其它不太值得信任的软件损害的风险的
情况下执行位并行串匹配算法。这可以被视为是重要的，其中位并行匹配算法由处理器元
件250执行，作为加密、验证或其它安全功能的部分。存储装置260内序列531、型式532和结果数据539中的一个或多个的存储帮助进一步确保这些中没有一个通过被变更以击败安全
措施或出于某种其它目的而遭损害。

[0027] 在各种实施例中，交互设备300合并处理器元件350、存储装置360、控制装置320、显示器380和将交互设备300耦合到网络999的接口390中的一个或多个。存储装置360存储控制例程340、序列531、型式532和结果数据539中的一个或多个。序列531和型式532各自可以是各种类型的数据中任一个的至少一部分，这取决于搜索设备100执行位并行串匹配所
为的目的。结果数据539包括是否在序列531内和/或在序列531内的（一个或多个）什么位置处发现型式532的指示。

[0028] 在包括交互设备300的图1和图2二者的变型的实施例中，交互设备300可以向搜索设备100提供序列531和型式532中的一个或两个，作为用于执行位并行串匹配的输入。可替代地或另外，在这样的操作的执行之后，交互设备300可以从搜索设备100接收结果数据
539。数据531、532和/或539的这些片段的交换可以通过网络999。这样的交换可以由采用由控制装置320和显示器380组成的用户接口的交互设备300的操作者产生，以指示对于信息
的所期望的搜索，使得型式532可以表示由该操作者指定的搜索项。可替代地，这样的交换可以由认证过程产生，使得序列531和/或型式532中的一个或另一个可以各自是公共或私
有密钥、将用密钥数字签名的消息、通过使用密钥而对消息签名所创建的数字签名等的至
少一部分。如加密和数字签名验证领域的技术人员将容易地认识到：串匹配经常用于执行
这样的安全功能。

[0029] 可替代地，以及在包括或不包括交互设备300的图1和2二者的变型的实施例中，搜索设备100可以经由搜索设备100的操作者对控制装置120的操作而接收序列531和型式532
中的一个或两个。此外，搜索设备100可以在显示器180上视觉呈现位并行串匹配的结果的
指示。序列531和型式532中的一个或二者的这样的供应和/或结果数据539的这样的呈现可
以起于在可能需要供应密码、指纹扫描、面部的图像捕获或其它安全相关的数据（其变成用于位并行串匹配的序列531或型式532之一）的过程中搜索设备100的操作者登录到搜索设
备100中。

[0030] 更具体地转向图1的变型，在执行控制例程140中，使得处理器元件150执行位并行串匹配。在这样做中，处理器元件150采用被划分成分道的处理器元件150的至少一个矢量
寄存器，并且处理器元件150的矢量指令集包括一个或多​​个位移位指令，其中不越过相邻分道之间而进位位。控制例程140合并指令，所述指令在由处理器元件150执行时使得处理
器元件150克服该位进位缺乏，如将被更详细地解释的。

[0031] 更具体地转向图2的变型，在执行控制例程140中，处理器元件150可以为执行位并行串匹配操作的处理器元件250提供支持，而不是处理器元件150这样做。因而，是处理器元件250通过控制例程240的执行而被使得通过使用被划分成分道的处理器元件250的矢量寄
存器来执行位并行串匹配，并且其中处理器元件250的矢量指令集包括一个或多个位移位
指令，其中不越过相邻分道之间而进位位。因而，在该变型中，是控制例程240合并指令，所述指令在由处理器元件250执行时使得处理器元件250克服该位进位缺乏。可以采用该变
型，其中位并行串匹配被执行为加密验证和/或其它安全相关的目的的部分。

[0032] 在各种实施例中，处理器元件150、250和350中的每一个可以包括多种商业上可得到的处理器中的任一个，包括而不限于：AMD® Athlon®，Duron®或Opteron®处理器；AMD 
Radeon™图形处理器；Analog Devices® Sharc®或TigerSharc™数字信号处理器；ARM®
应用、嵌入式或安全处理器；IBM®和/或Motorola® DragonBall®或PowerPC®处理器；
IBM和/或Sony® Cell(单元)处理器；Nvidia® GeForce®，Quadro®，Tesla™，Ion™或
PureVideo™图形处理器；Texas Instruments® DaVinci™数字信号视频处理器；或Intel
® Celeron®，Core(2) Duo®，Core(2) Quad®，Core i3®，Core i5®，Core i7®，Atom
®，Itanium®，Pentium®，Xeon®或XScale®处理器。此外，这些处理器元件中的一个或多
个可以包括多核处理器（无论多个核共存于相同的还是分离的管芯上）和/或多个物理上分离的处理器通过其而以某种方式链接的某个其它种类的多处理器架构。

[0033] 在各种实施例中，存储装置160、260和360中的每一个可以基于多种信息存储技术中的任一个，可能包括需要不间断地供应电力的易失性技术，并且可能包括需要使用可以
是或可以不是可移除的机器可读存储介质的技术。因而，这些存储装置中的每一个可以包
括多种类型（或类型的组合）的存储设备中的任一个，包括而不限于：只读存储器（ROM）、随机存取存储器（RAM）、动态RAM（DRAM）、双数据速率DRAM（DDR-DRAM）、同步DRAM（SDRAM）、静态RAM（SRAM）、可编程ROM（PROM）、可擦除可编程ROM（EPROM）、电可擦除可编程ROM（EEPROM）、闪速存储器、聚合物存储器（例如铁电聚合物存储器）、奥氏存储器、相变或铁电存储器、硅-氧化物-氮化物-氧化物-硅（SONOS）存储​​器、磁卡或光卡、一个或多个单独的铁磁盘驱动器或者被组织成一个或多个阵列的多个存储设备（例如被组织成独立磁盘阵列的冗余阵列或
者RAID阵列的多个铁磁盘驱动器）。应当注意的是：虽然这些存储装置中每一个被描绘为单个块，但这些中的一个或多个可以包括可以基于不同存储技术的多个存储设备。因而，例
如，这些描绘的存储装置中每一个的一个或多个可以表示以下的组合：程序和/或数据可以通过其而在某种形式的机器可读存储介质上被存储和传送的光学驱动器或闪速存储器卡
读取器，用以在相对延长的时段内本地存储程序和/或数据的铁磁盘驱动器，以及使得能够相对快地访问程序和/或数据的一个或多个易失性固态存储器设备（例如SRAM或DRAM）。还应当注意的是：这些存储装置中的每一个可以由基于同样存储技术的多个存储组件组成，
但是其可以由于使用中的专门化而被分离地维护（例如，一些DRAM设备被用作主存储装置，而其它DRAM设备被用作图形控制器的不同的帧缓冲器）。

[0034] 在各种实施例中，接口190和390中的每一个可以采用使得计算设备100和300中对应的多个能够如已经描述的那样通过网络999而被耦合的多种信令技术中的任一个。这些
接口中的每一个包括提供至少一些必需功能性以使能这样的耦合的电路。然而，该接口还
可以用由处理器元件150、250和350​​中对应的处理器元件执行的指令序列来至少部分地实现（例如以实现协议栈或其它特征）。在网络999的一个或多个部分采用电学和/或光学传导的线缆敷设的情况下，接口190可以采用符合各种行业标准中任一个的信令和/或协议，
所述行业标准包括而不限于：RS-232C、RS-422、USB、以太网（IEEE-802.3）或IEEE-1394。可替代地或另外，在网络999的一个或多个部分需要使用无线信号传输的情况下，接口190可
以采用符合各种行业标准中任一个的信令和/或协议，所述行业标准包括而不限于：IEEE 
802.11a、802.11b、802.11g、802.16、802.20（通常被称为“移动宽带无线接入”）；蓝牙；
ZigBee；或者蜂窝无线电话服务，诸如GSM与通用分组无线电服务（GSM/GPRS）、CDMA/1xRTT、用于全球演进的增强型数据速率（EDGE）、仅演进数据/优化的（EV-DO）、用于数据和语音的演进（EV-DV）、高速下行链路分组接入（HSDPA）、高速上行链路分组接入（HSUPA）、4G LTE等。
应当注意的是：虽然接口190和390中的每一个被描绘为单个块，但这些中的一个或多个可
以包括可以基于不同信令技术的多个接口。这可能是实情，尤其是在这些接口中的一个或
多个将计算设备100和300中对应的计算设备耦合到各自采用不同的通信技术的多于一个
网络的情况下。

[0035] 如先前讨论的，存在近年来已经设计出的多种类型的位并行串匹配算法，包括Shift-Or（移位-或）、Shift-And（移位-与）和BNDM（后向非确定性DAWG匹配，其中DAWG是对于有向非循环字图的首字母缩写词，并且其中“非确定性”指代非确定性有限自动机或
“NFA”的BNDM使用）。已经发现不同串匹配算法对于具有不同的长度和特性的序列和型式的不同组合是相对高效的，并且已经发现BNDM在这些的相对宽的范围上是高效的。

[0036] 图3和图4a至4c一起在概念级上描绘BNDM的一些有限的方面。应当注意的是：尽管提供具体位并行串匹配算法的细节的此描绘仅仅是为了帮助说明可以如何应用本文讨论
的位移位（bit-shifting）技术，以使得能够实现诸如B​​NDM之类的位并行串匹配算法的性能方面的改进。因而，BNDM的方面的该描绘不应被理解为将本文讨论的位移位技术的使用
仅仅限制到BNDM或任何其它特定的位并行串匹配算法。

[0037] 转向图3，在BNDM中，组成序列531的元素通过在元素方面与型式532为相同大小的“窗口”511而被读取，并且然后与型式532中的所有元素相比较以定位匹配的元素。通常，在往往被认为或至少被描述为沿着序列531“向前”的方向上沿着序列531移动窗口511。然而，在窗口511内，完成从序列531读取元素以用在对用于匹配元素的型式532的搜索中，所述读取始于窗口511内那些元素中的最后一个并且在窗口511内在往往被认为或至少被描述为
“向后”的方向上朝着那些元素中最前面的一个行进。

[0038] 应当注意的是：在英语语言以及其中一般从左向右读取单词和句子的各种其它语言中，从左向右移动一般被认为是在“向前”方向上移动，而从右向左移动一般被认为是在“向后”方向上移动。因为存在其中不是这种情况的其它语言（包括其中竖直和/或从右向左读取单词和句子的语言），所以应当注意的是：在本文中将向前和向右移动描绘和讨论为相同的一个以及将向后移动和向左移动描绘和讨论为相同的一个不应被理解为将本文所讨
论和描绘的内容限制到任何特定的方向。因而，本文中的特定方向的这样的讨论和描绘不
应被理解为如此限制可以应用本文讨论的技术的方式。

[0039] 图4a-c呈现沿着序列531移动窗口511以及以特定次序读取窗口511内的元素的三个可能场景。应当注意的是：在呈现这三个场景中，本文中没有做出任何尝试来阐述BNDM算法的或任何其它位并行串匹配算法的描述。描述位并行串匹配算法或任何其它形式的串匹
配算法完全超出本公开的范围。

[0040] 在图4a-c中，做出假定：其中沿着序列531的长度移动窗口511的“向前”方向是从左向右，以及其中读取窗口511内的序列531的元素以用于与型式532的元素进行比较的“向后”方向是从右向左。在图4a-c的每一个中的窗口511内以从字母“a”向前至字母“g”的字母表次序呈现英文字母表的字母，作为帮助阐明窗口511内的序列531的元素被读取的次序——始于窗口511的最后端（最右位置）处的“a”并且每次一个元素（即遵循英语语言的字母表次序）朝着窗口511的最前端（最左位置）处的“g”继续进行。不管以字母表次序的字母“a”到“g”作为对于在窗口511内读取的次序的指导的此描绘，应当再次注意的是：组成序列
531和型式532的元素可以是任何类型的数据，包括但不限于：DNA序列、文本、数值数据等。

[0041] 图4a呈现一场景，其中由于窗口511内序列531的元素和型式532的元素之间的不完全匹配，窗口511沿着序列531按等于窗口511如在元素方面计数的长度的元素的数目而
向前（向右）移动。更明确地，始于窗口511的最后端（最右位置）中的元素“a”，在型式532中发现对元素“a”的匹配。然后，在窗口511内沿着序列531向后移动（从右向左），元素“b”也被发现在型式532中具有匹配，然而，沿着序列531再次向后移动到元素“c”揭示了在型式532内的任何地方都没有对于元素“c”的匹配（如通过在型式532的元素位置中的五个之上的划掉所指示的）。在型式532内发现“a”和“b”但没有“c”的情况下，从窗口511内进一步读取元素以用于与型式532内的元素比较被视为是不必要的，因为现在清楚：在窗口511和型式532内的元素之间不可能存在完全匹配（因而，型式532内的其它元素可能是什么无关紧要）。

[0042] 图4b呈现一场景，其中窗口511沿着序列531按小于窗口511如在元素方面计数的长度的元素的数目而向前（向右）移动。如同图4a中描绘的场景，发现元素“a”和“b”的不完全匹配，其中在型式532内再次没有发现对于元素“c”的匹配（再次由在型式532的元素位置中的五个之上的划掉所指示），使得进一步读取窗口511的元素被视为是不必要的。然而，不像图4a的场景，图4b的不完全匹配包括在型式532的最前端（最左两个位置）处的匹配元素“a”和“b”，并且其中这些元素“a”和“b”以对于其在窗口511内的配对物的匹配次序。结果，不像图4a的场景，在图4b的场景中呈现如果窗口511沿着序列531按五个元素而不是按窗口
511如在元素方面测量的全长度向前移动则发现完全匹配的可能性。

[0043] 图4c呈现一场景，其中由于在窗口511内的序列531的元素和型式532的元素之间发现了完全匹配，窗口511沿着序列531按等于窗口511如在元素方面计数的长度的元素数
目向前（向右）移动。再次在窗口511的最后端（最右位置）处开始，并且在窗口511内沿着序列531向后（向左）移动，元素“a”，然后“b”，然后“c”，然后“d”，然后“e”，然后“f”，然后“g”被读取并且被发现全部存在于型式532内并以该相同的次序（也是向后行进）。发现这一个完全匹配的事实被记录（以及其沿着序列531的长度的位置）为结果数据539的部分。然后，窗口511沿着序列531按等于窗口511在元素方面的大小的元素数目向前（向右）移动，作为搜索这样的匹配的另一实例的部分。

[0044] 图5a和5b一起例示在BNDM的按位操作的示例实现方式中位移位的使用，其中型式532是文本串“humid”，并且序列531是在其中搜索“humid”的所有实例的文本串
“dehumidifier”。为简洁起见，描绘针对“humid”的实例的本搜索的执行的仅仅一部分，以便更清楚地示出位移位的使用。

[0045] 始于图5a，在BNDM和其它位并行串匹配算法中，实例化具有等于型式532中元素数量的位长度的测试位掩码“D”。测试位掩码D被反复初始化为全1，并且用在测试中用于在沿着序列531的长度的各种位置处的匹配，其中测试位掩码D被反复与相同长度的其它位掩码
按位进行“与”或者“或”运算（这取决于算法）。此外，在用于匹配的这些测试的许多测试之间，对测试位掩码D进行位移位。如将更详细解释的，正是测试位掩码D的位移位潜在地遭遇困难，其中在采用SIMD架构的处理器的矢量寄存器内实例化测试位掩码D。

[0046] 在BNDM中，也实例化各自具有等于型式532中的元素数量的位长度的附加位掩码B的集合。为存在于型式532内的元素的字母表的每个元素实例化这些位掩码B的每一个的至
少一个。因此，考虑到文本串“humid”由五个元素组成，其中没有任何一个重复，在位掩码B的集合中存在至少五个位掩码。这些位掩码B通过其相应的元素索引，使得对于文本串
“humid”，位掩码B的集合包括位掩码B（d）、B（h）、B（i）、B（m）和B（u）。在这些位掩码B的每一个内，以对它们相应的元素出现在型式532中何处进行指示的方式将位设置为0或1。

[0047] 如先前讨论的，在序列531内搜索型式532的实例以定位于序列531的开始处的窗口511开始。因而，如所描绘的，窗口511定位于序列531的最前（最左）端处的“dehum”上。也如先前讨论的，读取序列531的元素，一次一个，以尝试在型式532内发现匹配元素，这开始于窗口511的​​最后端（最右位置）处，并且朝着窗口511的​​最前端（最左位置）向后行进。
因而如所描绘的，读取的第一个元素是在窗口511最后端处的“m”。

[0048] 为了对型式532内“m”的至少一个实例进行测试，测试位掩码D被初始化为全1，并且倒数索引j被初始化为5。检索位掩码B（m），并且其位与测试位掩码D进行“与”运算，使得D=D＆B（m）。而且，索引j递减1，以反映此测试的发生。该“与”（AND）运算（按位逻辑与（conjunction）运算）的结果使得测试位掩码D具有非零位值（具体地，00100），其指示元素“m”的至少一个实例存在于型式532中。作为响应，针对窗口511（在其当前位置处）内的那些和型式532之间的更多元素匹配的搜索继续，并且从窗口511内读取下一个元素“u”。

[0049] 为了在型式532中“m”的至少一个实例的成功定位之后针对型式532内的“u”的至少一个实例进行测试，测试位掩码D被向左位移位一个位的位置。然后，检索位掩码B(u)，并且其位与测试位掩码D进行“与”运算，使得D=D＆B（u）。而且，索引j再次递减1，以反映此测试的发生。此“与”运算（按位逻辑与运算）的结果再次使得测试位掩码D具有非零位值（具体地，01000），其指示元素“u”的至少一个实例存在于型式532中。作为响应，针对窗口511（在其当前位置处）内的那些和型式532之间的更多元素匹配的搜索继续，并且从窗口511内读取下一个元素“h”。

[0050] 为了在型式532中的“m”和“u”的实例的成功定位之后针对型式532内的“h”的至少一个实例进行测试，测试位掩码D被再次向左位移位一个位的位置。然后，检索位掩码B（h），并且其位与测试位掩码D进行“与”运算，使得D=D＆B（h）。而且，索引j又再次递减1，以反映此测试的发生。此“与”运算（按位逻辑与运算）的结果又再次使得测试位掩码D具有非零位值（具体地，10000），其指示元素“h”的至少一个实例存在于型式532中。而且，测试位掩码D的最高有效位（MSB）现在被设置为1的事实指示利用在其当前位置中的窗口511的测试结束。如果已经测试了窗口511内的所有元素，使得j往下递减到0，那么测试位掩码D的MSB被设置为1将指示已经发现匹配。然而，在该实例中，j已经仅仅被往下递减到2，并且因此不存在匹配。

[0051] 转向图5b，响应于该匹配缺乏，窗口511沿着序列532向前（向右）移动，但不是针对等于窗口511如在元素方面计数的大小的元素数量。对于索引j的值2反映前述测试的结果，其指示在窗口511内从序列531读取的5个元素中的3个在型式532中确实具有匹配，并且因此，存在以下可能性：如果窗口511仅仅按j的非零值指示的元素数量而移动，则可能发现全型式532的匹配。因而，以类似于在图4b中所描绘的方式来按仅仅两个元素移动窗口511。

[0052] 在已经移动窗口511的情况下，测试位掩码D被再次初始化为全1，索引j被再次初始化为5，并且再次从窗口511内检索序列531的元素，这开始于窗口511最后（最右）端。如图
5b中所图示，文本串“humid”这次在窗口511内，并且因而将发现与型式532的文本串
“humid”的匹配。在标识该匹配中，测试位掩码D经受与位掩码B(d)、B(i)、B(m)、B(u)和B(h)（以该次序）的五个“与”运算，导致在每个“与”之后的测试位掩码D的非零值。而且，在这五个“与”运算之间，测试位掩码D被位移位四次。在这五个“与”运算的情况下，索引j从5一路往下递减到0，这指示窗口511内的所有元素已被读取并用在这样的测试中。因而，当测试位掩码D的MSB在五个“与”运算结束时被设置为1时，具有0值的索引j指示已经发现匹配。

[0053] 响应于发现该匹配，再次移动窗口511，并且以类似于图4c中所描绘的方式执行针对更多匹配的搜索。为了简明，不说明这样的进一步的执行。然而，在图5a-b中所图示的内容之中是对以下效应的示范：测试位掩码D的位移位在这样的位并行串匹配算法中频繁发
生，测试位掩码D至全1的初始化也是这样。因此，测试位掩码D的这样的位移位是这样的算法的执行的重要部分。

[0054] 图6a至6e一起图示在BNDM中位移位的使用的另一示例的方面，其中型式532是文本串“because of you”，并且测试位掩码D在被划分成分道552a至552d的矢量寄存器551内被实例化。应当注意的是：仅仅为了使得这些图能够在页面上完全合适的缘故，图6a-d描绘被故意图示为宽度上仅仅32位并且被划分成宽度上仅仅8位的四个分道的矢量寄存器的示
例集合。在实际实践中，预想的是：本文讨论的技术将应用到宽度上128、256、512或更多位的矢量寄存器，其具有各自在宽度上是16、32或64或可能更多位的分道。因此，本文中所描绘的矢量寄存器和分道的有限宽度不应被理解为将本文所述的技术的应用限制到这样的
小的位宽。

[0055] 应当注意的是：重复的使用由位掩码之间的“与”和“或”运算构成，包括各种寄存器中的位掩码。为了清楚，这些“与”和“或”运算是按位逻辑运算，其中在充当输入的两个位掩码操作数中对应的位的位置中的位被逻辑“与”或者“或”在一起，其中结果要么保持在提供用作操作数输入的两个位掩码的两个寄存器之一内要么被存放在第三寄存器内。因而，每个这样的“与”运算是按位逻辑与运算，其中两个操作数输入位掩码可以被描述为被“与”在一起或“在按位逻辑与运算中组合”。而且，每个这样的“或”运算是按位逻辑或
（disjunction）运算，其中两个操作数输入位掩码可以被描述为被“或”在一起或“在按位逻辑或运算中组合”。

[0056] 转向图6a，图示在使用SIMD特征的矢量寄存器551内初始化测试位掩码D的高效方法的示例。矢量掩码553被设置成指示将用全1填充矢量寄存器551的哪些分道552a至552d。
这样的矢量掩码是SIMD架构中的常见特征，作为控制矢量寄存器中的哪些分道将被包括在
特定的按位、算术或其它运算中的方式。在该情形下，型式532（“because of you”）内的元素的数量为14，并且从此中计算出仅仅需要两个分道552a和552b来持有测试位掩码D的对
应的14位的长度。因而，矢量位掩码553被设置为0011，以使得用全1填充分道被限制到分道
552a-b。矢量寄存器551的这两个分道然后用全1填充。还计算出测试位掩码D的14位的长度占据分道552b的除了两个最高有效位之外的全部（即分道552b的所有位位置，除了位位置7和6）。作为响应，矢量​​掩码553被设置成将矢量寄存器551上的向右位移位操作的使用限制到分道552b。然后矢量寄存器551的分道552b被向右进行位移位两次，导致0填充矢量寄
存器551的分道552b中的位位置7和6。

[0057] 虽然未具体示出，但矢量寄存器551的该初始化的状态（其中14位长度的测试位掩码D被初始化为全1，并且矢量寄存器551的所有其它位被初始化为0）可以被拷贝到另一个
矢量寄存器。作为对重复刚才在图6a中描述和描绘的初始化技术的节省时间和节省功率的
替代方案，每当测试位掩码D要被重新初始化为该相同状态时，测试位掩码D的该相同的初
始化的状态然后可以从该其它矢量寄存器拷贝回到矢量寄存器551中。

[0058] 图6b描绘经创建以指示型式532内的元素“e”的位置的位掩码B的集合的位掩码B(e)的示例。如所描绘的，在矢量寄存器的另一个554内实例化位掩码B(e)。取决于型式532内不同元素的数量与给定处理器内矢量寄存器的数量，在各种实施例中可以可能的是在矢
量寄存器内实例化每个位掩码B。

[0059] 图6c-e描绘在矢量寄存器551内按一位向左来位移位测试位掩码D的方法。图6c示出矢量寄存器551内的测试位掩码D在已经与矢量寄存器554内的位掩码B(e)进行“与”运算之后的状态。具体地，测试位掩码D被示为具有与位掩码B(e)在矢量寄存器554内被初始化
（图6b）成的位值相同的位值。

[0060] 如先前已经讨论的，在一些SIMD架构中，位移位操作导致在矢量寄存器的一个分道内的MSB和/或LSB位置处的位值仅仅被丢弃而不是被进位到该矢量寄存器的相邻分道。
假定矢量寄存器551是遭受该限制的SIMD的实现方式，则矢量寄存器551向左的位移位将导
致没有被进位到分道552b的LSB位位置（位位置0）的分道552a的MSB位置（位位置7）处的1。

[0061] 为了解决这个，矢量寄存​​器551与充当MSB掩码的另一个矢量寄存器555进行“与”运算，在所述MSB掩码中只有其分道552a-d的每一个中的MSB位被设置为1，并且该“与”运算（按位逻辑与运算）的结果被存储在充当进位掩码的仍另一个矢量寄存器556中。该
“与”运算（按位逻辑与运算）的结果是分道552a中的非零值以及矢量寄存器556的其它分道
552b-d中的零值。从矢量寄存器556的分道552a-d中的零和非零值（其指示在其四位内的那些分道中的每一个的零或非零状态）的该组合中创建4位矢量进位掩码557。矢量进位掩码
557的该4位矢量值然后被转换成标量值，以使能在其四个位之间向左位移位，并且然后转
换回4位矢量值。

[0062] 转向图6d，矢量进位掩码557作为对于矢量寄存器556的分道552a-d中的哪一个用1填充的按分道的控制。矢量寄存器556然后与充当LSB掩码的仍另一个矢量寄存器558进行
“与”运算，在所述LSB掩码中仅仅在其分道552a-d的每一个中的LSB位被设置为1，并且该“与”运算（按位逻辑与运算）的结果被存储回矢量寄存器556中。结果，矢量寄存​​器556现在充当进位掩码，从矢量寄存器551的分道552a的MSB位位置进位位值1。

[0063] 转向图6e，在该位被进位的情况下，持有测试位掩码D的矢量寄存器551向左移位一个位的位置。正如预期的，当分道552b的位位置4中的位值1被成功地移位到相同分道内
的位位置5时，分道552a的位位置7（MSB位位置）中的位值1不被进位到分道552b的位位置0（LSB位位置）使得其被丢失。然而，矢量寄存​​器551然后与充当用于该否则丢失的位值的进位掩码的矢量寄存器556进行“或”运算，并且该“或”运算（按位逻辑或运算）的结果被存储回矢量寄存器551中，从而用该否则丢失的位值填充矢量寄存器551的分道552b的位位置
0（LSB位位置）。

[0064] 应当注意的是：虽然图6c-e及其随附描述具体阐述技术的方面，所述技术用于克服在矢量寄存器的向左位移位操作中从MSB位位置向左到相邻分道中LSB位位置的位值进
位的缺乏，相同的技术可以用于克服在矢量寄存器的向右位移位操作中从LSB位位置向右
到相邻分道中MSB位的位值进位的缺乏。可能在实现移位-或（shift-OR）位并行串匹配算法中遇到具有这样的在分道之间缺乏位进位的矢量寄存器的这样的向右位移位。在这样的替
代的、向右位移位的情形下，在图6c-e中所描绘的内容中的许多将不变，除了矢量进位掩码
557内的矢量值将向右位移位，而在图6c中被转换为标量值，并且在图6e中矢量寄存器551
将向右位移位。

[0065] 图7更详细地图示图1或2的变型中任一个的框图的一部分的框图。更具体地，描绘其中在图1或图2中计算设备100的变型的任一个中执行位并行串匹配的操作环境的方面，
其中通过控制例程140或240的执行来使得处理器元件150或250中对应的处理器元件执行
前述功能。如将由本领域技术人员认识到的：这些控制例程中的每一个（包括组成其每一个的组件）被选为在被选为实现这些处理器元件中对应的处理器元件的无论什么类型的一个
或多个处理器上操作。

[0066] 在各种实施例中，控制例程140和240中的每一个可以包括操作系统、设备驱动程序和/或应用级例程的组合（例如在盘介质上提供的所谓的“软件套件”，从远程服务器获得的“小应用程序”等）。在包括操作系统的情况下，操作系统可以是各种可得到的操作系统中的任一个，包括而不限于：Windows™，OS X™，Linux®或Android OS™。在包括一个或多个设备驱动程序的情况下，那些设备驱动程序可以提供对计算设备100和控制器200中对应多
个的各种其它组件中任一个的支持，无论是硬件还是软件组件。

[0067] 取决于使得处理器元件150或250中的哪个来执行如本文所述的位并行串匹配，控制例程140和240中的一个或另一个包括初始化组件542，所述初始化组件542由处理器元件
150或250中对应的一个可执行以实例化和初始化测试位掩码D和位掩码B的集合中的每一
个位掩码。如已经描述的，用等于型式532内元素数量的位长度来实例化测试位掩码D和所
有位掩码B。初始化组件用指示型式532内的其相关联的元素的(一个或多个)位置的位值来
填充位掩码B中的每一个。通过用1填充测试位掩码D的位，初始化组件542还循环地准备测
试位掩码D，用于在窗口511和型式532内的元素之间的匹配测试中使用。在这样做中，初始化组件542可以采用SIMD特征来选择性填充在其内用1实例化测试位掩码D的矢量寄存器的
分道，继之以如已经描述的那样选择性地位移位那些分道中的最高有效的，以实现测试位
掩码D的所意图长度的1的序列。初始化组件542可以以此方式初始化该矢量寄存器，仅仅一次，并且然后将其初始化的状态拷贝到另一个矢量寄存器，以用于通过简单地从该其它矢
量寄存器中拷贝回该初始化的状态而在以后使用于重新初始化中。

[0068] 控制例程140和240中的一个或另一个还包括移位组件543，所述移位组件543由处理器元件150或250中对应的一个可执行以实现在这些处理器元件中对应一个的第一矢量
寄存器551内测试位掩码D的移位。如已经描述的，在MSB位位置处的位值被存储在充当进位掩码的第二矢量寄存器556中（通过与MSB掩码的“与”运算），并且形成矢量进位掩码557，其指示第二矢量寄存器的分道中的零和非零值。矢量进位掩码557的矢量值然后被转换成标
量值，被位移位，并且然后被转换回矢量值。矢量进位掩码557然后用于选择用1填充第二矢量寄存器556中的哪些分道，并且然后与LSB​掩码进行“与”运算，使得第二矢量寄存器556被使得仅仅在用1填充了的分道中的LSB位位置处具有1。位移位第一矢量寄存器551，其中
位的预期丢失发生在没有SIMD限制的话位进位就将会以其它方式发生的任何地方，并且第
一和第二矢量寄存器551和556进行“或”运算，使得否则缺失的进位位在其位移位之后被添加到第一矢量寄存器551，并且测试位掩码D是完整的，如它应当是的那样。

[0069] 控制例程140和240中的一个或另一个还包括测试组件547，所述测试组件547由处理器元件150或250中对应的一个可执行，以引导测试位掩码D的初始化和位移位的发生。测试组件547还沿着序列531执行窗口511的移位以及在结果数据539中发现的任何匹配的指
示的存储。

[0070] 图8图示逻辑流2100的一个实施例。逻辑流2100可以表示由本文所述的一个或多个实施例执行的一些或所有操作。更具体地，逻辑流2100可以说明在至少执行控制例程140或240中对应的一个中由搜索设备100的处理器元件150或250之一执行的操作。

[0071] 在2110处，计算设备（例如搜索设备100）在计算设备的处理器元件的矢量寄存器内实例化测试位掩码D，这通过首先计算存储测试位掩码D所需的该矢量寄存器的分道数
量。正如已经解释的，在执行按位操作以针对型式（例如型式532）的元素和移位窗口（例如窗口511）内序列（例如序列531）的部分之间的匹配进行测试中，各种不同的位并行串匹配算法利用测试位掩码（照惯例被指明为“D”）。

[0072] 在2120处，计算设备使用矢量掩码来选择性地仅仅填充其中存储有测试位掩码D的任何位的矢量寄存器的分道中的多个。如已经讨论的，这些分道的该填充典型地是用全
1。然而，应当注意的是：其它实施例是可能的，其中这些分道的填充需要用全0来清除它们。

[0073] 在2130处，计算设备位移位分道中的最高有效的一个，其中测试位掩码D的任何位被存储到右边以调整已被填充以匹配组成测试位掩码D的位位置的数量的位位置的总体数
量。如已经讨论的，可以通过再次使用矢量位掩码来实现特定分道的这样的选择性移位。

[0074] 图9图示逻辑流2200的一个实施例。逻辑流2200可以表示由本文所述的一个或多个实施例执行的一些或所有操作。更具体地，逻辑流2200可以说明在至少执行控制例程140或240中对应的一个中由搜索设备100的处理器元件150或250之一执行的操作。

[0075] 在2210处，计算设备（例如搜索设备100）在另一个矢量寄存器内存储在存储了测试位掩码D的矢量寄存器的每一个分道的MSB位位置处的位值的拷贝，两个寄存器都是实现
SIMD架构的处理器元件的部分。如已经描述的，这是通过“与”运算（按位逻辑与运算）来完成的，其中在仍另一个矢量寄存器中的MSB掩码用于有效地仅仅滤过存储了测试位掩码D的
矢量寄存器的分道的MSB位。

[0076] 在2220处，计算设备创建指示该其它矢量寄存器中的哪些分道持有零和非零值的矢量掩码，使得在矢量掩码中反映那些拷贝的MSB位的值。在2230处，矢量掩码的矢量值被转换成标量值，在2240处向左位移位一位，并且在2250处被转换回矢量掩码中的矢量值。

[0077] 在2260处，现在具有其移位的位值的矢量掩码用于用1选择性地填充所述另一矢量寄存器的分道（通过矢量掩码的位值中的对应位值而选择的分道）。在2270处，所述另一矢量寄存器与又一矢量寄存器进行“与”运算，以有效地仅仅滤过所述另一矢量寄存器的分道的LSB位，使得1仅仅存在于已经被用1选择性地填充的所述另一矢量寄存器的分道内的
LSB位位置处。

[0078] 在2280处，执行存储了测试位掩码D的矢量寄存器的向左位移位，以向左位移位测试位掩码D一个位位置。正如预期的，在每个分道内的MSB位位置处的位值丢失（特别是位值
1）。在2290处，通过将存储了测试位掩码D的矢量寄存器与所述另一矢量寄存器进行“或”运算，还原那些丢失的位值。

[0079] 图10图示适合于实现如先前所述的各种实施例的示例性处理架构3000的实施例。更具体地，处理架构3000（或其变型）可以被实现为计算设备100和300以及控制器200中的一个或多个的部分。应当注意的是：给予处理架构3000的组件参考标号，其中最后两位数对应于较早前被描绘和描述为这些计算设备的部分的组件的参考标号的最后两位数。这被完
成作为对于将这些计算设备的这样的组件与该示例性处理构架的组件相互关联的帮助。

[0080] 处理架构3000包括通常在数字处理中采用的各种元件，包括而不限于：一个或多个处理器、多核处理​​器、协处理器、存储器单元、芯片组、控制器、外围设备、接口、振荡器、定时设备、视频卡、音频卡、多媒体输入/输出（I/O）组件、电源等。如在本申请中所使用的，术语“系统”和“组件”旨在指代在其中实施数字处理的计算设备的实体，该实体是硬件、硬件和软件的组合、软件或执行中的软件，其示例由这个描绘的示例性处理架构提供。例如，组件可以是但不限于是：在处理器元件上运行的过程、处理器元件本身、可以采用光学和/或磁性存储介质的存储设备（例如硬盘驱动器、阵列中的多个存储驱动器等）、软件对象、可执行的指令序列、执行的线程、程序和/或整个计算设备（例如整个计算机）。通过说明的方式，在服务器上运行的应用和服务器二者可以是组件。一个或多个组件可以驻留在过程和/或执行的线程内，并且组件可以定位在一个计算设备上和/或分布在两个或更多个计算设
备之间。此外，组件可以通过各种类型的通信介质通信地耦合到彼此，以协调操作。协调可以涉及信息的单向或双向交换。例如，组件可以以通过通信介质被传送的信号的形式来传
送信息。信息可以实现为被分配给一个或多个信号线的信号。每个消息可以是串行或者基
本上并行地传输的一个信号或多个信号。

[0081] 如所描绘的，在实现处理架构3000中，计算设备至少合并处理器元件950、存储装置960、对其它设备的接口990以及耦合装置955。取决于实现处理架构3000的计算设备的各种方面，包括其所意图的使用和/或使用条件，这样的计算设备还可以合并附加组件。

[0082] 耦合装置955合并一个或多个总线、点对点互连、收发器、缓冲器、交叉点式交换机和/或至少将处理器元件950通信耦合到存储装置960的其它导体和/或逻辑。耦合装置955还可以将处理器元件950耦合到接口990和显示接口985中的一个或多个（取决于也存在这
些和/或其它组件中的哪些）。在处理器元件950通过耦合装置955如此耦合的情况下，处理器元件950能够执行以上针对计算设备100和/或控制器200详细描述的任务中的各种任务。
耦合装置955可以用信号通过其而被光学和/或电气传送的各种技术或技术组合中的任一
个来实现。此外，耦合装置955的至少部分可以采用符合多种行业标准中任一个的定时和/
或协议，所述行业标准包括而不限于：加速图形端口（AGP）、CardBus（卡总线）、扩展的行业标准架构（E-ISA）、微通道架构（MCA）、NuBus、外围组件互连（扩展的）（PCI-X）、PCI 快速（PCI-E）、个人计算机存储卡国际协会（PCMCIA）总线、HyperTransport™QuickPath（快速路径）等等。

[0083] 如先前讨论的，处理器元件950（对应于处理器元件150、250和350中的一个或多个）可以包括多种商业上可得到的处理器中的任一个，采用多种技术中的任一个，并用以许多方式中的任一个而物理组合的一个或​​多个核来实现。

[0084] 如先前讨论的，存储装置960（对应于存储装置160、260和360中的一个或多个）可以包括基于多种技术或技术组合中任一个的一个或多个不同的存储设备。更具体地，如所描绘的，存储装置960可以包括易失性存储装置961（例如基于一个或多个形式的RAM技术的固态存储装置）、非易失性存储装置962（例如固态、铁磁性或不需要恒定供应电力来保持其内容的其它存储装置）​​和可移除介质存储装置963（例如可以通过其将信息在计算设备之间传送的可移除盘或固态存储器卡存储装置）中的一个或多​​个。如可能包括多个不同类型的存储装置的存储装置960的该描绘承认在计算设备中多于一种类型的存储设备的常见
使用，其中一种类型提供使得能够由处理器元件950更快操纵数据的相对快的读和写能力
（但是可能使用恒定需要电力的“易失性”技术），而另一种类型提供非易失性存储的相对高密度（但是很可能提供相对慢的读和写能力）。

[0085] 考虑到采用不同技术的不同存储设备的往往不同的特性，对于这样的不同存储设备通过不同的存储控制器而耦合到计算设备的其它部分也是常见的，所述存储控制器通过
不同的接口耦合到其不同的存储设备。通过示例的方式，在易失性存储装置961存在并且基于RAM技术的情况下，易失性存储装置961可以通过存储控制器965a通信地耦合到耦合装置
955，存储控制器965a向易失性存储装置961提供适当的接口，所述易失性存储装置961或许采用行和列寻址，并且其中存储控制器965a可以执行行刷新和/或其它维护任务以帮助保
持在易失性存储装置961内存储的信息。通过另一个示例的方式，在非易失性存储装置962
存在并且包括一个或多个铁磁和/或固态盘驱动器的情况下，非易失性存储装置962可以通
过存储控制器965b通信地耦合到耦合装置955，存储控制器965b向非易失性存储装置962提
供适当的接口，所述非易失性存储装置962或许采用信息块和/或圆柱体和扇区的寻址。通
过仍另一个示例的方式，在可移除介质存储装置963存在并且包括一个或多​​个光学和/或固态盘驱动器（其采用可移除机器可读存储介质969的一个或多个片段）的情况下，可移除介质存储装置963可以通过存储控制器965c通信地耦合到耦合装置955，存储控制器965c向
可移除介质存储装置963提供适当的接口，所述可移除介质存储装置963或许采用信息块的
寻址，并且其中存储控制器965c可以以特定于延长机器可读存储介质969的寿命的方式来
协调读、擦除和写操作。

[0086] 易失性存储装置961或非易失性存储装置962中的一个或另一个可以包括以机器可读存储介质形式的制品，在所述机器可读存储介质上可以存储包括由处理器元件950可
执行的指令序列的例程，这取决于每一个所基于的技术。通过示例的方式，在非易失性存储装置962包括基于铁磁的盘驱动器（例如所谓的“硬驱动器”）的情况下，每个这样的盘驱动器典型地采用一个或多个旋转盘（platter），磁响应颗粒的涂层被沉积在所述旋转盘上并且以各种图案被磁性定向，以用类似于诸如软盘之类的可移除存储​​介质的方式存储诸如指令序列之类的信息。通过另一个示例的方式，非易失性存储装置962可以由固态存储设备的存储体组成，以用类似于紧凑型闪速卡的方式存储诸如指令序列之类的信息。再次，在不同的时间、在计算设备中采用不同类型的存储设备来存储可执行的例程和/或数据是常见
的。因而，包括将由处理器元件950执行的指令序列的例程最初可以被存储在计算机可读存储介质969上，并且可移除介质存储装置963随后可以用于将该例程拷贝到非易失性存储装
置962以用于不需要机器可读存储介质969的持续存在的较长期存储，和/或拷贝到易失性
存储装置961以使得能够在执行该例程时由处理器元件950更快地访问。

[0087] 如先前讨论的，接口990（对应于接口190和390）可以采用与可以用于将计算设备通信地耦合到一个或多个其它设备的各种通信技术中的任一个相对应的各种信令技术中
的任一个。再次，各种形式的有线或无线信令中的一个或二者可以用于使得处理器元件950能够与输入/输出设备（例如描绘的示例键盘920或打印机925）和/或其它计算设备交互，这可能通过网络（例如网络999）或网络的互连集。承认往往必须由任一个计算设备支持的多个类型的信令和/或协议的往往极大地不同的特性，接口990被描绘为包括多个不同的接口
控制器995a、995b和995c。接口控制器995a可以采用各种类型的有线数字串行接口或射频
无线接口中的任一个，以从诸如描绘的键盘920之类的用户输入设备接收串行传输的消息。
接口控制器995b可以采用各种基于线缆敷设的或无线的信令、定时和/或协议中的任一个，以通过描绘的网络999（或许是包括一个或多​​个链路的网络，更小的网络，或者或许是因特网）访问其它计算设备。接口995c可以采用各种导电线缆敷设中的任一个，从而使得能够使用串行或者并行的信号传输来向描绘的打印机925传送数据。可以通过接口990的一个或
多个接口控制器通信地耦合的设备的其它示例包括而不限于：麦克风、遥控装置、触笔、读卡器、指纹读取器、虚拟现实交互手套、图形输入平板、操纵杆、其它键盘、视网膜扫描仪、触摸屏的触摸输入组件、跟踪球、各种传感器、激光打印机、喷墨打印机、机械机器人、铣床等。

[0088] 在计算设备通信地耦合到（或者或许实际上合并）显示器（例如描绘的示例显示器980）的情况下，实现处理架构3000的这样的计算设备也可以合并显示接口985。虽然更一般化类型的接口可以用于通信地耦合到显示器，但是在显示器上视觉地显示各种形式的内容
中往往需要的稍微专门化的附加处理以及所使用的基于线缆敷设的接口的稍微专门化的
性质往往使得供应不同显示接口是合期望的。在显示器980的通信耦合中可以由显示接口
985采用的有线和/或无线信令技术可以利用符合各种行业标准中任一个的信令和/或协
议，所述行业标准包括而不限于各种模拟视频接口、数字视频接口（DVI）、DisplayPort（显示端口）等中的任一个。

[0089] 更一般地，计算设备100和300以及控制器200的各种元件可以包括各种硬件元件、软件元件或二者的组合。硬件元件的示例可以包括器件、逻辑器件、组件、处理器、微处理器、电路、处理器元件、电路元件（例如晶体管、电阻器、电容器、电感器等等）、集成电路、专用集成电路（ASIC）、可编程逻辑器件（PLD）、数字信号处理器（DSP）、现场可编程门阵列（FPGA）、存储器单元、逻辑门、寄存器、半导体器件、芯片、微芯片、芯片组等等。软件元件的示例可以包括软件组件、程序、应用、计算机程序、应用程序、系统程序、软件开发程序、机器程序、操作系统软件、中间件、固件、软件模块、例程、子例程、函数、方法、过程、软件接口、应用程序接口（API）、指令集、计算代码、计算机代码、代码段、计算机代码段、字、值、符号或其任何组合。然而，确定是否使用硬件元件和/或软件元件来实现实施例可以根据任何数量的因素而变化，诸如期望的计算速率、功率水平、耐热性、处理周期预算、输入数据速率、输出数据速率、存储器资源、数据总线速度以及其它设计或性能约束，如对于给定实现方式所期望的。

[0090] 一些实施例可以使用表述“一个实施例”或“实施例”连同其派生词来描述。这些术语意为：结合实施例所述的特定的特征、结构或特性被包括在至少一个实施例中。在说明书中的各种地方短语“在一个实施例中”的出现不一定全部指代相同实施例。此外，一些实施例可以使用表述“耦合的”和“连接的”连同其派生词来描述。这些术语不一定旨在作为彼此的同义词。例如，一些实施例可以使用术语“连接的”和/或“耦合的”来描述，以指示两个或更多个元件彼此直接物理或电接触。然而，术语“耦合的”还可以意为：两个或更多个元件彼此不直接接触，但是还仍然彼此协作或交互。

[0091] 强调的是：提供本公开的摘要以允许读者快速弄清本技术公开的性质。在以下理解的情况下提交摘要：它将不用于解释或限制权利要求的范围或含义。另外，在前述具体实施方式中，可看出：为了使本公开整体化的目的，各种特征被一起群组在单个实施例中。此公开方法不要被解释为反映以下意图：要求保护的实施例需要比在每个权利要求中明确陈
述的更多的特征。相反，如以下权利要求所反映的，发明主题在于少于单个公开的实施例的所有特征。因而以下权利要求据此被合并到具体实施方式中，其中每个权利要求独立地作
为分离的实施例。在所附权利要求中，术语“包括”和“其中”分别被用作相应的术语“包括有”和“在其中”的简明话语等同物。此外，术语“第一”、“第二”、“第三”等等仅仅用作标签，并不意图在其对象上强加数字要求。

[0092] 以上已经描述的内容包括所公开的架构的示例。当然，不可能描述组件和/或方法的每一个可想到的组合，但本领域普通技术人员可以认识到：许多另外的组合和置换是可
能的。因此，新颖的架构旨在涵盖落入所附权利要求的精神和范围内的所有这样的变更、修改和变型。详细的公开现在转向提供关于另外的实施例的示例。下面提供的示例并不旨在
是限制性的。

[0093] 一种执行串匹配的装置的示例包括：处理器元件；以及逻辑，用以接收包括第一串元素的型式以用于串匹配操作中，在处理器元件的第一矢量寄存器中实例化测试位掩码，所述第一矢量寄存器包括多个分道，将第一矢量寄存器的多个分道的最高有效位（MSB）位置处的位值拷贝到第一矢量掩码作为矢量值，作为标量值而位移位矢量值，位移位第一矢
量寄存器，采用第一矢量掩码的矢量值以选择性地填充处理器元件的第二矢量寄存器的分
道的最低有效位（LSB）位置，并且在按位逻辑或运算中将第二矢量寄存器组合到第一矢量寄存器中。

[0094] 装置的以上示例，其中所述逻辑用以接收包括第二串元素的序列以用在串匹配操作中，所述串匹配操作标识序列内型式的出现。

[0095] 装置的以上示例中的任一个，其中第一和第二串包括文本或DNA序列中之一的串。

[0096] 装置的以上示例中的任一个，其中所述装置包括显示器，并且所述逻辑用以视觉地呈现是否在序列内发现型式的指示。

[0097] 装置的以上示例中的任一个，其中所述逻辑用以向计算设备传输对是否在序列内发现型式进行指示的结果数据，从所述计算设备经由网络而接收型式和序列中的至少一
个。

[0098] 装置的以上示例中的任一个，其中串匹配操作基于后向非确定性DAWG匹配（BNDM）算法。

[0099] 装置的以上示例中的任一个，其中处理器元件基于单指令多数据（SIMD）架构。

[0100] 装置的以上示例中的任一个，其中所述逻辑用以在按位逻辑与运算中组合第一矢量寄存器与充当MSB掩码的第三矢量寄存器以将第一矢量寄存器的多个分道的MSB位位置
处的位值拷贝到第一矢量掩码，采用矢量值以用1选择性地填充第二矢量寄存器的分道的
位，并且在按位逻辑与运算中组合第二矢量寄存器与充当LSB掩码的第四矢量寄存器以选
择性地填充第二矢量寄存器的分道的LSB位位置。

[0101] 装置的以上示例中的任一个，其中所述逻辑用以计算存储测试位掩码所需的第一矢量寄存器的分道的数量，所述测试位掩码具有等于第一串的元素数量的位长度，采用第
二矢量掩码以选择性填充对于存储测试位掩码所需的第一矢量寄存器的所述数量的分道，
并且右移位所述数量的分道的最高有效分道以将跨所述数量的分道的全部而填充的位数
调整成等于测试位掩码的位长度。

[0102] 装置的以上示例中的任一个，其中所述逻辑用以用1选择性地填充第一矢量寄存器的所述数量的分道的所有位。

[0103] 装置的以上示例中的任一个，其中所述逻辑用以在处理器元件的第三矢量寄存器中初始化指示元素所出现于的第一串内的位置的位掩码，在按位逻辑与运算中组合第三矢
量寄存器与第一矢量寄存器，并且确定测试位掩码的MSB位处的位值，以确定是否在序列内发现型式。

[0104] 执行串匹配的另一装置的示例包括：处理器元件；以及逻辑，用以接收包括第一串元素的型式以用在串匹配操作中，计算存储测试位掩码所需的处理器元件的第一矢量寄存器的分道的数量，所述测试位掩码具有等于第一串的元素数量的位长度，采用第一矢量掩
码以选择性填充对于存储测试位掩码所需的第一矢量寄存器的所述数量的分道，并且右移
位所述数量的分道的最高有效分道以将跨所述数量的分道的全部而填充的位数调整成等
于测试位掩码的位长度。

[0105] 另一装置的以上示例，其中所述逻辑用以用1选择性地填充第一矢量寄存器的所述数量的分道的所有位。

[0106] 另一装置的以上示例中的任一个，其中所述逻辑用以接收包括第二串元素的序列以用在串匹配操作中，所述串匹配操作标识在序列内型式的出现，在处理器元件的第三矢
量寄存器中初始化指示元素所出现于的第一串内的位置的位掩码，在按位逻辑与运算中组
合第三矢量寄存器与第一矢量寄存器，并且确定测试位掩码的最高有效位（MSB）处的位值以确定是否在序列内发现型式。

[0107] 另一装置的以上示例中的任一个，其中第一及第二串包括文本或DNA序列中之一的串。

[0108] 另一装置的以上示例中的任一个，其中所述装置包括显示器，并且所述逻辑用以视觉地呈现是否在序列内发现型式的指示。

[0109] 另一装置的以上示例中的任一个，其中所述逻辑用以向计算设备传输对是否在序列内发现型式进行指示的结果数据，从所述计算设备经由网络而接收型式和序列中的至少
一个。

[0110] 另一装置的以上示例中的任一个，其中串匹配操作基于后向非确定性DAWG匹配（BNDM）算法。

[0111] 另一装置的以上示例中的任一个，其中处理器元件基于单指令多数据（SIMD）架构。

[0112] 另一装置的以上示例中的任一个，其中所述逻辑用以将第一矢量寄存器的多个分道的MSB位位置处的位值拷贝到第二矢量掩码作为矢量值，作为标量值而位移位矢量值，位移位第一矢量寄存器，采用第二矢量掩码的矢量值以选择性地填充处理器元件的第二矢量
寄存器的分道的LSB位位置，并且在按位逻辑或运算中将第二矢量寄存器组合到第一矢量
寄存器中。

[0113] 另一装置的以上示例中的任一个，其中所述逻辑用以在按位逻辑与运算中组合第一矢量寄存器与充当MSB掩码的第三矢量寄存器以将第一矢量寄存器的所述数量的分道的
MSB位位置处的位值拷贝到第二矢量掩码，采用矢量值以用1选择性地填充第二矢量寄存器
的分道的位，并且在按位逻辑与运算中组合第二矢量寄存器与充当LSB掩码的第四矢量寄
存器以选择性地填充第二矢量寄存器的分道的LSB位位置。

[0114] 执行串匹配的计算机实现的方法的示例包括：接收包括第一串元素的型式以及包括第二序列元素的序列以用在串匹配操作中，以确定型式是否存在于序列内，在处理器元
件的第一矢量寄存器中实例化测试位掩码，所述第一矢量寄存器包括多个分道，将第一矢
量寄存器的多个分道的最高有效位（MSB）位置处的位值拷贝到第一矢量掩码作为矢量值，作为标量值而位移位矢量值，位移位第一矢量寄存器，采用第一矢量掩码的矢量值以选择
性地填充处理器元件的第二矢量寄存器的分道的最低有效位（LSB）位位置，并且将第二矢量寄存器向第一矢量寄存器中进行“或”运算。

[0115] 计算机实现的方法的以上示例，其中第一和第二串包括文本或DNA序列中之一的串。

[0116] 计算机实现的方法的以上示例中的任一个，其中所述方法包括从控制装置或网络中的至少一个接收信号，所述信号传送型式和序列中的至少一个。

[0117] 计算机实现的方法的以上示例中的任一个，其中所述方法包括在显示器上视觉呈现是否在序列内发现型式的指示。

[0118] 计算机实现的方法的以上示例中的任一个，其中所述方法包括向计算设备传输对是否在序列内发现型式进行指示的结果数据，从所述计算设备经由网络而接收型式和序列
中的至少一个。

[0119] 计算机实现的方法的以上示例中的任一个，其中所述方法包括在串匹配操作中采用后向非确定性DAWG匹配（BNDM）算法。

[0120] 计算机实现的方法的以上示例中的任一个，其中所述方法包括在处理器元件的第三矢量寄存器中初始化指示元素所出现于的第一串内的位置的位掩码，将第三矢量寄存器
与第一矢量寄存器进行“与”运算，并且确定测试位掩码的MSB位处的位值以确定是否在序列内发现型式。

[0121] 执行串匹配的装置的示例包括用于执行计算机实现的方法的以上示例中任一个的构件。

[0122] 至少一个机器可读存储介质的示例包括指令，所述指令在由计算设备执行时使得计算设备：接收包括第一串元素的型式以及包括第二序列元素的序列以用在串匹配操作
中，以确定型式是否存在于序列内，在计算设备的处理器元件的第一矢量寄存器中实例化
测试位掩码，所述第一矢量寄存器包括多个分道，将第一矢量寄存器的多个分道的最高有
效位（MSB）位位置处的位值拷贝到第一矢量掩码作为矢量值，作为标量值而位移位矢量值，位移位第一矢量寄存器，采用第一矢量掩码的矢量值以选择性地填充处理器元件的第二矢
量寄存器的分道的最低有效位（LSB）位位置，并且在按位逻辑或运算中将第二矢量寄存器组合到第一矢量寄存器中。

[0123] 至少一个机器可读存储介质的以上示例，其中使得计算设备：从计算设备所耦合到的网络或计算控制装置中的至少一个接收信号，所述信号传送型式和序列中的至少一
个。

[0124] 至少一个机器可读存储介质的以上示例中的任一个，其中使得计算设备：在计算设备的显示器上视觉呈现是否在序列内发现型式的指示。

[0125] 至少一个机器可读存储介质的以上示例中的任一个，其中使得计算设备：经由计算设备所耦合到的网络而向计算设备传输结果数据，所述结果数据指示是否在序列内发现
型式。

[0126] 至少一个机器可读存储介质的以上示例中的任一个，其中串匹配操作基于后向非确定性DAWG匹配（BNDM）算法。

[0127] 至少一个机器可读存储介质的以上示例中的任一个，其中处理器元件基于单指令多数据（SIMD）架构。

[0128] 至少一个机器可读存储介质的以上示例中的任一个，其中使得计算设备：在处理器元件的第三矢量寄存器中初始化指示元素所出现于的第一串内的位置的位掩码，在按位
逻辑与运算中组合第三矢量寄存器与第一矢量寄存器，并且确定测试位掩码的MSB位处的
位值以确定是否在序列内发现型式。

[0129] 执行串匹配的仍另一装置的示例包括用于以下的构件：接收包括第一串元素的型式以及包括第二序列元素的序列以用在串匹配操作中，以确定型式是否存在于序列内，在
计算设备的处理器元件的第一矢量寄存器中实例化测试位掩码，所述第一矢量寄存器包括
多个分道，将第一矢量寄存器的多个分道的最高有效位（MSB）位位置处的位值拷贝到第一矢量掩码作为矢量值，作为标量值而位移位矢量值，位移位第一矢量寄存器，采用第一矢量掩码的矢量值以选择性地填充处理器元件的第二矢量寄存器的分道的最低有效位（LSB）位位置，并且在按位逻辑或运算中将第二矢量寄存器组合到第一矢量寄存器中。

[0130] 仍另一装置的以上示例，其中所述装置包括用于以下的构件：从计算设备所耦合到的网络或计算控制装置中的至少一个接收信号，所述信号传送型式和序列中的至少一
个。

[0131] 仍另一装置的以上示例中的任一个，其中所述装置包括用于以下的构件：在计算设备的显示器上视觉地呈现是否在序列内发现型式的指示。

[0132] 仍另一装置的以上示例中的任一个，其中所述装置包括用于以下的构件：经由计算设备所耦合到的网络而向计算设备传输结果数据，所述结果数据指示是否在序列内发现
型式。

[0133] 仍另一装置的以上示例中的任一个，其中串匹配操作基于后向非确定性DAWG匹配（BNDM）算法。

[0134] 仍另一装置的以上示例中的任一个，其中处理器元件基于单指令多数据（SIMD）架构。

[0135] 仍另一装置的以上示例中的任一个，其中所述装置包括用于以下的构件：在处理器元件的第三矢量寄存器中初始化指示元素所出现于的第一串内的位置的位掩码，在按位
逻辑与运算中组合第三矢量寄存器与第一矢量寄存器，并且确定测试位掩码的MSB位处的
位值，以确定是否在序列内发现型式。