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.