20200314

@liwei

Plan

  • LeetCode Daily 1hour
  • TensorFlow MLIR 1hour

Notes

LeetCode Daily

今天的题目是 300. 最长上升子序列，中等难度的简单规划题目。有两种状态方程定义的方法，对应了两种解题方法。

思路一：

  1. 判断数组是否为空，如果为空，则直接返回答案
  2. 另外申请一个数组，dp数组中的元素dp[i]表示以i结尾的最长上升子序列长度，dp[0] = 1
  3. 设原始数组为nums，则状态方程为 dp[i] = max(dp[i], dp[j] + 1) for each j in range(0, i) and nums[i] > nums[j]
  4. 返回dp数组的最大值
  5. 一个优化点是4中的数组最大值可以在3的状态变化过程中，记录并求值

两次遍历，时间复杂度为 N^2

思路二：

  1. 判断数组是否为空，如果是空，则直接返回答案
  2. 申请一个数组，dp数组中的元素dp[i]表示长度为i的最长上升子序列的最后一个元素值，dp[0] = nums[1]，dp一定是单调递增的，可以数学证明
  3. 设原始数组为nums，则对任意一个nums[i]，查找其在dp中的位置
    1. 若 dp[j] < nums[i] < dp[j + 1]，则我们可以用nums[i]更新dp[j + 1]
    2. 若 nums[i] 大于所有元素，则插入到dp的尾部，并更新最大长度的值

一次遍历，一次二分查找，最大时间复杂度为 NlogN

TensorFlow MLIR

在今晚的代码阅读中，我需要尝试记录下来从tensorflow的图定义，到调用mlir进行优化的完整路径中的关键数据结构和他们之间的关系。

  1. mlir的Python interface为 convert_graph_def(graph_def, pass_pipeline)，第一个参数为tensorflow中的graphdef数据结构，后者则是mlir中的pass pipeline的文本表示，它将运行于一个mlir的module上
  2. convrt_graph_def直接调用的c++函数为 std::string ImportGraphDef(const std::string &proto, const std::string &pass_pipeline, TF_Status *status)
  3. 于是，我们可以分成两路继续阅读代码，分别为 graph_def的解析与pass_pipeline的作用

今天注重阅读graphdef的翻译过程。首先介绍一下什么是graphdef，引用stackoverflow上的一个答案：

Graph or Computional Graph is the core concept of tensorflow to present computation. When you use tensorflow, you firstly create you own Computation Graph and pass the Graph to tensorflow. How to do that? As you may know, tensorflow support many front-end programming languages, like Python, C++, Java and Go and the core language is C++; how do the other languages transform the Graph to C++? They use a tool called protobuf which can generate specific language stubs, that's where the GraphDef come from. It's a serialized version of Graph.

We should read your *pb file using GraphDef and bind the GraphDef to a (default) Graph, then use a session to run the Graph for computation

在ImportGraphDef这个c++函数里面，大致的调用流程如下：

  1. 从pb读取和构建一个GraphDef数据结构
  2. 调用ConvertGraphdefToMlir函数，将GraphDef转为一个mlir::MLIRContext和一个mlir::OwingModuleRef
  3. 将pass_pipeline运行在module上

让我们展开2的过程，研究一下ConvertGraphdefToMlir的过程

  1. 将GraphDef调用tf自带的一系列函数，变成一个preprocessed_graphdef
  2. 将preprocessed_graphdef转变为一个tensorflow::Graph
  3. 调用ConverGraphToMlir，将Graph变为mlir::MLIRContext和mlir::OwingModuleRef

要注意的是，上面的1和2，在tensorflow中是不小的代码量，在这先不深究，重点探索tf的Graph数据结构是怎么被转化和解析的。

  1. 先对图做了一个Upgrade操作
  2. 调用了GraphDefImporter::Convert函数

在这，我先就此打住，明天将会仔细研究一下tensorflow::Graph、mlir::MLIRContext和mlir::OwingModuleRef三个数据结构

More

Q: In vim, what's difference between ctrl + t and ctrl + o?

A: CTRL-T is working with tag stack

CTRL-O is working with jumplist

Tag stack and jumplist are different list in vim, but they might have same items when you jumping through tags (eg. using CTRL-])

And this two keyboard shortcuts also work with vscode vim plugin.

TODO:

  1. tensorflow::Graph
  2. mlir::MLIRContext
  3. mlir::OwingModuleRef