High-throughput sketch update on a low-power stream processor

ABSTRACT

Sketch algorithms are widely used for many networking applications, such as identifying frequent items, top-k flows, and traffic anomalies. This paper explores the implementation of the Count-Min sketch update using Indexed SRF accesses on a SIMD stream processor (Imagine). Both the sketch data structure and the packet stream are modeled as streams, and in-lane accesses to the stream register file (SRF) support concurrent updates without explicit synchronization. The 500-MHz stream processor is capable of supporting sketch update at 10 Gbps throughput for minimum-sized IP packets. This is nearly the same performance as the 1.4-GHz Intel IXP2800 (13 Gbps), using significantly less power (2.89W vs. 21W).

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 2: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 3: C. Barakat et al. Modeling Internet backbone traffic at the flow level. IEEE Trans. on Signal Processing, 51(8), August 2003.
• 4: Bill Carlson, Intel Internet Exchange Architecture and Applications: A Practical Guide to Intel's Network Processors, Intel Press, 2003
• 5: J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143--154, April 1979.
• 6: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding frequent items in data streams, Theoretical Computer Science, v.312 n.1, p.3-15, 26 January 2004 [doi>10.1016/S0304-3975(03)00400-6]
• 7: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Random sampling for histogram construction: how much is enough?, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.436-447, June 01-04, 1998, Seattle, Washington, United States
• 8: G. Cormode and S. Muthukrishnan. Improved data stream summaries: The count-min sketch and its applications. Technical Report 2003-20, DIMACS, June 2003.
• 9: G. Cormode and S. Muthukrishnan. Summarizing and mining skewed data streams. In SIAM Inter. Conf. on Data Mining (SDM), 2005.
• 10: Graham Cormode , S. Muthukrishnan, What's new: finding significant differences in network data streams, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1219-1232, December 2005 [doi>10.1109/TNET.2005.860096]
• 11: Intel Corp. Intel IXP2800 Network Processor Hardware Reference Manual. November 2002.
• 12: Intel Corp. Intel IXP2800 and IXP2850 Network Processors B1 Stepping Qualification Report, Sept. 2004.
• 13: . William J. Dally. Packet processing with streams, Keynote Address. In HPCA Workshop on Network Processors, page 1, 2002.
• 14: DaMoN'05. First international workshop on data management on new hardware, 2005 June.
• 15: Cristian Estan , George Varghese, New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.270-313, August 2003 [doi>10.1145/859716.859719]
• 16: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 17: Minos Garofalakis, Analyzing massive data streams: past, present, and future, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California [doi>10.1145/882082.882084]
• 18: Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Querying and mining data streams: you only get one look a tutorial, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564794]
• 19: Allan Gottlieb , Ralph Grishman , Clyde P. Kruskal , Kevin P. McAuliffe , Larry Rudolph , Marc Snir, The NYU ultracomputer—designing a MIMD, shared-memory parallel machine, 25 years of the international symposia on Computer architecture (selected papers), p.239-254, June 27-July 02, 1998, Barcelona, Spain [doi>10.1145/285930.285983]
• 20: Nuwan Jayasena , Mattan Erez , Jung Ho Ahn , William J. Dally, Stream Register Files with Indexed Access, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.60, February 14-18, 2004 [doi>10.1109/HPCA.2004.10007]
• 21: Erik J. Johnson , Aaron R. Kunze, Ixp2400-2800 Programming: The Complete Microengine Coding Guide, Intel Press, 2003
• 22: Brucek Khailany , William J. Dally , Scott Rixner , Ujval J. Kapasi , John D. Owens , Brian Towles, Exploring the VLSI Scalability of Stream Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.153, February 08-12, 2003
• 23: VLSI Design and Verification of the Imagine Processor, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.289, September 16-18, 2002
• 24: Brucek Khailany , William J. Dally , Ujval J. Kapasi , Peter Mattson , Jinyung Namkoong , John D. Owens , Brian Towles , Andrew Chang , Scott Rixner, Imagine: Media Processing with Streams, IEEE Micro, v.21 n.2, p.35-46, March 2001 [doi>10.1109/40.918001]
• 25: Balachander Krishnamurthy , Subhabrata Sen , Yin Zhang , Yan Chen, Sketch-based change detection: methods, evaluation, and applications, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948236]
• 26: Yu-Kuen Lai and Gregory T. Byrd. AES packet encryption on a SIMD stream processor. In Embedded Cryptographic Hardware: Methodologies & Architectures, pages 615--624. Nova Science Publishers, 2004.
• 27: Yu-Kuen Lai and Gregory T. Byrd. AES packet encryption on a SIMD stream processor. In Embedded Cryptographic Hardware: Methodologies & Architectures, pages 615--624. Nova Science Publishers, 2004.
• 28: Yu-Kuen Lai and Gregory T. Byrd. Stream-based implementation of hash functions for multi-gigabit message authentication code. In Proc. of The 7th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), Dec. 2006.
• 29: Yan Luo , Jun Yang , Laxmi N. Bhuyan , Li Zhao, NePSim: A Network Processor Simulator with a Power Evaluation Framework, IEEE Micro, v.24 n.5, p.34-44, September 2004 [doi>10.1109/MM.2004.52]
• 30: David Meng et al. IXP2800 Intel Network Processor IP Forwarding Benchmark full disclosure report for OC192-pos, Oct. 2003.
• 31: MPDS'03. Workshop on management and processing of data streams in conjunction with ACM SIGMOD/PODS, 2003 June.
• 32: S. Muthukrishnan, Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 33: Jathin S. Rai, Yu-Kuen Lai, and Gregory T. Byrd. Packet processing on a SIMD stream processor. In Workshop on Network Processors and Applications (NP3) in conjunction with the 10th International Symposium on High-Performance Computer Architecture (HPCA10), pages 146--157, Madrid, Spain, Feb. 2004.
• 34: RIDE'05. RIDE workshop of stream data mining and applications RIDE-SDMA'05, 2005 April.
• 35: Scott Rixner , William J. Dally , Ujval J. Kapasi , Brucek Khailany , Abelardo López-Lagunas , Peter R. Mattson , John D. Owens, A bandwidth-efficient architecture for media processing, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.3-13, November 1998, Dallas, Texas, United States
• 36: Mikkel Thorup, Even strongly universal hashing is pretty fast, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.496-497, January 09-11, 2000, San Francisco, California, United States
• 37: Mikkel Thorup , Yin Zhang, Tabulation based 4-universal hashing with applications to second moment estimation, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 38: Mark N. Wegman and J. Lawrence Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22(3):265--279, June 1981.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Design, Performance

Keywords:
SIMD, VLIW, data stream processing, network processors, sketch, stream architecture