基于分塊處理的2D圖像并行繪制技術(shù)

文/吳振華

1 引言

在近年來，隨著計算機技術(shù)的快速發(fā)展，帶動了各種各樣不用功能的應(yīng)用軟件面世，隨著軟件越來越絢麗漂亮，對計算機性能的要求也越來越高，而計算機性能很大一部分的性能開銷是在圖像處理方面，在通常情況下，為了獲得更高的圖像處理性能，往往是依賴更快速的GPU處理（GPU英文全稱Graphic Processing Unit，中文翻譯為“圖形處理器”）。而高性能GPU往往都是功耗最高的部件之一，平均功率甚至超過CPU功耗，而與此同時，CPU的性能在大多數(shù)情況下卻出現(xiàn)“性能過剩”的情況，尤其是多核CPU，如今大多程序都只利用到單核，而Intel公司創(chuàng)始人之一戈登·摩爾曾經(jīng)提出著名的摩爾定律在多核CPU時代已經(jīng)幾乎走到盡頭，也就是說，基于單線程的應(yīng)用效率的提升已經(jīng)不能再依賴于CPU單核性能的提升，必須使用合適的并行技術(shù)和算法，最大限度的發(fā)揮多核CPU的優(yōu)勢，才能使得應(yīng)用程序的效率成倍提升。

從日常的應(yīng)用軟件不難看出，90%以上都是基于2D形式的表現(xiàn)和設(shè)計的，剩下很少的部分以3D的形式表現(xiàn)的。如果在這90%以上的應(yīng)用中，我們能在不增加或者幾乎不增加CPU負(fù)擔(dān)的情況下利用CPU完成這些繪圖的處理，就可以不必給GPU增加計算量產(chǎn)生功耗上的浪費。而這些軟件的功能不管多么復(fù)雜，最終與人交互的時候都會通過GUI（Graphical User Interface，圖形用戶界面）來表現(xiàn)，而這些內(nèi)容從畫面的直觀來看，無非就是一堆點，線，圖片和文字之類通過各種方式組合在一起形成特定的表現(xiàn)形式。其中最具有豐富表現(xiàn)的就是圖片了，無論我們看到多么絢麗的效果，無非就是圖片的各種混合，縮放，旋轉(zhuǎn)等等方式組合而成。在傳統(tǒng)的方式下，比如Windows平臺，大量應(yīng)用程序都采用微軟 的MFC（Microsoft Foundation Classes）來實現(xiàn)繪圖，而這些都是采用GDI（Graphics Device Interface，圖形設(shè)備接口）實現(xiàn)，這些方式雖然非常簡單，靈活，但是比較遺憾的是在上層的應(yīng)用開發(fā)中，沒有辦法修改底層實現(xiàn)，在繪圖的時候也都只能不可避免回到單線程進(jìn)行處理，從而不能使效率最大化。而多核并行計算技術(shù)是當(dāng)前計算機領(lǐng)域的研究熱點。多核中的并行分為指令級并行 (instruction-level parallelism，ILP) 和線程級并行 (thread-level parallelism，TLP)，而線程級并行被普遍認(rèn)為將是下一代高性能處理器的主流體系結(jié)構(gòu)技術(shù)。隨著多核計算機的普及，線程級并行計算已經(jīng)廣泛用于計算機科學(xué)的多個領(lǐng)域，也正引領(lǐng)著程序設(shè)計由串行到并行的基礎(chǔ)性變化。所以文章從線程級并行的角度出發(fā)，在軟件層面上論述并實現(xiàn)了并行的繪圖方式。

2 方法

2.1 計算機圖像處理的原理

計算機圖像處理的原理如圖1所示。

圖1

圖2

圖3

通常來說，計算機中CPU、GPU、顯示屏幕是以上面這種方式協(xié)同工作的。CPU計算好顯示內(nèi)容提交到 GPU，GPU渲染完成后將渲染結(jié)果放入幀緩沖區(qū)，隨后視頻控制器會按照幀緩沖區(qū)的數(shù)據(jù)，經(jīng)過可能的數(shù)模轉(zhuǎn)換傳遞給屏幕顯示。而對于程序來說，繪圖循環(huán)如圖2所示。

如何在這個繪圖循環(huán)中，優(yōu)化繪圖機制，減少執(zhí)行開銷，提高運行效率，是文中主要討論的問題。

2.2 繪圖處理流程

