Automatic data partitioning for the agere payload plus network processor

ABSTRACT

With the ever-increasing pervasiveness of the Internet and its stringent performance requirements, network system designers have begun utilizing specialized chips to increase the performance of network functions. To increase performance, many more advanced functions, such as traffic shaping and policing, are being implemented at the network interface layer to reduce delays that occur when these functions are handled by a general-purpose CPU. While some designs use ASICs to handle network functions, many system designers have moved toward using programmable network processors due to their increased exibility and lower design cost. In this paper, we describe a code generation technique designed for the Agere Payload Plus network processor. This processor utilizes a multi-block pipeline containing a Fast Pattern Processor (FPP) for classification, a Routing Switch Processor (RSP) for traffic management and a third block, the Agere Systems Interface (ASI), which provides additional functionality for performance. This paper focuses on code generation for the clustered VLIW compute engines on the RSP. Currently, due to the real-time nature of the applications run on the APP, the programmer must lay out and partition the application-specific data by hand to get good performance.The major contribution of this paper is to remove the need for hand partitioning for the RSP compute engines. We propose both a greedy code-generation approach that achieves harmonic mean performance equal to code that has been hand partitioned by an application programmer and a genetic algorithm that achieves a harmonic mean speedup of 1.08 over the same hand-partitioned code. Achieving harmonic mean performance that is equal to or better than hand partitioning removes the need to hand code for performance. This allows the programmer to spend more time on algorithm development.

REFERENCES

• 1: Alex Aletà , Josep M. Codina , F. Jesús Sánchez , Antonio González , David R. Kaeli, Exploiting Pseudo-Schedules to Guide Data Dependence Graph Partitioning, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.281-290, September 22-25, 2002
• 2: Vicki Allan , Steven J. Beaty , Bogong Su , Philip H. Sweany, Building a retargetable local instruction scheduler, Software—Practice & Experience, v.28 n.3, p.249-283, March 1998 [doi>10.1002/(SICI)1097-024X(199803)28:3<249::AID-SPE152>3.0.CO;2-X]
• 3: N. C. Audsley, A. Burns, M. F. Richardson, and A. J. Wellings. Hard real-time scheduling: The deadline monotonic approach. In Proceedings 8th IEEE Workshop on Real-Time Operating Systems and Software, Atlanta, GA, 1991.
• 4: G. Desoli. Instruction assignment for clustered VLIW DSP compilers: A new approach. HP Labs Technical Report HPL-98-13, HP Labs, Jan. 1998.
• 5: J. R. Ellis. A Compiler for VLIW Architectures. PhD thesis, Yale University, 1984.
• 6: 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
• 7: Jason Hiser , Steve Carr , Philip Sweany, Global Register Partitioning, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.13, October 15-19, 2000
• 8: Register Assignment for Software Pipelining with Partitioned Register Banks, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.211, May 01-05, 2000
• 9: Rainer Leupers, Instruction Scheduling for Clustered VLIW DSPs, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.291, October 15-19, 2000
• 10: Erik Nystrom , Alexandre E. Eichenberger, Effective cluster assignment for modulo scheduling, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.103-114, November 1998, Dallas, Texas, United States
• 11: Emre Özer , Sanjeev Banerjia , Thomas M. Conte, Unified assign and schedule: a new approach to scheduling for clustered register file microarchitectures, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.308-315, November 1998, Dallas, Texas, United States
• 12: V. Rayward-Smith, I. Osman, C. Reeves, and G. Smith. Modern Heuristic Search Methods. John Wiley and Sons, Ltd., 1996.
• 13: D. Sule, P. Sweany, and S. Carr. Evaluating register partitioning with genetic algorithms. In Proceedings of the Fourth International Conference on Massively Parallel Computing Systems, Ischia, Italy, April 2002.
• 14: D. Whitley. An overview of evolutionary algorithms. Journal of Information and Software Technology, 43:817--831, 2001.
• 15: Xiaotong Zhuang , Santosh Pande, Resolving Register Bank Conflicts for a Network Processor, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.269, September 27-October 01, 2003

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, Languages

Keywords:
network processors, partitioning, scheduling