Method ComputeSchedule

tensorflow/core/distributed_runtime/scheduler.cc:211–278

}

Microseconds GreedyScheduler::ComputeSchedule(
    std::vector<Microseconds>* start_times) {
  // Initialize pending_count
  std::vector<int> pending_count(graph_->num_node_ids());
  InitializePending(graph_, &pending_count);

  // Initialize event queue
  std::priority_queue<Event> event_queue;
  Event src_event;
  src_event.node = graph_->source_node();
  src_event.time = 0;
  src_event.is_completion = true;
  event_queue.push(src_event);
  Microseconds max_completion = Microseconds(0);

  while (!event_queue.empty()) {
    Event event = event_queue.top();
    event_queue.pop();
    if (event.is_completion) {
      Sim* sim = device_states_[event.node->assigned_device_name()];
      --sim->num_running;

      if (event.time > max_completion) {
        max_completion = event.time;
      }

      for (const Edge* out_edge : event.node->out_edges()) {
        Microseconds copy_time(0);
        const Node* out = out_edge->dst();
        if (!out_edge->IsControlEdge() &&
            event.node->assigned_device_name() != out->assigned_device_name()) {
          // TODO(yuanbyu): Use below with the real cost model.
          // int index = out_edge->src_output();
          // Bytes nb = cost_model_->SizeEstimate(event.node, index);
          // copy_time = CostModel::CopyTimeEstimate(nb);
          copy_time = 10;
        }
        if ((*start_times)[out->id()] < event.time + copy_time) {
          (*start_times)[out->id()] = event.time + copy_time;
        }

        bool is_ready = UpdatePending(out_edge, &pending_count);
        if (is_ready) {
          Event e{out, (*start_times)[out->id()], false};
          event_queue.push(e);
        }
      }
    } else {
      Sim* sim = device_states_[event.node->assigned_device_name()];
      sim->ready_nodes.push_back(event.node);
    }

    for (auto& x : device_states_) {
      Sim* sim = x.second;
      while (sim->num_running < sim->degree_parallelism &&
             !sim->ready_nodes.empty()) {
        Event e;
        e.node = GetNodeWithHighestPriority(sim->ready_nodes);