可扩展机器学习的并行与分布式优化算法综述

机器学习问题通常会转换成一个目标函数去求解,优化算法是求解目标函数中参数的重要工具.在大数据环境下,需要设计并行与分布式的优化算法,通过多核计算和分布式计算技术来加速训练过程.近年来,该领域涌现了大量研究工作,部分算法也在各机器学习平台得到广泛应用.本文针对梯度下降算法、二阶优化算法、邻近梯度算法、坐标下降算法、交替方向乘子算法五类最常见的优化方法展开研究,每一类算法分别从单机并行和分布式并行来分析相关研究成果,并从模型特性、输入数据特性、算法评价、并行计算模型等角度对每个算法进行详细对比.随后对有代表性的可扩展机器学习平台中优化算法的实现和应用情况进行对比分析.同时对本文中介绍的所有优化算法进行多层次分类,方便用户根据目标函数类型选择合适的优化算法,也可以通过该多层次分类图交叉探索如何将优化算法应用到新的目标函数类型.最后分析了现有优化算法存在的问题,提出可能的解决思路,并对未来研究方向进行展望.     

基于Spark的并行DBSCAN算法的设计与实现

随着云应用对运行时间和性能水平要求的逐步提高,以及内存价格的持续走低,基于内存的分布式计算框架Spark获得了前所未有的关注。主要研究DBSCAN算法在Spark上并行化的设计与实现,通过整体分析找到算法并行化可能的性能瓶颈,并从Spark的角度设计了并行DBSCAN算法的DAG图,优化了算法的并行化策略,最大化地降低了shuffle频率和数据量。最后将并行DBSCAN算法与单机DBSCAN算法进行性能对比,并通过实验分析不同参数对聚类结果的影响。结果表明,与单机DBSCAN算法相比,基于Spark的并行DBSCAN算法在聚类精度没有明显损失的情况下,数据量在3百万行时运行效率提高了37.2%,且加速比达到1.6。     

基于Spark的BIRCH算法并行化的设计与实现

在分布式计算和内存为王的时代,Spark作为基于内存计算的分布式框架技术得到了前所未有的关注与应用。着重研究BIRCH算法在Spark上并行化的设计和实现,经过理论性能分析得到并行化过程中时间消耗较多的Spark转化操作,同时根据并行化BIRCH算法的有向无环图DAG,减少shuffle和磁盘读写频率,以期达到性能优化。最后,将并行化后的BIRCH算法分别与单机的BIRCH算法和MLlib中的K-Means聚类算法做了性能对比实验。实验结果表明,通过Spark对BIRCH算法并行化,其聚类质量没有明显的损失,并且获得了比较理想的运行时间和加速比。     

基于Spark的并行遗传算法求解多峰函数极值

遗传算法求解多峰函数极值需进行反复多次的迭代运算,面对大数据样本时会出现运算效率过低的现象,这极大地限制了遗传算法的实际应用。经典Hadoop并行平台可在一定程度上提高遗传算法的运行效率,而新一代Spark并行平台可以更加充分地发挥遗传算法的并行潜能。设计并实现了基于Spark的并行遗传算法,在各个子节点上并行执行子种群个体的交叉、变异等操作,达到了高度并行化进化种群以高效求取多峰函数极值的目的。为方便比较,同时设计并实现了单机及Hadoop平台下的相应算法。实验结果表明,处理大数据样本时,相比传统单机和Hadoop平台,基于Spark的并行化遗传算法显著降低了求解多峰函数极值的耗时,大幅提高了算法的效率;同时,由于其并行计算带来的强大随机性,也有效避免了种群单一过早收敛的问题,提高了算法的准确性。     

基于优化RDD分区的Spark并行K-means 大尺度遥感图像分割

