大数据是当今数字化信息社会的最关键特征之一,传统的运行在单机上的机器学习算法面对爆炸式增长的数据无法满足存储和计算的需求。高性能计算系统的发展为算法并行化提供了强有力的平台。充分利用高性能计算系统的资源,设计并实现高效的分布式算法是需要研究解决的问题。交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)是一种具有分解性和收敛性的优化算法,它可以将原始问题分解为多个子问题,通过协调子问题的解得到全局解。这种分解协作的过程,能够灵活地利用分布式环境的优势。本文根据分布式ADMM算法的原理和特征,结合现代高性能计算系统的结构优势,以ADMM算法分布式实现中的编程模型层为研究切入点,设计实现了更细粒度并行性的ADMM算法。主要的研究内容和创新点如下:(1)为了充分利用现代高性能计算系统的多节点多核心计算资源,结合分布式ADMM算法的分层交替迭代特征,本文设计了一种混合MPI/Open MP并行编程模型,并基于此模型设计实现异步分层ADMM算法(Asynchronous ADMM algorithm based on a hybrid MPI/Open MP programming model,AH-ADMM)。该算法在节点间基于MPI实现并行化,在节点内基于Open MP实现更细粒度的线程级并行化,通过使用多线程代替多进程计算子问题,减轻了内存和通信的压力。同时,针对支持向量机(Support Vector Machine,SVM)问题,设计了高效的并行化策略加速子问题的计算。AH-ADMM算法在提高单节点计算能力的同时,可以在高性能计算系统上更好的扩展。(2)针对ADMM算法子问题计算开销大以及广泛存在的数据不均衡问题,本文结合分布式ADMM算法子问题求解的独立性和灵活性,提出一种基于混合MPI/Open MP并行编程模型的分治ADMM算法(Divide-and-conquer ADMM algorithm based on hybrid programming model,DCAH-ADMM)。本文针对节点内数据子集的类别不均衡和节点间数据子集的密度不均衡两种情况,通过动态调整节点对应的局部惩罚项参数,平衡各个节点的收敛程度,以此提高整个算法的收敛速度。在节点内,使用代价敏感支持向量机作为分类器处理样本类别的不平衡;在节点间,各个节点依据本地数据子集特征模型,选择更优的子问题优化算法进行子问题求解。文中设计实现的DCAH-ADMM算法通过对计算节点实行分而治之,节点内的代价敏感子问题模型提升了算法在不均衡数据集的分类效果,节点间实现的更细粒度并行化控制提高了算法总体的运行效率。(3)本文设计了一类ADMM求解子问题接口,基于该接口和混合并行编程模型开发实现了基于分布式ADMM算法的线性分类库ADMMLC。该代码库主要适用于训练大规模支持向量机和逻辑回归等线性分类模型。用户可以通过子问题接口快速高效地加入新的子问题优化算法,或直接输入参数进行模型的训练。ADMMLC使用户无需过多关注分布式ADMM算法复杂的底层机制,为算法设计者提供高层编程模式,以根据具体应用场景选择合适的子问题求解算法,提高并行算法可扩展性。本文针对支持向量机问题,对提出的算法研发了并行程序,在“天河二号”和“自强4000”两个高性能计算系统上进行了测试。实验结果显示,与其他基于纯MPI编程模型的分布式ADMM算法相比,AH-ADMM算法最多可以减少86.7%的运行时间,能够在最多193个计算核心的集群上更好地扩展。针对分布式数据不均衡问题,在AH-ADMM算法的基础上提出DCAH-ADMM算法,进一步提升了算法的运行效率,并增强了训练模型的鲁棒性。
暂无评论