可编程装置、层次并行机、用于提供状态信息的方法

摘要

本发明描述可编程装置、层次并行机及用于提供状态信息的方法。在一个此种可编程装置中，提供可编程元件。所述可编程元件经配置以实施一个或一个以上有限状态机。所述可编程元件经配置以接收N数字输入且依据所述N数字输入提供M数字输出。所述M数字输出包括来自少于所有所述可编程元件的状态信息。本发明还揭示其它可编程装置、层次并行机及方法。

说明书

相关申请案的交叉参考

本专利申请案主张2011年3月1日提出申请的标题为“可编程装置、层次并行机、 用于提供状态信息的方法(Programm able Device，Hierarchical Parallel Machines，Methods for Providing State Information)”的第13/037,706号美国申请案的优先权权益，所述美国 申请案依据35U.S.C.第119(e)款主张2010年月6月10日提出申请的标题为“用于在有 限状态机之间传送状态的系统及方法(System and Method for Transferring State Between Finite State Machine)”的第61/353,551号美国临时专利申请案的优先权权益，所述申请 案两者均以全文引用的方式特此并入本文中。

技术领域

背景技术

可编程装置的一个实例为并行机。并行机包括(例如)有限状态机(FSM)引擎及现场可 编程门阵列(FPGA)。FSM为状态表示，在状态与动作之间转变。有限状态机可以有向 流程图的形式表达。其可用以解决(例如)工程学、型式辨识、生物学及人工智能中的问 题。

发明内容

附图说明

图1图解说明根据本发明的各种实施例的层次并行机的实例。

图2图解说明根据本发明的各种实施例的经配置以用于型式辨识的层次并行机的实 例。

图3图解说明根据本发明的各种实施例的并行机的实例。

图4图解说明根据本发明的各种实施例的有限状态机图的实例。

图5图解说明根据本发明的各种实施例的有限状态机图的另一实例。

图6图解说明根据本发明的各种实施例的借助并行机所实施的两层级层次的另一实 例。

图7图解说明根据本发明的各种实施例的借助并行机所实施的四层级层次的实例。

图8图解说明根据本发明的各种实施例的有限状态机图群组的实例。

图9图解说明根据本发明的各种实施例的有限状态机图的另一实例，其中聚合以图 解方式所图解说明的状态机的最终状态。

图10图解说明根据本发明的各种实施例的有限状态机图群组的另一实例，其中聚 合以图解方式所图解说明的有限状态机中的每一者的最终状态。

图11图解说明根据本发明的各种实施例的可编程元件阵列的实例。

图12图解说明根据本发明的各种实施例的型式辨识处理器堆叠的实例。

图13图解说明根据本发明的各种实施例的借助并行机所实施的具有反馈的四层级 层次的实例。

图14图解说明根据本发明的各种实施例的借助并行机所实施的具有反馈的四层级 层次的另一实例。

图15图解说明根据本发明的各种实施例的有限状态机引擎。

图16图解说明根据本发明的各种实施例的图15的有限状态机引擎的块的实例。

图17图解说明根据本发明的各种实施例的图16的块的行的实例。

图18图解说明根据本发明的各种实施例的图10的行中的两个一群组的实例。

图19图解说明根据本发明的各种实施例用于编译器将源代码转换成图像以用于编 程图8的有限状态机的方法的实例。

图20图解说明根据本发明的各种实施例的具有基于冯·诺伊曼的架构的计算机的实 例。

具体实施方式

以下描述及图式充分图解说明特定实施例以使所属领域的技术人员能够实践所述 特定实施例。其它实施例可并入有结构、逻辑、电、过程及其它改变。一些实施例的各 部分及特征可包括于其它实施例的那些部分及特征中或替代其它实施例的那些部分及 特征。

除其它之外本文件还描述层次并行机(例如，层次有限状态机(HFSM)引擎)及相关方 法。图1中展示一个此种层次并行机10。每一层次并行机10包括两个或两个以上并行 机，例如，两个或两个以上有限状态机(FSM)引擎12。每一有限状态机引擎12为在输 入总线16上接收数据(例如，数据流)并对所述数据做出反应且依据所接收的数据提供(例 如，产生)输出的装置。

每一有限状态机引擎12可为任意复杂的。在例如图1中所展示的一个实施例中， 有限状态机引擎12经级联，其中将有限状态机引擎12中的至少一者的输出(例如，状态) 整体或部分地提供(例如，传递)到在级联中的下游的有限状态机引擎12中的一者或一者 以上。在一实例中，所述级联中的最后有限状态机引擎产生结果，可在输出总线(例如， 结果总线20)上提供所述结果。在一个实施例中，有限状态机引擎12中的每一者可例如 经由相应编程总线14来编程，例如，通过使用编程总线14将程序(例如，图像)加载(例 如，存储)到有限状态机引擎12上。

在一些实施例中，减少借助HPRP10处理数据所需要的时间可为重要的。借助HPRP 10处理数据的时间可至少部分地受在有限状态机引擎12之间所传递的数据(例如，状态 信息，例如状态向量)量的限制。在一些此类实施例中，有限状态机引擎12以层次配置 连接，且有限状态机引擎12之间的接口可经设计以近似实时操作。除其它之外，本文 件还描述此些考虑因素且建议一种用于层次并行机组(例如，层次FSM引擎12组)的物 理实施方案的一般方法。

在一个实例性实施例中，实施层次型式辨识处理器(HPRP)30，如图2中所展示。 型式辨识处理器为接收数据(例如，符号序列)并在辨识出(例如，检测到)所关注序列时产 生提供某一类型的通知的输出的装置。在简单情况中，在输入总线36上将单个输入符 号流提供到HPRP30。HPRP30经编程以经由编程总线34检测一特定输入符号序列或 若干特定输入符号序列。产生且可在结果总线40上提供结果(所检测到的序列)。图2中 展示HPRP30的逻辑接口(编程接口34及数据输入36)。

在所展示的实施例中，HPRP30可包括编程为型式辨识处理器(PRP)32的两个或两 个以上有限状态机引擎。每一PRP32为能够检测相应数据流(例如，输入总线36或输入 总线42上的数据流)中的符号序列的装置。举例来说，每一PRP32可能够匹配相应数据 流中的相应型式。在所图解说明的实施例中，第二PRP32接收第一PRP32的输出(在 输出总线38上提供)作为其输入并在结果总线40上产生结果。在一个实施例中，可经由 相应编程总线34来编程PRP32中的每一者。下文参考图15到18来描述实例性PRP32 (还称作“内容检查处理器”)。在某些实例中，使用有限状态机(FSM)引擎或现场可编程 门阵列(FPGA)或其变化形式或并行机的另一实施方案来实施HPRP30。

层次并行机10及30的两层级(例如，级)层次允许两个独立程序基于相同数据流而 操作。两层级层次可类似于建模为不同区的人类大脑中的视觉辨识。在此模型下，所述 区为实际上不同的型式辨识处理器，每一型式辨识处理器执行类似计算功能(检测数据流 中的符号序列)但使用不同程序(例如，签名)。通过将多个并行机连接在一起，可获得关 于数据流的更深知识。

举例来说，所述层次的第一层级(例如，由第一FSM引擎12或第一PRP32实施的 层级)可直接对原始数据流执行处理。也就是说，第一FSM12或PRP32可分别依据输 入总线16或输入总线36上的原始数据流而产生输出数据流(例如，原始数据流中的一匹 配或若干匹配的指示)。如图1中所展示，第二层级(例如，由第二FSM引擎12或第二 PRP32实施的层级)处理来自所述第一层级的输出数据流。举例来说，第二FSM引擎12 从第一FSM引擎12接收输出数据流(在输出总线18上提供)且第二FSM引擎12处理第 一FSM引擎12的输出数据流。因此，第二FSM引擎12并不接收原始数据流作为输入， 而是接收第一FSM引擎12所产生的输出数据流。可用第一图像编程第二FSM引擎12 以检测第一FSM引擎12所产生的输出数据流中的序列。第二FSM引擎12可耦合到单 独编程接口(例如，通过编程总线14)以用于接收第二图像。

在一实例中，HPRP30可经编程以实施型式辨识功能。举例来说，由HPRP30实施 的FSM可经配置以辨识输入到HPRP30的数据流中的一个或一个以上数据序列(例如， 签名)。当第一PRP32辨识出(例如，匹配)所述数据流中的所关注序列时，可在输出总 线38上提供指示所述辨识的输出数据流。在一实例中，所述型式辨识可为辨识一串符 号(例如，ASCII字符)以(例如)识别网络数据中的恶意软件或其它信息。

可将此输出数据流(例如，输出字、检测状态等)从第一PRP32的输出总线38馈送 到另一PRP32的输入总线42，如图2中所展示。两个PRP32的此串行连接提供将关于 过去事件的信息以经压缩字从第一PRP32提供到第二PRP32的手段。此信息提供实际 上可为已被第一PRP32辨识出的复杂事件(例如，数据流序列)的概要。

如上所述，在一些实施例中，减少在PRP的层级之间传递输出所需要的时间可为重 要的。在一些此种实施例中，PRP32之间的接口可经设计以支持HPRP30的每一层级 的实时操作。举例来说，本文件描述此些考虑因素且建议一种用于HPRP30的物理实施 方案的一般方法。

本文件除其它之外还描述用于使用层次结构处理数据的方法及设备。所述层次结构 可包含多个层级(例如，层)，其中每一层级处理数据(例如，对其执行分析)并提供输出(例 如，基于所述分析)。可将来自所述层次结构中的较低层级的输出作为输入提供到较高层 级。以此方式，较低层级可执行较基本/基础分析，而较高层级可使用来自一个或一个以 上较低层级的输出来执行较复杂分析。在一实例中，所述层次结构执行型式辨识。

在一实例中，借助以级联方式耦合在一起的多个有限状态机引擎来实施所述层次结 构。举例来说，第一有限状态机引擎与第二有限状态机引擎可串行耦合以使得所述第二 有限状态机引擎从所述第一有限状态机引擎接收输出作为输入。任一数目个有限状态机 引擎可一起耦合在此层次结构中。

除使用层次结构处理数据之外，本文件还描述用于使用来自一个有限状态机引擎的 输出来修改另一有限状态机引擎所执行的处理的方法及设备。使用上文所述的有限状态 机引擎实例，实施较高层级的处理的第二有限状态机引擎可将反馈信息提供到实施较低 层级的处理的第一有限状态机引擎。所述反馈信息可由所述第一有限状态机引擎用来以 类似于在生物大脑中学习的方式修改(例如，更新)处理。

