ext/dsent/model/timing_graph/ElectricalTimingTree.cc

   1 /* Copyright (c) 2012 Massachusetts Institute of Technology
   2  *
   3  * Permission is hereby granted, free of charge, to any person obtaining a copy
   4  * of this software and associated documentation files (the "Software"), to deal
   5  * in the Software without restriction, including without limitation the rights
   6  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   7  * copies of the Software, and to permit persons to whom the Software is
   8  * furnished to do so, subject to the following conditions:
   9  *
  10  * The above copyright notice and this permission notice shall be included in
  11  * all copies or substantial portions of the Software.
  12  *
  13  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  18  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  19  * THE SOFTWARE.
  20  */
  21
  22
  23 #include "model/timing_graph/ElectricalTimingTree.h"
  24
  25 #include "model/ElectricalModel.h"
  26 #include "model/timing_graph/ElectricalTimingNode.h"
  27 #include "model/timing_graph/ElectricalDriver.h"
  28 #include "model/timing_graph/ElectricalNet.h"
  29
  30 namespace DSENT
  31 {
  32     // Initialize the next visited number to be one above the initial number
  33     // used by ElectricalTimingNode
  34     int ElectricalTimingTree::msTreeNum = ElectricalTimingNode::TIMING_NODE_INIT_VISITED_NUM + 1;
  35
  36     ElectricalTimingTree::ElectricalTimingTree(const String& instance_name_, ElectricalModel* model_)
  37         : m_instance_name_(instance_name_), m_model_(model_)
  38     {
  39         //setTreeNum(1);
  40     }
  41
  42     ElectricalTimingTree::~ElectricalTimingTree()
  43     {
  44
  45     }
  46
  47     const String& ElectricalTimingTree::getInstanceName() const
  48     {
  49         return m_instance_name_;
  50     }
  51
  52     bool ElectricalTimingTree::performTimingOpt(ElectricalTimingNode* node_, double required_delay_)
  53     {
  54         // Extract the critical path from all timing paths branching out from the starting node
  55         double delay = performCritPathExtract(node_);
  56         double min_delay = delay;
  57
  58         unsigned int iteration = 0;
  59         unsigned int crit_path_iteration = 0;
  60         unsigned int max_iterations = 8000;                     //TODO: make this not hard-coded
  61         unsigned int max_iterations_single_crit_path = 400;     //TODO: make this not hard-coded
  62
  63         Log::printLine(getInstanceName() + " -> Beginning Incremental Timing Optimization");
  64
  65         // Size up the nodes if timing is not met
  66         while(required_delay_ < delay)
  67         {
  68             Log::printLine(getInstanceName() + " -> Timing Optimization Iteration " + (String) iteration +
  69                     ": Required delay = " + (String) required_delay_ + ", Delay = " +
  70                     (String) delay + ", Slack = " + (String) (required_delay_ - delay));
  71
  72             ElectricalTimingNode* node_for_timing_opt = NULL;
  73             // Go into the less expensive critical path delay calculation
  74             // While the timing is not met for this critical path
  75             while (required_delay_ < delay)
  76             {
  77                 // Find the node to optimize timing for, it would return a node to size up
  78                 node_for_timing_opt = findNodeForTimingOpt(node_);
  79                 // Give up if there are no appropriate nodes to size up or
  80                 // max number of iterations has been reached
  81                 // Size up the chosen node if there is an appropriate node to size up
  82                 if(node_for_timing_opt == NULL || iteration > max_iterations || crit_path_iteration > max_iterations_single_crit_path)
  83                     break;
  84                 else
  85                     node_for_timing_opt->increaseDrivingStrength();
  86
  87                 // Re-evaluate the delay of the critical path
  88                 delay = calculateCritPathDelay(node_);
  89                 iteration++;
  90                 crit_path_iteration++;
  91                 Log::printLine(getInstanceName() + " -> Critical Path Slack: " + (String) (required_delay_ - delay));
  92             }
  93             // Give up if there are no appropriate nodes to size up or
  94             // max number of iterations has been reached
  95             if (node_for_timing_opt == NULL || iteration > max_iterations || crit_path_iteration > max_iterations_single_crit_path)
  96                 break;
  97
  98             crit_path_iteration = 0;
  99             // Once the critical path timing is met, extract a new critical path from
 100             // all timing paths branching out from the starting node
 101             delay = performCritPathExtract(node_);
 102             min_delay = (min_delay > delay) ? delay : min_delay;
 103         }
 104         Log::printLine(getInstanceName() + " -> Timing Optimization Ended after Iteration: " + (String) iteration +
 105                 ": Required delay = " + (String) required_delay_ + ", Delay = " +
 106                 (String) delay + ", Slack = " + (String) (required_delay_ - delay));
 107
 108         min_delay = (min_delay > delay) ? delay : min_delay;
 109
 110         // Check if the timing meets the required delay
 111         if(required_delay_ < delay)
 112         {
 113             // Timing not met. Return false and print out a warning message
 114             const String& warning_msg = "[Warning] " + getInstanceName() + " -> Timing not met: Required delay = " +
 115                 (String) required_delay_ + ", Minimum Delay = " + (String) min_delay + ", Slack = " +
 116                 (String) (required_delay_ - delay);
 117             Log::printLine(std::cerr, warning_msg);
 118             return false;
 119         }
 120         return true;
 121     }
 122     //-------------------------------------------------------------------------
 123     // Extract Crit Path Delay (and marks the crit path)
 124     //-------------------------------------------------------------------------
 125     double ElectricalTimingTree::performCritPathExtract(ElectricalTimingNode* node_)
 126     {
 127         setTreeNum(getTreeNum() + 1);
 128         return extractCritPathDelay(node_);
 129     }
 130
 131     double ElectricalTimingTree::extractCritPathDelay(ElectricalTimingNode* node_)
 132     {
 133         //TODO: Replace with a stack data structure instead of recursion to prevent
 134         //stack overflow problems with long chains of logic (4000+ nodes) and/or better
 135         //performance. Nvm, stack data structure version seems to run much slower
 136
 137         // If the node has already been visited, return the delay!
 138         if (node_->getVisitedNum() == getTreeNum())
 139             return node_->getDelayLeft();
 140         // If the node has been marked as a false path, return 0.0
 141         else if (node_->getFalsePath())
 142             return 0.0;
 143
 144         // Set the new parity for this node
 145         node_->setVisitedNum(getTreeNum());
 146         node_->setDelayLeft(0.0);
 147
 148         double max_delay = 0;
 149         double current_delay = 0;
 150
 151         // Traverse downstream nodes to calculate the delay through each downstream path
 152         vector<ElectricalTimingNode*>* d_nodes = node_->getDownstreamNodes();
 153         for (unsigned int i = 0; i < d_nodes->size(); ++i)
 154         {
 155             current_delay = extractCritPathDelay(d_nodes->at(i));
 156             // Update the critical path
 157             if (current_delay > max_delay)
 158             {
 159                 node_->setCritPath(i);
 160                 max_delay = current_delay;
 161             }
 162         }
 163         // Calculate the delay left from this node
 164         double delay_left = node_->calculateDelay() + max_delay;
 165         node_->setDelayLeft(delay_left);
 166
 167         return delay_left;
 168
 169     }
 170
 171     double ElectricalTimingTree::calculateCritPathDelay(ElectricalTimingNode* node_) const
 172     {
 173         // Simplest case where theres nothing to optimize
 174         if (node_ == NULL)
 175             return 0.0;
 176
 177         double delay = 0.0;
 178         int crit_path = 0;
 179
 180         // Traverse the critical path and sum up delays
 181         while (crit_path >= 0)
 182         {
 183             delay += node_->calculateDelay();
 184             //Move on to the next node in the critical path
 185             crit_path = node_->getCritPath();
 186             if (crit_path >= 0)
 187                 node_ = node_->getDownstreamNodes()->at(crit_path);
 188         }
 189         return delay;
 190     }
 191     //-------------------------------------------------------------------------
 192
 193     //-------------------------------------------------------------------------
 194     // Find Worst Slew Helpers
 195     //-------------------------------------------------------------------------
 196     ElectricalTimingNode* ElectricalTimingTree::findNodeForTimingOpt(ElectricalTimingNode* node_) const
 197     {
 198         // Simplest case where theres nothing to optimize
 199         if (node_ == NULL)
 200             return NULL;
 201
 202         double max_transition_ratio = -10.0;
 203         double current_transition_ratio = 0.0;
 204         double previous_transition = 1e3 * node_->getTotalDownstreamCap();
 205         double current_transition = 0.0;
 206         ElectricalTimingNode* worst = NULL;
 207         int crit_path = 0;
 208
 209         // Find the node with the highest max_transition_ratio to return
 210         while (crit_path >= 0)
 211         {
 212             current_transition = node_->calculateDelay();
 213
 214             //If the node is not yet at max size, it is a potential choice for size up
 215             if (!node_->hasMaxDrivingStrength())
 216             {
 217                 current_transition_ratio = current_transition / previous_transition;
 218
 219                 if (current_transition_ratio > max_transition_ratio)
 220                 {
 221                     worst = node_;
 222                     max_transition_ratio = current_transition_ratio;
 223                 }
 224             }
 225
 226             if (node_->isDriver())
 227                 previous_transition = 0.0;
 228             previous_transition += current_transition;
 229
 230             //Move on to the next node in the critical path
 231             crit_path = node_->getCritPath();
 232
 233             if (crit_path >= 0)
 234                 node_ = node_->getDownstreamNodes()->at(crit_path);
 235         }
 236
 237         return worst;
 238     }
 239     //-------------------------------------------------------------------------
 240
 241     double ElectricalTimingTree::calculateNodeTransition(ElectricalTimingNode* node_) const
 242     {
 243         return node_->calculateTransition();
 244     }
 245
 246     ElectricalTimingTree::ElectricalTimingTree(const ElectricalTimingTree& /* graph_ */)
 247     {
 248         // Disabled
 249     }
 250
 251     ElectricalModel* ElectricalTimingTree::getModel()
 252     {
 253         return m_model_;
 254     }
 255
 256     void ElectricalTimingTree::setTreeNum(int tree_num_)
 257     {
 258         msTreeNum = tree_num_;
 259         return;
 260     }
 261
 262     int ElectricalTimingTree::getTreeNum()
 263     {
 264         return msTreeNum;
 265     }
 266
 267 } // namespace DSENT
 268