王 超 劉 偉 袁培苑

(北京理工大學(xué)信息與電子學(xué)院 北京 100081)

基于細(xì)粒度任務(wù)分配的空時(shí)自適應(yīng)并行處理算法研究

王 超 劉 偉*袁培苑

(北京理工大學(xué)信息與電子學(xué)院 北京 100081)

對于空時(shí)自適應(yīng)信號處理(Space-Time Adaptive Processing, STAP)算法的并行處理問題，傳統(tǒng)方法以粗粒度的劃分方式將 STAP算法分配到特定硬件系統(tǒng)中的不同處理器中，利用處理器間的流水計(jì)算來提高系統(tǒng)計(jì)算吞吐量。該文分析了傳統(tǒng)并行處理方法的缺陷：粗粒度的任務(wù)劃分方式犧牲了 STAP算法的并行度；傳統(tǒng)處理方法僅能適用于特定的系統(tǒng)環(huán)境。針對上述情況，該文提出一種基于細(xì)粒度任務(wù)分配的 STAP并行處理方法，該方法分為以下3個(gè)步驟：構(gòu)建細(xì)粒度的DAG(Direct Acyclic Graph)形式的STAP算法任務(wù)模型；使用統(tǒng)一拓?fù)浣Y(jié)構(gòu)模型描述不同結(jié)構(gòu)的目標(biāo)硬件系統(tǒng)；基于細(xì)粒度任務(wù)分配算法將任務(wù)模型分配到拓?fù)浣Y(jié)構(gòu)模型中的處理器實(shí)現(xiàn)并行計(jì)算。實(shí)驗(yàn)結(jié)果表明該并行處理方法能夠達(dá)到良好的加速比，并且對于不同的STAP應(yīng)用系統(tǒng)具有很好的適應(yīng)性。

信號處理；空時(shí)自適應(yīng)系統(tǒng)；并行處理；任務(wù)分配；細(xì)粒度

1 引言

空時(shí)自適應(yīng)處理(STAP)是新一代相控陣?yán)走_(dá)充分利用空域和時(shí)域信息通過空時(shí)2維濾波來抑制雜波與目標(biāo)檢測的一項(xiàng)關(guān)鍵技術(shù)，廣泛應(yīng)用于機(jī)載預(yù)警雷達(dá)、機(jī)載合成孔徑雷達(dá)、機(jī)載戰(zhàn)場偵察雷達(dá)及星載雷達(dá)、艦載雷達(dá)等實(shí)現(xiàn)雜波抑制與運(yùn)動補(bǔ)償[1]。STAP面對著根據(jù)外界雜波及干擾的環(huán)境實(shí)時(shí)地求解自適應(yīng)權(quán)值向量的問題[2,3]。求解權(quán)值向量是一個(gè)高密集計(jì)算型問題，運(yùn)算量巨大，數(shù)據(jù)交互復(fù)雜，通常采用并行處理技術(shù)提高算法的實(shí)時(shí)性。

傳統(tǒng)的并行處理方法將STAP算法流程劃分為若干粗粒度的計(jì)算任務(wù)，分配計(jì)算任務(wù)到專用的硬件環(huán)境中的處理器，利用處理器間的流水計(jì)算來提高系統(tǒng)計(jì)算吞吐量[4?6]。文獻(xiàn)[7]提出了一種通用的STAP并行計(jì)算模型，并給出了適用于流水計(jì)算的粗粒度任務(wù)分配方法。粗粒度任務(wù)劃分易于實(shí)現(xiàn)，但是犧牲了算法的并行度[8]。國外對于細(xì)粒度STAP并行處理也有一些研究。文獻(xiàn)[9]引入遺傳算法解決STAP并行化處理過程中的細(xì)粒度任務(wù)分配問題，但是該方法僅能適用于具有全交換拓?fù)浣Y(jié)構(gòu)的硬件環(huán)境中。文獻(xiàn)[10]提出了一種細(xì)粒度數(shù)據(jù)劃分方法，并在GPU(Graphics Processing Unit)中實(shí)現(xiàn)了單指令多數(shù)據(jù)流形式的STAP并行處理，但是GPU并不能應(yīng)用于機(jī)載平臺等嵌入式環(huán)境，這就限制了該方法實(shí)際應(yīng)用性。

