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

摘要：

布尔多项式求解是当今密码代数分析中的关键步骤,F4算法是布尔多项式求解的高效算法.分析了Lachartre为F4矩阵专门设计的高斯消去算法,针对其中布尔矩阵乘这一耗时的计算步骤,设计并实现了分布式异构(CPU+MIC)并行算法.布尔矩阵相对于普通矩阵主要体现在矩阵元素取值区间不一样上,由于布尔矩阵元素(0,1)导致矩阵乘操作的特殊性,普通矩阵乘的优化方法不能很好地满足布尔矩阵乘的需求.分别从布尔矩阵的存储、OpenMP多线程组织、访存、任务划分和调度等方面进行了性能优化,实现了布尔矩阵乘的分布式异构并行算法.通过随机生成布尔矩阵测试,优化后的分布式异构并行程序相较于分布式同构并行程序达到了2.45的加速比,体现了良好的性能提升.

关键词：F4算法、二元域、布尔矩阵乘、分布式异构并行

所属期刊栏目：39

分类号：TP303(计算技术、计算机技术)

资助基金：国家自然科学基金61502516,61572515;国家重点研发计划2016YFC1401803

在线出版日期：2017-05-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：634-640