并行幀緩存設(shè)備:基于多核CPU的Xorg并行顯示優(yōu)化?

高 瓏,戴華東,楊沙洲,丁 滟

1(國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410073)

2(軍事科學(xué)院 國(guó)防科技創(chuàng)新中心,北京 100091)

1 引 言

Xorg 圖形服務(wù)器起源于20 世紀(jì)80 年代初,是Unix/Linux 系統(tǒng)上最基本的圖形交互系統(tǒng)[1],大致架構(gòu)如圖1 所示.Xorg 圖形服務(wù)器采用Client/Server 設(shè)計(jì)思想,具備卓越的靈活性和強(qiáng)大的功能,成為Unix/Linux 中缺省的主流圖形交互環(huán)境.但是基于Client/Server 的X 協(xié)議的開銷,使Xorg 圖形服務(wù)器也一直因?yàn)樾屎托阅芊矫娴膯?wèn)題而飽受詬病[2].

針對(duì)Xorg 圖形服務(wù)器的效率和性能問(wèn)題,有過(guò)不少改進(jìn)的嘗試,比較著名的有WayLand[3-6],如圖2 所示.WayLand 改進(jìn)了Client/Server 的工作模式,轉(zhuǎn)而采用Client/Compositor 模式.但WayLand 對(duì)于幀緩存設(shè)備并無(wú)更多改進(jìn),對(duì)于嵌入式設(shè)備上的幀緩存設(shè)備的性能并無(wú)改善.

Fig.1 Xorg server圖1 Xorg 圖形服務(wù)器

Fig.2 WayLand compositor圖2 WayLand

資源受限的嵌入式操作系統(tǒng)常采用幀緩存設(shè)備作為Xorg 的繪圖設(shè)備.隨著多核CPU 的發(fā)展,目前嵌入式系統(tǒng)也逐步采用多核嵌入式CPU.但是Xorg 對(duì)于幀緩存設(shè)備仍然采用單線程串行的使用模式,導(dǎo)致在進(jìn)行大量繪制操作時(shí),容易造成CPU 單核負(fù)載過(guò)高,而其他CPU 核心處于相對(duì)空閑的狀態(tài),甚至影響到整個(gè)Xorg 的交互和顯示體驗(yàn).對(duì)于Xorg 的幀緩存設(shè)備進(jìn)行并行化研究,不僅對(duì)于加速幀緩存設(shè)備上的繪制操作具有意義,也將有利于在Xorg 上建立多用戶交互通道的研究.

本文將試圖從優(yōu)化Xorg 圖形服務(wù)器的幀緩存設(shè)備入手,研究如何在多核CPU 上優(yōu)化Xorg 圖形服務(wù)器的顯示性能.本文以下部分提及的Xorg 圖形服務(wù)器簡(jiǎn)稱為X.

1.1 主事件循環(huán)

與大部分系統(tǒng)服務(wù)進(jìn)程類似,X 中最主要的部分是一個(gè)名為Dispatch 的無(wú)限循環(huán),稱為主事件循環(huán).其偽算法采用單線程模式運(yùn)行,可以簡(jiǎn)要描述如圖3 所示.

· 首先,在步驟①中,X 將睡眠等待,直到被系統(tǒng)通知喚醒(包括鼠標(biāo)鍵盤等輸入事件觸發(fā)的SIGIO 信號(hào)以及用戶的請(qǐng)求等);

· 然后,在步驟②中,X 將輸入信息處理成標(biāo)準(zhǔn)事件放入事件隊(duì)列中,并將各個(gè)事件發(fā)送給對(duì)相應(yīng)事件感興趣的客戶端程序;

· 最后,在步驟③中,X 完成客戶端請(qǐng)求的服務(wù),一般是請(qǐng)求圖形繪制等服務(wù).如無(wú)任何輸入和服務(wù)請(qǐng)求發(fā)生,則X 將繼續(xù)睡眠等待.整個(gè)循環(huán)周而復(fù)始,直到X 被異常條件終止為止.

Fig.3 Main loop dispatch of Xorg圖3 Xorg 圖形服務(wù)器主事件循環(huán)

可以看到:目前X 對(duì)于用戶輸入、事件處理、響應(yīng)用戶請(qǐng)求等的處理依然采用串行處理方式,如果上一個(gè)主事件循環(huán)中的客戶端請(qǐng)求還沒(méi)有處理完,X 就難以及時(shí)處理用戶在下一個(gè)循環(huán)中的交互輸入并做出響應(yīng).在CPU 單核性能較弱或者系統(tǒng)重負(fù)載的情況下,這種串行處理方式將會(huì)使X 的交互體驗(yàn)變得很差.如果在軍事指揮控制等領(lǐng)域出現(xiàn)這種情況,將可能導(dǎo)致嚴(yán)重的后果.

針對(duì)這種問(wèn)題的并行化優(yōu)化的思路主要有兩個(gè)方向.

(1)在步驟③中讓X 盡快并行處理完客戶端程序的請(qǐng)求,如圖形繪制請(qǐng)求等,本文主要按此方向展開討論和研究;

