Synthesis of heterogeneous pipelined multiprocessor systems using ILP: jpeg case study

ABSTRACT

Streaming applications can be implemented with a pipeline of processors. Each processor in the pipeline can be an application Specific Instruction Set Processor (ASIP) with the result being a heterogeneous pipelined MPSoC system. Since ASIPs can be of differing configurations, finding the optimal set of configurations for a multiprocessor architecture is a difficult problem.

In this paper, we obtain an optimal system design for a set of processors which execute a multimedia application. The variables in the system are the presence or absence of different additional instructions and differing cache configurations for each of the processors. The problem is formulated as a 0-1 Integer Linear Programming (ILP) problem. To reduce the complexity of the ILP formulation, inferior ASIP configurations are efficiently pruned so that the solution could be reached quickly. Given a system runtime constraint, the proposed methodology finds a design with minimal area. We integrated this design methodology into a commercial design flow, and performed a case study upon the JPEG encoding application. We obtained 15 optimal designs subject to 15 different runtime constraints, each in less than 100 seconds from more than 4.2 x 10¹³ design points.

REFERENCES

• 1: Altera Nios Processor. Altera Corp. (http://www.altera.com).
• 2: ARC the leader in configurable processor technology. ARC International (http://www.arc.com).
• 3: lp solve. Available at: http://lpsolve.sourceforge.net/5.5/.
• 4: Xtensa Processor. Tensilica Inc. (http://www.tensilica.com).
• 5: Flix: Fast relief for performance-hungry embedded applications, 2005. Available at: http://www.tensilica.com/pdf/FLIX White Paper v2.pdf.
• 6: XPRES Generated Specialized Operations, 2005. Available at: http://tensilica.com/pdf/XPRES%201205.pdf
• 7: S. Banerjee, T. Hamada, P. Chau, and R. Fellman. Macro pipelining based scheduling on high performance heterogeneous multiprocessor systems. Signal Processing, IEEE Transactions on, 43(6):1468--1484, 1995.
• 8: A. Beric, R. Sethuraman, C. Pinto, H. Peters, G. Veldman, P. van de Haar, and M. Duranton. Heterogeneous multiprocessor for high definition video. Consumer Electronics, 2006. ICCE '06. 2006 Digest of Technical Papers. International Conference on, pages 401--402, 7-11 Jan. 2006.
• 9: Jason Cong , Guoling Han , Wei Jiang, Synthesis of an application-specific soft multiprocessor system, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216934]
• 10: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 11: J. DeSouza-Batista and A. Parker. Optimal synthesis of application specific heterogeneous pipelined multiprocessors. Application Specific Array Processors, 1994. Proceedings., International Conference on, pages 99--110, 22-24 Aug 1994.
• 12: J. Jeon and K. Choi. Loop pipelining in hardware-software partitioning. In Asia and South Pacific Design Automation Conference, pages 361--366, 1998.
• 13: Takeshi Kodaka , Keiji Kimura , Hironori Kasahara, Multigrain Parallel Processing for JPEG Encoding on a Single Chip Multiprocessor, Proceedings of the International Workshop on Innovative Architecture for Future Generation High-Performance Processors and Systems (IWIA'02), p.57, January 10-11, 2002
• 14: Shiann-Rong Kuang , Chin-Yang Chen , Ren-Zheng Liao, Partitioning and Pipelined Scheduling of Embedded System Using Integer Linear Programming, Proceedings of the 11th International Conference on Parallel and Distributed Systems - Workshops (ICPADS'05), p.37-41, July 20-22, 2005
• 15: M. Schwiegershausen , P. Pirsch, A formal approach for the optimization of heterogeneous multiprocessors for complex image processing schemes, Proceedings of the conference on European design automation, p.8-13, September 18-22, 1995, Brighton, England
• 16: S. L. Shee. ADAPT: Architectural and Design Exploration for Application Specific Instruction-set Processor Technologies. PhD thesis, School of CSE, University of New South Wales, Sydney, September 2007.
• 17: Seng Lin Shee , Andrea Erdos , Sri Parameswaran, Heterogeneous multiprocessor implementations for JPEG:: a case study, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176307]
• 18: Seng Lin Shee , Sri Parameswaran, Design methodology for pipelined heterogeneous multiprocessor system, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278682]
• 19: M. Strik, A. Timmer, J. van Meerbergen, and G.-J. van Rootselaar. Heterogeneous multiprocessor for the management of real-time video and graphics streams. Solid-State Circuits, IEEE Journal of, 35(11):1722--1731, Nov 2000.
• 20: Fei Sun , Srivaths Ravi , Anand Raghunathan , Niraj K. Jha, Synthesis of Application-Specific Heterogeneous Multiprocessor Architectures Using Extensible Processors, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design, p.551-556, January 03-07, 2005 [doi>10.1109/ICVD.2005.155]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Heterogeneous (hybrid) systems

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies; Modeling techniques

General Terms:
Algorithms, Design, Performance

Keywords:
MPSoCs, design space exploration, integer linear programming