CMP中一種動態(tài)線程劃分算法及Cache共享數(shù)據(jù)的提取方法.pdf

1、片上多核處理器系統(tǒng)已經(jīng)成為處理器發(fā)展的主流趨勢，針對此類系統(tǒng)的并行程序的運行時優(yōu)化成為當(dāng)前研究中的熱點。并行線程調(diào)度優(yōu)化已經(jīng)成為提高系統(tǒng)資源利用率的關(guān)鍵之一，而傳統(tǒng)調(diào)度算法不能夠很好地適應(yīng)新型片上并行結(jié)構(gòu)的特性。本文中介紹了片上多核系統(tǒng)中線程的共享數(shù)據(jù)問題以及現(xiàn)階段解決策略，并針對此問題提出了一種動態(tài)線程劃分算法和一種支持此劃分算法的統(tǒng)計信息提取方法。
　　 本文首先設(shè)計一種信息提取方法，利用硬件性能監(jiān)測單元獲取算法所需的數(shù)據(jù)，

2、以保證動態(tài)劃分算法的可行性。針對數(shù)據(jù)量過大的問題，采用了時間抽樣方法減緩樣本數(shù)據(jù)增加速度。為了降低整體算法運行規(guī)模，根據(jù)遠(yuǎn)程訪問地址采用空間抽樣方法進(jìn)行抽樣分析，避免檢測所有cache的訪問情況，以此減少算法運行規(guī)模和存儲空間。
　　 在算法設(shè)計過程中，首先從抽樣統(tǒng)計信息中獲取線程之間的關(guān)系，建立一個無向帶權(quán)圖。然后采用子圖識別算法對整個圖進(jìn)行連通子圖地識別。不同于現(xiàn)有的聚集算法，本文在連通子圖識別以后對所得子圖進(jìn)行規(guī)模大小地判

3、斷，當(dāng)一個連通子圖中包含的線程節(jié)點數(shù)大于N/K時（Ⅳ是系統(tǒng)中線程總數(shù)，K代表處理器核的數(shù)目），對此子圖進(jìn)行進(jìn)一步分割使得每一個劃分結(jié)果都滿足負(fù)載平衡的要求。然后采用貪婪算法把所有連通子圖重新劃分為K組，每一組對應(yīng)一個處理器核。算法運行以后向系統(tǒng)提交分配結(jié)果，然后算法睡眠直到系統(tǒng)狀態(tài)再次觸發(fā)線程劃分算法。
　　 在算法實驗中，從兩個角度對比動態(tài)劃分算法的有效性，一個對比角度是通過在仿真系統(tǒng)上定制處理器系統(tǒng)，并且運行商業(yè)的基準(zhǔn)程序來

4、獲取數(shù)據(jù)源。在此數(shù)據(jù)源上從兩個方面分析所設(shè)計的算法效果，其一就是對比不同程序中算法的效果，這里表現(xiàn)最好的是SPECJBB2000，在初始配置中優(yōu)化幅度接近70％。其二是對同樣的應(yīng)用采用不同的任務(wù)負(fù)載強度。當(dāng)服務(wù)程序個數(shù)和每個程序的線程個數(shù)分別增加的時候，算法的效果都有所提高，并且在最佳實例中達(dá)到1OO%的優(yōu)化效果。而在程序個數(shù)和線程數(shù)量同時增加時，結(jié)果顯示最好的優(yōu)化效果減弱到60%左右，即隨著任務(wù)整體負(fù)載的增加，在分配時算法丟棄的關(guān)聯(lián)邊

5、更多，算法優(yōu)化效果減弱。
　　 另一個對比角度是基于隨機數(shù)據(jù)源的實驗，從實驗結(jié)果可以得出任務(wù)負(fù)載量的變化并不會對算法效果產(chǎn)生大的影響。但當(dāng)片上核心數(shù)量增加時，算法的效果略有提升。就總體而言，動態(tài)劃分算法取得了很可觀的優(yōu)化效果。
　　 為了觀察抽樣方法對數(shù)據(jù)特征的影響，本文對抽樣參數(shù)變化的影響進(jìn)行了分析。分別從時間跨度、空間抽樣向量長度、映射比例三個方面分析抽樣的影響。通過實驗對比得出時間抽樣跨度在N=100時統(tǒng)計數(shù)據(jù)特征