基于Open VG云電子書系統(tǒng)的多級優(yōu)化框架設計

張春燕，于 麗

(新疆警察學院 信息安全工程系，烏魯木齊 830000)

基于Open VG云電子書系統(tǒng)的多級優(yōu)化框架設計

張春燕，于 麗

(新疆警察學院 信息安全工程系，烏魯木齊 830000)

針對電子書應用存在的文件格式、性能效率低下和圖像失真等問題，設計了一種應用于云電子書系統(tǒng)的多級優(yōu)化框架，優(yōu)化框架主要體現(xiàn)在如下三個方面；第一，對向量圖形類庫的性能進行描述，并提出了一種優(yōu)化算法，減少了類庫的時間復雜度;第二，在嵌入式GPU上并行進行坐標系統(tǒng)的計算;利用GPU在并行計算方面的優(yōu)勢，云電子書在向量圖形類庫方面獲取了顯著的性能提升;第三，云電子書將文件轉化功能轉嫁給Hadoop云平臺，節(jié)省了移動設備的能量消耗和計算時間。同時為了對Hadoop調度過程中的數(shù)據位置問題進行優(yōu)化，將位置感知調度器運用到提出的系統(tǒng);實驗結果表明：云電子書系統(tǒng)與最初的Open VG類庫相比，性能提升了約70%，而且云電子書系統(tǒng)與連續(xù)服務器平臺相比，計算時間減小了約60%。

電子書；向量圖形類庫；GPU；云；位置感知調度器

0 引言

電子書[1]主要由數(shù)字形式的文本和圖像構成，可在計算機或其他電子設備上觀看。最近十多年，許多電子書應用程序可以在移動設備上運行，而且出現(xiàn)了很多電子書應用程序。但是，這些應用程序沒有得到廣泛應用，這是因為電子書應用在移動設備上運行存在一些缺陷。其最大問題是圖像失真，當用戶調節(jié)圖像尺寸時，電子書的內容和圖像可能發(fā)生失真[2]，這是因為電子書上顯示的大多數(shù)圖像都是位圖類型的圖形。針對該問題，可縮放向量圖像(Scalable Vector Graphics, SVG)技術[3]是解決圖像失真的有效途徑。

近些年，一些工業(yè)制造商已經對電子書應用進行了廣泛的研究。大部分研究工作關注的是電子書應用[4]、安全[5-6]、和平臺標準化[7]。也有一些研究者[8-9]在移動操作系統(tǒng)上采用SVG技術，這些移動操作系統(tǒng)有Android、微軟的Windows Phone(現(xiàn)在已經很少見到Windows操作系統(tǒng)的智能手機)和蘋果的iOS。文獻[10-11]通過修改光柵化的處理過程，利用雙掃描線對渲染過程進行加速，進而優(yōu)化了Open VG[3]類庫的性能，其主要關注于渲染和光柵化過程中的算法優(yōu)化問題。但是，在Open VG[3]類庫中路徑轉化是另外一個計算強度函數(shù)，而Android VG[12]是一種三角劃分過程。

一般情況下，向量圖形技術不僅可以解決圖像失真問題，而且還可以很好地解決電子書中文件格式統(tǒng)一的問題。但是，將向量圖形技術引入到電子書應用中后，產生了另外兩個問題：

1)向量圖形圖像在電子書應用中所表現(xiàn)出的性能低于一張由位圖進行渲染的圖像，這是因為向量圖形技術需要花費大量的時間處理路徑的技術和繪制。

2)向量圖形圖像的文件尺寸與以位圖格式存儲的圖像相比要大很多，這是因為向量信息需要復雜的描述。

為了解決上述問題，本文提出了一種優(yōu)化電子書應用，即將嵌入式GPU[13]和云平臺的計算資源進行了有效的整合。將Open VG[3]類庫和Android系統(tǒng)進行了整合，并且通過嵌入式GPU加速優(yōu)化了Android系統(tǒng)上的向量圖形類庫。其突出的優(yōu)點有：

1)通過向量圖形庫解決了電子書應用中存在的圖像失真問題；

