JPEG2000的MQ模塊在DSP環(huán)境下的優(yōu)化實(shí)現(xiàn)

張浩宇，徐建軍，張　南

（國防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院，長沙　410072）

JPEG2000的MQ模塊在DSP環(huán)境下的優(yōu)化實(shí)現(xiàn)

張浩宇，徐建軍，張南

（國防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院，長沙410072）

隨著航空技術(shù)和專用CCD/CMOS成像技術(shù)的飛速發(fā)展，星載系統(tǒng)中圖像的大小和清晰度都成倍的提高，由此帶來的數(shù)據(jù)量和帶寬要求也呈指數(shù)級增長，如何在星載高性能的計(jì)算平臺(tái)下有效壓縮圖像成為了星載系統(tǒng)面臨的最主要挑戰(zhàn)之一。經(jīng)典的JPEG2000圖像壓縮算法，其模塊并不適應(yīng)高性能DSP中編譯器進(jìn)行流水線排布的要求，導(dǎo)致運(yùn)行效率無法達(dá)到要求。本文面向JPEG2000圖像壓縮算法，提出一種在DSP環(huán)境下，JPEG2000算法中MQ編碼器的優(yōu)化算法。優(yōu)化算法使用了多種線性匯編語言流水線排布的通用優(yōu)化技術(shù)對MQ編碼器進(jìn)行DSP環(huán)境適應(yīng)性優(yōu)化，并根據(jù)MQ編碼器算法特點(diǎn)，進(jìn)行了編碼流程簡化和二次重歸一化過程中冗余分支的消除。圖像壓縮試驗(yàn)表明，該算法提高了MQ編碼器的吞吐率，提升了JPEG2000的壓縮效率。

數(shù)字信號處理器；JPEG2000；算術(shù)編碼器；線性匯編

本文著錄格式：張浩宇，徐建軍，張南. JPEG2000的MQ模塊在DSP環(huán)境下的優(yōu)化實(shí)現(xiàn)[J]. 軟件，2016，37（9）：130-135

1　引言

在航天偵測領(lǐng)域，隨著圖像處理技術(shù)的進(jìn)步和應(yīng)用需求的發(fā)展，海量的探測數(shù)據(jù)和有限的空地?cái)?shù)傳帶寬之間的矛盾亟待解決。高性能DSP[1]的出現(xiàn)使得高速在軌圖像壓縮成為可能，依靠多個(gè)功能部件并發(fā)執(zhí)行指令和軟件流水排布技術(shù)，高性能 DSP顯著提升了程序代碼尤其是其中循環(huán)代碼的執(zhí)行效率。但是其編譯器在進(jìn)行軟件流水線排布時(shí)有著諸如循環(huán)中的代碼不能過長，一般不能超過250條線性匯編指令；循環(huán)中不能有函數(shù)調(diào)用；循環(huán)中不能有跳轉(zhuǎn)指令；循環(huán)中的條件判讀不能過多，一般不能超過6個(gè)；循環(huán)不能有嵌套；程序執(zhí)行時(shí)不能有中斷產(chǎn)生等限制[1]，這就對程序代碼的編寫提出了嚴(yán)格的要求。

JPEG2000是新一代的圖像壓縮算法，具有壓縮速度快，信噪比高，同時(shí)支持有損和無損壓縮，可同時(shí)生成多種分辨率等優(yōu)點(diǎn)。JPEG2000的壓縮過程如圖1所示，其中的嵌入式塊編碼過程（EBCOT）把經(jīng)過離散小波變化（DWT）得到的小波系數(shù)分成互相不重疊且大小相同的編碼塊，然后將編碼塊按比特位高低分成多個(gè)位平面，然后從最高有效位平面到最低有效位平面，對于每個(gè)位平面進(jìn)行基于上下文的算術(shù)編碼（MQ編碼）。

圖1　JPEG2000編碼流程

