以下文章來源于嵌入式系統(tǒng)專家之聲，作者Martin Ossmann

Martin Ossmann博士（德國）

翻譯：何靈淵

樹莓派Pico由RP2040微控制器驅動，其上搭載兩個CPU核，這讓它非常適合探索并行計算。本文通過真實的數(shù)字信號處理樣例來說明從雙核架構中提取最大價值的方法和考量。

本文中的樣例運用了不同的并行化手段。通過雙核處理器來加速一個程序的理論上限值為2，我們簡稱為S = 2。在下面的討論中，我們會給出每一個樣例的加速系數(shù)。

同步和“易變”屬性

在多核CPU上編程時，時常需要讓線程同步它們的活動。在下面這個最簡單的例子中，核0可以激活核1，通過變量trigger就可以實現(xiàn)。

圖1

兩個核都會使用變量trigger，為了讓編譯器知道變量的值由于多個線程都可使用，隨時可以改變，添加了“易變”（volatile）屬性。沒有這個屬性，編譯器可能會進行深入的代碼優(yōu)化，這也許會對兩個線程的共享、并行使用造成不良影響。

共享函數(shù)的使用

下面的例子演示了核0和核1可以同時使用一個函數(shù)。

圖2

函數(shù)delay(nn, cnt)中會打印消息列出正在運行的核和cnt的值，然后會進入等待循環(huán)執(zhí)行nn次（使用本地變量k）。

核0和核1一樣運行無限循環(huán)。循環(huán)內會調用delay函數(shù)，核0和1的nn參數(shù)分別為10000000和20000000，因此核1在delay函數(shù)中會執(zhí)行雙倍于核0次數(shù)的循環(huán)。cnt變量會跟蹤循環(huán)執(zhí)行的次數(shù)。兩個核多數(shù)時間都會同時在delay函數(shù)中。函數(shù)的共享是如何做到的呢？函數(shù)的代碼只會在內存中儲存一份，兩個核會執(zhí)行同樣的代碼。代碼中只有讀指令，所以只是訪問代碼并不會造成沖突。

兩個核當然有自己的程序計數(shù)器（PC），其中記載代碼指令的地址（代碼進行到了第幾步）。當函數(shù)被調用時，PC的值會入棧，參數(shù)也會入棧，然后會在棧上預約空間存儲本地變量（這里是k）。這一系列存儲在棧中的變量也被叫做棧幀。PC接下來會載入被調用函數(shù)的起始地址。

兩個核有獨立的棧和棧幀，所以即使代碼是共享的，兩個核也各自有一個delay函數(shù)的“實例”，代碼相同但是棧幀不同。如果delay函數(shù)中使用全局變量或者其他全局資源，分割就不復存在了，并行使用會導致問題。本例說明了并行編程需要考慮的問題。

核0可以影響核1的速度

下一個例子中我們將演示兩個核如何會以不明顯的方式互相影響。

圖3

核1運行簡單的無限循環(huán)，核0同樣運行無限循環(huán)，但是會將GPIO2設為高電平，等待625個周期，將GPIO2設為低電平，然后再等待625個周期。當核1不運行時，以Pico默認時鐘頻率125MHz運行的核0每秒會運行10萬次循環(huán)（125MHz/（2*625周期）），這會在GPIO2上輸出一個100kHz頻率的矩形波。當核1開始執(zhí)行時，核0的這一輸出信號頻率會降到75kHz。盡管兩個核之間沒有明顯的關聯(lián)，它們還是會互相影響。這其中的可能原因是兩個核共用同一個內存接口，這一現(xiàn)象通?？梢越忉尀槭裁幢疚闹谐绦虻募铀傧禂?shù)S一般都明顯低于2。

本例突出了并行程序中存在的意想不到的效果，調試這樣的并行程序可能會很有挑戰(zhàn)性。

先入先出（FIFO）通信

你可以通過兩個FIFO在兩個核之間安全地傳輸數(shù)據(jù)，一個從核0向核1發(fā)送數(shù)據(jù)，另一個從核1向核0發(fā)送數(shù)據(jù)。Pico SDK中的FIFO是線程安全的，意味著即使并行使用也能正常運行。

為了測試FIFO的性能，我們可以在核1上實現(xiàn)一個簡單的“服務器”：

圖4

這段代碼等待核0從FIFO發(fā)送數(shù)據(jù)，將得到的數(shù)字增加1000后返回給核0。

核0上運行的代碼如下：

圖5

運行時測量的數(shù)據(jù)表明，這段代碼大概需要0.62微秒。因為每次傳輸?shù)臄?shù)據(jù)為32位，這等同于104Mbit/s。下面這一計數(shù)循環(huán)用于比較樹莓派Pico的計算速度和數(shù)據(jù)傳輸率：

圖6

