嵌入式ARM多核處理器并行化方法分析_第1頁
嵌入式ARM多核處理器并行化方法分析_第2頁
嵌入式ARM多核處理器并行化方法分析_第3頁
嵌入式ARM多核處理器并行化方法分析_第4頁
嵌入式ARM多核處理器并行化方法分析_第5頁
已閱讀5頁,還剩2頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

【W(wǎng)ord版本下載可任意編輯】嵌入式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)化的方法。

1嵌入式多核處理器構(gòu)造

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

圖1SMP處理器構(gòu)造

在目前嵌入式領(lǐng)域中,使用為廣泛的為ARM處理器,因此以ARM雙核處理器OMAP4430作為研究對象。ARM對稱多處理(SymmetricMulti—Processing,SMP)構(gòu)造如圖1所示,根據(jù)程序的局部性原理,每一個處理器都具有私有的內(nèi)存(alMemory),常見的是緩存(L1Cache)。然而,多個處理器之間又涉及到相互通信問題,因此在常見的ARM處理器中使用二級緩存(L2Cache)來解決這一問題?;趯ΨQ多處理器構(gòu)造,所有的處理器(通常為2的倍數(shù))在硬件構(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)考慮緩存友好性(Cachefriendly);

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

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

2.10penMP工作原理簡介

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使用編譯原語sessiondirective和taskdirective來實現(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)鍵的就是確定哨兵元素(pivotdata)。數(shù)據(jù)序列中小于哨兵的數(shù)據(jù)將會放在哨兵元素的左側(cè),序列中大于哨兵的數(shù)據(jù)將會被放在哨兵元素的右側(cè)。當完成數(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)生大量重復函數(shù)調(diào)用,并且函數(shù)的執(zhí)行相互獨立。對于快速排序的掃描運算而言,算法首先確定哨兵元素(pivot),并對數(shù)據(jù)序列開展調(diào)整,然后對哨兵元素的左右區(qū)間再次開展遞歸調(diào)用算法。

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

任務(wù)空間中的數(shù)據(jù)大小取決于哨兵元素,因此,算法選取的劃分算法(PartitionAlgorithm)應(yīng)盡量將數(shù)據(jù)序列的劃分均衡化,本文使用簡單劃分算法和三元中值法(Median-of-ThreeMethod)開展測試。

2.4緩存優(yōu)化

緩存優(yōu)化(Cachefriendly)的目標是減少數(shù)據(jù)在內(nèi)存和緩存之間的拷貝。對于220個整型數(shù)據(jù)而言,數(shù)據(jù)大小為4MB,本文的測試平臺()MAP4430的二級緩存為1MB,需要將數(shù)據(jù)劃分為4個部分。

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

3并行化性能分析

3.1實驗環(huán)境介紹

本文采用***儀器(TexasInstruments)的OMAP4430嵌入式開發(fā)平臺。OMAP443O為嵌入式多核處理器,擁有對稱多處理雙核ARM處理器(Dual—coreARMCortex—A、緩存32KB、二級緩存1MB,嵌入式操作系統(tǒng)采用Ubuntul2.O4內(nèi)核,編譯器為arm—linux—gnueabihf—g,使用GNUgprof獲取算法執(zhí)行時間。

3.2性能測試

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

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

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

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

結(jié)語

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

以ARM雙核處理器(OMAP4430)作為測試平臺,從任務(wù)并行和緩存優(yōu)化實現(xiàn)并行優(yōu)化,從性能測試的結(jié)果看,任務(wù)并行具

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論