article

ILP and heuristic techniques for system-level design on network processor architectures

Authors:

Karam S. Chatha,

Vijay Ramamurthi,

Krishnan SrinivasanAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 12, Issue 4

Pages 48 - es

https://doi.org/10.1145/1278349.1278361

Published: 01 September 2007 Publication History

Abstract

Network processors incorporate several architectural features, including symmetric multiprocessing (SMP), block multithreading, and multiple memory elements, to support the high-performance requirements of current day applications. This article presents automated system-level design techniques for application development on such architectures. We propose integer linear programming formulations and heuristic techniques for process allocation and data mapping on SMP and block-multithreading-based network processors. The techniques incorporate process transformations and multithreading-aware data mapping to maximize the throughput of the application. The article presents experimental results that evaluate the techniques by implementing network processing applications on the Intel IXP 2400 architecture.

References

[1]

3GPP Organizational Partners. 2002. 3GPP confidentiality and integrity algorithms F8 and F9. http://www.3gpp.org/TB/Other/algorithms.htm.

[2]

Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., and Kann, V. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer.

Digital Library

[3]

Bender, A. 1996. Milp based task mapping for heterogeneous multiprocessor systems. In Proceedings of the Conference on European Design Automation. IEEE Computer Society Press, 190--197.

Digital Library

[4]

Blake, S. 1998. An Architecture for differentiated services. Request for Comments - 2475, Internet Engineering Task Force (IETF).

[5]

Campbell, A., Chou, S., Kounavis, M., Stachtos, V., and Vicente, J. 2002. Netbind: A binding tool for constructing data paths in network processor-based routers. In Proceedings of the IEEE Conference on Open Architectures and Network Programming. 91--103

[6]

Chekuri, C. 2000. Approximation algorithms for scheduling problems. Tech. Rep. CS-TR-98-116, Computer Science Department of Stanford University.

[7]

Chen, M.K., Li, X.F., Lian, R., Lin, J.H., Liu, L., Liu, T., and Ju, R. 2005. Shangri-La: Achieving high performance from compiled network applications while enabling ease of programming. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM Press, New York, 224--236.

Digital Library

[8]

Haas, R., Jeffries, C., Kencl, L., Kind, A., Metzler, B., Pletka, R., Waldvogel, M., Freléchoux, L., and Droz, P. 2002. Creating advanced functions on network processors: Experience and perspectives. Res. Rep. RZ--3460, IBM. November.

[9]

Hwang, C.-T., Lee, J.-H., and Hsu, Y.-C. 1991. A formal approach to scheduling problem in high level synthesis. IEEE Trans. Comput.-Aided Design Integrated Circ. Syst. 10, 464--475.

Digital Library

[10]

Intel. 2007. INTEL IXA SDK.

[11]

Johnson, E.J. and Kunze, A.R. 2003. IXP2400/2800 Programming: The Complete Microengine Coding Guide. Intel Press, Hillsboro, OR.

Digital Library

[12]

Keller, R., Ruf, L., Guindehi, A., and Plattner, B. 2002. Promethos: A dynamically extensible router architecture for active networks. In Proceedings of Active Networks 4th International Conference. 20--31.

Digital Library

[13]

Kulkarni, C., Gries, M., Sauer, C., and Keutzer, K. 2003. Programming challenges in network processor deployment. In Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES), 178--187.

Digital Library

[14]

Lee, K., Coulson, G., Blair, G., Joolia, A., and Ueyama, J. 2004. Towards a generic programming model for network processors. In Proceedings of the IEEE International Conference on Networks.

[15]

Morris, R., Kohler, E., Jannotti, J., and Kaashoek, M.F. 1999. The click modular router. In Proceedings of the Symposium on Operating Systems Principles. 217--231.

Digital Library

[16]

Ostler, C. and Chatha, K.S. 2007. An ilp formulation for system-level application mapping on network processor architectures. IEEE/ACM In the Conference on Design, Automation, and Test in Europe.

Digital Library

[17]

Plishker, W., Ravindran, K., Shah, N., and Keutzer, K. 2004. Automated task allocation on single chip, hardware multithreaded, multiprocessor systems. In Proceedings of the Workshop on Embedded Parallel Architectures (WEPA), 14--20.

[18]

Ramakrishna, S. and Jamadagni, H. 2003. Analytical bounds on the threads in IXP1200 network processor. In Proceedings of the Euromicro Symposium on Digital System Design, 426--429.

Digital Library

[19]

Ramamurthi, V., McCollum, J., Ostler, C., and Chatha, K.S. 2005. System level methodology for programming cmp based multi-threaded network processor architectures. In International Symposium on VLSI.

Digital Library

[20]

Ramaswamy, R., Weng, N., and Wolf, T. 2005. Application analysis and resource mapping for heterogeneous network processor architectures. In Network Processor Design: Issues and Practices, Vol. 3. M.A. Franklin et al. eds. Morgan Kaufmann Chapter 13, 277--306.

[21]

Ramaswamy, R. and Wolf, T. 2003. Packetbench: A tool for workload characterization of network processing. In Proceedings of the IEEE 6th Annual Workshop on Workload Characterization.

[22]

RFC. 1981. Request for comments 791, Internet Protocol Specification. http://www.faqs.org/rfcs/rfc791.html.

[23]

Roberts, L.G. 2000. Beyond Moore's law: Internet growth trends. IEEE Comput., 117--119.

Digital Library

[24]

Shachnai, H. and Tamir, T. 1999. Polynomial time approximation schemes for class-constrained packing problems. In Proceedings of Aproximation Algorithms for Combinatorial Optunization 3rd International Workshop. 123--138.

Digital Library

[25]

Shah, N. 2001. Understanding network processors. M.S. thesis, University of California, Berkeley.

