基于OpenCL的若干机器学习算法GPU实现及优化_王伟俨

《基于OpenCL的若干机器学习算法GPU实现及优化_王伟俨》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、密级:______硕士学位论文基于OpenCL的若干机器学习算法GPU实现及优化作者姓名：王伟俨指导教师:龙国平副研究员中国科学院软件研究所学位类别:工学硕士学科专业:计算机软件与理论培养单位:中国科学院软件研究所2014年4月SeveralMachineLearningAlgorithmImplementationsandOptimizationsBasedonGPUwithOpenCLByWeiyanWangADissertationSubmittedtoUniversityofChineseA

2、cademyofSciencesInpartialfulfillmentoftherequirementForthedegreeofMasterofComputerSoftwareandTheoryInstituteofSoftware,ChineseAcademyofSciencesApril,2014独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研

3、究所做的任何贡献均已在论文中作了明确的说明。签名：___________________日期：____________________关于论文使用授权的说明本人完全了解中国科学院软件研究所有关保留、使用学位论文的规定，即：中国科学院软件研究所有权保留送交论文的复印件，允许论文被查阅和借阅；中国科学院软件研究所可以公布论文的全部或部分内容，可以采用影印、缩印或其它复制手段保存论文。（保密的论文在解密后应遵守此规定）签名：__________导师签名：__________日期：__________中国科

4、学院软件研究所硕士论文基于OpenCL的若干机器学习算法GPU实现及优化摘要与大多数其他算法不同，机器学习算法并不是对问题解决方案直接的形式化描述。相反，当前主流的机器学习算法基于统计从大量的训练数据中提取规则训练模型，从而得到可推断其他待检测数据的模型或规则。机器学习算法因需不断迭代逼近最优解有计算密集的特点，因需频繁读取训练数据和检测数据中有访存密集的特点并因检测规则的复杂具有逻辑复杂性。因此，机器学习算法往往在训练时耗费大量时间，而在检测时常常不能满足实时性要求高的应用场景。另一方面，当前GP

5、U用于通用计算已经越来越普遍，大量的算法在GPU上获得了可观的加速比。因此，可以考虑基于GPU优化加速机器学习算法，减小训练开销满足检测的实时性要求。考虑到GPU计算平台的硬件架构特性，结合机器学习算法计算密集，访存密集和逻辑复杂的3大特点，本文主要从并行粒度选择，访存优化策略以及负载均衡策略3个方面研究了在GPU上实现并优化机器学习算法的方法。并行粒度的选择是并行的根基性问题，选择何种粒度进行并行将决定整个并行实现的框架和潜在优化空间。本文分别研究了讨论粗粒度与细粒度在发起足够多线程数掩盖延迟与通

6、讯同步开销上的影响，从而进一步讨论粗、细两种粒度的选择与取舍。此外，还提出了依据输入规模和参数进行动态选择并行粒度的策略。访存优化是并行优化的关键性问题，因为GPU众多的计算核心与显存相对窄的带宽间有着鸿沟，解决访存延迟是喂饱计算能力达到好的加速效果的关键。本文立足于具体机器学习算法的访存模式，分别从减少访存开销（主要包括对存储层次结构利用、手动cache等策略）和减少访存次数（主要包括基于数据流分析的kernel合并、循环缓冲，无锁全局同步机制的软，硬件实现等策略）两种思路进行优化，并结合资源消耗

7、和活跃wavefront数目之间的平衡等具体情况讨论了上述策略的适用场景。负载均衡优化问题是并行优化的难点性问题，整个程序的最终瓶颈在于任务量最大的计算核心。本文对work-group内和work-group间两类负载不均衡问题分别进行了研究。对于work-group内的负载不均衡主要从条件分歧的起因和影响两种思路中分别发展出任务队列消除条件分支分歧和并行粒度变换减少线程空闲两种具体的策略；而对于work-group间的负载不均衡主要进行了基于统计趋势和假设的任务分配方式研究。为了验证提出的GPU优

8、化思路和具体策略的有效性，在上述优化思路的指导下对2种计算机视觉算法(Viola-Jones人脸检测和SIFT特征)和1种自然语言处理算法（LDA文本分类算法）进行了优化。其中，Viola-Jones优化中合理的使用粗粒度并行，并有效的使用2维localmemory作为手动cache减少访存开销，并用变换并行粒度减少条件分支分歧引发的线程空闲提高设备使用率，最终获得的相对于CPU高达16倍的加速比。SIFT优化中，进一步挖掘关键点领域进行直方图统计时的并行性从而用更细