其次，傳統(tǒng)的處理方法往往只適用于特定的STAP應(yīng)用系統(tǒng)[4?6,9]。特定應(yīng)用系統(tǒng)中限定了系統(tǒng)參數(shù)，包括STAP處理通道數(shù)、脈沖數(shù)及處理距離單元數(shù)等信息；還限定了硬件環(huán)境信息，包括處理器的數(shù)量與處理器間的互聯(lián)方式。當(dāng)系統(tǒng)參數(shù)變化或硬件環(huán)境改變時(shí)，傳統(tǒng)方法往往不再適用，這大大限制了傳統(tǒng)方法的通用性。因此研究一種具有高并行度并且具有拓?fù)浣Y(jié)構(gòu)獨(dú)立性的并行處理方法對于STAP算法的應(yīng)用是非常有意義的。

我們可以分以下3個(gè)步驟實(shí)現(xiàn)STAP的并行處理：(1)劃分STAP算法為細(xì)粒度的計(jì)算任務(wù)，建立細(xì)粒度的任務(wù)模型。相比于粗粒度的方式，細(xì)粒度的劃分后任務(wù)模型具有更高的并行度[10]。(2)建立統(tǒng)一的拓?fù)浣Y(jié)構(gòu)模型，在模型參數(shù)中定義處理器的數(shù)量以及互聯(lián)方式等信息，對于不同的目標(biāo)硬件環(huán)境，配置不同的模型參數(shù)。(3)基于任務(wù)分配方法，完成任務(wù)模型到拓?fù)浣Y(jié)構(gòu)模型的分配。細(xì)粒度劃分后計(jì)算任務(wù)的數(shù)量以及任務(wù)間的計(jì)算約束關(guān)系會變得非常復(fù)雜[10]。直接實(shí)現(xiàn)任務(wù)分配是非常困難的，更好的方法是選取一種合適的任務(wù)分配算法實(shí)現(xiàn)計(jì)算任務(wù)集到多處理器平臺的映射。任務(wù)分配算法以優(yōu)化加速比為目標(biāo)通過計(jì)算任務(wù)間的約束關(guān)系及并行性選擇將可并行的任務(wù)分配到不同的處理器實(shí)現(xiàn)獨(dú)立計(jì)算。

2 基于細(xì)粒度任務(wù)分配的STAP處理方法

2.1 任務(wù)模型

2.2 拓?fù)浣Y(jié)構(gòu)模型

拓?fù)浣Y(jié)構(gòu)模型為目標(biāo)硬件系統(tǒng)的抽象，包含了處理器的信息及處理器間的互聯(lián)信息。定義拓?fù)浣Y(jié)構(gòu)模型TP = {U,CH}。其中U為有限的處理器集合，U中的每個(gè)元素表示一個(gè)獨(dú)立的處理器；CH為有限的通信通道集合，CH中的每個(gè)元素都表示處理器間的通信傳輸通道，傳輸通道分為單向傳輸通道和雙向傳輸通道。對于不同的硬件環(huán)境，需要配置不同的U與CH。

假設(shè)拓?fù)浣Y(jié)構(gòu)模型具有以下兩個(gè)特性：(1)非搶占式：處理器只有在完成當(dāng)前計(jì)算任務(wù)才能開始執(zhí)行新的任務(wù)；(2)并發(fā)性。處理器可以同時(shí)執(zhí)行并發(fā)的計(jì)算任務(wù)和通信傳輸任務(wù)。任務(wù)模型中的節(jié)點(diǎn)V需要被分配到拓?fù)浣Y(jié)構(gòu)模型中不同處理器U。當(dāng)間的數(shù)據(jù)傳輸eij就轉(zhuǎn)變?yōu)樘幚砥鏖g的 IPC(Inter Processor Communication)操作，并需要將該 IPC操作分配到連接uk與ul的傳輸通道中。處理器間傳輸通道的選擇一般采用最短路徑準(zhǔn)則。

2.3 任務(wù)分配算法

