检索
E-mail
RSS
作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (11): 281-283,286.doi: 10.3969/j.issn.1000-3428.2012.11.085

• 开发研究与设计技术 • 上一篇    下一篇

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

张博为，吴艳霞，顾国昌，孙 霖   

  1. (哈尔滨工程大学计算机科学与技术学院，哈尔滨 150001)
  • 收稿日期:2011-12-31 出版日期:2012-06-05 发布日期:2012-06-05
  • 作者简介:张博为(1983－)，男，博士研究生，主研方向：高性能可重构计算，嵌入式系统；吴艳霞，副教授、博士；顾国昌，教授、博士生导师；孙 霖，博士研究生
  • 基金项目:
    国家自然科学基金资助项目(61003036)；中央高校基本 科研业务费专项基金资助项目(HEUCF100606)；黑龙江省青年科学基金资助项目(QC2010049)

Parallel Architecture for Fast Solving Binary Linear System of Equations

ZHANG Bo-wei, WU Yan-xia, GU Guo-chang, SUN Lin   

  1. (College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)
  • Received:2011-12-31 Online:2012-06-05 Published:2012-06-05

PDF

887

被引次数

1

摘要： 针对求解GF(2)域的线性方程组问题，改进现有的高斯消元算法，提出一种快速求解未知向量的硬件并行结构，通过增加消元与行循环位移的并行操作以降低时间复杂度，采用一类仿“smart memory”基本单元的互联完成整个算法在硬件上的映射。对结构的性能分析表明，对于密度远大于或小于0.5的n阶二值增广矩阵，并行结构平均计算时间约为2n个时钟周期，远小于软件算法时间(1/4n3)。在 3阶~50阶的二值非稀疏增广矩阵上的实现结果表明，与软件实现相比，该结构的性能可提高约2个数量级。

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

Abstract: 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.

Key words: linear system of equations, parallel architecture, binary operation, hardware-optimized Gaussian elimination

中图分类号: