布尔矩阵乘的分布式异构并行优化

发布时间：2018-01-15 08:24

  本文关键词：布尔矩阵乘的分布式异构并行优化　出处：《计算机工程与科学》2017年04期 　论文类型：期刊论文

  更多相关文章： F算法 二元域 布尔矩阵乘 分布式异构并行

【摘要】：布尔多项式求解是当今密码代数分析中的关键步骤,F4算法是布尔多项式求解的高效算法。分析了Lachartre为F4矩阵专门设计的高斯消去算法,针对其中布尔矩阵乘这一耗时的计算步骤,设计并实现了分布式异构(CPU+MIC)并行算法。布尔矩阵相对于普通矩阵主要体现在矩阵元素取值区间不一样上,由于布尔矩阵元素(0,1)导致矩阵乘操作的特殊性,普通矩阵乘的优化方法不能很好地满足布尔矩阵乘的需求。分别从布尔矩阵的存储、OpenMP多线程组织、访存、任务划分和调度等方面进行了性能优化,实现了布尔矩阵乘的分布式异构并行算法。通过随机生成布尔矩阵测试,优化后的分布式异构并行程序相较于分布式同构并行程序达到了2.45的加速比,体现了良好的性能提升。
[Abstract]:Boolean polynomial is a key step in the analysis of the password algebra, F4 algorithm is an efficient algorithm of Boolean polynomial analysis. The Gauss elimination algorithm Lachartre is designed for the F4 matrix, the Boolean matrix multiply this time-consuming calculation steps, the design and implementation of distributed parallel algorithm (CPU+MIC). Compared with the ordinary Boolean matrix the matrix is mainly reflected in the range of matrix elements is not the same, because the Boolean matrix elements (0,1) special lead matrix multiplication operation, optimization method of ordinary matrix multiplication can not meet the demand of the Boolean matrix multiplication. From Boolean matrix storage, OpenMP multi thread organization, memory, task partitioning and scheduling other aspects of the performance optimization and implementation of the distributed heterogeneous Boolean matrix multiplication parallel algorithm. By randomly generated Boolean matrix test, distributed heterogeneous parallel optimization The program achieves a 2.45 acceleration ratio compared to a distributed isomorphic parallel program, showing a good performance improvement.

【作者单位】： 国防科学技术大学海洋科学与工程研究院;
【基金】：国家自然科学基金(61502516,61572515) 国家重点研发计划(2016YFC1401803)
【分类号】：TP338.6
【正文快照】： 通信地址:410073湖南省长沙市国防科学技术大学海洋科学与工程研究院Address:Institute of Marine Science and Engineering,National University of Defense Technology,Changsha 410073,Hunan,P.R.China1引言众多密码算法的安全性都可以归结为有限域上多项式系统的求解问题,，

本文编号：1427556