PerfIso: Performance Isolation for Commercial Latency-Sensitive Services

论文原址:https://www.usenix.org/system/files/conference/atc18/atc18-iorgulescu.pdf

演讲PPT:https://www.usenix.org/sites/default/files/conference/protected-files/atc18_slides_iorgulescu.pdf

这是微软在18年 usenix 会议上公开的一篇混部论文。这也是微软在混部这个领域公开的为数不多的论文之一。论文中描述了bing业务(非公有云)如何通过在离线混部 + CPU Blind Isolation 这个技术,将 indexserver 集群的利用率从21%提升到66%的过程

其中最关键的,还是 CPU Blind Isolation 这个技术,很有意思。


约束最优化:lagrange 对偶函数

学SVM的时候你会经常听到拉格朗日对偶。拉格朗日对偶是凸优化问题中比较常见的一个手段,关于凸优化,强烈建议Boyd的《凸优化》这本书,总结的很好

lagrange 对偶的基本思想,是将原目标函数,通过对其约束条件的加权求和,变成一个广义的目标函数。从而将一个M个变量N个约束的目标函数转换成一个M+N个变量的目标函数,再得到这个函数的对偶函数

这个对偶函数非常有用,因为他有几个重要性质:

  1. 无论原始问题是不是凸的,对偶问题一定是凸的,可以证明
  2. 对偶问题给出了原始问题的一个下界,可以证明
  3. 当满足一定条件时,对偶问题的解和原问题的解是等价的,可以证明

SVM 支持向量机

参考 mit 课程:https://web.mit.edu/6.034/wwwbob/svm.pdf

SVM 是机器学习领域非常流行的一个分类算法。他的前身其实就是感知机,想了解感知机原理的可以简单看我之前写的文章

传统感知机是有很多局限性的问题的,比如解决不了线性不可分的问题,比如泛化能力不强因为你可以找到N个解,但是不知道哪一个是最好的。SVM 就能很好的解决这些问题。

1. 支持向量

搞清楚什么是支持向量是了解SVM的前提。但是这里只能抽象的讲解,了解后面的内容,会加深你对支持向量的理解

在一个分类问题里,我们可能会有多个解,比如:

但是取哪个是最好的呢?直觉告诉我们,选能让样本分割的最远的超平面,这个就是 SVM 的做法,最大间隔化(后面会讲形式化的定义和推导)。SVM使用两个间隔最大的超平面,将所有数据完美分割在两边。

所以数学上,只需要一个超平面 + 间隔,就能形成一个决策边界,那些依附在决策边界上的点,就叫支持向量。为什么要给这些点起一个专有的名词?因为定义这个超平面只需要用到这些点,而其他远距离的点都是多余的。所以通常在一个2维空间上,最少只需要3个点,就能定义这个超平面


理解感知机模型

感知机是一种很传统和经典的分类算法了,现在机器学习的书基本上也很少详细讲了,大多还会简单介绍一下。看 ng 的机器学习课程,在讲 SVM 支持向量机的时候,从逻辑回归的代价函数直接修改到SVM的代价函数,实在难以理解,逻辑回归和SVM之间的关系和区别,还得好好想想

感知机模型有自身的局限性,它只能做线性分类。如果数据不是线性可分的,那还真没办法。但是了解感知机模型,对后面学习SVM很有帮助的

1. 感知机模型

感知机只能用来做线性分类,所谓线性分类是说,假设我们有一堆样本数据,我们必须找到一条线或者一个超平面,能把这堆样本划分到线的两边

preview

用数学的语言来说,如果我们有m个样本,每个样本对应于n维特征和一个二元类别输出,如下:


用 ReLU 整流单元逼近非线性神经网络

刚学习深度学习的时候,在网上曾经看过很多资料,始终搞不懂,为什么大家都说神经网络为什么能够无限逼近任意连续函数。大家普遍认为,理论上只要神经元足够多,神经网络足够大,就可以实现

后来知乎有个人写了偏文章解释了一下,有兴趣的可以移步这里:https://zhuanlan.zhihu.com/p/25590725

我困惑的根源在于:

  1. 神经网络说白了就是一个矩阵,神经元之间的链接就是各种矩阵运算
  2. 有很多激活函数是“线性”的,比如ReLU及其各种变种

当然,有些人认为ReLU是非线性激活函数,其实也没有错。但是我个人理解,叫分段线性函数,更合适一些。

那么问题来了,如果一个神经网络中,全部使用线性单元,无论经过多少次矩阵运算,最终训练出来的网络,不还是一个线性函数吗?


