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

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