How to support multi-devices in our new framework

[QiJune]

1. 首先定义问题，这里的multi-devices仅仅指的是在单机上，一个网络的不同层可以被拆分到不同设备上执行

net = ['op1', 'op2', 'op3', 'op4']

如上述所示，op1在CPU上执行，op2在0号GPU上执行，op3在1号GPU上执行，op4在FPGA上执行

对于多机情况，限定多机是单机的简单复制，仅考虑数据并行，不支持模型跨多机执行。

2. 目前Paddle中有两个概念与设备紧密相关，分别是Place和DeviceContext.

Place定义如下：

typedef boost::variant<GPUPlace, CPUPlace, FPGAPlace> Place;

DeviceContext定义如下：

class DeviceContext {};
class CPUDeviceContext : public DeviceContext {};
class CUDADeviceContext : public DeviceContext {};
class FPGADeviceContext : public DeviceContext {};

这里的FPGAPlace和FPGADeviceContext是为了举例说明怎么向Paddle添加一个新设备的支持。

3. Operator是描述一个操作的，真正的计算发生在OpKernel里面。一个Operator可以对应于多个OpKernel。我们可以针对不同的设备实现不同的OpKernel，注册到一个map中。

而OpKernel的选择，是运行时根据传入DeviceContext所包含的Place信息决定的。

virtual void OperatorBase::Run(const Scope& scope, const platform::DeviceContext& dev_ctx) const = 0;

4. 考虑怎么根据用户的配置，执行一个multi-devices的网络：

• 首先VarDesc和OpDesc必须包含device信息，这样才能知道Op执行在什么设备上
• 需要实现copy operator，用于不同设备之间数据的拷贝。当用户配置跨设备网络时，必须显式添加copy operator（以后可以由Paddle来自动添加，减轻用户负担）
• 需要实现DeviceContextManager，可以根据网络配置中的device信息，预先创建出对应的DeviceContext。然后在执行每一个Operator时，可以从从DeviceContextManager里面去拿DeviceContext参数。
• 所以还是需要有一个Executor/Scheduler/etc，这样一个概念，来根据用户配置的device信息，从DeviceContextManager中拿到对应的DeviceContext，然后执行每一个Operator

[QiJune]

看了一下dynet对multi-devices的支持，贴在这里了，供大家参考

dynet multi-devices支持

dynet一个鲜明的特点是Graph的构造和执行是同时进行的。

Device定义

dynet中Device可以对应于Paddle中的Place和DeviceContext，同时包括了device id信息以及CUDA stream等相关资源。

class Device {};
class Device_GPU : public Device {};
class Device_CPU : public Device {};

相关全局变量

std::vector<Device*> devices; // 存储Device_GPU
std::unordered_map<std::string, Device*> devices_map // 存储所有device;

在初始化的时候，每个GPU构造一个对应的Device_GPU；同时会构造一个Device_CPU.

用户可以使用get_global_device接口拿对应的Device

// 接口声明如下：
Device* get_global_device(const std::string& name);

// 接口使用如下：
Device* cpu_device = get_global_device("CPU");
Device* gpu_device = get_global_device("GPU:0");

使用样例

可以参考这个例子

一些重点是

// 初始化的时候创建全局的device
dynet::initialize(argc, argv);

// 获取已创建的device
Device* cpu_device = get_global_device("CPU");
Device* gpu_device = get_global_device("GPU:0");

// 模型添加参数时需要指定device
Parameter p_W = m.add_parameters({HIDDEN_SIZE, 2}, gpu_device);


// 定义输入时，需要指定device
Expression x = input(cg, {2}, &x_values, gpu_device);

// 当需要跨设备计算时，需要显式调用to_device操作，实际上相当于一个copy operator
Expression h = tanh(W * x + b);
Expression h_cpu = to_device(h, cpu_device);

[Superjomn]

想到的一个简单且灵活的方案，需要

1. 添加类似 mxnet 中的 dependency_engine 实现解依赖并行
2. op 可以单独设置 device 信息（类似 tf.device)

第一点可以实现高效并行，并且不限制计算的表示（是图还是block），对当前框架的修改最小

第二点可以方便地实现模型并行和数据并行（可以在python端写）

如上图的模型，具体执行时

