在多核CPU架构上的稀疏下三角方程求解器的性能优化方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN115951994A(43)申请公布日2023.04.11(21)申请号202211617705.9(22)申请日2022.12.15(71)申请人清华大学地址100084北京市海淀区清华园(72)发明人费翔张悠慧(74)专利代理机构北京知联天下知识产权代理事务所(普通合伙)11594专利代理师刘彦平(51)Int.Cl.G06F9/50(2006.01)G06F17/12(2006.01)G06F17/16(2006.01)权利要求书3页说明书10页附图3页(54)发明名称在多核CPU架构上的稀疏下三角方程求解器的性能优化方法(57)摘要本发明公开了一种在多核CPU架构上的稀疏下三角方程求解器的性能优化方法、系统、电子设备和存储介质，具体包括：把稀疏下三角矩阵拓扑排序后转换为有向无环图，即DAG图，将所述DAG图中每层的任务分别分配给多个线程，其中，在计算下三角矩阵的任一行所需要使用的NNZ中，当由同一个线程计算得到的NNZ占对应行全部所述NNZ的比例超过预设阈值时，优先把对应行的任务分配给所述线程，这里NNZ指矩阵中的非零元素；根据任务分配情况，寻找并删除所有冗余的数据依赖；寻找满足提前计算条件的行并进行提前计算。上述过程能够进一步减少冗余数据依赖，提高任务并行度和数据局部性，提高多核CPU架构下的稀疏下三角方程求解器的性能。CN115951994ACN115951994A权利要求书1/3页1.一种在多核CPU架构上的稀疏下三角方程求解器的性能优化方法，其特征在于，包括以下步骤：把稀疏下三角矩阵拓扑排序后转换为有向无环图，即DAG图，将所述DAG图中每层的任务分别分配给多个线程，其中，在计算下三角矩阵的任一行所需要使用的NNZ中，当由同一个线程计算得到的NNZ占对应行全部所述NNZ的比例超过预设阈值时，优先把对应行的任务分配给所述线程，这里NNZ指矩阵中的非零元素；根据任务分配情况，寻找并删除所有冗余的数据依赖；寻找满足提前计算条件的行并进行提前计算。2.如权利要求1所述的方法，其特征在于，所述在计算下三角矩阵的任一行所需要使用的NNZ中，只包括对应行在DAG图中对应层的上一层中的NNZ。3.如权利要求1所述的方法，其特征在于，根据任务分配情况，寻找并删除所有冗余的数据依赖，包括以下步骤：将所述DAG图中的每个任务转换为对应的task点，生成所述DAG图对应的task图，其中一个task是指DAG图的同一层次内分配给同一个线程的所有计算任务；分别根据每个task点在完成任务后已满足的所有数据依赖，记录对应task点的数据依赖集合；使task图中每条边中的下一个task点的数据依赖集合继承上一个task点的数据依赖集合中全部的数据依赖；根据所述上一个task点的数据依赖集合中的数据依赖，判断并删除所述下一个task点的数据依赖集合中所有冗余的数据依赖。4.如权利要求3所述的方法，其特征在于，根据任务分配情况，寻找并删除所有冗余的数据依赖，还包括以下步骤：按照线程和层次数的顺序，分别对每个task编号；在每个task点的数据依赖集合中，只保留所述集合中每个线程内task编号最大的数据依赖，删除来自该线程的其他数据依赖。5.如权利要求4所述的方法，其特征在于，按照线程和层次数的顺序，分别对每个task编号，包括以下步骤：按照线程的顺序，对一个线程的所有task编号完成后，再对下一个线程的所有task编号；在每个线程内部，按task所属层次数从小到大的顺序对task编号，一个层次内的所有task属于同一个task编号，每个task内允许包含多个DAG图中的点；当该线程在DAG图中的某层的task为空时，跳过该层，不编号。6.如权利要求1所述的方法，其特征在于，寻找满足提前计算条件的行，包括以下步骤：在每个任务结束计算时，确定已满足的数据依赖；每个task内允许包含多个DAG图中的点，DAG图中的每个点对应的是下三角矩阵的一行；当待计算的某个task内的点对应的全部数据依赖属于所述该task已满足的数据依赖时，将对应的task内的点确定为满足提前计算条件的行，其中task内的一个点对应的是下三角矩阵的某一行。7.如权利要求1至6任一所述的方法，其特征在于，当下三角矩阵的相邻两行之间的数2CN115951994A权利要求书2/3页据依赖的数量超过设定值时，所述在多核CPU架构上的稀疏下三角方程求解器的性能优化方法，还包括以下步骤：在把每行的任务分配给各个线程之前，对下三角矩阵的所有行进行分组，其中，把相邻行的数据依赖严重的连续若干行捆绑成一个组，进而把整个下三角矩阵的所有行切分成多个组；数据依赖严重的判断标准是，下三角矩阵对应的DAG图中每层的节点个数小于4，并且每层的节