測量數(shù)據(jù)表明，每次循環(huán)需要大約56納秒。如果我們讓服務器運行N = 10次，計算時間大約560納秒，通信時間620納秒，通信的開銷比例大于100%。因此，如果不想要通信開銷影響整體性能，服務器需要大幅提高計算能力。在并行計算環(huán)境中編程時，最好不要過于關注程序中最小的細節(jié)。除了FIFO，SDK也提供了隊列，幫助傳輸任意數(shù)據(jù)結構，提供更大的靈活性。另外，SDK提供多種線程同步機制，推薦細致學習SDK提供的功能。

軟件定義無線電（SDR）的并行化

圖7所示的是SDR前端的組成，在將輸入信號和本機振蕩器（LO）信號相乘后，你得到了I頻道（同相）和Q頻道（正交）。兩個頻道幾乎是并行的，非常適合并行計算。核0處理I頻道的數(shù)據(jù)，核1處理Q頻道的數(shù)據(jù)。混合后的相加依然由中斷例程處理。第一個并行的部分是巴特沃斯濾波器的實現(xiàn)，使用單精度浮點數(shù)。在圖8中，你可以看到低通濾波器的時間特征。

圖7 SDR前端的信號流動

圖8 I和Q低通濾波器例程的執(zhí)行

核0進行I頻道低通濾波器計算時會輸出黃色的“高電平”，核1進行Q頻道低通濾波器計算時會輸出藍綠色的“高電平”。有趣的是，I頻道的計算需要更長時間，這是因為核0也執(zhí)行中斷例程進行取樣，所以核0并不是一直可以使用，I頻道的計算于是需要更長時間。

標量積和循環(huán)分割

另一個樣例是標量積的計算。并行計算是基于以下的觀察：通常一組計算以循環(huán)進行，如果一個循環(huán)中的元素可以單獨計算，一個循環(huán)可以被分隔為兩個部分，由兩個核并行處理。計算兩個向量x和y的標量積的公式如下圖所示：

圖9

程序中的skpLoop例程會通過下面的算式計算k1到k2的加和：

圖10

在非并行的版本中，1到N的值會被直接加和。在并行的版本中，1到N/2和N/2到N的加和是并行進行的，算式如下圖所示：

圖11

最終結果通過兩個部分相加得到。核0和核1同時使用skpLoop中的加和循環(huán)。因為循環(huán)由兩個核分別使用，矩陣xk和yk各自不同，所以沒有沖突。這一程序的加速系數(shù)S = 1.8，程序代碼如圖12所示。

圖12串行和并行標量積計算

有限脈沖響應（FIR）濾波器

FIR濾波器在數(shù)字信號處理應用中有著廣泛應用。在N階的FIR濾波器中，當前輸出值的計算需要將最后N個信號的值進行加和，期間會將樣本和脈波響應系數(shù)ak相乘，公式如下圖所示：

圖13

圖14 FIR濾波器的信號流動

計算中需要將最后N個輸入值xk存儲起來，這可以通過一個環(huán)形緩沖區(qū)很容易地進行。計算的并行化和其他標量計算類似，可以通過循環(huán)分割來進行。你只需要正確地管理環(huán)形緩沖區(qū)和使用腳標。循環(huán)的邏輯如下圖所示：

圖15

readPtr參數(shù)指向環(huán)形緩沖區(qū)xBuf的起始位置。并行的FIR計算如下圖所示：

圖16

本程序的加速系數(shù)S = 1.7。

程序開發(fā)

調試并行程序經(jīng)常既復雜又有挑戰(zhàn)性。一般可以首先在一個更為靈活的環(huán)境中編寫一個版本的程序作為參考版本，像是一個開源、免費的處理環(huán)境，然后在那里進行調試。在這一過程中，你可以生成用于并行的測試數(shù)據(jù)。這一版本的軟件成型后可以移植到目標系統(tǒng)上，并用同樣的測試數(shù)據(jù)進行測試。調試時你可以比較兩個版本的軟件行為。

帶流水線的無限脈沖響應（IIR）濾波器

在數(shù)字信號處理中，IIR濾波器十分常用。IIR濾波器是一由系列雙二階單元（圖17）組成的。非并行的形式中，一個單元的輸入和上個單元的輸出一致，也就是計算單元2前必需完成單元1的計算。

圖17一個雙二階單元

每個單元取決于上一個單元的結果，用代碼表示如下圖所示：

圖18

這使得雙二階單元計算的并行化變得困難，不過我們可以應用一種流水線技巧。流水線的概念是從實現(xiàn)快速的處理器開始的，將指令的執(zhí)行分割為取指令、解碼和執(zhí)行三個步驟，不同命令的不同步驟可以同時執(zhí)行。

當讀取指令Ik時，上一個指令I(k-1)已經(jīng)被解碼，再上一個指令I(k-2)正在執(zhí)行中（圖19）。這樣的并行處理能提高輸出，單個指令并沒有提速。

圖19 CPU中的流水線

這一概念可以應用到IIR濾波器上，代碼如下圖所示：

圖20