K-均值聚类

本文摘自笔记:http://ai-start.com/ml2014/html/week8.html

参考视频: 13 – 2 – K-Means Algorithm (13 min).mkv

K-均值是最普及的聚类算法,算法接受一个未标记的数据集,然后将数据聚类成不同的组。

1)算法的基本过程

K-均值是一个迭代算法,假设我们想要将数据聚类成n个组,其方法为:

  1. 首先选择 K 个随机的点,称为聚类中心cluster centroids
  2. 对于数据集中的每一个数据,按照距离 K 个中心点的距离,将其与距离最近的中心点关联起来,与同一个中心点关联的所有点聚成一类
  3. 计算每一个组的平均值
  4. 将该组所关联的中心点移动到平均值的位置

重复步骤2-4直至中心点不再变化


无监督学习

前面我们学习的,回归和分类,都是监督学习中最经典的学习方法。

监督学习是从有标记的训练数据中推导出预测函数。有标记的训练数据是指每个训练实例都包括输入和期望的输出。一句话:给定数据,预测标签。

而无监督学习则是从无标记的训练数据中推断结论。最典型的无监督学习就是聚类分析,它可以在探索性数据分析阶段用于发现隐藏的模式或者对数据进行分组。一句话:给定数据,寻找隐藏的结构。

比如在分类问题中:

假设我们有一堆样本数据,并且知道每个数据的所属分类,那么通过监督学习,我们就能知道数据的特征和分类之间的关系,并以此建立数学模型。当输入一个新的数据时,我们就能够按照模型预测分类的结果。这就是监督学习

但是更多时候,我们可能是有一堆样本数据,我们甚至不知道这些数据到底可以分成几类。通过无监督学习算法,我们甚至可以自学的尝试为这堆数据分类,并找到其中隐藏的数学模型。这个就是无监督学习

无监督学习算法的应用场景,在生活中非常常见,Ng 在 13 – 1 – Unsupervised Learning_ Introduction (3 min).mkv 中举了一些例子


深度学习中的交叉验证

第一次看 ng 斯坦福机器学习这门课程的时候,就没看懂交叉验证是怎么回事。

1. 模型选择和交叉验证集

参考视频: 10 – 3 – Model Selection and Train_Validation_Test Sets (12 min).mkv

ng 在讲交叉验证的时候,是这么举例的

假设我们要在10个不同次数的二项式模型之间进行选择:

显然越高次数的多项式模型越能够适应我们的训练数据集,但是适应训练数据集并不代表着能推广至一般情况,我们应该选择一个更能适应一般情况的模型。我们需要使用交叉验证集来帮助选择模型。 即:使用60%的数据作为训练集,使用 20%的数据作为交叉验证集,使用20%的数据作为测试集


Top Down Analysis – Performance Tuning

https://indico.cern.ch/event/280897/contributions/1628888/attachments/515367/711139/Top_Down_for_CERN_2nd_workshop_-_Ahmad_Yasin.pdf

https://agenda.infn.it/event/17237/contributions/35958/attachments/67698/83296/ArchitectureNew_ESC19.pdf

这是2篇非常经典的微架构层面的性能分析相关的材料,作者提出了一套自顶向下的性能分析方法论

微架构的性能分析是一件很困难的事情:

  1. 复杂的微架构
  2. 应用/负载的多样性
  3. 难以处理的数据
  4. 时间、资源、优先级等其他更要命的约束

自顶向下分析法的目的就是要从顶层问题出发,层层剖解,直至找到瓶颈所在


cgroup 进程调度之 Borrowed-virtual-time (BVT) scheduling

规避 CFS 的非公平性问题(睡眠补偿等等),99年发表论文,15年heracles论文重新对 bvt 做了改进,从论文作者的名字,我扒到了对应的源码,这哥们把源码放到gist上了

1. cfs 睡眠补偿机制

在讲bvt之前,有必要先介绍一下 cfs 的睡眠补偿机制
cfs 调度器的目标是公平,cfs 希望每个进程得到调度的机会是一样的,这个“机会”是用 vruntime 来衡量的
但是如果一个进程一直在睡眠,那么它的 vruntime 是非常小的,当睡眠中的进程被唤醒时,基于 CFS 的调度逻辑,会一直持续运行当前进程,直到 vruntime 不是最小的时候,才会选择下一个进程来调度。
内核为了解决 sleep 进程获得过长时间的问题,增加了一个阈值限制,当进程被唤醒时,取当前运行队列的最小vruntime,并 + 上一个偏移量,这个偏移量默认是 1/2 个调度周期,12ms