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

1 嵌入式多核處理器結構

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

圖1 ARM SMP處理器結構

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

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

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

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

2 OpenMP并行化優化

2.1 0penMP工作原理簡介

OpenMP是一個基于共享內存模式的跨平臺多線程并行的編程接口。主線程生成一系列的子線程，并將任務映射到子線程進行執行，這些子線程并行執行，由運行時環境將線程分配給不同的物理處理器。默認情況下，各個線程獨立執行并行區域的代碼。可以使用work-sharingconstructs來劃分任務，使每個線程執行其分配部分的代碼。通過這種方式，使用OpenMP可以實現任務并行和數據并行。

圖2 任務并行模型

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

數據并行也就是數據級并行，對任務中處理的數據進行分塊并行執行，如圖3所示。C語言中的for循環最適合使用數據并行。

圖3 數據并行模型

2.2 快速排序算法原理

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

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

2.3 任務并行化優化

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

如下所示，對任務并行化優化針對每次掃描調整后的左右子區間，將每個子區間的運算抽象為一個任務，并通過OpenMP中的任務并行化原語#pragma omp task實現任務的并行化執行，從而實現了快速排序的任務并行化優化。

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

2.4 緩存優化

緩存優化（Cache friendly）的目標是減少數據在內存和緩存之間的拷貝。對于220個整型數據而言，數據大小為4 MB,本文的測試平臺（）MAP4430的二級緩存為1 MB,需要將數據劃分為4個部分。

如下所示，算法將4部分數據分為4個快速排序任務，4部分任務并行執行，完成后每部分數據序列排序完成，需要將4部分數據進行合并形成完成數據序列，因此在并行任務結束后，需要對數據進行歸并排序。

3 并行化性能分析

3.1 實驗環境介紹

本文采用德州儀器（Texas Instruments）的OMAP4430嵌入式開發平臺。OMAP443O為嵌入式多核處理器，擁有對稱多處理雙核ARM 處理器（Dual-core ARM Cortex-A、一級緩存32 KB、二級緩存1 MB,嵌入式操作系統采用Ubuntul2.O4內核，編譯器為arm-linux-gnueabihf-gcc，使用GNU gprof獲取算法執行時間。

3.2 性能測試

如下式所示，采用計算加速比的方式來分析并行優化的性能，加速比數值越大表示算法的并行程度越高，最低為1.性能測試采用4個算法版本，包括串行版本、并行2線程、并行4線程和緩存優化版，從不同角度來分析性能。

如圖4所示，從折線圖可以看出，3種并行化優化算法相對于串行版本，算法的并行性能都有較大提升，如表1所列，其并行加速比分別為1.30、1.29和1.21.對任務并行優化方案而言，分別使用2線程和4線程版本進行測試，從加速比的分析結果看來，2線程版本較4線程版本略好。理論上并行線程的數目越多性能越好，但本文采用OMAP443O只有兩個對稱多處理核心，即使算法擁有4個并行線程，但實際執行的線程只有2個，同時4個線程在獲取2個物理處理器時存在競爭關系，因而造成性能較之2線程版本有所下降。

圖4 算法執行時間

評價并行算法優劣還需考慮算法的負載均衡性，如表1、表2所列，緩存優化方案標準差遠遠小于任務并行化方案。究其原因，對于任務并行化方案而言，不同的測試數據以及劃分算法（partition）對區間的劃分有重要影響，從而造成任務執行時間變化范圍很大；對于緩存優化方案而言，其實質是數據并行，其每一個任務都是根據緩存大小進行劃分，因此每一個任務處理的數據規模基本一致，每一個任務執行的時間更確定，但由于并行任務執行完成后，需要對數據進行歸并，造成一定的性能下降。

結語

本文通過對嵌入式多核處理器硬件結構的分析，從對稱多處理角度對串行快速排序算法進行并行化優化，取得了很好的效果。

以ARM 雙核處理器（OMAP4430）作為測試平臺，從任務并行和緩存優化實現并行優化，從性能測試的結果看，任務并行具有良好的加速比，但負載均衡性差，并行線程數目不應超過物理處理器核的數目，過多的并行線程競爭處理器資源，造成性能下降。緩存優化具有良好的負載均衡性，但需要后續進行歸并操作，造成性能有所下降。

總之，在嵌入式多核處理器上進行并行化優化，一方面要充分發掘嵌人式多核處理器的并行性能，提高程序的并行性；另一方面也要考慮程序算法的負載均衡性，確保在不同應用環境中程序性能一致。