-
题名基于固定序的Bellman-Ford算法的改进
被引量：3
- 1
-
-
作者
韩伟一
-
机构
哈尔滨工业大学经济与管理学院
-
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2015年第4期111-115,共5页
-
基金
国家自然科学基金资助项目(71101037)
中央高校基本科研业务费专项资金资助(HIT.HSS.201406)
-
文摘
固定序算法是Bellman-Ford算法的一种基本改进算法。为了改变固定序算法在稀疏图上的劣势,本文通过预先订制参与迭代的点的计算顺序,对该算法进行了改进。实验表明,在稀疏图上,改进后的算法相对于原算法计算效率提高了近50%,并能够与国际流行的先进先出算法相媲美。本文的工作表明,固定序算法不仅在大规模稠密图上具有明显的优势,而且在稀疏图上也具有很强的竞争力。
-
关键词
运筹学
固定序改进算法
最短路序
拓扑序Bellman-Ford算法
-
Keywords
operations research
improved fixed order algorithm
the shortest path order
topological order
bellman-ford algorithm
-
分类号
O221.7
[理学—运筹学与控制论]
-
-
题名CUDA下单源最短路径算法并行优化
被引量：3
- 2
-
-
作者
张晗
钱育蓉
王跃飞
陈人和
田宸玮
-
机构
新疆大学软件学院
-
出处
《计算机工程与设计》
北大核心
2019年第8期2181-2189,共9页
-
基金
国家自然科学基金项目(61562086、61462079)
新疆维吾尔自治区创新团队基金项目(XJEDU2017T002)
-
文摘
为设计基于固定序的Bellman-Ford算法在CUDA平台下并行优化方案,结合算法计算密集和数据密集的特点。从核函数计算层面,提出访存优化方法和基于固定序优化线程发散;从CPU-GPU传输层面,提出基于CUDA流优化数据传输开销方法。对不同显卡进行测试,参照共享内存容量划分线程块、缩减迭代后向量维度并使用CUDA流缩短首次计算时延,相比传统算法,改进后并行算法加速比在200倍左右。该并行优化方案验证了固定序在CUDA平台具有可行性和可移植性,可作为多平台研究参照。
-
关键词
固定序改进算法
Bellman-Ford算法
并行计算
性能可移植性
图形处理器
统一计算设备架构
-
Keywords
improved fixed order algorithm
Bellman-Ford algorithm
parallel computing
performance portability
GPU
CUDA
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
