Dynamic thread and data mapping for NoC based CMPs

ABSTRACT

Thread mapping and data mapping are two important problems in the context of NoC (network-on-chip) based CMPs (chip multiprocessors). While a compiler can determine suitable mappings for data and threads, such static mappings may not work well for multithreaded applications that go through different execution phases during their execution, each phase with potentially different data access patterns than others. Instead, a dynamic mapping strategy, if its overheads can be kept low, may be a more promising option. In this work, we present dynamic (runtime) thread and data mappings for NoC based CMPs. The goal of these mappings is to reduce the distance between the location of the core that requests data and the core whose local memory contains that requested data. In our experiments, we evaluate our proposed thread mapping and data mapping in isolation as well as in an integrated manner.

REFERENCES

• 1: Xpress-mp. http://www.dashoptimization.com/pdf/Mosel1.pdf, 2002.
• 2: J. H. Anderson and J. M. Calandrino. Parallel real-time task scheduling on multicore platforms. In Proc. of RTSS '06.
• 3: V. Balasundaram et al. A static performance estimator to guide data partitioning decisions. In Proc. of PPOPP '91.
• 4: G. Chen et al. Application mapping for chip multiprocessors. In Proc. of DAC '08.
• 5: S. Chen et al. Scheduling threads for constructive cache sharing on cmps. In Proc. of SPAA '07.
• 6: Z. Chishti et al. Optimizing replication, communication, and capacity allocation in cmps. In Proce. of ISCA '05.
• 7: C.-L. Chou and R. Marculcscu. User-aware dynamic task allocation in networks-on-chip. In DATE, pages 1232--1237, 2008.
• 8: Z. Guz et al. Utilizing shared data in chip multiprocessors with the nahalal architecture. In Proc. of SPAA '08.
• 9: L. Jin et al. A flexible data to 12 cache mapping approach for future multicore processors. In Proc. of MSPC '06.
• 10: M. Kandemir. Data locality enhancement for cmps. In Proc. of ICCAD '07.
• 11: T. Kcmpf et al. A modular simulation framework for spatial and temporal task mapping onto multi-processor soc platforms. In DATE, pages 876--881, 2005.
• 12: K. Kennedy and U. Kremer. Automatic data layout for distributed-memory machines. ACM TOPLAS, 20(4):869--916, 1998.
• 13: S. Kim et al. Fair cache sharing and partitioning in a chip multiprocessor architecture. In Proc. of PACT '04.
• 14: P. S. Magnusson et al. Simics: A full system simulation platform. IEEE Computer, 35(2):50--58, 2002.
• 15: G. L. Nemhauser and L. A. Wolsey. Integer and combinatorial optimization. Wiley-Interscience, New York, NY, USA, 1988.
• 16: P. R. Panda et al. On-chip vs. off-chip memory: the data partitioning problem in embedded processor-based systems. ACM Trans. Des. Autom. Electron. Syst., 5(3):682--704, 2000.
• 17: R. Pop and S. Kumar. Mapping applications to noc platforms with multithreaded processor resources. NORCHIP Conference, 2005. 23rd, pages 36--39, Nov. 2005.
• 18: V. Suhendra et al. Integrated scratchpad memory optimization and task scheduling for mpsoc architectures. In Proc. of CASES '06.
• 19: S. C. Woo et al. The splash-2 programs: characterization and methodological considerations. In Proc. of ISCA '95.
• 20: J. Zhuo and C. Chakrabarti. System-level energy-efficient dynamic task scheduling. In Proc. of DAC '05.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

General Terms:
Algorithms, Performance

Keywords:
CMP, NoC, data, dynamic, mapping, thread