?

成像制導中的多處理器并行及二值化算法研究*

盧軍1，怯新現(xiàn)2，張?zhí)旆?，李哲1

(1.湖北工程學院 新技術學院，湖北 孝感432000；

2.湖北航天技術研究院 計量測試技術研究所，湖北 孝感432000)

摘要：導彈成像制導涉及大量圖像處理和計算，一般系統(tǒng)實現(xiàn)多以高性能單或多處理器為核心。討論了一種嵌入式多處理器系統(tǒng)的基本結構，利用平臺特有的FSMC總線同時支持靜態(tài)分割和任務級調(diào)度2種并行算法，并以此進行圖像二值化算法的并行化研究。試驗結果分析表明，該設計能夠支持2種并行化算法，成倍減少圖像處理的時間。

關鍵詞：嵌入式系統(tǒng)；多處理器系統(tǒng)；FSMC總線；二值化算法；并行算法

0引言

導彈成像制導中空間導航、目標定位均涉及大量圖像處理和計算，一般系統(tǒng)實現(xiàn)多以高性能CPU，F(xiàn)PGA或DSP等單核處理器或微控制器作為處理核心，例如文獻[1]利用DSP實現(xiàn)成像制導；文獻[2]圖像在精確制導中的應用；文獻[3]電視制導武器系統(tǒng)圖像跟蹤；文獻[4]反坦克導彈電視制導圖像處理系統(tǒng)等中均涉及大量的數(shù)字圖像處理任務。因此，提高大規(guī)模數(shù)字圖像處理能力成為武器裝備性能提升的一個重要方面。

當前絕大部分高性、超級能計算機系統(tǒng)以Intel，IBM為代表的多核處理器為基礎構建[5]，而在四代到五代計算機體系的發(fā)展中，嵌入式多核、多處理器系統(tǒng)因其高性能、高可靠性、低功耗[6-8]等特點在空間圖像處理、空間計算等領域日益受到關注。

提出一種基于ARM的嵌入式多處理器系統(tǒng)的基本結構，利用平臺特有的FSMC總線實現(xiàn)了一種同時支持任務靜態(tài)分割和任務級并行處理的結構，嘗試從SMP方向進行研究。

1基于嵌入式多處理器系統(tǒng)

1.1系統(tǒng)結構

當前典型的多處理器結構主要以FPGA，DSP，ARM多種組合方式的AMP(異構系統(tǒng))結構為主，如：文獻[9]高性能異構多處理器平臺，由FPGA和SPI流處理器組成；文獻[10]提出了一種多處理器異構系統(tǒng)可以增加系統(tǒng)的冗余能力；文獻[11]用FPGA實現(xiàn)互聯(lián)的多DSP并行系統(tǒng)結構，如圖1所示。文獻[12-13]也以FPGA和DSP組合多處理器系統(tǒng)。

圖1　FPGA與DSP并行處理異構系統(tǒng)結構框圖Fig.1　FPGA and DSP parallel processing heterogeneous　　　system architecture diagram

AMP的好處是可以利用不同處理單元的特性分別針對特定任務進行處理以加強系統(tǒng)的處理能力，但設計復雜、編程難度較大、通用性較低。因此嘗試設計一種基于ARM的SMP多處理器系統(tǒng)彌補這些缺陷并加以驗證。設計上使用五片芯片構成一個分布式存儲MIMD結構單元，其中主處理器(主機)選用STM32F107，從處理器(從機)選用STM32F103RG，為每個處理器配備64Mbit的SRAM；主從機通過SPI總線連接，并通過平臺特有的FSMC總線與存儲器連接。驗證流程主要分為設計輸入、綜合、功能仿真、實現(xiàn)、配置下載、下載后板級調(diào)試檢錯這幾個步驟[14-15]。系統(tǒng)結構簡圖如圖2所示。

圖2　基于FSMC總線的多處理器系統(tǒng)結構簡圖Fig.2　FSMC bus based multi-processor　　　system architecture diagram

該結構可以使用SMP也可以使用NUMA結構，非常規(guī)的AHB總線連接模式，可以通過高速以太網(wǎng)將多個系統(tǒng)構成群集[16]，具有以下特點：

