ACTA Scientiarum Naturalium Universitatis Pekinensis
高性能处理器中干扰公平队列I/O调度器
隋岩 叶嘉成 杨春† 佟冬
北京大学信息科学技术学院 北京100871; † 通信作者, E-mail: yangchun@mprc.pku.edu.cn
摘要 高性能处理器和系统需要高存储带宽和高效的外部I/O处理, 需要同时服务吞吐率密集应用和延迟敏感应用, 给多道程序计算机系统和多租户模式的超级计算机系统的公平性带来巨大的挑战。针对这两类应用共享SSD (solid-state disks)等可并发的存储设备问题, 开发一款基于队列的干扰公平(interference fair queueing, IFQ)调度器。在 Linux操作系统实现 IFQ 调度器, 并与其他调度器进行对比, 包括 Linux 的 CFQ调度器、STF调度器、MFAP的时间片流转调度器和MFAP的短时间片流转调度器。基于合成工作集、访问踪迹工作集和真实应用工作集的结果显示, IFQ调度器可以同时保证公平性和响应延迟。关键词 存储调度器; 干扰公平; 固态硬盘
北京大学学报(自然科学版)
(dominant resource fairness, DRF)分配策略, 对系统中的资源按照稀缺程度进行公平分配。基于DRF,人们进一步提出一些资源分配方法和公平策略[11–12]。
[13] [14] Dolev 等 和 Wang 等 将系统的性能瓶颈资源加
[15]入 DRF方法中予以考虑。Gutman 等 给出一个DRF分配的多项式时间分配算法。以上公平性研究都是针对吞吐率密集的满负荷(fully backlogged)用户, 但实际上很多延迟敏感用户并非永远满负荷地需求资源。这些用户在某些时刻会出现不需求资源的空闲阶段(idle time)。这种空闲主要来自两方面: 一方面是使用者交互过程中的思考时间(thinking time), 例如网页浏览器和游戏; 另一方面是对其他资源的阻塞式访问, 例如在用户启动和文件压缩等过程中, 用户应用顺序阻塞式地依次需求计算资源和存储资源。针对满负荷用户的公平性策略对非满负荷的用户是不公平的。非满负荷用户并不始终需求资源, 然而当他们有资源需求时, 依然需要和其他用户“公平”地共享资源。
为了解决这些问题, 研究者引入一个新的公平指标——干扰公平[16]。其基本想法是, 用户A对用户B的干扰, 应等同于用户B对用户A的干扰。为了在存储系统中有效且高效地保证干扰公平, 研究人员进一步提出MFAP[16], 根据各个用户访问存储资源的时间来评估消耗的资源量, 动态地分配各个用户竞争资源时的权重, 并通过不同尺寸时间片的轮转方法来实现。但是, 此方法的缺陷是, 一旦一个用户耗尽时间片, 必须等待下一个时间片的到来,会导致非常高的I/O请求响应延迟, 严重地影响用户体验。响应延迟保证通常基于公平队列方法实现, 广
[17]泛应用于网络 、存储I/O调度[18]和 GPU调度[19–20]等。此方法支持高细粒度的请求交错调度, 同时使用虚拟时间戳来保证公平性。当一个用户发出请求并得到服务时, 其虚拟时间戳会相应后移, 每次调度器都选择虚拟时间戳最靠前的用户进行服务。这种细粒度调度算法的主要问题是破坏了请求流的空间局部性, 因此会给硬盘驱动器(hard disk drive, HDD)带来额外的性能开销。幸运的是, 在固态硬盘(solid-state disk, SSD)上, 破坏请求流的空间局部性对系统性能影响不大。已有的MFAP资源消耗评估方法均针对HDD, 而 SSD设备有不同于HDD设备的独特性, 包括并行访问和性能不稳定等, 使得MFAP基于访问存储设备时间的评估资源消耗方
1006第56卷 第6期 2020年11月法并不适用于SSD设备。
针对以上问题, 本文开发一个基于队列的干扰公平(interference fair queueing, IFQ)调度器, 可以在SSD设备下同时保证请求的响应延迟和干扰公平。与现有的MFAP干扰公平调度器相比, IFQ调度器主要有两点改进: 使用队列调度算法, 可以有效地保证请求响应延迟; 使用访问数据量而不是访问时间来评估资源消耗, 可以支持SSD的并发访问和性能不稳定等特征。
1 研究动机1.1 SSD 设备的特性
我们从3个角度分析SSD设备的特性: 并发访问特性、随机访问特性和性能不稳定特性。
一个典型的SSD设备存在若干通道(channel),各通道内可能存在多个通路(plane)供数据包传输,因此 SSD的访问存在内置的并行性。我们通过一个实验来展示这种并行性。为了尽可能地降低干扰, 本文使用 direct I/O技术跳过操作系统的页缓存, 同时使用Linux 的 noop调度器来减少调度器带来的干扰。分别测试典型SSD设备下, 4和 128 KB数据的读操作性能, 结果见图1。可以看出, 随着并发读进程数量的提升, 系统吞吐率随之提升。
SSD设备还具有随机访问的特性, 与 HDD设备相比, SSD设备在服务随机访问请求流时, 只损失较少的性能。由于SSD设备控制器的复杂性, 其吞吐率并不恒定。例如, SSD设备的垃圾回收机制(garbage collection)使得其写入效率有非常大的变化, 即一段时间内有很高的写入速度, 之后速度会大幅度降低。
1.2时间片轮转调度和队列调度
很多 I/O调度器都基于时间片流转, 如 Linux
[21] [16]的 CFQ调度器 和 MFAP调度器 等。这些调度器给予不同的应用以不同大小的时间片, 之后依次调度这些时间片来服务应用请求。如果一个应用耗尽其时间片就需要等待其他应用, 直到再次轮转到它为止。在这段时间内, 应用的请求无法得到响应,影响用户体验, 如图2(a)所示。
为了解决这一问题, 一些调度器选择较短的时间片长度, 如图2(b)所示。这种方法只能缓解而不能解决该问题。更严重的是, 较短的时间片会导致更多的边界问题, 带来公平性的降低。也有一些调度器使用请求交错的轮转调度(图2 (c)), 但这种方法的问题是, 当一个应用的时间片耗尽后, 其请求延迟依然无法得到保证。
基于公平队列的调度能够在细粒度上保证公平性, 使得来自不同应用的请求被间隔地调度, 如图2(d)所示。这种细粒度的公平性有3个优势: 不需要等待时间片的轮转, 各个应用请求的响应延迟都可以得到保证; 支持多个应用同时发出请求, 从而充分地利用支持并发访问的设备(如SSD 等); 可以有效地解决 SSD设备访问性能变化的问题。
1.3长尾延迟问题
交互式的桌面应用和交互式的网络服务需要稳定的低响应延迟来吸引和维系用户群, 因此这些交互式场景对尾部延迟非常敏感[22–23]。通常认为, 长
99.9% tail delay and average delay of MFAP in different devices
从总体上看, 4个原则最终都可能归因于经济学或博弈论的公平问题, 它们符合常识的直觉。如DRF中讨论的, 策略最优和共享激励原则在商业化数据中心的环境下对保证不同付费用户之间的公平性非常重要。策略最优避免了严重的虚构特征的问题, 例如用户在他们的代码中加入无限循环, 人为地膨胀资源消耗, 以便提升其性能[5]。此外, 满足共享激励原则的任何策略还提供性能隔离, 因为它有效地保证了每个用户的最小分配性能不受其他用户需求的影响。性能单调是一个非常直观的公平性概念。多劳多得原则奖励客户消耗较少的资源, 如果用户消耗更少的资源, 将对系统贡献更多, 其他用户就可以共享更多资源, 并在性能方面受益。
2.2
Fig. 3
MFAP 调度算法
MFAP调度算法的核心问题是如何获得用户的统计信息。从直观上理解, MFAP需要在各个用户的工作集执行之前获得其详细信息, 以指导MFAP的调度, 这在真实环境中不现实, 也不可能。为了解决这一问题, MFAP使用一种推测式的调度算法,将整个系统的执行过程划分为若干等长的时间片段, 使用前一时间片段的信息指导下一时间片段的调度情况。
MFAP的干扰公平存储访问调度器面向HDD设备, 因此在没有RAID的情况下, MFAP模型中只有一个资源实例, 所以MFAP调度算法基于不同用户使用存储资源的时间来评估用户的资源消耗。
基于MFAP策略的不同权重, 我们分配不同的时间片给各个用户。例如, 如果检测到两个用户分
1008
干扰公平需要保证各个用户之间相互的干扰程度一致。简单地定量计算这些干扰, 会给n个用户共享资源的系统带来O(n2)的计算开销, 难以有效地实现。因此, 我们提出一种干扰公平分配策略,计算每个用户实际需求资源时的资源分配比率。当两个用户竞争资源时, 各自的分配比率与其消耗的资源成反比。例如, 与用户A相比, 用户B消耗两倍数量的资源, 则干扰公平分配策略在两个用户竞争资源时, 会按照 2:1的比例在用户A与B之间分配资源。
以一个包含6个资源实例(如6个处理器等)和3个用户的系统为例, 整个执行过程持续12个单位的时间, t=0执行过程开始, t=12执行过程结束。如果1个用户在1个时间单位内使用1个资源实例, 干扰公平分配策略则定义此用户消耗了1个单位的资源,即资源消耗=资源实例数×使用时间。因此, 有6×12 = 72个单位的资源消耗可供3个用户分配。假设用户A和B是延迟敏感用户, 用户C是吞吐率密集的, 则用户A在 t=0时开始需求资源, 并且在消耗 18个单位的资源后结束; 用户B在t=2时开始需求资源, 也在消耗18个单位的资源后结束; 用户C从 t=0 时开始一直需求资源。
计算得出用户A, B和C分别消耗18, 18和 36个单位的资源, 在干扰公平分配策略下, 3个用户分配资源的权重被分配为2:2:1。这一分配资源的权重只有在用户互相竞争使用资源时才有效, 因此并不意味着资源的分配比例永远是2:2:1, 或用户A获得40%的资源保留。
图 4为一个具体的分配示例。在时间段 t=[0, 2], 用户A与C竞争资源, 其资源分配比例为2:1。A分配4个资源实例, C分配两个。在这段时间内, A消耗8个单位的资源, C消耗4个单位。在t=2, B开始需求资源, 在时间段t=[2, 6.17], 用户A, B与C竞争资源, 资源分配比率为2:2:1, 因此A和B各自被分配2.4个资源实例, 而C被分配1.2个。在这
隋岩等 高性能处理器中干扰公平队列 I/O 调度器
北京大学学报(自然科学版)第56卷 第6期 2020年11月
对比MFAP与 IFQ的访问延迟可以发现, 从平均结果来看, 两种算法几乎没有区别, 但在延迟敏感应用访问存储延迟的长尾问题上, IFQ算法有明显的性能优势。
依然使用Umass的4个访问踪迹进行测试, 将访问踪迹模拟器与6个吞吐率密集读应用混合, 并测试读延迟的分布。最差情况的读延迟(99.9%的尾部延迟)结果如图8所示。可以看出, IFQ有效降低了最差情况的读延迟。
通过一个只包含读操作的Apache 测试, 对比MFAP, MFAP-S和 IFQ的请求延迟分布情况(图9),结果显示, IFQ方法可以有效地将读延迟分布压缩在一个较小的范围。
5总结
北京大学学报(自然科学版)第56卷 第6期 2020年11月
resource fairness: fair allocation of multiple resource types // Proceedings of the 8th USENIX conference on Networked systems design and implementation. Boston, 2011: 323–336 Elnably A, Du K, Varman P. Reward scheduling for QOS in cloud applications // 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Ottawa, 2012: 98–106 Elnably A, Wang H, Gulati A, et al. Efficient QOS for multi-tiered storage systems // USENIX Conference on Hot Topics in Storage & File Systems. Boston, 2012: 1–5 Dolev D, Feitelson D G, Halpern J Y, et al. No justified complaints: on fair sharing of multiple resources // Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Cambridge, 2012: 68–75 Wang H, Varman P. Balancing fairness and efficiency in tiered storage systems with bottleneck-aware allocation // Proceedings of the 12th USENIX Conference on File and Storage Technologies. Santa Clara, 2014: 229–242 Gutman A, Nisan N. Fair allocation without trade // Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-volume 2. Valencia, 2012: 719–728 Sui Yan, Yang Chun, Tong Dong, et al. MFAP: fair allocation between fully backlogged and non-fully backlogged applications // 2016 IEEE 34th International Conference on Computer Design. Phoenix, 2016: 576–583 Goyal P, Vin H M, Cheng H C. Start-time fair queueing: a scheduling algorithm for integrated services
1.北京大学软件与微电子学院, 北京 102600; 2. 德国慕尼黑工业大学, 慕尼黑† 通信作者, E-mail: caojian@ss.pku.edu.cn 80333;
针对高斯牛顿(Gauss-newton, GN)方法求解光束法平差模型时对初值准确度要求高、应用场景受限的问题, 提出基于拟牛顿法BFGS (Broyden-fletcher-goldfarb-shanno)修正的高斯牛顿算法——bfgs-gn 法。当高斯牛顿法的信息矩阵失去正定性后, 使用BFGS算法对法方程进行补充修正, 可从根本上消除高斯牛顿方法对初值敏感的数学缺陷。在数据集上的实验结果表明, BFGS-GN算法对不同类型的初值具有鲁棒性, 在初值较好的情况下, 所提方法与高斯牛顿法具有相同的精度和迭代效率; 在初值较差的情况下, 高斯牛顿方法因发散而失效, BFGS-GN算法仍可以收敛到较高的精度。关键词 光束法平差; 高斯牛顿; BFGS算法; 初值鲁棒
北京大学学报(自然科学版)第56卷 第6期 2020年11月
Dabeer 等[3]在 BA模型中融合路标点特征和车道线
[4]特征来优化自动驾驶车辆的姿态信息。Yang等提出点面BA模型来处理纹理缺乏场景中机器人的状态优化问题。Wu等[5]利用计算机并行计算方式,通过使用多核CPU 和 GPU进行算法加速。Zhao
[6]等 用影像间的视差角等角度信息代替直角坐标,降低雅克比矩阵(Jacobian matrix)的稀疏性。
3) 借助深度学习方法求解BA问题。这种方法往往需要基于数据特征进行精巧的设计来增强训练过程的收敛性, 且参数估计部分仍然采用传统方法,
[7]通用性不强。如Tang 等 设计 BA-NET, 通过学习到的量度特征来衡量重投影误差、优化场景深度和相机运动。
4) 直接研究BA模型的数值优化解。这是更加基础性的研究方向, 其目标是以各种质量的传感器采集的数据为基础, 提高求解方法的准确度和可拓展性。本文详细介绍此方向的研究。光束法平差模型的本质是非线性最小二乘求解问题, 通过多次迭代, 使3D路标点的重投影误差最小。在数值优化问题的诸多解法中, 牛顿法因具备二阶收敛速度而得到广泛的应用, 但在迭代求解的过程中, 牛顿法因计算复杂度过高而无法应用在数据量较大的BA模型求解中。这种情况下, 高斯牛顿方法通过忽略牛顿方法中产生的高阶导数, 极大地降低计算复杂度, 因此普遍应用于工程问题中。但是, 在忽略高阶项的同时也为高斯牛顿带来问题:当输入模型的初始值偏离真值较远时, 此方法极易发散, 无法满足收敛要求。
[8] LM (Levenberg-marquardt)方法 通过为高斯牛顿增加阻尼项来实现问题可解, 但由于阻尼的具体数值是通过不断尝试得到的, 因此很难获得精准的下降方向, 并导致迭代中的下降速度较慢。CG
[9] (Conjugate Gradient)方法 则是在高斯牛顿方法的数学模型基础上, 使用共轭梯度的方式求解方程,但由于信息矩阵的条件数较大, 会影响矩阵的收敛速度。CGBA方法[10]通过分解雅克比矩阵, 能够降低矩阵的条件数, 提高收敛速度, 但基于共轭梯度方式的解算方法通常无法收敛到更高精度的局部最小点。
[11] BFGS (Broyden-fletcher-goldfarb-shanno)方法是一种常见的拟牛顿方法, 具有良好的正定保持特性, 因此是数值优化领域常用的优化方法。SBFGSBA是利用BFGS的正定保持特性提出的一种新解
1014光束法平差是摄影测量和计算机视觉中的黄金定律, 其本质是关于相机姿态(ci)与三维点(pj)的最小二乘优化问题。相机姿态包含平移矩阵Ri和旋转矩阵Ti。通过三角化方法, 可以利用一对同名点获得一个空间中的三维路标点。在优化阶段, 需要把空间中的三维点通过相机模型重投影到影像上,形成坐标点 yˆij :
yˆ z ( c , p ), (1)
ij i j其中, 函数z(x)是把空间中的三维点投影成二维像点的投影方程。此时, 可以为所有观测到的图像特征点 yij和图像坐标空间中的预测点 yˆij 构建重投影误差方程:
r y ˆ y 。ij ij ij可以将BA问题描述为
(2)
止。对式(3)进行二阶泰勒展开:
gk )T 2 f k k其中, g f ( X ) 2 J r , 这里Jk表示雅克比矩阵T k k k (Jacobian matrix), 即观测方程对未知参数 X的一阶偏导矩阵。取 X=XK+1, 则式(4)可改写为
gk k f k 1 k k 1 k为了获得最小值点, 对式(5)右边求导,阶导数为零。此时求解出来的k ( X X k 1两次迭代之间的下降方向:
f
1) k f
f 2 k f k
k 1 k
k 1 k
)T
(19)
式(19)得到的 Bk+1是一个精确的矩阵, 可以更好地模拟 Hessian 矩阵, Ak+1是一个稠密矩阵, 通过式(8)获得。基于 BFGS 修正的 GN算法如下。算法 BFGS-GN已知: 相机位姿、路标点和特征点1. while 误差>T, 步长<100 do
T 2. if 正定 then kk
T 3.
k 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. end while 15. return result由于BA问题涉及的矩阵维数大、计算复杂度高, 会给稠密矩阵Ak+1的求解带来困难。然而, 低阶导数矩阵J J 具有稀疏性, 其结构如图1所示, T k 1 k 1黑色方块表示矩阵在该方块内有数值, 其余无色的区域表示矩阵在该处数值为 0。
本文借助 Hessian矩阵的低阶导数矩阵建立一个滤波器, 稀疏化高阶导数矩阵Ak+1。当低阶导数矩阵J J 中(i, j)位置的元素为零时, 滤波器中具T k 1 k 1有相同位置的元素也被设置为零。滤波矩阵 F
i ,j else if k 1
T k k A
k 1 1 1
then bfgs( A T k 1
else k 1 end if end if B gk k 1 k 1 1 k 1
TJ k 1 k 1 , , zk ) k 1
赵帅华等 基于 BFGS 修正的高斯牛顿光束法平差解算方法
米高的机载结构上, 拍摄的90幅航拍图像和37705个投影。第3个数据集是近景数据集, 图像来自公共机器人数据集合, 其中的 51652个投影使用开源软件L2SIFT提取。第4个数据集是从无人机(UAV)平台上采集的468幅分辨率为 5616×3744的大学校园图像。
提取高质量的图像投影点后, 使用基于相对姿态估计的算法, 计算两个相邻摄像机之间的相对姿态。在获得两个相邻摄像机的所有相对姿态后, 通过将相对姿态转换为第一摄像头坐标的方式, 将本地坐标参考系中的相机姿态初始化。然后, 通过交点算法实现3D点的初始化。将每个数据集整理为4个 txt文件, 分别是相机的内参文件、每张影像的位姿信息、每张影像的特征点文件和特征点对应的空间路标点文件。最后, 将摄像机姿态和路标点位置输入基于高斯牛顿法的光束法平差方法和基于BFGS修正的高斯牛顿方法中。统一使用优化参数计算得到的预测点和真实点间的均方误差(MSE)来衡量算法的准确性。
3.2实验结果与讨论
实验结果分为两种情况。如图2所示, 对于数据集 Dunhuan 和 Village, 高斯牛顿方法(GN)和本文提出的基于BFGS修正的高斯牛顿方法 (BFGSGN)具有相同的收敛精度和收敛速度。本文方法在中间迭代点处下降更快速(图2(a)), 图2(b)中两种方法取得相同的收敛效果。说明在数据集初值较好的情况下, 两种方法均能很好地模拟真实Hessian 矩阵, 达到较好的收敛效果。
如图3所示, 对于数据集Magala和 College, 使用高斯牛顿方法优化相机姿态和3D点坐标时, 迭代过程经过振荡后, 最终的结果出现发散。BFGSGN方法仍然可以将数据优化到较高的精度。从图3 可以看出, 高斯牛顿方法出现发散的原因在于,
Overall parameters of the test datasets
北京大学学报(自然科学版)第56卷 第6期 2020年11月
不弱于高斯牛顿的迭代效率和收敛精度。对于拥有较差初值的数据, BFGS-GN方法可以顺利地收敛,解决了基于高斯牛顿的光束法平差方法因对初值敏感而应用场景受限的问题。
4结语
高斯牛顿法是光束法平差中的重要方法, 因收敛精度高和超线性收敛速度而得到广泛应用。但是, 高斯牛顿法由于理论上的缺陷, 使得其对相机姿态和空间路标点的初始值具有较高要求, 当初始值远离真值时, 算法极容易发散, 丧失优化功能。本文通过对高斯牛顿方法初值敏感原因进行探索,提出基于 BFGS算法修正的高斯牛顿方法(BFGSGN方法)。在每次迭代前, BFGS-GN方法会对高斯牛顿信息矩阵的正定性进行判断, 在不满足正定规则时, 对高斯牛顿的目标方程进行修正。
实验结果表明, 对于高斯牛顿法不能实现收敛的数据集, BFGS-GN算法可以正常地收敛, 并获得较高收敛精度; 对于高斯牛顿法可以收敛的数据集, BFGS-GN算法同样可以获得相同的精度和迭代效率。因此, 本文提出的方法可以很好地解决高斯牛顿方法对于初值敏感的问题, 在保证收敛精度的前提下, 可以增加算法的鲁棒性, 有效地拓展应用场景。[10]