面向众核平台交替最小二乘法的实现与性能优化

发布时间：2020-04-09 15:16

【摘要】：推荐系统的任务是通过联系用户和产品,帮助用户发现对自己有价值的信息。优秀的推荐算法可以使得推荐系统的效率大大提高,增强推荐结果的正确性,满足海量用户的需求。异构众核体系结构的发展为高性能计算技术与推荐系统的结合带来了新的发展契机。本论文面向当前主流的多核与众核处理器实现并优化一种推荐系统领域极具代表性的算法:交替最小二乘法(ALS),旨在从不同角度最大化该推荐算法的性能。本文的主要工作和创新点包含以下三点:1.使用OpenCL实现了ALS算法,使其具备跨平台可移植特性;针对不同平台实施不同的优化技巧,组合不同优化技巧产生多个代码变体,从而方便研究者针对不同平台选择最优的优化方法。实验结果表明,相对于基准实现,在Intel E5-2670平台上优化后的ALS的执行速度提高为原来的5.5倍,在NVIDIA K20C平台上的性能提高了21.2倍;该实现在多个数据集上的性能均优于cuMF。2.在分析ALS算法热点和剖析已有ALS实现所存在问题的基础上,进一步提出了一种基于细粒度分块并行策略的ALS实现。该实现通过细粒度的任务划分与合理的线程配置实现了该算法性能上的大幅提升。实验数据表明,与基准实现相比,该实现在NVIDIA K20C平台上实现了多达88倍的性能加速,在AMD gfx803平台上实现了多达98倍的性能加速。此外,该实现在不同平台和不同特征维数上的性能均超越了cuMF。3.根据推荐系统数据集的特点,提出了一种基于数据重用策略的ALS实现。该实现是基于一种新的稀疏矩阵压缩分块存储格式以及数据重用/重排两种优化策略。数据重用策略降低了不同存储层次之间的数据传输次数,从而减少了访问全局存储的压力。数据重排策略通过重新组织稀疏矩阵的行列,最大化数据重用的收益。实验数据表明,相对于领域内最快的Gates实现,本文提出的实现在K20C平台上达到约2.08倍的加速比,在TITAN X平台上能够取得约3.72倍的加速比。据笔者所知,这是目前领域内最快的基于ALS算法的矩阵分解实现。本文结合了交替最小二乘算法、推荐系统数据集与异构众核体系结构的特点,合理地将任务映射到处理器的计算核心,运用了多种面向体系结构的优化技巧,从而能够充分地利用硬件架构的资源,实现在不同平台上矩阵分解性能的大幅度提升。本文所提出的ALS实现能够被直接地融入到当前主流地大数据处理框架中。
【图文】：

这种无论对于信息消费者还是信息生产者都产生了很大的挑战：对于消费者来说，从大量信息中找到自己感兴趣的信息是一件非常困难的事情；信息生产者，让自己生产的信息脱颖而出，受到广大用户的关注，也是一件困难的事情。推荐系统就是解决这一矛盾的重要工具。推荐系统的任务就是用户和信息，一方面帮助用户发现对自己有价值的信息，另一方面让信息能现在它感兴趣的用户面前，从而实现信息需求者和信息生产者的双赢。和搜擎不同，个性化推荐系统需要依赖用户的行为数据，因此一般都是作为一个存在于不同网站之中。在互联网的各类网站中都可以看到推荐系统的应用，性化推荐系统在这些网站中的主要作用是通过分析大量用户行为日志，给不户提供个性化的页面展示，从而提高网站的点击率和转化率[38]。因此，推荐系统广泛应用于互联网的各大领域，包括电子商务（亚马逊图荐—图 1.1，淘宝购物推荐—图 1.2，京东购物）、电影和视频（Netflix，YouTube性化音乐电台（豆瓣电台，Pandora，Last.fm，雅虎音乐）、社交网络（Faceboowitter，Linkedin）、个性化阅读（Google Reader，鲜果网）、基于位置的服Foursquare）、个性化邮件（Gmail，Tapestry）和广告等等。

为三类：基于内容的推荐系统，协同过滤推荐系统，混合推荐系统。基荐系统的核心是能够获得物品的准确描述（这些描述可以是人工生成的自动提取的）以及这些特征的重要记录，基于这些信息就可以为用户推趣的产品。然而，收集这些物品的描述是一项很大的工程，而且一些物要随着时间的变化来更新信息数据库。协同过滤方法则能够避免该问题思想是：如果用户集在过去有相同的偏好，那么可以假定在未来他们一似的偏好。混合推荐系统则是组合不同技术产生从而更好更精确的推荐在过去的几年里，推荐系统的研究与发展如火如荼。未来，，搜索结果的能会将搜索引擎变为上下文感知的推荐系统。类似地，其他一些飞速增，比如“物联网”或“服务网”也会用到推荐系统。目前比较常用且具的协同过滤推荐算法有交替最小二乘法 (Alternating Least Squares, AL度下降法 (Cyclic Coordinate Descent, CCD)，随机梯度下降法 (Stoient Descent, SGD)，奇异值分解 (Single Value Decomposition, SVD)等。推荐算法详细介绍请参见 1.2 节。本文重点关注的是基于交替最小二乘法解推荐算法。
【学位授予单位】：国防科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP391.3;O241.5

【相似文献】

相关期刊论文 前10条

1 邵品琮;;最小二乘法介}9[J];数学通报;1963年07期