图3图解说明可用以实施有限状态机引擎或型式辨识处理器的实例性并行机100。 并行机100可接收输入数据并基于所述输入数据而提供输出。并行机100可包括用于接 收输入数据的数据输入端口110及用于将输出提供到另一装置的输出端口114。数据输 入端口110提供用于将数据输入到并行机100的接口。

并行机100包括多个可编程元件，包括通用元件102及专用元件112。通用元件102 可包括一个或一个以上输入104及一个或一个以上输出106。通用元件102可被编程到 多个状态中的一者中。通用元件102的状态确定通用元件102将基于给定输入而提供何 种输出。也就是说，通用元件102的状态确定可编程元件将对给定输入如何做出反应(例 如，响应)。可将输入到数据输入端口110的数据提供到多个通用元件102以致使通用元 件102对其采取行动。通用元件102的实例可包括(例如)如下文详细论述的状态机元件 (SME)、计数器及/或可配置逻辑块以及其它可编程元件。在一实例中，SME可经编程(例 如，设定)以当在数据输入端口110处接收到给定输入时提供某一输出(例如，高信号或 “1”信号)。当在数据输入端口110处接收到除所述给定输入之外的输入时，所述SME 可提供不同输出(例如，低信号或“0”信号)。在一实例中，可配置逻辑块可经设定以基 于在数据输入端口110处所接收的输入而执行布尔逻辑函数(例如，“与”、“或”、“非 或”等)。本文稍后论述计数器的实例。专用元件112可包括存储器(例如，RAM)、逻辑 门、计数器、查找表、现场可编程门阵列(FPGA)及其它硬件元件。专用元件112可与通 用元件102交互且执行专用功能。

并行机100还可包括用于将程序(例如，图像)加载到并行机100上的编程接口111。 所述图像可编程(例如，设定)通用元件102的状态。也就是说，所述图像可配置通用元 件102以便以某一方式对给定输入做出反应。举例来说，通用元件102可经设定以当在 数据输入端口110处接收到字符‘a’时输出高信号。在一些实例中，并行机100可使 用时钟信号来控制通用元件102的操作的计时。在一些实施例中，在数据输入端口110 处所接收的数据可包括随时间或同时一起接收的固定数据集或随时间接收的数据流。所 述数据可从耦合到并行机100的任一源(例如数据库、传感器、网络等)接收或由所述源 产生。

并行机100还包括多个可编程开关108以用于选择性地将并行机100的不同元件(例 如，通用元件102、数据输入端口110、输出端口114、编程接口111及专用元件112) 耦合在一起。因此，并行机100包含在所述元件当中形成的可编程矩阵。在一实例中， 可编程开关108可选择性地将两个或两个以上元件彼此耦合在一起以使得通用元件102 的输入104、数据输入端口110、编程接口111或专用元件112可通过一个或一个以上 可编程开关108耦合到通用元件102的输出106、输出端口114、编程接口111或专用 元件112。因此，可通过设定可编程开关108来控制信号在所述元件之间的路由。虽然 图3图解说明给定元件与可编程开关108之间的某一数目个导体(例如，导线)，但应理 解，在其它实例中可使用不同数目个导体。此外，虽然图3图解说明每一通用元件102 个别地耦合到可编程开关108，但在其它实例中，多个通用元件102可作为一群组(例如， 图15中所图解说明的块802)耦合到可编程开关108。在一实例中，数据输入端口110、 数据输出端口114及/或编程接口111可实施为寄存器以使得向所述寄存器的写入将数据 提供到相应元件或从所述相应元件提供数据。

在一实例中，在一物理装置上实施单个并行机100，然而在其它实例中可在单个物 理装置(例如，物理芯片)上实施两个或两个以上并行机100。在一实例中，多个并行机 100中的每一者可包括相异数据输入端口110、相异输出端口114、相异编程接口111及 一组相异通用元件102。此外，每一组通用元件102可对其对应输入数据端口110处的 数据做出反应(例如，输出高信号或低信号)。举例来说，对应于第一并行机100的第一 组通用元件102可对对应于第一并行机100的第一数据输入端口110处的数据做出反应。 对应于第二并行机100的第二组通用元件102可对对应于第二并行机100的第二数据输 入端口110做出反应。因此，每一并行机100包括一组通用元件102，其中不同组通用 元件102可对不同输入数据做出反应。类似地，每一并行机100及每一对应组通用元件 102可提供相异输出。在一些实例中，来自第一并行机100的输出端口114可耦合到第 二并行机100的输入端口110，以使得用于第二并行机100的输入数据可包括来自第一 并行机100的输出数据。

在一实例中，用于加载到并行机100上的图像包含用于设定通用元件102的状态、 编程可编程开关108及配置并行机100内的专用元件112的多个信息位。在一实例中， 可将所述图像加载到并行机100上以编程并行机100以基于某些输入而提供所要输出。 输出端口114可基于通用元件102对输入端口110处的数据的反应而提供来自并行机100 的输出。来自输出端口114的输出可包括指示给定型式的匹配的单个位、包含指示与多 个型式的匹配及不匹配的多个位的字及对应于所有或某些通用元件102及专用元件112 的状态的输出向量。

并行机100的实例性用途包括型式辨识(例如，语音辨识、图像辨识等)、信号处理、 成像、计算机视觉、密码编译及其它。在某些实例中，并行机100可包含有限状态机(FSM) 引擎、现场可编程门阵列(FPGA)及其变化形式。此外，并行机100可为较大装置(例如， 计算机、寻呼机、蜂窝式电话、个人记事本、便携式音频播放器、网络装置(例如，路由 器、防火墙、交换机或其任一组合)、控制电路、相机等)中的组件。

并行机(例如，FSM引擎、PRP等)可实施状态机。状态机可表示为有向图。图4展 示简单状态机图150，其表示在字‘DOG’中所找到的字符序列。状态152为状态机图 150的输入状态。状态154为中间状态。在图4中，最终状态156(有时还称作终端状态) 由围绕‘G’状态的虚线边界识别。在一般情况中，当到达最终状态时，通过某一机制指 示匹配条件。此匹配条件可由来自并行机100(例如，FSM引擎12、PRP32)的显式信号 表示，或其可编码为二进制字并存储于存储器寄存器中。

不存在对状态机的大小的理论限制。在一般情况中，PRP或FSM引擎可针对所述 PRP或FSM引擎可检测到的每一特定符号序列实施单独状态机。如果需要，那么可对 状态机执行优化以便消除冗余(共用路径)，以便将状态机组合成较大实施方案或最小化 特定状态机实施方案的大小。此些优化可减小状态机实施方案及因此(例如)实施状态机 的状态机引擎的聚合大小。一旦完成此优化，便可实施单个大状态机。

图5展示较大状态机图200。在一般情况中，状态机实施方案可具有前向复杂连接 及后向复杂连接两者。在图5中所展示的实例中，一个输入状态202馈送两个中间状态 204。在此些状态机中，可存在许多最终状态208及许多其它中间状态204。

状态机中的每一状态具有指示所述状态是否活动的瞬时状况。仅活动状态可对输入 符号做出反应。在一个实施例中，当在输入总线36上接收到输入符号时，所述状态机 中的每一活动状态将分析所述符号以确定是否应产生激活信号。此激活信号将用以激活 序列中的下一状态。举例来说，指定字符‘b’的第一状态204将在第一节点204为活动的 且接收到字符‘b’作为输入数据时在输入字符‘b’上激活通过转变206连接到第一状态 204的第二状态204。

在图200中，输入状态202可首先被激活且可在输入数据匹配来自输入节点202的 转变206时激活下游状态204。在接收到输入数据时，可以此方式激活整个图200中的 状态204、208。经激活最终状态208对应于输入数据与所关注序列的匹配。因此，激活 最终状态208指示已在输入数据处接收到所关注序列。在实施型式辨识功能的有限状态 机引擎100的背景中，激活最终状态208可指示已在输入数据上检测到特定所关注型式。

在一实例中，每一中间状态204及最终状态208可对应于有限状态机引擎100中的 通用元件102。每一转变206可对应于通用元件102之间的连接。因此，转变到另一中 间状态204或最终状态208(例如，具有连接到另一中间状态204或最终状态208的转变 206)的中间状态204对应于可耦合到另一通用元件102的通用元件102。在一些特殊情 况中，开始状态202可未必具有对应通用元件102。

当有限状态机引擎100经编程以实施FSM时，通用元件102中的每一者可处于活 动或不活动状态中。不活动通用元件102不对输入接口110处的数据流做出反应。活动 通用元件102可对输入接口110处的数据流做出反应，且可在输入数据流匹配通用元件 102的设定时激活下游通用元件102。当通用元件102对应于最终状态208时，通用元 件102可耦合到输出端口114以提供与外部装置的匹配的指示，所述外部装置在一些情 况中可为另一有限状态机引擎100。

经由编程接口111加载到有限状态机引擎100上的图像可配置通用元件102及通用 元件102之间的连接，以使得基于对输入接口110处的数据流的响应而通过激活下游状 态来实施所要FSM。在一实例中，通用元件102保持活动达单个数据循环(例如，单个 字符、一组字符、单个时钟循环)且除非被上游通用元件102重新激活否则接着切换到不 活动。

可认为最终状态208存储经压缩的过去事件历史。举例来说，激活最终状态208所 需要的一个或一个以上输入数据序列可由所述最终状态208的激活表示。在一实例中， 最终状态208所提供的输出为二进制的，也就是说，所述输出指示是否已匹配对应所关 注序列。在FSM中最终状态208对中间状态204的比率可相当小。换句话说，虽然在 所述FSM中可存在高复杂度，但比较来说所述FSM的输出可为小的。

不管FSM引擎是实施单个经组合(经优化)状态机还是实施许多独立状态机，均存在 状态向量的概念。状态向量为在所实施的状态机中的个别状态与向量内的个别数字(例 如，位)位置之间具有一对一对应性的一维向量。也就是说，状态机中的每一状态与状态 向量中的数字有关。在图4的情况中，状态向量为3个位宽(其中一个位指示状态152、 154及156中的每一者的状态)。在图5的情况中，状态向量为74个位宽。状态机可为 任意复杂的且因此理论上对机器的总大小不施加任何限制。因此，状态向量可无限长。

