Communication-Aware Scheduling of Data-Parallel Tasks on Multicore Architectures

• Shimada Kana

  Graduate School of Science and Engineering, Ritsumeikan University

• Taniguchi Ittetsu

  Graduate School of Information Science and Technology, Osaka University

• Tomiyama Hiroyuki

  Graduate School of Science and Engineering, Ritsumeikan University

Abstract

Task scheduling has a significant impact on multicore computing systems. This paper studies scheduling of data-parallel tasks on multicore architectures. Unlike traditional task scheduling, this work allows individual tasks to run on multiple cores in a data-parallel fashion. In this paper, the inter-task communication overhead is taken into account during scheduling. The communication happens if main threads of two tasks with data-dependencies are mapped onto the different processors. This paper proposes two methods for data-parallel task scheduling with communication overhead. One is two-step method, which schedules tasks without communication and then assigns threads in the task on cores. The other is integrated method, which performs task scheduling and thread assignment simultaneously. Both of the two methods are based on integer linear programming. The proposed methods are evaluated through experiments and encouraging results are obtained.

Journal

• IPSJ Transactions on System LSI Design Methodology

  IPSJ Transactions on System LSI Design Methodology 12 (0), 65-73, 2019

  Information Processing Society of Japan

Keywords

• task scheduling
• integer linear programming
• multicore

Details

• CRID: 1390001288155460992
• NII Article ID: 130007687116
• DOI: 10.2197/ipsjtsldm.12.65
• ISSN: 18826687
• Web Site: https://www.jstage.jst.go.jp/article/ipsjtsldm/12/0/12_65/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed