// Builds the given graph, and (if successful) indexes the node

   // names for use in placement, and later lookup.

   Status BuildGraph(const GraphDefBuilder& builder, Graph* out_graph) {

     TF_RETURN_IF_ERROR(builder.ToGraph(out_graph));

     nodes_by_name_.clear();

     for (Node* node : out_graph->nodes()) {

       nodes_by_name_[node->name()] = node->id();

     }

     return Status::OK();

   }

   // Invokes the SimplePlacer on "graph". If no DeviceSet is specified, the

   // placement will use the default DeviceSet (of 10 CPU and 10 GPU devices).

   //

   // REQUIRES: "*graph" was produced by the most recent call to BuildGraph.

   Status Place(Graph* graph, DeviceSet* devices, SessionOptions* options) {

     SimplePlacer placer(graph, devices, options);

     return placer.Run();

   }

SimplePlacer::Run()在core/common_runtime/simple_placer.cc文件中，具体实现分为4个步骤：

 // 1. First add all of the nodes. Note that steps (1) and (2)

 // requires two passes over the nodes because the graph (and hence

 // the constraints) may not be acyclic.  这里graph可能是有环的？

 for (Node* node : graph_->nodes()) {

     // Skip the source and sink nodes.

     if (!node->IsOp()) { continue; }

     status = colocation_graph.AddNode(*node);

     if (!status.ok()) return AttachDef(status, node->def());

   }

 // 2. Enumerate the constraint edges, and use them to update the disjoint node set.         // disjoint set（并查集，即不相交的节点集合），一种树型数据结构，

 ...

 ColocationGraph maintains the connected components of a colocation constraint graph, and uses this information to assign a satisfying device placement to the nodes of the graph.

 The implementation uses the union- find algorithm to maintain the connected components efficiently and incrementally as edges (implied by ColocationGraph::ColocateNodes() invocations) are added.

 参考：并查集wiki

  . For each node, assign a device based on the constraints in thedisjoint node set.

   std::vector<Device*> devices;

   std::vector<Node*> second_pass;

   for (Node* node : graph_->nodes()) {

     // Skip the source and sink nodes.

     if (!node->IsOp()) {

       continue;

     }

     // Skip nodes that already have an assigned name.

     if (!node->assigned_device_name().empty()) {

       continue;

     }

     // Heuristic A: prefer to place "generators" with their only

     // consumers.

     //

     // If this is a node with no inputs and a single (non-ref)

     // consumer, we save this for a second pass, so that the

     // consumer's placement is chosen.

     if (IsGeneratorNode(node)) {    // generator node: no input, one output, not a reference-type node

       second_pass.push_back(node);

       continue;

     }

     status = colocation_graph.GetDevicesForNode(node, &devices);

     ...

     // Returns the first device in sorted devices list so we will always

     // choose the same device.

     //

     // TODO(vrv): Factor this assignment out into a pluggable

     // algorithm, so that SimplePlacer is responsible for enforcing

     // preconditions and we can experiment with other algorithms when

     // given a choice of devices. Once we have a better idea of the

     // types of heuristics we want to use and the information needed

     // to perform good placement we can add an interface for this.

     string assigned_device = devices[]->name();

     // Heuristic B: If the node only operates on metadata, not data,

     // then it is desirable to place that metadata node with its

     // input.

     if (IsMetadataNode(node)) {

       // Make sure that the input device type is in the list of supported

       // device types for this node.

       const Node* input = (*node->in_edges().begin())->src();

       // TODO(vrv): if the input is empty, consider postponing this

       // node's assignment to the second pass, so that we handle the

       // case where a metadata node's input comes from a backedge

       // of a loop.

       const string& input_device_name = input->assigned_device_name();

       if (CanAssignToDevice(input_device_name, devices)) {

         assigned_device = input_device_name;

       }

     }

     AssignAndLog(assigned_device, node);   // 将assigned_device分配个node节点，在步骤3中没有对符合Heuristic A的GeneratorNode分配设备，而是在步骤4中完成的

   }

 bool IsGeneratorNode(const Node* node) {

   return node->num_inputs() ==  && node->num_outputs() ==  && node->out_edges().size() ==  && !IsRefType(node->output_type());

 }

 bool IsMetadataNode(const Node* node) {

   const string& node_type = node->type_string();

   return (node_type == "Size" || node_type == "Shape" || node_type == "Rank");

 }

// 4. Perform a second pass assignment for those nodes explicitly skipped during the first pass.

...