Home | History | Annotate | Download | only in distributed_runtime 
      1 /* Copyright 2016 The TensorFlow Authors. All Rights Reserved.
      2 
      3 Licensed under the Apache License, Version 2.0 (the "License");
      4 you may not use this file except in compliance with the License.
      5 You may obtain a copy of the License at
      6 
      7     http://www.apache.org/licenses/LICENSE-2.0
      8 
      9 Unless required by applicable law or agreed to in writing, software
     10 distributed under the License is distributed on an "AS IS" BASIS,
     11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 See the License for the specific language governing permissions and
     13 limitations under the License.
     14 ==============================================================================*/
     15 
     16 #ifndef TENSORFLOW_CORE_DISTRIBUTED_RUNTIME_SCHEDULER_H_
     17 #define TENSORFLOW_CORE_DISTRIBUTED_RUNTIME_SCHEDULER_H_
     18 
     19 #include <deque>
     20 #include <functional>
     21 #include <map>
     22 #include <unordered_map>
     23 #include <vector>
     24 
     25 #include "tensorflow/core/common_runtime/device.h"
     26 #include "tensorflow/core/common_runtime/device_set.h"
     27 #include "tensorflow/core/graph/costmodel.h"
     28 
     29 namespace tensorflow {
     30 
     31 class SlackAnalysis {
     32  public:
     33   SlackAnalysis(const Graph* g, const CostModel* cost_model);
     34 
     35   ~SlackAnalysis() {}
     36 
     37   // Compute the earliest possible start time for each node, based on
     38   // a given cost model. 'asap_time' is indexed by node id.
     39   Microseconds ComputeAsap(std::vector<Microseconds>* asap_times);
     40 
     41   // Compute the latest possible start time for each node, based on
     42   // a given cost model. 'alap_time' is indexed by node id.
     43   Microseconds ComputeAlap(std::vector<Microseconds>* alap_times);
     44 
     45   // Compute the "slack" of each node. 'slacks' is indexed by node id.
     46   void ComputeSlack(std::vector<int64>* slacks);
     47 
     48  private:
     49   const Graph* graph_;
     50   const CostModel* cost_model_;
     51 
     52   TF_DISALLOW_COPY_AND_ASSIGN(SlackAnalysis);
     53 };
     54 
     55 class GreedyScheduler {
     56  public:
     57   struct Sim {
     58     int degree_parallelism;
     59     int num_running;
     60     std::vector<Node*> ready_nodes;
     61   };
     62 
     63   struct Event {
     64     Node* node;
     65     Microseconds time;
     66     bool is_completion;
     67 
     68     bool operator<(const Event& other) const { return time < other.time; }
     69   };
     70 
     71   GreedyScheduler(const DeviceSet* devices, const CostModel* cost_model,
     72                   const Graph* g, std::vector<int64>* priority);
     73 
     74   ~GreedyScheduler();
     75 
     76   // Computes the start time of each node given the priorities of
     77   // the nodes.
     78   Microseconds ComputeSchedule(std::vector<Microseconds>* start_times);
     79 
     80  private:
     81   // Returns the ready node with the highest priority for a sim.
     82   Node* GetNodeWithHighestPriority(const std::vector<Node*>& nodes);
     83 
     84   const DeviceSet* devices_;
     85   const CostModel* cost_model_;
     86   const Graph* graph_;
     87   std::vector<int64>* priority_;
     88   std::unordered_map<string, Sim*> device_states_;
     89 
     90   TF_DISALLOW_COPY_AND_ASSIGN(GreedyScheduler);
     91 };
     92 
     93 class PriorityScheduler {
     94  public:
     95   PriorityScheduler(const DeviceSet* devices, const CostModel* cost_model,
     96                     const Graph* g);
     97 
     98   ~PriorityScheduler() {}
     99 
    100   // Computes a schedule of the ideal start time for each node.
    101   // Returns the makespan (the total running time).
    102   Microseconds ComputeSchedule(std::vector<Microseconds>* start_times);
    103 
    104   // Computes a schedule and assigns priorities to the nodes based on
    105   // the schedule. Returns the makespan.
    106   Microseconds AssignPriorities(std::vector<int64>* priorities);
    107 
    108  private:
    109   const DeviceSet* devices_;
    110   const CostModel* cost_model_;
    111   const Graph* graph_;
    112 
    113   TF_DISALLOW_COPY_AND_ASSIGN(PriorityScheduler);
    114 };
    115 
    116 }  // namespace tensorflow
    117 
    118 #endif  // TENSORFLOW_CORE_DISTRIBUTED_RUNTIME_SCHEDULER_H_
    119