Shangri-La: achieving high performance from compiled network applications while enabling ease of programming

ABSTRACT

Programming network processors is challenging. To sustain high line rates, network processors have extremely tight memory access and instruction budgets. Achieving desired performance has traditionally required hand-coded assembly. Researchers have recently proposed high-level programming languages for packet processing, but the challenges of compiling these languages into code that is competitive with hand-tuned assembly remain unanswered.This paper describes the Shangri-La compiler, which accepts a packet program written in a C-like high-level language and applies scalar and specialized optimizations to generate a highly optimized binary. Hot code paths identified by profiling are mapped across processing elements to maximize processor utilization. Since our compilation target has no hardware caches, software-controlled caches are generated for frequently accessed application data structures. Packet handling optimizations significantly reduce per-packet memory access and instruction counts. Finally, a custom stack model maps stack frames to the fastest levels of the target processor's heterogeneous memory hierarchy.Binaries generated by the compiler were evaluated on the Intel IXP2400 network processor with eight packet processing cores and eight threads per core. Our results show the importance of both traditional and specialized optimization techniques for achieving the maximum forwarding rates on three network applications, L3-Switch, MPLS and Firewall.

REFERENCES

• 1: Amaral, J.N., Gao, G.R., Dehnert, J. and Towle, R. The SGI Pro64 Compiler Infrastructure: A Tutorial. In PACT'00, Philadelphia, PA, October 2000.
• 2: Oren Avissar , Rajeev Barua , Dave Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.6-26, November 2002 [doi>10.1145/581888.581891]
• 3: Jean-Loup Baer , Douglas Low , Patrick Crowley , Neal Sidhwaney, Memory Hierarchy Design for a Multiprocessor Look-up Engine, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.206, September 27-October 01, 2003
• 4: Broadcom Corporation. The Sibyte BCM1250 Processor. http://sibyte.broadcom.com/public/index.html
• 5: Benjie Chen , Robert Morris, Flexible Control of Parallelism in a Multiprocessor PC Router, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.333-346, June 25-30, 2001
• 6: Chiueh, T. and Pradhan, P. High-performance IP routing table lookup using CPU caching. In IEEE Infocom'99, New York, NY, March 1999.
• 7: Fred Chow , Sun Chan , Robert Kennedy , Shin-Ming Liu , Raymond Lo , Peng Tu, A new algorithm for partial redundancy elimination based on SSA form, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.273-286, June 16-18, 1997, Las Vegas, Nevada, United States
• 8: Keith D. Cooper , Timothy J. Harvey, Compiler-controlled memory, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.2-11, October 02-07, 1998, San Jose, California, United States
• 9: Jack W. Davidson , Sanjay Jinturkar, Memory access coalescing: a technique for eliminating redundant memory accesses, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.186-195, June 20-24, 1994, Orlando, Florida, United States
• 10: Jinquan Dai , Bo Huang , Long Li , Luddy Harrison, Automatically partitioning packet processing applications for pipelined architectures, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 11: Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Type-based alias analysis, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.106-117, June 17-19, 1998, Montreal, Quebec, Canada
• 12: Lal George , Matthias Blume, Taming the IXP network processor, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 13: Goglin, S., Johnson, E.J. and Vin, H. Baker: A Packet Processing Programming Language for Highly Concurrent Hardware. Under preparation for submission.
• 14: Rajiv Gupta , Eduard Mehofer , Youtao Zhang, A Representation for Bit Section Based Analysis and Optimization, Proceedings of the 11th International Conference on Compiler Construction, p.62-77, April 08-12, 2002
• 15: IBM. The PowerNP architecture. http://www.hifn.com/products/5np4g.html.
• 16: Intel Corporation. Intel IXP2400 Network Processor: Hardware Reference Manual. October 2002.
• 17: Intel Corporation. Microengine Version 2 (MEv2): Microengine C Compiler Coding Considerations. June 2003.
• 18: Erik J. Johnson , Aaron R. Kunze, Ixp2400-2800 Programming: The Complete Microengine Coding Guide, Intel Press, 2003
• 19: Ju, R., Chan, S. and Wu, Chengyong. Open Research Compiler for Itanium Processor Family. Tutorial in MICRO-34, Austin, TX, December 2001.
• 20: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 21: Eddie Kohler , Robert Morris , Benjie Chen, Programming language optimizations for modular router configurations, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 22: Jinhwan Kim , Sungjoon Jung , Yunheung Paek , Gang-Ryung Uh, Experience with a retargetable compiler for a commercial network processor, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581658]
• 23: Chidamber Kulkarni , Matthias Gries , Christian Sauer , Kurt Keutzer, Programming challenges in network processor deployment, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951735]
• 24: Bengu Li , Rajiv Gupta, Simple offset assignment in presence of subword data, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951715]
• 25: Girija Narlikar , Francis Zane, Performance modeling for fast IP lookups, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 2001, Cambridge, Massachusetts, United States
• 26: Intel Corporation. Microengine Version 2 (MEv2): Microengine C Compiler Coding Considerations. June 2003.
• 27: Network Processing Forum. IP Forwarding Application Level Benchmark. http://www.npforum.org/techinfo/ipforwarding_bm.pdf
• 28: Network Processing Forum. MPLS Forwarding Application Level Benchmark and Annex. http://www.npforum.org/techinfo/MPLSBenchmark.pdf
• 29: PMC-Sierra. MIPS-based Processors. http://pmc-sierra.com/processors/
• 30: Rosen, E., Viswanathan, A. and Callon, R. RFC 3031 - Multiprotocol Label Switching Architecture. IETF, January 2001.
• 31: Shah, N., Plishker, W. and Keutzer, K. NP-Click: A Programming Model for the Intel IXP1200. In 2nd Workshop on Network Processors (NP-2), Anaheim, CA, February 2003.
• 32: Shah, N., Plishker, W. and Keutzer, K. Comparing Network Processor Programming Environments: A Case Study. In 2004 Workshop on Productivity and Performance in High-End Computing (P-PHEC), HPCA-10, Madrid, Spain, February 2004.
• 33: Mark Stephenson , Jonathan Babb , Saman Amarasinghe, Bidwidth analysis with application to silicon compilation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.108-120, June 18-21, 2000, Vancouver, British Columbia, Canada
• 34: W. Richard Stevens, TCP/IP illustrated (vol. 1): the protocols, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 35: Sumesh Udayakumaran , Rajeev Barua, Compiler-decided dynamic memory allocation for scratch-pad based embedded systems, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951747]
• 36: Vin, H., Mudigonda, J., Jason, J., Johnson, E.J., Ju, R., Kunze, A. and Lian, R. A Programming Environment for Packet-processing Systems: Design Considerations. In 3rd Workshop on Network Processors & Applications, Madrid, Spain, February 2004.
• 37: Xiaotong Zhuang , Santosh Pande, Balancing register allocation across threads for a multithreaded network processor, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 38: Zhuang, X. and Pande, S. Resolving Register Bank Conflicts for a Network Processor. In PLDI'03, New Orleans, LA, June 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Data-flow languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages
      D.3.4 Processors
          Subjects: Optimization; Code generation; Compilers

General Terms:
Algorithms, Design, Languages, Performance

Keywords:
chip multiprocessors, dataflow programming, network processors, packet processing, program partitioning, throughput-oriented computing