公开(公告)号：US20090307175A1

公开(公告)日：2009-12-10

申请号：US12136386

申请日：2008-06-10

申请人： Iorio Francesco ,  Jan Van Lunteren

发明人： Iorio Francesco ,  Jan Van Lunteren

IPC分类号： G06N5/02

CPC分类号： G06F9/4498

摘要： A method, system and computer program product for performing pattern matching in parallel for a plurality of input streams. The method includes calculating a memory address in a translation table responsive to a current input value, a current state and current state information. A transition rule is retrieved from the transition rule table at the memory address, the transition rule including a test input value, a test current state, and next state information. It is determined if the current input value and the current state match the test input value and the test current state. The current state information is updated with the next state information in response to determining that the current input value and the current state match the test input value and the test current state. The current state information is updated with contents of a default transition rule in response to determining that the current input value and the current state do not match the test input value and the test current state.

摘要翻译： 一种用于对多个输入流并行执行模式匹配的方法，系统和计算机程序产品。 该方法包括响应于当前输入值，当前状态和当前状态信息来计算翻译表中的存储器地址。 从存储器地址的转移规则表中检索转移规则，转换规则包括测试输入值，测试当前状态和下一状态信息。 确定当前输入值和当前状态是否与测试输入值和测试当前状态相匹配。 响应于确定当前输入值和当前状态与测试输入值和测试当前状态匹配，当前状态信息被更新为具有下一状态信息。 响应于确定当前输入值和当前状态与测试输入值和测试当前状态不匹配，当前状态信息被更新为默认转换规则的内容。

公开(公告)号：US08645620B2

公开(公告)日：2014-02-04

申请号：US12143889

申请日：2008-06-23

申请人： Peter Buchmann ,  Martin Leo Schmatz ,  Jan Van Lunteren

发明人： Peter Buchmann ,  Martin Leo Schmatz ,  Jan Van Lunteren

IPC分类号： G06F12/00

CPC分类号： G06F12/02 ,  G06F12/0223 ,  G11C15/00

摘要： An interfacing apparatus and related method is provided for configuring to couple a plurality of memory devices being addressable by means of an address space to a processing unit. In one embodiment, the apparatus comprises a first memory access unit being adapted for receiving a memory address from said processing unit and for accessing said memory devices accordingly based on the address provided. It also comprises a second memory access unit being adapted for receiving content data from the processing unit and for controlling a search or update function accordingly for the received content data in one or more of the memory devices. In addition, an allocation unit is also provided for allocating a first part of the address space of the memory devices to said first memory access unit and allocating a second part of the address space of said memory devices to the second memory access unit, each of the memory access units being assigned to corresponding memory devices of the plurality of memory devices.

摘要翻译： 提供了一种接口装置和相关方法，用于将通过地址空间寻址的多个存储器件耦合到处理单元。 在一个实施例中，该装置包括第一存储器存取单元，其适于从所述处理单元接收存储器地址，并根据所提供的地址相应地访问所述存储器件。 它还包括第二存储器存取单元，其适于从处理单元接收内容数据，并用于相应地控制一个或多个存储器件中的所接收的内容数据的搜索或更新功能。 此外，还提供分配单元，用于将存储器件的地址空间的第一部分分配给所述第一存储器存取单元，并将所述存储器件的地址空间的第二部分分配给第二存储器存取单元， 所述存储器访问单元被分配给所述多个存储器件的相应的存储器件。

公开(公告)号：US08635180B2

公开(公告)日：2014-01-21

申请号：US13021757

申请日：2011-02-06

申请人： Giora Biran ,  Christoph Hagleitner ,  Timothy Hume Heil ,  Jan Van Lunteren

发明人： Giora Biran ,  Christoph Hagleitner ,  Timothy Hume Heil ,  Jan Van Lunteren

IPC分类号： G06N5/04

CPC分类号： G06N5/047 ,  G06N5/025

摘要： A pattern matching accelerator (PMA) for assisting software threads to find the presence and location of strings in an input data stream that match a given pattern. The patterns are defined using regular expressions that are compiled into a data structure comprised of rules subsequently processed by the PMA. The patterns to be searched in the input stream are defined by the user as a set of regular expressions. The patterns to be searched are grouped in pattern context sets. The sets of regular expressions which define the pattern context sets are compiled to generate a rules structure used by the PMA hardware. The rules are compiled before search run time and stored in main memory, in rule cache memory within the PMA or a combination thereof. For each input character, the PMA executes the search and returns the search results.

