星載SAR成像處理系統(tǒng)中多線程矩陣轉(zhuǎn)置的設(shè)計和實現(xiàn)

田 蕾 范士明

(航天恒星科技有限公司,北京 100086)

1 引言

矩陣轉(zhuǎn)置被廣泛地應(yīng)用于圖像處理、信號處理和統(tǒng)計學(xué)等領(lǐng)域,在合成孔徑雷達(SAR)的成像處理系統(tǒng)中也有非常重要的應(yīng)用。在進行SAR 的成像處理時,數(shù)據(jù)一般是以矩陣形式排列的,可以定義距離向采樣為行方向,方位向采樣為列方向。成像處理是對矩陣中的按行或按列的數(shù)據(jù)進行多次一維或二維的聯(lián)合處理。在要求快速成像處理時,通常都是將二維聯(lián)合處理轉(zhuǎn)化為一維處理的算法,即在進行完行(列)處理后,還需要針對列(行)進行處理。在行、列處理的轉(zhuǎn)換中,需要頻繁多次進行矩陣轉(zhuǎn)置操作。矩陣轉(zhuǎn)置算法的時效性決定了整個成像系統(tǒng)處理速度是否能夠滿足應(yīng)用需求。因此,有必要對矩陣轉(zhuǎn)置算法進行分析和研究。

隨著計算機技術(shù)的不斷發(fā)展,多核處理器已經(jīng)成為各種處理平臺的基本配置。由于本論文的研究環(huán)境是共享內(nèi)存的并行機,研究的矩陣轉(zhuǎn)置算法必須能夠適用于這種系統(tǒng)。現(xiàn)有的矩陣轉(zhuǎn)置算法一般都是串行的,無法充分利用多核處理器。多線程是基于這種硬件系統(tǒng)的并行處理技術(shù),因此,有必要對多線程的矩陣轉(zhuǎn)置算法進行研究。

本文主要對多線程技術(shù)在星載SAR 地面成像處理系統(tǒng)中的應(yīng)用進行研究。第2部分介紹SAR的成像處理系統(tǒng);第3部分研究和分析矩陣轉(zhuǎn)置方法;第4部分研究和分析多線程矩陣轉(zhuǎn)置的并行處理方法;第5部分研究和分析多線程矩陣轉(zhuǎn)置的實驗結(jié)果及結(jié)論。

2 SAR 的地面成像處理系統(tǒng)

圖1 星載SAR 的地面成像處理系統(tǒng)Fig.1 Image processing system of spaceborne SAR

星載SAR 的地面成像處理系統(tǒng)主要完成原始回波數(shù)據(jù)的分塊自適應(yīng)量化(BAQ)解壓縮和聚焦成像處理并進行輻射校正。生成的數(shù)據(jù)可以通過公共平臺提供產(chǎn)品生成模塊,生產(chǎn)指定格式的1級產(chǎn)品,或通過幾何校正等進一步的處理,實現(xiàn)更高級別的產(chǎn)品生產(chǎn)。本論文主要對條帶模式SAR 的成像處理進行研究和討論,因此,假設(shè)此地面成像處理系統(tǒng)主要處理條帶模式SAR 的原始回波數(shù)據(jù)。此星載SAR 的地面處理系統(tǒng)的處理流程如圖1所示。

如圖1所示,成像處理可以根據(jù)需要在一定范圍內(nèi)選擇適合的成像算法,為進一步說明矩陣轉(zhuǎn)置的作用,詳細分析距離-多普勒(Range Doppler,RD)和CS(Chirp Scaling)成像算法的處理流程,如圖2、3所示。

圖2 RD算法的處理流程Fig.2 Processing procedures of RD algorithm

圖3 CS算法的處理流程Fig.3 Processing procedures of CS algorithm

3 矩陣轉(zhuǎn)置

從以上兩種算法的處理流程可以看出,矩陣轉(zhuǎn)置是SAR成像處理中必不可少的一個處理步驟。如果沒有專門的轉(zhuǎn)置存儲設(shè)備的成像處理系統(tǒng),可以用兩種方式進行存儲:一種是處理器內(nèi)部的存儲器足夠大,可以將所有需要的數(shù)據(jù)全部讀入內(nèi)部存儲器中進行轉(zhuǎn)置;另一種是處理器內(nèi)部的存儲器不夠大,不能將所有待處理的數(shù)據(jù)一次全部讀入,一般通過內(nèi)存和外存共同完成轉(zhuǎn)置處理。隨著存儲器價格的不斷降低,現(xiàn)階段的內(nèi)存大小一般能夠滿足一次把所有需要的數(shù)據(jù)全部讀入的條件,因此,本文只對內(nèi)存的矩陣轉(zhuǎn)置算法進行研究和分析[1-2]。