(2)多個(gè)子線程同時(shí)并行處理主事件循環(huán),該方向思路將在第5.3 節(jié)中簡(jiǎn)要地加以討論.

1.2 幀緩存設(shè)備

幀緩存設(shè)備是從Linux 內(nèi)核2.2 版本開始引入的,被廣泛應(yīng)用在嵌入式領(lǐng)域[7-13].幀緩存設(shè)備對(duì)應(yīng)內(nèi)存或者GPU 顯存的一部分存儲(chǔ)空間,如圖4(a)中陰影部分所示.這部分空間內(nèi)放置的數(shù)據(jù)恰好對(duì)應(yīng)于屏幕上顯示的圖像,Xorg 通過(guò)向幀緩存設(shè)備寫入數(shù)據(jù)完成繪制操作,進(jìn)而畫出各種圖形,大量繪制時(shí)CPU 負(fù)載較重.與之相對(duì)應(yīng),在GPU 硬件加速模式中,CPU 則僅完成GPU 指令和數(shù)據(jù)在內(nèi)存的設(shè)置工作,隨后由GPU 完成剩余的圖形繪制,CPU 負(fù)載較輕,如圖4(b)所示.

由于CPU 性能的不斷提高,幀緩存設(shè)備的性能也不斷提高.同時(shí),由于很多現(xiàn)代CPU 指令集中也逐步加入了支持多媒體和圖形圖像處理的SIMD 指令[14-19],例如Intel 指令集中的MMX 指令和SSE 指令[20-22]、AMD指令集中的3DNow!指令[23,24]、ARM 指令集中的NEON 指令[25,26]等,使得很多現(xiàn)代CPU 在圖形圖像處理方面也有長(zhǎng)足進(jìn)步,CPU 逐步獲得較高的圖形繪制能力.例如:SSE 指令在Geometry Processing 中可以獲得接近4 倍的性能提升[22];使用ARM 的NEON 指令優(yōu)化后,不少應(yīng)用的性能可以提高4～8 倍[27],包括X 的繪制函數(shù)fbCompositeSolidMask的速度也提高了8 倍[27].由于在pixman 函數(shù)庫(kù)中通常已經(jīng)包含對(duì)于SSE 和NEON 等SIMD 指令的匯編指令級(jí)優(yōu)化,所以X 一般通過(guò)直接調(diào)用優(yōu)化過(guò)的pixman 圖形函數(shù)庫(kù)來(lái)利用這些CPU 的SIMD指令.另外,一般由于業(yè)界的GPU 大廠商,如AMD、Nvidia、ARM 等都不完全開放GPU 驅(qū)動(dòng)源碼和硬件接口協(xié)議,導(dǎo)致Linux桌面上的GPU 驅(qū)動(dòng)發(fā)展相對(duì)滯后,性能相對(duì)Windows 的商業(yè)閉源GPU 驅(qū)動(dòng)低很多,在國(guó)產(chǎn)CPU領(lǐng)域尤其如此.所以在某些嵌入式場(chǎng)景中,X 使用幀緩存設(shè)備獲得的性能甚至超過(guò)X 使用開源GPU 驅(qū)動(dòng)所獲得的性能[28,29].

在多核CPU 上進(jìn)一步提升幀緩存設(shè)備的性能,需在多核CPU 上針對(duì)幀緩存設(shè)備開發(fā)線程級(jí)并行處理(thread level parallelism,簡(jiǎn)稱TLP)[30,31].即:在多核之間同時(shí)并行處理數(shù)千條以上規(guī)模的指令序列[32],才能有效彌補(bǔ)核間通信與同步的開銷.

1.3 矩形填充

圖形上下文GC(graphics context)是X 中所有繪制操作的核心數(shù)據(jù)結(jié)構(gòu),所有的基本圖形繪制都要通過(guò)GC來(lái)完成.與文件系統(tǒng)讀寫操作類似,每一個(gè)GC 都有一組相對(duì)應(yīng)的GCOps 函數(shù)指針來(lái)完成圖形繪制.GCOps 包含畫點(diǎn)、畫線、畫矩形、畫橢圓、傳輸拷貝等20 余種繪制操作函數(shù)指針.對(duì)于幀緩存設(shè)備來(lái)說(shuō),所有的繪制操作,都是通過(guò)CPU 逐個(gè)改變像素點(diǎn)來(lái)實(shí)現(xiàn)的.對(duì)于其中任意一種繪制操作的并行優(yōu)化,原理上對(duì)于其他繪制操作都是適用的.本文主要針對(duì)矩形填充操作進(jìn)行優(yōu)化,其他繪制操作可以用類似的方法來(lái)實(shí)現(xiàn).

可繪制對(duì)象Drawable 是X 中所有可繪制對(duì)象的基本抽象結(jié)構(gòu),所有GCOps 的操作都在某一種可繪制對(duì)象Drawable 上完成.Drawable 又分為Pixmap 和Window 兩種,一般認(rèn)為,Pixmap 為單純圖像的位圖,而Window 則可能包含標(biāo)題欄、菜單欄、按鈕欄和窗體等組成部分.本文算法主要針對(duì)Window 類型的Drawable 對(duì)象實(shí)現(xiàn).

