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

3318 Journal of Software 软件学报 Vol.31, No.10, October 2020

程同步和互斥的相对开销所占比例逐步降低,使得加速比曲线更加趋近线性.
但曲线也并非一直增长,大约在 log 2 (N)=15 附近取得极值.考虑到本实验中 CPU 仅有 4 物理核心,所以创造
出多于 4 个物理核心的线程后,反而会带来子线程等待和切换的开销,所以再增加分屏数目或者增加队列长度
应当也不能再持续提高加速比,可以近似地认为该算法在参数 M=1024,log 2 (N)=20,S x ⋅S y =2×3 时取得加速比极大
值 2.06.此时,x11perf 的得分约为 935 333.
假设算法中串行执行的部分为 a,因为本实验中可同时并行执行的线程最多为 4 个,根据阿姆达尔定律 [40] ,
理想状态下的加速比应当为公式(1)中等号左边的多项式.考虑到实际测试时的各种开销,那么实际测试所得极
大值 2.06 应满足:
1
> 2.06 (1)
a + (1 a− )/ 4
所以可以推出 a<0.3139.所以,根据极限状态下的阿姆达尔定律,本算法的极限加速比将是串行部分比例 a
的倒数,即:
1
> 3.18 (2)
a
上述分析可以得出结论:通过不断增加 CPU 的核心数目,该算法加速比的极限值至少可以达到 3.18;从另一
个方面说,该算法仍然还有改进空间,例如将主线程 T 0 用于分配任务的串行计算时间以进一步优化压缩或者并
行化.

5 未来的工作

5.1 顺序一致性
在本文算法中,如图 20 所示,如果矩形 R 的右下顶点 P lr 超出所属子屏幕的范围,可能导致与其他子屏幕中
的矩形 R′有重叠.由于 R 和 R′分属不同的子线程绘制,如果由于线程调度的原因,最终导致较早请求绘制的矩形
遮挡了较晚请求绘制的矩形,可能会对用户交互产生影响.下一步将会在考虑顺序一致性的基础上对算法进行
改进,例如改进矩形划分算法,将同时出现在屏幕上的所有矩形动态划分成互不相交的若干组,以避免不同线程
之间的相互干扰.

R

P lr R′

绘制中的矩形
Fig.20 Sequence consistency
图 20 顺序一致性
5.2 子线程间的负载均衡
本文已经研究了主子线程间的负载均衡,可以避免出现单个子线程负担过重,但无法防止出现单个子线程
负载较低的情况,这种情况下可能会影响算法的并行加速效果.虽然此时可以通过操作系统调度其他线程运行,
但是如果一开始就把任务更加平均地分配给所有的子线程,那么将会有更好的加速效果.但从另外一个角度来
讲,更精确的任务分配算法也会带来更大的开销,这需要进一步权衡和研究.

5.3 单桌面多用户
同一个 X 图形服务器,仅允许一个用户(每个用户使用一对鼠标键盘)使用.X 图形服务器的 XInput 子系统