用于處理性能瓶頸的面向內(nèi)存的優(yōu)化技術(shù)

    內(nèi)存是嵌入式系統(tǒng)的一個(gè)關(guān)鍵瓶頸。許多嵌入式計(jì)算應(yīng)用程序花費(fèi)大量時(shí)間訪問內(nèi)存。內(nèi)存系統(tǒng)不僅是性能的主要決定因素，也是能耗的主要決定因素。
    內(nèi)存系統(tǒng)優(yōu)化可以針對(duì)內(nèi)存層次結(jié)構(gòu)的任何階段。通用和嵌入式社區(qū)已經(jīng)開發(fā)了多種技術(shù)來(lái)優(yōu)化緩存性能。近，已開發(fā)出暫存器存儲(chǔ)器的優(yōu)化技術(shù)。優(yōu)化還可以針對(duì)主存儲(chǔ)器，特別是當(dāng)它們被分區(qū)時(shí)。
    內(nèi)存系統(tǒng)優(yōu)化可以針對(duì)數(shù)據(jù)或指令。數(shù)組優(yōu)化是一類重要的面向數(shù)據(jù)的優(yōu)化?？刂屏鞣治鰩?lái)了改進(jìn)指令緩存行為的方法。全局內(nèi)存分析在嵌入式系統(tǒng)中尤為重要。
    許多嵌入式系統(tǒng)由許多在它們之間傳遞數(shù)據(jù)的子系統(tǒng)組成。這些子系統(tǒng)之間的緩沖區(qū)必須仔細(xì)調(diào)整大小，以避免緩沖區(qū)溢出和內(nèi)存浪費(fèi)。
    循環(huán)轉(zhuǎn)換
    一些優(yōu)化是在編譯早期應(yīng)用的，無(wú)需詳細(xì)了解目標(biāo)硬件。此類轉(zhuǎn)換試圖公開可供后續(xù)階段使用的并行性。循環(huán)是此類轉(zhuǎn)換的主要候選者，因?yàn)樗鼈兛梢詾閿?shù)據(jù)并行性提供重要的來(lái)源。
    循環(huán)變換在科學(xué)程序和優(yōu)化編譯器中的應(yīng)用已經(jīng)被研究了幾十年。這里沒有足夠的篇幅來(lái)闡述這個(gè)主題；我們僅介紹一些概念來(lái)說明如何使用該工作主體。

    理想的循環(huán)可以完全并行執(zhí)行。圖 3-15左側(cè)的代碼 有一個(gè)循環(huán)體，其中所有數(shù)組僅由i索引。因此，循環(huán)迭代不依賴于任何其他迭代。因此，所有循環(huán)體可以以任何順序并行執(zhí)行，而不會(huì)影響結(jié)果。在圖右側(cè)的代碼中，第i次 迭代取決于第i-1次 迭代的結(jié)果。

    圖 3-15 循環(huán)中的并行性和約束
    在這種情況下，在i – 1也完成之前我們無(wú)法完成迭代 i ，因此這些循環(huán)體必須按照循環(huán)枚舉的順序完成。從一個(gè)循環(huán)迭代到另一循環(huán)迭代的數(shù)據(jù)依賴性稱為循環(huán)攜帶依賴性
    編譯器必須調(diào)度操作，以便它們不會(huì)違反數(shù)據(jù)依賴性，即代碼在計(jì)算之前不會(huì)嘗試使用值。一般來(lái)說，許多可能的調(diào)度都滿足數(shù)據(jù)依賴性，只要我們有辦法枚舉這些依賴性。雖然單個(gè)循環(huán)可能提供一些機(jī)會(huì)，但循環(huán)嵌套提供了許多需要詳細(xì)分析的并行可能性。

    如圖 3-16所示，循環(huán)嵌套是一組循環(huán)，一個(gè)循環(huán)又一個(gè)循環(huán)。完美的循環(huán)嵌套在嵌套內(nèi)沒有條件。不完美的循環(huán)嵌套具有導(dǎo)致嵌套中的某些語(yǔ)句在某些情況下無(wú)法執(zhí)行的條件。

    圖 3-16：循環(huán)嵌套
    循環(huán)和循環(huán)嵌套具有許多數(shù)據(jù)依賴性——每次迭代中的每個(gè)操作都會(huì)生成自己的數(shù)據(jù)依賴性。然而，我們也知道循環(huán)提供了我們可以利用的結(jié)構(gòu)和規(guī)律性。循環(huán)和循環(huán)嵌套的一些可能的轉(zhuǎn)換包括：
    循環(huán)排列會(huì)更改嵌套中循環(huán)的順序。
    索引重寫改變了循環(huán)索引的表達(dá)方式。
    循環(huán)展開創(chuàng)建循環(huán)體的多個(gè)副本并適當(dāng)?shù)匦薷难h(huán)索引。
    循環(huán)拆分采用具有多個(gè)操作的循環(huán)，并為每個(gè)操作創(chuàng)建一個(gè)單獨(dú)的循環(huán)；循環(huán)融合執(zhí)行相反的操作。
    循環(huán)平鋪將循環(huán)拆分為循環(huán)嵌套，每個(gè)內(nèi)部循環(huán)處理一小塊數(shù)據(jù)。
    循環(huán)填充將數(shù)據(jù)元素添加到數(shù)組中，以更改數(shù)組映射到內(nèi)存系統(tǒng)結(jié)構(gòu)的方式。
    多胞體模型 [1; 4]通常用于表示和操作循環(huán)嵌套中的數(shù)據(jù)依賴關(guān)系。
    內(nèi)部循環(huán)體修改c的值，創(chuàng)建從c[i ][j ] 到c[i ][j + 1] 的數(shù)據(jù)依賴關(guān)系。我們將數(shù)組中的每個(gè)數(shù)據(jù)元素表示為二維空間中的節(jié)點(diǎn)，循環(huán)迭代變量形成空間的軸。這些節(jié)點(diǎn)在該空間中以三角形定義多面體。
    我們?cè)诿枋鯿[i ][j ]和c[i ][j + 1]之間循環(huán)傳遞依賴關(guān)系的節(jié)點(diǎn)之間添加邊。多胞體中的點(diǎn)完全描述了所有循環(huán)攜帶的依賴關(guān)系，但我們尚未降低該表示的復(fù)雜性。我們可以使用距離向量來(lái)描述一組向量的方向和距離。在這種情況下，所有數(shù)據(jù)依賴關(guān)系的形式都是[ij ] = [1 0]。執(zhí)行此計(jì)算的任何循環(huán)集都必須滿足這些循環(huán)攜帶的依賴性，但許多調(diào)度通常是可能的。我們可以應(yīng)用一個(gè)排序向量來(lái)描述循環(huán)訪問節(jié)點(diǎn)的順序。
    我們可以使用矩陣代數(shù)來(lái)操縱循環(huán)的形式。例如，如果我們想要交換循環(huán)，將j 放在外循環(huán)中，將i 放在內(nèi)循環(huán)中，我們可以將循環(huán)嵌套矩陣乘以交換矩陣，如下所示。
    這給出了循環(huán)嵌套
    for (j = 0; j < i ; j ++)
    for (i = 0; i < N; i ++)
    c [i + 1][ j ] = a[ i ][j ] *b[j];
    并非所有循環(huán)轉(zhuǎn)換都是合法的。 Wolf 和 Lam [15] 表明，如果所有變換后的依賴向量按字典順序都是正的，也就是說，如果它們?cè)诘臻g中不向后指向，則循環(huán)變換是合法的。
    并非所有重要的循環(huán)變換都可以通過矩陣代數(shù)來(lái)操作。例如，循環(huán)平鋪將一個(gè)大數(shù)組拆分為幾個(gè)較小的數(shù)組，以更改數(shù)組元素的遍歷順序。這種變換不能用矩陣操作來(lái)表示，但是一旦循環(huán)被平鋪，就可以使用矩陣方法來(lái)分析新的循環(huán)嵌套。
    循環(huán)置換和循環(huán)融合[16]可用于減少訪問矩陣元素所需的時(shí)間。當(dāng)循環(huán)排列用于將數(shù)組訪問順序更改為底層數(shù)據(jù)結(jié)構(gòu)中使用的順序時(shí)，可以減少延遲。多維數(shù)組由 C 以行優(yōu)先格式存儲(chǔ)，因此我們希望首先訪問行。圖 3-18 顯示了循環(huán)排列的示例。
    循環(huán)融合允許組合和重用不同循環(huán)中對(duì)同一數(shù)組的引用。還可以修改數(shù)組元素的布局，以更改它們映射到高速緩存或并行內(nèi)存系統(tǒng)的方式

    例如，轉(zhuǎn)置矩陣是循環(huán)置換的替代方法。還可以填充循環(huán)以更改數(shù)據(jù)元素落入緩存行的方式。緩存性能的提高可能足以彌補(bǔ)浪費(fèi)的內(nèi)存。
    鑒于內(nèi)存系統(tǒng)是系統(tǒng)功耗的主要貢獻(xiàn)者，我們預(yù)計(jì)循環(huán)轉(zhuǎn)換可能會(huì)損害或有助于程序的能耗。坎德米爾等人。 [9]通過使用SimplePower模擬幾個(gè)基準(zhǔn)程序的不同版本，研究了編譯器轉(zhuǎn)換對(duì)能耗的影響。