2)云電子書可以將向量圖形庫的時間復雜度從O(n2)減少到O(n*logn)，因此通過修改圖形三角劃分算法以及將路徑計算任務轉嫁到嵌入式GPU；

3)云電子書在Hadoop平臺[14]上開發(fā)并執(zhí)行了一個位置感知調度器，該調度器不僅提高了向量圖形轉化器的性能，而且提高了Hadoop平臺上的數(shù)據命中率。

1 云電子書的優(yōu)化

本節(jié)介紹云電子書系統(tǒng)中的系統(tǒng)類庫優(yōu)化過程，即基于Open VG[3]規(guī)范和源代碼開發(fā)出了優(yōu)化類庫。

為了識別和克服瓶頸，對計算密集型階段進行了性能分析，這里的計算密集型階段指的是：Open VG流程中的扁平化、轉化、三角劃分和光柵化。為了對性能進行分析，將性能分析函數(shù)置入Open VG類庫。三個廣為人知的簡單應用包括：Tiger VG、Apple VG和Star VG，這三個應用在改進的向量圖形類庫中執(zhí)行。其中，三角劃分是Open VG類庫中的性能瓶頸。三角劃分過程含有許多圖形計算任務，如計算頂點的坐標，并將整個圖形分割成許多三角形。因此，優(yōu)化三角劃分處理過程是向量圖形類庫中最重要的問題。

1.1 提出的加速三角劃分算法

加速三角劃分算法主要聚焦于對計算步驟的改進以及減少三角劃分算法的時間復雜度。通過將三角劃分步驟簡化為繪畫步驟，進而簡化了計算步驟。

Shiva VG的計算過程中存在三個步驟。第一個步驟是計算模板緩存中的繪制圖形，然后在幀緩存中尋找繪制區(qū)域以添加顏料。Android VG在三角劃分和幀緩存間存在一個更加復雜的流程，Android VG對平面圖形進行了三角劃分，并且向深度緩存中輸出了各部分的劃分圖形。深度緩存步驟結束之后，Android VG就具有了與Shiva VG相同的數(shù)據流。與上述向量圖形類庫不同的是，云電子書已經對計算步驟進行了簡化。于是云電子書在三角劃分步驟中遵循相同的步驟，但是，云電子書直接輸出了與繪制設置相關的劃分信息給幀緩存。這樣，云電子書的計算步驟降低了時間消耗，這是因為對三角劃分步驟進行了改進，這里的時間消耗是指不同緩存間數(shù)據移動所產生的消耗。

向量圖形類庫中原始的三角劃分算法的時間復雜度為O(n2)，其中n表示頂點的個數(shù)。如果輸入的資源是一幅復雜的照片，比如Tiger VG，三角劃分步驟所消耗的時間是向量圖形類庫的瓶頸。為了減小三角劃分步驟的時間復雜度，本文中利用一種單調三角劃分算法替代原始三角劃分算法。將一個多邊形拼接成多個單調多邊形的算法如算法1中所述。

定義1：x單調多邊形。如果每一行正交軸x軸與P最多相交兩次，那么這個多邊形P稱為x單調。

算法1：預處理單調圖形算法

輸入：一個多邊形G=(V,E)，V={v1,v2,...,vn}和一個凹頂點CV=φ的空集合

輸出：單調圖形M的一個集合

1 forj=1；j≤ndo

2 ifvj是一個凹頂點 then

3 將vj加入到CV中；

4 end

5 end

6 根據CV的x坐標將CV從左到右進行排序；

7 While 不是CV的終點 do

8 p =CV中取出的第一個元素；

9 畫一條垂直x軸且穿過凹頂點的直線L；

10 找到一個與直線L和圖像G的感興趣邊相鄰的頂點集合S；

11 if p是一個拼接點 then

12 將p與最近的頂點相連接，這個頂點位于p的右側，而且位于S中；

13 end

14 else

15 將p與最近的頂點相連接，這個頂點位于p的左側，而且位于S中；

16 end

17 將含有頂點p且不含有任何其它凹頂點的子圖形添加到M中；

18 End

19 返回M；

