成功大学资讯工程系.ppt

成功大學資訊工程系　CIAL實驗室 CSIE CIAL Lab Pipelined Architecture For Multi-String Match Outline 1. Introduction 2. Pipelined Architecture 3. Performance evaluation 4. Conclusion Introduction (1/6) A string Y of length n is a sequence of characters c1c2……cn. Let Σ = {Y1, Y2, ...YN} be a finite set of strings called keywords or signatures proposed hardware solutions are based on the well-known Aho-Corasick (AC) algorithm , where the system is modeled as a deterministic finite automaton(DFA) we present a pipelined processing approach to the implementation of AC algorithm, called P-AC. Introduction (2/6) Introduction (3/6) Introduction (4/6) Introduction (6/6) Introduction (5/5) Outline 1. Introduction 2. Pipelined Architecture 3. Performance evaluation 4. Conclusion Pipelined Architecture (1/6) Pipelined Architecture (2/6) Assume the pipeline has k+1 stages numbered from 0 to k last stage is only used to buffer the search result of stage (k-1). longer than k characters are divided into segments of length k last segment whose length can be less than k Pipelined Architecture (3/6) local transition tables (LT) can be implemented using hardware hashing For long strings with more than k characters, the match-result will be generated by the aggregation unit (AU). transition rule table (TD) to determine the next state segment ID will be passed to the corresponding partial match unit (PMi) of the AU. (PMi) sends a lookup request to the conditional match table (CMT); Pipelined Architecture (4/6) Pipelined Architecture (5/6) Pipelined Architecture (6/6) Outline 1. Introduction 2. Pipelined Architecture 3. Performance evaluation 4. Conclusion Performance evaluation (1/2) There are k+3 memories in the system (k memories for the pipeline unit) 2 memories for the DFA units and 1 memory for the CMT). DFA