并行程序設計語言中局部性機制的探討

王婧

摘 要：多核CPU的存儲層次越來越深而且越來越復雜，這已經成為優化大規模并行應用程序性能的關鍵瓶頸。目前并行程序設計語言和多核CPU有兩種局部性設計方法，一個是橫向局部性，另一個是縱向局部性，通過這兩種視角可以進一步了解現在并行程序設計語言中局部性機制的特點。文章就并行程序設計語言中局部性機制進行探討，深入分析其優缺點，探究未來并行程序設計語言設計的方向，指出新語言可以考慮這兩種局部性設計機制，希望能為相關從業者帶來一些參考。

關鍵詞：并行程序;設計語言;局部性機制

0 引言

為了解決訪問延遲與處理器速度之間的差距變大的問題，體系架構設計者在硬件上引入了存儲層次概念。同時，想要充分挖掘出存儲層次的硬件設計優點，并行程序設計語言要具備優秀的局部性機制，才能得到更高的性能。并行程序設計語言領域中，技術人員會逐步加入不同的局部性機制，進一步增強語言挖掘局部性的力度?？蒲腥藛T若要寫出性能高的代碼，需要考慮在并行程序設計語言和編程模型的設計中加入局部性的描述和表示機制，以方便科研人員利用這些機制來描述和挖掘算法及程序中的局部性[1]。

1 并行編程語言發展趨勢

隨著科技發展，多路多核處理器的出現使得MPI（Message Passing Interface）在優化設計并行算法時遇到困難，MPI是基于分布式存儲最受歡迎的編程方式。雖然MPI在節點間運行，OpenMP在節點內運行，這樣可以實現混合并行，但是這是兩種不一樣的并行語言，設計人員在設計時難度會增加。所以新并行編程語言一定要考慮到多層次并行的支持，進一步優化硬件層次的設計、訪存的延遲和帶寬等。數據局部性會成為重要的因素，新設計的編程語言要給技術人員定義數據局部性的機制，盡量減少訪存和通信次數，提高程序運行性能。存儲層次的復雜，使得并行程序設計語言中局部性機制更加重要，目前人們日益關注針對多核的存儲訪問局部性的算法研究，所以未來并行編程語言的研究重點是設計容易表達算法局部性的機制。

2 新設計的并行編程語言要具備的要點

首先要有具備縱向局部性和橫向局部性的顯式管理機制?，F在并行計算系統的存儲層次越來越復雜，如果只靠運行時系統和編譯器來處理局部性問題和并行性開發，不是最佳的處理方法，還要依靠技術人員的顯式管理。

新開發的并行編程語言要能夠應用在不一樣的并行編程模式中，比如任務并行、數據并行等。

統一管理程序的局部性和并行性，開發設計人員利用編程語言可以整體設計這兩種特性，想辦法減輕人員的工作負擔，同時又能夠開發高性能的并行程序，并且保證并行程序可在不同硬件平臺移植。

與Local View類似，這些方法雖然能夠幫助開發人員編程的效率，減輕他們的工作負擔，加快并行程序的開發進程，但是這種固定的處理數據方案也限制了更有效設計并行算法和數據劃分，而且也只能支持部分并行模式。雖然并行程序開發人員管理局部性可以復用分布類，但其實是有限的，就算是設計了大量的分布類，都很難高效使用。

3 并行程序設計語言中局部性機制

并行程序設計涉及多方面的知識，并非簡單的并行算法的設計，只有綜合考慮各方面的因素，才能設計出高效率的并行程序[2]。并行程序設計語言中局部性機制分為橫向局部性和縱向局部性兩種。對分布式并行程序設計而言，利用更多的局部性機制是橫向局部性，主要考慮怎么樣減少消息傳遞的開銷。而串行程序相反，考慮更多的是縱向局部性，現在已經有很多的文獻研究。

3.1? 并行程序設計語言中橫向局部性

橫向局部性是由于存儲位置的分布導致同一內存層次上的數據通信，例如Jacobi算法就是因為把數組數據分塊造成不同塊間的邊界通信。一般來說數據分布如果有不錯的空間局部性，就會有不錯的橫向局部性，但是橫向局部性不只有良好的空間局部性，還包括數據通信的開銷。并行程序設計語言的橫向局部性分為兩種設計，一種是像OpenMP，編譯器自動劃分和分配數據，另一種是像HPF，技術人員管理控制數據劃分和分配過程。

HPF編程模型和OpenMP，MPI都不一樣，前者為了管理并行程序設計語言中的橫向局部性，設計定義和它們不一樣的分布類型。在管理橫向局部性方面，顯然HPF優勢更大。開發人員運用HPF編寫程序時，一般運用編譯制導語句來進行數據的分塊，并行操作不同數據塊則運用forall語句，不過HPF描述數據局部性較單一。因為有劃分的內存地址空間，并行程序設計語言PGAS改進了OpenMP的存儲模型，但是數據分塊方法略有差異，思想還是差不多，由開發人員來管理數據分塊，運行時系統和編譯器管理線程間的通信。

3.2? 并行程序設計語言中縱向局部性

不同存儲層次之間的局部性就是縱向局部性，比如內存和Cache?？v向局部性還可以從時間和空間來分成兩種。隨著科技的發展，并行計算系統存儲層次越來越復雜，CPU性能和內存訪問性能之間的差距正在擴大。想要提高計算程序的性能，就一定要考慮到數據的縱向局部性。同時，這種考慮往往不具備可移植性，所以在對并行編程模型重新設計時，一定要顯式管理存儲層次，尤其是出現多核處理器后，讓并行程序對存儲層次進行顯式管理，進一步優化縱向局部性，是一種提升程序性能的重要方法。

在顯式管理縱向局部性方面，現在已經有多個基于Cell處理器的編程模型?？v使Cell SDK可以位于Cell核內部完成MPI編程，也可以位于獨立地址空間實施Pthread編程，然而Cell SDK在局部性管理上仍有缺陷，橫向局部性管理導致并行編程的難度大大增加，縱向局部性管理也只是實現了不同存儲層次間的通信，擴展性和可移植性很差。

Sequoia是為了應對Cell SDK的這些缺陷而出現的，現在是組成Cell的重要部分。開發人員可以用Sequoia顯式管理存儲層次，設計出性能更加好的算法。在顯式管理縱向局部性時，Sequoia設置數據傳遞大小會考慮底層硬件平臺的不同存儲層次特征，更好地顯式管理縱向局部性。不過計算機集群系統卻沒有上面所說的共享機制，它的計算節點是經由高速網絡之后連接，Sequoia為實現物理內存的抽象特意添加虛擬層。因此Sequoia不管是縱向局部性還是橫向局部性都可以管理，并且應該允許技術人員的繼續優化，不斷提升程序的性能?？傊瓹ell SDK可以顯式管理每個層次，可以看成是具備兩個存儲層次的Sequoia。

3.3? 綜合兩種局部性

在算法設計和并行實現時，想要讓并行程序的性能更高，就需要對縱向局部性和橫向局部性加以考慮。并行編程語言設計好了關于橫向局部性的管理機制，比如PGAS和MPI，不管用哪個通信機制，都是為了讓開發人員更好實現對橫向局部性的顯式管理，并且盡量減少通信開銷。當并行應用程序采用了這些編程語言時，橫向局部性、并行性挖掘和并行模式等都會考慮到，因此可以將并行性完美融合橫向局部性。在縱向局部性方面，由Sequoia設計出來的task，便于編程語言管理并行和兩種局部性，它既能制定多層次的并行模式，又有管理縱向局部性和橫向局部性的機制。在開發新的編程模型時可以考慮以上方式，編寫出更高效和性能更好的應用程序。

4 結語

現如今計算機存儲系統越來越復雜，尤其是多核處理器的出現，系統更加難以開發局部性，所以更加顯出局部性的描述和表示機制的優勢。局部性機制可以幫助研究人員寫的代碼性能更好，進一步挖掘算法。本文分析了并行程序設計語言和多核處理器的狀況，探討了未來并行程序設計語言的發展趨勢，詳細分析了并行程序設計語言中局部性機制的各種定義和應用。并行程序設計語言中局部性機制主要是分為縱向局部性和橫向局部性兩種，文章分別從這兩個視角來著重分析了局部性機制，對設計并行編程模型的方向更加明確。

[參考文獻]

[1]袁良，張云泉，白雪瑞，等.并行程序設計語言中局部性機制的研究[J].計算機科學，2020（1）：7-16.

[2]黃偉文，姚文慶.并行程序設計[J].寧波職業技術學院學報，2002（2）：87-90.

（編輯 何 琳）