矩形填充函數(shù)PolyFillRect是幀緩存設(shè)備的GCOps 的繪圖操作函數(shù)指針之一,專門用來(lái)在幀緩存設(shè)備上填充繪制由純色填滿的矩形.相應(yīng)的參數(shù)包含4 部分.

1) 指向Drawable 對(duì)象的指針pDrawable;

2) 指向GC 的指針pGC;

3) 該次繪制的矩形數(shù)量nrect;

4) 該次調(diào)用需要填充的矩形結(jié)構(gòu)鏈表的指針prect.

PolyFillRect一般隨后會(huì)調(diào)用單個(gè)矩形繪制函數(shù),例如fbFill,逐個(gè)繪制鏈表prect所指向的所有矩形,fbFill的前2 個(gè)參數(shù)一般與PolyFillRect相同,后4 個(gè)參數(shù)一般是矩形的左上頂點(diǎn)的坐標(biāo)值(x,y)以及寬度w和高度h.本文算法就是針對(duì)在幀緩存設(shè)備上的矩形繪制進(jìn)行多線程優(yōu)化的,在單個(gè)矩形繪制函數(shù)fbFill中生成任務(wù)并分發(fā)給多個(gè)子線程完成,其他繪制操作可以按照類似方法進(jìn)行優(yōu)化.

2 相關(guān)工作

針對(duì)X 相關(guān)的多線程優(yōu)化,已有的工作包括多調(diào)度隊(duì)列算法、X 的輸入線程化、CPU 和GPU 協(xié)同多線程等.Linux 內(nèi)核調(diào)度器的多調(diào)度隊(duì)列算法打破了集中調(diào)度的局限性,采用分散的多調(diào)度隊(duì)列,降低了全局調(diào)度開銷.不過(guò),針對(duì)其他具體應(yīng)用場(chǎng)景,仍需要根據(jù)算法思想進(jìn)行重新設(shè)計(jì)和優(yōu)化.X 的輸入線程化是指將處理鼠標(biāo)鍵盤事件的過(guò)程作為單獨(dú)的線程分離出來(lái),但并未進(jìn)行多線程處理,也不涉及幀緩存設(shè)備的優(yōu)化.CPU 和GPU 協(xié)同多線程優(yōu)化主要涉及CPU 端的數(shù)據(jù)準(zhǔn)備和控制等方面的多線程優(yōu)化,以便充分發(fā)揮高性能GPU 的繪制性能起輔助功能,但不包含CPU 端針對(duì)幀緩存設(shè)備的優(yōu)化工作.

2.1 多調(diào)度隊(duì)列

在并行計(jì)算中,單調(diào)度隊(duì)列帶來(lái)的性能開銷往往都是O(n)的,全局單一的任務(wù)調(diào)度隊(duì)列往往會(huì)帶來(lái)訪問(wèn)沖突、性能開銷大等問(wèn)題.例如:Linux 內(nèi)核在2.4 版本之前的調(diào)度器采用全局單一調(diào)度隊(duì)列,調(diào)度的開銷是O(n);而2.6 版本之后引入的O(1)調(diào)度器針對(duì)每個(gè)優(yōu)先級(jí)分別設(shè)置私有的任務(wù)調(diào)度隊(duì)列,將調(diào)度開銷降低到O(1)的常數(shù)時(shí)間,可以做到調(diào)度開銷與系統(tǒng)中線程個(gè)數(shù)無(wú)關(guān).CFS 調(diào)度器則為每一個(gè)CPU 核心維護(hù)一棵以時(shí)間為順序的紅黑樹,確保實(shí)現(xiàn)接近完全公平的進(jìn)程調(diào)度[33].但針對(duì)其他具體應(yīng)用場(chǎng)景仍需重新設(shè)計(jì)算法.

2.2 輸入線程化

在通常的處理流程中,X 圖形服務(wù)器在沒(méi)有任何輸入時(shí)一直保持睡眠狀態(tài),直到被鼠標(biāo)鍵盤的輸入事件激發(fā)的SIGIO 信號(hào)喚醒.因?yàn)樾盘?hào)處理開銷較大,也容易發(fā)生無(wú)效喚醒(lost wakeup)的問(wèn)題,開源社區(qū)已在嘗試放棄原先沿用的 SIGIO 信號(hào),改用獨(dú)立的單個(gè)線程處理輸入事件.例如,Keith Packard 這幾個(gè)月以來(lái)提交的threaded input 補(bǔ)丁[34],現(xiàn)在已經(jīng)合并到主分支加以發(fā)布.輸入線程從主事件循環(huán)中獨(dú)立出來(lái),將有效地減小主事件循環(huán)中鼠標(biāo)鍵盤的處理過(guò)程對(duì)圖形繪制的影響,改造后,如圖3 所示,X 圖形服務(wù)器根據(jù)用戶請(qǐng)求繪制圖形的過(guò)程(process request)將不必再等待鼠標(biāo)鍵盤處理過(guò)程(processInput)完成,而可以立即執(zhí)行.但處理鼠標(biāo)鍵盤的輸入線程仍為一個(gè),沒(méi)有考慮多用戶的情況,具體可以參考第5.3 節(jié)的討論.