圖2是MQ編碼器的一個(gè)簡要工作流程。它的輸入是當(dāng)前的數(shù)據(jù)位D和當(dāng)前位的上下文（如前文表述概念）決定的類型CX組成的一個(gè)決定對，而輸出是單個(gè)的壓縮碼字，也就是壓縮數(shù)據(jù)CD。壓縮數(shù)據(jù)CD也叫做一個(gè)“MQ碼段”，只是被壓縮的碼流中的一部分。當(dāng)數(shù)據(jù)位D和類型CX組成的數(shù)據(jù)對（CX，D）從位平面編碼器到達(dá)時(shí)，壓縮數(shù)據(jù)位CD增量的產(chǎn)生。

MQ編碼器使用了狀態(tài)變量來實(shí)現(xiàn)算術(shù)編碼，這些變量包括A，C，temp，t和L。A和C是分別用來表示概率區(qū)間長度和下限，他們一起表示出當(dāng)前的概率子區(qū)間。temp為一臨時(shí)的字節(jié)緩沖器，用來保存輸出的編碼。t用作一個(gè)計(jì)數(shù)器，當(dāng)這個(gè)計(jì)數(shù)器減少到零時(shí)，部分產(chǎn)生的編碼位應(yīng)被移出C寄存器，并移入臨時(shí)字節(jié)緩沖器temp中。L代表到當(dāng)前為止所產(chǎn)生的編碼字節(jié)數(shù)。

圖2　MQ編碼器流程

由于不同碼流引起的輸出序列是不同且唯一的，所以MQ編碼器對于不同的碼流概率估計(jì)值也不可能是固定的，必須能夠?qū)崿F(xiàn)隨著碼流數(shù)據(jù)變化而隨時(shí)調(diào)整。MQ編碼器通過使用概率值表和上下文狀態(tài)表能夠?qū)崿F(xiàn)隨碼流變化自適應(yīng)的功能。

其中概率估計(jì)表是一個(gè)可以對原始數(shù)據(jù)快速適應(yīng)的概率估計(jì)模型。概率估計(jì)表包括47個(gè)索引值。每個(gè)索引都對應(yīng)著不同的狀態(tài)，每個(gè)狀態(tài)有28位，其中6位是當(dāng)前符號是大概率符號（MPS）時(shí)下一個(gè)索引（NMPS）；6位是當(dāng)前符號是小概率符號（LPS）時(shí)下一個(gè)索引（NLPS）；一位是交換位（SWITCH）來確定本輪是否發(fā)生大概率符號的交換，只有當(dāng)前符號是小概率符號的時(shí)候才有可能用到；15位是小概率符號的概率值（Qe），它體現(xiàn)了序號值Index和對類型CX的LPS最不可能符號的估計(jì)概率之間的關(guān)系。大概率符號（MPS）就是在之前的碼流中出現(xiàn)的次數(shù)多的符號，它就是0或者1，隨著碼流輸入不斷變化。

上下文概率映射表包括19個(gè)不同的狀態(tài)，每個(gè)狀態(tài)包括索引值（index）和大概率符號值（MPS）。Index是一個(gè)范圍從0到46的6比特量，對應(yīng)于概率估計(jì)表中的一項(xiàng)，用于標(biāo)識(shí)對當(dāng)前類型的符號集合做的概率估計(jì)。

MQ編碼器大體可以分為兩個(gè)主要階段[2]，第一階段是編碼階段，根據(jù)輸入的上下文判斷當(dāng)前的編碼符號的類型是大概率符號（MPS）還是小概率符號（LPS），并根據(jù)該類型當(dāng)前保存的索引取出當(dāng)前該類型符號的概率估計(jì)值（Qe），并根據(jù)Qe值按照輸入D進(jìn)行新概率計(jì)算，更新A、C寄存器和該類型的索引。第二階段是重歸一化階段，主要進(jìn)行碼流的輸出和概率的重歸一化。

