Pattern matching in a multiprocessor environment

Details Pattern matching in a multiprocessor environment Pattern matching in a multiprocessor environment

2011-07-22

2011-12-27

Gaffin, Jeffrey A (Department: 2129)

Data processing: artificial intelligence

Knowledge processing system

Knowledge representation and reasoning technique

Reexamination Certificate

active

08086554

ABSTRACT:
Pattern matching in a plurality of interconnected processing engines includes: accepting a stream of input sequences over an interface and storing the input sequences; storing instructions for matching an input sequence to one or more patterns in memory accessible by a first set of one or more processing engines, and storing instructions for matching an input sequence to one or more patterns in memory accessible by a second set of one or more processing engines; distributing information identifying selected input sequences to the first and second sets of processing engines; and retrieving the identified input sequences to perform pattern matching in the first and second sets of processing engines.

REFERENCES:
patent: 5051886 (1991-09-01), Kawaguchi et al.
patent: 5329405 (1994-07-01), Hou et al.
patent: 5452451 (1995-09-01), Akizawa et al.
patent: 5815096 (1998-09-01), Smith
patent: 5831883 (1998-11-01), Suter et al.
patent: 5956724 (1999-09-01), Griffiths
patent: 5990899 (1999-11-01), Whitten
patent: 5995963 (1999-11-01), Nanba et al.
patent: 6012057 (2000-01-01), Mayer et al.
patent: 7394288 (2008-07-01), Agarwal
patent: 7411418 (2008-08-01), Gould et al.
patent: 7461236 (2008-12-01), Wentzlaff
patent: 7539681 (2009-05-01), Norton et al.
patent: 7565380 (2009-07-01), Venkatachary
patent: 7636717 (2009-12-01), Gupta et al.
patent: 7702629 (2010-04-01), Cytron et al.
patent: 7765183 (2010-07-01), Williams, Jr.
patent: 7805392 (2010-09-01), Steele et al.
patent: 2003/0051043 (2003-03-01), Wyschogrod et al.
patent: 2003/0110154 (2003-06-01), Ishihara et al.
patent: 2004/0162826 (2004-08-01), Wyschogrod et al.
patent: 2005/0125650 (2005-06-01), Chen et al.
patent: 2005/0132342 (2005-06-01), Van Lunteren
patent: 2005/0286742 (2005-12-01), Rasmussen et al.
patent: 2006/0020595 (2006-01-01), Norton et al.
patent: 2006/0085389 (2006-04-01), Flanagan et al.
patent: 2006/0101195 (2006-05-01), Jain
patent: 2006/0193159 (2006-08-01), Tan et al.
patent: 2007/0005596 (2007-01-01), Brown et al.
patent: 2007/0124146 (2007-05-01), Lunteren
patent: WO 2004/072796 (2004-08-01), None
Agarwal, Anant. “Raw Computation,”Scientific Americanvol. 281, No. 2: 44-47, Aug. 1999.
Taylor, Michael Bedford et. al., “Evaluation of the Raw Microprocessor: An Exposed-Wire-Delay Architecture for ILP and Streams,”Proceedings of International Symposium on Computer Architecture, Jun. 2004.
Taylor, Michael Bedford et. al., “Scalar Operand Networks: On-Chip Interconnect for ILP in Partitioned Architectures,”Proceedings of the International Symposium on High Performance Computer Architecture, Feb. 2003.
Taylor, Michael Bedford et. al., “A 16-Issue Multiple-Program-Counter Microprocessor with Point-to-Point Scalar Operand Network,”Proceedings of the IEEE International Solid-State Circuits Conference, Feb. 2003.
Taylor, Michael Bedford et. al., “The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs,”IEEE Micro, pp. 25-35, Mar.-Apr. 2002.
Lee, Walter et. al., “Space-Time Scheduling of Instruction-Level Parallelism on a Raw Machine,”Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS-VIII), San Jose, CA, Oct. 4-7, 1998.
Kim, Jason Sungtae et. al., “Energy Characterization of a Tiled Architecture Processor with On-Chip Networks,”International Symposium on Low Power Electronics and Design, Seoul, Korea, Aug. 25-27, 2003.
Barua, Rajeev et. al., “Compiler Support for Scalable and Efficient Memory Systems,”IEEE Transactions on Computers, Nov. 2001.
Waingold, Elliot et. al., “Baring it all to Software: Raw Machines,”IEEE Computer, pp. 86-93, Sep. 1997.
Lee, Walter et. al., “Convergent Scheduling,”Proceedings of the 35thInternational Symposium on Microarchitecture, Istanbul, Turkey, Nov. 2002.
Wentzlaff, David and Anant Agarwal, “A Quantitative Comparison of Reconfigurable, Tiled, and Conventional Architectures on Bit-Level Computation,”MIT/LCS Technical Report LCS-TR-944, Apr. 2004.
Suh, Jinwoo et. al., “A Performance Analysis of PIM, Stream Processing , and Tiled Processing on Memory-Intensive Signal Processing Kernels,”Proceedings of the International Symposium on Computer Architecture, Jun. 2003.
Barua, Rajeev et. al., “Maps: A Compiler-Managed Memory System for Raw Machines,”Proceedings of the Twenty-Sixth International Symposium on Computer Architecture(ISCA-26), Atlanta, GA, Jun. 1999.
Barua, Rajeev et. al., “Memory Bank Disambiguation using Modulo Unrolling for Raw Machines,”Proceedings of the Fifth International Conference on High Performance Computing, Chennai, India, Dec. 17-20, 1998.
Agarwal, A. et. al., “The Raw Compiler Project,”Proceedings of the Second SUIF Compiler Workshop, Stanford, CA, Aug. 21-23, 1997.
Taylor, Michael Bedford et. al., “Scalar Operand Networks,”IEEE Transactions on Parallel and Distributed Systems(Special Issue on On-Chip Networks), Feb. 2005.
Taylor, Michael. The Raw Prototype Design Document V5.01 [online]. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Sep. 6, 2004 [retrieved on Sep. 25, 2006]. Retrieved from the Internet: <ftp://ftp.cag.lcs.mit.edu/pub/raw/documents/RawSpec99.pdf>.
Moritz, Csaba Andras et. al., “Hot Pages: Software Caching for Raw Microprocessors,”MIT/LCS Technical Memo LCS-TM-599, Aug. 1999.
Dharmapurikar, S. & J. Lockwood. “Fast and Scalable Pattern Matching for Content Filtering,”ANCS'05, Oct. 26-28, 2005, Princeton, New Jersey, USA.
Tan, L. & T. Sherwood., “Architectures for Bit-Split String Scanning in Intrusion Detection,”IEEE Computer Society, Jan.-Feb. 2006 (pp. 1-9).
Lin Tan; Sherwood, T., “A high throughput string matching architecture for intrusion detection and prevention”, International Symposium on Computer Architecture (ISCA'05), 2005.
Benjamin C. Brodie, David E. Taylor, Ron K. Cytron, “A Scalable Architecture for High-Throughput Regular-Expression Pattern Matching,” pp. 191-202, International Symposium on Computer Architecture (ISCA'06), 2006.
Wiklund et al., SoCBUS: Switched network on chip for hard real time systems, Apr. 22-26, 2003, Proceeds of the Int'l Parallel and Distributed Processing Symposium (IPDPS), pp. 78-85.
Norton, Marc. “Optimizing Pattern matching for intrusion detection,” 2004, Sourcefire Inc., White Paper.
Takeda et al., Pattern Matching Machine for Text Compressed Using Finite State Model, Oct. 1997, DOI Technical Report, DOI-TR-142.
Aho et al., Efficient String Matching: An Aid to Bibliographic Search, Jun. 1975, Communications of the ACM, vol. 18 No. 6, pp. 333-340.
Amir et al., Efficient Pattern Matching with Scaling, Mar. 1992, Journal of Algorithms, pp. 344-357.
Kida et al., Multiple Pattern Matching in LZW Compressed Text, Mar. 30-Apr. 1, 1998, Data Compression Conference, 1998, DCC 98 Proceedings, pp. 103-112.
Fish & Richardson P.C., Unpublished Application in U.S. Appl. No. 11/564,694, filed Nov. 29, 2006, 55 pages.

Affiliated with

Also associated with

Rating

Pattern matching in a multiprocessor environment does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pattern matching in a multiprocessor environment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern matching in a multiprocessor environment will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4315706