ext/dsent/model/electrical/BroadcastHTree.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 #include "model/electrical/BroadcastHTree.h"
  23
  24 #include <cmath>
  25 #include <vector>
  26
  27 #include "model/PortInfo.h"
  28 #include "model/EventInfo.h"
  29 #include "model/TransitionInfo.h"
  30 #include "model/std_cells/StdCellLib.h"
  31 #include "model/std_cells/StdCell.h"
  32 #include "model/timing_graph/ElectricalLoad.h"
  33 #include "model/timing_graph/ElectricalDelay.h"
  34 #include "model/timing_graph/ElectricalDriver.h"
  35 #include "model/timing_graph/ElectricalTimingTree.h"
  36 #include "model/timing_graph/ElectricalNet.h"
  37
  38 namespace DSENT
  39 {
  40     using std::pow;
  41     using std::vector;
  42
  43     BroadcastHTree::BroadcastHTree(const String& instance_name_, const TechModel* tech_model_)
  44         : ElectricalModel(instance_name_, tech_model_)
  45     {
  46         initParameters();
  47         initProperties();
  48
  49         m_leaf_load_ = NULL;
  50         m_leaf_head_driver_ = NULL;
  51         m_leaf_head_load_ = NULL;
  52     }
  53
  54     BroadcastHTree::~BroadcastHTree()
  55     {
  56         clearPtrVector<StdCell>(&m_repeaters_);
  57         clearPtrVector<ElectricalLoad>(&m_repeater_loads_);
  58         clearPtrVector<ElectricalTimingTree>(&m_timing_trees_);
  59         clearPtrVector<StdCell>(&m_leaf_drivers_);
  60         delete m_leaf_load_;
  61         delete m_leaf_head_driver_;
  62         delete m_leaf_head_load_;
  63     }
  64
  65     void BroadcastHTree::initParameters()
  66     {
  67         addParameterName("NumberLevels");
  68         addParameterName("NumberBits");
  69         addParameterName("WireLayer");
  70         addParameterName("WireWidthMultiplier", 1.0);
  71         addParameterName("WireSpacingMultiplier", 1.0);
  72         return;
  73     }
  74
  75     void BroadcastHTree::initProperties()
  76     {
  77         addPropertyName("SitePitch");
  78         addPropertyName("TotalLoadCapPerBit");
  79         return;
  80     }
  81
  82     BroadcastHTree* BroadcastHTree::clone() const
  83     {
  84         // TODO
  85         return NULL;
  86     }
  87
  88     void BroadcastHTree::constructModel()
  89     {
  90         // Get parameters
  91         unsigned int number_levels = getParameter("NumberLevels").toUInt();
  92         unsigned int number_bits = getParameter("NumberBits").toUInt();
  93         const String& wire_layer = getParameter("WireLayer");
  94         double wire_width_multiplier = getParameter("WireWidthMultiplier").toDouble();
  95         double wire_spacing_multiplier = getParameter("WireSpacingMultiplier").toDouble();
  96
  97         ASSERT(number_levels > 0, "[Error] " + getInstanceName() +
  98                 " -> Number of levels must be > 0!");
  99         ASSERT(number_bits > 0, "[Error] " + getInstanceName() +
 100                 " -> Number of bits must be > 0!");
 101         ASSERT(getTechModel()->isWireLayerExist(wire_layer), "[Error] " + getInstanceName() +
 102                 " -> Wire layer does not exist!");
 103         ASSERT(wire_width_multiplier >= 1.0, "[Error] " + getInstanceName() +
 104                 " -> Wire width multiplier must be >= 1.0!");
 105         ASSERT(wire_spacing_multiplier >= 1.0, "[Error] " + getInstanceName() +
 106                 " -> Wire spacing multiplier must be >= 1.0!");
 107
 108         double wire_min_width = getTechModel()->get("Wire->" + wire_layer + "->MinWidth").toDouble();
 109         double wire_min_spacing = getTechModel()->get("Wire->" + wire_layer + "->MinSpacing").toDouble();
 110
 111         double wire_width = wire_min_width * wire_width_multiplier;
 112         double wire_spacing = wire_min_spacing * wire_spacing_multiplier;
 113
 114         double wire_cap_per_len = getTechModel()->calculateWireCapacitance(wire_layer, wire_width, wire_spacing, 1.0);
 115         double wire_res_per_len = getTechModel()->calculateWireResistance(wire_layer, wire_width, 1.0);
 116
 117         getGenProperties()->set("WireWidth", wire_width);
 118         getGenProperties()->set("WireSpacing", wire_spacing);
 119         getGenProperties()->set("WireCapacitancePerLength", wire_cap_per_len);
 120         getGenProperties()->set("WireResistancePerLength", wire_res_per_len);
 121
 122         // Create ports
 123         createInputPort("In", makeNetIndex(0, number_bits-1));
 124         createOutputPort("Out", makeNetIndex(0, number_bits-1));
 125
 126         // Create connections
 127         createNet("InTmp");
 128         createNet("OutTmp");
 129         assignVirtualFanin("InTmp", "In");
 130         assignVirtualFanout("Out", "OutTmp");
 131
 132         createLoad("In_Cap");
 133         createDelay("In_to_Out_delay");
 134
 135         ElectricalLoad* in_cap = getLoad("In_Cap");
 136         ElectricalDelay* in_to_out_delay = getDelay("In_to_Out_delay");
 137
 138         getNet("InTmp")->addDownstreamNode(in_cap);
 139         in_cap->addDownstreamNode(in_to_out_delay);
 140
 141         // Init
 142         for(unsigned int i = 0; i < number_levels; ++i)
 143         {
 144             StdCell* repeater = getTechModel()->getStdCellLib()->createStdCell("INV", "Repeater" + (String)i);
 145             ElectricalLoad* repeater_load = new ElectricalLoad("RepeaterIn_Cap" + (String)i, this);
 146             ElectricalTimingTree* timing_tree = new ElectricalTimingTree("RepeatedLink" + (String)i, this);
 147
 148             repeater->construct();
 149             repeater->getNet("Y")->addDownstreamNode(repeater_load);
 150             m_repeaters_.push_back(repeater);
 151             m_repeater_loads_.push_back(repeater_load);
 152             m_timing_trees_.push_back(timing_tree);
 153         }
 154
 155         // Create area, power, and event results
 156         createElectricalAtomicResults();
 157         createElectricalEventResult("Send");
 158         addEventResult(new AtomicResult("DriveLoad"));
 159         addEventResult(new AtomicResult("DriveTree"));
 160
 161         getEventResult("Send")->addSubResult(getEventResult("DriveLoad"), "Self", 1.0);
 162         getEventResult("Send")->addSubResult(getEventResult("DriveTree"), "Self", 1.0);
 163         return;
 164     }
 165
 166     void BroadcastHTree::updateModel()
 167     {
 168         // Get properties
 169         double site_pitch = getProperty("SitePitch").toDouble();
 170         double total_load_cap_per_bit = getProperty("TotalLoadCapPerBit").toDouble();
 171
 172         ASSERT(site_pitch > 0, "[Error] " + getInstanceName() +
 173                 " -> Site pitch must be > 0!");
 174         ASSERT(total_load_cap_per_bit >= 0.0, "[Error] " + getInstanceName() +
 175                 " -> Total load capacitance per bit must be >= 0!");
 176
 177         // Get parameters
 178         unsigned int number_levels = getParameter("NumberLevels");
 179         unsigned int number_bits = getParameter("NumberBits");
 180
 181         const String& wire_layer = getParameter("WireLayer");
 182         double wire_width = getGenProperties()->get("WireWidth").toDouble();
 183         double wire_spacing = getGenProperties()->get("WireSpacing").toDouble();
 184         double wire_cap_per_len = getGenProperties()->get("WireCapacitancePerLength").toDouble();
 185         double wire_res_per_len = getGenProperties()->get("WireResistancePerLength").toDouble();
 186
 187         double leaf_load_cap = total_load_cap_per_bit / pow(2.0, (double)(number_levels-1));
 188
 189         vector<double> wire_caps(number_levels, 0.0);
 190         vector<double> wire_ress(number_levels, 0.0);
 191         double wire_length = site_pitch / 2.0;
 192         for(unsigned int i = 0; i < number_levels; ++i)
 193         {
 194             wire_caps[i] = wire_cap_per_len * wire_length;
 195             wire_ress[i] = wire_res_per_len * wire_length;
 196             wire_length /= 2.0;
 197         }
 198
 199         // Start sizing each stage of repeaters for a transition times. TODO: Find a heuristic about
 200         // how the transition time is done...place and route tools make this user-specified
 201         double required_transition = 40e-12;
 202         m_number_segments_.resize(number_levels, 1);
 203         for(unsigned int i = 0; i < number_levels; ++i)
 204         {
 205             Log::printLine(getInstanceName() + " -> Beginning Repeater Insertion " + (String)i);
 206
 207             double transition;
 208             unsigned int iteration = 0;
 209             m_repeaters_[i]->setMinDrivingStrength();
 210             m_repeaters_[i]->getNet("Y")->setDistributedCap(wire_caps[i] / m_number_segments_[i]);
 211             m_repeaters_[i]->getNet("Y")->setDistributedRes(wire_ress[i] / m_number_segments_[i]);
 212             m_repeater_loads_[i]->setLoadCap(m_repeaters_[i]->getNet("A")->getTotalDownstreamCap());
 213
 214             transition = m_timing_trees_[i]->calculateNodeTransition(m_repeaters_[i]->getNet("Y"));
 215
 216             while(required_transition < transition)
 217             {
 218                 Log::printLine(getInstanceName() + " -> Repeater Insertion Iteration " + (String)iteration +
 219                         ": Required transition = " + (String)required_transition +
 220                         ", Transition = " + (String)transition +
 221                         ", Slack = " + (String)(required_transition - transition) +
 222                         ", Number of repeaters = " + (String)m_number_segments_[i]);
 223
 224                 // Size up if transition is not met
 225                 while(required_transition < transition)
 226                 {
 227                     if(m_repeaters_[i]->hasMaxDrivingStrength())
 228                     {
 229                         break;
 230                     }
 231                     m_repeaters_[i]->increaseDrivingStrength();
 232                     m_repeater_loads_[i]->setLoadCap(m_repeaters_[i]->getNet("A")->getTotalDownstreamCap());
 233                     transition = m_timing_trees_[i]->calculateNodeTransition(m_repeaters_[i]->getNet("Y"));
 234
 235                     iteration++;
 236                     Log::printLine(getInstanceName() + " -> Slack: " + (String)(required_transition - transition));
 237                 }
 238                 // Increase number of segments if thansition is not met
 239                 if(required_transition < transition)
 240                 {
 241                     m_number_segments_[i]++;
 242                     m_repeaters_[i]->setMinDrivingStrength();
 243                     m_repeaters_[i]->getNet("Y")->setDistributedCap(wire_caps[i] / m_number_segments_[i]);
 244                     m_repeaters_[i]->getNet("Y")->setDistributedRes(wire_ress[i] / m_number_segments_[i]);
 245                     m_repeater_loads_[i]->setLoadCap(m_repeaters_[i]->getNet("A")->getTotalDownstreamCap());
 246                     transition = m_timing_trees_[i]->calculateNodeTransition(m_repeaters_[i]->getNet("Y"));
 247                 }
 248             }
 249             Log::printLine(getInstanceName() + " -> Repeater Insertion " + (String)i + " Ended after Iteration: " + (String)iteration +
 250                     ": Required transition = " + (String)required_transition +
 251                     ", Transition = " + (String)transition +
 252                     ", Slack = " + (String)(required_transition - transition) +
 253                     ", Number of repeaters = " + (String)m_number_segments_[i]);
 254         }
 255
 256         // Insert inverters to ensure the transition time at the leaf
 257         int min_driving_strength_idx = m_repeaters_[number_levels-1]->getDrivingStrengthIdx();
 258
 259         // Remove everything and rebuild again
 260         clearPtrVector<StdCell>(&m_leaf_drivers_);
 261         delete m_leaf_load_;
 262         delete m_leaf_head_driver_;
 263         delete m_leaf_head_load_;
 264
 265         m_leaf_head_driver_ = getTechModel()->getStdCellLib()->createStdCell("INV", "LeafHeadDriver");
 266         m_leaf_head_driver_->construct();
 267         m_leaf_head_driver_->setDrivingStrengthIdx(min_driving_strength_idx);
 268
 269         m_leaf_head_load_ = new ElectricalLoad("LeafHead_Cap", this);
 270         m_leaf_head_driver_->getNet("Y")->addDownstreamNode(m_leaf_head_load_);
 271
 272         m_leaf_load_ = new ElectricalLoad("Leaf_Cap", this);
 273         m_leaf_load_->setLoadCap(leaf_load_cap);
 274
 275         StdCell* inv = getTechModel()->getStdCellLib()->createStdCell("INV", "LeafDriver0");
 276         inv->construct();
 277         inv->getNet("Y")->addDownstreamNode(m_leaf_load_);
 278         inv->setDrivingStrengthIdx(min_driving_strength_idx);
 279         m_leaf_drivers_.push_back(inv);
 280
 281         m_leaf_head_load_->setLoadCap(m_leaf_drivers_[0]->getNet("A")->getTotalDownstreamCap());
 282
 283         // Start inserting the buffers
 284         ElectricalTimingTree t2("LeafHead", m_leaf_head_driver_);
 285         int curr_driver = 0;
 286         unsigned int iteration = 0;
 287         while(true)
 288         {
 289             ElectricalTimingTree t("LeafDriver", m_leaf_drivers_[curr_driver]);
 290             double transition = t.calculateNodeTransition(m_leaf_drivers_[curr_driver]->getNet("Y"));
 291             Log::printLine(getInstanceName() + " -> Buffer Insertion : " + (String)iteration +
 292                     ": Required transition = " + (String)required_transition +
 293                     ", Transition = " + (String)transition +
 294                     ", Slack = " + (String)(required_transition - transition) +
 295                     ", Number of buffers = " + (String)(curr_driver+1));
 296
 297             // Size up the inverter at curr_driver so that it could drive the next stage
 298             while(required_transition < transition)
 299             {
 300                 if(m_leaf_drivers_[curr_driver]->hasMaxDrivingStrength())
 301                 {
 302                     const String& warning_msg = "[Warning] " + getInstanceName() + " -> Transition not met" +
 303                         ": Required transition = " + (String)required_transition +
 304                         ", Transition = " + (String)transition +
 305                         ", Slack = " + (String)(required_transition - transition);
 306                     Log::printLine(std::cerr, warning_msg);
 307                     break;
 308                 }
 309                 m_leaf_drivers_[curr_driver]->increaseDrivingStrength();
 310                 transition = t.calculateNodeTransition(m_leaf_drivers_[curr_driver]->getNet("Y"));
 311                 iteration++;
 312             }
 313             // Add an additional inverter if the transition for the first stage does not meet the required transition
 314             m_leaf_head_load_->setLoadCap(m_leaf_drivers_[curr_driver]->getNet("A")->getTotalDownstreamCap());
 315             transition = t2.calculateNodeTransition(m_leaf_head_driver_->getNet("Y"));
 316             if(required_transition < transition)
 317             {
 318                 inv = getTechModel()->getStdCellLib()->createStdCell("INV", "LeafDriver" + (String)(curr_driver+1));
 319                 inv->construct();
 320                 inv->getNet("Y")->addDownstreamNode(m_leaf_drivers_[curr_driver]->getNet("A"));
 321                 inv->setDrivingStrengthIdx(min_driving_strength_idx);
 322                 m_leaf_drivers_.push_back(inv);
 323                 curr_driver++;
 324             }
 325             else
 326             {
 327                 Log::printLine(getInstanceName() + " -> Buffer Insertion Ended after Iteration: " + (String)iteration +
 328                         ", Number of buffers = " + (String)(curr_driver+1));
 329                 break;
 330             }
 331         }
 332
 333
 334         // Update electrical interfaces
 335         getLoad("In_Cap")->setLoadCap(m_repeaters_[0]->getNet("A")->getTotalDownstreamCap());
 336         // TODO
 337         getDelay("In_to_Out_delay")->setDelay(0.0);
 338
 339         // Reset all the atomic results to 0 before start updating new results
 340         resetElectricalAtomicResults();
 341
 342         // Update area, power results
 343         double wire_area = 0.0;
 344         wire_length = site_pitch / 2.0;
 345         unsigned int number_branches = 1;
 346         for(unsigned int i = 0; i < number_levels; ++i)
 347         {
 348             wire_area += wire_length * (wire_width + wire_spacing) * number_branches * number_bits;
 349             addElecticalAtomicResultValues(m_repeaters_[i], m_number_segments_[i] * number_branches * number_bits);
 350             wire_length /= 2.0;
 351             number_branches *= 2;
 352         }
 353         number_branches = (unsigned int)pow(2.0, (double)number_levels-1);
 354         addElecticalAtomicResultValues(m_leaf_head_driver_, number_branches * number_bits);
 355         for(unsigned int i = 0; i < m_leaf_drivers_.size(); ++i)
 356         {
 357             addElecticalAtomicResultValues(m_leaf_drivers_[i], number_branches * number_bits);
 358         }
 359         addElecticalWireAtomicResultValue(wire_layer, wire_area);
 360
 361         return;
 362     }
 363
 364     void BroadcastHTree::useModel()
 365     {
 366         unsigned int number_bits = getParameter("NumberBits").toUInt();
 367         unsigned int number_levels = getParameter("NumberLevels").toUInt();
 368
 369         // Update the transition information for the modeled repeaters
 370         // Since we only modeled one repeater. So the transition information for 0->0 and 1->1
 371         // is averaged out
 372         const TransitionInfo& trans_In = getInputPort("In")->getTransitionInfo();
 373         double average_static_transition = (trans_In.getNumberTransitions00() + trans_In.getNumberTransitions11()) / 2.0;
 374         TransitionInfo mod_trans_In(average_static_transition, trans_In.getNumberTransitions01(), average_static_transition);
 375
 376         // Propagate the transition information
 377         propagateTransitionInfo();
 378
 379         // Update leakage and event
 380         double energy = 0.0;
 381         double power = 0.0;
 382         unsigned int number_branches = 1;
 383         for(unsigned int i = 0; i < number_levels; ++i)
 384         {
 385             assignPortTransitionInfo(m_repeaters_[i], "A", mod_trans_In);
 386             m_repeaters_[i]->use();
 387             power += m_repeaters_[i]->getNddPowerResult("Leakage")->calculateSum() * m_number_segments_[i] * number_branches;
 388             energy += m_repeaters_[i]->getEventResult("INV")->calculateSum() * m_number_segments_[i] * number_branches;
 389             number_branches *= 2;
 390         }
 391         energy *= number_bits;
 392         getEventResult("DriveTree")->setValue(energy);
 393
 394         energy = 0.0;
 395         assignPortTransitionInfo(m_leaf_head_driver_, "A", mod_trans_In);
 396         m_leaf_head_driver_->use();
 397         number_branches = (unsigned int)pow(2.0, (double)number_levels-1);
 398         power += m_leaf_head_driver_->getNddPowerResult("Leakage")->calculateSum() * number_branches;
 399         energy += m_leaf_head_driver_->getEventResult("INV")->calculateSum() * number_branches;
 400         for(unsigned int i = 0; i < m_leaf_drivers_.size(); ++i)
 401         {
 402             assignPortTransitionInfo(m_leaf_drivers_[i], "A", mod_trans_In);
 403             m_leaf_drivers_[i]->use();
 404             power += m_leaf_drivers_[i]->getNddPowerResult("Leakage")->calculateSum() * number_branches;
 405             energy += m_leaf_drivers_[i]->getEventResult("INV")->calculateSum() * number_branches;
 406         }
 407         power *= number_bits;
 408         energy *= number_bits;
 409         getEventResult("DriveLoad")->setValue(energy);
 410         getNddPowerResult("Leakage")->setValue(power);
 411
 412         return;
 413     }
 414
 415     void BroadcastHTree::propagateTransitionInfo()
 416     {
 417         propagatePortTransitionInfo("Out", "In");
 418         return;
 419     }
 420 } // namespace DSENT
 421