針對MQ編碼器的性能問題，不少學(xué)者提出了優(yōu)化方案，劉奇衛(wèi)[3]等人設(shè)計(jì)了4級流水線的2符號并發(fā)編碼結(jié)構(gòu)，王振道[4]等人設(shè)計(jì)實(shí)現(xiàn)了一種部分并行的優(yōu)化算法，但這些優(yōu)化都是針對算法本身的改進(jìn)，沒有針對DSP應(yīng)用平臺(tái)，仍無法改變其不適應(yīng)DSP環(huán)境的問題。本文基于TI的C6000系列DSP，消除了JPEG2000在DSP環(huán)境下對流水線排布影響較大的上下文機(jī)制，將MQ編碼器模塊進(jìn)行適應(yīng)性改造，大幅提高了程序的運(yùn)行速度。

2　改寫過程中的線性匯編優(yōu)化

首先對于MQ編碼器使用線性匯編語言進(jìn)行改寫，但僅僅對原模塊進(jìn)行簡單的線性匯編改造，并沒有體現(xiàn)出本文選擇DSP處理器的初衷。為了充分發(fā)揮DSP并行優(yōu)勢，提高程序性能，使用了以下方法：

（1）使用DSP環(huán)境下的指令條件執(zhí)行機(jī)制來取代原有跳轉(zhuǎn)指令。根據(jù)不同的DSP型號，在DSP中一般會(huì)提供5-6個(gè)條件寄存器，儲(chǔ)存在該寄存器中的變量可用于作為其它指令的條件：即當(dāng)條件寄存器內(nèi)變量非0時(shí)，使用它作為條件的指令就會(huì)被執(zhí)行，否則則不執(zhí)行，具體改造示例如圖3所示：

圖3　使用條件執(zhí)行機(jī)制消除跳轉(zhuǎn)

（2）循環(huán)展開。由于編譯器進(jìn)行流水排布時(shí)只對最內(nèi)層循環(huán)進(jìn)行排布，因此在程序改造中通過條件執(zhí)行機(jī)制將嵌套循環(huán)的外層循環(huán)每次迭代后的參數(shù)變化改為條件執(zhí)行語句，從而展開這一層循環(huán)，擴(kuò)大流水排布范圍，達(dá)到進(jìn)一步改善流水排布效果的目的。具體改造示例如圖4所示：

圖4　使用條件執(zhí)行機(jī)制展開循環(huán)

（3）通過數(shù)據(jù)預(yù)取與打包減少流水空閑。流水線排布的成功與否主要受到程序 的結(jié)構(gòu)影響，而排布成功之后的流水線的執(zhí)行時(shí)間則主要受制于訪存指令多少。訪存指令需要多個(gè)周期執(zhí)行，且往往與其后的指令有較高的相關(guān)性，很多時(shí)候會(huì)導(dǎo)致流水線因等待數(shù)據(jù)而停滯。對此，本文主要采用一次存取多個(gè)數(shù)據(jù)和提前讀取數(shù)據(jù)的方法減少訪存指令的數(shù)量及其造成的流水線空白期。C6000系列一次可以存取64位數(shù)據(jù)，而一般程序中處理的數(shù)據(jù)以16位和32位為主，這樣通過64位的存取操作指令和數(shù)據(jù)處理指令我們可以一次讀取多個(gè)數(shù)據(jù)從而減少存取指令的數(shù)量。同時(shí)，我們將循環(huán)中的讀取指令提前，即在進(jìn)入循環(huán)前預(yù)取第一次循環(huán)所要用到的數(shù)據(jù)，以后每次循環(huán)都在做本次循環(huán)的數(shù)據(jù)處理的同時(shí)預(yù)取下次循環(huán)即將用到的數(shù)據(jù)，減少因等待數(shù)據(jù)而造成的流水線停滯。

3　MQ編碼器模塊優(yōu)化

針對DSP獨(dú)特的體系結(jié)構(gòu)，為了提高M(jìn)Q模塊在DSP環(huán)境下的效率，不僅僅需要在匯編語言級別進(jìn)行適應(yīng)性優(yōu)化，而且需要對MQ編碼器的流程進(jìn)行優(yōu)化改造，使之在目標(biāo)平臺(tái)上具有更高的效率。

