Dynamic task scheduling strategies for deep memory hierarchies in the future

未来深度内存层次结构的动态任务调度策略

• 批准号: 22KJ0677
• 负责人: 椎名 峻平
• 金额: $ 1.41万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2023
• 资助国家: 日本
• 起止时间: 2023-03-08 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22KJ0677/
• 关键词: タスク並列処理; タスクスケジューリング; 動的負荷分散; ワークスティーリング; 大域アドレス空間; PGAS; 高性能計算

本年度は、まず前年度より引き続き研究を行ってきたADWSの共有キャッシュ向けの改良版Multi-level ADWSについて、成果の取りまとめを行った。Multi-level ADWSはADWSをベースとして、共有キャッシュ容量に収まる程度の部分的な計算を一度に行っていくことで共有キャッシュ効率を改善させたものである。本年度はNUMA環境におけるMulti-level ADWSによる性能向上など追加の実験を行い、本成果は国際ジャーナルIEEE TPDSに採択された。次に、当初の研究計画とは少し異なるが、ADWSのようなタスクスケジューリングを複数計算機から成る分散メモリ型計算機上に拡張するための基盤技術について研究を行った。これまでのタスクスケジューリングは主に1つの計算機内のマルチコアに閉じた並列処理であり、より大規模な処理を行う場合にはスパコン等の分散メモリ型計算機に拡張する必要がある。今年度は主に分散ワークスティーリング技術について研究を行った。負荷分散の観点からは並列タスクないしスレッドを効率的に計算機をまたいで動的に移動させることが重要であるが、その性能についてはこれまであまり実験的に解析されていなかった。本研究ではこの点について深堀りし、積極的にスレッドを計算機間で移動させるコストは全体的に高くはなく、むしろ負荷分散の効率が向上することによるメリットが大きいことを示した。実験には東京大学のWisteria/BDEC-01 Odysseyスーパーコンピュータを用い、10万コア以上を用いて95%を超える高い並列化効率を示し、十分なスケーラビリティを確認した。本成果は国際会議Cluster '22で発表した。

今年，我们首先汇编了ADWS改进的多级ADW版本的结果，用于共享缓存，自上一年以来，我们一直在继续研究。多级ADWS基于ADWS，并通过立即进行部分计算以适合共享高速缓存容量来提高共享的缓存效率。今年，进行了其他实验，包括在NUMA环境中使用多级ADW提高性能，并在国际杂志IEEE TPD中选择了这些结果。接下来，尽管与原始研究计划有点不同，但我们对将任务调度（例如ADW）的基本技术进行了研究，例如由多台计算机组成的分布式内存计算机。以前的任务调度主要是在一台计算机中的多核封闭的并行处理，并且在执行大规模处理时，有必要扩展到分布式内存计算机（例如SuperComputers）。今年，我们主要对分布式工作窃取技术进行了研究。从负载平衡的角度来看，重要的是在计算机上有效地动态移动并行任务或线程很重要，但是在实验中并未对其性能进行太多分析。这项研究详细研究了这一点，并表明，计算机之间主动移动线程的总成本不高，并且提高负载平衡效率的好处是很棒的。该实验是使用东京大学的Wisteria/BDEC-01 Odyssey超级计算机进行的，并使用超过100,000个核心，显示高平行化效率超过95％，并确认了足够的可伸缩性。这些结果是在国际会议集群'22上提出的。

项目成果

Distributed Continuation Stealing is More Scalable than You Might Think

分布式连续窃取比您想象的更具可扩展性

• 发表时间: 2022
• 作者: YOSHIOKA Tatsushi;IYOKI Kenta;SANO Tsuneji;OKUBO Tatsuya;WAKIHARA Toru;吉岡 達史・伊與木 健太・堀田 悠介・上村 佳大・加藤 丈晴・クレイグ・A・J・フィッシャー・劉 振東・大西 良治・佐々木 優吉・遠藤 明・武脇 隆彦・佐野 庸治・大久保 達也・脇原 徹;吉岡 達史・伊與木 健太・堀田 悠介・劉 振東・大西 良治・武脇 隆彦・佐野 庸治・大久保 達也・脇原 徹;吉岡 達史・伊與木 健太・堀田 悠介・劉 振東・大西 良治・武脇 隆彦・佐野 庸治・大久保 達也・脇原 徹;吉岡 達史・伊與木 健太・堀田 悠介・劉 振東・大西 良治・武脇 隆彦・佐野 庸治・大久保 達也・脇原 徹;Shumpei Shiina and Kenjiro Taura;Shumpei Shiina and Kenjiro Taura
• 通讯作者: Shumpei Shiina and Kenjiro Taura

Improving Cache Utilization of Nested Parallel Programs by Almost Deterministic Work Stealing

• DOI: 10.1109/tpds.2022.3196192
• 发表时间: 2022-12
• 期刊: IEEE Transactions on Parallel and Distributed Systems
• 影响因子: 5.3
• 作者: Shumpei Shiina;K. Taura

分散ワークスティーリングと協調するキャッシュ機構を備えたPGAS処理系

配合分布式工作窃取的具有缓存机制的PGAS处理系统

• 发表时间: 2022
• 作者: YOSHIOKA Tatsushi;IYOKI Kenta;SANO Tsuneji;OKUBO Tatsuya;WAKIHARA Toru;吉岡 達史・伊與木 健太・堀田 悠介・上村 佳大・加藤 丈晴・クレイグ・A・J・フィッシャー・劉 振東・大西 良治・佐々木 優吉・遠藤 明・武脇 隆彦・佐野 庸治・大久保 達也・脇原 徹;吉岡 達史・伊與木 健太・堀田 悠介・劉 振東・大西 良治・武脇 隆彦・佐野 庸治・大久保 達也・脇原 徹;吉岡 達史・伊與木 健太・堀田 悠介・劉 振東・大西 良治・武脇 隆彦・佐野 庸治・大久保 達也・脇原 徹;吉岡 達史・伊與木 健太・堀田 悠介・劉 振東・大西 良治・武脇 隆彦・佐野 庸治・大久保 達也・脇原 徹;Shumpei Shiina and Kenjiro Taura;Shumpei Shiina and Kenjiro Taura;椎名 峻平，田浦 健次朗
• 通讯作者: 椎名 峻平，田浦 健次朗