Processor Array Architectures for Deep Packet Classification Authors: Fayez Gebali and A.N.M. Ehtesham Rafiq Publisher: IEEE Transactions on Parallel and Distributed Systems Present: Kai-Tso Chang Date: October, 22, 2008 1 Define T: text length : n P: pattern length : m t0 t1tn-1 p0 p1 pm-1 2 The basic string matching
algorithm 3 Expressing the algorithm as an iterative expression 1. represents an m-input AND function 2. Match(a,b) is a function that is true when character a matches b 1=y0 input text: abcdx xxxxx 1=y1 input text: xabcd xxxxx 1=y6 input text: xxxxx xabcd 4 Dependence graph (DG) d
c b a 5 Timing fuction The column vector s =[s1,s2] is the scheduling vector and s is an integer 6 Timing function 7 Pipeline , broadcast Pipeline a certain variable whose null vector is e, we must satisfy the following inequality Broadcast a variable whose null vector is e, we must have
8 Pipeline , broadcast We have only one output variable Y whose null-vector is Pipeline: Broadcast: 9 Timing function d 3 4 c
2 3 b 1 2 0 1 a 5 4 3 2
6 7 8 9 8 5 6 7 4 5 6
3 4 5 7 6 10 Pipeline , broadcast 11 DG Node Projection d c b a
12 DG Node Projection 13 DG Node Projection 14 Design 1.a d c b a 3 2
1 0 4 3 2 1 5 4 3 2 6 7
8 9 5 6 7 8 4 5 6 7 3
4 5 6 15 Design 1.a 16 1 Input text: abcdx xxxxx d d a b c
3 1 1 c d c b a 2 1 clock 3 0 1 2 1 b b
a c d 1 1 1 a a b c d 0 1 T Design 1.b
d c b a 3 2 1 0 4 3 2 1 5
4 3 2 6 7 8 9 5 6 7 8 4
5 6 7 3 4 5 6 18 Design 1.b 19 Design 1.b 20
Design 1.c d c b a 3 4 2 3 1 2 0
1 5 4 3 2 6 7 8 9 8 5 6
7 4 5 6 3 4 5 7 6 21 22 Design 1.c
23 Comparing designs 1.a and 1.b 24 Design 2 25 Design 2 d c b a 5 6
7 8 9 10 11 6 7 8 9 10 11 12
7 8 9 10 11 12 13 8 9 10 12
13 14 11 26 Design 2.a d c b a 5 6 7 8
9 10 11 6 7 8 9 10 11 12 7
8 9 10 11 12 13 8 9 10 12 13 14
11 27 Design 2.a 28 a b c d x a c d b x 3 a b c
d x d 1 a b c x d a b d x c clock 8 0 1 2
3 4 5 6 7 1 a c x b d 2 c 1 b x a c d
b c d a 1 1 c b a b 1 b a c a b 1 a
0 a 1 29 Design 2.b 30 Comparing designs 1.a and 2.a 31 Design 3 Broadcast: 32 Design 3
d c b a 4 5 6 7 8 9 10 4 5
6 7 8 9 10 4 5 6 7 8 9
10 4 5 6 7 8 9 10 33 Design 3.a T 3 2
1 0 34 a b c d db c a d cbd a bc a clock 4
1 2 0 3 c a b c a b b a b a a 35