3.1 方陣轉(zhuǎn)置

本論文的開發(fā)環(huán)境是Linux 和C++,矩陣數(shù)據(jù)被存儲在動態(tài)分配的內(nèi)存里,按照行或列的順序存儲在動態(tài)數(shù)組里,矩陣轉(zhuǎn)置也是在數(shù)組內(nèi)完成的。方陣轉(zhuǎn)置相對于矩陣轉(zhuǎn)置更容易被實現(xiàn),為了使問題簡化,先分析方陣轉(zhuǎn)置的處理方法。令方陣A=(aij)(n+1)×(n+1),i,j =0,…,n,i =j,n =2N-1,N ≥0 且N ∈Z,轉(zhuǎn)置后AT=(aji)(n+1)×(n+1),假設(shè)A按行存儲成一維動態(tài)數(shù)組,則轉(zhuǎn)置后的AT按列存儲成一維動態(tài)數(shù)組,buff 1是存儲A和AT的內(nèi)存空間,buff 2是存儲中間結(jié)果的內(nèi)存空間。下面介紹兩種主要的方陣轉(zhuǎn)置方法:直接法和遞歸法。

3.1.1 直接法

根據(jù)方陣存儲鏈表的特點,直接轉(zhuǎn)置只需要把每對aij 和a ji 直接互換就可以實現(xiàn)。這種方法原理比較簡單,易于實現(xiàn),只在原來的內(nèi)存上就可以進行處理,但處理較大矩陣的效率不是很高,速度較慢。具體的處理過程如圖4所示。

圖4 方陣轉(zhuǎn)置直接法的處理過程Fig.4 Process of square matrix transposition direct method

3.1.2 遞歸法

對于較大的方陣可以用直接算法進行轉(zhuǎn)置,但效率并不是很高,速度有待提高,提出遞歸法進行轉(zhuǎn)置。遞歸法的原理相對要復(fù)雜一些,對遞歸的劃分和返回要特別注意。具體的實現(xiàn)過程如以下三步所示。

第二步,多次四等分后得到小方陣,對這些小方陣用直接法實現(xiàn)各個小方陣的轉(zhuǎn)置;

第三步,遞歸的返回過程,依次完成各次遞歸劃分后逆對角線上小方陣的互換,直到第一次遞歸劃分得到4個小方陣,把逆對角線上的小方陣互換,實現(xiàn)整個大方陣的轉(zhuǎn)置。

具體的遞歸法的處理過程如圖5所示。

可以看到,以上兩種方陣轉(zhuǎn)置方法不用額外申請大塊連續(xù)的內(nèi)存,整個轉(zhuǎn)置的實現(xiàn)都是在原來的內(nèi)存上完成的,有效地節(jié)省了內(nèi)存空間。

圖5 方陣轉(zhuǎn)置遞歸法的處理過程Fig.5 Process of square matrix transposition recursive method

3.2 矩陣轉(zhuǎn)置

令A(yù)=(aij)(n+1)×(m+1),i =0,…,n,j =0,…,m,n =2N-1,m =2M-1,N ≥0 且N ∈Z,M ≥0 且M ∈Z,轉(zhuǎn)置后AT=(aji)(m+1)×(n+1),假設(shè)A按行存儲成鏈表,則轉(zhuǎn)置后的AT按列存儲成鏈表。由于矩陣不具有方陣行列相等的特點,不能用方陣轉(zhuǎn)置的直接法和遞歸法實現(xiàn)轉(zhuǎn)置,需要另外申請一大塊連續(xù)的內(nèi)存空間存放中間結(jié)果,具體的實現(xiàn)過程如以下三步所示。

第二步,把buff 2 中對應(yīng)的小方陣分別在各自的存儲區(qū)內(nèi)進行轉(zhuǎn)置,當t ≤2α?xí)r,用方陣直接轉(zhuǎn)置法,當t ＞2α?xí)r,用方陣遞歸轉(zhuǎn)置法;

