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

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

单位：国防科学技术大学海洋科学与工程研究院; 湖南长沙410073