DSP應用優化技術――第二部分

簡介

　　數字信號處理 (DSP) 是一種采用增強功能處理信號與數據，以及修改這些信號的方法。數字信號處理技術還可用于分析信號，以確定特定的信息內容。DSP 主要涉及真實信號的處理。這些信號根據序號進行轉換與表示。然后采用數學方法處理這些信號，以便從信號提取特定信息或者以某種方式轉換信號。

　　DSP 一般駐留在實時嵌入式系統，其中計算的及時性與其正確性同等重要。DSP 在這些環境中很普通，因為對它們經過精心設計后，可非常迅速地執行常見的信號處理運算。DSP 的可編程性使應用能夠隨時間而改變和演進，從而為應用供應商提供眾多優勢。對 DSP 編程需要了解應用、DSP 硬件架構、以及用于生成可滿足系統緊迫期限要求的高效實時軟件代碼生成工具。

　　本文是系列文章的第二部分，總結在實踐中從高性能 DSP 獲得數量級速度提高所采用的某些技術。

優化的首要原則----切勿盲動！

　　在開始進行任何優化之前，您必須了解從何處著手。就性能方面來看，并非所有軟件生來相同！您必須首先了解瓶頸在何處。一旦分析了應用，就可以開始調整代碼。應用程序分析意味著權衡需在每部分代碼所花費的時間（或者所占用的內存、所消耗的功率）。軟件的某些部分可能只執行一次（初始化）或者只執行少數幾次。如果費盡心思優化此部分代碼并非明智之舉，因為獲得的整體節省效果會是微乎其微。更可能的情況是，會有幾部分軟件執行很多次，盡管代碼自身可能會很短，但代碼執行頻繁意味著花費在該代碼的總循環會很多。即使如果您在這些代碼中可以節省一、兩個循環，所獲得的節省也會很可觀。這就是在調整和優化過程中您應該多費些時間的地方。 

并行是關鍵所在

　　在編程超量標及 VLIM 期間時所要遵循的標準原則是"保持流水線充滿"（Keep the pipelines full!）。充滿的流水線意味著有效的代碼。為了確定流水線充滿的程度，您需要費些時間檢查匯編程序生成的匯編語言代碼。通常可以根據代碼中NOP 的冗余性檢查低效的代碼。

　　為了證明在基于 VLIW 的超量標機器中并行性的優勢，讓我們首先從圖 1 所示的簡單循環程序入手。如果我們準備編寫此程序的串行匯編語言實施，其代碼會與圖 2 中的類似。此循環采用超量標機器的兩個可用側之一。通過指令與 NOP 計數，它需要 26 個循環來執行循環的每個迭代。但是，我們可以做得更好。

　　在這個例子中，需要注意兩件事情。許多執行單元并未使用，而是處于空閑狀態。這是對處理器硬件的浪費。其次，在匯編程序的此部分存在眾多延遲間隙（準確說是 20 個），在其中 CPU 需要停滯下來等待加載或保存數據。在 CPU 停滯時，不會進行任何操作。在試圖處理大量數據時，這對處理器是很糟糕的事情。

　　有眾多方法可以在等待數據期間保持 CPU 運轉。我們可以執行不依賴正在等待的數據的其他運算。我們還可以使用超量標結構的兩側來幫助加載和保存其他數據值。圖 3 中的代碼就是一種對串行版本的改進。我們已經將 NOP 的數量從 20 個降至了 5 個。我們還可以并行執行某些步驟。第 4 行和第 5 行同時執行向器件的兩個單元（D1 和 D2）的加載。此代碼還執行循環前的分支運算，然后充分利用與該運算相關的延遲來完成當前循環的運算。請注意，在該代碼中存在新的一列，它可指定您希望將哪次執行單元用于特定運算。這種指定執行單元的靈活性使您能夠更好地對運算進行控制。

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：簡單的C循環

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循環的串行匯編語言實施

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循環更具并行性的實施

循環展開

