Taming the IXP network processor

ABSTRACT

We compile Nova, a new language designed for writing network processing applications, using a back end based on integer-linear programming (ILP) for register allocation, optimal bank assignment, and spills. The compiler's optimizer employs CPS as its intermediate representation; some of the invariants that this IR guarantees are essential for the formulation of a practical ILP model.Appel and George used a similar ILP-based technique for the IA32 to decide which variables reside in registers but deferred the actual assignment of colors to a later phase. We demonstrate how to carry over their idea to an architecture with many more banks, register aggregates, variables with multiple simultaneous register assignments, and, very importantly, one where bank- and register-assignment cannot be done in isolation from each other. Our approach performs well in practise---without causing an explosion in size or solve time of the generated integer linear programs.

REFERENCES

• 1: 3GPP. Specification of the 3GPP confidentiality and integrity algorithms. Version 1.2, Sept. 2000.
• 2: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 3: Andrew W. Appel, SSA is functional programming, ACM SIGPLAN Notices, v.33 n.4, p.17-20, April 1998 [doi>10.1145/278283.278285]
• 4: Andrew W. Appel , Lal George, Optimal spilling for CISC machines with few registers, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.243-253, June 2001, Snowbird, Utah, United States
• 5: Andrew W. Appel , David B. MacQueen, A Standard ML compiler, Proceedings of the Functional Programming Languages and Computer Architecture, p.301-324, September 14-16, 1987
• 6: Urban Boquist, Interprocedural register allocation for lazy functional languages, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.270-281, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224215]
• 7: William D. Clinger , Anne H. Hartheimer , Eric M. Ost, Implementation Strategies for First-Class Continuations, Higher-Order and Symbolic Computation, v.12 n.1, p.7-45, April 1999 [doi>10.1023/A:1010016816429]
• 8: CPLEX mixed integer solver. www.cplex.com, 2000.
• 9: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 10: J. Daemen and V. Rijmen. The block cipher rijndael, pages 288--296. LNCS 1820. Springer-Verlag, 2000. J.-J.Quisquater and B.Schneier, Eds.
• 11: J. Daemen and V. Rijmen. Rijndael, the advanced encryption standard. Dr. Dobb's journal, 26(3):137--139, March 2001.
• 12: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 13: Cormac Flanagan , Amr Sabry , Bruce F. Duba , Matthias Felleisen, The essence of compiling with continuations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.237-247, June 21-25, 1993, Albuquerque, New Mexico, United States
• 14: R. Fourer, D. M. Gay, and B. W. Kernighan. AMPL: A Modeling Language for Mathematical Programming. Scientific Press, South San Francisco, CA, 1993.
• 15: Changqing Fu , Kent Wilken, A faster optimal register allocator, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 16: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• 17: E. Grosse and Lakshman Y. N. Network processors applied to IPv4/IPv6 transition. Bell Labs Report.
• 18: Richard A. Kelsey, A correspondence between continuation passing style and static single assignment form, Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, p.13-22, January 23-25, 1995, San Francisco, California, United States
• 19: Timothy Kong , Kent D. Wilken, Precise register allocation for irregular architectures, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.297-307, November 1998, Dallas, Texas, United States
• 20: J. Park , S.-M. Moon, Optimistic Register Coalescing, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.196, October 12-18, 1998
• 21: Bernhard Scholz , Erik Eckstein, Register allocation for irregular architectures, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 22: R. Sharp, M. Blott, M. Coss, B. Ellis, D. Majette, and V. Purohit. Starburst: Building next-generation internet devices. Bell Labs Technical Journal, 6(2):6--17, 2001.
• 23: C. Strachey and C. Wadsworth. Continuations: A mathematical semantics which can deal with full jumps. Technical Monograph PRG-11, Programming Research Group, Oxford University, 1974.
• 24: Sriraman Tallam , Rajiv Gupta, Bitwidth aware global register allocation, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.85-96, January 15-17, 2003, New Orleans, Louisiana, USA
• 25: Youfeng Wu , James R. Larus, Static branch frequency and program profile analysis, Proceedings of the 27th annual international symposium on Microarchitecture, p.1-11, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192725]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Algorithms, Languages, Performance

Keywords:
Intel IXA, bank assignment, code generation, integer linear programming, network processors, programming languages, register allocation