投影片 1 - Ncku

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