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

文/吳振華

1 引言

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

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

2 方法

2.1 計(jì)算機(jī)圖像處理的原理

計(jì)算機(jī)圖像處理的原理如圖1所示。

圖1

圖2

圖3

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

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

2.2 繪圖處理流程

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

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

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

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

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

圖4

圖5

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

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

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

圖6

圖7

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

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

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

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

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

圖8

3.4 線程工作池

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

工作原理如下：

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

圖9

3.5 運(yùn)行測試

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

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

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

測試平臺(tái)：

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ù)的方式快速刷新隨機(jī)顯示圖片（注：圖片規(guī)格為128x64和81x100的圖片），如圖9所示，得到如下結(jié)果：

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

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

4 總結(jié)

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