預處理階段的時間復雜度為O(n*logn)，因此，預處理階段不能增加整個三角劃分過程的時間復雜度。預處理階段之后，輸入的多邊形已經轉化成多個單調多邊形塊。在多個單調多邊形上執(zhí)行這種單調三角劃分算法可以將三角劃分階段的時間復雜度從O(n2)降低為O(m*nlogn)，其中m表示G中單調多邊形的個數(shù)，m的大小遠小于n。單調三角劃分算法的具體過程如算法2中所示。

算法2:單調三角劃分算法

輸入：一個單調圖形G=(V,E)和V={v1,v2,...,vn}

輸出：一個三角圖形T

1 對V按照其x軸坐標將其從左至右進行排序

2 forj=1;j≤ndo

3 ifvj與vj-1并不相鄰 then

4 在vj和堆上所有的頂點之間添加斜線；

5 從堆中取出所有的頂點；

6 將vj-1和vj壓入到堆中；

7 end

8 else ifvj具有與vj-1一樣的鏈路 then

9 fork=1;k≤堆尺寸 do

10 從堆中獲取u；

11 ifviukuk-1≤πthen

12 在vi與ui-1之間添加斜邊；

13 從堆中取出ui；

14 end

15 向堆中壓入vj

16 end

17 end

18 end

1.2 并行計算框架的優(yōu)化

為了充分利用移動設備上的計算資源，本文提出了一種采用異構計算機機制的高性能框架，由于目前大多數(shù)移動設備都配備一個嵌入式GPU單元，因此在GPU單元的協(xié)助下，這些應用的性能有所提高。一個GPU含有許多ALU單元，這些ALU單元能夠并行執(zhí)行程序，因此GPU在運行計算密集型應用時速度快于CPU。根據GPU的特性，通過渲染腳本編程接口將移動設備平臺上的三角劃分計算任務轉嫁到嵌入式GPU內進行處理。圖1中給出了云電子書系統(tǒng)中轉嫁機制的框架。

圖1 向量圖形類庫的并行框架

為了充分利用移動設備中的計算單元，轉嫁機制將三角劃分階段的任務劃分成4個子任務，并且在微型處理器單元(micro processing unit, MPU)和GPU上單獨執(zhí)行各個子任務。GPU執(zhí)行的任務屬于計算密集型且高并行處理的任務，MPU不能并行處理任務。這種機制不但利用了GPU的優(yōu)勢，而且也沒有浪費MPU的計算資源。

2 云電子書的部署

云平臺在云電子書系統(tǒng)中所扮演的角色是提供擴展資源，云平臺由三個組件構成：Hadoop分布式文件系統(tǒng)[14](Hadoop Distributed File System, HDFS)、向量圖形轉化器程序和位置感知工作調度算法。由于云的分布式環(huán)境，本文提出了一種位置感知工作調度算法，并且將這種算法應用到云平臺中，進而減少計算節(jié)點和數(shù)據節(jié)點間進行數(shù)據傳輸?shù)臅r間復雜度。利用基于云電子書系統(tǒng)的優(yōu)化云端可以解決移動設備中有限資源所引起的問題。

2.1 參數(shù)描述

位置感知調度器中的參數(shù)包括數(shù)據節(jié)點、數(shù)據的權重、輸入數(shù)據的副本個數(shù)和每個節(jié)點上映射時隙點的個數(shù)。表1中給出了位置感知調度器中所有參數(shù)的簡單定義。

表1 位置感知調度器中定義的參數(shù)

位置感知調度器主要關注“稀有資源”的配置。將數(shù)據節(jié)點稱為稀有資源，數(shù)據節(jié)點中含有一些數(shù)據，這些資源相對缺乏，這是因為數(shù)據節(jié)點的大部分都屬于所需數(shù)據，一些具有高優(yōu)先級的任務占據這些數(shù)據節(jié)點。為了對稀有資源進行區(qū)分，將參數(shù)W(nj,Tdo)作為主要因子以測量位置感知調度器中數(shù)據節(jié)點的稀有程度。一個數(shù)據節(jié)點具有最小值的W(nj,Tdo)，即這個數(shù)據節(jié)點不屬于稀有資源，因此調度器可以向這個數(shù)據節(jié)點派發(fā)計算任務。權重公式的表達式如式(1)所示：

