2.4 緩存優(yōu)化

緩存優(yōu)化(Cache friendly)的目標(biāo)是減少數(shù)據(jù)在內(nèi)存和緩存之間的拷貝。對于220個(gè)整型數(shù)據(jù)而言，數(shù)據(jù)大小為4 MB，本文的測試平臺(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é)束后，需要對數(shù)據(jù)進(jìn)行歸并排序。

3 并行化性能分析

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

本文采用德州儀器(Texas Instruments)的OMAP4430嵌入式開發(fā)平臺(tái)。OMAP443O為嵌入式多核處理器，擁有對稱多處理雙核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 性能測試

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

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

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

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

結(jié)語

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

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

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