并行程序设计语言中局部性机制的探讨

王婧

摘 要：多核CPU的存储层次越来越深而且越来越复杂，这已经成为优化大规模并行应用程序性能的关键瓶颈。目前并行程序设计语言和多核CPU有两种局部性设计方法，一个是横向局部性，另一个是纵向局部性，通过这两种视角可以进一步了解现在并行程序设计语言中局部性机制的特点。文章就并行程序设计语言中局部性机制进行探讨，深入分析其优缺点，探究未来并行程序设计语言设计的方向，指出新语言可以考虑这两种局部性设计机制，希望能为相关从业者带来一些参考。

关键词：并行程序;设计语言;局部性机制

0 引言

为了解决访问延迟与处理器速度之间的差距变大的問题，体系架构设计者在硬件上引入了存储层次概念。同时，想要充分挖掘出存储层次的硬件设计优点，并行程序设计语言要具备优秀的局部性机制，才能得到更高的性能。并行程序设计语言领域中，技术人员会逐步加入不同的局部性机制，进一步增强语言挖掘局部性的力度。科研人员若要写出性能高的代码，需要考虑在并行程序设计语言和编程模型的设计中加入局部性的描述和表示机制，以方便科研人员利用这些机制来描述和挖掘算法及程序中的局部性[1]。

1 并行编程语言发展趋势

随着科技发展，多路多核处理器的出现使得MPI（Message Passing Interface）在优化设计并行算法时遇到困难，MPI是基于分布式存储最受欢迎的编程方式。虽然MPI在节点间运行，OpenMP在节点内运行，这样可以实现混合并行，但是这是两种不一样的并行语言，设计人员在设计时难度会增加。所以新并行编程语言一定要考虑到多层次并行的支持，进一步优化硬件层次的设计、访存的延迟和带宽等。数据局部性会成为重要的因素，新设计的编程语言要给技术人员定义数据局部性的机制，尽量减少访存和通信次数，提高程序运行性能。存储层次的复杂，使得并行程序设计语言中局部性机制更加重要，目前人们日益关注针对多核的存储访问局部性的算法研究，所以未来并行编程语言的研究重点是设计容易表达算法局部性的机制。

2 新设计的并行编程语言要具备的要点

首先要有具备纵向局部性和横向局部性的显式管理机制。现在并行计算系统的存储层次越来越复杂，如果只靠运行时系统和编译器来处理局部性问题和并行性开发，不是最佳的处理方法，还要依靠技术人员的显式管理。

新开发的并行编程语言要能够应用在不一样的并行编程模式中，比如任务并行、数据并行等。

统一管理程序的局部性和并行性，开发设计人员利用编程语言可以整体设计这两种特性，想办法减轻人员的工作负担，同时又能够开发高性能的并行程序，并且保证并行程序可在不同硬件平台移植。

与Local View类似，这些方法虽然能够帮助开发人员编程的效率，减轻他们的工作负担，加快并行程序的开发进程，但是这种固定的处理数据方案也限制了更有效设计并行算法和数据划分，而且也只能支持部分并行模式。虽然并行程序开发人员管理局部性可以复用分布类，但其实是有限的，就算是设计了大量的分布类，都很难高效使用。

3 并行程序设计语言中局部性机制

并行程序设计涉及多方面的知识，并非简单的并行算法的设计，只有综合考虑各方面的因素，才能设计出高效率的并行程序[2]。并行程序设计语言中局部性机制分为横向局部性和纵向局部性两种。对分布式并行程序设计而言，利用更多的局部性机制是横向局部性，主要考虑怎么样减少消息传递的开销。而串行程序相反，考虑更多的是纵向局部性，现在已经有很多的文献研究。

3.1  并行程序设计语言中横向局部性

横向局部性是由于存储位置的分布导致同一内存层次上的数据通信，例如Jacobi算法就是因为把数组数据分块造成不同块间的边界通信。一般来说数据分布如果有不错的空间局部性，就会有不错的横向局部性，但是横向局部性不只有良好的空间局部性，还包括数据通信的开销。并行程序设计语言的横向局部性分为两种设计，一种是像OpenMP，编译器自动划分和分配数据，另一种是像HPF，技术人员管理控制数据划分和分配过程。

