近似三对角Toeplitz方程组的并行化实现

摘要：近似三对角Toeplitz矩阵在时间序列分析、线性逼近、图论的特征值分析等多个领域经常出现。本文对近似三角Toeplitz 矩阵求解算法的串、并行算法进行了分析，并在流处理器平台上实现了算法的并行化，实验结果说明并行算法在流处理器平台上获得较好的加速。

关键词：Toeplitz；方程组；并行化；流处理器

中图分类号：TP301 文献标识码：A 文章编号：1674-0432（2013）-06-0280-2

0 引言

线性方程组的求解是许多科学和工程计算的基本问题之一。在核物理、流体力学、石油地震、数值天气预报等大规模数据处理中都会遇到三对角系统的求解问题，其中很重要的一类是以近似三角Toeplitz矩阵为系数矩阵的线性方程组的求解。由于在理论和实际应用上的重要性，近20年来三对角方程组的并行算法研究十分活跃，对于这种三对角矩阵算法的研究也取得了一系列的成果，本文在前人研究的基础上[1]，在流处理器平台上实现了算法的并行化。

1 近似三对角Toeplitz方程组串行求解的一般思想

我们选用的实验平台式是Imagine流处理器的时钟精确模拟器，并用流编程模型来编程。Imagine处理器[4][5][6]有8个运算簇，可以开发流程序的数据级并行性。软件管理的片上存储系统可以很好的捕获程序的数据局部性。我们使用的流编程模型包括StreamC/KernelC两级编程语言。流编程语言的主要思想是把相关数据的集合组成一个记录，再把有序的记录构成流。应用程序则被程序员分解成一些对大量流数据进行操作的计算函数（kernel），对输入流中数据进行计算，并把计算结果作为下一个计算函数的输入。

3 并行结果

在流处理器平台上，我们获得了图1中的数据，可以看出随着输入集规模的不断增加，流处理器也能获得不错的加速比。一方面流处理器中的大量的计算单元可以完成众多的计算操作，另一方面流处理器中软件管理的片上存储系统很好的开发了计算函数间的数据局部性，这两点使得并行算法在流处理器获得了不错的加速效果。

4 结论

本文首先讨论了求解近似三对角Toeplitz方程组的串行算法，然后在其分布式算法的基础上，描述了在流处理器上并行化算法的步骤，最后给出了并行化结果，说明了并行算法在流处理器平台上获得了较高的并行效率。

参考文献

[1] 单润红，高峰.近似三对角Toeplitz 方程组的快速分布式并行算法.

[2] 面向结构的并行算法——设计与分析.

[3] 赵自春，李晓梅1 Toeplitz 循环三对角方程组的并行解法1 国防系统分析与软件，1989，（2）：50-55.

[4] Scott Rixner1，William J. Dally. A Bandwidth-Efficient Architecture for Media Processing. Micro-31 （1998）.

[5] Ujval J. Kapasi， William J. Dally， Scott Rixner. The Imagine Stream Processor.

[6] Jung Ho Ahn， William J. Dally， Brucek Khailany. Evaluating the Imagine Stream Architecture.

作者简介：张传龙（1982-），男，安徽淮南人，安徽理工大学计算机学院2010级工程在读硕士研究生，研究方向：计算机科学与技术。