An automated exploration framework for FPGA-based soft multiprocessor systems

ABSTRACT

FPGA-based soft multiprocessors are viable system solutions for high performance applications. They provide a software abstraction to enable quick implementations on the FPGA. The multiprocessor can be customized for a target application to achieve high performance. Modern FPGAs provide the capacity to build a variety of micro-architectures composed of 20-50 processors, complex memory hierarchies, heterogeneous interconnection schemes and custom co-processors for performance critical operations. However, the diversity in the architectural design space makes it difficult to realize the performance potential of these systems. In this paper we develop an exploration framework to build efficient FPGA multiprocessors for a target application. Our main contribution is a tool based on Integer Linear Programming to explore micro-architectures and allocate application tasks to maximize throughput. Using this tool, we implement a soft multiprocessor for IPv4 packet forwarding that achieves a throughput of 2 Gbps, surpassing the performance of a carefully tuned hand design.

REFERENCES

• 1: EEMBC. http://www.eembc.org/.
• 2: ILOG CPLEX. http://www.ilog.com/products/cplex/.
• 3: A. Atamtürk and M. W. Savelsbergh. Integer Programming Software Systems. Technical Report BCOL.03.01, IEOR, University of California at Berkeley, January 2003.
• 4: Chris Rowen, Tensilica Inc. Fundamental Change in MPSoCs: A fifteen year outlook. In MPSOC'03 Workshop Proceedings. International Seminar on Application-Specific Multi-Processor SoC, 2003.
• 5: Martin Grajcar, Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system, Proceedings of the 36th ACM/IEEE conference on Design automation, p.280-285, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309931]
• 6: M. Gries and Y. Jin. Comprehensively Exploring the Design Space. In M. Gries and K. Keutzer, editors, Building ASIPs: The MESCAL Methodology, pages 131--178. Springer Inc., 2005.
• 7: M. Gries and K. Keutzer, editors. Building ASIPs: The MESCAL Methodology. Springer Inc., 2005.
• 8: P. D. Hoang and J. M. Rabaey. Scheduling of DSP Programs onto Multiprocessors for Maximum Throughput. In IEEE Transactions on Signal Processing, volume 41, pages 2225--2235, June 1993.
• 9: K. Ravindran, N. Satish, Y. Jin, and K. Keutzer. An FPGA-based Soft Multiprocessor System for IPv4 Packet Forwarding. In International Conference on Field Programmable Logic and Applications (FPL), August 2005.
• 10: M. Ruiz-Sánchez, E. Biersack, and W. Dabbous. Survey and Taxonomy of IP Address Lookup Algorithms. Network, IEEE, Vol.15, Iss.2, pages 8--23, March-April 2001.
• 11: Xilinx, Inc. Embedded Systems Tools Guide, Xilinx Embedded Development Kit, EDK version 6.2i edition, June 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
FPGA, IPv4 packet forwarding, design space exploration, integer linear programming, soft multiprocessors