然而，为了在并行机中实施实际状态机，通常对状态机的大小施加某一有限限制。 不严格界定此限制且可基于用以实施状态机的并行机的特性而确定此限制。

图6中展示另一HFSM400。在图6中所展示的HFSM400中，三个有限状态机引 擎402使用所有其相应状态向量数字的全部或一部分将关于其相应状态的信息提供到一 个有限状态机引擎404。在所展示的实例中，每一状态机引擎(402、404)经由其相应编 程接口(PROG)被编程。在其它实施例中，来自FSM引擎402中的每一者的数据用以编 程FSM引擎404。在一些此种实施例中，FSM引擎404经设计以根据从FSM引擎402 接收的状态信息进行调适。

图7中展示较复杂的HFSM500。在图7的HFSM500中，多个FSM引擎502、504、 506、508连接在一起，其中FSM引擎502通过总线510将状态信息提供(例如，馈送) 到FSM引擎504，FSM引擎504通过总线512将状态信息馈送到FSM引擎506，且FSM 引擎506通过总线514将状态信息馈送到FSM引擎508。多个FSM层级502到508的 此连接允许层次的每一层级实施不同状态机。在一些实例性HFSM中，层次的每一层级 对不同类型的型式敏感。在这些实例性HFSM中，如在HFSM500中，层次层级的此分 离允许HFSM实施低层级辨识，使所述低层级辨识传递穿过层次的各个层级以实现较高 层级辨识。在一个实例中，在HFSM500的结果总线516上提供结果，例如，特定型式 (例如，短语)的识别。在其它实例中，所述结果为来自FSM引擎502、504、506及508 中的一者或一者以上的状态位的组合。

如图7中所展示，一种用于以层次方式连接个别FSM引擎的方法为将一个FSM引 擎的输出连接到层次中的下一较高层级FSM引擎的输入。应理解，可实施HFSM500， 其中将来自一个层级的状态信息提供(例如，前馈或反馈)到层次中的任一其它层级。举 例来说，可将来自FSM引擎502的状态信息发送到FSM引擎506，而可将来自FSM引 擎508的状态信息反馈到FSM引擎502。一般来说，在无论何种被视为必需的配置中， 均可将来自一个或一个以上FSM引擎的状态信息提供到其它FSM引擎中的一者或一者 以上(例如，全部)。

图7中所展示的实例对应于书面语言的视觉识别。随着处理进展到层次的较高层级， 对数据流的积累的知识对应地增长。在所展示的实施例中，每一层级处的FSM引擎(FSM 引擎502、504、506及508)经级联以实现层次辨识能力。层次的每一连续层级可实施应 用于先前层级的输出的新规则(型式签名)。以此方式，可基于对非常基本的基元信息的 检测而识别高度详细的对象。

举例来说，到层级1(例如，第一FSM引擎502)的原始数据输入流可包含图像的像 素信息(例如，不管给定位是黑色/白色或接通/关断)。FSM引擎502可经编程以辨识(例 如，识别)所述位所形成的基元型式。在一个实例中，FSM引擎502经配置以识别邻近 位的群组何时形成垂直线、水平线、弧等。这些型式中的每一者可由来自FSM引擎502 的单独输出位(或信号)识别。举例来说，当FSM引擎502辨识出至少3个位的垂直线时， 可在输出字的第一位上将高信号(例如，逻辑1)发送到FSM引擎504。当FSM引擎502 识别出至少3个位的水平线时，可在输出字的第二位上将高信号发送到FSM引擎504。

同时FSM引擎504可经编程以识别由来自FSM引擎502的输出510形成的型式。 举例来说，FSM引擎504可经编程以识别FSM引擎502所识别的基元型式(线、弧等) 的组合所形成的型式。举例来说，FSM引擎504可经编程以识别水平线与垂直线何时交 叉从而形成字母“t”。如上文所提及，使用FSM引擎504所实施的HFSM500对来自 FSM引擎502的输出做出反应。因此，通过识别来自FSM引擎502的输出位中的型式 来识别基元型式的组合。

接着将来自FSM引擎504的输出512输入到FSM引擎506中，FSM引擎506可从 FSM引擎504所识别的字母的组合识别字。接着第四层级(FSM引擎508)可识别FSM引 擎506所识别的字所形成的短语。因此，较高层级可经编程以识别较低层级输出中的型 式。另外，较低层级可经编程以识别构成在较高层级中所识别的型式(反馈到较低层级) 的分量。

对字母的视觉识别用作实例。然而，本文所述的层次方法及系统可应用于其它数据。 举例来说，对对应于声音的数据的层次处理可从层级1处的音素的组合识别音节且从层 级2处的音节的组合识别字。在其它实例中，层次处理可应用于以层次方式在自身上构 建的机器数据。

当实施HPRP或HFSM(例如，HFSM500)时，可能遇到的一个问题是输入数据与输 出数据之间的不对称关系。当正实施的状态机变得足够大时，此不对称性加剧。对于所 处理的每一输入符号来说，FSM引擎的状态向量可响应于所述输入符号而改变。在一个 实施例中，每一FSM包括(例如)多达2的16次幂(64K)个状态。如果每一状态在状态向 量中具有对应数字，那么状态向量将为64K个位长。可能难以在FSM引擎之间传递所 述长度的向量。接下来将描述用以减小输入数据的大小与输出数据的大小之间的此不对 称的方法。

在一个实施例中，在总线上于FSM引擎之间发送数据。N位宽的总线可在64Kb/N 个循环中传递64Kb状态向量。在其它实施例中，所述状态向量经压缩以使得向量中仅 响应于输入符号而改变的数字传播到其它FSM引擎。举例来说，每一总线循环可能包 括状态向量中的在先前符号循环中已改变的数字的位置。在此情况中，所述输出可称作 差向量。

在又一实施例中，每一FSM引擎经设计以仅将来自状态向量的数字子集发送到其 它FSM引擎。在一个此种实施例中，每一FSM引擎经编程以使得传递到其它FSM引 擎的仅有状态信息为最终状态的状态信息。在一般情况中，最终状态的数目小于状态的 总数目。举例来说，PRP32中最终状态对总状态的比率取决于在PRP中所实施的状态 机。举例来说，比率可为高的(1∶5)或相当低(1∶10,000)。

在其中最终状态对总状态的比率为1∶10且状态向量为64Kb的实际实例中，此暗示 输出向量将为64Kb/10或6,554个位。在此实例中，PRP的每一输入循环(8个位符号) 将产生6,554个位的对应输出向量。

对于接下来的实例来说，将使用其中ASCII字符集为输入(符号)语言的实例。在此 情况中，每一输入符号由8位二进制字表示。在替代实施例中，可使用其它符号，例如， 其中每一输入符号为N位二进制字。

举例来说，在一个实施例中，发送到HPRP30(例如，图2中所描绘的HPRP30)中 的第二层级PRP32的输出向量可仅表示第一层级PRP32的最终状态。在另一实例中， 在HFSM500(例如，图7中所描绘的HFSM500)中，FSM引擎504可产生表示其最终 状态的输出向量并在输出总线514上将所述输出向量发送到FSM引擎506。在一个此种 实例中，输出总线514为8位宽总线。使用从先前实例所引用的8∶6,554比率，提供(例 如，传送)输出向量的6,554个位所需要的循环的数目将为6,554/8或820个循环。也就 是说，层次的每一连续层级将需要820个输入循环来处理来自先前层级的输出字。此效 应线性地以纹波形式穿过所述层次，以使得每一连续状态将需要820个输入循环来解析 其输入字。在此情况中，在给定比率下，PRP的六层级层次将需要4,100(5×820)个输入 循环以允许输入符号以纹波形式穿过直到在最高层级处产生结果为止。这些数目仅用作 实例。如果最终状态对总状态的比率增加，那么纹波时间将增加。同样，如果层次的层 级的数目增加，那么纹波时间将随着每一连续层级线性地增加。

基于上文所使用的实例，对于HFSM或HPRP产生结果来说，数个数量级的延迟(相 对于输入循环)是可能的。此类型的延迟在实时应用中可为不可接受的。如上所述，可通 过(例如)增加总线的大小来减少传送状态信息所需要的循环的数目。还可降低总线循环 时间以减少传送状态信息所需要的时间。此外，如上所述，可发送仅识别状态向量的由 于最后的符号而改变的数字的差向量。也可使用其它无损压缩机制。

接下来论述用以减小此延迟的其它方法，例如，实施输入与输出之间的1∶1关系。

一种用以在HFSM(例如，HFSM500)中获得输入与输出之间的1∶1关系的方式是使 输入总线518与输出总线510在大小(宽度)上相等。输出总线510的宽度可由HFSM500 自身确定。举例来说，输出总线510的大小可由状态机引擎502中的最终状态的数目确 定。一般来说，FSM引擎经编程以同时辨识许多不同型式。这些型式中的每一者可实施 为个别状态机。以此方式，FSM引擎可实施一组状态机，其全部并行运行。

图8以图解方式展示单个FSM引擎内全部并行运行的状态机532的群组530的实 例。在图8中，展示8个状态机532。实际上，FSM引擎可实施成千上万个个别状态机。

步骤1：状态机输出的聚合(最终状态)

如图9中所展示，每一个别状态机532可具有一个或一个以上最终状态208。虽然 可存在数个最终状态208，但特定状态机532的最终状态中的任一者具有相同或相关含 义。换句话说，如果到达状态机532的最终状态208中的任一者，那么认为所述状态机 具有匹配。实际上，此意指可(例如)通过使用“或”门540将对应于单个状态机532的 最终状态208的可编程元件的输出耦合在一起而聚合(例如，“或”运算在一起)所述最 终状态以提供如图9中所展示的单个输出542。在图9中所展示的实例中，状态机532 将三个最终状态208“或”运算在一起。如可理解，可使用其它逻辑来聚合最终状态208。

在一个实例中，一旦每一状态机532的最终状态208已经聚合(例如，经“或”运算)， 便将结果分组(例如，收集)成N个状态机532的逻辑群组，其中N等于相应输入符号语 言中的数字的数目。在其中第一层级的输入符号语言包含8位输入字的实例中，8个个 别状态机输出542可经聚合以提供输入符号546中的提供到层次的下一层级的一者。在 图7中，举例来说，仅层次的第一层级接收与标准语言(ASCII或其它)相关的输入符号。 则在所述实例中，FSM引擎502可产生在输出总线510上提供到FSM引擎504的8位 输出向量。层次的后续层级接收具有由先前层级确定的含义的输入符号。

