投影片 1 - Ncku

投影片 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

Recently Viewed Presentations

  • eCATS The Honeywell Web-based Corrective Action Solution eCATS

    eCATS The Honeywell Web-based Corrective Action Solution eCATS

    "The Honeywell Web-based Corrective Action Solution" eCATS for Suppliers Honeywell Confidential & Proprietary Last Revised: August 26, 2008 Dashboard Basics Logging in and the Dashboard Screens How to Login Forgot password Suppliers Registration Dashboard Screen Data Maintenance Status and Description...
  • January 14, 2013

    January 14, 2013

    It was in the clove of seasons, summer was dead but autumn had not yet been born, that the ibis lit in the bleeding tree. The flower garden was stained with rotting brown magnolia petals and ironweeds grew rank amid...
  • T-6B Fuel System - T-6B Texan II, Navy Primary Training

    T-6B Fuel System - T-6B Texan II, Navy Primary Training

    Ensure cap is seated with arrow forward and tab folding to back. Single-point. Primary method of refueling. Fills all tanks simultaneously. Pre-check valves test shutoff system in tank - lifting simulates full tank and fuel refilling stops. S.P. - 530#...
  • Taxonomy - Weebly

    Taxonomy - Weebly

    taxonomy. Benefits of classifying. Uses the same language for all names (Latin) Early Classification System . ... Human - Homo . sapien. Two Methods of Classifying Organisms . Cladograms. Dichotomous Keys . Dichotomous Key . Characteristics given in pairs. Author:
  • Bio 211 review exam #1 - Iowa State University

    Bio 211 review exam #1 - Iowa State University

    Bio 211 review exam #1. Define Science. the process of gaining knowledge and investigating the universe through observation, posing questions, and experimentation. ... All of the following are protists EXCEPT. A.) E. coli. B.) malaria. C.) kelp. D.) paramecium.
  • Physical Science - Home - Polk School District

    Physical Science - Home - Polk School District

    In the previous lesson, we learned that a physical property is whether it is a solid, liquid, or gas at room temperature. But what is a solid, liquid, or gas, anyway? You probably know of examples but do you know...
  • Thor as depicted in Modern Media Vikings as

    Thor as depicted in Modern Media Vikings as

    Longship or Longboat. A slong slender ship, shallow in the draft, with a large rectangular sail, rows of oars and a dragon figure head. These ships were able to travel on the sea or ocean, and rivers, giving them greater...
  • ChristianChristian PracticesPractices Revision Revision What is worship? Give

    ChristianChristian PracticesPractices Revision Revision What is worship? Give

    Christian Practices Revision . What is worship? Give examples of different forms of worship (liturgical, informal and private) Why is prayer significant for Christians? Explain the meaning of the Lord's Prayer. Why and how is Easter celebrated? Why and how...