任務(wù)分配算法以優(yōu)化加速比為目標(biāo)將任務(wù)模型中的節(jié)點(diǎn)v分配到拓?fù)浣Y(jié)構(gòu)模型的處理器u中，并根據(jù)節(jié)點(diǎn)的分配完成IPC操作到傳輸通道的分配。任務(wù)分配是一個(gè)具有 NP(Non-deterministic Polynomial) 完備性的問題，很難獲得最優(yōu)的分配結(jié)果，因此常見的任務(wù)分配算法一般基于啟發(fā)式算法獲得次優(yōu)結(jié)果[11]。

在現(xiàn)有的分配算法中，大都在分配過程中假定了理想的硬件環(huán)境[11?14]，即不限定處理器數(shù)目及互聯(lián)通道數(shù)目，這并不符合于我們建立的拓?fù)浣Y(jié)構(gòu)模型。DLS(Dynamic Level Scheduling)是唯一具有拓?fù)浣Y(jié)構(gòu)獨(dú)立性的分配算法[15]，即DLS脫離了拓?fù)浣Y(jié)構(gòu)對分配算法的影響。在分配過程中，DLS實(shí)時(shí)計(jì)算分配不同節(jié)點(diǎn)到不同處理器的動態(tài)優(yōu)先級 DL(Dynamic Level)，并依照DL順序完成節(jié)點(diǎn)分配。因此我們選擇DLS完成細(xì)粒度STAP任務(wù)模型的分配。

在每個(gè)分配步驟中，DLS中以∑表示當(dāng)前狀態(tài)的已分配信息，分配節(jié)點(diǎn)vi到處理器uj時(shí)需要完成：(1)根據(jù)pr(vi)的分配信息，完成vi前向IPC操作分配；(2)完成vi到uj的分配?！瓢逊峙涔?jié)點(diǎn)以及IPC的st, end等分配信息。統(tǒng)計(jì)出vi執(zhí)行前所需要完成的傳輸任務(wù)集合，如下：

IPC操作只能夠分配在拓?fù)浣Y(jié)構(gòu)模型中定義的通信通道，并根據(jù)各通信通道的已分配狀態(tài)確定IPC操作的起始執(zhí)行時(shí)間。DA表示所有recv_IPC(vi)的最后結(jié)束時(shí)間，同時(shí)也表示了∑下vi在uj上的數(shù)據(jù)就緒時(shí)間。

由 DA可以計(jì)算出st(vi)，代入式(3)計(jì)算式end(vi)完成vi在pj上的分配。當(dāng)前階段結(jié)束后更新∑?！频牡麓_保每個(gè)分配階段都可以完全獲取各處理器和通信通道的任務(wù)分配信息，并依此完成新任務(wù)的分配。式(6)中TF(uj,∑)表示∑下uj的空閑時(shí)間。

綜上所述，基于細(xì)粒度任務(wù)分配的STAP并行處理方法分為3個(gè)步驟：(1)構(gòu)建任務(wù)模型。根據(jù)系統(tǒng)參數(shù)建立STAP處理流程圖，將其劃分為細(xì)粒度的任務(wù)集并建立任務(wù)DAG圖。DAG中每個(gè)節(jié)點(diǎn)的計(jì)算粒度確定后，其計(jì)算開銷以及邊界的傳輸開銷可以通過實(shí)際測試獲取。(2)構(gòu)建拓?fù)浣Y(jié)構(gòu)模型。拓?fù)淠Ｐ蚑P = {U,CH}參數(shù)中應(yīng)明確定義處理器的個(gè)數(shù)以及處理器間的互聯(lián)關(guān)系。根據(jù)目標(biāo)硬件環(huán)境配置拓?fù)浣Y(jié)構(gòu)模型參數(shù)。(3)任務(wù)分配過程。使用DLS算法實(shí)現(xiàn)任務(wù)模型到拓?fù)浣Y(jié)構(gòu)模型的映射?？捎墒?7)估算分配結(jié)果的加速比。最終輸出并行分配結(jié)果；并行分配結(jié)果中包括：計(jì)算任務(wù)到處理器的映射關(guān)系、IPC任務(wù)到傳輸通道的映射關(guān)系以及計(jì)算任務(wù)和IPC的執(zhí)行順序關(guān)系。

3 并行處理的實(shí)現(xiàn)