第三步,把已轉(zhuǎn)置的小方陣從buff 2 對應(yīng)的存儲區(qū)中取出,存放到buff 1 對應(yīng)的存儲區(qū)中,完成整個大矩陣的轉(zhuǎn)置。

具體矩陣轉(zhuǎn)置的處理過程如圖6所示。

4 多線程的矩陣轉(zhuǎn)置

所謂多線程就是將應(yīng)用程序劃分成一個或多個同時運行的任務(wù)。在這種共享內(nèi)存的系統(tǒng)上進行并行處理的關(guān)鍵是對多處理器共享內(nèi)存的訪問控制,其基本實現(xiàn)模式有共享全部數(shù)據(jù)結(jié)構(gòu)(Shared Everything)與共享局部數(shù)據(jù)結(jié)構(gòu)(Shared S omething)兩種。兩種都允許處理器通過存/取共享內(nèi)存來進行通信,其主要區(qū)別在于共享全部數(shù)據(jù)結(jié)構(gòu)將所有的數(shù)據(jù)結(jié)構(gòu)都放在內(nèi)存,而共享局部數(shù)據(jù)結(jié)構(gòu)需要用戶顯式地指定出哪些數(shù)據(jù)結(jié)構(gòu)是潛在共享的,哪些是僅有某處理器私有的。由于本論文是對一幀原始回波數(shù)據(jù)的成像處理中矩陣轉(zhuǎn)置的多線程處理方法進行研究,所以重點關(guān)注共享全部數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)模式[3-4]。

4.1 共享全部數(shù)據(jù)結(jié)構(gòu)

這種模式的好處在于用戶可以很容易地利用一個已經(jīng)編寫好的串行程序,并將其轉(zhuǎn)化為一個共享內(nèi)存的并行程序,因為用戶不需要事先區(qū)分哪些數(shù)據(jù)是需要被其他處理器訪問的。但是,這種模式存在任何單個處理器對內(nèi)存的訪問都有可能影響到其他處理器的處理結(jié)果的問題。因此,對內(nèi)存的訪問要特別關(guān)注同步和互斥的問題[5-8]。

Linux系統(tǒng)對共享全局數(shù)據(jù)結(jié)構(gòu)是通過線程機制實現(xiàn)的,即提供線程庫支持并行處理?？梢浦膊僮飨到y(tǒng)接口線程庫(POSIX th read,Pthread)是一套通用的線程庫,它廣泛地被各種Unix所支持,是由可移動操作系統(tǒng)接口(Portable Operating System Interface,POSIX)提出的,具有良好的可移植性。使用Linux Pthread 的基本步驟如下:

第一步,以單進程的方式開始程序的執(zhí)行;

第二步,初始化所需的各個鎖;第三步,調(diào)用pthread_create 函數(shù)創(chuàng)建新線程;第四步,并行執(zhí)行線程代碼,正確加鎖和解鎖,以保證處理器對內(nèi)存訪問的正確性。

圖6 矩陣轉(zhuǎn)置的處理過程Fig.6 Process of matrix t ransposition

4.2 多線程矩陣轉(zhuǎn)置的并行處理方法

第一步,線程1 和線程2分別把buff 1 中的大矩陣劃分成若干個小方陣,A=(Aij)(q+1)×(p+1) =

根據(jù)一幀原始回波數(shù)據(jù)的特點,創(chuàng)建的線程數(shù)Nthread=2N,N ≥0 且N ∈Z ,為了簡化分析的過程,令N =1 ,則Nthread=2。具體的實現(xiàn)過程如下三步所示。其中i =0,…,q,j =0,…,p,(q+1)*t =(n+1),(p+1)*t =(m+1),t(令t =2α,α≥0 且α∈Z)為小方陣的大小,線程1 和線程2分別把劃分的小方陣從buff 1 對應(yīng)的存儲區(qū)中取出,存放到buff 2 對應(yīng)的存儲區(qū)中;

第二步,線程1 和線程2分別把buff 2 中對應(yīng)的小方陣分別在各自的存儲區(qū)內(nèi)進行轉(zhuǎn)置,當t ≤2α?xí)r,用方陣直接轉(zhuǎn)置法,當t ＞2α?xí)r,用方陣遞歸轉(zhuǎn)置法;

第三步,線程1 和線程2分別把已轉(zhuǎn)置的小方陣從buff 2 對應(yīng)的存儲區(qū)中取出,存放到buff 1 對應(yīng)的存儲區(qū)中,完成整個大矩陣的轉(zhuǎn)置。

