/* Copyright (c) 2012 Massachusetts Institute of Technology * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal * in the Software without restriction, including without limitation the rights * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell * copies of the Software, and to permit persons to whom the Software is * furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice shall be included in * all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN * THE SOFTWARE. */ #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* 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