计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2012年
11期
281-283,286
,共4页
张博为%吴艳霞%顾国昌%孙霖
張博為%吳豔霞%顧國昌%孫霖
장박위%오염하%고국창%손림
线性方程组%并行结构%二值运算%硬件优化的高斯消元
線性方程組%併行結構%二值運算%硬件優化的高斯消元
선성방정조%병행결구%이치운산%경건우화적고사소원
针对求解GF(2)域的线性方程组问题,改进现有的高斯消元算法,提出一种快速求解未知向量的硬件并行结构,通过增加消元与行循环位移的并行操作以降低时间复杂度,采用一类仿“smart memory”基本单元的互联完成整个算法在硬件上的映射.对结构的性能分析表明,对于密度远大于或小于0.5的n阶二值增广矩阵,并行结构平均计算时间约为2.n个时钟周期,远小于软件算法时间(1/4n3).在3阶~50阶的二值非稀疏增广矩阵上的实现结果表明,与软件实现相比,该结构的性能可提高约2个数量级.
針對求解GF(2)域的線性方程組問題,改進現有的高斯消元算法,提齣一種快速求解未知嚮量的硬件併行結構,通過增加消元與行循環位移的併行操作以降低時間複雜度,採用一類倣“smart memory”基本單元的互聯完成整箇算法在硬件上的映射.對結構的性能分析錶明,對于密度遠大于或小于0.5的n階二值增廣矩陣,併行結構平均計算時間約為2.n箇時鐘週期,遠小于軟件算法時間(1/4n3).在3階~50階的二值非稀疏增廣矩陣上的實現結果錶明,與軟件實現相比,該結構的性能可提高約2箇數量級.
침대구해GF(2)역적선성방정조문제,개진현유적고사소원산법,제출일충쾌속구해미지향량적경건병행결구,통과증가소원여행순배위이적병행조작이강저시간복잡도,채용일류방“smart memory”기본단원적호련완성정개산법재경건상적영사.대결구적성능분석표명,대우밀도원대우혹소우0.5적n계이치증엄구진,병행결구평균계산시간약위2.n개시종주기,원소우연건산법시간(1/4n3).재3계~50계적이치비희소증엄구진상적실현결과표명,여연건실현상비,해결구적성능가제고약2개수량급.