基于SIMD-BF的并行FFT算法

主要讨论了在数字图像信号处理中起重要作用的快速傅立叶变换,结合了近年来人们对该算法并行化的研究成果,刨析了一种基于SIMD-BF模型上的实用并行算法。

基于SIMD-BF模型的并行FFT算法设计与实现

在单指令多数据流-蝶形网络模型(SIMD-BF)上设计实现FFT算法。当前算法中,W指数的获得需要进行位反,左移和补零操作。本算法采用按时间抽取(Decimation-in-Time)方式,其W指数可以由处理器所在位置轻松获得,只需进行简单左移操作,利用该算法中清晰简单的W指数规律进行递归运算,输出即为结果。在提出的算法中,SIMD-BF模型结构处理器的通信方式发生变化,满足选通直达无需选路时间。改进型算法结果表明,W指数规律明显简单,可节省W的计算时间,可处理倒序输入的待变换序列。

动态图上的最短路径距离并行算法

设计动态图上最短路径距离查询的并行计算框架。通过构建增量图的方法,实现一个批次内的多个查询在不同数据图版本的多线程并发执行。对于每个查询,使用双向宽度优先搜索算法来减少搜索空间,并提出搜索过程中扩展方向的决策函数。利用BSR对数据图邻接表进行编码,结合SIMD指令和图顶点重标号算法,进一步提升数据级并行度。在真实图数据集下的大量实验验证了所提方法的高效性。