Kernelet: High-Throughput GPU Kernel Executions with Dynamic Slicing and Scheduling笔记

1 INTRODUCTION

GPU需要大的kernel吞吐量来体现GPU的运算优势，但是以前的研究都是针对单个kernel的运行优化，但是单个kernel一般都无法充分利用GPU的资源。而现在的GPU调度都是一个kernel占据GPU然后运行完之后再进行下一个kernel的执行。因此论文提出了一些优化策略，主要思想就是kernel slicing。也就是将大的kernel通过分成较少的block的方式，让多个kernel能够并行执行，以提高GPU的利用率。

所要解决的问题就是分片的粒度和如何调度分片使得GPU的利用率最大。

提出的名为"kernelet"的方法，能够动态的分片和调度，使用马尔科夫链指导kernel分片和调度策略，通过贪心算法来运行分片后的kernel执行，解决了上述问题，提高了GPU的吞吐量。

2 BACKGROUND AND PROBLEM DEFINITION

2.1 GPU Architectures

主要是介绍GPU的一些内容，这里着重注意的是，并没有强调reg和smem对于occupancy的影响，而是假设kernel的reg和smem都不会超过限度

2.2 Problem Definition

Application Scenario

提出本文的应用场景，一个是GPU Server内多个虚拟的用户对于GPU的访问，一个是Server外多个终端对于GPU的访问，本文所提出的方法对这两种场景都适用。

之后提出文章的两点假设

1. 本文的kernel运行在单个GPU上，能够被灵活调度，且不规定kernel到来的顺序
2. 每个kernel的block相互独立。

然后介绍了一些文章中的基本概念，以及要解决的问题就是在给定的一系列kernel组合中，如何执行分片和调度，使得总运行时间最少。

3 SYSTEM OVERVIEW

3.1 Design Rationale

由于是解决一组kernel的调度问题，所以需要考虑新来的kernel的调度；同时，分片和调度系统需要很小的开销。

为了实现上述目标，提出了三点：

1. 两层调度器，一个memory和一个kernel调度器。memory调度器重点在于充分利用PCI-e的带宽，kernel调度器在于充分利用GPU的资源。
2. 只考虑两个kernel的调度，因为已有的研究证明多个kernel的调度优化是NP完全问题。
3. 两个kernel的分片大小一旦固定就不改变

3.2 System Overview

分为等待队列和就绪队列，到来的kernel如果数据还在传输，就放在等待队列，一旦数据传输完成，就进入就绪队列。针对已经就绪的kernel，根据性能模型来调度两个kernel。

调度图

4 KERNELET METHODOLOGY

4.1 Kernel Slicing

首先设置了分片的开销阈值，所需分片造成的程序开销需要低于这个阈值。分片的原理就是在假设block独立的情况下，在每次启动kernel的时候提供一个修正过的index，使得多次启动kernel所得到的block index和未分片一样。

4.2 Scheduling

调度算法如下：

1. 定义R为一组等待执行的kernel
2. if 新来的kernel K加入
3.	将K加入R中
4.	对K进行性能检测
5. while R!=NULL do
6.	<K1,K2,size1,size2> = FindCoSchedule(R)
7.	将得到的输出定为策略c
8.	执行策略c
9.	while R 不变，并且K1和K2都还有block
10.		继续执行c

函数FindCoSchedule(R)
1. 生成c的备选空间
2. 执行剪枝
3. 应用模型计算所有的CP
4. 得到最大的CP组合策略c
5. 返回c

4.3 Performance Model

就是使用马尔科夫链模型来得到集合中最优的kernel和分片组合。

这里要注意的是Heterogeneous Workloads一节中写到，通过让两个kernel的执行时间差距最小，才能够最大限度增加kernel的并行度，也就是说，实际上两个kernel并行的情况下，模型所追求的是两个kernel执行时间差最小，来减少下两个kernel等待的时间，也就是说其他等待执行的kernel要等待这两个kernel完全执行完才可以进行下一步调度。算法实际上描述很有问题。

剩余

下面都是实验之类的，就不写了

总结

实际上这个论文有一个关键问题，就是论文中说分片的开销在GTX680上十分小(< 3%)，但是我在实际实验中发现开销很大(> 10%)，并且在一篇2017ASPLOS文章中，也有实验证明实际上分片的开销很大。