Multicore Task Scheduling and High-Level Synthesis for Embedded Systems

2022年8月15日 09:13

2021年度研究会推薦博士論文速報
［システムとLSIの設計技術研究会］

西川広記
（大阪大学大学院情報科学研究科助教）

邦訳：組込みシステム設計におけるマルチコアタスクスケジューリングと高位合成

■キーワード
組込みシステム／マルチコア／タスクスケジューリング

【背景】組込みシステムにおけるマルチコア・メニーコアの普及
【問題】マルチコアの能力を最大限に発揮するソフトウェア技術の不足
【貢献】タスク間とタスク内の並列性を活用するスケジューリング手法の確立

　マルチコアアーキテクチャは，組込みシステムの性能を高める技術として注目されている．この技術により，アプリケーションにおける処理単位であるタスクはマルチコアを用いて並列に実行可能となり，シングルコア以上の高性能化が実現される．しかしながら，組込みシステムにおけるコア数の増加に伴ってシステム設計はますます複雑化しており，設計自動化技術のさらなる発展が期待される．なかでも，組込みシステムの要求に応じてタスクの実行順序を最適に決定するタスクスケジューリングと呼ばれる技術は組込みシステム設計においてきわめて重要な要素の一つである．本研究では，マルチコアを効率的に利用する種々のタスクスケジューリング手法を提案する．

　タスクスケジューリングとは，アプリケーションにおけるタスクの実行順序を決定し，タスクをコアに割り当てる作業を指す．古典的なタスクスケジューリングでは，複数のタスクを異なるコアに割り当てることによりスケジュール長，すなわち全体の処理時間の短縮を目指すが，各々のタスクは1個のコア上で実行されることが想定されていることが多い（図左下）．一方，本研究では，各タスクが複数のコア上で並列に実行されることを許し，各タスクに割り当てるコア数をタスクスケジューリングと同時に決定する（図右下）．

　本研究では，このタスクスケジューリング問題に対し，良い解を高速に求める制約プログラミング手法を提案した$${^{1）}}$$．提案した手法は従来の手法よりも良いスケジュールを発見可能で，スケジュール長を最大で81.9%削減することが示された．さらに，提案手法を2つの方向に拡張した．1つ目の拡張は，データ通信時の遅延の考慮である．マルチコア上では複数のタスクが並列に実行されるが，多くの場合は並列処理のために発生するデータの通信などの遅延によって全体の処理性能が低下する．そこで，データ通信の遅延を考慮したタスクスケジューリング手法を提案した．実験により，提案手法は従来手法に比べスケジュール長を平均22.5%短縮することを示した$${^{2）}}$$．2つ目の拡張は，消費エネルギーの考慮である．高性能だが消費電力が高いコアと，低性能だが消費電力が低いコアの2種類のコアを持つ非均質なマルチコアアーキテクチャを対象として，スケジューリングと同時にコアの種類を最適に決定することにより，総消費エネルギーを削減する．実験により，提案手法は従来手法に比べ最大で12.4%消費エネルギーを削減することを示せた$${^{3），4）}}$$．

参考文献
1）Nishikawa, H., Shimada, K., Taniguchi, I. and Tomiyama, H. : A Constraint Programming Approach to Scheduling of Malleable Tasks, $${International}$$ $${Journal}$$ $${of}$$ $${Networking}$$ $${and}$$ $${Computing}$$, Vol.9, No.2, pp.131-146 (July 2019).
2）Nishikawa, H., Shimada, K., Taniguchi, I. and Tomiyama, H. : Mouldable Fork-Join Task Scheduling Techniques with Inte- and Intra-Task Communications, $${International}$$ $${Journal}$$ $${of}$$ $${Embedded}$$ $${Systems}$$$${,}$$ $${Inderscience}$$ $${Publishers}$$, Vol.15, No.1, pp.69-81 (Apr. 2022).
3）Nishikawa, H., Shimada, K., Taniguchi, I. and Tomiyama, H. : Energy-Aware Scheduling of Malleable Fork-Join Tasks under a Deadline Constraint on Heterogeneous Multicores, $${ACM}$$ $${SIGBED}$$ $${Review}$$, Vol.16, No.3, pp.57-62 (Oct. 2019).
4）Nishikawa, H., Shimada, K., Taniguchi, I. and Tomiyama, H. : Simultaneous Scheduling and Core-Type Optimization for Moldable Fork-Join Tasks on Heterogeneous Multicores, $${IEICE}$$ $${Transactions}$$ $${on}$$ $${Fundamentals}$$, Vol.E105-A, No.3, pp.540-548 (Mar. 2022).

（2022年5月19日受付）
（2022年8月15日note公開）

ーーーーーーーーーーーーーーーーーー
　取得年月日：2022年3月
　学位種別：博士（工学）
　大学：立命館大学
　正会員
ーーーーーーーーーーーーーーーーーー

推薦文［コンピュータサイエンス領域］システムとLSIの設計技術研究会
本論文では，マルチコア型の組込みシステムを対象とした種々のタスクスケジューリング手法を提案し，タスク間並列性と各タスク内データ並列性を同時に考慮することで，性能向上または消費エネルギー削減を実現している．今後ますます普及が進むマルチコア組込みシステムのソフトウェア基盤技術として高い価値を有する．

研究生活　　学部生で立命館大学冨山研究室に配属されて以来，博士課程に至るまで継続してマルチコア・メニーコアにおけるタスクスケジューリングの研究に従事してきました．それに並行し，博士課程ではその他数多くの研究プロジェクトに参画させていただきながらさまざまな関連分野に視野を拡げることができました．これらのおかげで，1年短縮する形で本研究を博士論文にまとめることができました．この過程において，指導教員の冨山宏之教授，共同研究者の孔祥博助教や大阪大学大学院情報科学研究科の谷口一徹准教授をはじめとして，研究室の先輩や同輩，後輩の皆様には数多くの助言や激励をいただきました．本研究は，これら多くの人々に支えられたからこそ成し得たことだと思います．今後，自身のますますの精進を図るとともに，瞬く間に発展を遂げる情報技術社会の礎として寄与できるよう，研究活動に励んでまいります．