[26]

Shah, N. and Keutzer, K. 2002. Network processors: Origin of species. In Proceedings of the 17th International Symposium on Computer and Information Sciences.

[27]

Shah, N., Plishker, W., and Keutzer, K. 2003. NP-Click: A programming model for the Intel ixp1200. In Proceedings of the 2nd Workshop on Network Processors at the 9th International Symposium on High Performance Computer Architecture.

[28]

Shirazi, B.A., Kavi, K.M., and Hurson, A.R., eds. 1995. Scheduling and Load Balancing in Parallel and Distributed Systems. IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

[29]

Srinivasan, A., Holman, P., Anderson, J., Baruah, S., and Kaur, J. 2003. Multiprocessor scheduling in processor-based router platforms: Issues and ideas. In Proceedings of the 2nd Workshop on Network Processors at the 9th International Symposium on High Performance Computer Architecture.

[30]

Tan, Z., Lin, C., Yin, H., and Li, B. 2004. Optimization and benchmark of cryptographic algorithms on network processors. IEEE Micro. 24, 5, 55--69.

Digital Library

[31]

Teja Corporation. 2006. Teja NP software platform for the intel IXP2XXX network processor family. http://www.teja.com/products/intel_ixp2xxx.html.

[32]

Thiele, L., Chakraborty, S., Gries, M., and Knzli, S. 2002. Design space exploration of network processor architectures. In Proceedings of the 1st Workshop on Network Processors at the 8th International Symposium on High Performance Computer Architecture.

[33]

Weng, N. and Wolf, T. 2005. Profiling and mapping of parallel workloads on network processors. In Proceedings of the 20th Annual ACM Symposium on Applied Computing (SAC) (Santa Fe, NM), 890--896.

Digital Library

[34]

Wheeler, B., Bolaria, J., and Iyer, S. 2005. NPU market sees broad-based expansion. http://www.linleygroup.com/npu/Newsletter/wire050420.html.

Cited By

Bonfietti ALombardi MMilano MBenini L(2013)Maximum-throughput mapping of SDFGs on multi-core SoC platformsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2013.05.00473:10(1337-1350)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1016/j.jpdc.2013.05.004
Lee HChe WChatha KJerraya ACarloni LChang NFummi F(2012)Dynamic scheduling of stream programs on embedded multi-core processorsProceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/2380445.2380465(93-102)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2380445.2380465
Che WChatha KGroeneveld PSciuto DHassoun S(2012)Unrolling and retiming of stream applications onto embedded multicore processorsProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228598(1272-1277)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228598
Show More Cited By

Index Terms

ILP and heuristic techniques for system-level design on network processor architectures
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation

Recommendations

An ILP formulation for system-level application mapping on network processor architectures
DATE '07: Proceedings of the conference on Design, automation and test in Europe

Current day network processors incorporate several architectural features including symmetric multi-processing (SMP), block multi-threading, and multiple memory elements to support the high performance requirements of networking applications. We present ...
Dynamically allocating processor resources between nearby and distant ILP
Special Issue: Proceedings of the 28th annual international symposium on Computer architecture (ISCA '01)

Modern superscalar processors use wide instruction issue widths and out-of-order execution in order to increase instruction-level parallelism (ILP). Because instructions must be committed in order so as to guarantee precise exceptions, increasing ILP ...
Exploiting an abstract-machine-based framework in the design of a Java ILP processor

Abstract machines bridge the gap between the high-level of programming languages and the low-level mechanisms of a real machine. The paper proposed a general abstract-machine-based framework (AMBF) to build instruction level parallelism processors using ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 12, Issue 4

September 2007

449 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1278349

Issue’s Table of Contents

Copyright © 2007 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 September 2007

Published in TODAES Volume 12, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
473
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bonfietti ALombardi MMilano MBenini L(2013)Maximum-throughput mapping of SDFGs on multi-core SoC platformsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2013.05.00473:10(1337-1350)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1016/j.jpdc.2013.05.004
Lee HChe WChatha KJerraya ACarloni LChang NFummi F(2012)Dynamic scheduling of stream programs on embedded multi-core processorsProceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/2380445.2380465(93-102)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2380445.2380465
Che WChatha KGroeneveld PSciuto DHassoun S(2012)Unrolling and retiming of stream applications onto embedded multicore processorsProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228598(1272-1277)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228598
Che WPanda AChatha KDe Micheli GAl-Hashimi BMueller WMacii E(2010)Compilation of stream programs for multicore processors that incorporate scratchpad memoriesProceedings of the Conference on Design, Automation and Test in Europe10.5555/1870926.1871198(1118-1123)Online publication date: 8-Mar-2010
https://dl.acm.org/doi/10.5555/1870926.1871198
Weijia Che Panda AChatha K(2010)Compilation of stream programs for multicore processors that incorporate scratchpad memories2010 Design, Automation & Test in Europe Conference & Exhibition (DATE 2010)10.1109/DATE.2010.5456976(1118-1123)Online publication date: Mar-2010
https://doi.org/10.1109/DATE.2010.5456976
Tumeo ABranca MCamerini LPilato CLanzi PFerrandi FSciuto DRosenstiel WWakabayashi K(2009)Mapping pipelined applications onto heterogeneous embedded systemsProceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis10.1145/1629435.1629495(443-452)Online publication date: 11-Oct-2009
https://dl.acm.org/doi/10.1145/1629435.1629495
Soewito BWeng N(2009)Concurrent workload mapping for multicore security systemsConcurrency and Computation: Practice and Experience10.1002/cpe.142321:10(1281-1306)Online publication date: 16-Apr-2009
https://doi.org/10.1002/cpe.1423

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents