張斯偉

摘要: 通過分析存儲器的層次結(jié)構(gòu)，引出了從單處理器系統(tǒng)到多處理器系統(tǒng)存儲器層次結(jié)構(gòu)的新問題，即高速緩存一致性的問題。因此，在多線程同時對共享內(nèi)存進行讀寫操作時，Cache缺失和多處理器數(shù)據(jù)不一致會帶來的相應(yīng)的內(nèi)存讀寫性能損耗。該文基于這個問題，設(shè)計了面向多線程內(nèi)存讀寫延時的內(nèi)存讀寫效率的測試方法。并通過的實驗，指出了綁定同一個處理器，會使得對共享內(nèi)存數(shù)據(jù)訪問的效率提高。并基于這個測試結(jié)果給出了對并行程序的優(yōu)化建議。

關(guān)鍵詞:多處理器系統(tǒng)；內(nèi)存性能；性能評估

中圖分類號：TP316 文獻標識碼：A 文章編號：1009-3044(2012)36-8814-04

從單處理器系統(tǒng)到多處理器系統(tǒng)，是一次里程碑式的飛躍。而隨著電子器件成本的減少，多核系統(tǒng)的應(yīng)用也變得越來越廣泛。但是，多處理器系統(tǒng)比單處理器系統(tǒng)更負責(zé)，從而帶來了很多問題。在現(xiàn)在在單機系統(tǒng)中比較流行的SMP多核結(jié)構(gòu)，在內(nèi)存性能上，與單處理器系統(tǒng)就有很大不同。其中比較重要的一項就是高速緩存的數(shù)據(jù)一致性[1]。高速緩存的數(shù)據(jù)一致性問題表現(xiàn)在程序上，就是當(dāng)多處理器并行的處理同一個內(nèi)存中的數(shù)據(jù)，會造成L2 Cache的缺失，從而使得高速緩存的同步消耗掉一定的性能。而在以前的很多測試方法中，是沒有考慮在不同處理器上訪問同一個內(nèi)存的性能損耗，比如Lmbench測試套件[2]，Lmbench是對內(nèi)存從低地址到高地址，依次測量不同地址位的讀寫延時，而沒有考慮并行狀態(tài)下，數(shù)據(jù)同步的開銷。該文考慮到多處理器在數(shù)據(jù)一致性上的開銷，以及L2 Cache缺失率的影響，提出一種面向多線程內(nèi)存讀寫延時的內(nèi)存性能評估方法。

1 存儲器的層次結(jié)構(gòu)

在理想情況下，編程者總是希望存儲容量無限大，而訪存速度又是盡量快。解決這個問題的一個較經(jīng)濟的方法就是采用存儲器層次結(jié)構(gòu)，其依據(jù)是程序訪問的局部性原理和內(nèi)存技術(shù)的性能價格比原則。所謂程序的局部性原理，就是認為大部分程序不是均衡的訪問所有代碼和數(shù)據(jù)。而內(nèi)存技術(shù)的性能價格比原則是，存儲技術(shù)越快，價格越低，因此存儲讀寫越快，存儲器容量越小。為了解決存儲器讀寫速度與存儲器存儲大小之間的矛盾，依據(jù)程序的局部性理論，計算機的學(xué)者們提出了一種較為經(jīng)濟的解決辦法，就是存儲器的層次結(jié)構(gòu)。如圖1所示。

為了匹配CPU的高速計算，越是快速的存儲器，離CPU越近，當(dāng)然，考慮到性價比，存儲量也越小。當(dāng)CPU計算需要訪問數(shù)據(jù)的時候，則在離自己最近的存儲器層次讀取數(shù)據(jù)。當(dāng)相應(yīng)的存儲器層次訪問不到相應(yīng)的數(shù)據(jù)，則在更遠更慢存儲量更大的存儲層次訪問數(shù)據(jù)，如果依然訪問不到，則再往更遠的一層訪問，以此類推。我們稱在相應(yīng)的存儲器層次能訪問到目標數(shù)據(jù)稱為命中，不能訪問到目標數(shù)據(jù)稱為不命中。由于程序的局部性原理，在低層次離CPU較近的存儲器層次命中的概率非常的高。在現(xiàn)代計算機系統(tǒng)中，大部分程序的低層次存儲器Cache命中率高達90%以上[3]。

隨著CPU性能的提高，存取效率和計算速度之間的不平衡性變得越來越顯著，因此存儲層次的重要性不斷增加。例如，在1980年，微處理器是不帶Cache的，但是到了2001年，處理器內(nèi)部通常帶有兩級Cache。隨著多級存儲結(jié)構(gòu)的發(fā)展，數(shù)據(jù)的一致性問題也變得越來越復(fù)雜。所謂的數(shù)據(jù)的一致性問題，就是不同存儲器層次數(shù)據(jù)不一致的問題。舉個例子，當(dāng)CPU要讀寫數(shù)據(jù)時，總是操作離自己最近的存儲器，而當(dāng)CPU改變了低層次存儲器，比如Cache，中的數(shù)據(jù)時，由于存儲總線的速度較慢，因此大部分的系統(tǒng)結(jié)構(gòu)，都不會立即把Cache中相應(yīng)的數(shù)據(jù)塊寫入高一層的存儲器，比如內(nèi)存。那么在CPU改變Cache后，到Cache把相應(yīng)數(shù)據(jù)塊寫入內(nèi)存中這段時間。Cache中的數(shù)據(jù)和內(nèi)存中的數(shù)據(jù)時不一致的。這就是多級存儲層次中的數(shù)據(jù)一致性問題

2 多處理器的高速緩存一致性

在多處理器系統(tǒng)中，數(shù)據(jù)的一致性問題的影響變得更為嚴重[4]。因為多處理器系統(tǒng)中，并行程序并非像單處理器系統(tǒng)中的“偽并行”運行，而由于多處理器能夠同時執(zhí)行不同的指令流，并行程序變成了“真并行”運行。而此時，數(shù)據(jù)的不一致性造成的影響會更為嚴重，而相對的Cache性能成為影響多處理器系統(tǒng)的關(guān)鍵資源[5-6]。

舉個例子，CPU1修改內(nèi)存地址為A的數(shù)據(jù)，由X1變?yōu)閄2。而此時CPU1發(fā)現(xiàn)地址A的數(shù)據(jù)由于最近讀寫過，存在于L1 Cache中。那么CPU1會把L1 Cache中地址A的數(shù)據(jù)由X1修改為X2。假設(shè)此時CPU2要讀地址A的數(shù)據(jù)，并且L1 Cache中也存在地址A的數(shù)據(jù)。而由于存儲器層次的數(shù)據(jù)不一致性，如果CPU L1 Cache中的數(shù)據(jù)還未來得及寫回，會導(dǎo)致L2 Cache的數(shù)據(jù)與CPU1的數(shù)據(jù)不同。進而導(dǎo)致CPU2中L1 Cache中地址A上的值還是X1，并未修改為X2。這樣就會造成多處理器結(jié)構(gòu)中的高速緩存一致性問題。

一般情況下，如果在一個存儲系統(tǒng)中讀取的任意一個數(shù)據(jù)項返回的結(jié)果都是最近寫入的數(shù)值，那么可以認為該存儲器是一致的。簡單來說，存儲器行為包括兩個方面，第一個方面叫做高速緩存一致性，它定義了讀操作可以返回什么樣的數(shù)值。第二個方面較存儲器的一致性，它定義了寫入的數(shù)值什么時候才能被讀操作返回。第一個性質(zhì)為了保證程序的順序，第二個性質(zhì)定義了所謂的存儲器一致性是什么。

為了解決高速緩存一致性問題，處理器的設(shè)計人員在硬件上引入了一個協(xié)議，稱為高速緩存一致性協(xié)議來，來解決該問題。采用比較廣泛的有兩類協(xié)議，目錄式協(xié)議和監(jiān)聽式協(xié)議[7]。目錄式協(xié)議是把所有物理塊共享狀態(tài)存放在一個地點，通過訪問目錄，來同步數(shù)據(jù)。監(jiān)聽式就是在每個含有物理存儲器中數(shù)據(jù)塊副本的高速緩存還要保留在該數(shù)據(jù)塊的共享狀態(tài)，但是并不集中保存狀態(tài)。高速緩存通常放在共享存儲總線上，所有高速緩存對總線進行監(jiān)聽，來確定是否含有自己請求數(shù)據(jù)塊的副本。

因此在多處理器同時對同一塊內(nèi)存進行操作的時候，會造成L1 Cache的一致性同步開銷和L2 Cache缺失，這與單處理器系統(tǒng)有本質(zhì)上的不同。因此在多處理器系統(tǒng)中，多處理器對相同內(nèi)存操作的效率，影響著多線程程序?qū)?nèi)存的讀寫效率。

由測試結(jié)果，可以看出。不同線程綁定在同一個處理器上時，內(nèi)存讀寫表現(xiàn)出了較高的效率，綁定在同一個處理器上，延時大概比綁定在不同的處理器上減少4%~5%。而線程綁定在不同處理器上時，也表現(xiàn)出更高的不穩(wěn)定性，其標準偏差比綁定在同一個處理器上時高81.5%。

5 多處理器架構(gòu)下并行程序優(yōu)化建議

從單處理器系統(tǒng)到多處理器系統(tǒng)是一個飛躍，對編程者也是一個挑戰(zhàn)。由上述測試結(jié)果可見，無論是在相同處理器上還是不同處理器上，多線程在訪問共享內(nèi)存時都會造成較大的性能損失。因此在進行并行程序的編寫時，應(yīng)提高線程的獨立性，即減少線程間的數(shù)據(jù)相關(guān)。這樣，每個線程的指令流訪問獨立的數(shù)據(jù)流，提高程序的并行性。

但是在多線程程序中很難保證每個線程之間的數(shù)據(jù)不重合。這樣必然涉及共享內(nèi)存的訪問和數(shù)據(jù)訪問的同步。由上述測試結(jié)果可得，在線程間共享數(shù)據(jù)較大時，盡量使共享數(shù)據(jù)的線程綁定在同一個內(nèi)核上進行，這樣不僅內(nèi)存讀寫效率提升，而且效率也更加穩(wěn)定。

6 結(jié)束語

相對于單處理器系統(tǒng)，多處理器系統(tǒng)雖然在性能上獲得了大幅度的提升，但是也使得硬件和軟件結(jié)構(gòu)變得更加復(fù)雜。使得以前相對簡單的性能問題，由于多處理器的并行，變得比以前復(fù)雜。

該文首先分析了存儲器的層次結(jié)構(gòu)，引出了在多處理器結(jié)構(gòu)下，高速緩存一致性的問題，指出在多線程同時對共享內(nèi)存進行操作的時候，會出現(xiàn)線程同步和多處理器數(shù)據(jù)一致性帶來的性能損耗?；谶@一點，設(shè)計了面向多線程內(nèi)存讀寫延時的內(nèi)存讀寫效率的測試方法。并通過在Linux平臺上的實驗，指出了綁定同一個處理器，會使得對共享內(nèi)存數(shù)據(jù)訪問的效率提高。并基于這個測試結(jié)果給出了對并行程序的優(yōu)化建議。

參考文獻 ：

[1] Jeffey K,David O,Mark H,et al.The stanford FLASH multiprocessor[C]// Chicago, Illinois, USA:Proceedings of the 21st Annual ACM/IEEE International Symposium on Computer Architecture,1994: 302-313.

[2] BROWN A,SELTZER M. Operating system benchmarking in the wake of lmbench：a case study of the performance of netbsd on the Intel x86 architecture[C]∥ACM SIGMETRICS International Conference on the Measurement and Modeling of Computer Systems.NewYork,USA:ACM,1997:214-224.

[3] 左琦,黃洋.嵌入式應(yīng)用環(huán)境下的Cache性能分析[J].計算機工程,2006(1).

[4] Fedorova A, Seltzer M, Small C, et al. Throughput-oriented scheduling on chip multithreading systems, Technical ReportTR-17-04 [R]. Cambridge, USA: Harvard University,2004.

[5] 盧宇彤,楊學(xué)軍,所光.一種面向多核系統(tǒng)的并行計算任務(wù)分配方法[J].計算機研究與發(fā)展,2009, 23(2): 359-364.

[6] Kandemir M, Chen G. Locality-aware process scheduling for embedded MPSoCs, 2005[C]//Proceedings-Design, Automation and Test in Europe, DATE 05, v Ⅱ, Munich, Germany, March 7-11, 2005. Munich, Germany: IEEE Conference Publications, 2005.

[7] Hennessy J L,Patterson D A.Computer Architecture: A Quantitative Approach[M]. 4th ed. Morgan Kaufmann, 2006.