High-bandwidth network memory system through virtual pipelines

ABSTRACT

As network bandwidth increases, designing an effective memory system for network processors becomes a significant challenge. The size of the routing tables, the complexity of the packet classification rules, and the amount of packet buffering required all continue to grow at a staggering rate. Simply relying on large, fast SRAMs alone is not likely to be scalable or cost-effective. Instead, trends point to the use of low-cost commodity DRAM devices as a means to deliver the worst-case memory performance that network data-plane algorithms demand. While DRAMs can deliver a great deal of throughput, the problem is that memory banking significantly complicates the worst-case analysis, and specialized algorithms are needed to ensure that specific types of access patterns are conflict-free.

We introduce virtually pipelined memory, an architectural technique that efficiently supports high bandwidth, uniform latency memory accesses, and high-confidence throughput even under adversarial conditions. Virtual pipelining provides a simple-to-analyze programming model of a deep pipeline (deterministic latencies) with a completely different physical implementation (a memory system with banks and probabilistic mapping). This allows designers to effectively decouple the analysis of their algorithms and data structures from the analysis of the memory buses and banks. Unlike specialized hardware customized for a specific data-plane algorithm, our system makes no assumption about the memory access patterns. We present a mathematical argument for our system's ability to provably provide bandwidth with high confidence and demonstrate its functionality and area overhead through a synthesizable design. We further show that, even though our scheme is general purpose to support new applications such as packet reassembly, it outperforms the state-of-the-art in specialized packet buffering architectures.

REFERENCES

