20200315

@liwei

Plan

  • LeetCode Daily
  • TensorFlow Graph

Notes

LeetCode Daily

今天的题目是 695. 岛屿的最大面积。开始我觉得是动态规划，但是结果发现是深度优先搜索。

思路 1：深度优先搜索

  1. 对任意一个节点，如果它是不存在，或者为 0，则返回与它连通的面积 0，否则进入 2
  2. 将其值标记为 0，保障其只被访问了一次
  3. 加上上/下/左/右节点的联通面积，这四个节点的访问方式同上面的 1 和 2
  4. 外层循环，计算以每个节点开始，可以得到的最大岛屿面积，取最大值

思路 2：深度优先 + 栈

与思路 1相同，只是改成用栈保存相邻未被访问的节点。

思路 3：广度优先

与思路 2相同，这次改成用队列保存相邻但是未被访问的节点。

TensorFlow 代码阅读

接着昨天的描述，今天需要弄清楚几个关键数据结构的意义和他们之间的关系。

TensorFlow Graph

Graph 数据数据结构的定义路径为 tensorflow/tensorflow/core/graph/graph.h

  1. Graph 的相关数据结构主要是Node和Edge，其中Edge分为Edge和ControlEdge
  2. Graph 中，有两种预定义的node，分别为 source node 和 sink node
  3. Graph 中的 node 包含了它们所在的 device 信息
  4. Graph 中，特别针对 while node 进行了处理

一个遗留问题是，the control flow in tensorflow, what is contrl edge and while node?

mlir::MLIRContext

这一数据结构的定义，在文档当中并没有完整的说明，只能查看 llvm 的代码。具体的目录是 llvm-project/mlir/include/mlir/IR/MLIRContext.h。

  1. MLIRContext 是一个包含了一系列的 MLIR modules 的顶层对象
  2. dialects 可以被注册到 MLIRContext 中
  3. operations 可以被注册到 MLIRContext 中
  4. 一个 context 中包含许多的 MLIRContexImpl

mlir::OwingModuleRef

数据结构定义的路径是 llvm-project/mlir/include/mlir/IR/Module.h ,但，这个数据结构只是一个 module 的包装器，所以问题转移成了 module 数据结构是什么

More

后续需要看的

  1. control flow in tensorflow
  2. MLIRContextImpl 数据结构
  3. mlir 中的 module 数据结构

完成之后，我需要回到 3 月 14 日的代码阅读内容，弄明白 tensorflow graph 是怎么变成 mlir 的。