• block 存储了一个 array of operators
  • slice (a)
  • A
  • slice (b)
  • B
  • slice (c)
  • C
  • average
• dependency engine 通过对Variable 的 Read/Write 分析解开依赖，如下执行

slice(a) > A 
                     \
slice(b) > B    -  average
                     /
slice(c) > C

为每个 device 的分配一个线程，CPU分配一个线程，4线程并行可以实现多device并行

在这种设计里

• 计算的存储方式无所谓（不需要纠结graph/block) (参照 mxnet engine
• block无需考虑多线程/多device，现有设计无需复杂化
• 更灵活，表现力可以支持任意复杂的数据并行/模型并行（参照 tf.device)
• 兼容了 tf 和 mxnet 比较核心的优势

dependency engine 本身工作量不算大，已经复刻了一个简单版本 simple dependency engine

[helinwang]

谢谢@QiJune，写得非常清晰。

首先VarDesc和OpDesc必须包含device信息，这样才能知道Op执行在什么设备上

op 可以单独设置 device 信息（类似 tf.device)。第二点可以方便地实现模型并行和数据并行（可以在python端写）

Device信息我认为应该让Paddle自动添加，不必暴露给用户。模型并行和数据并行咱们都可以自己改图，不需要用户参与。

[helinwang]

接着春伟说的“dependency engine”：

我觉得Block需要改的地方有：

1. 删除Block::Run，只有OP能够Run，Block只是OP依赖关系图和数据流的表示，不能够被Run。

需要增加的模块：

1. 改图以及Placement模块：
   1. 根据用户eval的target，找子图。
   2. 按照单机多卡或者多机，自动扩充图（先支持数据并行，以后支持模型并行）。
   3. 自动做Placement的工作，给图中的OP加上Place（包含单机多卡和多机的情况）。按机器切分图，加上send／recv OP。
   4. 发送给对应的engine运行。（单机只有一个engine，多机每个机器一个engine）
2. engine（叫dependency engine或者scheduler）拿到图之后不用做任何其他操作可以运行给定的图（Block）。

[QiJune]

@helinwang

Device信息我认为应该让Paddle自动添加，不必暴露给用户。模型并行和数据并行咱们都可以自己改图，不需要用户参与。

这里的multi-devices主要是指模型并行，即一个网络有些op由CPU执行，有些op由FPGA执行。那么就必须由用户来指定每个op在哪个具体的设备上执行。
即使用户不需要添加copy operator，由Paddle负责来改图，那么device信息还是要有的。至少copy operator得知道自己的src device和dst device是什么。

[QiJune]

@Superjom
赞同有dependency engine的相关设计，以及需要有tf.device的设计。

block 存储了一个 array of operators

block中的operator能不能在不同的device设备上？即前一个operator在CPU上，后一个operator在FPGA上。

[shijiaxin]

如果由Paddle添加Copy operator，是不是应该也由Paddle处理不同设备上同一个variable的命名问题？
比如用户写的是如下代码：
Operator("mul", X="A", Y="B", Out="C", device = "CPU")
Operator("softmax", X="C", Y="hidden", device = "GPU0")
那么Paddle会改写成：
Operator("mul", X="A", Y="B", Out="C", device = "CPU")
Operator("copy", X="C", Y="C-gpu0", src_device = "CPU", dst_device = "GPU0")
Operator("softmax", X="C-gpu0", Y="hidden", device = "GPU0")

[QiJune]

@shijiaxin 确实是的，需要自动的生成一些名字。

[helinwang]

@QiJune

这里的multi-devices主要是指模型并行，即一个网络有些op由CPU执行，有些op由FPGA执行。那么就必须由用户来指定每个op在哪个具体的设备上执行。
即使用户不需要添加copy operator，由Paddle负责来改图，那么device信息还是要有的。至少copy operator得知道自己的src device和dst device是什么。

Paddle可以有规则自动放OP，这个规则兼容用户指定的place，比如最基本的规则可以是FPGA>GPU>CPU，如果某些OP用户自己指定了place则用用户指定的。如果每个OP都需要用户place则太复杂了。

[dzhwinter]