這里增加的中間值inp1到inp4讓單元的計算互為獨立，雙二階計算可以并行，這正是雙核CPU上運行IIR濾波器的方法。這里的方法加速系數(shù)S大約為1.8。

就地執(zhí)行（XIP）功能

如果你多次運行IIR濾波器并測量時間，你會有令人驚訝的發(fā)現(xiàn)（表1）。首次運行需要大約64微秒，這是后面運行的2.5倍左右。這一加速可以從RP2040訪問代碼存儲的角度解釋。代碼在串行QPSI閃存中存儲，CPU可以像直接訪問CPU中數(shù)據(jù)一樣訪問（所以是就地執(zhí)行，eXecute In Place——XIP）。由于閃存的訪問使用串行接口，速度相對較慢。為了加速，XIP接口上有一個基于快速RAM的緩存，其中存儲最近剛讀取的內存字，所以同樣位置的內存不需要經(jīng)過QPSI接口，而是直接從緩存讀取。

表1 IIR濾波器執(zhí)行時間

這一過程可以解釋運行時間的數(shù)據(jù)。首次運行時，代碼不能使用緩存，QSPI訪問既慢又是串行性的。代碼載入到緩存之后，再運行的速度就會變快。這從一方面說明現(xiàn)代CPU運行時行為的復雜性。你需要了解這樣的機制，才能得到正確和可靠的結果。

快速傅里葉變換（FFT）

在數(shù)字信號處理中，快速傅里葉變換（FFT）時常用于分析信號。FFT計算由所謂的“蝴蝶操作”組成，蝴蝶操作中的數(shù)據(jù)流動如圖21所示。

圖21蝴蝶操作中的信號流動

圖中系數(shù)w為與蝴蝶操作相關的相位的余弦。

圖22表示N = 16時的數(shù)據(jù)流動，共進行l(wèi)og2N = 4次迭代，每次進行N/2個蝴蝶操作。在一次迭代中，蝴蝶操作互相獨立，所以可以并行執(zhí)行。一半的蝴蝶操作由核0執(zhí)行，另一半由核1執(zhí)行，每個核會執(zhí)行N/4個蝴蝶操作。加速系數(shù)S = 1.85。

圖22 16-點FFT的信號流動

霍納法則

現(xiàn)在讓我們把話題轉向如何處理x階的多項式。在下面的例子中，多項式為5階，算式為：

圖23

求值需要N-1次乘法計算x的次方，N-1次與系數(shù)ak相乘，以及N次加法運算?；艏{法則給出了更加高效的計算方法。例如，可以通過下圖中第一行的算式迭代計算5階p(x)的值（譯者注：p0為最終結果，第二和第三行通過展開多項式來證明p0和原多項式相等）：

圖24

最后，你會得到p(x)的值，而且只進行了N次乘法和N次加法，也就是說，總共節(jié)省了N-1次乘法?；艏{法則不能并行化，這是因為pk的值互相依賴，但是多項式本身可以被分割為兩部分，如下圖的算式所示：

圖25

現(xiàn)在我們可以同時求多項式q(x)和r(x)的值。要得到p(x)的值，只需要用x3（既x(N+1)/2）乘以q(x)加上r(x)。x(N+1)/2的快速計算非常重要，這可以通過利用連續(xù)乘方的結果1,x,x2,x4,x8,x16…來計算，例如x9= x8*x，計算需要log2N次。log2N相比N很?。ㄌ貏e是N很大時），計算會很快，不會特別影響性能。

N = 100時，在樹莓派Pico上運行非并行版本需要133微秒，霍納法則加上多項式分割的版本，兩個核各自需要71微秒，將兩者快速加和需要7微秒，也就是說并行算法需要78微秒，加速系數(shù)S = 133/78 = 1.7。x(N+1)/2的計算確實會影響效率，但是總體的提速效果依然很明顯。

線性代數(shù)

除了點積，矩陣向量積也可以并行化，加速系數(shù)S = 1.6。線性方程組也可以并行化，S = 1.8。兩個解決方案都使用了簡單的循環(huán)分割方法。

真正的高效率

通過探索本文中的一系列實例，可以看到在雙核的樹莓派Pico上能夠有效地將任務的執(zhí)行過程并行化。實踐中一些例子能達到S = 1.8，非常接近理論上限S = 2。最佳的并行策略需要合適的算法，尋找這樣的算法的過程尤為重要。只有能夠將任務分割，并獨立、分別執(zhí)行的方法，才能從并行處理中獲得最大的效率提升。

關于作者

Martin Ossmann

Martin Ossmann在12歲時就開始閱讀Elektor雜志和動手實驗了。在學習電子工程，并作為工程師工作數(shù)年之后，他成為了德國亞琛應用科學大學電子工程和信息技術系的一名教授。他不僅是若干科學著作的作者，30年來他時常在Elektor雜志上發(fā)表新的電路或是軟件項目，展示他豐富的專業(yè)知識。