解析嵌入式ARM多核處理器并行化方法

目前，嵌入式多核處理器已經(jīng)在嵌入式設備領(lǐng)域得到廣泛運用，但嵌人式系統軟件開(kāi)發(fā)技術(shù)還停留在傳統單核模式，并沒(méi)有充分發(fā)揮多核處理器的性能。程序并行化優(yōu)化目前在PC平臺上有一定運用，但在嵌入式平臺上還很少，另外，嵌入式多核處理器與PC平臺多核處理器有很大不同，因此不能直接將PC平臺的并行化優(yōu)化方法應用到嵌人式平臺。本文分別從任務(wù)并行和緩存優(yōu)化兩方面進(jìn)行并行化優(yōu)化的研究，探索在嵌人式多核處理器上對程序進(jìn)行并行化優(yōu)化的方法。

1 嵌入式多核處理器結構

嵌人式多核處理器的結構包括同構(Symmetric)和異構(Asymmetric)兩種。同構是指內部核的結構是相同的，這種結構目前廣泛應用在 PC多核處理器;而異構是指內部核的結構是不同的，這種結構常常在嵌入式領(lǐng)域使用，常見(jiàn)的是通用嵌入式處理器+DSP核。本文探究的嵌入式多核處理器采用同構結構，實(shí)現同一段代碼在不同處理器上的并行執行。

圖1 ARM SMP處理器結構

在目前嵌入式領(lǐng)域中，使用最為廣泛的為ARM 處理器，因此以ARM 雙核處理器OMAP4430作為研究對象。ARM 對稱(chēng)多處理(Symmetric Multi-Processing，SMP)結構如圖1所示，根據程序的局部性原理，每一個(gè)處理器都具有私有的內存(Local Memory)，常見(jiàn)的是一級緩存(L1Cache)。然而，多個(gè)處理器之間又涉及到相互通信問(wèn)題，因此在常見(jiàn)的ARM 處理器中使用二級緩存(L2 Cache)來(lái)解決這一問(wèn)題?；趯ΨQ(chēng)多處理器結構，所有的處理器(通常為2的倍數)在硬件結構上都是相同的，在使用系統資源上也是平等的。更重要的是，由于所有的處理器都有權利去訪(fǎng)問(wèn)相同的內存空間，在共享內存區域中，任何一個(gè)進(jìn)程或者線(xiàn)程都可以運行在任意一個(gè)處理器之上，這樣就使得程序的并行化成為可能。2在嵌入式多核平臺上進(jìn)行并行化優(yōu)化，需要考慮以下問(wèn)題：

① 并行化程序的性能取決于程序中串行化部分，程序性能不會(huì )隨著(zhù)并行線(xiàn)程數目的提升而不斷提升;

② 嵌入式多核處理器相對于PC處理器而言，其總線(xiàn)速度較慢，并且緩存(Cache)更小，會(huì )造成大量數據在內存(Memory)和緩存(Cache)問(wèn)不斷拷貝，因此在進(jìn)行并行化優(yōu)化的過(guò)程中，應考慮緩存友好性(Cache friendly);

③ 程序并行化執行線(xiàn)程數目應當小于或等于物理處理器的數目，線(xiàn)程過(guò)多會(huì )造成線(xiàn)程間搶占處理器資源，致使并行化性能下降。

2 OpenMP并行化優(yōu)化

2.1 0penMP工作原理簡(jiǎn)介

OpenMP是一個(gè)基于共享內存模式的跨平臺多線(xiàn)程并行的編程接口。主線(xiàn)程生成一系列的子線(xiàn)程，并將任務(wù)映射到子線(xiàn)程進(jìn)行執行，這些子線(xiàn)程并行執行，由運行時(shí)環(huán)境將線(xiàn)程分配給不同的物理處理器。默認情況下，各個(gè)線(xiàn)程獨立執行并行區域的代碼?？梢允褂脀ork-sharingconstructs來(lái)劃分任務(wù)，使每個(gè)線(xiàn)程執行其分配部分的代碼。通過(guò)這種方式，使用OpenMP可以實(shí)現任務(wù)并行和數據并行。

圖2 任務(wù)并行模型

任務(wù)并行模式創(chuàng )建一系列獨立的線(xiàn)程，每一個(gè)線(xiàn)程運行一個(gè)任務(wù)，線(xiàn)程之間相互獨立，如圖2所示。OpenMP使用編譯原語(yǔ)session directive和task directive來(lái)實(shí)現任務(wù)分配，每個(gè)線(xiàn)程可以獨立運行不同的代碼區域，同時(shí)支持任務(wù)的嵌套和遞歸。一旦創(chuàng )建任務(wù)，該任務(wù)就可能會(huì )在線(xiàn)程池(其大小等于物理線(xiàn)程數目)中空閑的線(xiàn)程上執行。

數據并行也就是數據級并行，對任務(wù)中處理的數據進(jìn)行分塊并行執行，如圖3所示。C語(yǔ)言中的for循環(huán)最適合使用數據并行。

圖3 數據并行模型

2.2 快速排序算法原理

快速排序算法是一種遞歸分治算法，算法中最為關(guān)鍵的就是確定哨兵元素(pivot data)。數據序列中小于哨兵的數據將會(huì )放在哨兵元素的左側，序列中大于哨兵的數據將會(huì )被放在哨兵元素的右側。當完成數據掃描后，哨兵元素分成的左右兩個(gè)部分就會(huì )調用快速排序算法遞歸進(jìn)行。

快速排序算法中涉及算法的遞歸調用，會(huì )產(chǎn)生大量任務(wù)，并且這些任務(wù)相互獨立，非常適合 OpenMP的任務(wù)并行模式;另外，就一次快速排序搜索算法而言，哨兵元素對于左右子區間數據容量大小具有決定性作用，考慮到嵌入式平臺的緩存(Cache)空間較小，需要對哨兵元素篩選算法進(jìn)行優(yōu)化，盡量使得劃分出來(lái)的左右子區間更均衡，滿(mǎn)足負載均衡的要求。

2.3 任務(wù)并行化優(yōu)化

通過(guò)對快速排序算法的分析，快速排序是一個(gè)遞歸調用算法，算法的執行過(guò)程中會(huì )產(chǎn)生大量重復函數調用，并且函數的執行相互獨立。對于快速排序的一次掃描運算而言，算法首先確定哨兵元素(pivot)，并對數據序列進(jìn)行一次調整，然后對哨兵元素的左右區間再次進(jìn)行遞歸調用算法。

如下所示，對任務(wù)并行化優(yōu)化針對每次掃描調整后的左右子區間，將每個(gè)子區間的運算抽象為一個(gè)任務(wù)，并通過(guò)OpenMP中的任務(wù)并行化原語(yǔ)#pragma omp task實(shí)現任務(wù)的并行化執行，從而實(shí)現了快速排序的任務(wù)并行化優(yōu)化。

任務(wù)空間中的數據大小取決于哨兵元素，因此，算法選取的劃分算法(Partition Algorithm)應盡量將數據序列的劃分均衡化，本文使用簡(jiǎn)單劃分算法和三元中值法(Median-of-Three Method)進(jìn)行測試。