2.3 CPU和GPU協(xié)同多線程

即使在圖4(b)所示的GPU 繪制模式中,CPU 也具有重要作用:CPU 將協(xié)助GPU 準(zhǔn)備所需的數(shù)據(jù)并進(jìn)行控制.由于現(xiàn)在很多GPU 性能越來(lái)越高,所以不少情況下CPU 端的計(jì)算也會(huì)成為系統(tǒng)的瓶頸,此時(shí)進(jìn)行CPU 的多核優(yōu)化將有助于消除這種繪制過(guò)程中的瓶頸.例如,最新的Windows 平臺(tái)上的圖形開發(fā)庫(kù)DirectX 12 和Linux的下一代OpenGL Vulkan 都已經(jīng)實(shí)現(xiàn)了針對(duì)多核CPU 的優(yōu)化,圖形渲染性能成倍提高[35,36].

3 幀緩存并行顯示優(yōu)化算法

為了實(shí)現(xiàn)幀緩存設(shè)備的并行化,并最大程度地避免不同子線程之間的數(shù)據(jù)相關(guān)性,我們對(duì)屏幕進(jìn)行劃分,劃分后的每一塊子屏幕對(duì)應(yīng)一個(gè)子線程,僅繪制位于該子屏幕中的圖形,如圖5 所示.本文中僅針對(duì)矩形填充操作SolidFill進(jìn)行了實(shí)現(xiàn),其他圖形繪制操作的實(shí)現(xiàn)與此類似.

Fig.5 Drawable screen partition圖5 Drawable 分屏

3.1 屏幕劃分

本文第1.3 節(jié)中已經(jīng)介紹過(guò)可繪制對(duì)象Drawable,X 中的每一個(gè)Drawable 都對(duì)應(yīng)屏幕上某一塊矩形可繪制區(qū)域,即窗口對(duì)象Window 或者位圖對(duì)象Pixmap 在屏幕上所占據(jù)的區(qū)域.圖5 中的最大矩形就代表某Drawable 對(duì)應(yīng)的可繪制區(qū)域,由橫坐標(biāo)x軸和縱坐標(biāo)y軸標(biāo)示.一般使用矩形的左上頂點(diǎn)Pul和右下頂點(diǎn)Plr的像素坐標(biāo)值即可唯一確定該矩形的位置和大小.

如圖5 所示,在并行幀緩存算法中,將幀緩存設(shè)備上的每一個(gè)Drawable 對(duì)象對(duì)應(yīng)的矩形屏幕按照x軸和y軸分別平均分成Sx和Sy份,這樣每一個(gè)Drawable 對(duì)象對(duì)應(yīng)的矩形屏幕就被均分成互不相交的Sx?Sy個(gè)子屏幕,每一個(gè)子屏幕用Dk〈i,j〉來(lái)表示,其中,i和j分別代表x軸和y軸上從1 開始的區(qū)間編號(hào),其中,k=Sx(j-1)+i,易知k的范圍1≤k≤Sx?Sy.根據(jù)子屏幕的劃分方法,有:

分屏規(guī)則.給定矩形R的左上頂點(diǎn)Pul以及子屏幕D,R?D,當(dāng)且僅當(dāng)Pul∈D.

也就是說(shuō):僅當(dāng)矩形的左上頂點(diǎn)Pul屬于某個(gè)子屏幕D時(shí),該矩形才屬于該子屏幕D.我們?yōu)樗械淖悠聊籇k創(chuàng)建一個(gè)子線程Tk,將所有屬于子屏幕Dk的矩形R?Dk的填充繪制任務(wù)交給與子屏幕Dk綁定的子線程Tk完成.對(duì)于右下頂點(diǎn)Plr可能超出其所在子屏幕D的矩形,我們將在第5.1 節(jié)中給出討論.

3.2 私有任務(wù)隊(duì)列

并行幀緩存設(shè)備算法參照單生產(chǎn)者多消費(fèi)者模型[37]實(shí)現(xiàn).在經(jīng)典的生產(chǎn)者消費(fèi)者模型中仍然存在一些競(jìng)爭(zhēng)沖突和遍歷開銷等問(wèn)題.為了改進(jìn)這些問(wèn)題,并行幀緩存設(shè)備算法中的每個(gè)消費(fèi)者都采用了獨(dú)立的私有任務(wù)隊(duì)列作為緩沖區(qū),如圖6(b)所示.矩形繪制任務(wù)將由生產(chǎn)者按照分屏規(guī)則分發(fā)到消費(fèi)者各自的私有隊(duì)列中,再由消費(fèi)者從各自的私有隊(duì)列中取出完成.由于分屏規(guī)則計(jì)算量不大,所以生產(chǎn)者分配引入的串行開銷在可以接受的范圍內(nèi).

