一种快速求解二值线性方程组的并行结构  

Parallel Architecture for Fast Solving Binary Linear System of Equations

作　　者：张博为[1] 吴艳霞[1] 顾国昌[1] 孙霖[1] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机工程》2012年第11期281-283,286,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(61003036);中央高校基本科研业务费专项基金资助项目(HEUCF100606);黑龙江省青年科学基金资助项目(QC2010049)

摘　　要：针对求解GF（2）域的线性方程组问题,改进现有的高斯消元算法,提出一种快速求解未知向量的硬件并行结构,通过增加消元与行循环位移的并行操作以降低时间复杂度,采用一类仿＂smart memory＂基本单元的互联完成整个算法在硬件上的映射。对结构的性能分析表明,对于密度远大于或小于0.5的n阶二值增广矩阵,并行结构平均计算时间约为2n个时钟周期,远小于软件算法时间（1/4n3）。在3阶~50阶的二值非稀疏增广矩阵上的实现结果表明,与软件实现相比,该结构的性能可提高约2个数量级。This paper presents an efficient parallel architecture for fast solving linear system of equations over binary operations of GF（2）,which is derived from a proposed hardware-optimized Gaussian elimination.The optimization of the Gaussian elimination with pivot element is realized by using parallel elimination and cyclic shift operations instead of loop nest in each iteration.A mesh structure of ＂smart memory＂ cells is proposed for building the whole parallel architecture where the modified algorithm is mapped onto.The average running time of the architecture for n-dimension binary matrix equals 2n cycles as opposed to about 1/4n3 in software.Experimental results show that the performance of the system is improved by about two orders of magnitude.

关 键 词：线性方程组 并行结构 二值运算 硬件优化的高斯消元 

分 类 号：TP303[自动化与计算机技术—计算机系统结构]