　　循環展開是一種用于提高在循環分支邏輯之間執行的、指令數量的技術。它可以降低執行循環分支邏輯的次數。由于循環分支邏輯是額外開銷，降低其次數可以減少開銷，而且可以使循環主體－結構的重要部分運行更快。通過復制循環主體一定次數、然后修改終端邏輯來理解循環主體的多個迭代，可以展開一個循環。循環展開的缺點是使用更多的片上寄存器。每個迭代需要使用不同的寄存器。一旦使用了可用的寄存器，處理器就會開始訪問堆棧保存所需要的數據。訪問片外堆棧需要很高的代價，并且有可能消除由展開循環而實現的增益。只有在循環的單個迭代循環展開中的運算沒有使用處理器結構的全部可用資源時，才可以使用循環展開。如果您對此不很確定，請檢查匯編語言輸出。另一個缺點是增加代碼長度。展開后的循環需要更多指令，進而需要更多內存。

{{分頁}}

軟件流水線化

　　最佳優化策略之一是編寫能夠由匯編程序有效流水線化的代碼。軟件流水線化是一種有效調度循環和功能單元的優化策略。比如在 TMS320C62x™ 生成中，如果匯編程序了解如何操作，則存在 8 個可以同時使用的功能單元。有時只是 C 代碼結構的細微更改，其就有可能產生大為不同的結果。在軟件流水線化中，會調度循環的多個迭代來并行執行。循環會被重新組織，其結果是流水線化后的代碼中的每個迭代都是由從原始循環中不同迭代選擇的指令序列構成。在圖 4 所示的例子中說明了一個帶 3 個迭代的 5 步驟循環。在管線被 "primed" 或者最初加載運算時，存在一個稱為 prolog 的初始階段（循環 n 與 n+1）。循環 n+2～n+4 是實際流水線化后的代碼部分。處理器就是在此部分中針對三個不同循環（1、2、3）執行不同運算（C、B、A）。這里存在一個 epilog 部分，其中，退出循環之前執行剩余的指令。只是一套充分利用的流水線，其可生成速度最快、效率最高的代碼。

　　如圖 5 所示，軟件流水線化比循環展開速度更快，因為盡管建立流水線的開銷更為復雜，但是只執行一次，而在展開的循環中卻要執行多次，在標準循環建立過程中會執行許多次。

                
圖 4：軟件管道化的五步驟管道

圖　5：標準循環開銷與循環展開及軟件流水線化的對比

　　圖 6 說明同樣簡單的部分 C 代碼以及相應的匯編語言輸出。在此例中，要求匯編程序嘗試流水線化代碼。匯編語言輸出中的流水線化后的循環 prolog 和循環核心部分就是證明。在這個例子中，流水線化的代碼并未達到其最佳效果。您可以通過查看代碼流水線化后的循環核心中存在多少 NOP 來檢查低效的代碼。此例中,流水線化后的循環核心總共有 5 個 NOP 循環，第 16 行中 2 個，第 20 行中 3 個。此循環共需要執行 10 個循環。NOP 是能夠實現更有效循環的首要證據。但是，這個循環到底能夠有多短呢？預計最小循環長度的一個方法是確定哪個執行單元使用次數最多。在該例中，單元 D 比其他任何單元使用得都更頻繁，總共使用 3 次（第14、15 與 21 行）。超量標器件存在兩側，從而在最低 2 個時鐘的循環中每個時鐘可以使用每個單元兩次（D1 和 D2），即一個時鐘 2 次 D 運算，第二個時鐘中 1 個 D 單元。匯編程序具有足夠的智能在流水線的兩側使用 D 單元（第 14 行和第 15 行），從而使它能夠并行化指令并且只使用 1 個時鐘。在等待完成加載的同時可以執行其他指令，而不是坐等 NOP 延遲浪費時間。

{{分頁}}

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 語言例子以及相應流水線化的匯編語言輸出

　　在循環的簡例中，很明顯輸入獨立于輸出。換句話說，并不存在相關性。但是，匯編程序對這點一無所知。匯編程序一般來說是有點悲觀的小家伙。在形勢不明朗的情況下，它一般并不進行任何優化。匯編語言比較保守，會假定輸入每次通過循環時會依賴此前的輸出。如果了解了輸入與輸出無關，我們就可以通過把 input1 和input2 斷言為 "const" 來提示匯編程序，向它說明這些字段不會改變。這是進行軟件流水線化和節省吞吐量的切入點。圖 7 說明了這種 C 代碼及其相應匯編語言。

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：相應流水線化后的匯編語言輸出