基于細(xì)粒度任務(wù)分配的并行處理方法分3步完成，其中任務(wù)分配過程使用較為成熟的DLS分配算法，因此實(shí)現(xiàn)STAP應(yīng)用系統(tǒng)的并行處理時(shí)需要完成細(xì)粒度任務(wù)模型的構(gòu)建以及拓?fù)浣Y(jié)構(gòu)模型的配置。

3.1 細(xì)粒度任務(wù)模型構(gòu)建

全自適應(yīng)STAP算法計(jì)算量過于龐大，工程應(yīng)用一般選擇基于頻域降維的 3DT-SAP算法。本節(jié)以3DT-SAP算法為例簡述細(xì)粒度STAP任務(wù)模型的構(gòu)建方法。設(shè)置脈沖數(shù)為M，陣元數(shù)為N，距離單元數(shù)為L，參照文獻(xiàn)[4,5]中的 STAP處理流程構(gòu)建粗粒度的任務(wù)DAG圖，如圖1(a)所示。圖中的節(jié)點(diǎn)表示計(jì)算任務(wù)，節(jié)點(diǎn)間的連接箭頭表示計(jì)算任務(wù)間的數(shù)據(jù)傳輸。

由數(shù)據(jù)分配節(jié)點(diǎn)將數(shù)據(jù)分發(fā)到N個(gè)多普勒濾波節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)完成L次M點(diǎn)FFT，完成后數(shù)據(jù)由STAP數(shù)據(jù)分配節(jié)點(diǎn)分配到M?2個(gè)數(shù)據(jù)組合節(jié)點(diǎn)中。對于每個(gè)數(shù)據(jù)組合節(jié)點(diǎn)，將N個(gè)處理通道中相鄰的3組脈沖數(shù)據(jù)組合在一起[15]。組合后的數(shù)據(jù)由權(quán)值生成節(jié)點(diǎn)計(jì)算得到自適應(yīng)權(quán)值。權(quán)值生成可以通過如下步驟完成：組合數(shù)據(jù)轉(zhuǎn)置后經(jīng)由QR分解節(jié)點(diǎn)得到3N×3N維的上三角矩陣A；聯(lián)合空時(shí) 2維導(dǎo)向矢量s求解兩次線性方程組計(jì)算得到自適應(yīng)權(quán)值矢量w，如圖1(b)所示。最終由自適應(yīng)權(quán)值聯(lián)合數(shù)據(jù)組合節(jié)點(diǎn)的輸出完成濾波過程，得到 STAP的輸出。

傳統(tǒng)的 STAP并行處理方法通常使用粗粒度QR分解操作，犧牲了算法的并行度，本文將采用一種細(xì)粒度的QR分解方法。計(jì)算權(quán)值的距離門數(shù)Lls應(yīng)滿足自適應(yīng)權(quán)值的收斂條件，取Lls=3 ×3N構(gòu)成9N×3N的數(shù)據(jù)矩陣來求解權(quán)值向量[4]。將輸入Lls×3N階矩陣依照行順序分為K塊(Lls/K)×3N階子矩陣，在實(shí)際應(yīng)用中一般保證3N為Lls/K的整數(shù)倍；將QR分解分割為兩種細(xì)粒度的計(jì)算任務(wù)：消除下三角元素操作以及消除上三角元素操作。

圖1 粗粒度任務(wù)模型DAG

(1)消除下三角操作過程：假設(shè)子矩陣M1的前r列元素全部為0，r+1列元素非 0，使用 Givens旋轉(zhuǎn)法將元素M1ij(i∈[2,Lls/K],j∈[r+ 1,r+i? 1])消除為0。

(2)消除上三角操作過程：選擇全0列數(shù)r相同的兩個(gè)子矩陣M1和M2，矩陣中元素M1ij和M2ij i∈[2,Lls/K],j∈ [r+ 1,r+i? 1])為0；元素M1ij和M2ij(i∈[1,Lls/K],j∈ [r+ 1,r+i])非 0。以M1作為參考矩陣將矩陣M2中的元素M2ij(i∈ [1,Lls/K],j∈ [r+ 1,r+i])消除為0。完成后M1的全0列數(shù)仍為r,M2的全0列數(shù)為r+L/K。