具體多線程轉(zhuǎn)置的并行處理過程如圖7所示。

以上是為了對問題的模型進行簡化,對兩個線程矩陣轉(zhuǎn)置的并行處理方法進行的研究和分析,實際處理時可以根據(jù)需要創(chuàng)建線程數(shù),但根據(jù)一幀原始回波數(shù)據(jù)的特點,必須滿足Nthread=2N,N ≥0 且N ∈Z。

5 實驗和結(jié)論

5.1 在HP 服務(wù)器上的實驗結(jié)果

實驗所用的平臺為HP Proliant DL580,是一臺通用服務(wù)器。

本文所研究的多線程矩陣轉(zhuǎn)置在HP 上的運算結(jié)果如表1所示。由于這臺服務(wù)器具有四路四核的結(jié)構(gòu),因此采用1、2、4、8、16 和32個線程分別進 行并行處理并觀察實驗結(jié)果。

圖7 多線程矩陣轉(zhuǎn)置的處理過程Fig.7 Processing process of multi-thread matrix transposition

表1 多線程矩陣轉(zhuǎn)置的實驗結(jié)果Table1 Result of multi-thread matrix transposition

如上表所示,隨著處理線程個數(shù)從1 遞增到4,并行處理時間相應(yīng)的減少,隨著處理線程個數(shù)從4增加到32,并行處理時間反而小幅增加。

5.2 結(jié)論及分析

上面的實驗結(jié)果說明,隨著線程個數(shù)逐漸增大到4,多線程矩陣轉(zhuǎn)置的并行處理所用的時間逐漸減少到最小值,但再增加線程個數(shù),并行處理時間反而增加。這是由于本系統(tǒng)是4個處理器,每個處理器都是4 核的,當線程為4個、8個和16個時,所用的時間相差不大,8個和16個線程的處理時間有小幅增加,都比較充分地利用了處理器的資源。由于線程的建立、銷毀和同步也要占用處理器資源,運行8個和16個線程利用處理器資源而節(jié)省的時間被這些線程的其他額外開銷抵消了。但當線程數(shù)增加到32個時,由于超過了所有處理器的總核數(shù),并行處理時間繼續(xù)增加。

多線程矩陣轉(zhuǎn)置的并行處理方法能有效地利用多處理器和多核的硬件資源,比傳統(tǒng)的單線程和單進程的串行矩陣轉(zhuǎn)置的效率更高,轉(zhuǎn)置的正確性不會由于線程個數(shù)增加而發(fā)生變化,具有良好的并行擴展性,有利于進行快速的矩陣轉(zhuǎn)置。隨著通用計算機平臺性能的不斷提升,這種方法一定會在不久的將來具有更好的應(yīng)用前景。

References)

[1]張冠杰,張濤,張歡陽,等.實時SAR成像中的高速矩陣轉(zhuǎn)置算法及實現(xiàn)[C]//2005年中國合成孔徑雷達會議:359-364

[2]謝應(yīng)科,張濤,韓承德.實時SAR成像系統(tǒng)中矩陣轉(zhuǎn)置的設(shè)計和實現(xiàn)[J].計算機研究與發(fā)展,2003(1):6-11

[3]賈韶旭,潘錦.多線程技術(shù)在探底雷達中的應(yīng)用[C]//2007年全國微波毫米波會議:1953-1956

[4]李建軍,陳鴻星,張紅新.Linux 線程庫的實現(xiàn)機制[J].計算機與現(xiàn)代化,2005(4):96-98,113

[5]師林.Linux 內(nèi)核同步技術(shù)的基本原理及應(yīng)用原則[J].計算機科學(xué),2006(9):165-167

[6]孫東,方建勛,李廉登.實時應(yīng)用中POSIX 信號燈技術(shù)研究[C]//中國計算機用戶協(xié)會信息系統(tǒng)分會2005年信息交流大會:247-248,253

[7]黃道穎,張安琳.Linux系統(tǒng)對SMP 并行處理的支持[J].鄭州輕工業(yè)學(xué)院學(xué)報(自然科學(xué)版),2001(4):26-30

[8]龍卉,皮亦鳴.合成孔徑雷達并行成像算法研究及實現(xiàn)[D].成都:電子科技大學(xué),2001