Effective thread management on network processors with compiler analysis

ABSTRACT

Mapping packet processing tasks on network processor micro-engines involves complex tradeoffs that relating to maximizing parallelism and pipelining. Due to an increase in the size of the code store and complexity of the application requirements, network processors are being programmed with heterogeneous threads that may execute code belonging to different tasks on a given micro-engine. Also, most network applications are streaming applications that are typically processed in a pipelined fashion. Thus, the tasks on different micro-engines are pipelined in such a way as to maximize the throughput. Tasks themselves could have different run time performance demands. Traditionally, runtime management involving processor sharing, real-time scheduling etc. is provided by the runtime environment (typically an operating system) using the hardware support for timers and interrupts that allows time slicing the resource amongst the tasks. However, due to stringent performance requirements on network processors (which process packets from very high speed network traffic), neither OS nor hardware mechanisms are typically feasible/available.In this paper, we show that it is very difficult and inefficient for the programmer to meet the constraints of runtime management by coding them statically. Due to the infeasibility of hardware or OS solution (even in the near future), the only choice left is a compiler approach.We propose a complete compiler solution to automatically insert explicit context switch (ctx) instructions provided on the processors so that the execution of programs is better manipulated at runtime to meet their constraints. We show that such an approach is feasible opening new application domains that would need heterogeneous thread programming. Such approaches would in general become important for multi-core processors.

REFERENCES

• 1: Feliks J. Welfeld, Network processing in content inspection applications, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500047]
• 2: Tammo Spalink , Scott Karlin , Larry Peterson , Yitzchak Gottlieb, Building a robust software-based router using network processors, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 3: Jens Wagner , Rainer Leupers, C Compiler Design for an Industrial Network Processor, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.155-164, August 2001, Snow Bird, Utah, United States
• 4: Jack Liu , Timothy Kong , Fred C. Chow, Effective Compilation Support for Variable Instruction Set Architecture, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.56-67, September 22-25, 2002
• 5: 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
• 6: 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
• 7: "IXP 1200 Network Processor: Programmer's Reference Manual", Part No. 278304-010. Dec. 2001.
• 8: "IXP 1200 Network Processor Family: Hardware Reference Manual", Part No. 278303-009. Dec. 2001.
• 9: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 10: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 11: T. Wolf and M. Franklin, "CommBench -- A Telecommunication Benchmark for Network Processors", ISPASS, 2000.
• 12: Gokhan Memik , William H. Mangione-Smith , Wendong Hu, NetBench: a benchmarking suite for network processors, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 13: Xiaotong Zhuang , Jian Liu, WRAPS Scheduling and Its Efficient Implementation on Network Processors, Proceedings of the 9th International Conference on High Performance Computing, p.252-263, December 18-21, 2002
• 14: Michael Hicks , Pankaj Kakkar , Jonathan T. Moore , Carl A. Gunter , Scott Nettles, PLAN: a packet language for active networks, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.86-93, September 26-29, 1998, Baltimore, Maryland, United States
• 15: C.H.Papadimitriou, M.Yannakakis. "Optimization, Approximation and Complexity Classes", J. Computer and System Sciences, Vol.43, 1991.
• 16: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 17: R.West, C.Poellabauer, "Analysis of a Window-Constrained Scheduler for Real-Time and Best-Effort Packet Streams," RTSS, 2000.
• 18: C.Clark, et.el, "A Hardware Platform for Network Intrusion Detection and Prevention," 3rd Workshop on Network Processor Applications.
• 19: 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
• 20: 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
• 21: 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

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

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

General Terms:
Design, Performance

Keywords:
CPU scheduling, compiler optimizations, network processors, real-time scheduling