SUBSET ENCODING METHOD: INCREASING PATTERN DENSITY FOR FINITE AUTOMATA

摘要

The subset encoding method and related automata designs for improving the space efficiency for many applications on the Automata Processor (AP) are presented. The method is a general method that can take advantage of the character-or ability of STEs (State Transition Elements) on the AP, and can relieve the problems of limited hardware capacity and inefficient routing. Experimental results show that after applying the subset encoding method on Hamming distance automata, up to 3.2× more patterns can be placed on the AP if a sliding window is required. If a sliding window is not required, up to 192× more patterns can be placed on the AP. For a Levenshtein distance, the subset encoding can split the Levenshtein automata into small chunks and make them routable on the AP. The impact of the subset encoding method depends on the character size of the AP.

主权项

1. An encoding method of a processor for a pattern matching application comprising the steps of:
encoding a plurality of input data before streaming them into the processor, encoding and placing a plurality of patterns on loop structures on the processor, and matching the encoded input data on the processor using the loop structures,wherein the plurality of input data are application data, and the loop structures contain the encoded patterns.