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

Martin Ossmann博士（德國）

翻譯：何靈淵

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

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

同步和“易變”屬性

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

圖1

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

共享函數(shù)的使用

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

圖2

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

核0和核1一樣運(yùn)行無限循環(huán)。循環(huán)內(nèi)會調(diào)用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ù)的代碼只會在內(nèi)存中儲存一份，兩個核會執(zhí)行同樣的代碼。代碼中只有讀指令，所以只是訪問代碼并不會造成沖突。

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

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

核0可以影響核1的速度

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

圖3

核1運(yùn)行簡單的無限循環(huán)，核0同樣運(yùn)行無限循環(huán)，但是會將GPIO2設(shè)為高電平，等待625個周期，將GPIO2設(shè)為低電平，然后再等待625個周期。當(dāng)核1不運(yùn)行時，以Pico默認(rèn)時鐘頻率125MHz運(yùn)行的核0每秒會運(yùn)行10萬次循環(huán)（125MHz/（2*625周期）），這會在GPIO2上輸出一個100kHz頻率的矩形波。當(dāng)核1開始執(zhí)行時，核0的這一輸出信號頻率會降到75kHz。盡管兩個核之間沒有明顯的關(guān)聯(lián)，它們還是會互相影響。這其中的可能原因是兩個核共用同一個內(nèi)存接口，這一現(xiàn)象通常可以解釋為什么本文中程序的加速系數(shù)S一般都明顯低于2。

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

先入先出（FIFO）通信

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

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

圖4

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

核0上運(yùn)行的代碼如下：

圖5

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

圖6

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

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

圖7所示的是SDR前端的組成，在將輸入信號和本機(jī)振蕩器（LO）信號相乘后，你得到了I頻道（同相）和Q頻道（正交）。兩個頻道幾乎是并行的，非常適合并行計(jì)算。核0處理I頻道的數(shù)據(jù)，核1處理Q頻道的數(shù)據(jù)?；旌虾蟮南嗉右廊挥芍袛嗬烫幚怼５谝粋€并行的部分是巴特沃斯濾波器的實(shí)現(xiàn)，使用單精度浮點(diǎn)數(shù)。在圖8中，你可以看到低通濾波器的時間特征。

圖7 SDR前端的信號流動

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

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

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

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

圖9

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

圖10

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

圖11

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

圖12串行和并行標(biāo)量積計(jì)算

有限脈沖響應(yīng)（FIR）濾波器

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

圖13

圖14 FIR濾波器的信號流動

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

圖15

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

圖16

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

程序開發(fā)

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

帶流水線的無限脈沖響應(yīng)（IIR）濾波器

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

圖17一個雙二階單元

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

圖18

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

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

圖19 CPU中的流水線

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

圖20

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

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

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

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

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

快速傅里葉變換（FFT）

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

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

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

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

圖22 16-點(diǎn)FFT的信號流動

霍納法則

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

圖23

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

圖24

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

圖25

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

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

線性代數(shù)

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

真正的高效率

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

關(guān)于作者

Martin Ossmann

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