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 38namespace 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 422