Integrated scratchpad memory optimization and task scheduling for MPSoC architectures

ABSTRACT

Multiprocessor system-on-chip (MPSoC) is an integrated circuit containing multiple instruction-set processors on a single chip that implements most of the functionality of a complex electronic system. An MPSoC architecture is, in general, customized for an embedded application. A critical component of this customization process is the on-chip memory system configuration. Embedded systems increasingly employ software-controlled scratchpad memory(SPM) due to its inherent advantages in terms of area, energy, and timing predictability compared to caches. An application-specific flexible partitioning of the on-chip SPM budget among the processors is critical for performance optimization. Moreover, scheduling the tasks of an application on to the processors and partitioning the SPM are inter-dependent even though these steps are decoupled in the traditional design space exploration process. In this work, we design an integrated task mapping, scheduling, SPM partitioning, and data allocation technique based on Integer Linear Programming(ILP)formulation. Our ILP formulation explores the optimal performance limit and shows that integrated task schedul-ing and SPM optimization improves performance by up to 80% for embedded applications.

REFERENCES

• 1: Federico Angiolini , Luca Benini , Alberto Caprara, Polynomial-time algorithm for on-chip scratchpad memory partitioning, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951751]
• 2: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 3: Oren Avissar , Rajeev Barua , Dave Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.6-26, November 2002 [doi>10.1145/581888.581891]
• 4: Rajeshwari Banakar , Stefan Steinke , Bo-Sik Lee , M. Balakrishnan , Peter Marwedel, Scratchpad memory: design alternative for cache on-chip memory in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774805]
• 5: L. Benini, D. Bertozzi, A. Guerri, and M. Milano. Allocation and scheduling for mpsocs via decomposition and no-good generation. In International Joint Conferences on Artificial Intelligence (IJCAI), 2005.
• 6: Karam S. Chatha , Ranga Vemuri, Hardware-Software partitioning and pipelined scheduling of transformative applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.3, p.193-208, June 2002 [doi>10.1109/TVLSI.2002.1043323]
• 7: A. Dominguez, S. Udayakumaran, and R. Barua. Heap data allocation to scratch-pad memory in embedded systems. Journal of Embedded Computing, 2005.
• 8: H. Peter Hofstee, Power Efficient Processor Architecture and The Cell Processor, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.258-262, February 12-16, 2005 [doi>10.1109/HPCA.2005.26]
• 9: M. Kandemir and N. Dutt. Memory systems and compiler support for mpsoc architectures. In A. Jerraya and W. Wolf, editors, Multiprocessor Systems-on-Chips. Morgan Kaufmann, 2005.
• 10: Mahmut Kandemir , J. Ramanujam , A. Choudhary, Exploiting shared scratch pad memory space in embedded multiprocessor systems, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513974]
• 11: 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
• 12: Yu-Kwong Kwok , Ishfaq Ahmad, Benchmarking and comparison of the task graph scheduling algorithms, Journal of Parallel and Distributed Computing, v.59 n.3, p.381-422, Dec. 1999 [doi>10.1006/jpdc.1999.1578]
• 13: Samy Meftali , Ferid Gharsalli , Frederic Rousseau , Ahmed A. Jerraya, An optimal memory allocation for application-specific multiprocessor system-on-chip, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500006]
• 14: G. DeMicheli, R. Ernst, and W. Wolf. Readings in Hardware/Software Co-Design. Morgan Kaufmann, 2002.
• 15: R. Niemann and P. Marwedel. Hardware/software partitioning using integer programming. In Design, Automation and Test in Europe (DATE), 1996.
• 16: O. Ozturk , M. Kandemir , G. Chen , M. J. Irwin , M. Karakoy, Customized on-chip memories for embedded chip multiprocessors, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1121008]
• 17: O. Ozturk , G. Chen , M. Kandemir , M. Karakoy, An Integer Linear Programming Based Approach to Simultaneous Memory Space Partitioning and Data Allocation for Chip Multiprocessors, Proceedings of the IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures, p.50, March 02-03, 2006 [doi>10.1109/ISVLSI.2006.22]
• 18: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 19: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, On-chip vs. off-chip memory: the data partitioning problem in embedded processor-based systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.682-704, July 2000 [doi>10.1145/348019.348570]
• 20: Jan Sjödin , Carl von Platen, Storage allocation for embedded processors, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502221]
• 21: S. Steinke , L. Wehmeyer , B. Lee , P. Marwedel, Assigning Program and Data Objects to Scratchpad for Energy Reduction, Proceedings of the conference on Design, automation and test in Europe, p.409, March 04-08, 2002
• 22: 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 (VLSID'05), p.551-556, January 03-07, 2005 [doi>10.1109/ICVD.2005.155]
• 23: M. Y. Wu , D. D. Gajski, Hypertool: A Programming Aid for Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.330-343, July 1990 [doi>10.1109/71.80160]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design, Performance

Keywords:
MPSoC, scheduling, scratchpad memory, task mapping