大尺度遥感图像分割对单机处理方式而言是巨大挑战.Spark平台为在单机上构建用于大数据处理的分布式计算环境提供了可能.当Spark平台内置的K-means算法用于数字图像处理时,其中的Spark Shuffle弹性分布式数据集(RDD)分区一般采用缺省设置,尽管这种RDD设置简单便捷,但对大尺度图像分割任务容易造成“多分区、小数据”现象,极大影响图像分割速度.为此,采用覆盖部分上海市区的WorldView-3遥感图像为测试数据,在K-means算法初始化聚类中心阶段自定义影响RDD分区的参数spark.sql.shuffle.partitions,在迭代计算阶段调用coalesce()算子减少分区数;与串行K-means算法对比验证单机处理大数据的可行性与有效性,与优化前的Spark并行K-means算法对比实现了大尺度遥感图像快速分割.实验结果表明,在K-means算法初始化聚类中心和迭代计算阶段,将RDD分区数设置在CPU核数的1sim10倍,总用时由优化前的145s缩减到97s,尤其在初始化聚类中心阶段的时间效率上,优化后是优化前的500sim1000倍.     

Spark环境下的并行模糊C均值聚类算法

针对聚类算法需要处理数据集的规模越来越大、时效性要求越来越高,对算法的大数据适应能力和性能要求更高的问题,提出一种在Spark分布式内存计算平台下的模糊C均值(FCM)算法Spark-FCM。首先对矩阵通过水平分割实现分布式存储,不同向量存储在不同节点;然后基于FCM算法的计算特点,设计了分布式和缓存敏感的常用矩阵操作,包括乘法、转置和加法等;最后基于矩阵操作和Spark平台特点,设计了Spark-FCM算法,主要数据结构采用分布式矩阵存储,具有节点间数据移动少和每个步骤分布式计算特点。通过在单机和集群环境下测试,算法具有良好的可扩展性,并可以适应大规模数据集,算法性能与数据量成线性关系,集群环境下性能比单机提高2~3倍。     

基于Spark的高效并行自动编码机

机器学习中一个非常关键的问题就是如何获取良好的数据特征表示,许多经典的特征提取方法是基于数据间关系或利用简单线性组合降维后得到数据的特征表示。其中深度学习算法在各种学习任务中都可以取得良好的效果,而且可以学到很好的数据特征表示。但现有深度学习算法或模型大多为单机串行实现,不能处理较大规模的数据且运行时间较长。本文设计实现了一种基于Spark分布式平台的高效并行自动编码机,该编码机可以有效地进行特征表示学习,并且利用分布式计算平台Spark对 算法进行加速,优化了对稀疏数据的操作,大大提升了运行效率。本文通过在文本数据特征学习以及协同过滤两个任务上的实验,表明本文所实现的并行自动编码机的有效性和高效性。     

基于Spark的蚁群优化算法

为应对大数据时代中组合优化问题的求解,基于云计算框架Spark,借助其基于内存、分布式的特定,提出一种并行蚁群优化算法。其思路是通过将蚂蚁构造为弹性分布式数据集,由此给出相应的一系列转换算子,实现了蚂蚁构造解过程的并行化。通过在旅行商问题(TSP)求解的仿真实验结果说明了所提出的并行算法的可行性;并在同等实验环境下对比基于MapReduce的蚁群优化算法,优化速度提升达10倍以上。     

基于Spark的人工蜂群改进算法

针对人工蜂群（ABC）算法求解组合优化问题时效率低的问题,提出了基于Spark云计算框架的并行ABC改进算法。首先,将蜂群划分为子蜂群并将蜂群构造为弹性分布式数据集,子蜂群使用广播机制交换优秀个体;然后,采用一系列转换算子,实现蜜蜂寻找解过程的并行化;最后,用万有引力质量计算代替轮盘赌概率计算,减少计算量。通过旅行商问题（TSP）求解说明了算法的可行性。实验结果表明：对比标准ABC算法,所提算法加速比最大达到3.24;对比未改进的并行ABC算法,该算法收敛速度提高约10%。所提算法在复杂问题求解方面优势更加明显。     

多核处理平台上任务图模型的并行调度策略研究

