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

Distributed heterogeneous parallel Boolean matrix multiplication and its performance optimization

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

The Boolean polynomial solution is a key step in the analysis of cryptographic algebra, and the F4 algorithm is an efficient algorithm for Boolean polynomial solution. We analyze the Gaussian elimination algorithm designed by Lachartre for F4 matrix, then design and implement the distributed heterogeneous （CPU ＋ MIC） parallel algorithm for the time consumption calculation of Boolean matrix multiplication. The Boolean matrix differs from ordinary matrixes mainly in the valuetaking intervals of matrix elements. The optimization method of the general matrix multiplication cannot satisfy the Boolean matrix multiplication because the Boolean matrix element （0,1） leads to the particularity of the matrix multiplication operation. We realize the distributed heterogeneous parallel algorithms of Boolean matrix multiplication by optimizing its performance respectively on binary domain matrix storage, OpenMP multithreading organization, fetch, task partition and scheduling, etc. By randomly generating the Boolean matrix tests, the optimized distributed heterogeneous parallel program achieves an acceleration ratio of 2.45 compared with the distributed isomorphism parallel program, which shows a good performance improvement.