并行幀緩存設(shè)備算法如圖6(b)所示,T0代表生產(chǎn)者主線程,Tk(1≤k≤Sx?Sy)代表綁定子屏幕Dk(1≤k≤Sx?Sy)的消費(fèi)者子線程.生產(chǎn)者算法如圖7 所示,消費(fèi)者算法如圖8 所示,生產(chǎn)者和消費(fèi)者公用的處理子函數(shù)Process(q)如圖9 所示.

圖6(b)中就緒隊(duì)列Qk長(zhǎng)度N以及運(yùn)行隊(duì)列qk長(zhǎng)度M,實(shí)際上已成為并行幀緩存設(shè)備算法的兩個(gè)主要參數(shù),在第4 節(jié)的實(shí)驗(yàn)中可以看到不同的M和N的取值對(duì)于算法性能的影響.

Fig.6 Multi-task queues圖6 多任務(wù)調(diào)度隊(duì)列

Fig.7 Master T0 thread圖7 主線程T0 算法

Fig.8 Worker Tk thread圖8 子線程Tk 算法

Fig.9 Process function圖9 Process 子函數(shù)

3.2.1 任務(wù)封裝

首先,單個(gè)矩形R(x,y,w,h,seq)被封裝成為獨(dú)立的矩形填充任務(wù)t,如圖6(b)所示,其中包含矩形的坐標(biāo)〈x,y〉、寬w、高h(yuǎn)、標(biāo)記時(shí)間順序的序列號(hào)seq等內(nèi)容,這樣便于將多個(gè)矩形填充任務(wù)加入隊(duì)列.序列號(hào)seq代表任務(wù)生成時(shí)的時(shí)間戳,如圖5 所示算法,每生成一次序列號(hào)seq加1.seq采用長(zhǎng)整型類型long int,一般假定seq在Drawable 生存周期中不會(huì)溢出.因此,如果某任務(wù)的序列號(hào)較小,那么該任務(wù)的生成時(shí)間也較早.

3.2.2 條件等待

每一個(gè)任務(wù)隊(duì)列都設(shè)有加入任務(wù)和彈出任務(wù)兩個(gè)條件等待變量,分別用于控制向隊(duì)列中加入任務(wù)和彈出任務(wù).當(dāng)任務(wù)隊(duì)列l(wèi)為空時(shí),所有從隊(duì)列l(wèi)中彈出任務(wù)的線程,將自動(dòng)進(jìn)入睡眠狀態(tài)等待,直到有線程向隊(duì)列l(wèi)中壓入任務(wù)后,將自動(dòng)喚醒所有等待任務(wù)的線程,繼續(xù)從隊(duì)列中彈出任務(wù).同樣地,若隊(duì)列l(wèi)的長(zhǎng)度超出閾值后,所有向隊(duì)列l(wèi)中增加任務(wù)的線程將獲得一個(gè)錯(cuò)誤返回值,表明隊(duì)列長(zhǎng)度已經(jīng)超過(guò)限定值;此時(shí)可以采取相應(yīng)措施應(yīng)對(duì),本算法采取的是主子線程負(fù)載均衡的措施,具體見第3.3 節(jié)中的討論.圖7 和圖8 所示算法中,都隱含了操作隊(duì)列時(shí)的喚醒和睡眠動(dòng)作.

3.2.3 私有緩沖區(qū)

在標(biāo)準(zhǔn)的單生產(chǎn)者多消費(fèi)者模型中[37],多消費(fèi)者共享的公用緩沖區(qū)容易產(chǎn)生擁塞.如果采用共享的公用緩沖區(qū),如圖6(a)所示,則將導(dǎo)致兩個(gè)問(wèn)題:(1)共享的公用緩沖區(qū)將帶來(lái)競(jìng)爭(zhēng)沖突,某一個(gè)消費(fèi)者在讀寫訪問(wèn)公用緩沖區(qū)時(shí),其他消費(fèi)者只能等待;(2)每一個(gè)消費(fèi)者遍歷共享的公用緩沖區(qū)的開銷較大,遍歷開銷與緩沖區(qū)的長(zhǎng)度N成正比,如果共享的公用緩沖區(qū)較大,還將導(dǎo)致線程間的競(jìng)爭(zhēng)開銷急劇增長(zhǎng).

在并行幀緩沖算法中,每個(gè)消費(fèi)者都具有私有的隊(duì)列緩沖區(qū).主線程既是生產(chǎn)者,也要負(fù)責(zé)將任務(wù)分配到適當(dāng)?shù)淖泳€程中去.主線程將按照分屏規(guī)則把每一個(gè)矩形放入相應(yīng)的消費(fèi)者子線程的私有隊(duì)列緩沖區(qū)中去.由于主線程分配任務(wù)時(shí)處于串行模式?jīng)]有競(jìng)爭(zhēng),可以較快完成,所以這樣既避免了消費(fèi)者遍歷共享的公用緩沖區(qū)挑選任務(wù)的開銷,也避免了多消費(fèi)者在訪問(wèn)共享的公用緩沖區(qū)時(shí)可能產(chǎn)生的競(jìng)爭(zhēng)沖突.具體如圖6(b)所示,在并行幀緩存設(shè)備算法中,每個(gè)消費(fèi)者子線程Tk都擁有兩個(gè)相對(duì)獨(dú)立的私有任務(wù)隊(duì)列:就緒隊(duì)列Qk和運(yùn)行隊(duì)列qk.生產(chǎn)者主線程T0產(chǎn)生矩形填充任務(wù)后,根據(jù)第3.1 節(jié)中的分屏規(guī)則,將任務(wù)放入與子屏幕Dk綁定的子線程Tk的就緒隊(duì)列Qk中.每個(gè)消費(fèi)者子線程Tk每次從自身的就緒隊(duì)列Qk中彈出不多于M個(gè)任務(wù),放入自身的運(yùn)行隊(duì)列qk中,再根據(jù)運(yùn)行隊(duì)列qk中各個(gè)任務(wù)的內(nèi)容逐個(gè)完成矩形填充的繪制工作.

3.2.4 就緒和運(yùn)行雙隊(duì)列

與傳統(tǒng)的生產(chǎn)者消費(fèi)者模型不同,如圖6(b)所示,并行幀緩存設(shè)備算法中的每個(gè)消費(fèi)者子線程Tk(1≤k≤Sx?Sy)都有兩個(gè)分離的隊(duì)列:就緒隊(duì)列Qk和運(yùn)行隊(duì)列qk,分別存放等待繪制的任務(wù)和正在繪制的任務(wù).這樣,當(dāng)生產(chǎn)者線程獨(dú)占就緒隊(duì)列Qk并向Qk中添加產(chǎn)品時(shí),消費(fèi)者線程仍然可以獨(dú)占運(yùn)行隊(duì)列qk來(lái)消費(fèi)產(chǎn)品,而不會(huì)產(chǎn)生互斥競(jìng)爭(zhēng);反之亦然.另一方面,消費(fèi)者每次最多從就緒隊(duì)列Qk中彈出M個(gè)任務(wù)到運(yùn)行隊(duì)列qk,相比每次僅彈出1 個(gè)任務(wù)就進(jìn)行處理而言,也減少了消費(fèi)者互斥訪問(wèn)就緒隊(duì)列Qk的頻率,降低了與生產(chǎn)者之間發(fā)生私有任務(wù)隊(duì)列訪問(wèn)沖突的概率.

3.3 主子線程負(fù)載均衡

在經(jīng)典的生產(chǎn)者消費(fèi)者模型中,當(dāng)有限產(chǎn)品緩沖區(qū)滿時(shí),生產(chǎn)者都是處于空閑等待狀態(tài),等待消費(fèi)者消耗緩沖區(qū)里面的產(chǎn)品之后[37],生產(chǎn)者才能加入新的產(chǎn)品.但空閑的生產(chǎn)者可能浪費(fèi)系統(tǒng)軟硬件資源.

3.3.1 溢出隊(duì)列

與經(jīng)典生產(chǎn)者消費(fèi)者模型不同,本算法設(shè)立了私有任務(wù)隊(duì)列的溢出隊(duì)列,用于主子線程間的負(fù)載均衡[38,39].如圖6 中的溢出隊(duì)列所示:當(dāng)某個(gè)子線程Tk的就緒隊(duì)列Qk長(zhǎng)度大于隊(duì)列長(zhǎng)度預(yù)設(shè)閾值N時(shí),生產(chǎn)者主線程T0將暫停生產(chǎn)任務(wù),并協(xié)助任務(wù)已滿的子線程繪制矩形.具體就是從Qk中彈出等待最久的若干任務(wù)形成溢出隊(duì)列,并加入到主線程T0的運(yùn)行隊(duì)列q0中,由主線程T0盡快地將溢出的任務(wù)繪制完成.當(dāng)生產(chǎn)者主線程T0完成所有子線程的溢出任務(wù)后,生產(chǎn)者主線程T0才再次重新轉(zhuǎn)換回生產(chǎn)者角色,繼續(xù)生產(chǎn)任務(wù).

這種主子線程間的負(fù)載均衡主要有以下好處.

1) 防止子線程任務(wù)隊(duì)列長(zhǎng)度的無(wú)限快速增長(zhǎng).如圖7 所示算法,如果不進(jìn)行負(fù)載均衡,主線程T0將任務(wù)放入恰當(dāng)?shù)淖泳€程Tk的就緒隊(duì)列Qk后,并不需要做任何實(shí)際的矩形填充繪制工作即可返回,所以從調(diào)用主線程T0的應(yīng)用程序來(lái)看,矩形填充操作都將會(huì)以異?？斓乃俣韧瓿?而此時(shí)的任務(wù)實(shí)際上仍然在某個(gè)子進(jìn)程的私有緩沖區(qū)中,并沒(méi)有實(shí)際繪制完成.如果不對(duì)生產(chǎn)產(chǎn)品的速度加以限制,這將可能導(dǎo)致過(guò)長(zhǎng)的就緒隊(duì)列Qk.當(dāng)Drawable 所屬的整個(gè)進(jìn)程退出時(shí),相應(yīng)子線程將不得不耗費(fèi)非常長(zhǎng)的時(shí)間來(lái)處理并清空這些任務(wù)隊(duì)列;