(1) 主機負責與外部進行數(shù)據(jù)/任務交互，在內(nèi)部負責任務調(diào)度并處理部分任務，大多任務交給從機具體處理；

(2) 主機和從機擁有各自獨立訪問存儲空間，但只允許主機訪問從機存儲空間以分派任務數(shù)據(jù)；而它們之間的調(diào)度主要通過硬件方式的信號量機制實現(xiàn)，因此無需傳統(tǒng)處理過程的兩次數(shù)據(jù)傳輸，可以節(jié)省大量通信開銷；

(3) 主機和從機構成異步結構，從機之間則具有高度的并行性，可以實現(xiàn)任務級并行。

1.2二級流水線處理機制

圖2所示結構中主機和從機采用特殊的FSMC總線結構連接，可以同時支持任務級別并行(算法11)和靜態(tài)負載平衡(算法22)并行調(diào)度，通過對從機的調(diào)度可實現(xiàn)從機在兩個時間周期內(nèi)交替?zhèn)魉?分派)并處理任務，形成二級流水線處理過程，提高程序的并行性，從而較大幅度提系統(tǒng)的運行性能，如圖3所示。

現(xiàn)結構主要使用外部存儲器，如能利用處理器自有緩存則可以進一步優(yōu)化調(diào)度流程。

1.3多工作模式切換

系統(tǒng)支持多種工作模式的切換以滿足不同任務環(huán)境和算法的需求，是因為考慮到導彈制導的實際工作環(huán)境和可靠性要求。例如，在導彈飛行的初期和中期，可將絕大部分處理器資源用于姿態(tài)控制與導航，而在末端進行目標識別和制導時將調(diào)度更多處理器參與圖像處理工作，如圖4所示；如果某個處理器出現(xiàn)故障，可以將其負擔的任務遷移到其它處理器，從而提高系統(tǒng)冗余度，提高系統(tǒng)的可靠性。

圖3　系統(tǒng)的二級流水線處理過程示意圖Fig.3　Two-stage pipelining processing system diagram

圖4　導彈飛行中的處理器資源分布示意圖Fig.4　Processor resource distribution diagram　　　 of a missile in flight

2圖像二值化算法

成像制導中最基本的圖像處理是圖像二值化操作，因此以算法的并行化過程對系統(tǒng)基本性能進行測試。二值化算法是通過設定某個閾值，把具有灰度級的圖像變換成只有2個灰度級的黑白圖像。假設輸入圖像為的矩陣F[0,…,M-1,0,…,N-1]，輸出圖像為M×N的矩陣G[0,…,M-1,0,…,N-1]，假設閾值為T，那么圖像二值化的算法為

(1)

3并行算法設計

任務模型：假設有R幅大小為M×N的圖像待處理，系統(tǒng)中有n個處理器可以處理任務；系統(tǒng)中消息傳遞時間固定為TSR且與任務規(guī)模無關，單位字節(jié)傳輸時間為TW，如果一次傳送E字節(jié)，則一次消息傳遞所需的總時間為T=TSR+TWE。

3.1靜態(tài)任務分割算法

3.2任務級并行處理算法

主機主進程(){在從機上創(chuàng)建子進程管理對象;判定各從機空閑狀態(tài);將一個任務寫入空閑從機,并通知該從機處理;接收從機任務完成信號并進行計時統(tǒng)計處理;若所有任務完成且沒有新任務,則終止所有進程,否則循環(huán)執(zhí)行本過程}從機子進程(){檢查主機任務(中斷)信號;有任務則從對應存儲空間取任務并進行計算;完成任務,向主機發(fā)送完成(中斷)信號}

圖5　任務級并行處理算法流程簡圖Fig.5　Task-level parallel processing algorithm diagram

4算法分析

前面簡單分析了2種算法的效能，這里再進行詳細分析：

(1) 計算步

通過算法可知，對每個處理機來說，平均要執(zhí)行NM/n個賦值運算步。

(2) 通信步

算法1：主處理機要把F矩陣發(fā)送給n個處理機，還要接收返回的計算結果，所以通信步為2n。

算法2：由于FSMC共享存儲器的特性，待處理數(shù)據(jù)由主機調(diào)度直接由圖像設備寫入相應處理器存儲空間，而結果無需回送主機并可直接轉交給控制設備，因此通訊步為2。

