| 75 | : graph_(g), cost_model_(cost_model) {} |
| 76 | |
| 77 | Microseconds SlackAnalysis::ComputeAsap(std::vector<Microseconds>* asap_times) { |
| 78 | asap_times->resize(graph_->num_node_ids()); |
| 79 | |
| 80 | std::vector<int> pending_count(graph_->num_node_ids()); |
| 81 | InitializePending(graph_, &pending_count); |
| 82 | |
| 83 | std::deque<const Node*> queue; |
| 84 | Node* srcNode = graph_->source_node(); |
| 85 | queue.push_back(srcNode); |
| 86 | (*asap_times)[srcNode->id()] = 0; |
| 87 | |
| 88 | while (!queue.empty()) { |
| 89 | const Node* curr = queue.front(); |
| 90 | queue.pop_front(); |
| 91 | Microseconds ctime = cost_model_->TimeEstimate(curr); |
| 92 | for (const Edge* out_edge : curr->out_edges()) { |
| 93 | // The time needed for 'out' to get its input from 'curr'. |
| 94 | Microseconds copy_time(0); |
| 95 | const Node* out = out_edge->dst(); |
| 96 | if (!out_edge->IsControlEdge() && |
| 97 | curr->assigned_device_name() != out->assigned_device_name()) { |
| 98 | // Add an arbitrary 10microsecs for each copy. |
| 99 | // TODO(yuanbyu): Use below with the real cost model. |
| 100 | // int index = out_edge->src_output(); |
| 101 | // Bytes nb = cost_model_->SizeEstimate(curr, index); |
| 102 | // copy_time = CostModel::CopyTimeEstimate(nb); |
| 103 | copy_time = 10; |
| 104 | } |
| 105 | Microseconds new_asap = (*asap_times)[curr->id()] + ctime + copy_time; |
| 106 | if ((*asap_times)[out->id()] < new_asap) { |
| 107 | (*asap_times)[out->id()] = new_asap; |
| 108 | } |
| 109 | |
| 110 | bool is_ready = UpdatePending(out_edge, &pending_count); |
| 111 | if (is_ready) { |
| 112 | queue.push_back(out); |
| 113 | } |
| 114 | } |
| 115 | } |
| 116 | return (*asap_times)[graph_->sink_node()->id()]; |
| 117 | } |
| 118 | |
| 119 | Microseconds SlackAnalysis::ComputeAlap(std::vector<Microseconds>* alap_times) { |
| 120 | alap_times->resize(graph_->num_node_ids()); |
no test coverage detected