如果由Paddle添加Copy operator，是不是应该也由Paddle处理不同设备上同一个variable的命名问题？
比如用户写的是如下代码：
Operator("mul", X="A", Y="B", Out="C", device = "CPU")
Operator("softmax", X="C", Y="hidden", device = "GPU0")
那么Paddle会改写成：
Operator("mul", X="A", Y="B", Out="C", device = "CPU")
Operator("copy", X="C", Y="C-gpu0", src_device = "CPU", dst_device = "GPU0")
Operator("softmax", X="C-gpu0", Y="hidden", device = "GPU0")

这个是有考虑的，例如加入device_prefix，Operator在gpu0上名字会是"GPU0/A". 这个很容易解决，
相关的PR，大家在python层面的API没有达成一致。
@shijiaxin

[dzhwinter]

按照现在的Block设计，Block是单设备单线程的，应该预先切分op到包含对应device的Block中去。就不会有同一个Block中的op位于不同的device情况。
假设FPGA上的一个Block为BlockFPGA, CPU上的一个Block为BlockCPU，外层包含BlockFPGA和BlockCPU的这个概念目前没有确定。因为Block现在没有嵌套。
未来的设计里Block如何hold这种情况？ @Superjom

[helinwang]

今天和@dzhwinter讨论了下，如果有device to device (on the same machine) send / recv OP （或者称为copy OP），有个好处是多个OP用同一个其他device的tensor的时候，内存不用copy多遍。
比如：

# Tensor "t" on CPU, OP "+" on GPU
a = t + 1
b = t + 1

如果隐式copy，按照现在的实现应该是t被copy两遍。如果是copy OP，则t被显式copy，只会被copy一次。

[dzhwinter]

显式copy方便框架做进一步的优化。例如提前分析依赖后发现未来没有写操作，具有多个读操作，就可以提前完成拷贝。这步优化需要框架来完成。

[QiJune]

贴一下mxnet的multi-devices的原理：

1. python端需要指定一个 group2ctx的参数，里面是一个key-value的map，value是设备id

ngpu = 2
# A simple two GPU placement plan
group2ctx = {'embed': mx.gpu(0),
             'decode': mx.gpu(ngpu - 1)}

2. 在配置模型并行的拓扑结构时，需要给每层指定一个key，这个key就是上面map中的key

with mx.AttrScope(ctx_group='embed'):
        embed_weight=mx.sym.Variable("embed_weight")

with mx.AttrScope(ctx_group='decode'):
        cls_weight = mx.sym.Variable("cls_weight")
        cls_bias = mx.sym.Variable("cls_bias")

3. 把拓扑结构与group2ctx绑定起来，构造一个C++端的executor

4. C++端的executor构造一个图，在NNVM里面专门有一个place_device的pass，来对Graph中的每个节点进行遍历，设置device信息；如果发现跨设备，则插入copy operator

调用关系图如下：

GraphExecutor::InitGraph  --> GraphExecutor::AssignContext  --> nnvm::pass::PlaceDevice

[dzhwinter]

多谢 @QiJune ! 这个我们是调研过的。其中包括了mxnet，tensorflow。详细见Survey-Multi-GPU, Distributed-Tensorflow，笔记写的比较简单，可以参考一下。

place这个问题其实是给各个op标记运算设备，并提供可用variable(内存)的过程，处于编译修改运行的Graph之后。用来在用户约束的条件下(例如某个op/某些层运行在特殊设备上；运行集群中有GPU等设备可以加速；等等)找到合适的运行策略。mxnet框架和tensorflow框架很相似，tf单独成为一个概念，称为placement，代码实现见placer。

在tf中，Placement的执行标记过程的算法是，placement algorithm，这个标记策略甚至可以对专用算法优化，其中对reinforment learning的优化论文见Optimization in Reinforcement Learning。

以tf为例，Placement模块实现逻辑是

1. 在op里记录 device约束标记。 指定到node，job, device 三级结构。

message NodeDef {
  // DEVICE_SPEC ::= PARTIAL_SPEC
  //
  // PARTIAL_SPEC ::= ("/" CONSTRAINT) *
  // CONSTRAINT ::= ("job:" JOB_NAME)
  //              | ("replica:" [1-9][0-9]*)
  //              | ("task:" [1-9][0-9]*)
  //              | ( ("gpu" | "cpu") ":" ([1-9][0-9]* | "*") )
  //
  // Valid values for this string include:
  // * "/job:worker/replica:0/task:1/device:GPU:3"  (full specification)
  // * "/job:worker/device:GPU:3"                   (partial specification)
  // * ""                                    (no specification)
  //
  // If the constraints do not resolve to a single device (or if this
  // field is empty or not present), the runtime will attempt to
  // choose a device automatically.
  string device = 4;
}