對于第k個(gè)子矩陣Mk，如果k≤3N/(L/K)時(shí)，分解完成的條件為：前(i? 1) × (L/K)列元素全為0，且Mkij(i∈[2,Lls/K],j∈ [r+ 1,r+i? 1])為，元素Mkij(i∈[1,Lls/K],j∈ [r+ 1,r+i])非 0；k＞Lls/K× 3N時(shí)，完成條件為Mk消除為全 0矩陣。

對于所有子矩陣Mk(k∈ [1,K])，持續(xù)進(jìn)行消除下三角操作和消除上三角操作，直到滿足分解完成條件。當(dāng)所有K個(gè)子矩陣都完成分解后，依照行序號重新將子矩陣組合即可得到新的矩陣，其前3N行3N列為上三角矩陣，其余部分為0。將圖1(b)中的QR分解節(jié)點(diǎn)替換為上述分解方法，以此構(gòu)建細(xì)粒度的DAG圖，完成任務(wù)模型建立。

3.2 拓?fù)浣Y(jié)構(gòu)模型的配置

定義 4種測試拓?fù)浣Y(jié)構(gòu)：Ring, Cubic,Rectangular及Cuboid如圖2所示。圖中每個(gè)節(jié)點(diǎn)表示一個(gè)處理器，處理器間的箭頭線表示兩個(gè)處理器間全雙工的通信通道。Ring型拓?fù)浣Y(jié)構(gòu)硬件上由4片TS201 DSP組成，每片DSP與相鄰的2片DSP通過LINK通道雙向互聯(lián)；Cubic型拓?fù)浣Y(jié)構(gòu)硬件上由8片TS201 DSP組成，每片DSP與相鄰的3片DSP通過LINK通道雙向互聯(lián)，Cubic型可以看作是Ring型結(jié)構(gòu)的擴(kuò)展。Rectangular型拓?fù)浣Y(jié)構(gòu)硬件上8片TS201 DSP組成，相鄰的DSP之間通過 LINK通道雙向互聯(lián)；Cuboid型硬件上由兩組Rectangular型拓?fù)浣Y(jié)構(gòu)擴(kuò)展而成。依據(jù)圖2各拓?fù)浣Y(jié)構(gòu)中處理器的個(gè)數(shù)以及處理器間的連接關(guān)系配置拓?fù)浣Y(jié)構(gòu)模型TP = {U,CH}。

3.3 實(shí)驗(yàn)及分析

依照表1配置5組STAP處理參數(shù)，并使用DLS算法實(shí)現(xiàn)并行任務(wù)分配。其中實(shí)驗(yàn)1-實(shí)驗(yàn)4依據(jù)4.1節(jié)中的方法建立細(xì)粒度的DAG任務(wù)圖，實(shí)驗(yàn)5直接使用粗粒度的DAG任務(wù)圖。

圖2 拓?fù)浣Y(jié)構(gòu)示意圖

表1 STAP參數(shù)設(shè)定及p與CCR統(tǒng)計(jì)

通過實(shí)際測試獲取各 DAG圖中各任務(wù)在TS201中的實(shí)際計(jì)算開銷，表2統(tǒng)計(jì)了TS201中各維數(shù)矩陣消除上三角與消除下三角操作的計(jì)算開銷。其中實(shí)驗(yàn)5中QR分解分塊個(gè)數(shù)K=1，因此僅需要一次消除下三角操作即可完成QR分解，故不存在消除上三角操作。根據(jù)式(1)與式(2)統(tǒng)計(jì)得到5個(gè)實(shí)驗(yàn)中 DAG的并行度p及CCR，統(tǒng)計(jì)如表 1所示。

表2 QR分解操作計(jì)算開銷統(tǒng)計(jì)(μs)

由圖 1(a)可以看出，M?2組權(quán)值計(jì)算之間為相對獨(dú)立的過程。在實(shí)驗(yàn)1中M=32，需完成30組權(quán)值計(jì)算與STAP濾波，因此實(shí)驗(yàn)1中的并行度最高達(dá)到了36.82。對比實(shí)驗(yàn)3與實(shí)驗(yàn)5，實(shí)驗(yàn)3中采用細(xì)粒度的任務(wù)劃分方法，并行度達(dá)到了35.27；而實(shí)驗(yàn)5采用粗粒度的方法，并行度僅為14.36?？梢钥闯黾?xì)粒度的任務(wù)劃分雖然增加了傳輸開銷，但是換取了并行度的有效提高。