摘要翻译： 模式匹配加速器（PMA），用于帮助软件线程查找匹配给定模式的输入数据流中字符串的存在和位置。 使用正则表达式定义模式，该正则表达式被编译成由PMA随后处理的规则组成的数据结构。 在输入流中要搜索的模式由用户定义为一组正则表达式。 要搜索的模式分组在模式上下文集中。 定义模式上下文集的正则表达式集合被编译为生成由PMA硬件使用的规则结构。 该规则在搜索运行时间之前被编译并存储在主存储器中，在PMA内的规则高速缓冲存储器中或其组合中。 对于每个输入字符，PMA执行搜索并返回搜索结果。

公开(公告)号：US08620968B2

公开(公告)日：2013-12-31

申请号：US13571431

申请日：2012-08-10

申请人： Kubilay Atasu ,  Florian Doerfler ,  Christoph Hagleitner ,  Jan Van Lunteren

发明人： Kubilay Atasu ,  Florian Doerfler ,  Christoph Hagleitner ,  Jan Van Lunteren

IPC分类号： G06F17/30

CPC分类号： G06F17/30985

摘要： A computer program product comprising a computer readable storage medium containing computer code that, when executed by a computer, implements a method for transforming a finite state automaton (FSA) of a regular expression, wherein the method includes determining, by a computer, a first subexpression R1 and a second subexpression R2 in the regular expression; calculating an overlap FSA, the overlap FSA configured to determine the existence of a partial overlap or a full overlap between the first subexpression R1 and the second subexpression R2; determining whether the overlap FSA has an accepting state; and in the event the overlap FSA is determined not to have an accepting state, determining that the transformation of the regular expression is safe, and constructing a transformed FSA of the regular expression comprising a first FSA for the first subexpression R1 and a second FSA for the second subexpression R2.

摘要翻译： 一种计算机程序产品，包括包含计算机代码的计算机可读存储介质，所述计算机代码当由计算机执行时实现用于转换正则表达式的有限状态自动机（FSA）的方法，其中所述方法包括由计算机确定第一 正则表达式中的子表达式R1和第二子表达式R2; 计算重叠FSA，配置为确定第一子表达式R1和第二子表达式R2之间的部分重叠或全部重叠的存在的重叠FSA; 确定重叠FSA是否具有接受状态; 并且在重叠FSA被确定为不具有接受状态的情况下，确定正则表达式的变换是安全的，并且构建包括用于第一子表达式R1的第一FSA和第二FSA的正则表达式的变换FSA， 第二个子表达式R2。

公开(公告)号：US08402003B2

公开(公告)日：2013-03-19

申请号：US13022904

申请日：2011-02-08

申请人： Giora Biran ,  Christoph Hagleitner ,  Timothy H. Heil ,  Jan Van Lunteren

发明人： Giora Biran ,  Christoph Hagleitner ,  Timothy H. Heil ,  Jan Van Lunteren

IPC分类号： G06F17/30

CPC分类号： G06F17/30985

摘要： A pattern matching accelerator (PMA) for assisting software threads to find the presence and location of strings in an input data stream that match a given pattern. The patterns are defined using regular expressions that are compiled into a data structure comprised of rules subsequently processed by the PMA. The patterns to be searched in the input stream are defined by the user as a set of regular expressions. The patterns to be searched are grouped in pattern context sets. The sets of regular expressions which define the pattern context sets are compiled to generate a rules structure used by the PMA hardware. The rules are compiled before search run time and stored in main memory, in rule cache memory within the PMA or a combination thereof. For each input character, the PMA executes the search and returns the search results.

摘要翻译： 模式匹配加速器（PMA），用于帮助软件线程查找匹配给定模式的输入数据流中字符串的存在和位置。 使用正则表达式定义模式，该正则表达式被编译成由PMA随后处理的规则组成的数据结构。 在输入流中要搜索的模式由用户定义为一组正则表达式。 要搜索的模式分组在模式上下文集中。 编译定义模式上下文集的正则表达式集合，以生成PMA硬件使用的规则结构。 该规则在搜索运行时间之前被编译并存储在主存储器中，在PMA内的规则高速缓冲存储器中或其组合中。 对于每个输入字符，PMA执行搜索并返回搜索结果。

