公开(公告)号：CN108363723A

公开(公告)日：2018-08-03

申请号：CN201810008095.X

申请日：2018-01-04

Applicant: 复旦大学

Inventor： 祝远扬 ,  李锐 ,  邱堃 ,  赵进 ,  王新

IPC: G06F17/30 ,  G06F9/54

CPC classification number: G06F17/30958 ,  G06F9/544 ,  G06F17/30979

Abstract: 本发明属于计算机网络通信技术领域，具体为关于类PLL最短路距离查询算法的并行化加速方法。本发明的类PLL算法是一种基于搜索剪枝的“构建索引—询问查询”的两阶段算法，在构建索引的过程中，充分利用CPU多核的特性，合理地分配计算量和计算方式，对构建索引的过程实现并行化计算，提高时间效率；在询问的阶段中，对批量询问进行处理与分析，合并具有相同端点的询问，对不同的另一端进行并行化查询，以提高CPU多核的利用率以加快计算速度。本发明通过并行化的方式提高串行特征强烈的类PLL算法构建索引以及在批量询问处理中的计算效率，并使得这种并行化加速方法能够在充分利用多核计算单元的特性下高效完成算法功能。

公开(公告)号：CN108363723B

公开(公告)日：2021-07-23

申请号：CN201810008095.X

申请日：2018-01-04

Applicant: 复旦大学

Inventor： 祝远扬 ,  李锐 ,  邱堃 ,  赵进 ,  王新

IPC: G06F16/901 ,  G06F16/903 ,  G06F9/54

Abstract: 本发明属于计算机网络通信技术领域，具体为关于类PLL最短路距离查询算法的并行化加速方法。本发明的类PLL算法是一种基于搜索剪枝的“构建索引—询问查询”的两阶段算法，在构建索引的过程中，充分利用CPU多核的特性，合理地分配计算量和计算方式，对构建索引的过程实现并行化计算，提高时间效率；在询问的阶段中，对批量询问进行处理与分析，合并具有相同端点的询问，对不同的另一端进行并行化查询，以提高CPU多核的利用率以加快计算速度。本发明通过并行化的方式提高串行特征强烈的类PLL算法构建索引以及在批量询问处理中的计算效率，并使得这种并行化加速方法能够在充分利用多核计算单元的特性下高效完成算法功能。