2) 防止圖形界面進(jìn)入無(wú)響應(yīng)的等待狀態(tài).因?yàn)槿绻鸛org 主線程T0發(fā)現(xiàn)任務(wù)生產(chǎn)過(guò)多后,不進(jìn)行負(fù)載均衡而是立即進(jìn)入睡眠狀態(tài),這將導(dǎo)致Xorg 進(jìn)入無(wú)響應(yīng)的等待狀態(tài),停止響應(yīng)用戶的鼠標(biāo)鍵盤,圖形交互系統(tǒng)也將失去響應(yīng),當(dāng)前窗口將變灰無(wú)法操作.

值得注意的是:因?yàn)闆](méi)有線程給生產(chǎn)者主線程T0分配任務(wù),所以T0的就緒隊(duì)列Q0一直保持為空.

4 測(cè)試和結(jié)論

4.1 測(cè)試平臺(tái)和用例

測(cè)試平臺(tái)采用一臺(tái)商用DELL OPTIPLEX 3010 臺(tái)式機(jī),4 核心,4G 內(nèi)存,操作系統(tǒng)采用Ubuntu 15.10,內(nèi)核為4.2.0.測(cè)試用例采用通用的x11perf -rect100 測(cè)試用例,如圖10 所示.

Fig.10 x11perf -rect100圖10 x11perf -rect100 測(cè)試用例

上述的測(cè)試平臺(tái)在單線程的普通幀緩存模式下,x11perf -rect100 的得分約為454 000.在并行幀緩存算法中,將把圖10 所示的測(cè)試窗口按照x軸和y軸分別均分成Sx和Sy份,共被分為Sx?Sy個(gè)互不相交的子屏幕.測(cè)試結(jié)果如圖11～圖19 所示.

Fig.11 Sx?Sy=1×1圖11 Sx?Sy=1×1

Fig.12 Sx?Sy=2×1圖12 Sx?Sy=2×1

Fig.13 Sx?Sy=1×2圖13 Sx?Sy=1×2

Fig.14 Sx?Sy=3×1圖14 Sx?Sy=3×1

Fig.15 Sx?Sy=1×3圖15 Sx?Sy=1×3

Fig.16 Sx?Sy=2×2圖16 Sx?Sy=2×2

Fig.17 Sx?Sy=3×2圖17 Sx?Sy=3×2

Fig.18 Sx?Sy=2×3圖18 Sx?Sy=2×3

Fig.19 Sx?Sy=3×3圖19 Sx?Sy=3×3

4.2 加速比分析

實(shí)驗(yàn)測(cè)試曲線如圖11～圖19 所示,因?yàn)樗接芯途w隊(duì)列長(zhǎng)度N數(shù)量級(jí)變化很大,所以采用log2(N)表示圖中橫坐標(biāo).縱坐標(biāo)為x11perf 得分(得分值越高,性能也越高).不同顏色的曲線對(duì)應(yīng)不同的私有運(yùn)行隊(duì)列長(zhǎng)度M值.

從圖11～圖19,每一個(gè)圖都代表一種不同的分屏方案.不同的分屏方案(Sx和Sy)之間對(duì)比,一般分屏數(shù)量越多,性能值越高,但超過(guò)4 個(gè)分屏后,性能增加明顯減少,甚至下降;每一個(gè)圖內(nèi),每一條由相同的運(yùn)行隊(duì)列長(zhǎng)度M對(duì)應(yīng)的曲線,一般都隨著N的增大其性能逐步提高,但都在大約log2(N)=15 之后便不再明顯上升反而有所下降;每一個(gè)圖內(nèi),在任意N值附近,一般M越大性能越高,但當(dāng)M超過(guò)1 024 后,性能反而有所下降.

從圖11～圖19 可見:隨著屏幕越分越細(xì)密(Sx和Sy增大)以及子進(jìn)程私有隊(duì)列越來(lái)越長(zhǎng)(M和N越來(lái)越長(zhǎng)),矩形繪制性能逐步提高,并且測(cè)試曲線逐步接近直線,加速比也逐步趨于線性.分析其原因,主要是由于隨著屏幕劃分的增多,可以創(chuàng)造出更多的線程,為充分發(fā)揮多核CPU 的性能提供了可能;另外,M和N的增加,也使多線程同步和互斥的相對(duì)開銷所占比例逐步降低,使得加速比曲線更加趨近線性.

但曲線也并非一直增長(zhǎng),大約在log2(N)=15 附近取得極值.考慮到本實(shí)驗(yàn)中CPU 僅有4 物理核心,所以創(chuàng)造出多于4 個(gè)物理核心的線程后,反而會(huì)帶來(lái)子線程等待和切換的開銷,所以再增加分屏數(shù)目或者增加隊(duì)列長(zhǎng)度應(yīng)當(dāng)也不能再持續(xù)提高加速比,可以近似地認(rèn)為該算法在參數(shù)M=1024,log2(N)=20,Sx?Sy=2×3 時(shí)取得加速比極大值2.06.此時(shí),x11perf 的得分約為935 333.

