A Packet Classifier Using Parallel EVMDD (k) Machine

Author

Nakahara, H. ; Sasao, T. ; Matsuura, Motoharu

fYear

2013

fDate

26-28 Sept. 2013

Firstpage

43

Lastpage

48

Abstract

A decision diagram machine (DDM) is a special-purpose processor that uses special instructions to evaluate a decision diagram. This paper presents a packet classifier using a parallel edge-valued multi-valued decision diagram (EVMDD (k)) machine. To reduce computation time and code size, first, a rule set for the packet classifier is partitioned into groups. Then, the parallel EVMDD (k) machine evaluates them. We implemented the parallel EVMDD (k) machine consisting of 32 EVMDD (4) machines on an FPGA, and compared it with the Intel´s Core i5 microprocessor running at 1.7GHz. Our machine is 7.8-40.1 times faster than the Core i5, and it requires only 12.0-52.6 percents of the memory for the Core~i5.

Keywords

decision diagrams; field programmable gate arrays; microprocessor chips; packet switching; parallel machines; pattern classification; FPGA; code size reduction; computation time reduction; decision diagram machine; edge valued multivalued decision diagram; frequency 1.7 GHz; packet classifier; parallel EVMDD (k) machine; special instruction; special purpose processor; Boolean functions; Computer science; Data structures; Educational institutions; IP networks; Memory management; Protocols; Multicore; Packet Classifier;

fLanguage

English

Publisher

ieee

Conference_Titel

Embedded Multicore Socs (MCSoC), 2013 IEEE 7th International Symposium on

Conference_Location

Tokyo

Type

conf

DOI

10.1109/MCSoC.2013.26

Filename

6657902