Automated task distribution in multicore network processors using statistical analysis

ABSTRACT

Chip multiprocessor designs are the most common types of architectures seen in Network Processors. As the Network Processors are used to implement increasingly complicated applications, task distribution among the cores is becoming an important problem. In this paper, we propose a new task allocation scheme for such architectures. This scheme relies on the inherent modular nature of the networking applications and intelligently distributes modules among different execution cores. Additionally, we selectively replicate modules to parallelize execution of tasks having longer processing time. We have developed a technique that uses the probability distribution of the execution times of different modules in the networking applications. The proposed schemes result in resource utilization of up to 95%, 89%, and 84% on average for the processors with 2, 4, and 8 cores, respectively. The schemes are highly scalable and can improve the throughput by 6.72 times for 8 core processors, aggregated over four representative applications. The combination of selective replication of modules and variation-aware task allocation result in up to 12.5% (9.9% on average) performance improvement as compared to a scheme based on just mean processing time.

REFERENCES

• 1: F. Baker, Requirements for IP Version 4 Routers, RFC Editor, 1995
• 2: Burger, D. and T. Austin, The SimpleScalar Tool Set, Version 2.0. 1997, Univ. of Wisconsin-Madison, Comp. Sci. Dept.
• 3: Chandra Chekuri, Approximation Algorithms for Scheduling Problems, Stanford University, Stanford, CA, 1998
• 4: 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, ACM SIGPLAN Notices, v.40 n.6, June 2005
• 5: Datar, S. and M. A. Franklin, Task Scheduling of Processor Pipelines with Application to Network Processors, Department of Computer Science and Engineering, Washington University in St. Louis.
• 6: Devadas, S. and A. R. Newton., Algorithms for Hardware Allocation in Datapath Synthesis. IEEE Trans. On CAD, July 1989. 8, No. 7, pp. 768--781,(7).
• 7: Michael I. Gordon , William Thies , Saman Amarasinghe, Exploiting coarse-grained task, data, and pipeline parallelism in stream programs, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 8: Intel. The Intel® Pentium® 4 processor - Product Briefs, {http://www.intel.com/design/Pentium4/prodbref/index.htm}.
• 9: Intel, Intel® IXP2400 Network Processor Thermal and Mechanical Design Guideline. March 2003.
• 10: Intel, C., Intel® IXP2800 Network Processor Product Brief. 2002: Santa Clara/CA.
• 11: Kohler, E. The Click Modular Router Project. in http://pdos.csail.mit.edu/click.
• 12: 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]
• 13: McMahan, S., et al. A 600 MHz NT3 network processor. in The Digest of Technical Papers for IEEE International Solid-State Circuits Conference (ISSCC). 2003.
• 14: Memik, G. and W. H. Mangione-Smith. NEPAL: A Framework for Efficiently Structuring Applications for Network Processors. in Workshop on Network Processors -- NP2 (held in conjunction with HPCA). Feb. 2003. Anaheim, CA.
• 15: Motorola, C-5 Network Processor Fact Sheet. Oct. 2001.
• 16: Plishker, W., et al. Automated Task Allocation for Network Processors. in Network System Design Conference Proceedings. October, 2004.
• 17: J. Postel, Internet Control Message Protocol, RFC Editor, 1981
• 18: Postel, J., Internet Protocol. RFC 791 (Sept.), Internet Engineering Task Force. ftp://ftp.ietf.org/rfc/rfc0791.txt, 1981.
• 19: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round robin, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.231-242, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 20: Hadas Shachnai , Tami Tamir, Polynominal time approximation schemes for class-constrained packing problem, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.238-249, September 05-08, 2000
• 21: Shah, N., W. Plishker, and K. Keutzer. NP-Click: A Programming Model for the Intel IXP1200. in 2nd Workshop on Network Processors (NP-2) at the 9th International Symposium on High Performance Computer Architecture (HPCA-9). February, 2003. Anaheim, CA.
• 22: Srinivasan, A., Multiprocessor Scheduling in Processor-based Router Platforms: Issues and Ideas. Network Processor Design:Issues and Practices, November 2003.
• 23: Tsai, M., et al. A Benchmarking Methodology for Network Processors. in 1st Network Processor Workshop, 8th Int. Symposium on High Performance Architectures. 2002.
• 24: Vin, H.M., et al. A Programming Environment for Packet-processing Systems: Design Considerations. in The Workshop on Network Processors & Applications - NP3. Held in conjunction with The 10th International Symposium on High-Performance Computer Architecture 2004.
• 25: Wheeler, B. and L. Gwennap, A Guide to Metro Network Processors. 8 ed. December, 2006: The Linley Group.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

General Terms:
Algorithms, Performance