從日常應(yīng)用的軟件我們知道，在很多情況下，每一幀的畫面變化的時候，或許并不是屏幕內(nèi)所有區(qū)域的畫面都變化了，比如點擊一個按鈕，就只是這個按鈕做了一個變化表示這個按鈕的狀態(tài)變成“被按下了”，而與此同時，屏幕的其他部分是不需要做改變的，如果能把這些不需要改變的部分做標(biāo)記，在每一幀刷新時候跳過這些計算，那么性能將會得到很大提高。

如圖3，以繪制圖片為例：有A，B兩個圖片，繪圖順序為A-B，在傳統(tǒng)的方式下，每一幀畫面需要刷新的時候，都要重新繪制AB的全部部分，哪怕AB的繪圖屬性都不發(fā)生變化，或者只是A或者B發(fā)生了變化都需要這么做。而明顯地看出，在AB都沒變化的時候，AB是不需要重新繪制的，如果A發(fā)生變化，也只需要重新繪制A和B∩A的部分。所以我們要把需要繪制的部分描繪為“需要更新”，不需要重繪制的描繪為“保持不變”，保留上一次繪圖的內(nèi)容即可，只需要處理“需要更新”的部分即可。

為此，我們把整個屏幕區(qū)域劃分為M個固定的子區(qū)域，只要這個與這些子區(qū)域相交的繪制屬性發(fā)生變化，就重新繪制與這個子區(qū)域相交的圖片的交集部分。如圖4。

繪圖順序是A-B，如果A的繪圖屬性發(fā)生發(fā)生變化，與A相交的子區(qū)域會被重新繪制，對于上圖來說，需要繪制的部分有：A ∩ A11，A ∩ A21， A ∩ A12， A ∩ A22，B ∩ A22。不需要重繪制的有：B ∩ A32，B ∩ A23，B ∩ A33。

這樣劃分子區(qū)域的好處，在于對于子區(qū)域變化后計算。設(shè)有n個需要繪制的圖片，最壞情況下，每個圖片與M個固定子區(qū)域相交的部分，計算也只是M*n，由于M是一個固定常數(shù)，它相對于n而言都很小，所以可以認(rèn)為這個計算的時間復(fù)雜度為O(n)。而且每個子區(qū)域是固定的范圍，所以每個子區(qū)域的計算都可以作為一個獨立模塊，也就很自然和直觀的看出這個方式非常適合多線程的并行處理，發(fā)揮多核處理器的最大性能。

圖4

圖5

3 實現(xiàn)與結(jié)果討論

3.1 從上層繪圖過程到底層繪圖命令

對于上層的軟件開發(fā)來說，如果要顯示一個圖片，或者一個文字，或者繪制一些點，線之類，是不去關(guān)心底層是如何處理的，也沒有必要關(guān)心。所以，底層做的一切，都是為了上層在不需要了解細(xì)節(jié)的情況下，就能實現(xiàn)高效率的繪圖方案。為此，需要構(gòu)建一個從上層到下層的橋梁，也就是在上層調(diào)用繪圖處理的時候，需要轉(zhuǎn)換為底層命令，要實現(xiàn)這一目的，需要定義一系列的繪圖命令，每一個命令對應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以及一個管理命令的命令池結(jié)構(gòu)，最終目標(biāo)是把各種繪圖命令做一個隊列化的操作，以便在繪圖的時候能順序進(jìn)行處理。流程如圖5。

圖6

圖7

3.2 分塊子區(qū)域的邏輯

在3.1的基礎(chǔ)上，把整個繪圖區(qū)域劃分為若干個子區(qū)域，由于每個子區(qū)域的數(shù)據(jù)是不重疊的，所以能非常方便的用于并行處理。對于每個子區(qū)域，使用兩個命令隊列，一個是“當(dāng)前幀的繪圖命令隊列”，一個是“上一幀的繪圖命令隊列”，每一幀開始的時候，清空當(dāng)前幀繪圖命令隊列，再逐漸添加當(dāng)前幀的各種繪圖命令，這樣設(shè)計的目的，是用于判斷當(dāng)前幀的繪圖命令隊列和上一幀的繪圖命令隊列是否完全一樣，如果完全一樣，就說明這個區(qū)域沒有改動，是不需要重新繪制的。如果不一致，則需要做繪圖處理。如此完成操作之后，交換當(dāng)前幀和上一幀的繪圖命令隊列指針，繼續(xù)往返循環(huán)。對于每個子區(qū)域的工作機制如圖6。

3.3 繪圖指令分配到子區(qū)域

要把上層繪圖的指令分配到每個相關(guān)的子區(qū)域，先看最簡單的方式：