3.1編碼流程簡化

MQ的編碼階段的算法流程如圖5所示，算法有五條執(zhí)行路徑，在原有算法的運(yùn)行情況下DSP的匯編優(yōu)化器難以排布并行流水線，效率會(huì)大大降低。而如果基于前述的DSP并行流水排布規(guī)則進(jìn)行優(yōu)化，為了消除分支指令，相當(dāng)于將5條路徑全部展開串行執(zhí)行，將導(dǎo)致循環(huán)單次迭代長度過長且相關(guān)性較高，即使排布出流水也極大的影響流水線排布效果。因此，需要對算法的執(zhí)行流程進(jìn)行優(yōu)化。

將圖中的左路分支合并入右路后MQ編碼器的重歸一化流程如圖6所示，其中，當(dāng)t=0時(shí)的字節(jié)輸出過程在一次重歸一化過程中最多執(zhí)行2次，輸出字節(jié)時(shí)有兩種情況主要是因?yàn)镸Q編碼器當(dāng)0xFF字節(jié)被輸出到字節(jié)緩沖器時(shí)，會(huì)將一多余的冗余位插入到變化的碼字中，保證來自之前編碼中對C寄存器的算術(shù)操作所產(chǎn)生的進(jìn)位不會(huì)傳播到已經(jīng)被發(fā)送到字節(jié)緩沖中的字節(jié)。在發(fā)生第一次字節(jié)輸出時(shí)，由于C寄存器的值來源于編碼階段，在發(fā)生C=C+D的操作時(shí)可能會(huì)產(chǎn)生進(jìn)位，故8位的temp寄存器的值在與進(jìn)位相加時(shí)出現(xiàn)了3種可能會(huì)大于等于0xFF的情況，這就使得不僅需要對輸出進(jìn)行獨(dú)立，使temp=0x100時(shí)輸出0xFF，還需要在寄存器向temp中移入值時(shí)考慮進(jìn)位的存在，導(dǎo)致這一分支比較復(fù)雜。但是在第二次字節(jié)輸出發(fā)生時(shí)，寄存器C和t的值都來源于上一次字節(jié)輸出后的更新，這種情況下，上一次字節(jié)輸出后的處理保證了這一次t=0時(shí)C一定不會(huì)產(chǎn)生進(jìn)位，故不需要考慮特殊的輸出，也不需要考慮保留進(jìn)位，其過程可簡化成如，從而減少冗余分支，提高性能。

圖5　MQ編碼器編碼流程

圖6　優(yōu)化后的MQ編碼流程

圖7　重歸一化階段算法流程圖

3.2二次重歸一化的冗余分支消除

首先將圖7中的左路分支合并入右路后MQ編碼器的重歸一化流程。其中，當(dāng)t=0時(shí)的字節(jié)輸出過程在一次重歸一化過程中最多執(zhí)行2次，輸出字節(jié)時(shí)有兩種情況主要是因?yàn)镸Q編碼器當(dāng)0xFF字節(jié)被輸出到字節(jié)緩沖器時(shí)，會(huì)將一多余的冗余位插入到變化的碼字中，保證來自之前編碼中對C寄存器的算術(shù)操作所產(chǎn)生的進(jìn)位不會(huì)傳播到已經(jīng)被發(fā)送到字節(jié)緩沖中的字節(jié)。

在發(fā)生第一次字節(jié)輸出時(shí)，由于C寄存器的值來源于編碼階段，在發(fā)生C=C+D的操作時(shí)可能會(huì)產(chǎn)生進(jìn)位，故8位的temp寄存器的值在與進(jìn)位相加時(shí)出現(xiàn)了3種可能會(huì)大于等于0xFF的情況，這就使得不僅需要對輸出進(jìn)行獨(dú)立，使temp=0x100時(shí)輸出0xFF，還需要在寄存器向temp中移入值時(shí)考慮進(jìn)位的存在，導(dǎo)致這一分支比較復(fù)雜。