　　在查看此匯編語言時需要留意幾點。首先，流水線化后的循環核心已經縮小了。事實上，現在循環只有 2 個循環長。第 44－47 行在循環的第一個循環執行（并行指令由 || 符號表示），第 48－50 行在第二個循環執行。利用我們通過 "const" 斷言提供的附加相關性信息，匯編程序已經能夠充分利用這些單元中的并行優勢來高效地調用循環的內部部分。但是，這點需要一定代價。代碼的 prolog 和 epilog 部分現在已經變得大得多了。更緊密的流水線化核心將需要更多啟動 (priming) 運算來根據各種指令和分支延遲協調所有的執行。但是，一旦啟動 (primed)，核心循環就能夠以極其快的速度運行，在循環的各個迭代上執行運算。正如我們在前面所說明，軟件流水線化的目標是提高經常性事件速度。 核心在此例中就是經常性事件，而且我們已經大大提高了它的速度。對于循環計數比較小的循環，可能不值得進行代碼流水線化。但是，對于那些要執行數千次的循環計數較大的循環來說，軟件流水線化是唯一的出路。

{{分頁}}

　　在流水線化后的核心要執行的 2 個循環中，會有許多事情發生。在匯編語言列表中的右列說明每條指令執行哪個迭代。每個 "@" 符號表示迭代計數。因此，在這個核心中，第 44 行為迭代 n+2 執行分支，第 45 和 46 行為迭代 n+4 執行加載，第 48 行保存迭代的結果，第 49 行為迭代 n+2 執行乘法，而第 50 行為迭代 n+3 執行減法，這一切全在 2 個循環中完成。一旦流水線化后的核心停止執行，epilog 就會完成運算。匯編程序能夠使該循環變成 2 個循環長，這正是我們通過檢查低效代碼版本所期望達到的結果。

　　流水線化的功能的代碼長度有所增加，看看所生成的代碼就一目了然。這是編程人員為了追求速度而不得不面對的折中之一。

　　在使用堆棧的程序中，還存在必須要解決的其他問題。匯編程序必須確定在堆棧（需要更多時間訪問）中放置哪些變量以及要在快速片上寄存器中放置哪些變量。匯編程序有時并不能確定變量的去處。它會干脆不費神地嘗試去流水線化包含太多變量的循環。這種情況下，明智的做法是將大循環分成較小的循環，并使匯編程序能夠對之進行流水線化（圖 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：將大循環分成較小的循環能夠更有效地進行流水線化

　　如果不仔細分析并結構化代碼，就不存在所謂的軟件流水線化。例如，不要流水線化沒有足夠處理功能的循環。另一方面，也不能流水線化具有太多處理功能的循環，因為循環主體會耗盡可用的寄存器。此外，不能流水線化循環內的函數調用。相反，如果您希望獲得流水線化后的循環，需要利用函數的內聯擴展來代替函數調用。

　　流水線化的缺陷之一是禁用中斷。完全 primed 管道中間的中斷會破壞指令執行中的協同配合 (synergy)。匯編程序會在進入流水線化的部分之前禁用中斷來保護軟件流水線化運算，并在退出時啟用中斷（圖 9）。這意味著獲得軟件流水線化效率的代價是不可搶先的代碼部分。編程人員必須能夠確定不可搶先代碼的部分對現實性能的影響。

                                     
 圖 9：在代碼的軟件流水線化期間禁用的中斷

最后手段――匯編語言

　　經常可以通過稍微修改 C 語言代碼來緩解這種狀況，但是獲得最佳（或接近最佳）解決方案需要時間和多個迭代。圖 10 說明了采用這種方法優化代碼的過程。最后的方法是采用匯編語言對算法進行編碼。匯編語言難以編寫、理解和維護。正在開發相關工具使匯編語言編程人員更易于為超量標與 VLIW 處理器編寫有效的代碼。例如，匯編語言優化器就能使編程人員編寫串行匯編語言，然后自動將其優化到軟件流水線化后的循環中。

  &