基于Open VG云电子书系统的多级优化框架设计

张春燕，于 丽

(新疆警察学院 信息安全工程系，乌鲁木齐 830000)

基于Open VG云电子书系统的多级优化框架设计

张春燕，于 丽

(新疆警察学院 信息安全工程系，乌鲁木齐 830000)

针对电子书应用存在的文件格式、性能效率低下和图像失真等问题，设计了一种应用于云电子书系统的多级优化框架，优化框架主要体现在如下三个方面；第一，对向量图形类库的性能进行描述，并提出了一种优化算法，减少了类库的时间复杂度;第二，在嵌入式GPU上并行进行坐标系统的计算;利用GPU在并行计算方面的优势，云电子书在向量图形类库方面获取了显著的性能提升;第三，云电子书将文件转化功能转嫁给Hadoop云平台，节省了移动设备的能量消耗和计算时间。同时为了对Hadoop调度过程中的数据位置问题进行优化，将位置感知调度器运用到提出的系统;实验结果表明：云电子书系统与最初的Open VG类库相比，性能提升了约70%，而且云电子书系统与连续服务器平台相比，计算时间减小了约60%。

电子书；向量图形类库；GPU；云；位置感知调度器

0 引言

电子书[1]主要由数字形式的文本和图像构成，可在计算机或其他电子设备上观看。最近十多年，许多电子书应用程序可以在移动设备上运行，而且出现了很多电子书应用程序。但是，这些应用程序没有得到广泛应用，这是因为电子书应用在移动设备上运行存在一些缺陷。其最大问题是图像失真，当用户调节图像尺寸时，电子书的内容和图像可能发生失真[2]，这是因为电子书上显示的大多数图像都是位图类型的图形。针对该问题，可缩放向量图像(Scalable Vector Graphics, SVG)技术[3]是解决图像失真的有效途径。

近些年，一些工业制造商已经对电子书应用进行了广泛的研究。大部分研究工作关注的是电子书应用[4]、安全[5-6]、和平台标准化[7]。也有一些研究者[8-9]在移动操作系统上采用SVG技术，这些移动操作系统有Android、微软的Windows Phone(现在已经很少见到Windows操作系统的智能手机)和苹果的iOS。文献[10-11]通过修改光栅化的处理过程，利用双扫描线对渲染过程进行加速，进而优化了Open VG[3]类库的性能，其主要关注于渲染和光栅化过程中的算法优化问题。但是，在Open VG[3]类库中路径转化是另外一个计算强度函数，而Android VG[12]是一种三角划分过程。

一般情况下，向量图形技术不仅可以解决图像失真问题，而且还可以很好地解决电子书中文件格式统一的问题。但是，将向量图形技术引入到电子书应用中后，产生了另外两个问题：

1)向量图形图像在电子书应用中所表现出的性能低于一张由位图进行渲染的图像，这是因为向量图形技术需要花费大量的时间处理路径的技术和绘制。

2)向量图形图像的文件尺寸与以位图格式存储的图像相比要大很多，这是因为向量信息需要复杂的描述。

为了解决上述问题，本文提出了一种优化电子书应用，即将嵌入式GPU[13]和云平台的计算资源进行了有效的整合。将Open VG[3]类库和Android系统进行了整合，并且通过嵌入式GPU加速优化了Android系统上的向量图形类库。其突出的优点有：

1)通过向量图形库解决了电子书应用中存在的图像失真问题；

2)云电子书可以将向量图形库的时间复杂度从O(n2)减少到O(n*logn)，因此通过修改图形三角划分算法以及将路径计算任务转嫁到嵌入式GPU；

3)云电子书在Hadoop平台[14]上开发并执行了一个位置感知调度器，该调度器不仅提高了向量图形转化器的性能，而且提高了Hadoop平台上的数据命中率。

1 云电子书的优化

本节介绍云电子书系统中的系统类库优化过程，即基于Open VG[3]规范和源代码开发出了优化类库。

为了识别和克服瓶颈，对计算密集型阶段进行了性能分析，这里的计算密集型阶段指的是：Open VG流程中的扁平化、转化、三角划分和光栅化。为了对性能进行分析，将性能分析函数置入Open VG类库。三个广为人知的简单应用包括：Tiger VG、Apple VG和Star VG，这三个应用在改进的向量图形类库中执行。其中，三角划分是Open VG类库中的性能瓶颈。三角划分过程含有许多图形计算任务，如计算顶点的坐标，并将整个图形分割成许多三角形。因此，优化三角划分处理过程是向量图形类库中最重要的问题。

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

加速三角划分算法主要聚焦于对计算步骤的改进以及减少三角划分算法的时间复杂度。通过将三角划分步骤简化为绘画步骤，进而简化了计算步骤。