HPF编程模型和OpenMP，MPI都不一样，前者为了管理并行程序设计语言中的横向局部性，设计定义和它们不一样的分布类型。在管理横向局部性方面，显然HPF优势更大。开发人员运用HPF编写程序时，一般运用编译制导语句来进行数据的分块，并行操作不同数据块则运用forall语句，不过HPF描述数据局部性较单一。因为有划分的内存地址空间，并行程序设计语言PGAS改进了OpenMP的存储模型，但是数据分块方法略有差异，思想还是差不多，由开发人员来管理数据分块，运行时系统和编译器管理线程间的通信。

3.2  并行程序设计语言中纵向局部性

不同存储层次之间的局部性就是纵向局部性，比如内存和Cache。纵向局部性还可以从时间和空间来分成两种。随着科技的发展，并行计算系统存储层次越来越复杂，CPU性能和内存访问性能之间的差距正在扩大。想要提高计算程序的性能，就一定要考虑到数据的纵向局部性。同时，这种考虑往往不具备可移植性，所以在对并行编程模型重新设计时，一定要显式管理存储层次，尤其是出现多核处理器后，让并行程序对存储层次进行显式管理，进一步优化纵向局部性，是一种提升程序性能的重要方法。

在显式管理纵向局部性方面，现在已经有多个基于Cell处理器的编程模型。纵使Cell SDK可以位于Cell核内部完成MPI编程，也可以位于独立地址空间实施Pthread编程，然而Cell SDK在局部性管理上仍有缺陷，横向局部性管理导致并行编程的难度大大增加，纵向局部性管理也只是实现了不同存储层次间的通信，扩展性和可移植性很差。

Sequoia是为了应对Cell SDK的这些缺陷而出现的，现在是组成Cell的重要部分。开发人员可以用Sequoia显式管理存储层次，设计出性能更加好的算法。在显式管理纵向局部性时，Sequoia设置数据传递大小会考虑底层硬件平台的不同存储层次特征，更好地显式管理纵向局部性。不过计算机集群系统却没有上面所说的共享机制，它的计算节点是经由高速网络之后连接，Sequoia为实现物理内存的抽象特意添加虚拟层。因此Sequoia不管是纵向局部性还是横向局部性都可以管理，并且应该允许技术人员的继续优化，不断提升程序的性能。总之Cell SDK可以显式管理每个层次，可以看成是具备两个存储层次的Sequoia。

3.3  综合两种局部性

在算法设计和并行实现时，想要让并行程序的性能更高，就需要对纵向局部性和横向局部性加以考虑。并行编程语言设计好了关于横向局部性的管理机制，比如PGAS和MPI，不管用哪个通信机制，都是为了让开发人员更好实现对横向局部性的显式管理，并且尽量减少通信开销。当并行应用程序采用了这些编程语言时，横向局部性、并行性挖掘和并行模式等都会考虑到，因此可以将并行性完美融合横向局部性。在纵向局部性方面，由Sequoia设计出来的task，便于编程语言管理并行和两种局部性，它既能制定多层次的并行模式，又有管理纵向局部性和横向局部性的机制。在开发新的编程模型时可以考虑以上方式，编写出更高效和性能更好的应用程序。

4 结语

现如今计算机存储系统越来越复杂，尤其是多核处理器的出现，系统更加难以开发局部性，所以更加显出局部性的描述和表示机制的优势。局部性机制可以帮助研究人员写的代码性能更好，进一步挖掘算法。本文分析了并行程序设计语言和多核处理器的状况，探讨了未来并行程序设计语言的发展趋势，详细分析了并行程序设计语言中局部性机制的各种定义和应用。并行程序设计语言中局部性机制主要是分为纵向局部性和横向局部性两种，文章分别从这两个视角来着重分析了局部性机制，对设计并行编程模型的方向更加明确。

[参考文献]

[1]袁良，张云泉，白雪瑞，等.并行程序设计语言中局部性机制的研究[J].计算机科学，2020（1）：7-16.

[2]黄伟文，姚文庆.并行程序设计[J].宁波职业技术学院学报，2002（2）：87-90.

（编辑 何 琳）