假設(shè)算法中串行執(zhí)行的部分為a,因?yàn)楸緦?shí)驗(yàn)中可同時(shí)并行執(zhí)行的線程最多為4 個(gè),根據(jù)阿姆達(dá)爾定律[40],理想狀態(tài)下的加速比應(yīng)當(dāng)為公式(1)中等號(hào)左邊的多項(xiàng)式.考慮到實(shí)際測(cè)試時(shí)的各種開銷,那么實(shí)際測(cè)試所得極大值2.06 應(yīng)滿足:

所以可以推出a<0.3139.所以,根據(jù)極限狀態(tài)下的阿姆達(dá)爾定律,本算法的極限加速比將是串行部分比例a的倒數(shù),即:

上述分析可以得出結(jié)論:通過(guò)不斷增加CPU 的核心數(shù)目,該算法加速比的極限值至少可以達(dá)到3.18;從另一個(gè)方面說(shuō),該算法仍然還有改進(jìn)空間,例如將主線程T0用于分配任務(wù)的串行計(jì)算時(shí)間以進(jìn)一步優(yōu)化壓縮或者并行化.

5 未來(lái)的工作

5.1 順序一致性

在本文算法中,如圖20 所示,如果矩形R的右下頂點(diǎn)Plr超出所屬子屏幕的范圍,可能導(dǎo)致與其他子屏幕中的矩形R′有重疊.由于R和R′分屬不同的子線程繪制,如果由于線程調(diào)度的原因,最終導(dǎo)致較早請(qǐng)求繪制的矩形遮擋了較晚請(qǐng)求繪制的矩形,可能會(huì)對(duì)用戶交互產(chǎn)生影響.下一步將會(huì)在考慮順序一致性的基礎(chǔ)上對(duì)算法進(jìn)行改進(jìn),例如改進(jìn)矩形劃分算法,將同時(shí)出現(xiàn)在屏幕上的所有矩形動(dòng)態(tài)劃分成互不相交的若干組,以避免不同線程之間的相互干擾.

Fig.20 Sequence consistency圖20 順序一致性

5.2 子線程間的負(fù)載均衡

本文已經(jīng)研究了主子線程間的負(fù)載均衡,可以避免出現(xiàn)單個(gè)子線程負(fù)擔(dān)過(guò)重,但無(wú)法防止出現(xiàn)單個(gè)子線程負(fù)載較低的情況,這種情況下可能會(huì)影響算法的并行加速效果.雖然此時(shí)可以通過(guò)操作系統(tǒng)調(diào)度其他線程運(yùn)行,但是如果一開始就把任務(wù)更加平均地分配給所有的子線程,那么將會(huì)有更好的加速效果.但從另外一個(gè)角度來(lái)講,更精確的任務(wù)分配算法也會(huì)帶來(lái)更大的開銷,這需要進(jìn)一步權(quán)衡和研究.

5.3 單桌面多用戶

同一個(gè)X 圖形服務(wù)器,僅允許一個(gè)用戶(每個(gè)用戶使用一對(duì)鼠標(biāo)鍵盤)使用.X 圖形服務(wù)器的XInput 子系統(tǒng)可以在同一個(gè)桌面上支持多個(gè)相對(duì)獨(dú)立的鼠標(biāo)鍵盤,但是目前,測(cè)試XInput 的多個(gè)鼠標(biāo)鍵盤只能按照主從模式交替使用,還無(wú)法做到指針移動(dòng)和點(diǎn)擊等全部功能完全對(duì)等地同時(shí)使用.另外,XInput 子系統(tǒng)對(duì)于應(yīng)用程序不透明,導(dǎo)致有些應(yīng)用程序暫時(shí)還無(wú)法使用XInput 子系統(tǒng).

如果能夠?qū)崿F(xiàn)單桌面多用戶,即同一個(gè)桌面允許多個(gè)用戶(每個(gè)用戶使用一對(duì)鼠標(biāo)鍵盤)同時(shí)操作,與通過(guò)網(wǎng)絡(luò)連接起來(lái)的多桌面多用戶相比,就可以共享更多資源,并降低用戶間的通信開銷,提高多用戶之間互操作和協(xié)作的效率,例如共用顯存中已經(jīng)渲染好的3D 圖像、使用共享內(nèi)存作為高帶寬通信等.結(jié)合多屏顯示技術(shù)還可以通過(guò)一臺(tái)終端并行完成多臺(tái)顯控終端的功能,減小顯控終端的體積和重量.這對(duì)于車載或者機(jī)載條件下的協(xié)同指揮而言,可能具有潛在的應(yīng)用價(jià)值.

將主事件循環(huán)完全線程化,是實(shí)現(xiàn)單桌面多用戶的技術(shù)途徑之一,還可以避免因?yàn)槟硞€(gè)用戶的某個(gè)耗時(shí)操作導(dǎo)致主事件循環(huán)的后續(xù)操作無(wú)法進(jìn)行,以至整個(gè)桌面陷入無(wú)響應(yīng)死鎖狀態(tài)的情況.本文中所研究的多任務(wù)隊(duì)列,將為這些研究工作提供技術(shù)支持.