DSP應用優(yōu)化技術(shù)――第二部分
簡(jiǎn)介
數字信號處理 (DSP) 是一種采用增強功能處理信號與數據,以及修改這些信號的方法。數字信號處理技術(shù)還可用于分析信號,以確定特定的信息內容。DSP 主要涉及真實(shí)信號的處理。這些信號根據序號進(jìn)行轉換與表示。然后采用數學(xué)方法處理這些信號,以便從信號提取特定信息或者以某種方式轉換信號。
DSP 一般駐留在實(shí)時(shí)嵌入式系統,其中計算的及時(shí)性與其正確性同等重要。DSP 在這些環(huán)境中很普通,因為對它們經(jīng)過(guò)精心設計后,可非常迅速地執行常見(jiàn)的信號處理運算。DSP 的可編程性使應用能夠隨時(shí)間而改變和演進(jìn),從而為應用供應商提供眾多優(yōu)勢。對 DSP 編程需要了解應用、DSP 硬件架構、以及用于生成可滿(mǎn)足系統緊迫期限要求的高效實(shí)時(shí)軟件代碼生成工具。
本文是系列文章的第二部分,總結在實(shí)踐中從高性能 DSP 獲得數量級速度提高所采用的某些技術(shù)。
優(yōu)化的首要原則----切勿盲動(dòng)!
在開(kāi)始進(jìn)行任何優(yōu)化之前,您必須了解從何處著(zhù)手。就性能方面來(lái)看,并非所有軟件生來(lái)相同!您必須首先了解瓶頸在何處。一旦分析了應用,就可以開(kāi)始調整代碼。應用程序分析意味著(zhù)權衡需在每部分代碼所花費的時(shí)間(或者所占用的內存、所消耗的功率)。軟件的某些部分可能只執行一次(初始化)或者只執行少數幾次。如果費盡心思優(yōu)化此部分代碼并非明智之舉,因為獲得的整體節省效果會(huì )是微乎其微。更可能的情況是,會(huì )有幾部分軟件執行很多次,盡管代碼自身可能會(huì )很短,但代碼執行頻繁意味著(zhù)花費在該代碼的總循環(huán)會(huì )很多。即使如果您在這些代碼中可以節省一、兩個(gè)循環(huán),所獲得的節省也會(huì )很可觀(guān)。這就是在調整和優(yōu)化過(guò)程中您應該多費些時(shí)間的地方。
并行是關(guān)鍵所在
在編程超量標及 VLIM 期間時(shí)所要遵循的標準原則是"保持流水線(xiàn)充滿(mǎn)"(Keep the pipelines full!)。充滿(mǎn)的流水線(xiàn)意味著(zhù)有效的代碼。為了確定流水線(xiàn)充滿(mǎn)的程度,您需要費些時(shí)間檢查匯編程序生成的匯編語(yǔ)言代碼。通??梢愿鶕a中NOP 的冗余性檢查低效的代碼。
為了證明在基于 VLIW 的超量標機器中并行性的優(yōu)勢,讓我們首先從圖 1 所示的簡(jiǎn)單循環(huán)程序入手。如果我們準備編寫(xiě)此程序的串行匯編語(yǔ)言實(shí)施,其代碼會(huì )與圖 2 中的類(lèi)似。此循環(huán)采用超量標機器的兩個(gè)可用側之一。通過(guò)指令與 NOP 計數,它需要 26 個(gè)循環(huán)來(lái)執行循環(huán)的每個(gè)迭代。但是,我們可以做得更好。
在這個(gè)例子中,需要注意兩件事情。許多執行單元并未使用,而是處于空閑狀態(tài)。這是對處理器硬件的浪費。其次,在匯編程序的此部分存在眾多延遲間隙(準確說(shuō)是 20 個(gè)),在其中 CPU 需要停滯下來(lái)等待加載或保存數據。在 CPU 停滯時(shí),不會(huì )進(jìn)行任何操作。在試圖處理大量數據時(shí),這對處理器是很糟糕的事情。
有眾多方法可以在等待數據期間保持 CPU 運轉。我們可以執行不依賴(lài)正在等待的數據的其他運算。我們還可以使用超量標結構的兩側來(lái)幫助加載和保存其他數據值。圖 3 中的代碼就是一種對串行版本的改進(jìn)。我們已經(jīng)將 NOP 的數量從 20 個(gè)降至了 5 個(gè)。我們還可以并行執行某些步驟。第 4 行和第 5 行同時(shí)執行向器件的兩個(gè)單元(D1 和 D2)的加載。此代碼還執行循環(huán)前的分支運算,然后充分利用與該運算相關(guān)的延遲來(lái)完成當前循環(huán)的運算。請注意,在該代碼中存在新的一列,它可指定您希望將哪次執行單元用于特定運算。這種指定執行單元的靈活性使您能夠更好地對運算進(jìn)行控制。
1 void example1(float *out, float *input1, float *input2)
2 {
3 int i;
4
5 for(i = 0; i < 100; i++)
6 {
7 out[i] = input1[i] * input2[i];
8 }
9 }
圖1:簡(jiǎn)單的C循環(huán)
1 ;
2 ; serial implementation of loop (26 cycles per iteration)
3 ;
4 L1: LDW *B++,B5 ;load B[i] into B5
5 NOP 4 ; wait for load to complete
6
7 LDW *A++,A4 ; load A[i] into A4
8 NOP 4 ; wait for load to complete
9
10 MPYSP B5,A4,A4 ; A4 = A4 * B5
11 NOP 3 ; wait for mult to complete
12
13 STW A4,*C++ ; store A4 in C[i]
14 NOP 4 ; wait got store to complete
15
16 SUB i,1,i ; decrement i
17 [i] B L1 ; if i != 0, goto L1
18 NOP 5 ; delay for branch
圖2:C循環(huán)的串行匯編語(yǔ)言實(shí)施
1 ; using delay slots and duplicate execution units of the device
2 ; 10 cycles per iteration
3
4 L1: LDW .D2 *B++,B5 ;load B[i] into B5
5 || LDW .D1 *A++,A4 ;load A[i] into A4
6
7 NOP 2 ; wait load to complete
8 SUB .L2 i,1,i ;decrement i
9 [i] B .S1 L1 ; if i != 0, goto L1
10
11 MPYSP .M1X B5,A4,A4 ; A4 = A4 * B5
12 NOP 3 ; wait mpy to complete
13
14 STW .D1 A4,*C++ ;store A4 into C[i]
圖3:C循環(huán)更具并行性的實(shí)施
循環(huán)展開(kāi)
循環(huán)展開(kāi)是一種用于提高在循環(huán)分支邏輯之間執行的、指令數量的技術(shù)。它可以降低執行循環(huán)分支邏輯的次數。由于循環(huán)分支邏輯是額外開(kāi)銷(xiāo),降低其次數可以減少開(kāi)銷(xiāo),而且可以使循環(huán)主體-結構的重要部分運行更快。通過(guò)復制循環(huán)主體一定次數、然后修改終端邏輯來(lái)理解循環(huán)主體的多個(gè)迭代,可以展開(kāi)一個(gè)循環(huán)。循環(huán)展開(kāi)的缺點(diǎn)是使用更多的片上寄存器。每個(gè)迭代需要使用不同的寄存器。一旦使用了可用的寄存器,處理器就會(huì )開(kāi)始訪(fǎng)問(wèn)堆棧保存所需要的數據。訪(fǎng)問(wèn)片外堆棧需要很高的代價(jià),并且有可能消除由展開(kāi)循環(huán)而實(shí)現的增益。只有在循環(huán)的單個(gè)迭代循環(huán)展開(kāi)中的運算沒(méi)有使用處理器結構的全部可用資源時(shí),才可以使用循環(huán)展開(kāi)。如果您對此不很確定,請檢查匯編語(yǔ)言輸出。另一個(gè)缺點(diǎn)是增加代碼長(cháng)度。展開(kāi)后的循環(huán)需要更多指令,進(jìn)而需要更多內存。
{{分頁(yè)}}
軟件流水線(xiàn)化
最佳優(yōu)化策略之一是編寫(xiě)能夠由匯編程序有效流水線(xiàn)化的代碼。軟件流水線(xiàn)化是一種有效調度循環(huán)和功能單元的優(yōu)化策略。比如在 TMS320C62x™ 生成中,如果匯編程序了解如何操作,則存在 8 個(gè)可以同時(shí)使用的功能單元。有時(shí)只是 C 代碼結構的細微更改,其就有可能產(chǎn)生大為不同的結果。在軟件流水線(xiàn)化中,會(huì )調度循環(huán)的多個(gè)迭代來(lái)并行執行。循環(huán)會(huì )被重新組織,其結果是流水線(xiàn)化后的代碼中的每個(gè)迭代都是由從原始循環(huán)中不同迭代選擇的指令序列構成。在圖 4 所示的例子中說(shuō)明了一個(gè)帶 3 個(gè)迭代的 5 步驟循環(huán)。在管線(xiàn)被 "primed" 或者最初加載運算時(shí),存在一個(gè)稱(chēng)為 prolog 的初始階段(循環(huán) n 與 n+1)。循環(huán) n+2~n+4 是實(shí)際流水線(xiàn)化后的代碼部分。處理器就是在此部分中針對三個(gè)不同循環(huán)(1、2、3)執行不同運算(C、B、A)。這里存在一個(gè) epilog 部分,其中,退出循環(huán)之前執行剩余的指令。只是一套充分利用的流水線(xiàn),其可生成速度最快、效率最高的代碼。
如圖 5 所示,軟件流水線(xiàn)化比循環(huán)展開(kāi)速度更快,因為盡管建立流水線(xiàn)的開(kāi)銷(xiāo)更為復雜,但是只執行一次,而在展開(kāi)的循環(huán)中卻要執行多次,在標準循環(huán)建立過(guò)程中會(huì )執行許多次。
圖 4:軟件管道化的五步驟管道
圖 5:標準循環(huán)開(kāi)銷(xiāo)與循環(huán)展開(kāi)及軟件流水線(xiàn)化的對比
圖 6 說(shuō)明同樣簡(jiǎn)單的部分 C 代碼以及相應的匯編語(yǔ)言輸出。在此例中,要求匯編程序嘗試流水線(xiàn)化代碼。匯編語(yǔ)言輸出中的流水線(xiàn)化后的循環(huán) prolog 和循環(huán)核心部分就是證明。在這個(gè)例子中,流水線(xiàn)化的代碼并未達到其最佳效果。您可以通過(guò)查看代碼流水線(xiàn)化后的循環(huán)核心中存在多少 NOP 來(lái)檢查低效的代碼。此例中,流水線(xiàn)化后的循環(huán)核心總共有 5 個(gè) NOP 循環(huán),第 16 行中 2 個(gè),第 20 行中 3 個(gè)。此循環(huán)共需要執行 10 個(gè)循環(huán)。NOP 是能夠實(shí)現更有效循環(huán)的首要證據。但是,這個(gè)循環(huán)到底能夠有多短呢?預計最小循環(huán)長(cháng)度的一個(gè)方法是確定哪個(gè)執行單元使用次數最多。在該例中,單元 D 比其他任何單元使用得都更頻繁,總共使用 3 次(第14、15 與 21 行)。超量標器件存在兩側,從而在最低 2 個(gè)時(shí)鐘的循環(huán)中每個(gè)時(shí)鐘可以使用每個(gè)單元兩次(D1 和 D2),即一個(gè)時(shí)鐘 2 次 D 運算,第二個(gè)時(shí)鐘中 1 個(gè) D 單元。匯編程序具有足夠的智能在流水線(xiàn)的兩側使用 D 單元(第 14 行和第 15 行),從而使它能夠并行化指令并且只使用 1 個(gè)時(shí)鐘。在等待完成加載的同時(shí)可以執行其他指令,而不是坐等 NOP 延遲浪費時(shí)間。
{{分頁(yè)}}
1 void example1(float *out, float *input1, float *input2)
2 {
3 int i;
4
5 for(i = 0; i < 100; i++)
6 {
7 out[i] = input1[i] * input2[i];
8 }
9 }
1 _example1:
2 ;** ---------------------------------------------------------*
3 MVK .S2 0x64,B0
4
5 MVC .S2 CSR,B6
6 || MV .L1X B4,A3
7 || MV .L2X A6,B5
8 AND .L1X -2,B6,A0
9 MVC .S2X A0,CSR
10 ;** ---------------------------------------------------------*
11 L11: ; PIPED LOOP PROLOG
12 ;** ---------------------------------------------------------*
13 L12: ; PIPED LOOP KERNEL
14 LDW .D2 *B5++,B4 ;
15 || LDW .D1 *A3++,A0 ;
16 NOP 2
17 [ B0] SUB .L2 B0,1,B0 ;
18 [ B0] B
.S2 L12 ;
19 MPYSP .M1X B4,A0,A0 ;
20 NOP 3
21 STW .D1 A0,*A4++ ;
22 ;** --------------------------------------------------------*
23 MVC .S2 B6,CSR
24 B .S2 B3
25 NOP 5
26 ; BRANCH OCCURS
圖 6:C 語(yǔ)言例子以及相應流水線(xiàn)化的匯編語(yǔ)言輸出
在循環(huán)的簡(jiǎn)例中,很明顯輸入獨立于輸出。換句話(huà)說(shuō),并不存在相關(guān)性。但是,匯編程序對這點(diǎn)一無(wú)所知。匯編程序一般來(lái)說(shuō)是有點(diǎn)悲觀(guān)的小家伙。在形勢不明朗的情況下,它一般并不進(jìn)行任何優(yōu)化。匯編語(yǔ)言比較保守,會(huì )假定輸入每次通過(guò)循環(huán)時(shí)會(huì )依賴(lài)此前的輸出。如果了解了輸入與輸出無(wú)關(guān),我們就可以通過(guò)把 input1 和input2 斷言為 "const" 來(lái)提示匯編程序,向它說(shuō)明這些字段不會(huì )改變。這是進(jìn)行軟件流水線(xiàn)化和節省吞吐量的切入點(diǎn)。圖 7 說(shuō)明了這種 C 代碼及其相應匯編語(yǔ)言。
1 void example2(float *out, const float *input1, const float *input2)
2 {
3 int i;
4
5 for(i = 0; i < 100; i++)
6 {
7 out[i] = input1[i] * input2[i];
8 }
9 }
1 _example2:
2 ;** ---------------------------------------------------------------*
3 MVK .S2 0x64,B0
4
5 MVC .S2 CSR,B6
6 || MV .L1X B4,A3
7 || MV .L2X A6,B5
8
9 AND .L1X -2,B6,A0
10
11 MVC .S2X A0,CSR
12 || SUB .L2 B0,4,B0
13
14 ;** --------------------------------------------------------------*
15 L8: ; PIPED LOOP PROLOG
16
17 LDW .D2 *B5++,B4 ;
18 || LDW .D1 *A3++,A0 ;
19
20 NOP 1
21
22 LDW .D2 *B5++,B4 ;@
23 || LDW .D1 *A3++,A0 ;@
24
25 [ B0] SUB .L2 B0,1,B0 ;
26
27 [ B0] B .S2 L9 ;
28 || LDW .D2 *B5++,B4 ;@@
29 || LDW .D1 *A3++,A0 ;@@
30
31 MPYSP .M1X B4,A0,A5 ;
32 || [ B0] SUB .L2 B0,1,B0 ;@
33
34 [ B0] B .S2 L9 ;@
35 || LDW .D2 *B5++,B4 ;@@@
36 || LDW .D1 *A3++,A0 ;@@@
37
38 MPYSP .M1X B4,A0,A5 ;@
39 || [ B0] SUB .L2 B0,1,B0 ;@@
40
41 ;** --------------------------------------------------------------*
42 L9: ; PIPED LOOP KERNEL
43
44 [ B0] B .S2 L9 ;@@
45 || LDW .D2 *B5++,B4 ;@@@@
46 || LDW .D1 *A3++,A0 ;@@@@
47
48 STW .D1 A5,*A4++ ;
49 || MPYSP .M1X B4,A0,A5 ;@@
50 || [ B0] SUB .L2 B0,1,B0 ;@@@
51
52 ;** --------------------------------------------------------------*
53 L10: ; PIPED LOOP EPILOG
54 NOP 1
55
56 STW .D1 A5,*A4++ ;@
57 || MPYSP .M1X B4,A0,A5 ;@@@
58
59 NOP 1
60
61 STW .D1 A5,*A4++ ;@@
62 || MPYSP .M1X B4,A0,A5 ;@@@@
64 NOP 1
65 STW .D1 A5,*A4++ ;@@@
66 NOP 1
67 STW .D1 A5,*A4++ ;@@@@
68 ;** --------------------------------------------------------------*
69 MVC
.S2 B6,CSR
70 B .S2 B3
71 NOP 5
72 ; BRANCH OCCURS
圖 7:相應流水線(xiàn)化后的匯編語(yǔ)言輸出
在查看此匯編語(yǔ)言時(shí)需要留意幾點(diǎn)。首先,流水線(xiàn)化后的循環(huán)核心已經(jīng)縮小了。事實(shí)上,現在循環(huán)只有 2 個(gè)循環(huán)長(cháng)。第 44-47 行在循環(huán)的第一個(gè)循環(huán)執行(并行指令由 || 符號表示),第 48-50 行在第二個(gè)循環(huán)執行。利用我們通過(guò) "const" 斷言提供的附加相關(guān)性信息,匯編程序已經(jīng)能夠充分利用這些單元中的并行優(yōu)勢來(lái)高效地調用循環(huán)的內部部分。但是,這點(diǎn)需要一定代價(jià)。代碼的 prolog 和 epilog 部分現在已經(jīng)變得大得多了。更緊密的流水線(xiàn)化核心將需要更多啟動(dòng) (priming) 運算來(lái)根據各種指令和分支延遲協(xié)調所有的執行。但是,一旦啟動(dòng) (primed),核心循環(huán)就能夠以極其快的速度運行,在循環(huán)的各個(gè)迭代上執行運算。正如我們在前面所說(shuō)明,軟件流水線(xiàn)化的目標是提高經(jīng)常性事件速度。 核心在此例中就是經(jīng)常性事件,而且我們已經(jīng)大大提高了它的速度。對于循環(huán)計數比較小的循環(huán),可能不值得進(jìn)行代碼流水線(xiàn)化。但是,對于那些要執行數千次的循環(huán)計數較大的循環(huán)來(lái)說(shuō),軟件流水線(xiàn)化是唯一的出路。
{{分頁(yè)}}
在流水線(xiàn)化后的核心要執行的 2 個(gè)循環(huán)中,會(huì )有許多事情發(fā)生。在匯編語(yǔ)言列表中的右列說(shuō)明每條指令執行哪個(gè)迭代。每個(gè) "@" 符號表示迭代計數。因此,在這個(gè)核心中,第 44 行為迭代 n+2 執行分支,第 45 和 46 行為迭代 n+4 執行加載,第 48 行保存迭代的結果,第 49 行為迭代 n+2 執行乘法,而第 50 行為迭代 n+3 執行減法,這一切全在 2 個(gè)循環(huán)中完成。一旦流水線(xiàn)化后的核心停止執行,epilog 就會(huì )完成運算。匯編程序能夠使該循環(huán)變成 2 個(gè)循環(huán)長(cháng),這正是我們通過(guò)檢查低效代碼版本所期望達到的結果。
流水線(xiàn)化的功能的代碼長(cháng)度有所增加,看看所生成的代碼就一目了然。這是編程人員為了追求速度而不得不面對的折中之一。
在使用堆棧的程序中,還存在必須要解決的其他問(wèn)題。匯編程序必須確定在堆棧(需要更多時(shí)間訪(fǎng)問(wèn))中放置哪些變量以及要在快速片上寄存器中放置哪些變量。匯編程序有時(shí)并不能確定變量的去處。它會(huì )干脆不費神地嘗試去流水線(xiàn)化包含太多變量的循環(huán)。這種情況下,明智的做法是將大循環(huán)分成較小的循環(huán),并使匯編程序能夠對之進(jìn)行流水線(xiàn)化(圖 8)。
我們可以不采用:
for (expression)
{
Do A
Do B
Do C
Do D
}
而是采用:
for (expression)
Do A
for (expression)
Do B
for (expression)
Do C
for (expression)
Do D
圖 8:將大循環(huán)分成較小的循環(huán)能夠更有效地進(jìn)行流水線(xiàn)化
如果不仔細分析并結構化代碼,就不存在所謂的軟件流水線(xiàn)化。例如,不要流水線(xiàn)化沒(méi)有足夠處理功能的循環(huán)。另一方面,也不能流水線(xiàn)化具有太多處理功能的循環(huán),因為循環(huán)主體會(huì )耗盡可用的寄存器。此外,不能流水線(xiàn)化循環(huán)內的函數調用。相反,如果您希望獲得流水線(xiàn)化后的循環(huán),需要利用函數的內聯(lián)擴展來(lái)代替函數調用。
流水線(xiàn)化的缺陷之一是禁用中斷。完全 primed 管道中間的中斷會(huì )破壞指令執行中的協(xié)同配合 (synergy)。匯編程序會(huì )在進(jìn)入流水線(xiàn)化的部分之前禁用中斷來(lái)保護軟件流水線(xiàn)化運算,并在退出時(shí)啟用中斷(圖 9)。這意味著(zhù)獲得軟件流水線(xiàn)化效率的代價(jià)是不可搶先的代碼部分。編程人員必須能夠確定不可搶先代碼的部分對現實(shí)性能的影響。
圖 9:在代碼的軟件流水線(xiàn)化期間禁用的中斷
最后手段――匯編語(yǔ)言
經(jīng)??梢酝ㄟ^(guò)稍微修改 C 語(yǔ)言代碼來(lái)緩解這種狀況,但是獲得最佳(或接近最佳)解決方案需要時(shí)間和多個(gè)迭代。圖 10 說(shuō)明了采用這種方法優(yōu)化代碼的過(guò)程。最后的方法是采用匯編語(yǔ)言對算法進(jìn)行編碼。匯編語(yǔ)言難以編寫(xiě)、理解和維護。正在開(kāi)發(fā)相關(guān)工具使匯編語(yǔ)言編程人員更易于為超量標與 VLIW 處理器編寫(xiě)有效的代碼。例如,匯編語(yǔ)言?xún)?yōu)化器就能使編程人員編寫(xiě)串行匯編語(yǔ)言,然后自動(dòng)將其優(yōu)化到軟件流水線(xiàn)化后的循環(huán)中。
&
評論