﻿ 基于Spark的分布式数字信号处理算法库设计
 计算机系统应用  2018, Vol. 27 Issue (8): 214-218 PDF

1. 中国科学院大学, 北京 100049;
2. 中国科学院 沈阳计算技术研究所, 沈阳 110168

Design of Distributed Digital Signal Processing Algorithm Library Based on Spark
QIAO Xin, LIU Feng, YU Bi-Hui
University of Chinese Academy of Sciences, Beijing 100049, China;
Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China
Abstract: The traditional DSP and FPGA-based digital signal processing technology is more suitable for real-time signal processing. It is limited by the size and frequency resolution of the data. So it unsuitable for applications of off-line data processing, data analysis and data mining under large-scale data. Currently the industrial big data analytics platforms can use Spark as a computational engine for real-time signal processing and off-line signal processing acceleration. However, there is a lack of mathematical solutions such as digital signal processing for distributed parallel computing engines. Consequently, this paper presents a library of distributed digital signal processing algorithms based on Spark, which provides a support for the analysis of industrial big data application scenarios. This paper describes the architecture of the algorithm library design and takes the FFT algorithm and DFT algorithm as examples to introduce the distributed implementation of the traditional digital signal algorithm in Spark. Finally, this paper persents a test and analysis for this algorithm library. The results show that the algorithm library can correctly accomplish the function of digital signal processing and it can fulfill the industrial big data analysis platform for large-scale data sets for digital signal processing needs.
Key words: Spark     digital signal processing     distributed computing     algorithm library

1 分布式数字信号处理算法库的功能组织与架构设计

 图 1 算法库功能组织图

 图 2 Spark层面算法库架构图

2 分布式算法实现

2.1 基于Spark并行计算引擎的分布式FFT算法实现

Spark中的数据是通过RDD进行存储和表示的, 使用map和reduce函数进行RDD之间的转换[35]. 通过文献[68]可知, FFT算法的关键步骤为蝶形运算和变址运算, 所以本部分主要介绍对蝶形运算和变址运算中的map和reduce的设计思想. 除此之外, 由于FFT算法可以使用按照时间拆分的基2方法进行优化计算, 所以在本部分中还详细介绍了数据填充部分的步骤, 作为对原始数据的预处理环节.

2.1.1 数据填充

(1) 创建RDD用于存储原始数据.

(2) 将RDD传递给map函数, map函数首先会为每条数据赋予一个递增的key值, 然后判断该数据块是否需要填充, 若需要则进行填充, 否则不做任何操作. map过程将会产生新的RDD.

(3) 将第二步的RDD传递给reduce函数进行简单格式整合, 生成这一阶段的结果RDD.

2.1.2 变址运算

(1) 将经过数据填充阶段的结果RDD作为该阶段的原始序列.

(2) 将原始序列传递给map函数, map函数会将每条记录的key值转换为二进制表示, 然后将二进制key值进行逆序转换, 再将逆序key值排序, 最后把排序好的结果存储在新的RDD中.

(3) 将第二步生成的RDD传递给reduce函数进行简单格式整合, 生成新的RDD. 该RDD中存储的数据即为符合要求的输入序列.

2.1.3 蝶形运算

(1) 将经过变址运算阶段的RDD作为输入序列.

(2) 将输入序列传递给map函数, map函数将每条记录的key值更换成统一值.

(3) 将第二步的结果传递给reduce函数, 在reduce函数中按照传统的FFT算法中的蝶形运算进行计算, 并将结果进行格式整合, 输出到文件中.

2.2 基于Spark并行计算引擎的分布式DFT算法实现

(1) 创建RDD用于存储原始数据.

(2) 将RDD传递给map函数, map函数按照该算法的数学公式进行逐级累加, 并产生新的RDD用于存储中间结果.

(3) 将第二步的RDD传递给reduce函数进行简单格式整合, 并将结果输出至文件存储.

3 分布式数字信号处理算法库的正确性测试与性能分析

3.1 分布式数字信号处理算法库的正确性测试

3.2 分布式数字信号处理算法库的性能分析

 图 3 数据量-运行时间关系图

4 结论与展望

 [1] 彭宇, 姜红兰, 杨智明, 等. 基于DSP和FPGA的通用数字信号处理系统设计. 国外电子测量技术, 2013, 32(1): 17-21. DOI:10.3969/j.issn.1002-8978.2013.01.008 [2] 冯兴杰, 王文超. Hadoop与Spark应用场景研究. 计算机应用研究(优先发表), 2018, 35(9). [3] 李玮. Apache Spark技术研究与应用前景分析. 电信技术, 2016(9): 67-68, 71. DOI:10.3969/j.issn.1000-1247.2016.09.017 [4] 英昌甜, 于炯, 卞琛, 等. 基于RDD关键度的Spark检查点管理策略. 计算机研究与发展, 2017, 54(12): 2858-2872. DOI:10.7544/issn1000-1239.2017.20160717 [5] Zaharia M, Xin RS, Wendell P, et al. Apache spark: A unified engine for big data processing. Communications of the ACM, 2016, 59(11): 56-65. DOI:10.1145/3013530 [6] 刘大庆, 林浩然, 陈树越. 快速傅里叶变换中计算倒序的新思路. 电子与信息学报, 2018, 40(3): 758-762. [7] 马学娟. 基于快速傅里叶变换(FFT)和小波变换的大型风机机械振动故障的分析. 科技与创新, 2016(11): 121, 125. [8] Chen L, Hu Z, Lin JM, et al. Optimizing the fast Fourier transform on a multi-core architecture. Proceedings of 2017 IEEE International Parallel and Distributed Processing Symposium. Rome, Italy. 2007. 1–8.