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
30namespace 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
269