一旦状态机已经分组(例如，8个一组的若干个组)，正规化输入及输出向量的第一 层级便已完成。使用来自本发明中所使用的实例的数目，可以103个8位字来表示820 个最终状态。这些8位字中的每一者编码8个个别状态机532的最终状态的状况。记住 在此8位输出向量中所编码的最终状态的总数目可远大于8。这是因为对同一状态机532 中的最终状态208所执行的“或”运算函数可将8个以上状态“或”运算在一起。

在一个实施例中，每一FSM引擎包括N位宽的输入端口及N位宽的输出端口。在 一个实施例中，通过N位总线将来自每一层级的状态信息(例如，以输出向量的形式， 例如，状态向量的全部或一部分，或差向量)分布到下一FSM引擎。举例来说，FSM引 擎502使用N位输出总线510将状态信息分布到FSM引擎504。在一个实施例中，将 同一N位输出向量提供(例如，分布)到FSM引擎504中的每一状态机。在另一实施例中， 将FSM引擎504中的可编程元件分组成若干群组(例如，块)且FSM引擎502的输出端 口将N位字序列写入到FSM引擎504且以预定义方式(例如，依序地)将字序列分布到 FSM引擎504中的状态机元件块。此方法允许将额外状态信息分布到FSM引擎504， 但需要额外总线循环来传送完整的状态信息。

在一个实施例中，一个可编程元件群组的状态信息是通过发送包括另一FSM引擎 的指示的地址信息及所述FSM引擎内的可编程元件群组的地址而发送到所述FSM引擎 中的所述群组。可在(例如)图7中的总线510上分布所述信息。

步骤2：PRP上的输入总线的数目的扩充

FSM12或PRP32的一个实施方案具有将输入符号广播到在PRP中所实施的所有状 态机532的单个流输入。然而，可扩展FSM12及PRP32的定义以实施一个以上流输入 (分别为16及36)。在先前所引用的实例中，独立流输入的总数目将等于103。举例来说， 为了完整地实施，HPRP则将需要103个8位输入或用于每一PRP32的820个位的输入 总线。

在一个实施例中，在可编程元件(例如，状态机元件(SME))阵列560上实施FSM12 及PRP32。在一个实例中，每一SME在同质二维阵列560中。可将此阵列560细分成 若干个别区，其中每一区具有其自己的专用流输入(分别为16及36)。图11展示SME 元件的此二维阵列560。举例来说，将图11细分成SME群组562的阵列560，其中每 一SME群组562可对应于有限状态机引擎800中的块802。整个阵列560可包括(例 如)16×16个SME群组(总共256个群组)，其中每一群组562包括128个含两个SME的 群组(GOT)(例如，其中每一群组562包括16个GOT行，例如，图16中所图解说明的 行806)。

在一些实施例中，每一GOT行含有8个GOT、一(若干)额外可编程元件(例如，布 尔逻辑或计数器)且可将两个输出提供到输出总线18、38。如果跨越FSM12及PRP32 使用所有可用输出，那么此阵列可具有(例如)多达8192个位以驱动到下一层级PRP32。

当构造例如图7中所展示的HFSM500时，可将两个不同半导体装置(例如，FSM 引擎502及504)中的二维SME群组562阵列连接在一起。存在将两个半导体装置连接 在一起的各种手段。举例来说，当I/O计数变得足够高时，可利用裸片间互连件。在一 个实例性实施方案中，如图12中所展示，HPRP570中的256个SME群组562中的每 一者可具有裸片的底部上的8位接口(例如，输入总线36、42)及所述裸片的顶部上的8 位接口(例如，输出总线38、40)。当将这些接口置于预定义位置中时，一个PRP层级(PRP1) 582可直接堆叠于较低层级PRP(PRP0)580的顶部上，其中输入及输出接口自然地对准 且使用例如互连件574的互连件(例如，穿硅通孔)连接在一起。

此对准有效地形成SME列(由输入路径572、输出路径578以及互连件574及576 界定)的概念，其中所述列的每一层级表示含在同一裸片上的SME群组。继续使用先前 所论述的实例性数目，在每一PRP层级(580、582及584)上，SME群组562可由在先前 层级上所实施的多达8个状态机驱动。来自先前层级的8个状态机可为任意复杂的，直 到SME群组562所施加的限制。图12展示三层级HPRP的实例(边缘视图)，其中突出 显示SME列中的一者。在每一层级中，SME的分组将来自所述层级的状态信息(例如， 经编码的8位字)提供到下一较高层级。

总的来说，当以此方式配置时，HPRP可以PRP层次的每一层级仅一个输入时钟循 环的延迟提供实质上瞬时结果。因输入与输出字的不对称性而引起的问题得以解决且整 个层次可与流输入572同步操作。

在某些实施例中，将来自一个FSM引擎12的状态信息发送到一个以上其它FSM 引擎12。图6中展示此实施例。参考图12中所图解说明的HPRP570描述此实施例， 举例来说，可将来自PRP580的状态信息发送到PRP584。在一个此种实施例中，互连 件576及574形成将状态信息传输到列中的块中的任一者的总线。举例来说，互连件574 及576可包含一个或一个以上穿通孔互连件，且可提供于每一列中以用于将状态信息传 递到非邻近PRP。在一个此种实施例中，堆叠中的每一PRP连接到所述穿通孔并从所述 穿通孔接收信息。在另一实施例中，在制造过程期间根据需要将PRP的输入选择性地连 接到穿通孔。

在其它实施例中，来自一个SME群组的状态信息分布到同一PRP32中的邻近块， 且通过那些块分布到其它PRP32(例如，在同一块列中)。

在一个实施例中，来自一个或一个以上PRP32的状态信息或从所述状态信息导出 的信息用以重新编程层次中的其它PRP32。图13图解说明四层级层次的实例，其使用 反馈来重新编程所述层次的部分。一般来说，可基于来自较高或较低层级有限状态机引 擎的输出或基于其自己的输出而重新编程给定PRP32(例如，第一有限状态机引擎602)。 因此，第一有限状态机引擎602可改变以根据在运行时间期间改变的条件进行调适。在 一实例中，反馈可供较低层级基于较高层级进行学习(被重新编程)。使用有限状态机引 擎602作为实例，反馈可在编程接口602B处接收且可呈用于有限状态机引擎602的新 的或经更新程序的形式。在一实例中，所述经更新程序可重新编程一些或所有有限状态 机引擎602。

借助四个有限状态机引擎602、604、606、608来实施图13中的四层级层次600， 每一并行机具有数据输入端口602A、604A、606A、608A、编程接口602B、604B、606B、 608B及输出端口602C、604C、606C、608C。第一有限状态机引擎602实施层次600 的第一层级且将输出提供到实施层次600的第二层级的第二有限状态机引擎604。第三 有限状态机引擎606及第四有限状态机引擎608同样实施层次600的第三层级及第四层 级。在一实例中，基于层次600对第一有限状态机引擎602所接收的输入数据的分析而 将来自第四有限状态机引擎608的输出作为层次600的输出发送到外部装置。因此，来 自第四有限状态机引擎608的输出对应于层次600的集合输出。在其它实例中，来自有 限状态机引擎中的其它者602、604或606的输出可对应于层次600的集合输出。

可将来自第二有限状态机引擎604、第三有限状态机引擎606及第四有限状态机引 擎608的输出各自反馈到下面层级处的有限状态机引擎602、604、606的编程接口602B、 604B、606B。举例来说，将来自第四有限状态机引擎608的输出反馈到第三有限状态机 引擎606的编程接口606B中。因此可基于来自第四有限状态机引擎608的输出而重新 编程第三有限状态机引擎606。因此，第三有限状态机引擎608可在运行时间期间修改 其程序。可分别基于来自第二有限状态机引擎604及第三有限状态机引擎606的输出而 在运行时间期间类似地重新编程第一有限状态机引擎602及第二有限状态机引擎604。

在一实例中，来自来自有限状态机引擎604、606、608的输出的反馈经处理(例如， 分析及编译)以形成用于重新编程有限状态机引擎602、604、606的程序。举例来说，来 自有限状态机引擎608的输出可在被发送到编程接口606B之前由处理装置614分析并 编译。处理装置614可基于来自有限状态机引擎608的输出而产生用于有限状态机引擎 606的经更新程序。处理装置614可分析所述输出并编译用于第三有限状态机引擎606 的经更新程序。接着可通过编程接口606B将所述经更新程序加载到第三有限状态机引 擎606上以重新编程第三有限状态机引擎606。在一实例中，所述经更新程序可仅含有 从当前程序的部分改变。因此，在一实例中，经更新程序仅替换有限状态机引擎602、 604、606、608上的当前程序的一部分。在另一实例中，经更新程序替换当前程序的全 部或一大部分。同样，处理装置610、612可基于来自第二有限状态机引擎604及第三 有限状态机引擎606的输出而以类似方式分析并编译反馈。可借助一个或一个以上额外 有限状态机引擎来实施或可借助不同类型的机器(例如，具有冯·诺伊曼架构的计算机)来 实施处理装置610、612、614。

在一些实例中，处理装置610、612、614在编译新的程序之前分析来自较高层级的 输出。在一实例中，处理装置610、612、614分析所述输出以确定如何更新较低层级程 序且接着基于所述分析而编译新的或经更新较低层级程序。虽然在层次600中给定有限 状态机引擎处的反馈是从直接在所述给定有限状态机引擎上面的层级接收的，但反馈可 从任一层级有限状态机引擎到较高、较低或同一层级处的另一有限状态机引擎。举例来 说，反馈可在有限状态机引擎的编程输入处从所述同一有限状态机引擎的输出或从相 同、较高或较低层级处的另一有限状态机引擎的输出接收。另外，有限状态机引擎可从 多个不同有限状态机引擎接收反馈。基于反馈对有限状态机引擎的重新编程可与对输入 数据中的型式识别在时间上断开(例如，并不随着原始数据的处理实时地)。

沿层次向下往回发送信息以影响较低层级的重新编程的目的是可使得较低层级在 辨别所关注型式时可变得更高效。在一些实例中，认识到将信息传送到层次的较高层级 花费时间，因此在可能时避免将信息发送到较高层级的过程。在一些实例中，较高层级 可基本上用以解析对于系统来说为新的型式的识别。此可类似于在生物大脑的大脑新皮 质中发生的所使用过程。在一实例中，如果可在较低层级处完全解析一型式，那么应这 样做。反馈机制为将“学习”传送到层次的较低层级的一种方法。沿层次向下回推信息 的此过程将帮助保留层次的上部层级以用于处理新的或不熟悉的型式。此外，可通过减 小穿过层次的各个层级的数据传送量来加速整个辨识过程。

