diff options
Diffstat (limited to 'ext/dsent/model/timing_graph/ElectricalTimingTree.cc')
| -rw-r--r-- | ext/dsent/model/timing_graph/ElectricalTimingTree.cc | 247 |
1 files changed, 247 insertions, 0 deletions
diff --git a/ext/dsent/model/timing_graph/ElectricalTimingTree.cc b/ext/dsent/model/timing_graph/ElectricalTimingTree.cc new file mode 100644 index 000000000..83d583c53 --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalTimingTree.cc @@ -0,0 +1,247 @@ + +#include "model/timing_graph/ElectricalTimingTree.h" + +#include "model/ElectricalModel.h" +#include "model/timing_graph/ElectricalTimingNode.h" +#include "model/timing_graph/ElectricalDriver.h" +#include "model/timing_graph/ElectricalNet.h" + +namespace DSENT +{ + // Initialize the next visited number to be one above the initial number + // used by ElectricalTimingNode + int ElectricalTimingTree::msTreeNum = ElectricalTimingNode::TIMING_NODE_INIT_VISITED_NUM + 1; + + ElectricalTimingTree::ElectricalTimingTree(const String& instance_name_, ElectricalModel* model_) + : m_instance_name_(instance_name_), m_model_(model_) + { + //setTreeNum(1); + } + + ElectricalTimingTree::~ElectricalTimingTree() + { + + } + + const String& ElectricalTimingTree::getInstanceName() const + { + return m_instance_name_; + } + + bool ElectricalTimingTree::performTimingOpt(ElectricalTimingNode* node_, double required_delay_) + { + // Extract the critical path from all timing paths branching out from the starting node + double delay = performCritPathExtract(node_); + double min_delay = delay; + + unsigned int iteration = 0; + unsigned int crit_path_iteration = 0; + unsigned int max_iterations = 8000; //TODO: make this not hard-coded + unsigned int max_iterations_single_crit_path = 400; //TODO: make this not hard-coded + + Log::printLine(getInstanceName() + " -> Beginning Incremental Timing Optimization"); + + // Size up the nodes if timing is not met + while(required_delay_ < delay) + { + Log::printLine(getInstanceName() + " -> Timing Optimization Iteration " + (String) iteration + + ": Required delay = " + (String) required_delay_ + ", Delay = " + + (String) delay + ", Slack = " + (String) (required_delay_ - delay)); + + ElectricalTimingNode* node_for_timing_opt = NULL; + // Go into the less expensive critical path delay calculation + // While the timing is not met for this critical path + while (required_delay_ < delay) + { + // Find the node to optimize timing for, it would return a node to size up + node_for_timing_opt = findNodeForTimingOpt(node_); + // Give up if there are no appropriate nodes to size up or + // max number of iterations has been reached + // Size up the chosen node if there is an appropriate node to size up + if(node_for_timing_opt == NULL || iteration > max_iterations || crit_path_iteration > max_iterations_single_crit_path) + break; + else + node_for_timing_opt->increaseDrivingStrength(); + + // Re-evaluate the delay of the critical path + delay = calculateCritPathDelay(node_); + iteration++; + crit_path_iteration++; + Log::printLine(getInstanceName() + " -> Critical Path Slack: " + (String) (required_delay_ - delay)); + } + // Give up if there are no appropriate nodes to size up or + // max number of iterations has been reached + if (node_for_timing_opt == NULL || iteration > max_iterations || crit_path_iteration > max_iterations_single_crit_path) + break; + + crit_path_iteration = 0; + // Once the critical path timing is met, extract a new critical path from + // all timing paths branching out from the starting node + delay = performCritPathExtract(node_); + min_delay = (min_delay > delay) ? delay : min_delay; + } + Log::printLine(getInstanceName() + " -> Timing Optimization Ended after Iteration: " + (String) iteration + + ": Required delay = " + (String) required_delay_ + ", Delay = " + + (String) delay + ", Slack = " + (String) (required_delay_ - delay)); + + min_delay = (min_delay > delay) ? delay : min_delay; + + // Check if the timing meets the required delay + if(required_delay_ < delay) + { + // Timing not met. Return false and print out a warning message + const String& warning_msg = "[Warning] " + getInstanceName() + " -> Timing not met: Required delay = " + + (String) required_delay_ + ", Minimum Delay = " + (String) min_delay + ", Slack = " + + (String) (required_delay_ - delay); + Log::printLine(std::cerr, warning_msg); + return false; + } + return true; + } + //------------------------------------------------------------------------- + // Extract Crit Path Delay (and marks the crit path) + //------------------------------------------------------------------------- + double ElectricalTimingTree::performCritPathExtract(ElectricalTimingNode* node_) + { + setTreeNum(getTreeNum() + 1); + return extractCritPathDelay(node_); + } + + double ElectricalTimingTree::extractCritPathDelay(ElectricalTimingNode* node_) + { + //TODO: Replace with a stack data structure instead of recursion to prevent + //stack overflow problems with long chains of logic (4000+ nodes) and/or better + //performance. Nvm, stack data structure version seems to run much slower + + // If the node has already been visited, return the delay! + if (node_->getVisitedNum() == getTreeNum()) + return node_->getDelayLeft(); + // If the node has been marked as a false path, return 0.0 + else if (node_->getFalsePath()) + return 0.0; + + // Set the new parity for this node + node_->setVisitedNum(getTreeNum()); + node_->setDelayLeft(0.0); + + double max_delay = 0; + double current_delay = 0; + + // Traverse downstream nodes to calculate the delay through each downstream path + vector<ElectricalTimingNode*>* d_nodes = node_->getDownstreamNodes(); + for (unsigned int i = 0; i < d_nodes->size(); ++i) + { + current_delay = extractCritPathDelay(d_nodes->at(i)); + // Update the critical path + if (current_delay > max_delay) + { + node_->setCritPath(i); + max_delay = current_delay; + } + } + // Calculate the delay left from this node + double delay_left = node_->calculateDelay() + max_delay; + node_->setDelayLeft(delay_left); + + return delay_left; + + } + + double ElectricalTimingTree::calculateCritPathDelay(ElectricalTimingNode* node_) const + { + // Simplest case where theres nothing to optimize + if (node_ == NULL) + return 0.0; + + double delay = 0.0; + int crit_path = 0; + + // Traverse the critical path and sum up delays + while (crit_path >= 0) + { + delay += node_->calculateDelay(); + //Move on to the next node in the critical path + crit_path = node_->getCritPath(); + if (crit_path >= 0) + node_ = node_->getDownstreamNodes()->at(crit_path); + } + return delay; + } + //------------------------------------------------------------------------- + + //------------------------------------------------------------------------- + // Find Worst Slew Helpers + //------------------------------------------------------------------------- + ElectricalTimingNode* ElectricalTimingTree::findNodeForTimingOpt(ElectricalTimingNode* node_) const + { + // Simplest case where theres nothing to optimize + if (node_ == NULL) + return NULL; + + double max_transition_ratio = -10.0; + double current_transition_ratio = 0.0; + double previous_transition = 1e3 * node_->getTotalDownstreamCap(); + double current_transition = 0.0; + ElectricalTimingNode* worst = NULL; + int crit_path = 0; + + // Find the node with the highest max_transition_ratio to return + while (crit_path >= 0) + { + current_transition = node_->calculateDelay(); + + //If the node is not yet at max size, it is a potential choice for size up + if (!node_->hasMaxDrivingStrength()) + { + current_transition_ratio = current_transition / previous_transition; + + if (current_transition_ratio > max_transition_ratio) + { + worst = node_; + max_transition_ratio = current_transition_ratio; + } + } + + if (node_->isDriver()) + previous_transition = 0.0; + previous_transition += current_transition; + + //Move on to the next node in the critical path + crit_path = node_->getCritPath(); + + if (crit_path >= 0) + node_ = node_->getDownstreamNodes()->at(crit_path); + } + + return worst; + } + //------------------------------------------------------------------------- + + double ElectricalTimingTree::calculateNodeTransition(ElectricalTimingNode* node_) const + { + return node_->calculateTransition(); + } + + ElectricalTimingTree::ElectricalTimingTree(const ElectricalTimingTree& /* graph_ */) + { + // Disabled + } + + ElectricalModel* ElectricalTimingTree::getModel() + { + return m_model_; + } + + void ElectricalTimingTree::setTreeNum(int tree_num_) + { + msTreeNum = tree_num_; + return; + } + + int ElectricalTimingTree::getTreeNum() + { + return msTreeNum; + } + +} // namespace DSENT + |