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

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

　　1 嵌入式多核處理器結構

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

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

　　圖1 ARM SMP處理器結構

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

　?、?并行化程序的性能取決于程序中串行化部分，程序性能不會隨著并行線程數(shù)目的提升而不斷提升；

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

　?、?程序并行化執(zhí)行線程數(shù)目應當小于或等于物理處理器的數(shù)目，線程過多會造成線程間搶占處理器資源，致使并行化性能下降。

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

　　2.1 0penMP工作原理簡介

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

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

　　圖2 任務并行模型

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

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

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

　　圖3 數(shù)據(jù)并行模型

　　2.2 快速排序算法原理

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

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

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

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

　　如下所示，對任務并行化優(yōu)化針對每次掃描調(diào)整后的左右子區(qū)間，將每個子區(qū)間的運算抽象為一個任務，并通過OpenMP中的任務并行化原語#pragma omp task實現(xiàn)任務的并行化執(zhí)行，從而實現(xiàn)了快速排序的任務并行化優(yōu)化。

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