反馈可使层次的较低层级对输入处的数据流更加敏锐地敏感。此“向下推”信息的 结果是可在层次的较低层级处做出决策且所述决策可如此快地完成。因此，在一实例中， 来自较低层级有限状态机引擎(例如，第一有限状态机引擎602)的输出可对应于从层次 600到另一装置的集合输出连同来自第四有限状态机引擎608的输出。外部装置可(例如) 监视来自这些有限状态机引擎602、608中的每一者的输出以确定层次600何时已识别 出型式。

在一实例中，反馈信息可包括对应于所分析的数据流的识别信息。举例来说，所述 识别信息可包括数据的识别特性、数据的格式、数据的协议及/或任一其它类型的识别信 息。所述识别信息可由(例如)处理装置610收集、分析且用来调适用于输入数据的分析 方法。接着可用经调适的分析方法来编程有限状态机引擎。识别信息可包括(例如)输入 数据的语言。有限状态机引擎可首先经编程以确定输入数据的语言且一旦已识别对应于 输入的语言便可在运行时间期间对所述有限状态机引擎进行调适(例如，重新编程)。用 于有限状态机引擎的经调适分析方法可更特定地对应于用于所识别语言的分析方法。最 后，有限状态机引擎可使用经调适分析方法来分析未来的输入数据。反馈过程可反复以 使得可在输入数据中找到额外识别信息以允许进一步调适分析方法。

用于加载到有限状态机引擎上的程序(本文中还称作“图像”)可由下文关于图19所 论述的编译器产生。一般来说，编译可为计算密集的过程，且可能在第一次编译型式签 名的大数据库时最明显。在运行时间操作中，较高层级的有限状态机引擎可正在以用于 较低层级有限状态机引擎的增量程序更新的形式将反馈提供到较低层级。因此，到较低 层级有限状态机引擎的反馈信息可为对原始程序的编译起来较不计算密集的小得多的 增量更新。

图14图解说明借助四个有限状态机引擎702、704、706、708所实施的四层级层次 700的另一实例。此处，第二有限状态机引擎704、第三有限状态机引擎706及第四层 级有限状态机引擎708从较低层级的输出以及原始数据流接收输入数据。因此，层级2、 3及4可从来自较低层级与原始数据的型式的组合识别型式。

如从图13及14可见，有限状态机引擎可以几乎任一方式级联，其中可将到层次的 原始数据输入以及来自有限状态机引擎的输出发送到任一其它有限状态机引擎，包括其 自身。此外，可将来自给定有限状态机引擎的输出作为输入数据及/或作为反馈发送到另 一有限状态机引擎以用于更新用于有限状态机引擎的程序。

如上所述，由于有限状态机引擎处理输入数据流的一个位(或字)的时间，串行地级 联有限状态机引擎可增加通过所有有限状态机引擎完全处理所述输入数据流的时间。层 次的最低层级通常将接收最低(最细微的)层级的输入。因此，应预期较低层级比高层级 的输出更活跃。也就是说，层次中的每一连续层级可汇编较高层级对象。在一实例中， 有限状态机引擎具有限制可多快地将输入数据馈送到有限状态机引擎的最大输入速率。 可将此输入速率视为单个数据循环。在每一连续数据循环上，有限状态机引擎具有激活 许多最终状态的可能性。此可致使有限状态机引擎(尤其在层次的最低层级处)产生显著 量的输出(匹配)数据。举例来说，如果将输入作为字节流提供到最低层级有限状态机引 擎，那么在任一给定数据循环上，有限状态机引擎可产生多个字节的状态信息。如果一 个字节的信息可产生多个字节的状态信息，那么有限状态机引擎的整个层次应同步以使 得信息沿层次向上传递。然而，反馈无需同步，在较低层级处越快地接收反馈，所述较 低层级便可越快地调适且分析越高效。

作为一实例，层次(借助单个有限状态机引擎实施)的每一层级的最大大小输出可等 于1024个字节且层次的深度可等于4个层级。用于有限状态机引擎的输入数据流数据 速率可等于128MB/秒。在这些条件下，可在7.63微秒中横越层次的每一层级。在四层 级层次的情况下，有限状态机引擎的整个堆叠的总稳定时间将为7.63微秒的4倍或30.5 微秒。在30.5微秒的稳定时间的情况下，暗示输入数据频率应限于32KB/s。

值得注意地，此高度取决于有限状态机引擎的配置。有限状态机引擎可为可配置的 以对输入数据速率对状态机大小进行折衷。另外，如果对产生加载于有限状态机引擎上 的个别图像的编译器做出对应修改，那么可调整到所述有限状态机引擎的输入字大小。

在一实例中，可在具有冯·诺伊曼架构的机器上以软件来实施用以实施参考图1到 14所述的一个或一个以上FSM的方法。因此，软件指令可致使处理器对原始数据流实 施第一层级分析FSM。来自所述第一层级FSM的输出接着可由所述处理器根据第二层 级FSM来处理，等等。此外，上文所论述的反馈循环可由分析来自所述FSM的层级的 输出并使用所述输出来产生用于所述层级中的一者或一者以上的新FSM的处理器实施。

图15到18图解说明在本文中称作“FSM引擎800”的并行机的实例。在一实例中， FSM引擎800包含有限状态机的硬件实施方案。因此，FSM引擎800实施对应于FSM 中的多个状态的多个可选择性耦合的硬件元件(例如，可编程元件)。类似于FSM中的状 态，硬件元件可分析输入流并基于所述输入流而激活下游硬件元件。

FSM引擎800包括多个可编程元件，包括通用元件及专用元件。所述通用元件可经 编程以实施许多不同功能。这些通用元件包括以层次方式组织成行806(图16及17中所 展示)及块802(图15及16中所展示)的SME804、805(图18中所展示)。为了在以层次 方式组织的SME804、805之间路由信号，使用可编程开关的层次，其包括块间开关803 (图15及16中所展示)、块内开关808(图9及10中所展示)及行内开关812(图17中所 展示)。SME804、805可对应于FSM引擎800所实施的FSM的状态。可通过使用下文 所述的可编程开关将SME804、805耦合在一起。因此，可通过将SME804、805编程 为对应于状态的功能且通过选择性地将SME804、805耦合在一起以对应于FSM中的状 态之间的转变而在FSM引擎800上实施FSM。

图15图解说明实例性FSM引擎800的总体视图。FSM引擎800包括可选择性地与 可编程块间开关803耦合在一起的多个块802。另外，块802可选择性地耦合到输入块 809(例如，数据输入端口)以用于接收信号(例如，数据)并将数据提供到块802。块802 还可选择性地耦合到输出块813(例如，输出端口)以用于将信号从块802提供到外部装 置(例如，另一FSM引擎800)。FSM引擎800还可包括编程接口811以将程序(例如， 图像)加载到FSM引擎800上。所述图像可编程(例如，设定)SME804、805的状态。也 就是说，所述图像可将SME804、805配置为以某一方式对输入块809处的给定输入做 出反应。举例来说，SME804可经设定以当在输入块809处接收到字符‘a’时输出高信号。

在一实例中，可将输入块809、输出块813及/或编程接口811实施为寄存器以使得 向所述寄存器的写入将数据提供到相应元件或从所述相应元件提供数据。因此，可将来 自存储于对应于编程接口811的寄存器中的图像的位加载于SME804、805上。虽然图 15图解说明块802、输入块809、输出块813与块间开关803之间的某一数目个导体(例 如，导线、迹线)，但应理解在其它实例中可使用更少或更多导体。

图16图解说明块802的实例。块802可包括可选择性地与可编程块内开关808耦 合在一起的多个行806。另外，行806可借助块间开关803选择性地耦合到另一块802 内的另一行806。在一实例中，包括缓冲器801以控制去往/来自块间开关803的信号的 计时。行806包括组织成元件对(本文中称作两个一群组(GOT)810)的多个SME804、805。 在一实例中，块802包含十六(16)个行806。

图17图解说明行806的实例。GOT810可通过可编程行内开关812选择性地耦合 到行806内的其它GOT810及任何其它元件824。GOT810还可借助块内开关808耦合 到其它行806中的其它GOT810，或借助块间开关803耦合到其它块802中的其它GOT 810。在一实例中，GOT810具有第一输入814及第二输入816以及输出818。第一输入 814耦合到GOT810的第一SME804且第二输入816耦合到GOT810的第二SME805。

在一实例中，行806包括第一多个行互连导体820及第二多个行互连导体822。在 一实例中，GOT810的输入814、816可耦合到一个或一个以上行互连导体820、822， 且输出818可耦合到一个行互连导体820、822。在一实例中，第一多个行互连导体820 可耦合到行806内的每一GOT810的每一SME804。第二多个行互连导体822可耦合到 行806内的每一GOT810的一个SME804，但不可耦合到GOT804的另一SME805。 在一实例中，第二多个行互连导体822的第一半可耦合到行806内的SME804的第一半 (来自每一GOT810的一个SME804)且第二多个行互连导体822的第二半可耦合到行 806内的SME805的第二半(来自每一GOT810的另一SME804)。第二多个行互连导体 822与SME804、805之间的有限连接性在本文中称作“奇偶”。在一实例中，行806 还可包括专用元件824，例如计数器、可编程布尔逻辑元件、现场可编程门阵列(FPGA)、 专用集成电路(ASIC)、可编程处理器(例如，微处理器)及其它元件。

在一实例中，专用元件824包括计数器(在本文中也称作计数器824)。在一实例中， 计数器824包含12位可编程倒数计数器。12位可编程计数器824具有计数输入、复位 输入及零计数输出。计数输入在被断言时使计数器824的值递减1。复位输入在被断言 时致使计数器824从相关联寄存器加载初始值。对于12位计数器824来说，可加载多 达12位的数值作为所述初始值。当计数器824的值递减到零(0)时，断言零计数输出。 计数器824还具有至少两种模式：脉冲及保持。当将计数器824设定为脉冲模式时，在 计数器824递减到零时于时钟循环期间断言零计数输出，且在下一时钟循环处不再断言 零计数输出。当将计数器824设定为保持模式时，在计数器824递减到零时于时钟循环 期间断言零计数输出，且保持断言所述零计数输出直到计数器824由正断言的复位输入 复位为止。在一实例中，专用元件824包括布尔逻辑。在一些实例中，此布尔逻辑可用 以从FSM引擎800中的终端状态SME提取信息。所提取的信息可用以将状态信息传送 到其它FSM引擎800及/或传送用以重新编程FSM引擎800或重新编程另一FSM引擎 800的编程信息。

