Page 337 - 《软件学报》2020年第10期

高珑 等:并行帧缓存设备:基于多核 CPU 的 Xorg 并行显示优化 3313

3 帧缓存并行显示优化算法

为了实现帧缓存设备的并行化,并最大程度地避免不同子线程之间的数据相关性,我们对屏幕进行划分,划
分后的每一块子屏幕对应一个子线程,仅绘制位于该子屏幕中的图形,如图 5 所示.本文中仅针对矩形填充操作
SolidFill 进行了实现,其他图形绘制操作的实现与此类似.
沿 x 轴划分为 S x 个
为每一个子屏幕 D k
j=1,2,Sy 创建一个子线程 T k 子屏幕=1,2,…,S x

Sy 个子屏幕 D k〈i,j〉,k=S x(j−1)+i

轴划分为 P ul R P lr

y
沿 绘制中的矩形
Fig.5 Drawable screen partition
图 5 Drawable 分屏
3.1 屏幕划分

本文第 1.3 节中已经介绍过可绘制对象 Drawable,X 中的每一个 Drawable 都对应屏幕上某一块矩形可绘
制区域,即窗口对象 Window 或者位图对象 Pixmap 在屏幕上所占据的区域.图 5 中的最大矩形就代表某
Drawable 对应的可绘制区域,由横坐标 x 轴和纵坐标 y 轴标示.一般使用矩形的左上顶点 P ul 和右下顶点 P lr 的
像素坐标值即可唯一确定该矩形的位置和大小.
如图 5 所示,在并行帧缓存算法中,将帧缓存设备上的每一个 Drawable 对象对应的矩形屏幕按照 x 轴和 y
轴分别平均分成 S x 和 S y 份,这样每一个 Drawable 对象对应的矩形屏幕就被均分成互不相交的 S x ⋅S y 个子屏幕,
每一个子屏幕用 D k 〈i,j〉来表示,其中,i 和 j 分别代表 x 轴和 y 轴上从 1 开始的区间编号,其中,k=S x (j−1)+i,易知 k
的范围 1≤k≤S x ⋅S y .根据子屏幕的划分方法,有:
分屏规则.给定矩形 R 的左上顶点 P ul 以及子屏幕 D,R⊂D,当且仅当 P ul ∈D.
也就是说:仅当矩形的左上顶点 P ul 属于某个子屏幕 D 时,该矩形才属于该子屏幕 D.我们为所有的子屏幕
D k 创建一个子线程 T k ,将所有属于子屏幕 D k 的矩形 R⊂D k 的填充绘制任务交给与子屏幕 D k 绑定的子线程 T k
完成.对于右下顶点 P lr 可能超出其所在子屏幕 D 的矩形,我们将在第 5.1 节中给出讨论.
3.2 私有任务队列

并行帧缓存设备算法参照单生产者多消费者模型 [37] 实现.在经典的生产者消费者模型中仍然存在一些竞
争冲突和遍历开销等问题.为了改进这些问题,并行帧缓存设备算法中的每个消费者都采用了独立的私有任务
队列作为缓冲区,如图 6(b)所示.矩形绘制任务将由生产者按照分屏规则分发到消费者各自的私有队列中,再由
消费者从各自的私有队列中取出完成.由于分屏规则计算量不大,所以生产者分配引入的串行开销在可以接受
的范围内.
并行帧缓存设备算法如图 6(b)所示,T 0 代表生产者主线程,T k (1≤k≤S x ⋅S y )代表绑定子屏幕 D k (1≤k≤S x ⋅S y )
的消费者子线程.生产者算法如图 7 所示,消费者算法如图 8 所示,生产者和消费者公用的处理子函数 Process(q)
如图 9 所示.
图 6(b)中就绪队列 Q k 长度 N 以及运行队列 q k 长度 M,实际上已成为并行帧缓存设备算法的两个主要参数,
在第 4 节的实验中可以看到不同的 M 和 N 的取值对于算法性能的影响.