采用細(xì)粒度任務(wù)模型后，STAP算法中各處理階段被拆分為細(xì)粒度的計(jì)算任務(wù)與通信任務(wù)，并映射到不同的處理器交錯(cuò)執(zhí)行，很難直接評估各處理階段的計(jì)算開銷時(shí)間與通信開銷。因此一般使用加速比ACR來衡量各實(shí)驗(yàn)中STAP的總體并行性能，ACR由式(9)計(jì)算得出。圖3給出了5組實(shí)驗(yàn)中DLS的ACR統(tǒng)計(jì)，其中每組實(shí)驗(yàn)都包含了Ring, Cubic,Rectangular以及Cuboid 4種不同拓?fù)浣Y(jié)構(gòu)下的分配測試。

圖3 ACR統(tǒng)計(jì)

可以看出：(1)在同一組實(shí)驗(yàn)中，隨著拓?fù)浣Y(jié)構(gòu)中處理器節(jié)點(diǎn)個(gè)數(shù)的增加，ACR也逐步增加。(2)對比實(shí)驗(yàn) 1與實(shí)驗(yàn) 3。雖然實(shí)驗(yàn) 1中任務(wù)圖的p= 36.82大于實(shí)驗(yàn)3的p= 35.27，但是實(shí)驗(yàn)1的CCR較大，因此在4種拓?fù)浣Y(jié)構(gòu)下實(shí)驗(yàn)3的ACR都超越了實(shí)驗(yàn)1?？梢钥闯鲈赟TAP算法并行度接近的情況下，較大的通信開銷將會影響并行加速性能。(3)對比實(shí)驗(yàn)3與實(shí)驗(yàn)5，在相同的系統(tǒng)參數(shù)配置下，細(xì)粒度任務(wù)模型具有更高的并行性，更適合于并行實(shí)現(xiàn)，因此達(dá)到了更優(yōu)的ACR。

[7]提出了一種適用于流水處理的通用STAP并行計(jì)算模型，并給出了該計(jì)算模型下粗粒度的計(jì)算任務(wù)分配方法。該方法下的并行加速比統(tǒng)計(jì)見表 3。由于并行加速比與處理器的數(shù)量有直接關(guān)系，因此我們選擇具有相同處理器數(shù)量的拓?fù)浣Y(jié)構(gòu)模型實(shí)驗(yàn)結(jié)果與參考文獻(xiàn)[7]的加速比進(jìn)行比較。其中4片處理器對應(yīng)于本文中Ring型拓?fù)浣Y(jié)構(gòu)下的5組實(shí)驗(yàn)；8片處理器對應(yīng)于本文中 Cubic與Rectangular型拓?fù)浣Y(jié)構(gòu)下的5組實(shí)驗(yàn)。結(jié)果比較如表3所示。

表3 加速比比較

由于細(xì)粒度 STAP算法本身具有很高的并行度，在處理器數(shù)量都為4的條件下，本文中Ring型拓?fù)浣Y(jié)構(gòu)模型的前4組實(shí)驗(yàn)使用了細(xì)粒度的任務(wù)模型，加速比性能要優(yōu)于參考文獻(xiàn)[7]中的加速比3.67；第5組實(shí)驗(yàn)使用了粗粒度的任務(wù)模型，因此加速比與參考文獻(xiàn)[7]基本一致。

在Cubic與Rectangular下的實(shí)驗(yàn)中，實(shí)驗(yàn)1，實(shí)驗(yàn)3和實(shí)驗(yàn)4的加速比優(yōu)于參考文獻(xiàn)[7]中8片處理器的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)2的加速性能基本與其一致。而第5組實(shí)驗(yàn)使用了粗粒度的任務(wù)模型，因此加速比小于參考文獻(xiàn)[7]中的結(jié)果。

聯(lián)合表1可以看出，5組實(shí)驗(yàn)中實(shí)驗(yàn)2與實(shí)驗(yàn)5的任務(wù)模型并行度較低，因此加速比性能較差。而實(shí)驗(yàn)1，實(shí)驗(yàn)3和實(shí)驗(yàn)4的任務(wù)模型并行度較高，因此在與參考文獻(xiàn)[7]的結(jié)果比較中達(dá)到了更優(yōu)的加速性能。這也再次說明，并行度越高的任務(wù)模型越適合于本文提出的STAP并行處理方法。

