skip to main content
10.1145/1095890.1095895acmconferencesArticle/Chapter ViewAbstractPublication PagesancsConference Proceedingsconference-collections
Article

Resource mapping and scheduling for heterogeneous network processor systems

Published: 26 October 2005 Publication History

Abstract

Task to resource mapping problems are encountered during (i) hardware-software co-design and (ii) performance optimization of Network Processor systems. The goal of the first problem is to find the task to resource mapping that minimizes the design cost subject to all design constraints. The goal of the second problem is to find the mapping that maximizes the performance, subject to all architectural constraints. To meet the design goals in performance, it may be necessary to allow multiple packets to be inside the system at any given instance of time and this may give rise to the resource contention between packets. In this paper, a Randomized Rounding (RR) based solution is presented for the task to resource mapping and scheduling problem. We also proposed two techniques to detect and eliminate the resource contention. We evaluate the efficacy of our RR approach through extensive simulation. The simulation results demonstrate that this approach produces near optimal solutions in almost all instances of the problem in a fraction of time needed to find the optimal solution. The quality of the solution produced by this approach is also better than often used list scheduling algorithm for task to resource mapping problem. Finally, we demonstrate with a case study, the results of a Network Processor design and scheduling problem using our techniques.

References

[1]
K. Chatha and R. Vemuri. Hardware-software partitioning and pipelined scheduling of transformative applications. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 10:193--208, 2002.
[2]
R. Dick, D. Rhodes, and W. Wolf. Tgff: task graphs for free. International Workshop Hardware/Software Codesign, pages 97--101, Mar 1998.
[3]
N. P. Forum. Benchmark implementation agreements. Network Processing Forum, http://www.npforum.org/techinfo/IA.
[4]
Intel. Intel application building blocks design guide. http://www.intel.com/design/network/-products/npfamily/sdk.htm.
[5]
A. Kalavade and P. A. Subrahmanyam. Hardware/software partitioning for multi-function systems. IEEE Transactions on CAD of ICs and Systems, 17(9):516--521, Sep 1998.
[6]
R. Niemann and P. Marwedel. Hardware software partitioning using integer programming. Electronic Design & Test Conference, pages 473--479, 1996.
[7]
M. Palesi and T. Givargis. Multi-objective design space exploration using genetic algorithms. Tenth International Symposium on Hardware/Software Codesign, pages 67--72, May 2002.
[8]
A. Prasad, W. Qui, and R. Mahapatra. Hardware software partitioning of multifunction systems. Design Automation for Embedded Systems, Dec 2002.
[9]
P. Raghavan and C. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proof. Combinatorica, 7:365--374, 1987.
[10]
R. Ramaswamy, N. Neng, and T. Wolf. Application analysis and resource mapping for heterogeneous network processor architectures. Proc. of Third Workshop on Network Processors and Applications (NP-3) in conjunction with Tenth International Symposium on High Performance Computer Architecture (HPCA-10), pages 103--119, Feb 2004.
[11]
L. Thiele, S. Chakraborty, M. Gries, and S. Kunzli. Design space exploration of network processor architectures. First Workshop on Network Processors at the 8th International Symposium on High-Performance Computer Architecture (HPCA8), pages 30--41, 2002.
[12]
H. Vin, J. Mudigonda, J. Jason, E. Johnson, R. Ju, A. Kunze, and R. Lian. A programming environment for packet-processing systems: Design considerations. In the Workshop on Network Processors & Applications - NP3 in conjunction with The 10th International Symposium on High-Performance Computer Architecture, Feb 2004.

Cited By

View all
  • (2014)A Performance Analysis Methodology for Multicore, Multithreaded ProcessorsIEEE Transactions on Computers10.1109/TC.2012.22363:2(276-289)Online publication date: 1-Feb-2014
  • (2014)Computing Resource Allocation with PEADGAConfigurable Intelligent Optimization Algorithm10.1007/978-3-319-08840-2_10(291-331)Online publication date: 19-Aug-2014
  • (2014)Enabling Network Security in HPC Systems Using Heterogeneous CMPsHigh‐Performance Computing on Complex Environments10.1002/9781118711897.ch20(383-399)Online publication date: 18-Apr-2014
  • Show More Cited By

Index Terms

  1. Resource mapping and scheduling for heterogeneous network processor systems

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ANCS '05: Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems
    October 2005
    230 pages
    ISBN:1595930825
    DOI:10.1145/1095890
    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: 26 October 2005

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. HW-SW partitioning
    2. codesign
    3. network processor
    4. randomized rounding

    Qualifiers

    • Article

    Conference

    ANCS05

    Acceptance Rates

    Overall Acceptance Rate 88 of 314 submissions, 28%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)5
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2014)A Performance Analysis Methodology for Multicore, Multithreaded ProcessorsIEEE Transactions on Computers10.1109/TC.2012.22363:2(276-289)Online publication date: 1-Feb-2014
    • (2014)Computing Resource Allocation with PEADGAConfigurable Intelligent Optimization Algorithm10.1007/978-3-319-08840-2_10(291-331)Online publication date: 19-Aug-2014
    • (2014)Enabling Network Security in HPC Systems Using Heterogeneous CMPsHigh‐Performance Computing on Complex Environments10.1002/9781118711897.ch20(383-399)Online publication date: 18-Apr-2014
    • (2012)A study of optimal allocation of computing resources in cloud manufacturing systemsThe International Journal of Advanced Manufacturing Technology10.1007/s00170-012-3939-063:5-8(671-690)Online publication date: 15-Feb-2012
    • (2008)A Fast Performance Analysis Tool for Multicore, Multithreaded Communication ProcessorsProceedings of the 2008 11th IEEE High Assurance Systems Engineering Symposium10.1109/HASE.2008.18(135-144)Online publication date: 3-Dec-2008
    • (2007)Replication-based partial dynamic scheduling on heterogeneous network processorsProceedings of the 7th international conference on Advanced parallel processing technologies10.5555/1785246.1785252(4-13)Online publication date: 22-Nov-2007
    • (2007)Replication-Based Partial Dynamic Scheduling on Heterogeneous Network ProcessorsAdvanced Parallel Processing Technologies10.1007/978-3-540-76837-1_4(4-13)Online publication date: 2007

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media