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

1(國防科技大學 計算機學院,湖南 長沙 410073)

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

1 引 言

Xorg 圖形服務器起源于20 世紀80 年代初,是Unix/Linux 系統(tǒng)上最基本的圖形交互系統(tǒng)[1],大致架構如圖1 所示.Xorg 圖形服務器采用Client/Server 設計思想,具備卓越的靈活性和強大的功能,成為Unix/Linux 中缺省的主流圖形交互環(huán)境.但是基于Client/Server 的X 協(xié)議的開銷,使Xorg 圖形服務器也一直因為效率和性能方面的問題而飽受詬病[2].

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

Fig.1 Xorg server圖1 Xorg 圖形服務器

Fig.2 WayLand compositor圖2 WayLand

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

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

1.1 主事件循環(huán)

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

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

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

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

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

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

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

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

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

1.2 幀緩存設備

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

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

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

1.3 矩形填充

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

可繪制對象Drawable 是X 中所有可繪制對象的基本抽象結構,所有GCOps 的操作都在某一種可繪制對象Drawable 上完成.Drawable 又分為Pixmap 和Window 兩種,一般認為,Pixmap 為單純圖像的位圖,而Window 則可能包含標題欄、菜單欄、按鈕欄和窗體等組成部分.本文算法主要針對Window 類型的Drawable 對象實現.

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

1) 指向Drawable 對象的指針pDrawable;

2) 指向GC 的指針pGC;

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

4) 該次調用需要填充的矩形結構鏈表的指針prect.

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

2 相關工作

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

2.1 多調度隊列

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

2.2 輸入線程化

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

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

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

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

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

Fig.5 Drawable screen partition圖5 Drawable 分屏

3.1 屏幕劃分

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

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

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

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

3.2 私有任務隊列

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

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

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

Fig.6 Multi-task queues圖6 多任務調度隊列

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

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

Fig.9 Process function圖9 Process 子函數

3.2.1 任務封裝

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

3.2.2 條件等待

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

3.2.3 私有緩沖區(qū)

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

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

3.2.4 就緒和運行雙隊列

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

3.3 主子線程負載均衡

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

3.3.1 溢出隊列

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

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

1) 防止子線程任務隊列長度的無限快速增長.如圖7 所示算法,如果不進行負載均衡,主線程T0將任務放入恰當的子線程Tk的就緒隊列Qk后,并不需要做任何實際的矩形填充繪制工作即可返回,所以從調用主線程T0的應用程序來看,矩形填充操作都將會以異常快的速度完成,而此時的任務實際上仍然在某個子進程的私有緩沖區(qū)中,并沒有實際繪制完成.如果不對生產產品的速度加以限制,這將可能導致過長的就緒隊列Qk.當Drawable 所屬的整個進程退出時,相應子線程將不得不耗費非常長的時間來處理并清空這些任務隊列;

2) 防止圖形界面進入無響應的等待狀態(tài).因為如果Xorg 主線程T0發(fā)現任務生產過多后,不進行負載均衡而是立即進入睡眠狀態(tài),這將導致Xorg 進入無響應的等待狀態(tài),停止響應用戶的鼠標鍵盤,圖形交互系統(tǒng)也將失去響應,當前窗口將變灰無法操作.

值得注意的是:因為沒有線程給生產者主線程T0分配任務,所以T0的就緒隊列Q0一直保持為空.

4 測試和結論

4.1 測試平臺和用例

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

Fig.10 x11perf -rect100圖10 x11perf -rect100 測試用例

上述的測試平臺在單線程的普通幀緩存模式下,x11perf -rect100 的得分約為454 000.在并行幀緩存算法中,將把圖10 所示的測試窗口按照x軸和y軸分別均分成Sx和Sy份,共被分為Sx?Sy個互不相交的子屏幕.測試結果如圖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 加速比分析

實驗測試曲線如圖11～圖19 所示,因為私有就緒隊列長度N數量級變化很大,所以采用log2(N)表示圖中橫坐標.縱坐標為x11perf 得分(得分值越高,性能也越高).不同顏色的曲線對應不同的私有運行隊列長度M值.

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

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

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

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

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

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

5 未來的工作

5.1 順序一致性

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

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

5.2 子線程間的負載均衡

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

5.3 單桌面多用戶

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

如果能夠實現單桌面多用戶,即同一個桌面允許多個用戶(每個用戶使用一對鼠標鍵盤)同時操作,與通過網絡連接起來的多桌面多用戶相比,就可以共享更多資源,并降低用戶間的通信開銷,提高多用戶之間互操作和協(xié)作的效率,例如共用顯存中已經渲染好的3D 圖像、使用共享內存作為高帶寬通信等.結合多屏顯示技術還可以通過一臺終端并行完成多臺顯控終端的功能,減小顯控終端的體積和重量.這對于車載或者機載條件下的協(xié)同指揮而言,可能具有潛在的應用價值.

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