• 1: Banit Agrawal , Timothy Sherwood, Virtually Pipelined Network Memory, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.197-207, December 09-13, 2006 [doi>10.1109/MICRO.2006.51]
• 2: A. Nikologiannis and M. Katevenis, "Efficient per-flow queueing in DRAM at OC-192 line rate using out-of-order execution techniques," in Proc. IEEE Int. Conf. Commun. (ICC'2001), Helsinki, Finland, Jun. 2001, pp. 2048-2052.
• 3: S. Iyer, R. R. Kompella, and N. McKeown, "Designing packet buffers for router linecards," Stanford Univ., Tech. Rep. TR02-HPNG-031001, Nov. 2002.
• 4: Jorge García , Jesús Corbal , Llorenç Cerdà , Mateo Valero, Design and Implementation of High-Performance Memory Systems for Future Packet Buffers, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.373, December 03-05, 2003
• 5: Timothy Sherwood , George Varghese , Brad Calder, A pipelined memory architecture for high throughput network processors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 6: Jahangir Hasan , Satish Chandra , T. N. Vijaykumar, Efficient use of memory bandwidth to improve network processor throughput, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 7: Wi-fen Lin, Reducing DRAM Latencies with an Integrated Memory Hierarchy Design, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.301, January 20-24, 2001
• 8: Scott Rixner, Memory Controller Optimizations for Web Servers, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.355-366, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.22]
• 9: Xiaodong, Fine-grain Priority Scheduling on Multi-channel Memory Systems, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.107, February 02-06, 2002
• 10: Jun Shao , Brian T. Davis, A Burst Scheduling Access Reordering Mechanism, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.285-294, February 10-14, 2007 [doi>10.1109/HPCA.2007.346206]
• 11: B. K. Mathew, S. A. McKee, J. B. Carter, and A. Davis, "Design of a parallel vector access unit for SDRAM memory systems," in Proc. 6th Int. Symp. High-Perform. Comput. Archit. (HPCA'00), 2000, pp. 39-48.
• 12: Sung I. Hong , Sally A. McKee , Maximo H. Salinas , Robert H. Klenke , James H. Aylor , Wm. A. Wulf, Access Order and Effective Bandwidth for Streams on a Direct Rambus Memory, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.80, January 09-12, 1999
• 13: Scott Rixner , William J. Dally , Ujval J. Kapasi , Peter Mattson , John D. Owens, Memory access scheduling, Proceedings of the 27th annual international symposium on Computer architecture, p.128-138, June 2000, Vancouver, British Columbia, Canada
• 14: Roger Espasa , Mateo Valero , James E. Smith, Out-of-order vector architectures, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.160-170, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 15: B. Ramakrishna Rau, Pseudo-randomly interleaved memory, Proceedings of the 18th annual international symposium on Computer architecture, p.74-83, May 27-30, 1991, Toronto, Ontario, Canada
• 16: Tomás Lang , Mateo Valero , Montse Peiron , Eduard Ayguadé, Conflict-Free Access for Streams in Multimodule Memories, IEEE Transactions on Computers, v.44 n.5, p.634-646, May 1995 [doi>10.1109/12.381949]
• 17: Jesus Corbal , Roger Espasa , Mateo Valero, Command Vector Memory Systems: High Performance at Low Cost, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.68, October 12-18, 1998
• 18: Fan Chung , Ronald Graham , George Varghese, Parallelism versus memory allocation in pipelined router forwarding engines, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007928]
• 19: G. A. Bouchard, M. Calle, and R. Ramaswami, "Dynamic random access memory system with bank conflict avoidance feature," U.S. Patent 6 944 731, Sep. 2005.
• 20: G. Shrimali and N. McKeown, "Building packet buffers with interleaved memories," in Proc. Workshop High Perform. Switching and Routing, Hong Kong, May 2005, pp. 1-5.
• 21: Sailesh Kumar , Patrick Crowley , Jonathan Turner, Design of Randomized Multichannel Packet Storage for High Performance Routers, Proceedings of the 13th Symposium on High Performance Interconnects, p.100-106, August 17-19, 2005 [doi>10.1109/CONECT.2005.17]
• 22: Florin Baboescu , Dean M. Tullsen , Grigore Rosu , Sumeet Singh, A Tree Based Router Search Engine Architecture with Single Port Memories, Proceedings of the 32nd annual international symposium on Computer Architecture, p.123-133, June 04-08, 2005
• 23: Jahangir Hasan , Srihari Cadambi , Venkatta Jakkula , Srimat Chakradhar, Chisel: A Storage-efficient, Collision-free Hash-based Network Processing Architecture, Proceedings of the 33rd annual international symposium on Computer Architecture, p.203-215, June 17-21, 2006
• 24: Richard Crisp, Direct Rambus Technology: The New Main Memory Standard, IEEE Micro, v.17 n.6, p.18-28, November 1997 [doi>10.1109/40.641593]
• 25: M. Gries, "A survey of synchronous RAM architectures," Computer Eng. and Networks Lab. (TIK), ETH Zurich, Switzerland, Tech. Rep. 71, Apr. 1999.
• 26: Brian Davis , Bruce L. Jacob , Trevor N. Mudge, The New DRAM Interfaces: SDRAM, RDRAM and Variants, Proceedings of the Third International Symposium on High Performance Computing, p.26-31, October 16-18, 2000
• 27: Vinodh Cuppu , Bruce Jacob , Brian Davis , Trevor Mudge, A performance comparison of contemporary DRAM architectures, Proceedings of the 26th annual international symposium on Computer architecture, p.222-233, May 01-04, 1999, Atlanta, Georgia, United States
• 28: RamBus, "RDRAM memory: Leading performance and value over SDRAM and DDR," 2001.
• 29: Samsung, "Samsung RamBus MR18R162GDF0-CM8 512 MB 16 bit 800 MHz datasheet," 2005.
• 30: J. Truong, "Evolution of network memory," Samsung Semiconductor, Inc., Mar. 2005.
• 31: T. Kirihata et al., "An 800 MHz embedded dram with a concurrent refresh mode," in Proc. IEEE Int. Solid-State Circuits Conf. (ISSCC), Feb. 2004, pp. 15-19.
• 32: J. L. Carter and M. N. Wegman, "Universal classes of hash functions," J.Comput. Syst. Sci., vol. 18, pp. 143-154, 1979.
• 33: Éliane Jaulmes , Antoine Joux , Frédéric Valette, On the Security of Randomized CBC-MAC Beyond the Birthday Paradox Limit: A New Construction, Revised Papers from the 9th International Workshop on Fast Software Encryption, p.237-251, February 04-06, 2002
• 34: "Internet core router test: Looking at latency," 2001 [Online]. Available: http://www.lightreading.com/document.asp?doc_id=4009&page_number=7
• 35: P. Shivakumar and N. P. Jouppi, "Cacti 3.0: An integrated cache timing, power and area model," Western Research Lab (WRL) Res. Rep., Tech. Rep, 2001/2.
• 36: J. Turner, "A proposed architecture for the Geni backbone platform," Mar. 2006.
• 37: W. Eatherton, "The push of network processing to the top of the pyramid," 2005, ANCS'05 Keynote.
• 38: Sarang Dharmapurikar , Vern Paxson, Robust TCP stream reassembly in the presence of adversaries, Proceedings of the 14th conference on USENIX Security Symposium, p.5-5, July 31-August 05, 2005, Baltimore, MD

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories
          Subjects: Dynamic memory (DRAM)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
      C.2.m Miscellaneous

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies; Virtual memory

General Terms:
Algorithms, Design, Management

Keywords:
DRAM, MTS, VPNM, bank conflicts, mean time to stall, memory, memory controller, network, packet buffering, packet reassembly, universal hashing, virtual pipeline