2. SessionOption标记对设备环境的约束。记录运行环境中可用资源。

3. 给切分Graph提供标记。Placement algorithm 一次运行，打两种标记，分别是PRE_PLACEMENT 和Post_PLACEMENT。

  // Groups of passes are run at different points in initialization.
  enum Grouping {
    PRE_PLACEMENT,          // after cost model assignment, before placement.
    POST_PLACEMENT,         // after placement.
    POST_REWRITE_FOR_EXEC,  // after re-write using feed/fetch endpoints.
    POST_PARTITIONING,      // after partitioning
  };

4. 分发切分后的Graph到各个设备上，执行对应的op.

  TF_RETURN_IF_ERROR(OptimizationPassRegistry::Global()->RunGrouping(
      OptimizationPassRegistry::PRE_PLACEMENT, optimization_options));

  TF_RETURN_IF_ERROR(placer.Run());

  TF_RETURN_IF_ERROR(OptimizationPassRegistry::Global()->RunGrouping(
      OptimizationPassRegistry::POST_PLACEMENT, optimization_options));

[dzhwinter]

对Placement的标记解释一下，tf中的PRE_PLACEMENT 标记给placement algorithm用的，是tf内部预估op的耗时（称为cost model），提供标签作用。例如同样的copy/send/recv operator，跨节点和跨设备开销不同，跨设备rdma, infiniteBand，普通网线也不相同。

Post_PLACEMENT是place 运行后标记给切Graph的模块使用，此时op都已分配device。

[dzhwinter]

这是个好问题！另外，Auto placement在分布式环境中的优化是个难题。这是tf的讨论issue: tensorflow/tensorflow#2126

[QiJune]

@dzhwinter 多谢提供TensorFlow的一些设计思路。

Auto placement是一个非常难的问题，我们建议现阶段暂时不考虑这个问题。

我们考虑的问题是，device的描述信息都是用户明确给定的，在严格遵循用户配置的基础上，考虑一定程度上的并行优化(比如在CPU上的多线程执行优化，在一块GPU上的多CUDA stream执行优化)。

因此我们要做的事情有两个：

1. 提供一种简便的用户配置device信息的机制。所有的varibale和operator的device都由用户指定，显然对用户来说一个负担，我们可以设计一种机制来减轻用户负担。同时要保证能根据用户的配置，最终解析得到每一个variable和operator的明确的device信息。
2. 设计一个执行引擎。可以对op的执行读写依赖进行分析，满足依赖关系的op可以并行执行。比如backward和update显然是可以同时进行的，op1的backward完成之后，就可以执行op1的update；与此同时，op2的backward计算也在进行。这样可以做到计算与通信互相掩盖。

[helinwang]

Auto placement是一个非常难的问题，我们建议现阶段暂时不考虑这个问题。

@QiJune 谢谢回复，我们准备的是自动placement单机多卡，和多机trainer - pserver架构，模型并行并不在目前要做的范围中。目前我们的确还没有实现出来，所以考虑可能不是很周到。我以为这两种自动placement并不是很难：因为我们知道那些是参数，哪些是梯度，哪些是optimizer（v2 api标明了哪些是optimizer），单机多卡要做的是broadcast 参数和梯度的值，多机pserver要做的是把参数和optimier放到pserver上，目前看起来没有特别难实现的事情？（也可能是我们考虑少了）

[Superjomn]

和王叔讨论了下，暂时应该不准备采用dependency engine，data parallel 和 model parallel 应该要有具体的实现 @QiJune @helinwang

[QiJune]

@Superjom @helinwang @dzhwinter
OK，我的理解总共有三个问题需要回答，我写一下我的理解：

• 问题1： 要做什么事情

支持数据并行和模型并行

• 问题2：大概怎么做

1 前提是VarDesc和OpDesc有一个device字段，在执行Block前，都需要填入明确device信息。因此，我们需要设计一种规则，来简化用户的配置负担。然后把用户的配置解析，对device字段进行填充。