公开(公告)号：US08176413B2

公开(公告)日：2012-05-08

申请号：US12059913

申请日：2008-03-31

申请人： Glenn A. Marcy ,  Jan Van Lunteren ,  Marcel Waldvogel

发明人： Glenn A. Marcy ,  Jan Van Lunteren ,  Marcel Waldvogel

IPC分类号： G06F17/27 ,  G06F11/00

CPC分类号： G06F17/2247 ,  G06F17/2725

摘要： A data processing method comprises receiving an electronically parseable document, scanning the document according to at least one predefined rule to determine if the document is suspicious, and, if the document is determined not to be suspicious, parsing the document with a first parser, and, if the document is determined to be suspicious, parsing the document with a second parser.

摘要翻译： 数据处理方法包括接收电子可解析文档，根据至少一个预定义规则扫描文档以确定文档是否可疑，以及如果文档被确定为不可疑，则用第一解析器解析文档，以及 如果文档被确定为可疑，则使用第二个解析器解析文档。

公开(公告)号：US07844422B2

公开(公告)日：2010-11-30

申请号：US11740558

申请日：2007-04-26

申请人： Rolf Fritz ,  Markus Kaltenbach ,  Ulrich Mayer ,  Thomas Pflueger ,  Cordt Starke ,  Jan Van Lunteren

发明人： Rolf Fritz ,  Markus Kaltenbach ,  Ulrich Mayer ,  Thomas Pflueger ,  Cordt Starke ,  Jan Van Lunteren

IPC分类号： G06F17/10

CPC分类号： G06F17/2247

摘要： The invention relates to a method of optimizing a state transition function specification for a state machine engine based on a probability distribution for the state transitions. For the preferred embodiment of the invention, a B-FSM state machine engine accesses a transition rule memory using a processor cache. The invention allows improving the cache hit rate by exploiting the probability distribution. The N transition rules that comprise a hash table entry will be loaded in a burst mode from the main memory, from which the N transition rules are transferred to the processor cache. Because the comparison of the actual state and input values against each of the transition rules can immediately start after each of these rules has been received, the overall performance is improved as the transition rule that is most likely to be selected is the first to be transferred as part of the burst access.

摘要翻译： 本发明涉及一种基于状态转换的概率分布优化状态机引擎的状态转换功能规范的方法。 对于本发明的优选实施例，B-FSM状态机引擎使用处理器高速缓存来访问转换规则存储器。 本发明允许通过利用概率分布来提高缓存命中率。 构成哈希表条目的N个转换规则将以从主存储器的突发模式加载，N个转换规则从该存储器传送到处理器高速缓存。 因为实际状态和输入值与每个转换规则的比较可以在接收到每个这些规则之后立即开始，因为最有可能选择的转换规则是首先被转移的整体性能得到改善 作为突发访问的一部分。

公开(公告)号：US07508985B2

公开(公告)日：2009-03-24

申请号：US10970798

申请日：2004-10-21

申请人： Jan Van Lunteren

发明人： Jan Van Lunteren

IPC分类号： G06K9/00 ,  G06F17/30

CPC分类号： G06F17/30985 ,  Y10S707/99936

摘要： An XML parsing system includes a pattern-matching system 1 that receives an input stream 2 of characters corresponding to the XML document to be parsed, and provides an output 3 for subsequent processing in software by a processor 4. The pattern matching system 1 includes two main components, a controller in the form of a programmable state machine 5, which is programmed with an appropriate state transition diagram 6, and a character processing unit 7 in the form of a token and character handler. The programmable state machine 5 controls the character processing unit 7 to, e.g., compare characters in the input character stream 2 with other received or stored characters. The character processing unit 7 then provides feedback to the programmable state machine controller 5, e.g., as to whether the compared characters match, so that the programmable state machine controller 5 can then parse the received document accordingly.

摘要翻译： XML解析系统包括模式匹配系统1，其接收与要解析的XML文档相对应的字符的输入流2，并且通过处理器4提供用于后续处理的输出3。模式匹配系统1包括两个 主要组件，以可编程状态机5的形式的控制器，其由适当的状态转换图6编程，以及以令牌和字符处理器的形式的字符处理单元7。 可编程状态机5控制字符处理单元7，例如将输入字符流2中的字符与其他接收或存储的字符进行比较。 字符处理单元7然后向可编程状态机控制器5提供例如关于所比较的字符是否匹配的反馈，使得可编程状态机控制器5然后可以相应地解析所接收的文档。

公开(公告)号：US07193997B2

公开(公告)日：2007-03-20

申请号：US10090592

申请日：2002-02-28

申请人： Jan Van Lunteren ,  Antonius Engbersen

发明人： Jan Van Lunteren ,  Antonius Engbersen

IPC分类号： H04L12/28

CPC分类号： H04L47/10 ,  H04L29/06 ,  H04L45/742 ,  H04L45/7453 ,  H04L47/20 ,  H04L69/22

摘要： Methods and apparatus are provided for classifying data packets in data processing systems. A first packet classification method determines which of a plurality of predefined processing rules applies to a data packet, where each rule is associated with a range of possible data values in each of a plurality of dimensions (X,Y) corresponding to respective data items in the packet format. For each dimension (X,Y), it is determined which of a set of predefined basic ranges contains the corresponding data value (I1, I2) from the packet, where the basic ranges correspond to respective non-overlapping value ranges between successive rule range boundaries in the dimension. For the basic range so determined for each dimension, a corresponding basic range identifier is selected from a set of predefined basic range identifiers corresponding to respective basic ranges in that dimension. For each of at least two dimensions (X,Y), the basic range identifiers comprise respective pD-bit strings generated independently for that dimension by a process of deriving a primitive range hierarchy based on the rule ranges in that dimension. The resulting basic range identifiers, one for each dimension, are then combined to produce a search key which is supplied to a ternary content-addressable memory (5). In the memory (5), the search key is compared with a set of ternary rule vectors, each associated with a particular rule and derived for that rule from the aforementioned hierarchies, to identify at least one rule which applies to the data packet. A second method classifies data packets according to the values in respective data packets of a single, predetermined data item (DA) in the data packet format, where a plurality of classification results are predefined for respective ranges of values of the data item (DA). Here the data item (DA) in the packet is first segmented. The resulting segments are then equated to different dimensions (X,Y) of a multidimensional packet classification problem and are processed in a similar manner to identify a classification result for the packet.

公开(公告)号：US20050132342A1

公开(公告)日：2005-06-16

申请号：US10970798

申请日：2004-10-21

申请人： Jan Van Lunteren

发明人： Jan Van Lunteren

IPC分类号： G06F9/45 ,  G06F17/30

CPC分类号： G06F17/30985 ,  Y10S707/99936

摘要： An XML parsing system includes a pattern-matching system 1 that receives an input stream 2 of characters corresponding to the XML document to be parsed, and provides an output 3 for subsequent processing in software by a processor 4. The pattern matching system 1 includes two main components, a controller in the form of a programmable state machine 5, which is programmed with an appropriate state transition diagram 6, and a character processing unit 7 in the form of a token and character handler. The programmable state machine 5 controls the character processing unit 7 to, e.g., compare characters in the input character stream 2 with other received or stored characters. The character processing unit 7 then provides feedback to the programmable state machine controller 5, e.g., as to whether the compared characters match, so that the programmable state machine controller 5 can then parse the received document accordingly.

摘要翻译： XML解析系统包括模式匹配系统1，其接收与要解析的XML文档相对应的字符的输入流2，并且通过处理器4提供用于后续处理的输出3。模式匹配系统1包括两个 主要组件，以可编程状态机5的形式的控制器，其由适当的状态转换图6编程，以及以令牌和字符处理器的形式的字符处理单元7。 可编程状态机5控制字符处理单元7，例如将输入字符流2中的字符与其他接收或存储的字符进行比较。 字符处理单元7然后向可编程状态机控制器5提供例如关于所比较的字符是否匹配的反馈，使得可编程状态机控制器5然后可以相应地解析所接收的文档。