基于Spark的大规模分布式矩阵运算算法研究与实现

来源 :南京大学 | 被引量 : 0次 | 上传用户:feihuiy1
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,随着计算机和信息技术的迅猛发展和普及应用,行业应用数据呈爆炸性增长,全球进入到了一个全新的“大数据”时代,引起业界、学术界和各国政府的高度关注。大数据中往往隐含着很多在小数据量时不具备的深度知识和价值,因此大数据存储处理与分析应用成为近几年来的研究热点。机器学习和数据分析是将大数据转换成有用知识的关键技术。而在大数据机器学习处理时,大多数机器学习和数据分析算法都可以表示为矩阵或向量代数计算。因而在大数据机器学习算法中,矩阵运算的性能很大程度上决定了学习和分析算法整体的运行性能。以深度神经网络算法为例,大部分的计算量都花费在矩阵乘法上。而大数据场景下矩阵运算的另一个技术难题是,大规模矩阵运算无法基于单机在可接受的时间内完成,因此,有必要研究实现基于集群的大规模分布式矩阵运算方法和算法。为此,本文将研究基于大数据平台的大规模分布式矩阵运算方法和算法,以提高大规模矩阵运算的计算性能,最终为分布式学习系统提供基础矩阵算法库支撑。在实际的大数据处理场景中,通常包括稠密矩阵和稀疏矩阵两大类矩阵。为此,本文首先对大规模稠密矩阵相关运算进行研究。在分析了Hadoop和Spark等大数据平台上已有相关工作的基础上,提出了能更好地权衡矩阵运算并发度与shuffle数据读写开销的矩阵运算执行策略C-RMM (Concurrent Replication based Matrix Multiplication);并且根据底层Spark平台的相关特性,在算法实现环节,提出了以下三种优化措施,包括在MapMM (Map-side Matrix multiplicatic n)策略中更高效地利用本地原生库,提供更高效的分布式行-块矩阵转换,以及减少矩阵乘法join阶段的shuffle数据读写开销。此外,本文还进一步利用Spark的联合分区的特性,对矩阵间逐元素运算进行了相关性能优化。除了稠密矩阵外,现实世界大数据处理场景中,很多大规模矩阵具有很大的稀疏性,对这种稀疏矩阵,如果采用稠密矩阵运算方法进行处理,不仅会浪费较大的数据存储空间,而且运算性能也难以令人满意。为此,本文第二部分工作对大规模稀疏矩阵相关运算方法和算法进行了研究与实现。在区分了高度稀疏的矩阵乘法和中度稀疏的矩阵乘法各自特点和相关应用场景后,对于中度稀疏矩阵乘法问题,本文仍然采用分块切分的思想。为了优化分布式计算过程中单节点上的计算性能,本文比较了现有的基于JVM的单机矩阵运算库,参照已有工作中的相关设计思想,研究实现了一套高效的单机稀疏矩阵运算方法,从而在整体上提高了分布式运算的整体性能。在稠密和稀疏矩阵运算方法和算法研究与实现的基础上,本文进一步设计并构建了一个基于Spark的高效大规模分布式矩阵运算库——-Marlin,并在三种不同特征类型的矩阵乘法运算上,与Spark MLlib、SystemML和SciDB进行了相关运算操作的性能对比。实验结果表明,在大规模稠密矩阵乘法场景下,Marlin相比于Spark MLlib. SystemML和SciDB可以分别达到2-4倍的平均加速比;在设定常见稀疏度的大规模稀疏-稀疏矩阵乘法场景下,Marlin可以分别达到8-16倍的平均加速比;在大规模稠密-稀疏矩阵乘法场景下,Marlin可以分别达到3-5倍的平均加速比。最后,为了验证所研究实现算法的整体有效性,本文还利用矩阵相关运算算法分别实现了深度神经网络和非负矩阵分解两个真实的机器学习算法应用,并将Marli n与SystemML口SciDB进行了性能对比。实验结果表明,在深度神经网络的应用中,Marlin相比于其他系统可以达到5-29倍的加速比;在非负矩阵分解应用中,Marlin相比于其他系统可以达到约2-3倍的加速比。同时,Marlin系统还表现出了近乎线性的系统和数据可扩展性。
其他文献
互联网技术的快速发展产生了数据爆炸和信息过载的问题,同时现代生活节奏的加快催生了用户快速阅读的需求,使得文本自动摘要技术成为了当今科学界的研究热点。相比其他自然语
该论文以"数据业务计算机综合服务管理系统"的设计和实现为基础,探讨了建立此类分布式系统的方法和模式,从多角度讨论了目前关于分布式处理的先进技术,提出了分布式应用系统
论文简单的介绍了WBM的原理及其分类,并结合作者设计的基于代理的WBM网络管理系统Netmiss及设计中的关键技术做了详尽的阐述.其中包括Netmiss原型系统SNMP通讯原语的设计实现
该文在阅读了大量有关文献的基础上,首先,对部线型网络和令牌环网这两种局域网的性能进行了分析和研究,得到了一些对局域网的规划和设计具有重要意义的结论:对总线型网络而言
随着信息技术的不断发展,人们每天都会面对超过自身接受范围的信息量。因此对文本进行主题分类,并为人们推送特定的信息就成了一个热门的研究议题。众多在线社交平台和在线新
论文对课件制作所涉及的媒体素材库进行了研究,提出了一种新的数据模型,并在该基础上采用课件分层设计方法.最终实现了基于媒体素材的分层课件制作工具.该工具可以利用媒体素