(3) 計算復雜度和通信復雜度

從計算步的分析可知，兩種算法的計算時間復雜度均為O(NM/n)，算法1空間復雜度為O(NM/n)，算法2空間復雜度為O(NM)，關于通信復雜度：

算法1：根據(jù)靜態(tài)任務分配策略，可以求出總的通訊量為

(2)

所以算法1的通信復雜度為O(NM).

算法2：只需將F矩陣發(fā)送給從機而無需回傳結果，因此通訊數(shù)據(jù)量為NM，通信步為2，因此總通信量為

Ctlp(n)=2+NM.

(3)

任務調(diào)度所需通訊次數(shù)不隨任務規(guī)模的增加而變化，算法2的通信復雜度為O(NM).

(4) 并行度

并行度計算僅考慮計算開始到完成之間的時間，因此理想的并行度為n。

(5) 加速比和效率

根據(jù)漸進加速比的計算公式

(4)

若有n臺處理機可用，設一個賦值步的計算時間為，并且不考慮通信開銷時，

(5)

(6)

所以，該算法理論上加速比可達到n(N)，效率可達1。

(6) 系統(tǒng)加速比和系統(tǒng)整體效率

根據(jù)前文分析，系統(tǒng)在理想狀況下的加速比和系統(tǒng)效率為：

對于算法1：

(7)

(8)

由于算法2不對任務進行分割，因此以R個任務的并行性進行分析算出其理想加速比和效率：

(9)

(10)

(11)

(12)

5系統(tǒng)測試

根據(jù)以上算法，在實驗平臺中選擇規(guī)模為160×120，320×240，640×480 3種尺寸的任務分別進行了實際的測試，其結果如表1，2所示。

將2種算法所需的計算時間除以100得到的數(shù)值和效率值在一個范圍內(nèi)，便于進行比較，如圖6所示。

從以上實驗數(shù)據(jù)中，可以得到以下結論：

表1　靜態(tài)分割算法測試表

表2　任務級并行算法測試表

圖6　靜態(tài)負載和任務級并行處理在不同任務　　　規(guī)模下效率折線圖Fig.6　Efficiency line chart of static load and　　　　task-level parallel processingunder　　　　different scales of the task

(1) 由于任務粒度的關系，算法1的整體效率低于算法2；同期算法1所需的計算時間增長幅度也明顯高于算法2，計算時間的增長導致了效率曲線在規(guī)模增加后逐步收斂；

(2) 算法1需要的通信步較多，其總執(zhí)行時間約為算法2的2倍。但系統(tǒng)計時精度為毫秒級，低于毫秒無法有效計算，因此在任務規(guī)模較小時誤差較大，因此以上測試的初始效率約為63%；

(3) 隨著處理機數(shù)的增加，2種算法的加速比和效率都得到了增長，但算法2的增長幅度較快。特別是算法1的執(zhí)行效率沒有明顯提升，這是因為貌似均衡的分割算法導致了各個任務之間分配的不均衡，分割算法產(chǎn)生了通訊，也就影響了其整體效率的提升；

(4) 表1，2中規(guī)模為640×480的圖像處理時間均低于40 ms，滿足連續(xù)圖像的實時處理要求。但實際應用中還可能需要進行如均衡化、降噪等處理，這將延長處理時間，降低實時性處理能力。以中值濾波為例，系統(tǒng)采用基于冒泡法排序的串行化算法約需4 259 ms，而快速排序的FSMF算法[17]可以將時間復雜度降低到O(NlnN)；NSMF可以將3×3模板的比較次數(shù)降低到30次；基于統(tǒng)計思想的SMF算法和FMF算法需要21次比較；文獻[18]僅需要18次比較，這都可以較大幅度的提高系統(tǒng)的吞吐量。分別采用以上算法后優(yōu)化，對于規(guī)模為640×480的圖像處理結果如表3所示。

表3　中值濾波算法的多種優(yōu)化并行處理結果對比