(1)

其中：

(2)

式(1)中，參數(shù)W(nj,Tdo)表示節(jié)點nj中可利用數(shù)據di與云平臺中可利用數(shù)據w(di)總和之間的比值。因此，當節(jié)點nj中含有一些數(shù)據時，參數(shù)W(nj,Tdo)的值會增加，且這些數(shù)據僅存在于節(jié)點nj中。

2.2 位置感知調度算法

本文在工作調度器中采用位置感知調度器。在分配任務之前，工作跟蹤器利用式(1)計算出每個節(jié)點上數(shù)據干擾的權重，每個節(jié)點利用空時隙點執(zhí)行該任務。然后，工作跟蹤器挑選出具有最小數(shù)據干擾權重的節(jié)點，并將任務分派給這個數(shù)據節(jié)點的任務跟蹤器序列。算法3中給出了位置感知算法詳細的步驟。調度器不僅可以計算數(shù)據干擾的權重，進而以一種簡單的方式避免稀有資源分配，而且通過引入數(shù)據干擾權重概念增強了Map Reduce框架中的數(shù)據位置。因此，位置感知調度器減少了數(shù)據傳輸過程中的網絡延遲引起的開銷。另外，利用位置感知調度器還可以提高云平臺的性能。

算法3:位置感知調度算法

輸入：一個用戶任務t和N中的元數(shù)據

輸出：將t分派給nt

1 計算N中每個數(shù)據節(jié)點的權重值w(di)；

2 按照升序對數(shù)據節(jié)點的權重進行排序；

3 從N挑選出第一個具有最小數(shù)據干擾權重值的節(jié)點nfirst；

4 將任務j分派給節(jié)點nfirst中的任務序列。

3 實驗結果與分析

本節(jié)對Android系統(tǒng)和云平臺上執(zhí)行云電子書應用的實驗結果進行了討論。為了展現(xiàn)出云電子書性能的改善水平，本文在云電子書上運行了一系列的位圖格式文件，并且與其它方法進行了對比實驗。向量圖形類庫方法指的是Open VG[3]、Android VG[12]，Hadoop調度器的方法中包括先到先服務準則、文獻[15]提出的公平調度器[15]和提出的位置感知調度器。實驗結果顯示云電子書系統(tǒng)能夠提升73%的Open VG類庫的性能，減小50%～75%文件轉化過程中的時間消耗，并且提高云平臺中10%的數(shù)據命中概率。

3.1 實驗環(huán)境

將實驗環(huán)境劃分為兩個：一個是手持設備中的向量圖形類庫；另一個是Hadoop平臺中的向量圖形轉化器。手持設備環(huán)境中，本文將云電子書安裝在一個Google Nexus 10平臺上。云電子書支持版本為2.3及其之后的Android系統(tǒng)，因此可以將云電子書安裝在大多數(shù)的手持設備上。此外，移動端通過網絡與云平臺進行通信，因此，無線網絡頻段中的干擾不能對移動端的性能產生影響。

云平臺主要由兩個部分構成：第一個部分是Xen云平臺(在多個物理機器上)，第二個部分是Hadoop集群(在Xen集群上)。將這些具有Xen云平臺的物理機器(服務器)作為Xen集群，在Xen集群中，每一個物理機器上都運行多個虛擬機(Virtual Machine, VM)，管理員也可以通過控制面板管理/安裝虛擬機。硬件資源的信息如表2所示。

表2 物理硬件資源

3.2 向量圖形類庫性能

通過運行多個標準對向量圖形類庫性能的提高進行測試，這些基準包括Tiger VG、Apple VG和Star VG，實驗也對Open VG流程中不同階段的性能進行了測量。表3～5給出了不同方法所測量的所有性能值。

