skip to main content
10.1145/1134650.1134662acmconferencesArticle/Chapter ViewAbstractPublication PagescpsweekConference Proceedingsconference-collections
Article

Effective thread management on network processors with compiler analysis

Published: 14 June 2006 Publication History

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]
F. J. Welfeld "Network processing in content inspection applications. ISSS 2001," ISSS 2001, Sep. 2001.
[2]
T.Spalink, S.Karlin, L.Peterson, Y.Gottlieb, "Building a Robust Software-Based Router Using Network Processors," SOSP, Oct. 2001.
[3]
J. Wagner and R. Leupers, "C Compiler Design for an Industrial Network Processor", LCTES'01, Jun. 2001.
[4]
J. Liu, T. Kong, and F. Chow, "Effective compilation support for variable instruction set architecture", In Proc. PACT'02, Sep. 2002.
[5]
L. George, M. Blume, "Taming the IXP Network Processor", PLDI'03, Jun. 2003.
[6]
X. Zhuang, S. Pande, "Resolving Register Bank Conflicts for a Network Processor," In Proc. PACT'03, Sep. 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, J.W.Layland, "Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment." J. of ACM, 20, pp. 40--61, 1973.
[10]
A. Demers, S. Keshav, S. Shenker, "Analysis and simulation of a fair queueing algorithm," In Proc. ACM SIGCOMM, Sep. 1989.
[11]
T. Wolf and M. Franklin, "CommBench -- A Telecommunication Benchmark for Network Processors", ISPASS, 2000.
[12]
G.Memik, W.H. Mangione-Smith, and W. Hu., "NetBench: A Benchmarking Suite for Network Processors", ICCAD, Nov. 2001.
[13]
X. Zhuang, J. Liu, "WRAPS Scheduling and Its Efficient Implementation on Network Processors", HiPC 2002, Dec. 2002.
[14]
M. Hicks, P. Kakkar, J. T. Moore, C. A. Gunter, S. Nettles, "PLAN: A Packet Language for Active Networks," ICFP, Sep. 1998.
[15]
C.H.Papadimitriou, M.Yannakakis. "Optimization, Approximation and Complexity Classes", J. Computer and System Sciences, Vol.43, 1991.
[16]
D.M.Tullsen, S.J.Eggers, H.M.Levy, "Simultaneous multithreading: Maximizing on-chip parallelism," ISCA'95, Jun. 1995.
[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]
X.Zhuang, S.Pande, "Balancing Register Allocation Across Threads for a Multithreaded Network Processor", PLDI 2004, Jun. 2004.
[20]
Michael Chen, X.-F Li, R. Lian, J. Lin, L. Liu, T. Liu and R. Ju, Shangri-La: achieving high performance from compiled network applications while enabling ease of programming, PLDI 2005
[21]
J. Dai, Bo Huang, L. Li and L. Harrison, Automatically partitioning packet processing applications for pipelined architectures, PLDI 2005.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
LCTES '06: Proceedings of the 2006 ACM SIGPLAN/SIGBED conference on Language, compilers, and tool support for embedded systems
June 2006
220 pages
ISBN:159593362X
DOI:10.1145/1134650
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 41, Issue 7
    Proceedings of the 2006 LCTES Conference
    July 2006
    208 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/1159974
    Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. CPU scheduling
  2. compiler optimizations
  3. network processors
  4. real-time scheduling

Qualifiers

  • Article

Conference

LCTES06

Acceptance Rates

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 441
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 03 Jan 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media