凭借着高性能,低功耗的特性,多核处理器已经占据了目前的主要市场.提出一种多核处理平台上基于任务图模型的调度策略.建立了多核平台上任务图的空间与时间并行调度模型;针对任务图的空间并行与时间并行调度模型提出了并行节点合并、分配的优化算法与流水线并行的优化算法.最后,提出将优化的空间与时间并行调度技术相结合的并行调度策略.通过实验验证,本文提出的算法比其他多核并行调度算法降低了处理器核心间的通信与同步开销,提高了系统的计算效率与吞吐量.     

基于Spark的分布式数字信号处理算法库设计

传统的基于DSP与FPGA的数字信号处理技术更加适用于实时信号处理,且受到数据规模和频率分辨率的限制,使得其不适于进行大规模数据下的离线式数据处理、分析与挖掘的应用.目前工业大数据分析平台可以采用Spark作为实时信号处理和离线信号处理加速的计算引擎,但该分析平台缺少适用于分布式并行计算引擎的数字信号处理等数学计算的解决方案.基于此,本文提出了基于Spark的分布式数字信号处理算法库,为面向分析的工业大数据应用场景提供支撑.本文介绍了该算法库的架构设计,并以FFT算法和DFT算法为例介绍了传统数字信号处理算法在Spark下的分布式实现,最后对算法库进行了正确性测试和性能分析.结果表明该算法库能够正确完成数字信号处理的功能,同时可以满足工业大数据分析平台对于大规模数据集进行数字信号处理的需求.     

云环境下求解大规模优化问题的协同差分进化算法

差分进化是一种求解连续优化问题的高效算法。然而差分进化算法求解大规模优化问题时,随着问题维数的增加,算法的性能下降,且搜索时间呈指数上升。针对此问题,本文提出了一种新的基于Spark的合作协同差分进化算法（SparkDECC）。SparkDECC采用分治策略,首先通过随机分组方法将高维优化问题分解成多个低维子问题,然后利用Spark的弹性分布式数据模型,对每个子问题并行求解,最后利用协同机制得到高维问题的完整解。通过在13个高维测试函数上进行的对比实验和分析,实验结果表明算法加速明显且可扩展性好,验证了SparkDECC的有效性和适用性。     

利用坐标下降实现并行稀疏子空间聚类

随着数据规模的不断扩大,稀疏子空间聚类问题面临计算上的巨大挑战。现有稀疏子空间聚类算法如交替方向乘子法(ADMM)往往基于串行实现,难以利用多核处理器提高处理大规模聚类问题的效率。针对这个问题,提出一种基于坐标下降的并行稀疏子空间聚类方法。该方法利用稀疏子空间聚类可以建模为求解一系列的样本自稀疏表达子问题的特点,使用坐标下降方法来求解每个子问题,具有参数少、收敛快的优点;同时结合自稀疏表达子问题独立的特点,在处理器的各个核心上同时求解不同样本对应的子问题,因此可以充分利用计算机资源,减少运行时间开销。在模拟数据和运动分割数据集Hopkins-155上与常用的ADMM算法进行对比实验,结果表明该算法在多核处理器上可以显著提升运行速度且聚类精度与ADMM相当。     

基于Spark的CT图像FBP重建算法程序并行设计

将常用于CT图像重建的滤波反投影算法程序设计成能够运行在大数据框架Spark中的并行模式,以此来提高计算效率并实现批量图像的重建,缩短图像重建时间。基于分布式计算框架Spark,利用其图像处理工具Thunder,将滤波反投影算法在图像重建过程中设计成并行程序模式,实现图像的片间并行重建。实验结果表明,随着Spark集群规模的不断扩大,在确保重建图像质量的前提下,重建一定数量的CT图像相比单机模式下时间显著缩短,并行滤波反投影算法具有完全加速比,并行效率趋近于1。基于Spark集群实现的滤波反投影算法能够显著提升CT图像重建速度,并实现大量图像并行重建,可扩展其他的CT图像重建算法,对远程医学图像重建平台的建设具有重要参考意义。     

Platform impact on performance of parallel genetic algorithms: Design and implementation considerations

