Analytic modeling of network processors for parallel workload mapping

ABSTRACT

Network processors are heterogeneous system-on-chip multiprocessors that are optimized to perform packet forwarding and processing tasks at Gigabit data rates. To meet the performance demands of increasing link speeds and complex network applications, network processors are implemented with several dozen embedded processor cores and hardware accelerators that run multiple packet processing applications in parallel. The parallel nature of the processing system makes it increasingly difficult for application developers to understand and manage resources and map processing tasks to the hardware. To address this problem, we present a methodology for profiling and analyzing network processor applications, mapping processing tasks to a generalized network processor architecture, and analytically determining the expected throughput performance. The key novelty of this work is not only the adaptation of application analysis and mapping algorithms to heterogeneous network processors, but also that the entire process can be automated and hidden from the application developer. Starting with the analysis of a uniprocessor implementation of the application, the process yields a mapping of the partitioned application that shows best performance for a given network processor system. The simplicity of the proposed randomized mapping algorithm allows the use of this methodology in network processor runtime systems where dynamic reallocation of tasks is necessary but processing power is limited. We present results that show the effectiveness of the analysis and mapping methodology as well as its application to design space exploration.

REFERENCES

• 1: A. Agarwal, Performance Tradeoffs in Multithreaded Processors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.525-539, September 1992 [doi>10.1109/71.159037]
• 2: Austin, T. M. and Sohi, G. S. 1993. Tetra: evaluation of serial program performance on fine-grain parallel processors. Tech. rep. 1163, Computer Science Department, University of Wisconsin, Madison.
• 3: F. Baker, Requirements for IP Version 4 Routers, RFC Editor, 1995
• 4: D. P. Bhandarkar, Analysis of Memory Interference in Multiprocessors, IEEE Transactions on Computers, v.24 n.9, p.897-908, September 1975 [doi>10.1109/T-C.1975.224335]
• 5: Daemen, J. and Rijmen, V. 2000. The block cipher Rijndael. Lecture Notes in Computer Science. Vol. 1820. Springer-Verlag, Berlin, Germany, 288--296.
• 6: L. W. Dowdy , E. Rosti , G. Serazzi , E. Smirni, Scheduling issues in high-performance computing, ACM SIGMETRICS Performance Evaluation Review, v.26 n.4, p.60-69, March 1999 [doi>10.1145/309746.309756]
• 7: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 8: Franklin, M. A. and Wolf, T. 2002. A network processor performance and design model with benchmark parameterization. In Proceedings of the 1st Network Processor Workshop (NP-1) in Conjunction with the 8th International Symposium on High-Performance Computer Architecture (HPCA-8). ACM, New York, 63--74.
• 9: Franklin, M. A. and Wolf, T. 2003. Power considerations in network processor design. In Proceedings of the 2nd Network Processor Workshop (NP-2) in Conjunction with 9th International Symposium on High-Performance Computer Architecture (HPCA-9). ACM, New York, 10--22.
• 10: Goglin, S. D., Hooper, D., Kumar, A., and Yavatkar, R. 2003. Advanced software framework, tools, and languages for the IXP family. Intel Tech. J. 7, 4, 64--76.
• 11: Grasso et al., P. A. 1984. Memory interference in multimicroprocessor systems with a time-shared bus. Proc. IEEE 131, 10.
• 12: Gries, M., Kulkarni, C., Sauer, C., and Keutzer, K. 2003. Exploring trade-offs in performance and programmability of processing element topologies for network processors. In Proceedings of the 2nd Network Processor Workshop (NP-2) in Conjunction with 9th International Symposium on High-Performance Computer Architecture (HPCA-9). ACM, New York, 75--87.
• 13: C. H. Hoogendoorn, A General Model for Memory Interference in Multiprocessors, IEEE Transactions on Computers, v.26 n.10, p.998-1005, October 1977 [doi>10.1109/TC.1977.1674734]
• 14: Intel Corporation 2003. Intel IXA software developers Kit 2.01.
• 15: Ujval J. Kapasi , Scott Rixner , William J. Dally , Brucek Khailany , Jung Ho Ahn , Peter Mattson , John D. Owens, Programmable Stream Processors, Computer, v.36 n.8, p.54-62, August 2003 [doi>10.1109/MC.2003.1220582]
• 16: Richard M. Karp, An introduction to randomized algorithms, Discrete Applied Mathematics, v.34 n.1-3, p.165-201, Nov. 1991 [doi>10.1016/0166-218X(91)90086-C]
• 17: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 18: Kokku, R., Riché, T., Kunze, A., Mudigonda, J., Jason, J., and Vin, H. 2003. A case for run-time adaptation in packet processing systems. In Proceedings of the 2nd Workshop on Hot Topics in Networks (HOTNETSII). Cambridge, MA.
• 19: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 20: Vijay Lakamraju , Israel Koren , C. M. Krishna, Filtering Random Graphs to Synthesize Interconnection Networks with Multiple Objectives, IEEE Transactions on Parallel and Distributed Systems, v.13 n.11, p.1139-1149, November 2002 [doi>10.1109/TPDS.2002.1058097]
• 21: B. A. Malloy , E. L. Lloyd , M. L. Soffa, Scheduling DAG's for Asynchronous Multiprocessor Execution, IEEE Transactions on Parallel and Distributed Systems, v.5 n.5, p.498-508, May 1994 [doi>10.1109/71.282560]
• 22: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 23: Nilsson, S. and Karlsson, G. 1999. IP-address lookup using LC-tries. IEEE J. Sel. Areas Comm. 17, 6, 1083--1092.
• 24: Ramaswamy, R., Weng, N., and Wolf, T. 2004. Application analysis and resource mapping for heterogeneous network processor architectures. In Proceedings of the 3rd Workshop on Network Processors and Applications (NP-3) in Conjunction with the 10th International Symposium on High Performance Computer Architecture (HPCA-10). ACM, New York, 103--119.
• 25: R. Ramaswamy , Ning Weng , T. Wolf, Analysis of Network Processing Workloads, Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, 2005, p.226-235, March 20-22, 2005 [doi>10.1109/ISPASS.2005.1430577]
• 26: 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 (WWC-6). IEEE, Los Alamitos, CA, 42--50.
• 27: Gerald L. Reijns , Arjan J. C. van Gemund, Analysis of a shared-memory multiprocessor via a novel queuing model, Journal of Systems Architecture: the EUROMICRO Journal, v.45 n.14, p.1189-1193, July 1999 [doi>10.1016/S1383-7621(98)00028-9]
• 28: Shah, N., Plishker, W., and Keutzer, K. 2003. NP-Click: A programming model for the intel IXP1200. In Proceedings of the 2nd Network Processor Workshop (NP-2) in Conjunction with 9th International Symposium on High-Performance Computer Architecture (HPCA-9). ACM, New York, 100--111.
• 29: Michael Bedford Taylor , Jason Kim , Jason Miller , David Wentzlaff , Fae Ghodrat , Ben Greenwald , Henry Hoffman , Paul Johnson , Jae-Wook Lee , Walter Lee , Albert Ma , Arvind Saraf , Mark Seneski , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs, IEEE Micro, v.22 n.2, p.25-35, March 2002 [doi>10.1109/MM.2002.997877]
• 30: Teja Technologies. 2003. TejaNP datasheet. Teja Technologies. http://www.teja.com.
• 31: Thiele, L., Chakraborty, S., Gries, M., and Künzli, S. 2002. Design space exploration of network processor architectures. In Proceedings of the 1st Network Processor Workshop (NP-1) in Conjunction with the 8th International Symposium on High-Performance Computer Architecture (HPCA-8). ACM, New York, 30--41.
• 32: Arjan J. C. van Gemund, Performance prediction of parallel processing systems: the PAMELA methodology, Proceedings of the 7th international conference on Supercomputing, p.318-327, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.166002]
• 33: Wei, Y.-C. and Cheng, C.-K. 1991. Ratio cut partitioning for hierarchical designs. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 10, 7, 911--921.
• 34: T. Wolf , M. Franklin, CommBench-a telecommunications benchmark for network processors, Proceedings of the 2000 IEEE International Symposium on Performance Analysis of Systems and Software, p.154-162, April 24-25, 2000
• 35: Tilman Wolf , Ning Weng , Chia-Hui Tai, Design considerations for network processor operating systems, Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA [doi>10.1145/1095890.1095901]

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

General Terms:
Design, Performance

Keywords:
Application profiling, embedded systems, multiprocessor scheduling, network processors