協調性と耐障害性に優れた並列実行順序計画法

具有良好协调性和容错性的并行执行订单规划方法

基本信息

批准号：
21K19774
负责人：
八杉昌宏
金额：
$ 4.08万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Challenging Research (Exploratory)
财政年份：
2021
资助国家：
日本
起止时间：
2021-07-09 至 2024-03-31
项目状态：
已结题

项目摘要

並列分散環境において、一つの計算を複数の実行主体が協力して並列実行するには、各主体の担当範囲を決めることが多い。不規則計算等の場合は、分割統治的に与えられる階層的計算に関してワークスティールに基づく実行時割り当ても行われている。このような「計算を分担」という「常識」とは正反対の革新的パラダイムとして「冗長計算を階層的に省略」という並列実行手法を提唱している。どの主体も全範囲を異なる順序で担当しつつ、実行時に他から結果を得た部分の計算は省略し、全体として障害耐性も並列効率も高める。また、事前の並列実行順序計画から各主体が局所的に情報交換の内容や相手を判断する手法を考案している。各主体の視点からの階層的な状況を、限られた情報から制約方程式を解くように「逆算」する。当該年度も各主体（ワーカ）の計画法の改善を中心とした。行列表現などの数学的準備を整理し、当初 Pワーカ (2^{k－1} < P ≦ 2^k) の計画では、ハミング符号の全ビット（2^k －1 ビット）の一部（4k－1 ビット）を用いていたのに対して、任意の階層で順序バランスを改善するためにはさらに短いビット長（周期的な計画の長さ）のほうがよい可能性を検討していたが、行列表現の計画を与えて実験できるようなプログラムを開発して、実験したところ、当初の長めのビット長のほうが性能が良いことが多いという結果が得られた。また、冗長計算を階層的に省略するための結果のやり取りを、後で必要と判断されるまで遅延するための機構について、C言語への変換に基づくものやC++プログラミングに基づくものについて検討した。

在并行分布式环境中，为了使多个执行实体能够协作并并行执行单个计算，通常需要确定每个实体的责任范围。在不规则计算的情况下，对于以分而治之的方式给出的分层计算也执行基于工作窃取的运行时分配。他提出了一种“分层消除冗余计算”的并行执行方法，作为一种创新范式，与“共享计算”的“常识”完全相反。每个实体以不同的顺序负责整个范围，同时省略在运行时从其他实体获取结果的部分的计算，从而从整体上提高容错能力和并行效率。此外，我们还设计了一种方法，其中每个实体根据先前的并行执行顺序计划在本地确定信息交换的内容和合作伙伴。从每个主体的角度来看的分层情况是“向后计算”的，就好像从有限的信息中求解约束方程一样。本财年还重点改进了各实体（工人）的规划方法。整理好矩阵表示等数学准备后，基于总比特数的一部分（2^k −1比特），初步规划了P个worker（2^{k−1} < P ≤ 2^k）汉明码 ( 4k-1然而，我们正在考虑一种可能性，即较短的位长度（周期计划长度）会更好，以便改善任意层次结构中的顺序平衡，但矩阵表示我开发了一个程序，允许我通过给出计划来进行实验，当我尝试它时，我发现初始位长度越长，性能通常越好。此外，我们还研究了基于C语言转换的机制和基于C++编程的机制，以延迟结果交换，直到稍后认为有必要，以便分层消除冗余计算。