從表3中可以看到不同任務所需的時間差異是巨大的，圖像二值化串行時間需要72 ms，而基于冒泡法排序的中值濾波任務則需4 259 ms，根本達不到圖像的實時化處理要求，但是也應看到通過并行算法以及處理機數(shù)量就可以成本減少處理時間，與此同時如果能夠對具體任務本身所需的基本算法進行改進，可以更大幅度的減少處理時間，如基于快速計算的中值濾波在并行度為4時需606 ms完成任務，相比基礎的冒泡法已經(jīng)提升了7倍的性能。

6結束語

針對成像制導中圖像處理系統(tǒng)構建的具有FSMC特殊總線的SMP多處理器并行處理系統(tǒng)，由主機進行任務調(diào)度和快速切換，支持靜態(tài)任務分割和任務級并行處理，大大提高了系統(tǒng)的處理能力。研究并實現(xiàn)了圖像處理中基礎的二值化并行處理算法以及中值濾波算法的性能度量。雖然系統(tǒng)的單項任務處理能力能夠滿足需求，但對于實際中復雜多任務任務處理的能力還不足，這與目前選用的STM32本身的處理能力有關，后續(xù)研究中可以使用性能更好的如Cortex-A7/A8架構的系統(tǒng)提升基礎運算能力并重點關注復雜任務的并行化處理過程。

參考文獻：

[1]尹哲春,張福欣,馬紅艷.基于DSP的成像制導仿真圖像生成技術研究[J].電子設計工程,2010,18(6)：87-88,92.

YIN Zhe-chun, ZHANG Fu-xin, MA Hong-yan. Imaging Guidance Simulation and Image Generation Technology Based on DSP [J]. Electrical Design Engineering, 2010,18 (6) ：87-88,92.

[2]祝明波,陳麒,張東興.圖像在精確制導中的應用綜述[J].飛彈導航,2013(11)：70-74,84.

ZHU Ming-bo,CHEN Qi, ZHANG Dong-xing. Overview of Image Applications in Precision-Guided [J]. Missile-Guidance, 2013(11):70-74,84.

[3]鮑學良,范惠林,劉成亮.電視制導武器系統(tǒng)圖像跟蹤方法研究[J].吉林大學學報,2012,30(4)：355-360.

BAO Xue-liang, FAN Hui-lin, LIU Cheng-liang,et al. Image Tracking Method for TV Guidance Weapon System[J]. Journal of Jilin University, 2012,30 (4):355-360.

[4]劉光燦,白廷柱, 黃飛江.反坦克導彈電視制導圖像處理系統(tǒng)設計[J].激光與紅外,2011,41(1)：79-83.

LIU Guang-can, BAI Ting-zhu, HUANG Fei-jiang. TV-Guided Anti-Tank Missile Designed Image Processing System [J]. Laser and Infrared, 2011,41 (1)：79-83.

[5]MCNAIRY C, Bhatia R Montecito.A Dual-Core,Dual-Thread Itanium Processor[C]∥ IEEE Micro, 2005, 25(2)：10-20.

[6]Lee Trong-Yen,Fan Yang-Hsin,Cheng Yu-Minetal. Hardware Oriented Partition for Embedded Multiprocessor FPGA System[C]∥Proceedings of the 2the International Conference on Innovative Computing, Information and Control (ICICIC 2007),Kumamoto, Japan,2007.

[7]TOLEDO F,MARTINEZ J, FERRANDEZ J. FPGA-Based Platform for Image and Video Processing Embedded Systems[C]∥Proceedings of the 2007 3rd Southern Conference on Programmable Logic(SPL’07),2007:171-176.

[8]LI Yong,WANG Zhi-ying,ZHAO Xue-mi,et al. Designg of a Low-Power Embedded Processor Architecture Using Asynchronous Function Units[C]∥Lecture Notes In Computer Science,2008:354-363.

[9]全巍,文梅,伍楠,等.高性能異構多處理器平臺及其應用[J].計算機工程與科學,2011, 33(1)：60-65.

QUAN Wei,WEN Mei,WU Nan, et al. High Performance Heterogeneous Multi-Processor Platforms and Applications [J].Computer Engineering and Science, 2011, 33 (1): 60-65.

[10]劉品陽.一種多處理器異構系統(tǒng)設計與實現(xiàn)[J].計算機技術與發(fā)展,2011,21(5):179-182.

LIU Pin-yang. A Multi Processor Design and Implementation of Heterogeneous Systems [J].Computer Technology and Development, 2011, 21 (5) : 179-182.