图18图解说明GOT810的实例。GOT810包括具有输入814、816且使其输出826、 828耦合到“或”门830及3对1多路复用器842的第一SME804及第二SME805。3 对1多路复用器842可经设定以将GOT810的输出818耦合到第一SME804、第二SME 805或“或”门830。“或”门830可用以将输出826、828两者耦合在一起以形成GOT 810的共用输出818。在一实例中，如上文所论述，第一SME804及第二SME805展现 出奇偶，其中第一SME804的输入814可耦合到行互连导体822中的一些行互连导体且 第二SME805的输入816可耦合到其它行互连导体822。在一实例中，可通过设定开关 840中的任一者或两者而使GOT810内的两个SME804、805级联及/或循环回到其自身。 可通过将SME804、805的输出826、828耦合到其它SME804、805的输入814、816 而使SME804、805级联。可通过将输出826、828耦合到其自己的输入814、816而使 SME804、805循环回到其自身。因此，第一SME804的输出826可不耦合到第一SME 804的输入814及第二SME805的输入816中的任一者、耦合到其中的一者或耦合到其 中的两者。

在一实例中，状态机元件804、805包含并行耦合到检测线834的多个存储器单元 832，例如通常用于动态随机存取存储器(DRAM)中的那些存储器单元。一个此种存储器 单元832包含可设定为一数据状态(例如对应于高值或低值(例如，1或0)的数据状态)的 存储器单元。存储器单元832的输出耦合到检测线834且到存储器单元832的输入基于 数据流线836上的数据而接收信号。在一实例中，数据流线836上的输入经解码以选择 存储器单元832中的一者。选定存储器单元832将其所存储的数据状态作为输出提供到 检测线834上。举例来说，可将在数据输入端口809处所接收的数据提供到解码器(未展 示)且所述解码器可选择数据流线836中的一者。在一实例中，所述解码器可将ACSII 字符转换成256个位中的1。

因此，当存储器单元832设定为高值且数据流线836上的数据对应于存储器单元832 时，存储器单元832将高信号输出到检测线834。当数据流线836上的数据对应于存储 器单元832且存储器单元832设定为低值时，存储器单元832将低信号输出到检测线834。 检测线834上来自存储器单元832的输出由检测电路838感测。在一实例中，输入线814、 816上的信号将相应检测电路838设定为活动或不活动状态。当设定为不活动状态时， 不管相应检测线834上的信号如何，检测电路838均在相应输出826、828上输出低信 号。当设定为活动状态时，检测电路838在从相应SME804、805的存储器单元834中 的一者检测到高信号时在相应输出线826、828上输出高信号。当处于活动状态中时， 检测电路838在来自相应SME804、805的所有存储器单元834的信号为低时在相应输 出线826、828上输出低信号。

在一实例中，SME804、805包括256个存储器单元832且每一存储器单元832耦 合到不同数据流线836。因此，SME804、805可经编程以在数据流线836中的选定一者 或一者以上在其上具有高信号时输出高信号。举例来说，SME804可将第一存储器单元 832(例如，位0)设定为高且将所有其它存储器单元832(例如，位1到255)设定为低。 当相应检测电路838处于活动状态中时，SME804在对应于位0的数据流线836在其上 具有高信号时在输出826上输出高信号。在其它实例中，SME804可经设定以通过将适 当存储器单元832设定为高值而在多个数据流线836中的一者在其上具有高信号时输出 高信号。

在一实例中，可通过从相关联寄存器读取位而将存储器单元832设定为高值或低值。 因此，可通过将编译器所创建的图像存储到寄存器中并将所述寄存器中的位加载到相关 联存储器单元832中来编程SME804。在一实例中，所述编译器所创建的图像包括高与 低(例如，1与0)位的二进制图像。所述图像可编程FSM引擎800以通过级联SME804、 805而作为FSM操作。举例来说，可通过将检测电路838设定为活动状态而将第一SME 804设定为活动状态。第一SME804可经设定以在对应于位0的数据流线836在其上具 有高信号时输出高信号。第二SME805最初可设定为不活动状态，但可经设定以在活动 时在对应于位1的数据流线836在其上具有高信号时输出高信号。可通过设定第一SME 804的输出826以耦合到第二SME805的输入816来级联第一SME804与第二SME805。 因此，当在对应于位0的数据流线836上感测到高信号时，第一SME804在输出826 上输出高信号且将第二SME805的检测电路838设定为活动状态。当在对应于位1的数 据流线836上感测到高信号时，第二SME805在输出828上输出高信号以激活另一SME 504、SME805或供从FSM引擎800输出。

图19图解说明用于编译器将源代码转换成经配置以编程并行机的图像的方法1000 的实例。方法1000包括将源代码剖析成语法树(框1002)，将所述语法树转换成自动机(框 1004)，优化所述自动机(框1006)，将所述自动机转换成网表(框1008)，将所述网表置于 硬件上(框1010)，路由所述网表(框1012)及公布所得图像(框1014)。

在一实例中，编译器包括允许软件开发者创建用于在FSM引擎800上实施FSM的 图像的应用程序编程接口(API)。编译器提供用以将源代码中的输入正则表达式集转换成 经配置以编程FSM引擎800的图像的方法。可通过用于具有冯·诺伊曼架构的计算机的 指令来实施所述编译器。这些指令可致使计算机上的处理器实施编译器的功能。举例来 说，所述指令在由处理器执行时可致使处理器对所述处理器可存取的源代码执行框 1002、1004、1006、1008、1010、1012及1014中所述的动作。图20中展示具有冯·诺 伊曼架构的实例性计算机且下文对其进行描述。

在一实例中，源代码描述用于识别符号群组内的符号型式的搜索串。为了描述搜索 串，源代码可包括多个正则表达式(regex)。正则表达式可为用于描述符号搜索型式的串。 正则表达式广泛地用于各种计算机领域中，例如程序设计语言、文本编辑器、网络安全 及其它领域。在一实例中，编译器所支持的正则表达式包括用于搜索未结构化数据的搜 索准则。未结构化数据可包括自由形式的数据且不具有应用于所述数据内的字的索引。 字可包括所述数据内的可打印及不可打印的字节的任一组合。在一实例中，编译器可支 持多种不同源代码语言以用于实施包括Perl(例如，Perl兼容正则表达式(PCRE))、PHP、 Java及.NET语言的正则表达式。

在框1002处，编译器可剖析源代码以形成关系连接的运算符的布置，其中不同类 型的运算符对应于源代码所实施的不同函数(例如，源代码中的正则表达式所实施的不同 函数)。剖析源代码可创建所述源代码的类属表示。在一实例中，所述类属表示包含源代 码中的正则表达式的经编码表示，其呈称作语法树的树形图的形式。本文所述的实例涉 及作为语法树(还称作“抽象语法树”)的布置，然而在其它实例中可使用具体语法树或 其它布置。

如上文所提及，由于编译器可支持源代码的多种语言，因此不管语言如何剖析均将 源代码转换成非语言特定表示(例如，语法树)。因此，不管源代码的语言如何，由编译 器进行的进一步处理(框1004、1006、1008、1010)均可从共用输入结构起作用。

如上所述，语法树包括关系连接的多个运算符。语法树可包括多种不同类型的运算 符。也就是说，不同运算符可对应于源代码中的正则表达式所实施的不同函数。

在框1004处，将语法树转换成自动机。自动机包含FSM的软件模型且可因此分类 为确定性或非确定性。确定性自动机在给定时间具有单个执行路径，而非确定性自动机 具有多个同时执行路径。所述自动机包含多个状态。为了将语法树转换成自动机，将语 法树中的运算符及运算符之间的关系转换成状态，其中所述状态之间具有转变。在一实 例中，可部分地基于FSM引擎800的硬件而转换所述自动机。

