Automatically partitioning packet processing applications for pipelined architectures

ABSTRACT

Modern network processors employs parallel processing engines (PEs) to keep up with explosive internet packet processing demands. Most network processors further allow processing engines to be organized in a pipelined fashion to enable higher processing throughput and flexibility. In this paper, we present a novel program transformation technique to exploit parallel and pipelined computing power of modern network processors. Our proposed method automatically partitions a sequential packet processing application into coordinated pipelined parallel subtasks which can be naturally mapped to contemporary high-performance network processors. Our transformation technique ensures that packet processing tasks are balanced among pipeline stages and that data transmission between pipeline stages is minimized. We have implemented the proposed transformation method in an auto-partitioning C compiler product for Intel Network Processors. Experimental results show that our method provides impressive speed up for the commonly used NPF IPv4 forwarding and IP forwarding benchmarks. For a 9-stage pipeline, our auto-partitioning C compiler obtained more than 4X speedup for the IPv4 forwarding PPS and the IP forwarding PPS (for both the IPv4 traffic and IPv6 traffic).

REFERENCES

• 1: Challenges in Building Network Processor Based Solutions, http://www.futsoft.com/pdf/NPwp.pdf
• 2: Intel IXP family of Network Processors, www.intel.com/design/network/products/npfamily/index.htm
• 3: IBM PowerNP Network Processors http://www-3.ibm.com/chips/techlib/techlib.nsf/products/IBM_PowerNP_NP4GS3
• 4: CPort Network Processor family, http://www.windriver.com/cgi-bin/partnerships/directory/viewProd.cgi?id=1371
• 5: Agere's PayloadPlus Family of Network Processors, http://www.agere.com/telecom/network_processors.html
• 6: AMCC's nP7xxx series of Network Processors, http://www.mmcnetworks.com/solutions/
• 7: Introduction to the Auto-Partitioning Programming Model, http://www.intel.com/design/network/papers/25411401.pdf
• 8: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 9: TejaNP*: A Software Platform for Network Processors, http://www.teja.com
• 10: Vin, H., Mudigonda, J., Jason, J., Johnson, E., Ju, R., Kunze, A. and Lian, R. A Programming Environment for Packet-processing Systems: Design Considerations, 3rd Workshop on Network Processors & Applications (Feb. 2004)
• 11: Michael K. Chen , Xiao Feng Li , Ruiqi Lian , Jason H. Lin , Lixia Liu , Tao Liu , Roy Ju, Shangri-La: achieving high performance from compiled network applications while enabling ease of programming, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 12: A V Goldberg , R E Tarjan, A new approach to the maximum flow problem, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.136-146, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12144]
• 13: Honghua Yang , D. F. Wong, Efficient network flow based min-cut balanced partitioning, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.50-55, November 06-10, 1994, San Jose, California, United States
• 14: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 15: Tao Zhang , Santosh Pande , Antonio Valverde, Tamper-resistant whole program partitioning, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 16: David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994 [doi>10.1145/197405.197406]
• 17: Ken Kennedy , Kathryn S. McKinley, Loop distribution with arbitrary control flow, Proceedings of the 1990 ACM/IEEE conference on Supercomputing, p.407-416, November 12-16, 1990, New York, New York
• 18: Jia Liang Han, Program Partition and Logic Program Analysis, IEEE Transactions on Software Engineering, v.21 n.12, p.959-968, December 1995 [doi>10.1109/32.489072]
• 19: Tao Yang , Apostolos Gerasoulis, PYRROS: static task scheduling and code generation for message passing multiprocessors, Proceedings of the 6th international conference on Supercomputing, p.428-437, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143446]
• 20: Jaspal Subhlok , Gary Vondran, Optimal mapping of sequences of data parallel tasks, ACM SIGPLAN Notices, v.30 n.8, p.134-143, Aug. 1995
• 21: A. N. Choudhary , B. Narahari , D. M. Nicol , R. Simha, Optimal Processor Assignment for a Class of Pipelined Computations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.439-445, April 1994 [doi>10.1109/71.273050]
• 22: Jaspal Subhlok , David R. O'Hallaron , Thomas Gross , Peter A. Dinda , Jon Webb, Communication and memory requirements as the basis for mapping task and data parallel programs, Proceedings of the 1994 conference on Supercomputing, p.330-339, December 1994, Washington, D.C., United States
• 23: Salvatore Orlando , Raffaele Perego, Scheduling Data-Parallel Computations on Heterogeneous and Time-Shared Environments, Proceedings of the 4th International Euro-Par Conference on Parallel Processing, p.356-366, September 01-04, 1998
• 24: Michael I. Gordon , William Thies , Michal Karczmarek , Jasper Lin , Ali S. Meli , Andrew A. Lamb , Chris Leger , Jeremy Wong , Henry Hoffmann , David Maze , Saman Amarasinghe, A stream compiler for communication-exposed architectures, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 25: Network Processor Forum (NPF), IPv4 Forwarding Benchmark Implementation Agreements (July 2002), http://www.npforum.org/benchmarking/licenseagm_IPv4.shtml
• 26: Network Processor Forum (NPF), IP Forwarding Benchmark Implementation Agreements (June 2003), http://www.npforum.org/benchmarking/licenseagm_ipforwarding.shtml
• 27: William Thies, Michal Karczmarek, Michael Gordon, David Maze, Jeremy Wong, Henry Hoffmann, Matthew Brown, and Saman Amarasinghe. StreamIt: A Compiler for Streaming Applications, MIT-LCS Technical Memo TM-622, Cambridge, MA (December, 2001)
• 28: Heidi Ziegler , Byoungro So , Mary Hall , Pedro C. Diniz, Coarse-Grain Pipelining on Multiple FPGA Architectures, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.77, September 22-24, 2002
• 29: Wei Du , Renato Ferreira , Gagan Agrawal, Compiler Support for Exploiting Coarse-Grained Pipelined Parallelism, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.8, November 15-21, 2003
• 30: B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192731]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Design, Performance

Keywords:
live-set transmission, network processor, packet processing, parallel, pipelining transformation, program partition