Paddle Lite是飞桨的轻量化推理引擎，为手机、IoT端提供高效推理能力，且广泛整合跨平台硬件，满足端侧部署及应用落地的需求。本文将描述Paddle Lite在模型转换过程（模型转换opt工具）中，静态Kernel选择的策略以及一些思考。
注：华为NPU、XPU、APU等硬件设备的Kernel选择，有其整体的"subgraph"的OP和Kernel，一般只有一个Kernel可选，与本文所述的方法存在不同。
Paddle Lite底层Kernel选择上会考虑候选Place，Place由设备（Target）、精度（Precision）、数据排布（DataLayout）等构成。
/* Place specifies the execution context of a Kernel or input/output for a
* kernel. It is used to make the analysis of the MIR more clear and accurate.
*/
struct LITE_API Place {
TargetType target{TARGET(kUnk)};
PrecisionType precision{PRECISION(kUnk)};
DataLayoutType layout{DATALAYOUT(kUnk)};
int16_t device{0}; // device ID
Place() = default;
Place(TargetType target,
PrecisionType precision = PRECISION(kFloat),
DataLayoutType layout = DATALAYOUT(kNCHW),
int16_t device = 0)
: target(target), precision(precision), layout(layout), device(device) {}
}01. Kernel注册的Place：同一个op根据Place的不同可注册实现多种Kernel
同一个op如conv2d，可能会有不同设备的实现如ARM CPU、OpenCL、x86、CUDA等。在Kernel注册时，需要指定Kernel的Place信息。
Place用于Kernel注册，以区分唯一性。如实现一个基于ARM CPU以NCHW数据排布且以FP32计算的conv2d Kernel，那么其注册时候就会以conv2d、kARM、kFloat，kNCHW，def，用来区分这个Kernel的唯一性。下面是conv2d的多种不冲突的Kernel注册形式：
conv2d, kARM, kInt8, kNCHW, def
conv2d, kARM, kFloat, kNCHW, def
conv2d, kARM, kFloat, kNHWC, def
conv2d, kOpenCL, kFloat, kNCHW, def
conv2d, kOpenCL, kFloat, kImageDefault, defPS：def默认为用来区分Kernel注册时唯一性起名的一部分，作为补充。
02. 用于Kernel选择的候选valid_places
模型推理时，遇到conv2d是选择OpenCL还是ARM CPU来执行呢？如上面5个conv2d，模型执行时候选哪个？
这个涉及到同一个op算子，在对应不同Kernel注册的Place（上面5个conv2d Kernel）和候选的执行valid_places的比较打分排序。其中，valid_place是预设好的，例如下面是以ARM CPU跑Float kernel时的预设valid_places：
std::vector<Place> valid_places({
Place{TARGET(kARM), PRECISION(kFloat)},
});再如，下面是OpenCL以FP16的精度ImageDefault的数据排布跑模型时的预设 valid_places：
std::vector<Place> valid_places({
Place{TARGET(kOpenCL), PRECISION(kFP16), DATALAYOUT(kImageDefault)},
Place{TARGET(kOpenCL), PRECISION(kFloat), DATALAYOUT(kNCHW)},
Place{TARGET(kOpenCL), PRECISION(kAny), DATALAYOUT(kImageDefault)},
Place{TARGET(kOpenCL), PRECISION(kAny), DATALAYOUT(kNCHW)},
TARGET(kARM), // enable kARM CPU Kernel when no opencl Kernel
});此外，valid_places中place顺序越靠前，越倾向选择该place对应的Kernel，即权重系数越大（见后文KernelGrade方法中的 weight计算）。
03. Kernel选择策略：候选Kernel的place与用户valid_places的笛卡尔积
Pass是Paddle Lite用于遍历计算图，并对计算图进行修改的系列操作，如某些op融合、op删除。针对op选择合适的Kernel，也是通过Pass实现的。Kernel选择有两种方法，一种是对同一个op多种Kernel动态测试运行时间，选择时间最短的的Kernel组合；另外一种根据预设的规则来选择，规则中已做了较为综合的考虑。那Paddle Lite选择策略是怎样的呢？
Paddle Lite有一个基于已有注册Kernel与valid_places匹配度的打分策略，即第二种，根据预设规则来做选择。其实现的代码对应下面两个文件：
- ./lite/core/mir/http://static_kernel_pick_pas...：全图遍历，为每个op选择Kernel。该过程会计算图中的每个计算节点对应的多种Kernel, 这些Kernel的Place与用户传入的 valid_places中的每个Place，两两打分（笛卡尔积），选择分数最高的Kernel；
- ./lite/core/mir/static_kernel_pick_pass.h：KernelGrade会计算特定Kernel与valid_place 中每个Place的匹配分数。匹配分数是基于Place中包含的设备（Target）、精度（Precision）、数据排布（DataLayout）等信息计算得到，即打分策略。
下面描述一下这两个步骤：
3.1 全图遍历选择Kernel
上面第一个步骤代码化简如下，步骤解释见下面注释：
// lite/core/mir/static_kernel_pick_pass.cc
// 1. 依次遍历模型graph节点
for (auto& node : graph->mutable_nodes()) {
if (!node.IsStmt()) continue; // 跳过非计算节点
auto& instruct = node.AsStmt();
// 获取所有该节点的输入和输出的tensor精度，实现略
std::unordered_map<std::string, PrecisionType> in_precision_types;
std::unordered_map<std::string, PrecisionType> out_precision_types;
// 获取该层op的不同kernel候选实现：instruct.kernels()
// 比方该层是conv2d，那么instruct.kernels()方法，
// 就可获取到所有编译进去的conv2d的不同实现。
// 2. 依次(for)对不同Kernel实现打分(KernelGrade)，
// KernelGrade用来找出该Kernel实现的最佳Place，
// 及最佳Place下的Kernel得分。
std::vector<std::pair<float, std::unique_ptr<KernelBase>>> scored;
for (auto&& kernel : instruct.kernels()) {
float score = KernelGrade(instruct,
*kernel,
graph->valid_places(),
in_precision_types,
out_precision_types,
instruct.op_info()->input_names(),
instruct.op_info()->output_names());
// 3. 记录每种Kernel实现在最佳Place下的最高分值
scored.emplace_back(score, std::move(kernel));
}
// 4. 对打分结果scored排序，clear清空候选Kernel列表
// 重置候选Kernel列表为分数最高的那一个Kernel，
// 即最终选中要执行的Kernel
std::sort(scored.begin(), scored.end(), KernelScoreCmp);
instruct.kernels().clear();
instruct.kernels().emplace_back(std::move(scored.front().second));
}3.2 KernelGrade：对Kernel的不同Place打分
在全图遍历选择Kernel的过程中，KernelGrade方法起了至关重要的作用：该方法找出当前Kernel下的最佳Place（方法内会对用户传入的 valid_places遍历计算打分: final_score=score*weight），及最佳Place下的该Kernel得分。
公式中 weight就是 valid_places中的次序，越靠前的Place， weight越大。例如希望模型以CPU的NCHW的layout来跑，其中的 valid_places第一个必须是Place{kARM, kFloat, kNCHW}，假设第二个是 Place{kARM,kFloat,kNHWC}，除了layout其他都和第一个Place一样，那么，在两个Place都有对应Kernel注册且实现过的前提下（候选Kernel里二者都有），因NCHW是第一位，则NCHW对应的Place的weight就更大，包含NCHW的Place最终被选中为winner_place概率会大，包含NCHW的Place的Kernel被选中的概率也会更大。
Kernel对Place打分的过程是前文所述的第二个步骤，该步骤有5个阶段，代码简化如下：
// lite/core/mir/static_kernel_pick_pass.h
size_t KernelGrade(
const mir::Node::Stmt& instruct,
const KernelBase& kernel,
const vector<Place>& valid_places,
const unordered_map<std::string, PrecisionType>& in_node_precisons,
const unordered_map<std::string, PrecisionType>& out_node_precisons) {
float final_score_for_winner_place{-1.};
const int kMax = numeric_limits<int>::max();
size_t place_size = valid_places.size();
for (size_t pidx = 0; pidx < place_size; ++pidx) {
const auto& place = valid_places[pidx];
float weight = static_cast<float>(place_size - pidx) / place_size;
size_t place_score{0};
if (place.target == kernel.target())
place_score += kMax / KernelPickFactor::Factor::TargetFirst;
if (place.precision == kernel.precision())
place_score += kMax / KernelPickFactor::Factor::PrecisionFirst;
if (place.layout == kernel.layout())
place_score += kMax / KernelPickFactor::Factor::DataLayoutFirst;
if ((in_node_precisons == kernel_registered_in_tensor_precisions) &&
out_node_precisons == kernel_registered_out_tensor_precisions))
place_score *= 2;
if (weight * place_score > final_score_for_winner_place) {
final_score_for_winner_place = weight * place_score;
winner_place = place;
}
}
return final_score_for_winner_place;
}这5个阶段，对应当前Place信息所包含的的设备、精度、数据排布、输入输出精度检查、当前place信息在预设的valid_place中的排位系数，前3个在计算时有对应系数，下面来看看代码中的设定以及思考：
// /lite/core/types.h
// 系数在实际计算中转为分母
class KernelPickFactor {
public:
using value_type = unsigned char;
enum class Factor : int {
// The following factors are sorted by priority.
TargetFirst = 1,
PrecisionFirst = 1 << 1,
DataLayoutFirst = 1 << 2,
DeviceFirst = 1 << 3,
};
设备target（系数为1）：相比Place中的其他两个数据，设备系数排在首位，因为数据在不同设备上的传输开销极大。若模型中conv都是GPU计算，中间有些层的实现是CPU的，且无zero copy前提下，来回的数据拷贝带来的性能下降就很明显。
精度precision（系数为1/4）：其实精度还有数据排布哪个排在第二位更好，还需实践检验，以OpenCL来说，数据排布layout为cl::image（kImageDefault）可利用L1 cache,一般性能比cl::buffer（NCHW）要好，精度FP16比FP32性能也要好不少，就从OpenCL来说可能二者打分的系数可以一样。当前Paddle Lite的实现是精度的重要性系数（比layout）更大。
数据排布datalayout（系数为1/8）：同上。访存的优化也是必要的，CPU为了更极致的计算性能，而定义了NHWC的数据排布，也是打分的一项考量。
Kernel注册的输入输出的tensor精度，与该graph中当前op的输入输出精度是否匹配。全部匹配就分数翻倍。该打分会检查当前graph中的节点精度和Kernel注册时tensor的精度是否一致。其实不仅是精度，layout和target也可以做这个判断。
分数乘以当前place在valid_places中的排位系数。这个前面已经说过，排在越靠前的place，对应Kernel被选中的 概率就越大。
以上，便是Kernel静态选择的整个过程。
04.思考
其实可以看到：
Paddle Lite的Kernel选择前先做graph层级op粒度的融合操作，与硬件无关；
在之后，是与硬件信息相关的静态Kernel选择。选择基于Place{target, precision, layout}信息，从而确定要执行的Kernel，其中没有参考如卷积核的大小，输入的大小等信息。换句话说，该过程与模型输入、op具体信息无关，选择的依据粒度仍然较大；
static_pick_kernel_pass是模型转换为Paddle Lite格式的过程中一个pass，在之后的pass里应该还有更大的操作空间。比方结合试跑，结合模型更细粒度的信息做一些更细粒度的Kernel选择和定制化修改。
05.补充
- 细粒度的Kernel选择如CPU conv3x3s2p1或者OpenCL的cl Kernel是什么阶段选择的呢？
答：细粒度如conv3x3s2p1要执行的Kernel，会在运行期lite kernel第一次执行的时候基于op具体信息做选择。此外，如果是动态shape，即当前层本次推理的输入与下次不同，也会触发ReinitWhenNeeded方法，进而重新选择。
以OpenCL为例，选择cl Kernel的阶段位于执行的Kernel里，该阶段也会定义lws等与硬件相关的信息。若想做针对OpenCL做模型自动化调优，需要在Lite Kernel这个粒度来做。而且也仅限当前Kernel这个Place，前面我们说过Place包含三个信息target/precision/layout，对于Opencl有两种layout：kNCHW和kImageDefault，对应cl::Buffer和cl::Image2D。但前面说了Lite Kernel的layout已经在静态选Kernel时确定了，即一次只能调优一种Layout下的实现。
- 基于模型试跑的最佳Kernel搜索，是否易于实现呢？
答：目前Paddle Lite还不支持基于试跑的最佳Kernel搜索。一般的策略是让每个Kernel持有一个计算最快的方法，在跑第一遍网络时，根据每层跑多种实现的耗时，记录最快方法，以供后续使用。
如果要更大范围，考虑更多backend做最佳性能的Kernel搜索的话。可能有2种方式：
静态选择和具体选择，对应的两个阶段需要打通。即StaticPickKernel过程，与具体的Kernel选择绑定，这时可以全盘考虑。这个过程也需要拿到conv的kernel size，input shape等信息。但这样虽然两个阶段的Kernel选择打通，但是二阶段的具体Kernel判断需要再写一遍，维护上有一定成本；
两阶段分开做Kernel选择，即每个阶段相对于局部的最优，从而达到相对全局的(次)最优。其实我们的目的是找一个模型在所有不同target、precision、layout的Kernel实现上排列组合这个模型下的最佳性能。但静态选择的策略，在本质上已经考虑了backend不同带来的差异。端侧对性能的极致要求，可能不同backend下的Kernel组合出的一个模型，也会带来性能不稳定，在端侧会非常不友好,而且还有拷贝带来的性能损耗。
如在使用过程中有问题，可加入飞桨官方QQ群进行交流：703252161，飞桨推理部署交流群官方QQ群：696965088。
如果您想详细了解更多飞桨的相关内容，请参阅以下文档。
官网地址：https://www.paddlepaddle.org.cn
飞桨轻量化推理引擎Paddle Lite项目地址：
GitHub: https://github.com/PaddlePadd...
Gitee: https://gitee.com/paddlepaddl...
飞桨开源框架项目地址：