2 既然不采用dependency engine，那么应该就先只是串行的版本，数据并行和模型并行先做串行的，再考虑下一步优化

• 问题3：优先级怎么样

1 数据并行优先级高于模型并行

2 在模型并行中，(单机上模型并行 --集群数据并行) 的方式 高于 整个集群模型并行

[QiJune]

@helinwang

• 单机多卡，多机多卡的数据并行，auto placement并不困难。
• (单机上模型并行 --集群数据并行)，用户在单机上指定网路拓扑结构分别在哪些device上，然后我们自动扩展到多机上，这个也不是很困难。
• 多机多卡的模型并行，auto placement比较困难，先不考虑。

[dzhwinter]

感谢回复！

问题1： 要做什么事情
支持数据并行和模型并行

框架提供多设备(多节点)的设备支持能力。例如你提到的部分op运行在 arm，fpga等设备上，不属于数据并行。

不支持模型并行。原因是从实践上看，模型并行几乎没有实际应用。对large scale 的embedding 层可以特殊处理，放进parameter server。

问题2：大概怎么做
1 前提是VarDesc和OpDesc有一个device字段，在执行Block前，都需要填入明确device信息。因此，我们需要设计一种规则，来简化用户的配置负担。然后把用户的配置解析，对device字段进行填充。

@helinwang @Superjom @QiJune 我们曾达成一致，在OpDesc添加一个device字段。这个想法暂时没得到王叔支持，他认为单个GPU或者fpga只是用来加速，即使是运行在gpu上，也一定有一个cpu thread来支持invoke。所以把device放进op还是Block Desc还在考虑。

解析用户配置，填充device字段

我理解这个并不困难，就是auto placement，在 Converter
@helinwang 的PR里给了设计描述。

Place the OPs in the graph onto different devices on different PaddlePaddle runtime according to a placement algorithm and device constraint specified by the user.

Placement Algorithm

Our first implementation will only support "trainer-parameter server" placement: the parameters, initializers, and optimizers are placed on the PaddlePaddle runtimes with the parameter server role. And everything else will be placed on the PaddlePaddle runtimes with the trainer role. This has the same functionality of our "trainer-parameter server" architecture of PaddlePaddle v0.10.0, but is more general and flexible.

In the future, we will implement the general placement algorithm, which makes placements according to the input IR, and a model of device computation time and device communication time. Model parallelism requires the general placement algorithm.

tf中的难点是auto placement的优化算法，现阶段并不考虑。

2 既然不采用dependency engine，那么应该就先只是串行的版本，数据并行和模型并行先做串行的，再考虑下一步优化

dependency engine是 @Superjom 目前的一个想法，还在讨论中，和这个issue中的数据并行，模型并行无关。这个想法没有得到王叔的支持，

我在写多卡的支持demo，#3948 ，上周基本在做MITHackathon，开发上update比较少，大部分设计内容都在helin的两个PR中，，没有及时同步抱歉哈

[QiJune]

不支持模型并行。原因是从实践上看，模型并行几乎没有实际应用。对large scale 的embedding 层可以特殊处理，放进parameter server。

@dzhwinter 这个还是非常有用的，paddle实现了parallelNN就可以支持网络一些层是跨设备的。我能想到的使用场景如下：

• 用户为了快速验证自己的想法，在python端写了一个CPU的operator，然后其他的Op仍然使用GPU训练。
• 某些op在GPU上实现非常困难，比如crf，nce等等。一个网络拓扑结构绝大部分会在GPU上运行，而这些op需要在CPU上运行。
• 某些op在FPGA上会得到显著加速，比如fc，embedding等，因此某些op会在FPGA上运行，其他不适合加速的op会在CPU上运行

总之，Paddle原本就支持的parallelNN的功能，我们需要在Paddle重构之后仍然支持。我们可以在单机上支持这种跨设备的能力，在集群上，整体来看仍然是数据并行。Paddle目前的版本也是这么做的。

[dzhwinter]

这里的模型并行有误会。一个网络中部分op运行在设备A，部分运行在设备B上必然是支持的。通过Converter添加send/recv/copy来支持。
其余问题线下已沟通。