如圖7，假定每個子區(qū)域大小為W x H, 有一個 M x N 大小的圖片貼在了x, y的位置，那么該圖片與圖中的4個子區(qū)域都有交集，所以A(0,0), A(1,0), A(1,0), A(1,1)這幾個子區(qū)域都需要把這個圖片的繪圖命令添加到自身的繪圖隊列。繪圖的時候，只需要處理這個圖片與每個子區(qū)域范圍交集的部分就行，相當(dāng)于把繪圖的范圍精確的分配到每一個子區(qū)域，對于其他的情況，比如繪制一段線段，一批點集之類的圖片數(shù)據(jù)，均可用類似的方式，把對應(yīng)的數(shù)據(jù)按照不同的方式進(jìn)行切割，分配到對應(yīng)的子區(qū)域內(nèi)，再做不同的數(shù)據(jù)處理，得到的每個子區(qū)域需要繪制的內(nèi)容就是一個互不相交的結(jié)果，組合起來就得到了整個完整的繪圖區(qū)域。

圖8

3.4 線程工作池

到此為止，已經(jīng)得到了所需繪制的一系列子區(qū)域中的各種繪圖命令，為了實現(xiàn)并行的計算，文中設(shè)計了一個工作線程的集合，如圖8。

工作原理如下：

把需要重新繪制的n個子區(qū)域做成一個隊列，如圖8 A1-An，假定有3個工作線程做處理，最開始的時候，選取A1,A2,A3分別進(jìn)入每個工作線程，并把它們從隊列中刪除，然后工作線程開始進(jìn)入工作狀態(tài)，由于每一個子區(qū)域的計算量都不一樣，所以每個工作線程的完成進(jìn)度有快有慢，比如計算A1的工作線程完成了，便可以繼續(xù)從隊列里面尋找下一個子區(qū)域重復(fù)上述過程，如果隊列為空，且所有工作線程都工作完成，就說明本次并行處理全部完成了，也就代表這一幀的畫面整體處理完成。

圖9

3.5 運行測試

在并行計算領(lǐng)域，加速比用于表示當(dāng)并行算法與對應(yīng)的順序執(zhí)行算法相比較時，速度快了多少。加速比以如下公式定義：

其中p指CPU數(shù)量，T1指順序執(zhí)行算法的執(zhí)行時間，Tp指當(dāng)有P個處理器時，并行算法的執(zhí)行時間。當(dāng)Sp=p時，Sp便可稱為理想加速比。意味著若將處理器加倍，執(zhí)行速度也會加倍。由加速比派生出來的加速效率則是度量性能的指標(biāo)，定義如下：

加速效率Ep的值一般介于0~1之間，表示在解決問題的時候，參與計算的處理器得到了什么程度的充分利用，如果加速效率Ep>1則稱為超線性加速比。

測試平臺：

CPU：Intel Corei7 6700K @4.00GHZ

主板：技嘉GA-Z170-HD3

內(nèi)存：海盜船DDR4-2133 @16GB

硬盤：三星850EVO@250G 固態(tài)硬盤

顯卡：七彩虹 GTX1070 8G顯存

操作系統(tǒng)：Windows10 專業(yè)版

在1024x768 分辨率下，使用傳統(tǒng)方式（單線程，無分塊處理）與分塊處理的并行繪制技術(shù)的方式快速刷新隨機顯示圖片（注：圖片規(guī)格為128x64和81x100的圖片），如圖9所示，得到如下結(jié)果：

不鎖定刷新率，讓程序每秒鐘盡可能的刷新多次，記錄如下：

可以計算出這個條件下的加速效率E8分別為：63%, 79%, 82%, 82%，平均加速效率=76.5%

4 總結(jié)

傳統(tǒng)的繪圖方式既不能利用并行處理讓CPU利用最大化，也不能通過分塊處理技術(shù)減少計算量，而基于分塊處理的并行繪制技術(shù)，在CPU利用最大化的同時，也能優(yōu)化的減少計算量，在單位時間內(nèi)承載的計算量更多，同等計算量下耗費的時間最少，大大提高了多核CPU的加速效率，所以是一種很值得推廣的技術(shù)，尤其在繪圖密集型領(lǐng)域比如游戲領(lǐng)域能大大發(fā)揮加速作用。雖然該技術(shù)在純CPU處理下和傳統(tǒng)方式對比取得了很好的效果，但是遺憾的是，該技術(shù)還不能讓GPU進(jìn)行類似并行化處理并和傳統(tǒng)的方式進(jìn)行比較，如果今后能利用GPU進(jìn)行分塊并行處理的話，相信性能還會比傳統(tǒng)方式提升一個很大的臺階。