110448Snilay@cs.wisc.edu/* Copyright (c) 2012 Massachusetts Institute of Technology 210448Snilay@cs.wisc.edu * 310448Snilay@cs.wisc.edu * Permission is hereby granted, free of charge, to any person obtaining a copy 410448Snilay@cs.wisc.edu * of this software and associated documentation files (the "Software"), to deal 510448Snilay@cs.wisc.edu * in the Software without restriction, including without limitation the rights 610448Snilay@cs.wisc.edu * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 710448Snilay@cs.wisc.edu * copies of the Software, and to permit persons to whom the Software is 810448Snilay@cs.wisc.edu * furnished to do so, subject to the following conditions: 910448Snilay@cs.wisc.edu * 1010448Snilay@cs.wisc.edu * The above copyright notice and this permission notice shall be included in 1110448Snilay@cs.wisc.edu * all copies or substantial portions of the Software. 1210448Snilay@cs.wisc.edu * 1310448Snilay@cs.wisc.edu * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 1410448Snilay@cs.wisc.edu * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 1510448Snilay@cs.wisc.edu * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 1610448Snilay@cs.wisc.edu * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 1710448Snilay@cs.wisc.edu * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 1810448Snilay@cs.wisc.edu * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 1910448Snilay@cs.wisc.edu * THE SOFTWARE. 2010448Snilay@cs.wisc.edu */ 2110448Snilay@cs.wisc.edu 2210447Snilay@cs.wisc.edu 2310447Snilay@cs.wisc.edu#include "model/timing_graph/ElectricalTimingTree.h" 2410447Snilay@cs.wisc.edu 2510447Snilay@cs.wisc.edu#include "model/ElectricalModel.h" 2610447Snilay@cs.wisc.edu#include "model/timing_graph/ElectricalTimingNode.h" 2710447Snilay@cs.wisc.edu#include "model/timing_graph/ElectricalDriver.h" 2810447Snilay@cs.wisc.edu#include "model/timing_graph/ElectricalNet.h" 2910447Snilay@cs.wisc.edu 3010447Snilay@cs.wisc.edunamespace DSENT 3110447Snilay@cs.wisc.edu{ 3210447Snilay@cs.wisc.edu // Initialize the next visited number to be one above the initial number 3310447Snilay@cs.wisc.edu // used by ElectricalTimingNode 3410447Snilay@cs.wisc.edu int ElectricalTimingTree::msTreeNum = ElectricalTimingNode::TIMING_NODE_INIT_VISITED_NUM + 1; 3510447Snilay@cs.wisc.edu 3610447Snilay@cs.wisc.edu ElectricalTimingTree::ElectricalTimingTree(const String& instance_name_, ElectricalModel* model_) 3710447Snilay@cs.wisc.edu : m_instance_name_(instance_name_), m_model_(model_) 3810447Snilay@cs.wisc.edu { 3910447Snilay@cs.wisc.edu //setTreeNum(1); 4010447Snilay@cs.wisc.edu } 4110447Snilay@cs.wisc.edu 4210447Snilay@cs.wisc.edu ElectricalTimingTree::~ElectricalTimingTree() 4310447Snilay@cs.wisc.edu { 4410447Snilay@cs.wisc.edu 4510447Snilay@cs.wisc.edu } 4610447Snilay@cs.wisc.edu 4710447Snilay@cs.wisc.edu const String& ElectricalTimingTree::getInstanceName() const 4810447Snilay@cs.wisc.edu { 4910447Snilay@cs.wisc.edu return m_instance_name_; 5010447Snilay@cs.wisc.edu } 5110447Snilay@cs.wisc.edu 5210447Snilay@cs.wisc.edu bool ElectricalTimingTree::performTimingOpt(ElectricalTimingNode* node_, double required_delay_) 5310447Snilay@cs.wisc.edu { 5410447Snilay@cs.wisc.edu // Extract the critical path from all timing paths branching out from the starting node 5510447Snilay@cs.wisc.edu double delay = performCritPathExtract(node_); 5610447Snilay@cs.wisc.edu double min_delay = delay; 5710447Snilay@cs.wisc.edu 5810447Snilay@cs.wisc.edu unsigned int iteration = 0; 5910447Snilay@cs.wisc.edu unsigned int crit_path_iteration = 0; 6010447Snilay@cs.wisc.edu unsigned int max_iterations = 8000; //TODO: make this not hard-coded 6110447Snilay@cs.wisc.edu unsigned int max_iterations_single_crit_path = 400; //TODO: make this not hard-coded 6210447Snilay@cs.wisc.edu 6310447Snilay@cs.wisc.edu Log::printLine(getInstanceName() + " -> Beginning Incremental Timing Optimization"); 6410447Snilay@cs.wisc.edu 6510447Snilay@cs.wisc.edu // Size up the nodes if timing is not met 6610447Snilay@cs.wisc.edu while(required_delay_ < delay) 6710447Snilay@cs.wisc.edu { 6810447Snilay@cs.wisc.edu Log::printLine(getInstanceName() + " -> Timing Optimization Iteration " + (String) iteration + 6910447Snilay@cs.wisc.edu ": Required delay = " + (String) required_delay_ + ", Delay = " + 7010447Snilay@cs.wisc.edu (String) delay + ", Slack = " + (String) (required_delay_ - delay)); 7110447Snilay@cs.wisc.edu 7210447Snilay@cs.wisc.edu ElectricalTimingNode* node_for_timing_opt = NULL; 7310447Snilay@cs.wisc.edu // Go into the less expensive critical path delay calculation 7410447Snilay@cs.wisc.edu // While the timing is not met for this critical path 7510447Snilay@cs.wisc.edu while (required_delay_ < delay) 7610447Snilay@cs.wisc.edu { 7710447Snilay@cs.wisc.edu // Find the node to optimize timing for, it would return a node to size up 7810447Snilay@cs.wisc.edu node_for_timing_opt = findNodeForTimingOpt(node_); 7910447Snilay@cs.wisc.edu // Give up if there are no appropriate nodes to size up or 8010447Snilay@cs.wisc.edu // max number of iterations has been reached 8110447Snilay@cs.wisc.edu // Size up the chosen node if there is an appropriate node to size up 8210447Snilay@cs.wisc.edu if(node_for_timing_opt == NULL || iteration > max_iterations || crit_path_iteration > max_iterations_single_crit_path) 8310447Snilay@cs.wisc.edu break; 8410447Snilay@cs.wisc.edu else 8510447Snilay@cs.wisc.edu node_for_timing_opt->increaseDrivingStrength(); 8610447Snilay@cs.wisc.edu 8710447Snilay@cs.wisc.edu // Re-evaluate the delay of the critical path 8810447Snilay@cs.wisc.edu delay = calculateCritPathDelay(node_); 8910447Snilay@cs.wisc.edu iteration++; 9010447Snilay@cs.wisc.edu crit_path_iteration++; 9110447Snilay@cs.wisc.edu Log::printLine(getInstanceName() + " -> Critical Path Slack: " + (String) (required_delay_ - delay)); 9210447Snilay@cs.wisc.edu } 9310447Snilay@cs.wisc.edu // Give up if there are no appropriate nodes to size up or 9410447Snilay@cs.wisc.edu // max number of iterations has been reached 9510447Snilay@cs.wisc.edu if (node_for_timing_opt == NULL || iteration > max_iterations || crit_path_iteration > max_iterations_single_crit_path) 9610447Snilay@cs.wisc.edu break; 9710447Snilay@cs.wisc.edu 9810447Snilay@cs.wisc.edu crit_path_iteration = 0; 9910447Snilay@cs.wisc.edu // Once the critical path timing is met, extract a new critical path from 10010447Snilay@cs.wisc.edu // all timing paths branching out from the starting node 10110447Snilay@cs.wisc.edu delay = performCritPathExtract(node_); 10210447Snilay@cs.wisc.edu min_delay = (min_delay > delay) ? delay : min_delay; 10310447Snilay@cs.wisc.edu } 10410447Snilay@cs.wisc.edu Log::printLine(getInstanceName() + " -> Timing Optimization Ended after Iteration: " + (String) iteration + 10510447Snilay@cs.wisc.edu ": Required delay = " + (String) required_delay_ + ", Delay = " + 10610447Snilay@cs.wisc.edu (String) delay + ", Slack = " + (String) (required_delay_ - delay)); 10710447Snilay@cs.wisc.edu 10810447Snilay@cs.wisc.edu min_delay = (min_delay > delay) ? delay : min_delay; 10910447Snilay@cs.wisc.edu 11010447Snilay@cs.wisc.edu // Check if the timing meets the required delay 11110447Snilay@cs.wisc.edu if(required_delay_ < delay) 11210447Snilay@cs.wisc.edu { 11310447Snilay@cs.wisc.edu // Timing not met. Return false and print out a warning message 11410447Snilay@cs.wisc.edu const String& warning_msg = "[Warning] " + getInstanceName() + " -> Timing not met: Required delay = " + 11510447Snilay@cs.wisc.edu (String) required_delay_ + ", Minimum Delay = " + (String) min_delay + ", Slack = " + 11610447Snilay@cs.wisc.edu (String) (required_delay_ - delay); 11710447Snilay@cs.wisc.edu Log::printLine(std::cerr, warning_msg); 11810447Snilay@cs.wisc.edu return false; 11910447Snilay@cs.wisc.edu } 12010447Snilay@cs.wisc.edu return true; 12110447Snilay@cs.wisc.edu } 12210447Snilay@cs.wisc.edu //------------------------------------------------------------------------- 12310447Snilay@cs.wisc.edu // Extract Crit Path Delay (and marks the crit path) 12410447Snilay@cs.wisc.edu //------------------------------------------------------------------------- 12510447Snilay@cs.wisc.edu double ElectricalTimingTree::performCritPathExtract(ElectricalTimingNode* node_) 12610447Snilay@cs.wisc.edu { 12710447Snilay@cs.wisc.edu setTreeNum(getTreeNum() + 1); 12810447Snilay@cs.wisc.edu return extractCritPathDelay(node_); 12910447Snilay@cs.wisc.edu } 13010447Snilay@cs.wisc.edu 13110447Snilay@cs.wisc.edu double ElectricalTimingTree::extractCritPathDelay(ElectricalTimingNode* node_) 13210447Snilay@cs.wisc.edu { 13310447Snilay@cs.wisc.edu //TODO: Replace with a stack data structure instead of recursion to prevent 13410447Snilay@cs.wisc.edu //stack overflow problems with long chains of logic (4000+ nodes) and/or better 13510447Snilay@cs.wisc.edu //performance. Nvm, stack data structure version seems to run much slower 13610447Snilay@cs.wisc.edu 13710447Snilay@cs.wisc.edu // If the node has already been visited, return the delay! 13810447Snilay@cs.wisc.edu if (node_->getVisitedNum() == getTreeNum()) 13910447Snilay@cs.wisc.edu return node_->getDelayLeft(); 14010447Snilay@cs.wisc.edu // If the node has been marked as a false path, return 0.0 14110447Snilay@cs.wisc.edu else if (node_->getFalsePath()) 14210447Snilay@cs.wisc.edu return 0.0; 14310447Snilay@cs.wisc.edu 14410447Snilay@cs.wisc.edu // Set the new parity for this node 14510447Snilay@cs.wisc.edu node_->setVisitedNum(getTreeNum()); 14610447Snilay@cs.wisc.edu node_->setDelayLeft(0.0); 14710447Snilay@cs.wisc.edu 14810447Snilay@cs.wisc.edu double max_delay = 0; 14910447Snilay@cs.wisc.edu double current_delay = 0; 15010447Snilay@cs.wisc.edu 15110447Snilay@cs.wisc.edu // Traverse downstream nodes to calculate the delay through each downstream path 15210447Snilay@cs.wisc.edu vector<ElectricalTimingNode*>* d_nodes = node_->getDownstreamNodes(); 15310447Snilay@cs.wisc.edu for (unsigned int i = 0; i < d_nodes->size(); ++i) 15410447Snilay@cs.wisc.edu { 15510447Snilay@cs.wisc.edu current_delay = extractCritPathDelay(d_nodes->at(i)); 15610447Snilay@cs.wisc.edu // Update the critical path 15710447Snilay@cs.wisc.edu if (current_delay > max_delay) 15810447Snilay@cs.wisc.edu { 15910447Snilay@cs.wisc.edu node_->setCritPath(i); 16010447Snilay@cs.wisc.edu max_delay = current_delay; 16110447Snilay@cs.wisc.edu } 16210447Snilay@cs.wisc.edu } 16310447Snilay@cs.wisc.edu // Calculate the delay left from this node 16410447Snilay@cs.wisc.edu double delay_left = node_->calculateDelay() + max_delay; 16510447Snilay@cs.wisc.edu node_->setDelayLeft(delay_left); 16610447Snilay@cs.wisc.edu 16710447Snilay@cs.wisc.edu return delay_left; 16810447Snilay@cs.wisc.edu 16910447Snilay@cs.wisc.edu } 17010447Snilay@cs.wisc.edu 17110447Snilay@cs.wisc.edu double ElectricalTimingTree::calculateCritPathDelay(ElectricalTimingNode* node_) const 17210447Snilay@cs.wisc.edu { 17310447Snilay@cs.wisc.edu // Simplest case where theres nothing to optimize 17410447Snilay@cs.wisc.edu if (node_ == NULL) 17510447Snilay@cs.wisc.edu return 0.0; 17610447Snilay@cs.wisc.edu 17710447Snilay@cs.wisc.edu double delay = 0.0; 17810447Snilay@cs.wisc.edu int crit_path = 0; 17910447Snilay@cs.wisc.edu 18010447Snilay@cs.wisc.edu // Traverse the critical path and sum up delays 18110447Snilay@cs.wisc.edu while (crit_path >= 0) 18210447Snilay@cs.wisc.edu { 18310447Snilay@cs.wisc.edu delay += node_->calculateDelay(); 18410447Snilay@cs.wisc.edu //Move on to the next node in the critical path 18510447Snilay@cs.wisc.edu crit_path = node_->getCritPath(); 18610447Snilay@cs.wisc.edu if (crit_path >= 0) 18710447Snilay@cs.wisc.edu node_ = node_->getDownstreamNodes()->at(crit_path); 18810447Snilay@cs.wisc.edu } 18910447Snilay@cs.wisc.edu return delay; 19010447Snilay@cs.wisc.edu } 19110447Snilay@cs.wisc.edu //------------------------------------------------------------------------- 19210447Snilay@cs.wisc.edu 19310447Snilay@cs.wisc.edu //------------------------------------------------------------------------- 19410447Snilay@cs.wisc.edu // Find Worst Slew Helpers 19510447Snilay@cs.wisc.edu //------------------------------------------------------------------------- 19610447Snilay@cs.wisc.edu ElectricalTimingNode* ElectricalTimingTree::findNodeForTimingOpt(ElectricalTimingNode* node_) const 19710447Snilay@cs.wisc.edu { 19810447Snilay@cs.wisc.edu // Simplest case where theres nothing to optimize 19910447Snilay@cs.wisc.edu if (node_ == NULL) 20010447Snilay@cs.wisc.edu return NULL; 20110447Snilay@cs.wisc.edu 20210447Snilay@cs.wisc.edu double max_transition_ratio = -10.0; 20310447Snilay@cs.wisc.edu double current_transition_ratio = 0.0; 20410447Snilay@cs.wisc.edu double previous_transition = 1e3 * node_->getTotalDownstreamCap(); 20510447Snilay@cs.wisc.edu double current_transition = 0.0; 20610447Snilay@cs.wisc.edu ElectricalTimingNode* worst = NULL; 20710447Snilay@cs.wisc.edu int crit_path = 0; 20810447Snilay@cs.wisc.edu 20910447Snilay@cs.wisc.edu // Find the node with the highest max_transition_ratio to return 21010447Snilay@cs.wisc.edu while (crit_path >= 0) 21110447Snilay@cs.wisc.edu { 21210447Snilay@cs.wisc.edu current_transition = node_->calculateDelay(); 21310447Snilay@cs.wisc.edu 21410447Snilay@cs.wisc.edu //If the node is not yet at max size, it is a potential choice for size up 21510447Snilay@cs.wisc.edu if (!node_->hasMaxDrivingStrength()) 21610447Snilay@cs.wisc.edu { 21710447Snilay@cs.wisc.edu current_transition_ratio = current_transition / previous_transition; 21810447Snilay@cs.wisc.edu 21910447Snilay@cs.wisc.edu if (current_transition_ratio > max_transition_ratio) 22010447Snilay@cs.wisc.edu { 22110447Snilay@cs.wisc.edu worst = node_; 22210447Snilay@cs.wisc.edu max_transition_ratio = current_transition_ratio; 22310447Snilay@cs.wisc.edu } 22410447Snilay@cs.wisc.edu } 22510447Snilay@cs.wisc.edu 22610447Snilay@cs.wisc.edu if (node_->isDriver()) 22710447Snilay@cs.wisc.edu previous_transition = 0.0; 22810447Snilay@cs.wisc.edu previous_transition += current_transition; 22910447Snilay@cs.wisc.edu 23010447Snilay@cs.wisc.edu //Move on to the next node in the critical path 23110447Snilay@cs.wisc.edu crit_path = node_->getCritPath(); 23210447Snilay@cs.wisc.edu 23310447Snilay@cs.wisc.edu if (crit_path >= 0) 23410447Snilay@cs.wisc.edu node_ = node_->getDownstreamNodes()->at(crit_path); 23510447Snilay@cs.wisc.edu } 23610447Snilay@cs.wisc.edu 23710447Snilay@cs.wisc.edu return worst; 23810447Snilay@cs.wisc.edu } 23910447Snilay@cs.wisc.edu //------------------------------------------------------------------------- 24010447Snilay@cs.wisc.edu 24110447Snilay@cs.wisc.edu double ElectricalTimingTree::calculateNodeTransition(ElectricalTimingNode* node_) const 24210447Snilay@cs.wisc.edu { 24310447Snilay@cs.wisc.edu return node_->calculateTransition(); 24410447Snilay@cs.wisc.edu } 24510447Snilay@cs.wisc.edu 24610447Snilay@cs.wisc.edu ElectricalTimingTree::ElectricalTimingTree(const ElectricalTimingTree& /* graph_ */) 24710447Snilay@cs.wisc.edu { 24810447Snilay@cs.wisc.edu // Disabled 24910447Snilay@cs.wisc.edu } 25010447Snilay@cs.wisc.edu 25110447Snilay@cs.wisc.edu ElectricalModel* ElectricalTimingTree::getModel() 25210447Snilay@cs.wisc.edu { 25310447Snilay@cs.wisc.edu return m_model_; 25410447Snilay@cs.wisc.edu } 25510447Snilay@cs.wisc.edu 25610447Snilay@cs.wisc.edu void ElectricalTimingTree::setTreeNum(int tree_num_) 25710447Snilay@cs.wisc.edu { 25810447Snilay@cs.wisc.edu msTreeNum = tree_num_; 25910447Snilay@cs.wisc.edu return; 26010447Snilay@cs.wisc.edu } 26110447Snilay@cs.wisc.edu 26210447Snilay@cs.wisc.edu int ElectricalTimingTree::getTreeNum() 26310447Snilay@cs.wisc.edu { 26410447Snilay@cs.wisc.edu return msTreeNum; 26510447Snilay@cs.wisc.edu } 26610447Snilay@cs.wisc.edu 26710447Snilay@cs.wisc.edu} // namespace DSENT 26810447Snilay@cs.wisc.edu 269