本文關(guān)鍵詞：布爾矩陣乘的分布式異構(gòu)并行優(yōu)化　出處：《計算機(jī)工程與科學(xué)》2017年04期 　論文類型：期刊論文

  更多相關(guān)文章： F算法 二元域 布爾矩陣乘 分布式異構(gòu)并行

【摘要】：布爾多項式求解是當(dāng)今密碼代數(shù)分析中的關(guān)鍵步驟,F4算法是布爾多項式求解的高效算法。分析了Lachartre為F4矩陣專門設(shè)計的高斯消去算法,針對其中布爾矩陣乘這一耗時的計算步驟,設(shè)計并實現(xiàn)了分布式異構(gòu)(CPU+MIC)并行算法。布爾矩陣相對于普通矩陣主要體現(xiàn)在矩陣元素取值區(qū)間不一樣上,由于布爾矩陣元素(0,1)導(dǎo)致矩陣乘操作的特殊性,普通矩陣乘的優(yōu)化方法不能很好地滿足布爾矩陣乘的需求。分別從布爾矩陣的存儲、OpenMP多線程組織、訪存、任務(wù)劃分和調(diào)度等方面進(jìn)行了性能優(yōu)化,實現(xiàn)了布爾矩陣乘的分布式異構(gòu)并行算法。通過隨機(jī)生成布爾矩陣測試,優(yōu)化后的分布式異構(gòu)并行程序相較于分布式同構(gòu)并行程序達(dá)到了2.45的加速比,體現(xiàn)了良好的性能提升。
[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.

【作者單位】： 國防科學(xué)技術(shù)大學(xué)海洋科學(xué)與工程研究院;
【基金】：國家自然科學(xué)基金(61502516,61572515) 國家重點研發(fā)計劃(2016YFC1401803)
【分類號】：TP338.6
【正文快照】： 通信地址:410073湖南省長沙市國防科學(xué)技術(shù)大學(xué)海洋科學(xué)與工程研究院Address:Institute of Marine Science and Engineering,National University of Defense Technology,Changsha 410073,Hunan,P.R.China1引言眾多密碼算法的安全性都可以歸結(jié)為有限域上多項式系統(tǒng)的求解問題,，

本文編號：1427556