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

1 嵌入式多核處理器結(jié)構(gòu)

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

圖1 ARM SMP處理器結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

2.2 快速排序算法原理

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

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

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

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

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

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

2.4 緩存優(yōu)化

緩存優(yōu)化（Cache friendly）的目標(biāo)是減少數(shù)據(jù)在內(nèi)存和緩存之間的拷貝。對(duì)于220個(gè)整型數(shù)據(jù)而言，數(shù)據(jù)大小為4 MB,本文的測(cè)試平臺(tái)（）MAP4430的二級(jí)緩存為1 MB,需要將數(shù)據(jù)劃分為4個(gè)部分。

如下所示，算法將4部分?jǐn)?shù)據(jù)分為4個(gè)快速排序任務(wù)，4部分任務(wù)并行執(zhí)行，完成后每部分?jǐn)?shù)據(jù)序列排序完成，需要將4部分?jǐn)?shù)據(jù)進(jìn)行合并形成完成數(shù)據(jù)序列，因此在并行任務(wù)結(jié)束后，需要對(duì)數(shù)據(jù)進(jìn)行歸并排序。

3 并行化性能分析

3.1 實(shí)驗(yàn)環(huán)境介紹

本文采用德州儀器（Texas Instruments）的OMAP4430嵌入式開(kāi)發(fā)平臺(tái)。OMAP443O為嵌入式多核處理器，擁有對(duì)稱(chēng)多處理雙核ARM 處理器（Dual-core ARM Cortex-A、一級(jí)緩存32 KB、二級(jí)緩存1 MB,嵌入式操作系統(tǒng)采用Ubuntul2.O4內(nèi)核，編譯器為arm-linux-gnueabihf-gcc，使用GNU gprof獲取算法執(zhí)行時(shí)間。

3.2 性能測(cè)試

如下式所示，采用計(jì)算加速比的方式來(lái)分析并行優(yōu)化的性能，加速比數(shù)值越大表示算法的并行程度越高，最低為1.性能測(cè)試采用4個(gè)算法版本，包括串行版本、并行2線(xiàn)程、并行4線(xiàn)程和緩存優(yōu)化版，從不同角度來(lái)分析性能。

如圖4所示，從折線(xiàn)圖可以看出，3種并行化優(yōu)化算法相對(duì)于串行版本，算法的并行性能都有較大提升，如表1所列，其并行加速比分別為1.30、1.29和1.21.對(duì)任務(wù)并行優(yōu)化方案而言，分別使用2線(xiàn)程和4線(xiàn)程版本進(jìn)行測(cè)試，從加速比的分析結(jié)果看來(lái)，2線(xiàn)程版本較4線(xiàn)程版本略好。理論上并行線(xiàn)程的數(shù)目越多性能越好，但本文采用OMAP443O只有兩個(gè)對(duì)稱(chēng)多處理核心，即使算法擁有4個(gè)并行線(xiàn)程，但實(shí)際執(zhí)行的線(xiàn)程只有2個(gè)，同時(shí)4個(gè)線(xiàn)程在獲取2個(gè)物理處理器時(shí)存在競(jìng)爭(zhēng)關(guān)系，因而造成性能較之2線(xiàn)程版本有所下降。

圖4 算法執(zhí)行時(shí)間

評(píng)價(jià)并行算法優(yōu)劣還需考慮算法的負(fù)載均衡性，如表1、表2所列，緩存優(yōu)化方案標(biāo)準(zhǔn)差遠(yuǎn)遠(yuǎn)小于任務(wù)并行化方案。究其原因，對(duì)于任務(wù)并行化方案而言，不同的測(cè)試數(shù)據(jù)以及劃分算法（partition）對(duì)區(qū)間的劃分有重要影響，從而造成任務(wù)執(zhí)行時(shí)間變化范圍很大；對(duì)于緩存優(yōu)化方案而言，其實(shí)質(zhì)是數(shù)據(jù)并行，其每一個(gè)任務(wù)都是根據(jù)緩存大小進(jìn)行劃分，因此每一個(gè)任務(wù)處理的數(shù)據(jù)規(guī)?；疽恢?，每一個(gè)任務(wù)執(zhí)行的時(shí)間更確定，但由于并行任務(wù)執(zhí)行完成后，需要對(duì)數(shù)據(jù)進(jìn)行歸并，造成一定的性能下降。

結(jié)語(yǔ)

本文通過(guò)對(duì)嵌入式多核處理器硬件結(jié)構(gòu)的分析，從對(duì)稱(chēng)多處理角度對(duì)串行快速排序算法進(jìn)行并行化優(yōu)化，取得了很好的效果。

以ARM 雙核處理器（OMAP4430）作為測(cè)試平臺(tái)，從任務(wù)并行和緩存優(yōu)化實(shí)現(xiàn)并行優(yōu)化，從性能測(cè)試的結(jié)果看，任務(wù)并行具有良好的加速比，但負(fù)載均衡性差，并行線(xiàn)程數(shù)目不應(yīng)超過(guò)物理處理器核的數(shù)目，過(guò)多的并行線(xiàn)程競(jìng)爭(zhēng)處理器資源，造成性能下降。緩存優(yōu)化具有良好的負(fù)載均衡性，但需要后續(xù)進(jìn)行歸并操作，造成性能有所下降。

總之，在嵌入式多核處理器上進(jìn)行并行化優(yōu)化，一方面要充分發(fā)掘嵌人式多核處理器的并行性能，提高程序的并行性；另一方面也要考慮程序算法的負(fù)載均衡性，確保在不同應(yīng)用環(huán)境中程序性能一致。