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

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

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

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

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

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