總結(jié)了他們的結(jié)果。他們?cè)诓煌幕鶞?zhǔn)上試驗(yàn)了不同類型的轉(zhuǎn)換，并測(cè)量了未優(yōu)化和優(yōu)化代碼的能耗，測(cè)試了每個(gè)程序?qū)崿F(xiàn)的多種緩存配置。
    這些實(shí)驗(yàn)的一個(gè)有趣結(jié)果是，除了循環(huán)展開之外，大多數(shù)優(yōu)化都會(huì)增加 CPU 內(nèi)核的能耗。鑒于坎德米爾等人。在技術(shù)參數(shù)中，能耗的增加被內(nèi)存系統(tǒng)能耗的減少所抵消，但不同的技術(shù)可能會(huì)導(dǎo)致此類轉(zhuǎn)換的凈能量損失。
    任何優(yōu)化策略都必須平衡內(nèi)存系統(tǒng)和的能耗。這些實(shí)驗(yàn)還表明，增加高速緩存大小和關(guān)聯(lián)性確實(shí)會(huì)以增加高速緩存中的靜態(tài)和動(dòng)態(tài)能耗為代價(jià)。
    這些技術(shù)參數(shù)的存儲(chǔ)系統(tǒng)其余部分的增益再次抵消了損失，但不同的技術(shù)可能會(huì)改變平衡。