Automatic multithreading and multiprocessing of C programs for IXP

ABSTRACT

Effective compilation of packet processing applications onto the Intel IXP network processors requires, among other things, the automatic use of multiple threads on one or more processing elements, and the automatic introduction of synchronization as required to correctly enforce dependences between such threads. We describe the program transformation that is used in the Intel Auto-partitioning C Compiler for IXP to automatically multithread/multi-process a program for the IXP. This transformation consists of steps that introduce inter-thread signaling to enforce dependences, optimize the placement of such signaling, reduce the number of signals in use to the number available in hardware, and transform the initialization code for correct execution in the multithreaded version. Experimental results show that our method provides impressive speedup for six PPSes (Packet Processing Stages) in the widely used NPF IP forwarding benchmarks. For most packet processing stages, our algorithms can achieve almost linear performance improvement after automatic multi-threading transformation. The automatic multi-processing transformation help further boost the speedup of two PPSes.

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: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 10: S. P. Midkiff , D. A. Padua, Compiler algorithms for synchronization, IEEE Transactions on Computers, v.36 n.12, p.1485-1495, Dec. 1987 [doi>10.1109/TC.1987.5009499]
• 11: Jens Knoop, Eliminating partially dead code in explicitly parallel programs, Theoretical Computer Science, v.196 n.1-2, p.365-393, April 6, 1998 [doi>10.1016/S0304-3975(97)00208-9]
• 12: Jens Knoop , Bernhard Steffen , Jürgen Vollmer, Parallelism for free: efficient and optimal bitvector analyses for parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.268-299, May 1996 [doi>10.1145/229542.229545]
• 13: Ramakrishnan Rajamony , Alan L. Cox, Optimally Synchronizing DOACROSS Loops on Shared Memory Multiprocessors, Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, p.214, November 11-15, 1997
• 14: Ding-Kai Chen , Pen-Chung Yew, Redundant Synchronization Elimination for DOACROSS Loops, IEEE Transactions on Parallel and Distributed Systems, v.10 n.5, p.459-470, May 1999 [doi>10.1109/71.770138]
• 15: Ron G. Cytron. Doacross, beyond vectorization for multiprocessors, Proceedings of the International Conference on Parallel Processing, pages 836--844, 1986
• 16: V. P. Krothapalli , P. Sadayappan, Removal of Redundant Dependences in DOACROSS Loops with Constant Dependences, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.281-289, July 1991 [doi>10.1109/71.86104]
• 17: Z.Li and W.Abu-Sufah, "On Reducing Data Synchronization in Multiprocessed Loops," IEEE Trans. Computers, vol. 36, no. 1, pp. 105--109, Jan. 1987
• 18: P.Shaffer, "Minimization of Interprocessor Synchronization in Multiprocessors with Shared and Private Memory", Proc. Int'l Conf. Parallel Processing, vol. III, pp. 138--141, Aug. 1989
• 19: D. Callahan , K. Kennedy , J. Subhlok, Analysis of event synchronization in a parallel programming tool, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.21-30, March 14-16, 1990, Seattle, Washington, United States
• 20: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994 [doi>10.1145/183432.183443]
• 21: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 22: Jonathan Aldrich , Craig Chambers , Emin Gün Sirer , Susan J. Eggers, Static Analyses for Eliminating Unnecessary Synchronization from Java Programs, Proceedings of the 6th International Symposium on Static Analysis, p.19-38, September 22-24, 1999
• 23: Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
• 24: 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
• 25: 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]
• 26: Network Processor Forum (NPF), IP Forwarding Benchmark Implementation Agreements (June 2003), http://www.npforum.org/benchmarking/licenseagm_ipforwarding.shtml.

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:
code motion, critical section, multi-processing, multi-threading, network processor