在一实例中，用于自动机的输入符号包括字母、数字0到9及其它可打印字符的符 号。在一实例中，输入符号由字节值0到255(包括0及255)表示。在一实例中，自动 机可表示为有向图，其中所述图的节点对应于状态集。在一实例中，输入符号α(也就是 说，δ(p，α)上从状态p到状态q的转变由从节点p到节点q的有向连接展示。在一实例 中，自动机的反转产生新的自动机，其中某一符号α上的每一转变p→q在同一符号上反 转q→p。在反转中，开始状态变为最终状态且最终状态变为开始状态。在一实例中，自 动机所接受(例如，匹配)的语言是当依序输入到所述自动机中时将到达最终状态的所有 可能字符串的集。所述自动机所接受的语言中的每一串追踪从开始状态到一个或一个以 上最终状态的路径。

在框1006处，在构造自动机之后，优化所述自动机以除其它之外还减小其复杂度 及大小。可通过组合冗余状态来优化所述自动机。

在框1008处，将经优化的自动机转换成网表。将所述自动机转换成网表将所述自 动机的每一状态映射到FSM引擎800上的硬件元件(例如，SME804、805、其它元件824) 并确定所述硬件元件之间的连接。

在框1010处，放置所述网表以选择目标装置的对应于所述网表的每一节点的特定 硬件元件(例如，SME804、805、专用元件824)。在一实例中，放置基于FSM引擎800 的一般输入及输出约束而选择每一特定硬件元件。

在框1012处，对所放置的网表进行路由以确定用于可编程开关(例如，块间开关803、 块内开关808及行内开关812)的设定，以便将选定硬件元件耦合在一起以实现网表所描 述的连接。在一实例中，通过确定FSM引擎800的将用以连接选定硬件元件及用于可 编程开关的设定的特定导体来确定用于可编程开关的设定。相比于框1010处的放置， 路由可能考虑硬件元件之间的连接的更特定限制。因此，假定有对FSM引擎800上的 导体的实际限制，路由可调整通过全域放置所确定的所述硬件元件中的一些硬件元件的 位置以便进行适当连接。

一旦网表经放置及路由，便可将所述经放置及路由的网表转换成用于编程FSM引 擎800的多个位。所述多个位在本文中称作图像。

在框1014处，编译器公布图像。所述图像包含用于编程FSM引擎800的特定硬件 元件及/或可编程开关的多个位。在其中所述图像包含多个位(例如，0及1)的实施例中， 所述图像可称作二进制图像。可将所述位加载到FSM引擎800上以编程SME804、805、 专用元件824及可编程开关的状态，以使得经编程FSM引擎800实施具有源代码所描 述的功能性的FSM。放置(框1010)及路由(框1012)可将FSM引擎800中的特定位置处 的特定硬件元件映射到自动机中的特定状态。因此，所述图像中的位可编程特定硬件元 件及/或可编程开关以实施所要功能。在一实例中，可通过将机器代码保存到计算机可读 媒体来公布所述图像。在另一实例中，可通过将所述图像显示于显示装置上来公布所述 图像。在又一实例中，可通过将图像发送到另一装置(例如用于将图像加载到FSM引擎 800上的编程装置)来公布所述图像。在又一实例中，可通过将图像加载到并行机(例如， FSM引擎800)上来公布所述图像。

在一实例中，可通过将来自图像的位值直接加载到SME804、805及其它硬件元件 824或通过将所述图像加载到一个或一个以上寄存器中且接着将来自所述寄存器的位值 写入到SME804、805及其它硬件元件824而将所述图像加载到FSM引擎800上。在一 实例中，可编程开关(例如，块间开关803、块内开关808及行内开关812)的状态。在一 实例中，FSM引擎800的硬件元件(例如，SME804、805、其它元件824、可编程开关 803、808、812)经存储器映射以使得编程装置及/或计算机可通过将所述图像写入到一个 或一个以上存储器地址而将所述图像加载到FSM引擎800上。

本文所述的方法实例可为至少部分地机器或计算机实施的。一些实例可包括用指令 编码的计算机可读媒体或机器可读媒体，所述指令可操作以配置电子装置以执行以上实 例中所述的方法。此些方法的实施方案可包括代码，例如微码、汇编语言代码、高级语 言代码等。此代码可包括用于执行各种方法的计算机可读指令。所述代码可形成计算机 程序产品的部分。此外，所述代码可在执行期间或在其它时间有形地存储于一个或一个 以上易失性或非易失性计算机可读媒体上。这些计算机可读媒体可包括(但不限于)硬盘、 可装卸磁盘、可装卸光盘(例如，压缩光盘及数字视频光盘)、盒式磁带、存储卡或存储 棒、随机存取存储器(RAM)、只读存储器(ROM)等。

图20大体图解说明具有冯·诺伊曼架构的计算机1500的实例。在阅读并理解本发明 的内容后，所属领域的技术人员将即刻理解可从基于计算机的系统中的计算机可读媒体 激活软件程序以执行所述软件程序中所界定的功能的方式。所属领域的技术人员将进一 步理解可用来创建经设计以实施及执行本文所揭示的方法的一个或一个以上软件程序 的各种程序设计语言。可使用面向对象的语言(例如Java、C++或一种或一种以上其它语 言)以面向对象的格式来结构化程序。或者，可使用程序语言(例如汇编、C等)以面向程 序的格式来结构化程序。软件组件可使用所属领域的技术人员众所周知的若干种机制(例 如应用程序接口或进程间通信技术，包括远程程序呼叫或其它)中的任一者进行通信。各 种实施例的教示不限于任一特定程序设计语言或环境。

因此，可实现其它实施例。举例来说，制品(例如计算机、存储器系统、磁盘或光盘、 某一其它存储装置或任一类型的电子装置或系统)可包括耦合到其上存储有指令1524 (例如，计算机程序指令)的计算机可读媒体1522(例如存储器(例如，可装卸存储媒体以 及包括电、光学或电磁导体的任一存储器))的一个或一个以上处理器1502，所述指令在 由一个或一个以上处理器1502执行时导致执行关于以上方法所述的动作中的任一者。

计算机1500可采取具有直接及/或使用总线1508耦合到若干个组件的处理器1502 的计算机系统的形式。此些组件可包括主存储器1504、静态或非易失性存储器1506及 大容量存储装置1516。耦合到处理器1502的其它组件可包括输出装置1510(例如视频 显示器)、输入装置1512(例如键盘)及光标控制装置1514(例如鼠标)。用以将处理器1502 及其它组件耦合到网络1526的网络接口装置1520还可耦合到总线1508。可利用若干个 众所周知的传送协议(例如，HTTP)中的任一者经由网络接口装置1520在网络1526上进 一步传输或接收指令1524。耦合到总线1508的这些元件中的任一者可取决于待实现的 特定实施例而不存在、单独存在或以复数数目存在。

在一实例中，处理器1502、存储器1504、1506或存储装置1516中的一者或一者以 上可各自包括在执行时可致使计算机1500执行本文所述的方法中的任何一者或一者以 上的指令1524。在替代实施例中，计算机1500作为独立装置操作或可连接(例如，连网) 到其它装置。在连网环境中，计算机1500可在服务器-客户端网络环境中以服务器或客 户端装置的资格或在对等(或分布式)网络环境中作为对等装置操作。计算机1500可包括 个人计算机(PC)、平板PC、机顶盒(STB)、个人数字助理(PDA)、蜂窝式电话、网络器 具、网络路由器、交换机或桥接器或能够执行指定待由所述装置采取的动作的指令集(顺 序或以其它方式)的任一装置。此外，尽管仅图解说明单个计算机1500，但术语“计算 机”还应视为包括个别或共同地执行一指令集(或多个指令集)以执行本文所论述的方法 中的任何一者或一者以上的任一装置集合。

计算机1500还可包括输出控制器1528以用于使用一个或一个以上通信协议(例如， 通用串行总线(USB)、IEEE1394等)与外围装置通信。输出控制器1528可(例如)将图像 提供到以通信方式耦合到计算机1500的编程装置1530。编程装置1530可经配置以编程 并行机(例如，并行机100、FSM引擎800)。在其它实例中，编程装置1530可与计算机 1500集成在一起并耦合到总线1508或可经由网络接口装置1520或另一装置与计算机 1500通信。

尽管将计算机可读媒体1524展示为单个媒体，但术语“计算机可读媒体”应视为 包括存储一个或一个以上指令集1524的单个媒体或多个媒体(例如，集中式或分布式数 据库，或相关联高速缓冲存储器及服务器，及/或各种存储媒体，例如处理器1502寄存 器、存储器1504、1506及存储装置1516)。术语“计算机可读媒体”还应视为包括能够 存储、编码或载运指令集以供所述计算机执行且致使所述计算机执行本发明的方法中的 任何一者或一者以上或能够存储、编码或载运此指令集所利用或与此指令集相关联的数 据结构的任一媒体。术语“计算机可读媒体”因此应视为包括(但不限于)有形媒体(例如 固态存储器)、光学媒体及磁性媒体。

提供发明摘要以符合37C.F.R.第1.72(b)款，其需要将允许读者探知所述技术揭示内 容的本质及主旨的摘要。提交本摘要基于以下理解：其并非将用以限制或解释权利要求 书的范围或含义。特此将所附权利要求书并入到详细描述中，其中每一权利要求自身作 为单独实施例。

实例性实施例

实例1包括一种可编程装置，其具有多个可编程元件，其中所述可编程元件经配置 以实施一个或一个以上有限状态机，其中所述多个可编程元件经配置以接收N数字输入 且依据所述N数字输入提供M数字输出，其中所述M数字输出包括来自少于所有所述 可编程元件的状态信息。

实例2包括一种层次并行机，其具有：第一并行机，其包含多个可编程元件，其中 所述可编程元件经配置以实施一个或一个以上有限状态机，其中所述多个可编程元件经 配置以接收N数字输入且依据所述N数字输入提供M数字输出，其中所述M数字输出 包括来自少于所有所述可编程元件的状态信息；及第二并行机，其经配置以接收并处理 所述M数字输出的至少一部分。

实例3包括一种可编程装置，其具有多个可编程元件，其中所述可编程元件经配置 以实施一个或一个以上有限状态机，其中所述多个可编程元件经配置以接收N数字输入 且依据所述N数字输入提供M数字输出，其中所述M数字输出是通过压缩来自所述可 编程元件中的每一者的状态信息而形成。

实例4包括一种层次并行机，其具有：第一并行机，其包含多个可编程元件，其中 所述可编程元件经配置以实施一个或一个以上有限状态机，其中所述多个可编程元件经 配置以接收N数字输入且依据所述N数字输入提供M数字输出，其中所述M数字输出 是通过压缩来自所述可编程元件中的每一者的状态信息而形成。

实例5包括一种将状态信息从并行机提供到另一装置的方法，其中所述并行机包括 多个可编程元件，其中所述可编程元件中的每一者经配置以具有对应状态。所述方法包 括：确定状态信息，其中所述状态信息包含所述并行机中的所述可编程元件中的每一者 的状态；压缩所述状态信息；及将所述经压缩状态信息提供到所述另一装置。

实例6包括一种层次并行机，其具有具有至少一个N数字输入及多个N数字输出 的第一层级并行机，其中所述N数字输出中的每一者对应于在所述第一层级并行机上所 实施的N个状态机的相应群组。

实例7包括一种包含经配置以实施至少一个有限状态机的多个可编程元件的并行 机。所述并行机经配置以：确定状态信息，其中所述状态信息包含所述可编程元件中的 每一者的状态；压缩所述状态信息；及将所述经压缩状态信息提供到另一装置。

在实例8中，实例1到7中的任一者的标的物可任选地包括其中所述多个可编程元 件包含两个或两个以上可编程元件群组中的一者。

在实例9中，实例1到8的任一者的标的物可任选地包括：N数字输入接口，其耦 合到所述一个可编程元件群组且经配置以接收所述N数字输入；及M数字输出接口， 其耦合到所述一个可编程元件群组且经配置以提供所述M数字输出。

在实例10中，实例1到9中的任一者的标的物可任选地包括其中所述一个可编程 元件群组包含可编程元件块。

在实例11中，实例1到10中的任一者的标的物可任选地包括其中所述可编程元件 块包含多个可编程元件行，其中所述行中的每一者耦合到多个块内开关中的相应一者。

在实例12中，实例1到11中的任一者的标的物可任选地包括其中所述行中的每一 者中的可编程元件包含：两个状态机元件的多个群组；及另一可编程元件。

在实例13中，实例1到12中的任一者的标的物可任选地包括：可编程开关，其经 配置以选择性地将所述一个可编程元件群组耦合到所述可编程元件群组中的另一者；输 入端口；及/或输出端口。

在实例14中，实例1到13中的任一者的标的物可任选地包括寄存器，所述寄存器 经配置以存储经配置以编程所述多个可编程元件及所述多个可编程开关的程序。

在实例15中，实例1到14中的任一者的标的物可任选地包括其中N等于M。

在实例16中，实例1到15中的任一者的标的物可任选地包括其中M为N的整数 倍数。

在实例17中，实例1到16中的任一者的标的物可任选地包括“或”逻辑，所述“或” 逻辑经配置以聚合来自所述可编程元件中的用以实施所述有限状态机中的同一者的两 者或两者以上的输出。

在实例18中，实例1到17中的任一者的标的物可任选地包括其中所述可编程元件 经配置以实施N个状态机的逻辑群组，其中所述N个状态机的所述输出经聚合以提供 所述M数字输出。

在实例19中，实例1到▲中的任一者的标的物可任选地包括其中所述逻辑包含“或” 门。

在实例20中，实例1到19中的任一者的标的物可任选地包括其中所述M数字输出 中所包括的所述状态信息包含经压缩状态信息。

在实例21中，实例1到20中的任一者的标的物可任选地包括其中所述多个可编程 元件包含状态机元件。

在实例22中，实例1到21中的任一者的标的物可任选地包括其中所述M数字输出 包含差向量。

在实例23中，实例1到22中的任一者的标的物可任选地包括其中所述所实施的一 个或一个以上有限状态机中的每一状态对应于状态向量中的相应数字，且其中所述差向 量仅包括所述状态向量中的响应于提供到所述可编程装置的输入符号而改变的那些数 字。

在实例24中，实例1到23中的任一者的标的物可任选地包括其中所述所实施的一 个或一个以上有限状态机中的每一状态对应于状态向量中的相应数字，且其中所述M数 字输出仅包含所述状态向量中的所述数字的子集。

在实例25中，实例1到24中的任一者的标的物可任选地包括其中所述数字的所述 子集包含对应于所述一个或一个以上有限状态机中的最终状态的那些数字。

在实例26中，实例1到25中的任一者的标的物可任选地包括其中在所述装置中所 实施的所有状态机接收所述N数字输入。

在实例27中，实例1到26中的任一者的标的物可任选地包括其中所述多个可编程 元件包含两个或两个以上可编程元件群组中的一者，其中所述群组中的每一者具有其自 己的专用输入。

在实例28中，实例1到27中的任一者的标的物可任选地包括其中所述N数字输入 在半导体裸片的底部上，且其中所述M数字输出在所述半导体裸片的顶部上。

在实例29中，实例1到28中的任一者的标的物可任选地包括其中所述多个可编程 元件包含两个或两个以上可编程元件群组中的一者，且其中所述可编程装置经配置以将 状态信息从所述群组中的一者提供到所述可编程装置中的所述群组中的另一者。

在实例30中，实例1到29中的任一者的标的物可任选地包括其中所述第二并行机 经配置以接收并处理所述整个M数字输出。

在实例31中，实例1到30中的任一者的标的物可任选地包括：输入总线，其耦合 到所述第一并行机且经配置以提供所述N数字输入；及输出总线，其耦合于所述第一并 行机与所述第二并行机之间，所述输出总线经配置以将所述M数字输出的至少一部分提 供到所述第二并行机。

在实例32中，实例1到31中的任一者的标的物可任选地包括其中所述输入总线与 输出总线在大小上相等。

在实例33中，实例1到32中的任一者的标的物可任选地包括其中所述第一及第二 并行机中的所述对应群组由相应互连件群组耦合。

在实例34中，实例1到33中的任一者的标的物可任选地包括所述M数字输出被提 供到在所述第二并行机中所实施的每一状态机。

在实例35中，实例1到34中的任一者的标的物可任选地包括其中所述第二并行机 包含分组成多个群组的多个可编程元件，其中所述M数字输出是根据预定义方式提供到 所述群组中的相应一者。

在实例36中，实例1到35中的任一者的标的物可任选地包括其中所述第二并行机 包含经配置以将地址信息发送到所述第二并行机的多个可编程元件，其中所述地址信息 指示正将所述M数字输出提供到所述第二并行机中的所述群组中的哪一者。

在实例37中，实例1到36中的任一者的标的物可任选地包括其中所述并行机为堆 叠的。

在实例38中，实例1到37中的任一者的标的物可任选地包括其中所述多个可编程 元件包含两个或两个以上可编程元件群组中的一者，其进一步包含对应于每一群组的逻 辑，其中对应于所述群组中的相应一者的所述逻辑聚合来自所述群组中的两个或两个以 上可编程元件的状态信息，且其中来自所述群组的所述M数字输出的一个或一个以上数 字为此逻辑的函数。

在实例39中，实例1到38中的任一者的标的物可任选地包括其中所述M数字输出 是通过压缩来自所述可编程元件的状态信息而形成。

在实例40中，实例1到39中的任一者的标的物可任选地包括逻辑，所述逻辑经配 置以聚合来自所述可编程元件中的用以实施所述有限状态机中的同一者的两者或两者 以上的输出。

在实例41中，实例1到40中的任一者的标的物可任选地包括其中所述可编程元件 经配置以实施N个状态机的逻辑群组，其中所述N个状态机的所述输出经聚合以提供 所述M数字输出。

在实例42中，实例1到41中的任一者的标的物可任选地包括其中压缩所述状态信 息包括对所述状态信息应用无损压缩算法。

在实例43中，实例1到42中的任一者的标的物可任选地包括其中将所述经压缩状 态信息提供到所述另一装置包含将所述经压缩状态信息提供到另一并行机。

在实例44中，实例1到43中的任一者的标的物可任选地包括其中将所述经压缩状 态信息提供到所述另一装置包含将所述经压缩状态信息提供到系统存储器。

在实例45中，实例1到44中的任一者的标的物可任选地包括其中压缩所述状态信 息包含聚合在所述并行机上所实施的有限状态机中的最终状态。

在实例46中，实例1到45中的任一者的标的物可任选地包括第一层级并行机，其 具有至少一个N数字输入及多个N数字输出，其中所述N数字输出中的每一者对应于 在所述第一层级并行机上所实施的N个状态机的相应群组。

在实例47中，实例1到46中的任一者的标的物可任选地包括其中在所述第一层级 并行机上所实施的所述状态机中的至少一者包括对应于所述至少一个状态机的多个最 终状态的多个可编程元件，其中将对应于所述多个最终状态的所述多个可编程元件的输 出聚合在一起以提供所述N数字输出中的一者的一个数字。

在实例48中，实例1到47中的任一者的标的物可任选地包括其中在所述N数字输 出中的一者上提供的数据编码在所述第一层级并行机上所实施的N个状态机的所述相 应群组的所述最终状态的状况。

在实例49中，实例1到48中的任一者的标的物可任选地包括其中所述第一层级并 行机包含有限状态机引擎。

在实例50中，实例1到49中的任一者的标的物可任选地包括其中所述有限状态机 引擎包含可编程元件群组阵列，且其中所述可编程元件群组中的每一者耦合到所述N数 字输出中的相应一者。

在实例51中，实例1到50中的任一者的标的物可任选地包括其中所述第一层级并 行机具有多个N数字输入且其中所述可编程元件群组中的每一者耦合到所述第一层级 并行机的所述N数字输入中的相应一者。

在实例52中，实例1到51中的任一者的标的物可任选地包括其中所述第二层级并 行机包含有限状态机引擎。

在实例53中，实例1到52中的任一者的标的物可任选地包括其中所述有限状态机 引擎包含可编程元件群组阵列，且其中所述可编程元件群组中的每一者耦合到所述N数 字输入中的相应一者。

在实例54中，实例1到53中的任一者的标的物可任选地包括其中所述第二层级并 行机具有多个N数字输出且其中所述可编程元件群组中的每一者耦合到所述第二层级 并行机的所述N数字输出中的相应一者。

在实例55中，实例1到54中的任一者的标的物可任选地包括其中所述第一并行机 包含第一裸片，且所述第二并行机包含与所述第一裸片堆叠在一起的第二裸片。

在实例56中，实例1到55中的任一者的标的物可任选地包括进一步包含第三并行 机及总线，其中所述第三并行机包含与所述第一裸片及所述第二裸片堆叠在一起的第三 裸片，其中所述第二裸片在所述堆叠中的所述第一裸片与所述第三裸片之间，且其中所 述总线经配置以在所述第一并行机与所述第三并行机之间传送状态信息。

在实例57中，实例1到56中的任一者的标的物可任选地包括其中所述总线包含多 个互连件。

在实例58中，实例1到57中的任一者的标的物可任选地包括其中所述互连件包含 穿通孔互连件。

在实例59中，实例1到58中的任一者的标的物可任选地包括其中所述并行机包含 有限状态机引擎。

在实例60中，实例1到59中的任一者的标的物可任选地包括其中所述有限状态机 引擎包含型式辨识处理器。

在实例61中，实例1到60中的任一者的标的物可任选地包括其中所述并行机包含 现场可编程门阵列。

在实例62中，实例1到61中的任一者的标的物可任选地包括其中所述第一层级并 行机的所述至少一个N数字输入经配置以接收原始数据。

在实例63中，实例1到62中的任一者的标的物可任选地包括其中所述第二层级并 行机的所述N数字输入中的每一者对应于在所述第二层级并行机上所实施的N个状态 机的相应群组，其中在所述第二层级并行机上所实施的N个状态机的每一群组由在所述 第一层级并行机上所实施的多达N个状态机驱动。

在实例64中，实例1到63中的任一者的标的物可任选地包括其中另一装置包含第 二并行机，其中所述第二并行机经配置以接收并处理所述经压缩状态信息。

在实例65中，实例1到64中的任一者的标的物可任选地包括其中所述并行机经配 置以压缩所述状态信息包含所述并行机经配置以聚合在所述并行机上所实施的有限状 态机的最终状态。

在实例66中，实例1到65中的任一者的标的物可任选地包括经配置以聚合所述最 终状态的布尔逻辑。

在实例67中，实例1到66中的任一者的标的物可任选地包括其中所述并行机经配 置以压缩所述状态信息包含所述并行机经配置以输出差向量，其中所述差向量仅识别已 响应于输入符号而改变的那些状态。

在实例68中，实例1到67中的任一者的标的物可任选地包括其中所述并行机经配 置以压缩所述状态信息包含所述并行机经配置以输出输出向量，其中所述输出向量仅提 供在所述并行机上所实施的有限状态机中的最终状态的状态信息。