5組實(shí)驗(yàn)加載了不同的系統(tǒng)參數(shù)，并且每組實(shí)驗(yàn)都使用了4種完全不同的拓?fù)浣Y(jié)構(gòu)。由結(jié)果可以看出：(1)建立細(xì)粒度的任務(wù)模型提高了算法的并行度，DAG形式的任務(wù)模型適應(yīng)于不同系統(tǒng)參數(shù)的STAP應(yīng)用；(2)構(gòu)建TP = {U,CH}形式的拓?fù)浣Y(jié)構(gòu)可以適用于不同目標(biāo)硬件環(huán)境；(3)選擇具有拓?fù)浣Y(jié)構(gòu)獨(dú)立性的DLS分配算法使得整個(gè)STAP并行處理過程脫離了應(yīng)用參數(shù)與系統(tǒng)硬件結(jié)構(gòu)的限制。

4 結(jié)論

在STAP并行處理算法中，傳統(tǒng)的并行處理方法使用粗粒度的任務(wù)劃分方式，并且僅僅能夠適用于特定的應(yīng)用參數(shù)及硬件系統(tǒng)結(jié)構(gòu)。粗粒度的任務(wù)劃分犧牲了STAP流程的并行度；限定應(yīng)用參數(shù)及硬件結(jié)構(gòu)雖然易于實(shí)現(xiàn)，但同時(shí)也限定了傳統(tǒng)的STAP并行處理方法的通用性。針對這些問題，本文提出了一種更具實(shí)用性的STAP并行處理方法，該方案分為以下3個(gè)步驟：建立STAP處理流程并以此構(gòu)建細(xì)粒度的 DAG形式任務(wù)模型；根據(jù)實(shí)際硬件構(gòu)建拓?fù)浣Y(jié)構(gòu)模型；基于DLS任務(wù)分配算法將任務(wù)模型中的任務(wù)分配到拓?fù)浣Y(jié)構(gòu)模型中的不同處理器實(shí)現(xiàn)STAP并行計(jì)算。

由實(shí)驗(yàn)結(jié)果可以看出，該并行方法能夠達(dá)到良好的加速比，并且對于不同的STAP應(yīng)用以及不同的硬件環(huán)境具有很好的適應(yīng)性。

參 考 文 獻(xiàn)

[1] 保錚, 廖桂生, 吳仁彪, 等. 相控陣機(jī)載雷達(dá)雜波抑制的時(shí)空二維自適應(yīng)濾波[J]. 電子學(xué)報(bào), 1993, 21(9): 1-7.

Bao Zheng, Liao Gui-sheng, Wu Ren-biao,et al.. 2-D temporal-tpatial adaptive clutter suppression for phased array airborne radars[J].Acta Electronica Sinica, 1993, 21(9):1-7.

[2] Huang Yao. A reduced-rank STAP method based on solution of linear equations[C]. Proceedings of the 2010 International Conference on Computer Design and Applications (ICCDA),Qinghuangdao, China, 2010: 235-238.

[3] Wu Ren-biao, Wang Lu, and Su Zhi-gang. Study on adaptive monopulse with reduced dimension STAP technique[C].Proceedings of the 2010 International Conference on Image Analysis and Signal Processing (IASP), Xiamen, China, 2010:159-163.

[4] 范西昆, 王永良, 陳輝. 機(jī)載雷達(dá)空時(shí)自適應(yīng)處理的實(shí)時(shí)實(shí)現(xiàn)[J]. 電子與信息學(xué)報(bào), 2006, 28(12): 2224-2227.

Fan Xi-kun, Wang Yong-liang, and Chen Hui. Real-time implementation of airborne radar space-time adaptive processing[J].Journal of Electronics&Information Technology, 2006, 28(12): 2224-2227.

[5] 任磊, 王永良, 陳輝, 等. STAP 并行處理系統(tǒng)的調(diào)度問題研究[J]. 系統(tǒng)工程與電子技術(shù), 2009, 31(4): 874-880.

