LU分解在Godson-Tvl众核体系结构上的半行化研究

随着集成电路工艺的发展,众核体系结构成为人们日益关注的计算平台.LU分解是科学和工程计算中被广泛使用的核心算法之一,尽管在传统的并行体系结构上已有大量的并行化研究工作,但是结合新犁众核体系结构特征的工作还不多.文章从负载均衡、延迟容忍和性能分析模型3个方面系统研究了LU分解在众核体系结构上的并行化问题.该文的贡献在于:首先,针对二维卷帘负载分配方案难以达到良好负载均衡的缺点,提出一种新的"之"字形分配方案,实验表明不经任何优化的情况下性能比前者提高20%,优化后达到了40%;其次,提出了一个性能加速比的分析模型,并用实验定量研究了实测性能加速比和理论值之间的差距,发现在合理利用片上存储优化访存延迟,并恰当选择矩阵分块参数的情况下,实测加速效果能比较接近理论值;通过实验还证明实测性能难以达到理论预测值的两个主要原因:访存带宽有限和片上网络的资源竞争.

Parallelization of LU Decomposition on the Godson-Tvl Many-Core Architecture

The many-core architecture is increasingly becoming a promising computing platform due to the advancement of semi-conductor technology. LU decomposition is a widely used kernel in both scientific and engineering computations. Although there are a lot of related works on tra-ditional parallel architectures, there is still little work focusing on parallelizing it on many-core architectures. This paper investigates this problem from three aspects: load balancing, latency hiding and performance modeling. There are three contributions of this work: Firstly, a novel load balancing technique has been introduced to overcome the limitations of 2D scatter decomposi-tion. Experimental results show that the proposed scheme achieves 20％ performance improve-ment without optimization and 40％ improvement after optimization. Secondly, an analytical per-ormance model is presented. Quantitative experimental study shows that by carefully hiding memory latency through on chip memory hierarchy and for a selected block size, the upper bound of theoretical performance can be approximated by experiments. Experimental results also reveal two primary causes which make theoretical speedup hard to achieve: limited DRAM bandwidth and resource contention of on-chip network.