但在第二次字節(jié)輸出發(fā)生時(shí)，寄存器C和t的值都來源于上一次字節(jié)輸出后的更新，這種情況下，上一次字節(jié)輸出后的處理保證了這一次t=0時(shí)C一定不會(huì)產(chǎn)生進(jìn)位，故不需要考慮特殊的輸出，也不需要考慮保留進(jìn)位，其過程可簡化成如圖8，從而減少冗余分支，提高性能。

圖8　優(yōu)化后輸出過程

4　試驗(yàn)及測試結(jié)果

選用不同分辨率下的圖像壓縮的標(biāo)準(zhǔn)測試樣本中Lena的黑白二值圖片作為測試集合。對于使用原始MQ編碼器模塊的JPEG2000程序及使用優(yōu)化后版本的JPEG2000程序分別進(jìn)行壓縮測試并利用Profiler獲取其總執(zhí)行時(shí)間及MQ模塊執(zhí)行時(shí)間。各程序版本編譯選項(xiàng)為-opt-level=3。測試結(jié)果如下表所示。測試結(jié)果表明，本文提出的MQ模塊優(yōu)化改造有效提高了MQ模塊及壓縮程序的執(zhí)行效率。

圖9　圖像測試集

表1　壓縮測試結(jié)果

5　結(jié)束語

本文提出了一種星載DSP環(huán)境下JPEG2000的算術(shù)編碼模塊的優(yōu)化方案，該方案采用循環(huán)展開等方法解決原程序無法排布軟件流水的問題，另外通過算法執(zhí)行路徑和垂直提升算法進(jìn)行優(yōu)化改造，從而大大提高了MQ模塊的單次執(zhí)行效率以及JPEG2000壓縮算法的整體壓縮效率。另外，該方法在實(shí)際使用中還有若干問題有待解決，如MQ編碼器軟件流水排布效率問題以及JPEG2000中其他模塊的優(yōu)化問題等，都有待于進(jìn)一步研究。

[1] Texas Instruments Incorporated. TMS320C6000系列DSP編程工具與指南[M]. 田黎育, 何佩琨. 出版地: 北京清華大學(xué)出版社, 2006. 9: 235-240.

[2] Skodras A, Christopoulos C, Ebrahimi T. The Jpeg 2000 Still Image Compression Standard[J]. IEEE Signal Processing Magazine, 2010, 18(5): 36-58.

[3] 劉奇衛(wèi). 基于JPEG2000二進(jìn)制算術(shù)編碼器的研究與設(shè)計(jì)[D]. 浙江大學(xué), 2006.

[4] 王鎮(zhèn)道, 章兢等. 一種JPEG2000算術(shù)編碼器的優(yōu)化算法與實(shí)現(xiàn)[J]. 湖南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2007, 34(4).

Optimization and Implementation of MQ Encoder of JPEG2000 in DSP

ZHANG Hao-yu, XU Jian-jun, ZHANG Nan
(Academy of Computer Science and Technology, National University of Defense Technology, Changsha 410072)

With the rapid development of aviation technology and a dedicated CCD/CMOS imaging technology, space borne system image size and clarity are increased exponentially, which lead to the exponential growing of the magnitude of data and bandwidth requirements. Therefore, how to compress images effectively in space borne systems have become a hot topic and a serious challenge. The classic JPEG2000 image compression algorithm is not designed to run on DSP, so the perfermance decline rapidly. This paper present a optimized MQ-encoder in DSP based on JPEG2000 compression algorithm. The optimizations used in the paper include serval common optimized techonologies in order to let the compiler construct pipeline properly. Furthermore, based on the characters of MQ encoder, we simplify the encoding flow and cut some paths in the secondary normalization. According to the experiment results, the optimized MQ-encode algorithm applying our method achieves higher throughput compared to the classical algorithm.

DSP; JPEG2000; MQ; Arithmetic-Encoder

TP391.41

A

10.3969/j.issn.1003-6970.2016.09.031