Tiger VG的實驗結果如表3所示，從表3中可以看出向量圖形類庫在三角劃分步驟的的性能明顯提升，這是因為在最初的設計中三角劃分具有較大的圖形計算任務負載，在云電子書中，三角劃分的負載可以轉嫁給嵌入式GPU計算單元。

表3 Tiger VG的各階段執(zhí)行時間 ms

Apple VG的實驗結果如表4所示，Apple VG的三角劃分步驟性能也提升較大，Apple VG的執(zhí)行時間減少約60%。另一方面，雖然Star VG的結果如表5所示，雖然含有許多較輕權重的計算任務，但性能依然有所提高。

表4 Apple VG的各階段執(zhí)行時間 ms

表5 Star VG的各階段執(zhí)行時間 ms

云電子書在Star VG和Apple VG的實驗中明顯的提升這兩種實驗環(huán)境的性能。與之相反的是，Star VG的性能并沒有提升很多，這是因為Tiger VG和Apple VG是復雜的2D動畫片。云電子書通過優(yōu)化算法和嵌入式GPU計算器能夠減少復雜2D動畫片的執(zhí)行時間。另一方面，Star VG是一個簡單的2D圖形，這個圖形不需要多余的計算能力。

3.3 云平臺的性能

云平臺的實驗結果在每個階段分別解釋對增強方法效果的影響。首先，云電子書采用圖像群組框架的并行方法，將電子書中所有的位圖格式圖像劃分為多個群組，然后并行地在Hadoop平臺上對位圖格式圖像組進行轉化。本文將云電子書和其它方法進行了性能增強方面的比較，方法包括具有順序處理的服務器和常規(guī)的Hadoop平臺。圖2中給出了提出方法所獲取的性能增強結果，以及總的執(zhí)行時間。圖2中，將實驗任務從2500設置為100000。當任務的個數(shù)增加時，云電子書獲取了顯著的性能提升。當任務的個數(shù)達到100000時，可獲得55%的性能提升。

圖2 服務器端云電子書的性能

為了展現(xiàn)本文提出工作調度器的性能，在兩個不同的分布中設置了三個不同的負載。實驗中，將每分鐘處理15000個任務設置為高，將每分鐘處理10000個任務設置為中，將每分鐘處理5000個任務設置為低。此外，利用一個結合正太分布和泊松分布的仿真客戶端安裝任務生成器以生成實驗負載。在服務器端對所提出的調度器進行了仿真實驗。

表6給出了當工作跟蹤器采用不同調度算法時工作跟蹤器中遺漏計數(shù)個數(shù)(高度負載)。當跟蹤器采用本文所提出的算法作為其調度器時，工作跟蹤器內遺漏計數(shù)的個數(shù)可以減少150～300。表7給出了運行中型負載情況下不同調度器的工作跟蹤器的遺漏比例。如表7所示，本文提出方法對應的數(shù)據遺漏比率性能與先進先出(first in first out, FIFO)調度器相比要高出10%。類似地，如圖8所示，在較輕負載情況下，提出的方法也可以減少10%的數(shù)據遺漏比率。

表6 服務器端調度算法的數(shù)據遺漏比率(高度負載) %

表7 服務器端調度算法的數(shù)據遺漏比率(中度負載) %

表8 服務器端調度算法的數(shù)據遺漏比率(輕度負載) %

4 結論

本文提出了一種綜合電子書系統(tǒng)，即Android系統(tǒng)上的云電子書系統(tǒng)，該系統(tǒng)可提供文件轉化、數(shù)據歸檔和向量圖像表示功能。為了有效地優(yōu)化云電子書系統(tǒng)，提出了一種應用于云電子書系統(tǒng)的多級別優(yōu)化框架。在圖形描述、計算性能等多個方面進行了優(yōu)化。與其他幾種系統(tǒng)和類庫相比，明顯提升了整體性能。

由于許多編程人員利用GPU計算的優(yōu)勢來提高嵌入式環(huán)境中系統(tǒng)類庫的性能，而Open VG是一種性能較差的嵌入平臺實現(xiàn)2D向量圖形標準接口，后期針對特定平臺考慮用GPU對其進行改善。