Many problems in the operations research field cannot be solved to optimality within reasonable amounts of time with current computational resources. In order to find acceptable solutions to these computationally demanding problems, heuristic methods such as genetic algorithms are often developed. Parallel computing provides alternative design options for heuristic algorithms, as well as the opportunity to obtain performance benefits in both computational time and solution quality of these heuristics. Heuristic algorithms may be designed to benefit from parallelism by taking advantage of the parallel architecture. This study will investigate the performance of the same global parallel genetic algorithm on two popular parallel architectures to investigate the interaction of parallel platform choice and genetic algorithm design. The computational results of the study illustrate the impact of platform choice on parallel heuristic methods. This paper develops computational experiments to compare algorithm development on a shared memory architecture and a distributed memory architecture. The results suggest that the performance of a parallel heuristic can be increased by considering the desired outcome and tailoring the development of the parallel heuristic to a specific platform based on the hardware and software characteristics of that platform.     

基于Spark的分布式大数据机器学习算法

对于大数据而言,机器学习技术是不可或缺的;对于机器学习而言,大规模的数据可以提升模型的精准度。然而复杂的机器学习算法从时间和性能上都急需分布式内存计算这种关键技术。Spark分布式内存计算可以实现算法的并行操作,有利于机器学习算法处理大数据集。因此本文提出在Spark分布式内存环境下实现非线性机器学习算法,其中包括多层可变神经网络、BPPGD SVM、K-means,并在实现的基础上进行数据压缩、数据偏向抽样或者数据加载等方面的优化。为了实现充分配置资源批量运行脚本,本文也实现SparkML调度框架来调度以上优化算法。实验结果表明,优化后的3种算法平均误差降低了40%,平均时间缩短了90%。     

Two-dimensional frequency-domain visco-elastic full waveform inversion: Parallel algorithms, optimization and performance

Full waveform inversion (FWI) is an appealing seismic data-fitting procedure for the derivation of high-resolution quantitative models of the subsurface at various scales. Full modelling and inversion of visco-elastic waves from multiple seismic sources allow for the recovering of different physical parameters, although they remain computationally challenging tasks. An efficient massively parallel, frequency-domain FWI algorithm is implemented here on large-scale distributed-memory platforms for imaging two-dimensional visco-elastic media. The resolution of the elastodynamic equations, as the forward problem of the inversion, is performed in the frequency domain on unstructured triangular meshes, using a low-order finite element discontinuous Galerkin method. The linear system resulting from discretization of the forward problem is solved with a parallel direct solver. The inverse problem, which is presented as a non-linear local optimization problem, is solved in parallel with a quasi-Newton method, and this allows for reliable estimation of multiple classes of visco-elastic parameters. Two levels of parallelism are implemented in the algorithm, based on message passing interfaces and multi-threading, for optimal use of computational time and the core-memory resources available on modern distributed-memory multi-core computational platforms. The algorithm allows for imaging of realistic targets at various scales, ranging from near-surface geotechnic applications to crustal-scale exploration.     

面向FT-M7002的Sobel边缘检测算法优化实现

边缘检测是图像处理与计算机视觉领域中一种重要的图像分析方法,Sobel算子常用于粗精度的边缘提取,在图像边缘检测中被广泛应用。随着国产飞腾（FT）系列高性能数字信号处理器的发展,图像处理领域对FT平台的需求日益提高,同时急需实现面向FT平台的高性能图像处理算法。针对上述问题,在FT-M7002平台上对Sobel边缘检测算法进行向量并行优化,使用FT-M7002处理器内嵌SIMD指令,挖掘Sobel边缘检测算法中的数据级并行性,同时设计并实现一种字符型与整型数据间的并行化转换接口,使用循环展开优化方法提升指令节拍数,通过DMA矩阵转置解决数据访存不连续的问题。采用双缓冲技术实现数据传输与内核计算的并行,从而隐藏数据传输与计算之间的时间间隙。对比分析多种卷积核大小及图片规模下原Sobel算法与优化算法的性能,结果表明,与原始算法相比,该优化算法能取得1.66~3.14倍的加速比,此外,相较TMS320C6678处理器上的运行结果,在FT-M7002平台上优化算法可达到1.87~2.08倍的加速效果。