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

Martin Ossmann博士（德國）

翻譯：何靈淵

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

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

同步和“易變”屬性

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

圖1

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

共享函數(shù)的使用

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

圖2

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

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

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

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

核0可以影響核1的速度

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

圖3

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

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

先入先出（FIFO）通信

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

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

圖4

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

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

圖5

運(yùn)行時(shí)測量的數(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ì)算時(shí)間大約560納秒，通信時(shí)間620納秒，通信的開銷比例大于100%。因此，如果不想要通信開銷影響整體性能，服務(wù)器需要大幅提高計(jì)算能力。在并行計(jì)算環(huán)境中編程時(shí)，最好不要過于關(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頻道（正交）。兩個(gè)頻道幾乎是并行的，非常適合并行計(jì)算。核0處理I頻道的數(shù)據(jù)，核1處理Q頻道的數(shù)據(jù)?；旌虾蟮南嗉右廊挥芍袛嗬烫幚?。第一個(gè)并行的部分是巴特沃斯濾波器的實(shí)現(xiàn)，使用單精度浮點(diǎn)數(shù)。在圖8中，你可以看到低通濾波器的時(shí)間特征。

圖7 SDR前端的信號流動(dòng)

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

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

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

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

圖9

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

圖10

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

圖11

最終結(jié)果通過兩個(gè)部分相加得到。核0和核1同時(shí)使用skpLoop中的加和循環(huán)。因?yàn)檠h(huán)由兩個(gè)核分別使用，矩陣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個(gè)信號的值進(jìn)行加和，期間會(huì)將樣本和脈波響應(yīng)系數(shù)ak相乘，公式如下圖所示：

圖13

圖14 FIR濾波器的信號流動(dòng)

計(jì)算中需要將最后N個(gè)輸入值xk存儲(chǔ)起來，這可以通過一個(gè)環(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)性。一般可以首先在一個(gè)更為靈活的環(huán)境中編寫一個(gè)版本的程序作為參考版本，像是一個(gè)開源、免費(fèi)的處理環(huán)境，然后在那里進(jìn)行調(diào)試。在這一過程中，你可以生成用于并行的測試數(shù)據(jù)。這一版本的軟件成型后可以移植到目標(biāo)系統(tǒng)上，并用同樣的測試數(shù)據(jù)進(jìn)行測試。調(diào)試時(shí)你可以比較兩個(gè)版本的軟件行為。

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

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

圖17一個(gè)雙二階單元

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

圖18

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

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

圖19 CPU中的流水線

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

圖20

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

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

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

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

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

快速傅里葉變換（FFT）

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

圖21蝴蝶操作中的信號流動(dòng)

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

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

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

霍納法則

現(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

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

圖25

現(xiàn)在我們可以同時(shí)求多項(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很?。ㄌ貏e是N很大時(shí)），計(jì)算會(huì)很快，不會(huì)特別影響性能。

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

線性代數(shù)

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

真正的高效率

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

關(guān)于作者

Martin Ossmann

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