2 谢乐平;陈坡;谢淑坤;;最小二乘法教学研究[J];智富时代;2017年01期

3 侯丽丽;任海霞;孙晓丹;刘杨;申琦;;好多元分辨-交替最小二乘法研究姜黄素的性质及降解过程[J];计算机与应用化学;2012年12期

4 王祖荫;卡尔曼滤波与经典最小二乘法[J];岩矿测试;1993年01期

5 R.P.柯雷;贾德华;;用于一般优化问题的最小二乘法[J];铁路航测;1987年03期

6 楼运豪;核测量实验中数据处理方法研究[J];实验室研究与探索;1987年03期

7 徐彦忠,丘思畴;用最小二乘法确定太阳电池电参数[J];华中理工大学学报;1988年S2期

8 王飞跃 ,王景美 ,谢贻权;最佳格点集在最小二乘法中的应用[J];浙江大学学报(自然科学版);1988年03期

9 谷峰;最小二乘法解对切比雪夫解的逼近[J];浙江大学学报(自然科学版);1988年06期

10 孙锁泰 ,杨加明;连续性最小二乘法解正交异性薄板弯曲问题[J];江苏工学院学报;1988年03期

相关会议论文 前10条

1 王大愚;;最小二乘法平滑技术在体育中运用的尝试[A];第四届全国运动生物力学学术会议论文集（二）[C];1983年

2 朱凤蓉;徐江;董宏波;周国庆;李志明;;最小二乘法在同位素质谱学中的应用[A];2007年全国质谱学会无机质谱、同位素质谱、质谱仪器和教育学专业委员会学术交流会论文集[C];2007年

3 柳明;刘雨;苏宝库;蒋效雄;;总体最小二乘法辨识惯导平台误差模型研究[A];2007'仪表，自动化及先进集成技术大会论文集（一）[C];2007年

4 沈燕华;王勇;;膜结构裁剪膜片展开的约束最小二乘法[A];计算机技术在工程建设中的应用——第十二届全国工程建设计算机应用学术会议论文集[C];2004年

5 蒋维;张文坤;罗俊波;杨树生;;基于最小二乘法的机床热误差建模补偿技术[A];“装备中国”2017年“创新滨海·SEW杯”高端装备创新设计大赛论文集[C];2017年

6 张武军;尹旭日;徐泉峰;;基于音圈电机驱动的快速定位系统参数辨识[A];第六届全国信息获取与处理学术会议论文集（2）[C];2008年

7 董艳萍;邢昱;赵文哠;;基于最小二乘法的社会网络辨识[A];第37届中国控制会议论文集（B）[C];2018年

8 毛利军;陈少林;;基于假设模态法的结构模态识别[A];第九届全国振动理论及应用学术会议论文集[C];2007年

9 陈云生;;用最小二乘法与搜索法寻求A值与风速V关系的数学表达式[A];中国电子学会可靠性分会第十三届学术年会论文选[C];2006年

10 张波;张大庆;于一发;张刚刚;;基于数据的自适应动态规划——总体最小二乘法[A];第26届中国控制与决策会议论文集[C];2014年

相关博士学位论文 前10条

1 覃永辉;偏微分方程的耦合Legendre Chebyshev配置最小二乘法[D];上海大学;2016年

2 于志云;非线性方程的混合有限元研究[D];郑州大学;2012年

3 高俊文;面向机械故障诊断应用的盲分离技术研究[D];华南理工大学;2016年

4 王彩华;稳态奇异扰动问题的数值解[D];天津大学;2014年

5 李壮;短基线定位关键技术研究[D];哈尔滨工程大学;2013年

6 孔祥兵;基于同质区分析的高光谱影像混合像元分解[D];武汉大学;2012年

7 陈学松;强化学习及其在机器人系统中的应用研究[D];广东工业大学;2011年

8 马永杰;基于非线性化学指纹图谱技术的乳品质控方法研究及数学模型构建[D];陕西科技大学;2016年

9 徐宗秋;基于多导航卫星系统的精密单点定位模型与方法研究[D];辽宁工程技术大学;2013年

10 邓祥力;大型变压器保护新原理研究和装置研制[D];华中科技大学;2011年

相关硕士学位论文 前10条

1 陈静;面向众核平台交替最小二乘法的实现与性能优化[D];国防科技大学;2018年

2 Meyof Kweyui Ngongang Mark;基于无线电信号的精确定位[D];北京邮电大学;2019年

3 常保利;电控机械式自动变速器智能换挡策略建模与仿真研究[D];长安大学;2018年

4 张秀楠;基于可见光的室内三维定位算法研究[D];南京师范大学;2018年

5 陈佩玉;基于平面波综合技术的双站柱面近场散射测量方法研究[D];西安电子科技大学;2018年

6 高庚;最小二乘法和总体最小二乘法线性回归中的估值漂移及其判定[D];太原理工大学;2018年

7 何加宝;多段径向基函数网络的正交最小二乘法和正则最小二乘法[D];安徽工业大学;2012年

8 董巧玲;不同误差影响模型下总体最小二乘法在多元线性回归中的应用研究[D];太原理工大学;2016年

9 韩倩;基于模糊对数最小二乘法的企业价值评价研究[D];成都理工大学;2011年

10 陈雪松;基于递归最小二乘法的电压闪变研究[D];四川大学;2006年

本文编号：2620924