[1] Larson L C. Digital readers: the next chapter in E-Book reading and response[J]. Reading Teacher, 2010, 64(1): 15-22.

[2] 毛香英, 郁 梅, 蔣剛毅,等. 基于結構失真分析的立體圖像質量客觀評價模型[J]. 計算機輔助設計與圖形學學報, 2012, 24(8): 1047-1056.

[3] Goya C.Visualization of collecting locations based on scalable vector graphics for the specimen information software [J]. Advanced Materials Research, 2014, 642(4): 322-331.

[4] 樂銀煌. 基于學習型電子書的移動學習模式研究及其應用[D]. 中國科學技術大學, 2014.

[5] 楊志剛, 張新興, 龐弘燊. 電子書閱讀器在國外圖書館的應用現(xiàn)狀及存在問題[J]. 大學圖書館學報, 2011, 29(4): 11-17.

[6] 焦靈芝. 亞馬遜電子書平臺研究[D]. 南京:南京大學, 2013.

[7] 王 芳. 電子書標準化建設的目的、現(xiàn)狀與對策探討[J]. 情報科學, 2011, 27(6): 953-956.

[8] Sans V, Diaz J, Implementing a multimedia application on iphone: a case study[A]. 2011 IEEE 14th International Conference on Computational Science and Engineering (CSE), 2011: 233-238.

[9] 丁建飛. 基于語義的電子書交互閱讀[D]. 北京:北京交通大學, 2013.

[10] Kim D, Cha K, Chae S I. A high-performance Open VG accelerator with dual-scanline filling rendering[J]. IEEE Transactions on Consumer Electronics, 2008, 54(3): 1303-1311.

[11] Kim D, Cha K, Soo-Ik C. Adaptive Scanline Filling Algorithm for Open VG 2D Vector Graphics Accelerator.[J]. Ieice Transactions on Information & Systems, 2009, 92(7): 1500-1502.

[12] Jackson W. WatchFaces Vector Design: Using Vector Graphics for WatchFaces [M].Pro Android Wearables. Apress, 2015.

[13] 楊 瑛, 劉文文, 吳方貴. 基于GPU的可視化測量儀器軟件設計[J]. 計算機測量與控制, 2016, 24(8): 150-153.

[14] 姚衛(wèi)國, 張東波. 基于Hadoop分布式平臺的Web文本關鍵詞提取方案[J]. 湘潭大學自然科學學報, 2016, 38(2): 79-83.

[15] Liu J, Wu T, Lin M W, et al. An Efficient Job Scheduling for MapReduce Clusters[J]. International Journal of Future Generation Communication & Networking, 2015, 34(6): 109-115.

Multiple-level Optimization Framework Design of Cloud Electronic Book System Based on Open VG

Zhang Chunyan, Yu Li

(Department of Information Security Engineering, Xinjiang Police College, Urumqi 830000, China)

Concerning the problem of file format, low performance efficiency and image distortion in the application of e-books, a multiple-level optimization framework of cloud e-book is proposed, in which the optimization framework is mainly reflected in the following three aspects. Firstly, the performance of the vector graphics library is described, and an optimization algorithm is proposed to reduce the time complexity of the class library. Secondly, parallel coordinate system is used to calculate on an embedded GPU. Cloud electronic books in the vector graphics library has obtained a significant performance improvement by making use of the advantage of GPU in parallel computing. Thirdly, file conversion function of cloud e-books is passed on to the Hadoop cloud platform, by which cloud save energy consumption and computation time of the mobile equipment. And in order to optimize the Hadoop scheduler in the process of data location problem, location aware scheduler is applied to the proposed system. The experimental results show that, compared with the original VG Open class library, the performance of the cloud e-book system is improved by about 70%, and the computing time is reduced by about 60% compared with the continuous server platform.

electronic books; vector graphic library; GPU; cloud; location aware scheduler

2017-02-14；

2017-03-06。

張春燕(1979-)，女，江蘇豐縣人，碩士，講師，主要從事算法設計、控制理論與控制工程等方向的研究。

1671-4598(2017)08-0162-04

10.16526/j.cnki.11-4762/tp.2017.08.042

TP391

A