2021年操作系统设计与实现研讨会（OSDI）有哪些值得关注的文章？ 第1页

OSDI 2021是改为annual后的第一届会议，因为时间的仓促和与其他会议投稿时间的冲突，今年OSDI应该算是一个小年，投稿数量和社区关注度都打了一个折扣，但是还是有不少亮眼的工作，聊几个个人感兴趣的工作，抛砖引玉，如有谬误非常感谢纠正！

Pollux: Co-adaptive Cluster Scheduling for Goodput-Optimized Deep Learning

引起了非常多讨论的一篇工作，也是best paper之一，核心的设计原则我想可以从两方面来阐述：

1. 之前的分布式深度学习集群调度中常常分为硬件资源和用户任务两个层次，在分配GPU时由于任务的复杂以及黑盒的特性并不清楚怎样分配可以达到最佳的效率，而用户任务中learning rate与batch size两个超参数又依赖于对于data parallelism的了解来达到最佳的效果。通常的实践中依赖于用户自己设定超参数以及对于资源的需求，但是用户不可能对于不同的任务与不同的硬件都有设定好参数的能力。对于scheduler而言，本来是耦合的部件却因为现行的抽象设计只能在两个层面分开追求性能的优化，在硬件资源方面，寻找合适数量的GPU来达到性价比最高的throughput的想法被很多之前的工作采用，而在超参数的设定方面，为了加快模型的收敛，之前的工作既有聚焦于算法侧（各种新的optimizer）的也有系统侧的（比如去年OSDI上的KongFu）。Pollux提出goodput的概念，结合了throughput与模型收敛速率两个指标，是一种系统研究中很经典的全局优化的思路，近在去年OSDI上就有思路相近的工作。
2. 文章更大的篇幅在构建一个cost model作为协同优化的指导，使得paper看起来有一些ML的味道。虽然cost model是一个很自然的想法，但是大多时候都会被诟病不够通用和不够准确，这也使得很多人包括我自己其实对于这种方法有先入为主的排斥。Pollux能做到如此准确和有效的原因，除了简明合理的formulation以外，我想还是依赖了一个很强有力的assumption，也就是deep learning训练的任务在给定的独占计算资源下，性能表现非常deterministic。去年OSDI中ClockWork和Rammer也利用了这一点（只是举两个自己熟悉的例子，其实还有很多），但都只是基于此做了简单的heuristic，一部分原因可能是这两个工作的优化目标很难像Pollux这样formulate，更重要的原因可能还是大家习惯的思考问题角度不一样，邢波老师在ML和system结合上之前已经不少类似的尝试，这次的成功显然也不是偶然。

一个拓展的讨论可能是，这个工作是否能够启发我们去用类似的思路formulate更多的系统性能优化问题？这个可能也是拿best paper的主要原因，很可惜OSDI没有线下开，不然应该会有很有启发性的讨论。

PET: Optimizing Tensor Programs with Partially Equivalent Transformations and Automated Corrections

是基于TASO的一个后续工作，将graph transformation的规则从完全数学等价拓展成了部分等价，然后引入了一个高效的纠错机制。通过扩大了图优化的搜索空间，进一步地提升了性能增益。核心的想法是对于多个线性算子组成的一个子图，其输入tensor和输出tensor中的各个元素有很直接的映射关系，譬如C[i] = B[i] + A[i]，这个性质可以被用来高效判断graph transformation前后计算是否等价或者部分等价以及纠错。深入理解机制的话可能需要详细过一下整个推导，我还是很惊讶在原来TASO的基础上还能往前走这么一大步，但是直观上来讲这个工作比起TASO，适用范围要窄了一些，因为线性算子的子图这个假设比较强。进一步来讲，线性算子子图数学上这么好的性质，放在graph level来搜索优化很可能是不如放在tensor expression更高效的，在回答提问时作者也提到了确实正在做这个方向上的探索。经朋友提醒，有一些来自PL领域的工作也在做类似的尝试，感兴趣的同学可以参考一下这篇paper：https://www.mwillsey.com/papers/egg。

MAGE: Nearly Zero-Cost Virtual Memory for Secure Computation

非常好的工作，也是今年的best paper之一，最核心的切入点就是，secure computation的oblivious性质，这个词比较难翻译，但意思就是程序执行中不会泄露除程序执行结果本身以外的信息。举例而言就是我们知道一个普通的程序中可能会有很多if else分支，那么程序执行过程中走不同的分支会有不同的执行时间，产生不同的内存访问，这些信息可以被执行环境所观测到从而泄露数据隐私。在secure computation中，从程序编写到编译器优化，都需要杜绝这样的风险。怎样正确地实现与安全地执行仅在数学上安全的加密算法，一直都是一个比较重要的问题。MAGE走的是另一个方向，利用程序oblivious的性质，他们意识到整个程序的内存访问其实是可以提前预测的！所以他们通过编译的方法，提前计算和规划了程序的内存访问，数据预取等，因为secure computation经常和加密数据打交道，而加密数据体积常常比原始数据大很多倍（会引入大量page fault, swapping），对于IO的优化至关重要而MAGE确实起到了立竿见影的效果。

Graph Embeddings and Neural Networks

今年应该是OSDI/SOSP第一次收GNN System优化的工作，而且一次性就收了四篇，其中三篇集中在分布式GNN的scalability问题，GNNAdvisor比较综合地介绍了一些细粒度的优化。大部分都是扎实的工作，但是就从我自己的经验上感觉，现阶段GNN System的设计，不能脱离算法的发展，或者说，其实还没有建立起真正好的可以有效连接算法和计算资源的中间抽象，重要的工作更可能诞生于一个同时了解算法应用和系统设计的团队。当然这个只是很个人的口嗨式的high level的表达，顺手给AWS Shanghai AI Lab打一个广告，如果对于GNN算法和系统设计感兴趣的话，国内可能找不到比DGL team更好的地方（打钱！）。

最后就是侃一侃Timothy的keynote，不知道现在有没有公开release，其实还是非常有趣和值得一看。核心的诉求就是，OS不是一个垂垂老矣，没有什么机会的领域，恰恰相反的是，随着底层各种硬件的加速异构化，现在正是一个对于OS来讲需要大的变革的时代。Linux的那一套哪怕是十几年前Barrelfish诞生的时候就应该过时的过度简单的系统抽象，在今天会带来越来越多的问题。当然也有很多人反馈到OS研究这一行各种意义上的门槛都太高了，我自己深以为然，另一方面自己其实也比较惭愧system programming做的太少所以对于核心OS的研究基本也只能泛泛而谈。这里其实很敬佩IPADS团队，作为国内最强的，能够持之以恒地深耕OS核心问题的团队，今年一口气被OSDI接受四篇工作并不是运气使然。