嵌入式ARM多核處理器并行化方法
目前,嵌入式多核處理器已經(jīng)在嵌入式設(shè)備領(lǐng)域得到廣泛運用,但嵌人式系統(tǒng)軟件開發(fā)技術(shù)還停留在傳統(tǒng)單核模式,并沒有充分發(fā)揮多核處理器的性能。程序并行化優(yōu)化目前在PC平臺上有一定運用,但在嵌入式平臺上還很少,另外,嵌入式多核處理器與PC平臺多核處理器有很大不同,因此不能直接將PC平臺的并行化優(yōu)化方法應(yīng)用到嵌人式平臺。本文分別從任務(wù)并行和緩存優(yōu)化兩方面進行并行化優(yōu)化的研究,探索在嵌人式多核處理器上對程序進行并行化優(yōu)化的方法。
本文引用地址:http://m.butianyuan.cn/article/201609/303909.htm1嵌入式多核處理器結(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)域使用,常見的是通用嵌入式處理器+DSP核。本文探究的嵌入式多核處理器采用同構(gòu)結(jié)構(gòu),實現(xiàn)同一段代碼在不同處理器上的并行執(zhí)行。
圖1 ARM SMP處理器結(jié)構(gòu)
在目前嵌入式領(lǐng)域中,使用最為廣泛的為ARM處理器,因此以ARM雙核處理器OMAP4430作為研究對象。ARM對稱多處理(Symmetric Multi-Processing,SMP)結(jié)構(gòu)如圖1所示,根據(jù)程序的局部性原理,每一個處理器都具有私有的內(nèi)存(Local Memory),常見的是一級緩存(L1Cache)。然而,多個處理器之間又涉及到相互通信問題,因此在常見的ARM處理器中使用二級緩存(L2 Cache)來解決這一問題?;趯ΨQ多處理器結(jié)構(gòu),所有的處理器(通常為2的倍數(shù))在硬件結(jié)構(gòu)上都是相同的,在使用系統(tǒng)資源上也是平等的。更重要的是,由于所有的處理器都有權(quán)利去訪問相同的內(nèi)存空間,在共享內(nèi)存區(qū)域中,任何一個進程或者線程都可以運行在任意一個處理器之上,這樣就使得程序的并行化成為可能。2在嵌入式多核平臺上進行并行化優(yōu)化,需要考慮以下問題:
①并行化程序的性能取決于程序中串行化部分,程序性能不會隨著并行線程數(shù)目的提升而不斷提升;
②嵌入式多核處理器相對于PC處理器而言,其總線速度較慢,并且緩存(Cache)更小,會造成大量數(shù)據(jù)在內(nèi)存(Memory)和緩存(Cache)問不斷拷貝,因此在進行并行化優(yōu)化的過程中,應(yīng)考慮緩存友好性(Cache friendly);
③程序并行化執(zhí)行線程數(shù)目應(yīng)當(dāng)小于或等于物理處理器的數(shù)目,線程過多會造成線程間搶占處理器資源,致使并行化性能下降。
2 OpenMP并行化優(yōu)化
2.1 0penMP工作原理簡介
OpenMP是一個基于共享內(nèi)存模式的跨平臺多線程并行的編程接口。主線程生成一系列的子線程,并將任務(wù)映射到子線程進行執(zhí)行,這些子線程并行執(zhí)行,由運行時環(huán)境將線程分配給不同的物理處理器。默認情況下,各個線程獨立執(zhí)行并行區(qū)域的代碼??梢允褂脀ork-sharingconstructs來劃分任務(wù),使每個線程執(zhí)行其分配部分的代碼。通過這種方式,使用OpenMP可以實現(xiàn)任務(wù)并行和數(shù)據(jù)并行。
圖2任務(wù)并行模型
任務(wù)并行模式創(chuàng)建一系列獨立的線程,每一個線程運行一個任務(wù),線程之間相互獨立,如圖2所示。OpenMP使用編譯原語session directive和task directive來實現(xiàn)任務(wù)分配,每個線程可以獨立運行不同的代碼區(qū)域,同時支持任務(wù)的嵌套和遞歸。一旦創(chuàng)建任務(wù),該任務(wù)就可能會在線程池(其大小等于物理線程數(shù)目)中空閑的線程上執(zhí)行。
數(shù)據(jù)并行也就是數(shù)據(jù)級并行,對任務(wù)中處理的數(shù)據(jù)進行分塊并行執(zhí)行,如圖3所示。C語言中的for循環(huán)最適合使用數(shù)據(jù)并行。
圖3數(shù)據(jù)并行模型
2.2快速排序算法原理
快速排序算法是一種遞歸分治算法,算法中最為關(guān)鍵的就是確定哨兵元素(pivot data)。數(shù)據(jù)序列中小于哨兵的數(shù)據(jù)將會放在哨兵元素的左側(cè),序列中大于哨兵的數(shù)據(jù)將會被放在哨兵元素的右側(cè)。當(dāng)完成數(shù)據(jù)掃描后,哨兵元素分成的左右兩個部分就會調(diào)用快速排序算法遞歸進行。
快速排序算法中涉及算法的遞歸調(diào)用,會產(chǎn)生大量任務(wù),并且這些任務(wù)相互獨立,非常適合OpenMP的任務(wù)并行模式;另外,就一次快速排序搜索算法而言,哨兵元素對于左右子區(qū)間數(shù)據(jù)容量大小具有決定性作用,考慮到嵌入式平臺的緩存(Cache)空間較小,需要對哨兵元素篩選算法進行優(yōu)化,盡量使得劃分出來的左右子區(qū)間更均衡,滿足負載均衡的要求。
2.3任務(wù)并行化優(yōu)化
通過對快速排序算法的分析,快速排序是一個遞歸調(diào)用算法,算法的執(zhí)行過程中會產(chǎn)生大量重復(fù)函數(shù)調(diào)用,并且函數(shù)的執(zhí)行相互獨立。對于快速排序的一次掃描運算而言,算法首先確定哨兵元素(pivot),并對數(shù)據(jù)序列進行一次調(diào)整,然后對哨兵元素的左右區(qū)間再次進行遞歸調(diào)用算法。
如下所示,對任務(wù)并行化優(yōu)化針對每次掃描調(diào)整后的左右子區(qū)間,將每個子區(qū)間的運算抽象為一個任務(wù),并通過OpenMP中的任務(wù)并行化原語#pragma omp task實現(xiàn)任務(wù)的并行化執(zhí)行,從而實現(xiàn)了快速排序的任務(wù)并行化優(yōu)化。
任務(wù)空間中的數(shù)據(jù)大小取決于哨兵元素,因此,算法選取的劃分算法(Partition Algorithm)應(yīng)盡量將數(shù)據(jù)序列的劃分均衡化,本文使用簡單劃分算法和三元中值法(Median-of-Three Method)進行測試。
2.4緩存優(yōu)化
緩存優(yōu)化(Cache friendly)的目標是減少數(shù)據(jù)在內(nèi)存和緩存之間的拷貝。對于220個整型數(shù)據(jù)而言,數(shù)據(jù)大小為4 MB,本文的測試平臺()MAP4430的二級緩存為1 MB,需要將數(shù)據(jù)劃分為4個部分。
如下所示,算法將4部分數(shù)據(jù)分為4個快速排序任務(wù),4部分任務(wù)并行執(zhí)行,完成后每部分數(shù)據(jù)序列排序完成,需要將4部分數(shù)據(jù)進行合并形成完成數(shù)據(jù)序列,因此在并行任務(wù)結(jié)束后,需要對數(shù)據(jù)進行歸并排序。
評論