Shiva VG的计算过程中存在三个步骤。第一个步骤是计算模板缓存中的绘制图形，然后在帧缓存中寻找绘制区域以添加颜料。Android VG在三角划分和帧缓存间存在一个更加复杂的流程，Android VG对平面图形进行了三角划分，并且向深度缓存中输出了各部分的划分图形。深度缓存步骤结束之后，Android VG就具有了与Shiva VG相同的数据流。与上述向量图形类库不同的是，云电子书已经对计算步骤进行了简化。于是云电子书在三角划分步骤中遵循相同的步骤，但是，云电子书直接输出了与绘制设置相关的划分信息给帧缓存。这样，云电子书的计算步骤降低了时间消耗，这是因为对三角划分步骤进行了改进，这里的时间消耗是指不同缓存间数据移动所产生的消耗。

向量图形类库中原始的三角划分算法的时间复杂度为O(n2)，其中n表示顶点的个数。如果输入的资源是一幅复杂的照片，比如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)，因此，预处理阶段不能增加整个三角划分过程的时间复杂度。预处理阶段之后，输入的多边形已经转化成多个单调多边形块。在多个单调多边形上执行这种单调三角划分算法可以将三角划分阶段的时间复杂度从O(n2)降低为O(m*nlogn)，其中m表示G中单调多边形的个数，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 并行计算框架的优化

为了充分利用移动设备上的计算资源，本文提出了一种采用异构计算机机制的高性能框架，由于目前大多数移动设备都配备一个嵌入式GPU单元，因此在GPU单元的协助下，这些应用的性能有所提高。一个GPU含有许多ALU单元，这些ALU单元能够并行执行程序，因此GPU在运行计算密集型应用时速度快于CPU。根据GPU的特性，通过渲染脚本编程接口将移动设备平台上的三角划分计算任务转嫁到嵌入式GPU内进行处理。图1中给出了云电子书系统中转嫁机制的框架。

图1 向量图形类库的并行框架

为了充分利用移动设备中的计算单元，转嫁机制将三角划分阶段的任务划分成4个子任务，并且在微型处理器单元(micro processing unit, MPU)和GPU上单独执行各个子任务。GPU执行的任务属于计算密集型且高并行处理的任务，MPU不能并行处理任务。这种机制不但利用了GPU的优势，而且也没有浪费MPU的计算资源。

2 云电子书的部署

云平台在云电子书系统中所扮演的角色是提供扩展资源，云平台由三个组件构成：Hadoop分布式文件系统[14](Hadoop Distributed File System, HDFS)、向量图形转化器程序和位置感知工作调度算法。由于云的分布式环境，本文提出了一种位置感知工作调度算法，并且将这种算法应用到云平台中，进而减少计算节点和数据节点间进行数据传输的时间复杂度。利用基于云电子书系统的优化云端可以解决移动设备中有限资源所引起的问题。

2.1 参数描述

位置感知调度器中的参数包括数据节点、数据的权重、输入数据的副本个数和每个节点上映射时隙点的个数。表1中给出了位置感知调度器中所有参数的简单定义。

表1 位置感知调度器中定义的参数

位置感知调度器主要关注“稀有资源”的配置。将数据节点称为稀有资源，数据节点中含有一些数据，这些资源相对缺乏，这是因为数据节点的大部分都属于所需数据，一些具有高优先级的任务占据这些数据节点。为了对稀有资源进行区分，将参数W(nj,Tdo)作为主要因子以测量位置感知调度器中数据节点的稀有程度。一个数据节点具有最小值的W(nj,Tdo)，即这个数据节点不属于稀有资源，因此调度器可以向这个数据节点派发计算任务。权重公式的表达式如式(1)所示：

(1)

其中：

(2)

式(1)中，参数W(nj,Tdo)表示节点nj中可利用数据di与云平台中可利用数据w(di)总和之间的比值。因此，当节点nj中含有一些数据时，参数W(nj,Tdo)的值会增加，且这些数据仅存在于节点nj中。

2.2 位置感知调度算法

本文在工作调度器中采用位置感知调度器。在分配任务之前，工作跟踪器利用式(1)计算出每个节点上数据干扰的权重，每个节点利用空时隙点执行该任务。然后，工作跟踪器挑选出具有最小数据干扰权重的节点，并将任务分派给这个数据节点的任务跟踪器序列。算法3中给出了位置感知算法详细的步骤。调度器不仅可以计算数据干扰的权重，进而以一种简单的方式避免稀有资源分配，而且通过引入数据干扰权重概念增强了Map Reduce框架中的数据位置。因此，位置感知调度器减少了数据传输过程中的网络延迟引起的开销。另外，利用位置感知调度器还可以提高云平台的性能。

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

输入：一个用户任务t和N中的元数据

输出：将t分派给nt

1 计算N中每个数据节点的权重值w(di)；

2 按照升序对数据节点的权重进行排序；