[11]顏露新,張?zhí)煨?鄒勝,等.用FPGA實現(xiàn)互聯(lián)的多DSP并行系統(tǒng)結構[J].系統(tǒng)工程與電子技術,2005,27(10)：1757-1775.

YAN Lu-xin,ZHANG Tian-xu, ZOU Sheng, et al. Realized by FPGA Interconnects System of Multi-DSP Parallel Structure [J]. Systems Engineering and Electronics, 2005, 27 (10)：1757-1775.

[12]王潔,張淑燕,劉濤,等.基于FPGA的嵌入式多核處理器及SUSAN算法并行化[J].計算機學報，2008，31(11)：1995-2004.

WANG Jie, ZHANG Shu-yan, LIU Tao, et al. Embedded Multi-Core Processor Based on FPGA and Parallelization of SUSAN Algorithm [J]. Computer Journal, 2008, 31 (11): 1995-2004.

[13]呂雷,王明昌,秦金明.基于FPGA的多DSP紅外實時圖像處理系統(tǒng)[J].現(xiàn)代電子技術, 2010(22)：97-99.

Lü Lei, WANG Ming-chang, QIN Jin-ming. Based on Multi-DSP FPGA Real-Time Infrared Image Processing System [J]. Modern Electronic Technology, 2010(22)：97-99.

[14]YAN Li-ke, SHI Qing-song, CHEN Tian-zhou，et al. An on-Chip Communication Mechanism Design in the Embedded Heterogeneous Multi-Core Architecture[C]∥Proceedings of the 2008 IEEE International Conference on Networking ,Sensing and Control(ICNSC)，2008:1842-1845.

[15]Vermeulen Bart. Functional Debug Techniques for Embedded System[J].IEEE Design and test of computers, 2008,25(33):208-215.

[16]張?zhí)旆? 基于Cortex嵌入式架構的智能儲物管理系統(tǒng)[D].武漢：武漢大學，2012：10-12,33,56-60.

ZHANG Tian-fan. Embedded Intelligent Storage Management System Architecture Based on Cortex [D].Wuhan: Wuhan University,2012:10-12,33,56-60.

[17]Rafael C Gonzalez，Richard E Woods. Digital Image Processing [M].New Jersey: Prentice Hall，2010:178-179.

[18]董付國，原達，王金鵬.中值濾波快速算法的進一步思考[J].計算機工程與應用，2007，43(26)：48-49.

DONG Fu-guo, YUAN Da, WANG Jin-peng. Further Consideration of Fast Median Filtering Algorithm [J].Computer Engineering and Applications, 2007,43 (26): 48-49.

Multiprocessor in Missile Guidance Systems and Research of Binarization Algorithms of Parallel Algorithms

LU Jun1, KAI Xin-xian2,ZHANG Tian-fan1, Li Zhe1

(1.Hubei Engineering University，College of Technology,Hubei Xiaogan 432000，China;2.Hubei Institute of Aerospace Technology,Institute of Measurement and Testing technology, Hubei Xiaogan 432000,China)

Abstract:Missile guidance involves a large amount of image processing and calculations, and generally system realization takes single or multi high performance processorsasits core. The basic structure of an embedded multiprocessor system is analyzed, and the platform-specific FSMC bus is used to support static segmentation and task-scheduling two parallel algorithms, and further study the parallelization of image binarization algorithm. Test results show that the design can support two parallel algorithms, greatly reducing image processing time.

Key words:embedded systems; multiprocessor systems; FSMC bus; binarization algorithm; parallel algorithms

中圖分類號：TJ765.3

文獻標志碼：A

文章編號：1009-086X(2015)-02-0103-07

doi:10.3969/j.issn.1009-086x.2015.02.017

通信地址：432000湖北省孝感市學院路158號E-mail：mail.lujun@gmail.com

作者簡介：盧軍(1975-)，男，湖北孝昌人。副教授，碩士，研究方向為網(wǎng)絡信息安全與多智能體協(xié)同控制。

基金項目：湖北省自然科學基金(2014CFB576)；湖北工程學院自然科學基金(201515)

* 收稿日期：2014-10-20；
修回日期：2014-12-05