Ren Lei, Wang Yong-liang, Chen Hui,et al.. Research on the scheduling problems of STAP parallel processing system[J].Systems Engineering and Electronics, 2009, 31(4): 874-880.

[6] Lebak J M and Bojanczyk A W. Design and performance evaluation of a portable parallel library for space-time adaptive processing[J].IEEE Transactions on Parallel and Distributed Systems, 2000, 11(3): 287-298.

[7] 邵銀波, 王永良, 李強(qiáng), 等. 一種用于空時(shí)自適應(yīng)處理的并行計(jì)算模型[J]. 電子學(xué)報(bào), 2006, 34(3): 450-453.Shao Yin-bo, Wang Yong-liang, Li Qiang,et al.. A parallel computation model for space-time adaptive processing[J].Acta Electronica Sinica, 2006, 34(3): 450-453.

[8] West M and Antonio K. A genetic algorithm approach to scheduling communications for a class of parallel space-time adaptive processing algorithms[J].Journal of Parallel and Distributed Computing, 2002, 62(9): 1386-1406.

[9] Roedera M, Davisa N, Furteka J,et al.. GPU implementations for fast factorizations of STAP covariance matrices[C]. Proc. SPIE, San Diego, USA, 2008: 707403-1-707403-12.

[10] Kruatrachue B and Lewis T. Grain size determination for parallel processing[J].IEEE Transactions on Software, 1988,5(1): 23-32.

[11] Wang Chao and Liu Wei. Multi-processor task scheduling in signal processing systems[C]. Proceedings of the International Conference on Computer Science and Information Technology, Chengdu, China, 2011: 532-539.

[12] Ebaid A, Ammar R, and Rajasekaran S. Task clustering &scheduling with duplication using recursive critical path approach (RCPA)[C]. Proceedings of the 2010 IEEE International Symposium on Signal Processing and Information Technology, Luxor, 2010: 34-41.

[13] Hwang R, Gen M, and Katayama H. A comparison of multiprocessors task scheduling algorithms with communication costs[J].Computer&Research, 2008, 35(3):976-993.

[14] Sun Wei-fang, Zhu Yu-dan, Sun Zhi-yuan,et al.. A priority-Based task scheduling algorithm in Grid [C].Proceedings of the Third International Symposium on Parallel Architectures, Algorithms and Programming(PAAP), Dalian, China, 2010: 311-315.

[15] Sih G C and Lee E A. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architecture[J].IEEE Transactions on Parallel and Distributed Systems, 1993, 4(2): 175-186.

Research on the Parallel Processing Algorithm of STAP Based on Fine-grained Task Scheduling

Wang Chao Liu Wei Yuan Pei-yuan
(School of Information and Electronics,Beijing Institute of Technology,Beijing100081,China)

In the parallelization of Space-Time Adaptive Processing (STAP) arithmetic, traditional methods schedule the STAP arithmetic to different processors in the specific hardware architecture through coral-granularity division and improve the throughput by pipeline processing between processors. In the paper, its disadvantages are discussed from two perspectives: Coarse-grained scheduling hinders the parallelism; They are only suitable for the specific system parameters and hardware architectures. Thus, a new method based on fine-grained scheduling is put forward, which consists of three steps: Firstly, fine-grained task model in the form of Direct Acyclic Graph (DAG) is constructed; Secondly, the topology model is built to describe the target system;Finally, the established task model in fine-grained manner is assigned to different processors described in model topology. The experiment of the proposed method shows that it achieves better acceleration ratio, and more flexiable adaptation to different STAP applications.

Signal processing; Space-Time Adaptive Processing (STAP) systems; Parallel processing; Task scheduling; Fine-granularity

TN911.7

A文章編號：1009-5896(2012)06-1398-06

10.3724/SP.J.1146.2011.00683

2011-07-06收到，2012-03-05改回

*通信作者：劉偉 eliuwei@bit.edu.cn

王 超： 男，1985年生，博士生，研究方向?yàn)閷?shí)時(shí)信號處理.

劉 偉： 男，1976年生，講師，研究方向?yàn)閷?shí)時(shí)信號處理.

袁培苑： 女，1988年生，碩士生，研究方向?yàn)閷?shí)時(shí)信號處理.