求解二元域上Gr(o)bner基的异构并行高斯消去及其性能优化
Gr(o)bner基方法是求解多项式系统的一类主流方法,F4算法是当前计算Gr(o)bner基最快的算法之一,主要的计算代价是对F4矩阵进行高斯消去.本文在二元域上分析了Lachartre为F4矩阵专门设计的高斯消去算法,针对其中主元行约化这一耗时的计算步骤,设计实现了CPU+MIC的异构并行算法,并分别从OpenMP多线程组织、SIMD向量化、访存等方面进行了性能优化.通过HFE密码系统测试给出了算法的性能.例如求解中等规模的问题HFE80,优化后的异构并行程序相对于CPU上的多线程并行程序取得了约1.732倍的性能提升.
计算机技术 高斯消去算法 二元域 并行计算 主元行约化
唐波 朱敏 赵娟 夏华 李金才
国防科技大学计算机学院,湖南长沙 410073
国内会议
广州
中文
489-496
2014-11-06（万方平台首次上网日期，不代表论文的发表时间）