3 从N挑选出第一个具有最小数据干扰权重值的节点nfirst；

4 将任务j分派给节点nfirst中的任务序列。

3 实验结果与分析

本节对Android系统和云平台上执行云电子书应用的实验结果进行了讨论。为了展现出云电子书性能的改善水平，本文在云电子书上运行了一系列的位图格式文件，并且与其它方法进行了对比实验。向量图形类库方法指的是Open VG[3]、Android VG[12]，Hadoop调度器的方法中包括先到先服务准则、文献[15]提出的公平调度器[15]和提出的位置感知调度器。实验结果显示云电子书系统能够提升73%的Open VG类库的性能，减小50%～75%文件转化过程中的时间消耗，并且提高云平台中10%的数据命中概率。

3.1 实验环境

将实验环境划分为两个：一个是手持设备中的向量图形类库；另一个是Hadoop平台中的向量图形转化器。手持设备环境中，本文将云电子书安装在一个Google Nexus 10平台上。云电子书支持版本为2.3及其之后的Android系统，因此可以将云电子书安装在大多数的手持设备上。此外，移动端通过网络与云平台进行通信，因此，无线网络频段中的干扰不能对移动端的性能产生影响。

云平台主要由两个部分构成：第一个部分是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的各阶段执行时间 ms

Apple VG的实验结果如表4所示，Apple VG的三角划分步骤性能也提升较大，Apple VG的执行时间减少约60%。另一方面，虽然Star VG的结果如表5所示，虽然含有许多较轻权重的计算任务，但性能依然有所提高。

表4 Apple VG的各阶段执行时间 ms

表5 Star VG的各阶段执行时间 ms

云电子书在Star VG和Apple VG的实验中明显的提升这两种实验环境的性能。与之相反的是，Star VG的性能并没有提升很多，这是因为Tiger VG和Apple VG是复杂的2D动画片。云电子书通过优化算法和嵌入式GPU计算器能够减少复杂2D动画片的执行时间。另一方面，Star VG是一个简单的2D图形，这个图形不需要多余的计算能力。

3.3 云平台的性能

云平台的实验结果在每个阶段分别解释对增强方法效果的影响。首先，云电子书采用图像群组框架的并行方法，将电子书中所有的位图格式图像划分为多个群组，然后并行地在Hadoop平台上对位图格式图像组进行转化。本文将云电子书和其它方法进行了性能增强方面的比较，方法包括具有顺序处理的服务器和常规的Hadoop平台。图2中给出了提出方法所获取的性能增强结果，以及总的执行时间。图2中，将实验任务从2500设置为100000。当任务的个数增加时，云电子书获取了显著的性能提升。当任务的个数达到100000时，可获得55%的性能提升。

图2 服务器端云电子书的性能

为了展现本文提出工作调度器的性能，在两个不同的分布中设置了三个不同的负载。实验中，将每分钟处理15000个任务设置为高，将每分钟处理10000个任务设置为中，将每分钟处理5000个任务设置为低。此外，利用一个结合正太分布和泊松分布的仿真客户端安装任务生成器以生成实验负载。在服务器端对所提出的调度器进行了仿真实验。

表6给出了当工作跟踪器采用不同调度算法时工作跟踪器中遗漏计数个数(高度负载)。当跟踪器采用本文所提出的算法作为其调度器时，工作跟踪器内遗漏计数的个数可以减少150～300。表7给出了运行中型负载情况下不同调度器的工作跟踪器的遗漏比例。如表7所示，本文提出方法对应的数据遗漏比率性能与先进先出(first in first out, FIFO)调度器相比要高出10%。类似地，如图8所示，在较轻负载情况下，提出的方法也可以减少10%的数据遗漏比率。

表6 服务器端调度算法的数据遗漏比率(高度负载) %

表7 服务器端调度算法的数据遗漏比率(中度负载) %

表8 服务器端调度算法的数据遗漏比率(轻度负载) %

4 结论

本文提出了一种综合电子书系统，即Android系统上的云电子书系统，该系统可提供文件转化、数据归档和向量图像表示功能。为了有效地优化云电子书系统，提出了一种应用于云电子书系统的多级别优化框架。在图形描述、计算性能等多个方面进行了优化。与其他几种系统和类库相比，明显提升了整体性能。

由于许多编程人员利用GPU计算的优势来提高嵌入式环境中系统类库的性能，而Open VG是一种性能较差的嵌入平台实现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] 杨志刚, 张新兴, 庞弘燊. 电子书阅读器在国外图书馆的应用现状及存在问题[J]. 大学图书馆学报, 2011, 29(4): 11-17.

[6] 焦灵芝. 亚马逊电子书平台研究[D]. 南京:南京大学, 2013.

[7] 王 芳. 电子书标准化建设的目的、现状与对策探讨[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] 姚卫国, 张东波. 基于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