diff options
author | Nilay Vaish <nilay@cs.wisc.edu> | 2014-10-11 15:02:23 -0500 |
---|---|---|
committer | Nilay Vaish <nilay@cs.wisc.edu> | 2014-10-11 15:02:23 -0500 |
commit | e8ed7b1d1b5bef31e9874f679a5797c2e00d06f1 (patch) | |
tree | 421c9c50377aa664958685914f5504c4c019e21f /ext/dsent/model/timing_graph | |
parent | a098fad174d8559037602b248b8e6f7f46bfebbb (diff) | |
download | gem5-e8ed7b1d1b5bef31e9874f679a5797c2e00d06f1.tar.xz |
ext: add the source code for DSENT
This patch adds a tool called DSENT to the ext/ directory. DSENT
is a tool that models power and area for on-chip networks. The next
patch adds a script for using the tool.
Diffstat (limited to 'ext/dsent/model/timing_graph')
16 files changed, 1261 insertions, 0 deletions
diff --git a/ext/dsent/model/timing_graph/ElectricalDelay.cc b/ext/dsent/model/timing_graph/ElectricalDelay.cc new file mode 100644 index 000000000..e87a77be9 --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalDelay.cc @@ -0,0 +1,55 @@ + +#include "model/timing_graph/ElectricalDelay.h" +#include "model/timing_graph/ElectricalLoad.h" + +namespace DSENT +{ + //------------------------------------------------------------------------- + // Electrical Delay + //------------------------------------------------------------------------- + + ElectricalDelay::ElectricalDelay(const String& instance_name_, ElectricalModel* model_) + : ElectricalTimingNode(instance_name_, model_), m_delay_(0.0) + { + + } + + ElectricalDelay::~ElectricalDelay() + { + + } + + void ElectricalDelay::setDelay(double delay_) + { + m_delay_ = delay_; + return; + } + + double ElectricalDelay::getDelay() const + { + return m_delay_; + } + + double ElectricalDelay::calculateDelay() const + { + return m_delay_; + } + + double ElectricalDelay::calculateTransition() const + { + return 1.386 * getMaxUpstreamRes() * getTotalDownstreamCap(); + } + + double ElectricalDelay::getMaxUpstreamRes() const + { + return ElectricalTimingNode::getMaxUpstreamRes(); + } + + double ElectricalDelay::getTotalDownstreamCap() const + { + return ElectricalTimingNode::getTotalDownstreamCap(); + } + +} // namespace DSENT + + diff --git a/ext/dsent/model/timing_graph/ElectricalDelay.h b/ext/dsent/model/timing_graph/ElectricalDelay.h new file mode 100644 index 000000000..d3d3d3a8c --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalDelay.h @@ -0,0 +1,43 @@ +#ifndef __DSENT_MODEL_ELECTRICAL_DELAY_H__ +#define __DSENT_MODEL_ELECTRICAL_DELAY_H__ + +#include "util/CommonType.h" +#include "model/timing_graph/ElectricalTimingNode.h" + +namespace DSENT +{ + class ElectricalLoad; + + class ElectricalDelay : public ElectricalTimingNode + { + public: + ElectricalDelay(const String& instance_name_, ElectricalModel* model_); + virtual ~ElectricalDelay(); + + public: + // Specify an ideal delay + void setDelay(double delay_); + // Get the ideal delay + double getDelay() const; + // Calculate delay + double calculateDelay() const; + // Calculate transition + double calculateTransition() const; + // get maximum of upstream drive resistance + double getMaxUpstreamRes() const; + // get total amount of downstream load capacitance + double getTotalDownstreamCap() const; + + private: + // Disable copy constructor + ElectricalDelay(const ElectricalDelay& net_); + + private: + // The amount of ideal delay + double m_delay_; + }; + +} // namespace DSENT + +#endif // __DSENT_MODEL_ELECTRICAL_DELAY_H__ + diff --git a/ext/dsent/model/timing_graph/ElectricalDriver.cc b/ext/dsent/model/timing_graph/ElectricalDriver.cc new file mode 100644 index 000000000..9456ef067 --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalDriver.cc @@ -0,0 +1,95 @@ + +#include "model/timing_graph/ElectricalDriver.h" +#include "model/timing_graph/ElectricalNet.h" +#include "model/ElectricalModel.h" + +namespace DSENT +{ + ElectricalDriver::ElectricalDriver(const String& instance_name_, ElectricalModel* model_, bool sizable_) + : ElectricalTimingNode(instance_name_, model_), m_output_res_(0.0), m_sizable_(sizable_) + { + + } + + ElectricalDriver::~ElectricalDriver() + { + + } + + void ElectricalDriver::setOutputRes(double output_res_) + { + m_output_res_ = output_res_; + return; + } + + double ElectricalDriver::getOutputRes() const + { + return m_output_res_; + } + + double ElectricalDriver::calculateDelay() const + { + return 0.693 * m_output_res_ * getTotalDownstreamCap(); + } + + double ElectricalDriver::calculateTransition() const + { + return 1.386 * getMaxUpstreamRes() * getTotalDownstreamCap(); + } + + double ElectricalDriver::getMaxUpstreamRes() const + { + return m_output_res_; + } + + bool ElectricalDriver::isSizable() const + { + return m_sizable_; + } + + bool ElectricalDriver::hasMaxDrivingStrength() const + { + if (!isSizable()) + { + return true; + } + return (getModel() == NULL) || (getModel()->hasMaxDrivingStrength()); + } + + bool ElectricalDriver::hasMinDrivingStrength() const + { + if (!isSizable()) + { + return true; + } + return (getModel() == NULL) || (getModel()->hasMinDrivingStrength()); + } + + void ElectricalDriver::increaseDrivingStrength() + { + ASSERT(isSizable(), "[Error] " + getInstanceName() + + " -> Attempted to size up unsizable driver!"); + if(!hasMaxDrivingStrength()) + { + getModel()->increaseDrivingStrength(); + } + return; + } + + void ElectricalDriver::decreaseDrivingStrength() + { + ASSERT(isSizable(), "[Error] " + getInstanceName() + + " -> Attempted to size down unsizable driver!"); + if(!hasMinDrivingStrength()) + { + getModel()->decreaseDrivingStrength(); + } + return; + } + + bool ElectricalDriver::isDriver() const + { + return true; + } +} // namespace DSENT + diff --git a/ext/dsent/model/timing_graph/ElectricalDriver.h b/ext/dsent/model/timing_graph/ElectricalDriver.h new file mode 100644 index 000000000..604206b5d --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalDriver.h @@ -0,0 +1,57 @@ +#ifndef __DSENT_MODEL_ELECTRICAL_DRIVER_H__ +#define __DSENT_MODEL_ELECTRICAL_DRIVER_H__ + +#include "util/CommonType.h" +#include "model/timing_graph/ElectricalTimingNode.h" + +namespace DSENT +{ + class ElectricalModel; + + class ElectricalDriver : public ElectricalTimingNode + { + public: + ElectricalDriver(const String& instance_name_, ElectricalModel* model_, bool sizable_); + virtual ~ElectricalDriver(); + + public: + // Set the output resistance of this driver + void setOutputRes(double output_res_); + // Get the output resistance of this driver + double getOutputRes() const; + // Calculate delay due to total load capacitance + double calculateDelay() const; + // Calculate transition + double calculateTransition() const; + // get maximum of upstream drive resistance + double getMaxUpstreamRes() const; + + // Get whether the driver is sizable + bool isSizable() const; + // Return true if the instance has minimum driving strength + bool hasMinDrivingStrength() const; + // Return true if the instance has maximum driving strength + bool hasMaxDrivingStrength() const; + // Increase driving strength index by 1 + void increaseDrivingStrength(); + // Decrease driving strength index by 1 + void decreaseDrivingStrength(); + + bool isDriver() const; + + private: + // Disable copy constructor + ElectricalDriver(const ElectricalDriver& port_); + + private: + // Name of this instance + String m_instance_name_; + // Output resistance + double m_output_res_; + // Sizable flag + bool m_sizable_; + }; +} // namespace DSENT + +#endif // __DSENT_MODEL_ELECTRICAL_DRIVER_H__ + diff --git a/ext/dsent/model/timing_graph/ElectricalDriverMultiplier.cc b/ext/dsent/model/timing_graph/ElectricalDriverMultiplier.cc new file mode 100644 index 000000000..bf8600fd8 --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalDriverMultiplier.cc @@ -0,0 +1,53 @@ + +#include "model/timing_graph/ElectricalDriverMultiplier.h" +#include "model/timing_graph/ElectricalLoad.h" + +namespace DSENT +{ + //------------------------------------------------------------------------- + // Electrical Net + //------------------------------------------------------------------------- + + ElectricalDriverMultiplier::ElectricalDriverMultiplier(const String& instance_name_, ElectricalModel* model_) + : ElectricalTimingNode(instance_name_, model_) + { + + } + + ElectricalDriverMultiplier::~ElectricalDriverMultiplier() + { + + } + + double ElectricalDriverMultiplier::calculateDriveRes( double input_drive_res_) const + { + return input_drive_res_; + } + + double ElectricalDriverMultiplier::calculateDelay() const + { + // This is just a model helper element, it does not contribute delay + return 0; + } + + double ElectricalDriverMultiplier::calculateTransition() const + { + return getMaxUpstreamRes() * getTotalDownstreamCap(); + } + + double ElectricalDriverMultiplier::getTotalDownstreamCap() const + { + // Finds the max of the load caps (as opposed to summing) + double max_cap = 0; + vector<ElectricalTimingNode*>* downstream_nodes = ElectricalTimingNode::getDownstreamNodes(); + for (unsigned int i = 0; i < downstream_nodes->size(); ++i) + { + max_cap = std::max(max_cap, downstream_nodes->at(i)->getTotalDownstreamCap()); + } + + return max_cap; + } + +} // namespace DSENT + + diff --git a/ext/dsent/model/timing_graph/ElectricalDriverMultiplier.h b/ext/dsent/model/timing_graph/ElectricalDriverMultiplier.h new file mode 100644 index 000000000..62b14569f --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalDriverMultiplier.h @@ -0,0 +1,42 @@ +#ifndef __DSENT_MODEL_ELECTRICAL_DRIVER_MULTIPLIER_H__ +#define __DSENT_MODEL_ELECTRICAL_DRIVER_MULTIPLIER_H__ + +#include "util/CommonType.h" +#include "model/timing_graph/ElectricalTimingNode.h" + +namespace DSENT +{ + // Simple class that can be used to mimic the presence of multiple drivers + // output drivers (each driving one of the downstream loads) when only one + // such driver has been instantiated (such as models that take advantage of + // bit duplicattion). When the downsream loads differ in load cap, it + // just returns the largest of the caps + class ElectricalDriverMultiplier : public ElectricalTimingNode + { + public: + ElectricalDriverMultiplier(const String& instance_name_, ElectricalModel* model_); + virtual ~ElectricalDriverMultiplier(); + + public: + // Calculate drive resistance of this node; + double calculateDriveRes(double input_drive_res_) const; + // Calculate wiring delay (or net delay) + double calculateDelay() const; + // Calculate transition + double calculateTransition() const; + // get total amount of downstream load capacitance + double getTotalDownstreamCap() const; + + private: + // Disable copy constructor + ElectricalDriverMultiplier(const ElectricalDriverMultiplier& net_); + + private: + // Name of this instance + String m_instance_name_; + }; + +} // namespace DSENT + +#endif // __DSENT_MODEL_ELECTRICAL_DRIVER_MULTIPLIER_H__ + diff --git a/ext/dsent/model/timing_graph/ElectricalLoad.cc b/ext/dsent/model/timing_graph/ElectricalLoad.cc new file mode 100644 index 000000000..a20d6459d --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalLoad.cc @@ -0,0 +1,49 @@ + +#include "model/timing_graph/ElectricalLoad.h" +#include "model/ElectricalModel.h" +#include "model/timing_graph/ElectricalDriver.h" + +namespace DSENT +{ + ElectricalLoad::ElectricalLoad(const String& instance_name_, ElectricalModel* model_) + : ElectricalTimingNode(instance_name_, model_), m_load_cap_(0.0) + { + } + + ElectricalLoad::~ElectricalLoad() + { + } + + void ElectricalLoad::setLoadCap(double load_cap_) + { + m_load_cap_ = load_cap_; + return; + } + + double ElectricalLoad::getLoadCap() const + { + return m_load_cap_; + } + + bool ElectricalLoad::isLoad() const + { + return true; + } + + double ElectricalLoad::calculateDelay() const + { + return 0; + } + + double ElectricalLoad::calculateTransition() const + { + return 1.386 * getMaxUpstreamRes() * getTotalDownstreamCap(); + } + + double ElectricalLoad::getTotalDownstreamCap() const + { + return m_load_cap_; + } + +} // namespace DSENT + diff --git a/ext/dsent/model/timing_graph/ElectricalLoad.h b/ext/dsent/model/timing_graph/ElectricalLoad.h new file mode 100644 index 000000000..551eccf85 --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalLoad.h @@ -0,0 +1,43 @@ +#ifndef __DSENT_MODEL_ELECTRICAL_LOAD_H__ +#define __DSENT_MODEL_ELECTRICAL_LOAD_H__ + +#include "util/CommonType.h" +#include "model/timing_graph/ElectricalTimingNode.h" + +namespace DSENT +{ + class ElectricalModel; + class ElectricalDriver; + + class ElectricalLoad : public ElectricalTimingNode + { + public: + ElectricalLoad(const String& instance_name_, ElectricalModel* model_); + virtual ~ElectricalLoad(); + + public: + // Set the input capacitance of this input port + void setLoadCap(double load_cap_); + // Get the load capacitance + double getLoadCap() const; + // Get total load capacitance + double getTotalDownstreamCap() const; + // Calculate delay due to total load capacitance + double calculateDelay() const; + // Calculate transition + double calculateTransition() const; + + bool isLoad() const; + + private: + // Disable copy constructor + ElectricalLoad(const ElectricalLoad& load_); + + private: + // Load capacitance + double m_load_cap_; + }; +} // namespace DSENT + +#endif // __DSENT_MODEL_ELECTRICAL_LOAD_H__ + diff --git a/ext/dsent/model/timing_graph/ElectricalNet.cc b/ext/dsent/model/timing_graph/ElectricalNet.cc new file mode 100644 index 000000000..09baa77e5 --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalNet.cc @@ -0,0 +1,73 @@ + +#include "model/timing_graph/ElectricalNet.h" +#include "model/timing_graph/ElectricalLoad.h" + +namespace DSENT +{ + //------------------------------------------------------------------------- + // Electrical Net + //------------------------------------------------------------------------- + + ElectricalNet::ElectricalNet(const String& instance_name_, ElectricalModel* model_) + : ElectricalTimingNode(instance_name_, model_), m_distributed_res_(0), m_distributed_cap_(0) + { + + } + + ElectricalNet::~ElectricalNet() + { + + } + + double ElectricalNet::calculateDelay() const + { + // Remember that this is a pi model, delay is distributed cap * distributed_res / 2 + + // distributed res * (other downstream caps) + return 0.693 * (getTotalDownstreamCap() - m_distributed_cap_ / 2) * m_distributed_res_; + } + + double ElectricalNet::calculateTransition() const + { + return 1.386 * getMaxUpstreamRes() * (m_distributed_cap_ * 0.2 + ElectricalTimingNode::getTotalDownstreamCap()); + } + + double ElectricalNet::getMaxUpstreamRes() const + { + return m_distributed_res_ + ElectricalTimingNode::getMaxUpstreamRes(); + } + + double ElectricalNet::getTotalDownstreamCap() const + { + return m_distributed_cap_ + ElectricalTimingNode::getTotalDownstreamCap(); + } + + void ElectricalNet::setDistributedCap(double distributed_cap_) + { + m_distributed_cap_ = distributed_cap_; + return; + } + + void ElectricalNet::setDistributedRes(double distributed_res_) + { + m_distributed_res_ = distributed_res_; + return; + } + + double ElectricalNet::getDistributedCap() const + { + return m_distributed_cap_; + } + + double ElectricalNet::getDistributedRes() const + { + return m_distributed_res_; + } + + bool ElectricalNet::isNet() const + { + return true; + } + +} // namespace DSENT + + diff --git a/ext/dsent/model/timing_graph/ElectricalNet.h b/ext/dsent/model/timing_graph/ElectricalNet.h new file mode 100644 index 000000000..b96bfea91 --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalNet.h @@ -0,0 +1,50 @@ +#ifndef __DSENT_MODEL_ELECTRICAL_NET_H__ +#define __DSENT_MODEL_ELECTRICAL_NET_H__ + +#include "util/CommonType.h" +#include "model/timing_graph/ElectricalTimingNode.h" + +namespace DSENT +{ + class ElectricalLoad; + + class ElectricalNet : public ElectricalTimingNode + { + public: + ElectricalNet(const String& instance_name_, ElectricalModel* model_); + virtual ~ElectricalNet(); + + public: + // Set distributed res/cap + void setDistributedRes(double distributed_res_); + void setDistributedCap(double distributed_cap_); + // Get distributed res/cap + double getDistributedRes() const; + double getDistributedCap() const; + // Calculate wiring delay (or net delay) + double calculateDelay() const; + // Calculate transition + double calculateTransition() const; + // get maximum of upstream drive resistance + double getMaxUpstreamRes() const; + // get total amount of downstream load capacitance + double getTotalDownstreamCap() const; + + virtual bool isNet() const; + + private: + // Disable copy constructor + ElectricalNet(const ElectricalNet& net_); + + private: + // Name of this instance + String m_instance_name_; + // Distributed capacitance and resistance of the net + double m_distributed_res_; + double m_distributed_cap_; + }; + +} // namespace DSENT + +#endif // __DSENT_MODEL_ELECTRICAL_NET_H__ + diff --git a/ext/dsent/model/timing_graph/ElectricalTimingNode.cc b/ext/dsent/model/timing_graph/ElectricalTimingNode.cc new file mode 100644 index 000000000..d8b2bfd13 --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalTimingNode.cc @@ -0,0 +1,174 @@ + +#include "model/timing_graph/ElectricalTimingNode.h" +#include "model/timing_graph/ElectricalLoad.h" + +namespace DSENT +{ + // Set the optical node initial visited num + const int ElectricalTimingNode::TIMING_NODE_INIT_VISITED_NUM = 0; + + ElectricalTimingNode::ElectricalTimingNode(const String& instance_name_, ElectricalModel* model_) + : m_instance_name_(instance_name_), m_model_(model_), m_false_path_(false), m_crit_path_(-1), + m_visited_num_(ElectricalTimingNode::TIMING_NODE_INIT_VISITED_NUM), m_delay_left_(0.0) + { + m_upstream_nodes_ = new vector<ElectricalTimingNode*>(); + m_downstream_nodes_ = new vector<ElectricalTimingNode*>(); + } + + ElectricalTimingNode::~ElectricalTimingNode() + { + delete m_upstream_nodes_; + delete m_downstream_nodes_; + } + + double ElectricalTimingNode::getMaxUpstreamRes() const + { + double max_res = 0.0; + + for(unsigned int i = 0; i < m_upstream_nodes_->size(); ++i) + { + double res = m_upstream_nodes_->at(i)->getMaxUpstreamRes(); + if(max_res < res) + { + max_res = res; + } + } + return max_res; + } + + double ElectricalTimingNode::getTotalDownstreamCap() const + { + double cap_sum = 0; + + for(unsigned int i = 0; i < m_downstream_nodes_->size(); ++i) + { + cap_sum += m_downstream_nodes_->at(i)->getTotalDownstreamCap(); + } + + return cap_sum; + } + + vector<ElectricalTimingNode*>* ElectricalTimingNode::getUpstreamNodes() const + { + return m_upstream_nodes_; + } + + vector<ElectricalTimingNode*>* ElectricalTimingNode::getDownstreamNodes() const + { + return m_downstream_nodes_; + } + + const String& ElectricalTimingNode::getInstanceName() const + { + return m_instance_name_; + } + + ElectricalModel* ElectricalTimingNode::getModel() + { + return m_model_; + } + + bool ElectricalTimingNode::isDriver() const + { + return false; + } + + bool ElectricalTimingNode::isNet() const + { + return false; + } + + bool ElectricalTimingNode::isLoad() const + { + return false; + } + + + const ElectricalModel* ElectricalTimingNode::getModel() const + { + return (const ElectricalModel*) m_model_; + } + + void ElectricalTimingNode::addDownstreamNode(ElectricalTimingNode* node_) + { + m_downstream_nodes_->push_back(node_); + node_->m_upstream_nodes_->push_back(this); + return; + } + + void ElectricalTimingNode::setFalsePath(bool false_path_) + { + m_false_path_ = false_path_; + return; + } + + bool ElectricalTimingNode::getFalsePath() const + { + return m_false_path_; + } + + + //------------------------------------------------------------------------- + // Functions for delay optimization + //------------------------------------------------------------------------- + // By default, electrical timing nodes cannot be sized up/down + bool ElectricalTimingNode::hasMaxDrivingStrength() const + { + return true; + } + + bool ElectricalTimingNode::hasMinDrivingStrength() const + { + return true; + } + + void ElectricalTimingNode::increaseDrivingStrength() + { + return; + } + + void ElectricalTimingNode::decreaseDrivingStrength() + { + return; + } + //------------------------------------------------------------------------- + + //------------------------------------------------------------------------- + // Node variables for critical path delay calculations + //------------------------------------------------------------------------- + void ElectricalTimingNode::setCritPath(int crit_path_) + { + m_crit_path_ = crit_path_; + return; + } + + int ElectricalTimingNode::getCritPath() const + { + return m_crit_path_; + } + + void ElectricalTimingNode::setVisitedNum(int visited_num_) + { + m_visited_num_ = visited_num_; + return; + } + + int ElectricalTimingNode::getVisitedNum() const + { + return m_visited_num_; + } + + void ElectricalTimingNode::setDelayLeft(double delay_left_) + { + m_delay_left_ = delay_left_; + } + + double ElectricalTimingNode::getDelayLeft() const + { + return m_delay_left_; + } + //------------------------------------------------------------------------- + +} // namespace DSENT + + diff --git a/ext/dsent/model/timing_graph/ElectricalTimingNode.h b/ext/dsent/model/timing_graph/ElectricalTimingNode.h new file mode 100644 index 000000000..01c6497da --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalTimingNode.h @@ -0,0 +1,104 @@ +#ifndef __DSENT_MODEL_ELECTRICAL_TIMING_NODE_H__ +#define __DSENT_MODEL_ELECTRICAL_TIMING_NODE_H__ + +#include "util/CommonType.h" + +namespace DSENT +{ + class ElectricalModel; + + class ElectricalTimingNode + { + public: + // The starting visited number flag of all timing nodes + static const int TIMING_NODE_INIT_VISITED_NUM; + + public: + ElectricalTimingNode(const String& instance_name_, ElectricalModel* model_); + virtual ~ElectricalTimingNode(); + + public: + + // Calculate the delay this node contributes + virtual double calculateDelay() const = 0; + // Calculate the transition at this node + virtual double calculateTransition() const = 0; + // get maximum of upstream drive resistance + virtual double getMaxUpstreamRes() const; + // get total amount of downstream load capacitance + virtual double getTotalDownstreamCap() const; + // Return instance name + const String& getInstanceName() const; + // get upstream timing nodes + vector<ElectricalTimingNode*>* getUpstreamNodes() const; + // get downstream timing nodes + vector<ElectricalTimingNode*>* getDownstreamNodes() const; + // Connect a downstream timing node + void addDownstreamNode(ElectricalTimingNode* node_); + // Return the node's parent model + ElectricalModel* getModel(); + const ElectricalModel* getModel() const; + // Set/get false path marker + void setFalsePath(bool false_path_); + bool getFalsePath() const; + + virtual bool isDriver() const; + virtual bool isNet() const; + virtual bool isLoad() const; + + + //----------------------------------------------------------------- + // Functions for delay optimization + //----------------------------------------------------------------- + // Return true if the instance has minimum driving strength + virtual bool hasMinDrivingStrength() const; + // Return true if the instance has maximum driving strength + virtual bool hasMaxDrivingStrength() const; + // Increase driving strength index by 1 + virtual void increaseDrivingStrength(); + // Decrease driving strength index by 1 + virtual void decreaseDrivingStrength(); + //----------------------------------------------------------------- + + //----------------------------------------------------------------- + // Node variables for critical path delay calculations + //----------------------------------------------------------------- + // Critical path marker + void setCritPath(int crit_path_); + int getCritPath() const; + // Visited parity marker + void setVisitedNum(int visited_parity_); + int getVisitedNum() const; + // Delay left in this path + void setDelayLeft(double delay_left_); + double getDelayLeft() const; + //----------------------------------------------------------------- + + + private: + // Disable copy constructor + ElectricalTimingNode(const ElectricalTimingNode& node_); + + private: + // Name of this instance + String m_instance_name_; + // A pointer to the model that contains this node + ElectricalModel* m_model_; + // Upstream electrical nets + vector<ElectricalTimingNode*>* m_upstream_nodes_; + // Downstream electrical nets + vector<ElectricalTimingNode*>* m_downstream_nodes_; + // False path marker + bool m_false_path_; + // Critical path index (to next downstream node) + int m_crit_path_; + // Odd / even path visited (so that you don't have to clear it) + int m_visited_num_; + // The amount of delay left to the end of the timing path + double m_delay_left_; + }; + +} // namespace DSENT + +#endif // __DSENT_MODEL_ELECTRICAL_TIMING_NODE_H__ + diff --git a/ext/dsent/model/timing_graph/ElectricalTimingOptimizer.cc b/ext/dsent/model/timing_graph/ElectricalTimingOptimizer.cc new file mode 100644 index 000000000..dd7b4330a --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalTimingOptimizer.cc @@ -0,0 +1,73 @@ +#include "model/timing_graph/ElectricalTimingOptimizer.h" + +#include "model/PortInfo.h" +#include "model/ModelGen.h" +#include "model/std_cells/StdCell.h" +#include "model/std_cells/StdCellLib.h" +#include "model/timing_graph/ElectricalNet.h" +#include "model/timing_graph/ElectricalTimingTree.h" + +namespace DSENT +{ + ElectricalTimingOptimizer::ElectricalTimingOptimizer(const String& instance_name_, const TechModel* tech_model_) + : ElectricalModel(instance_name_, tech_model_), m_model_(NULL) + {} + + ElectricalTimingOptimizer::~ElectricalTimingOptimizer() + {} + + void ElectricalTimingOptimizer::setModel(ElectricalModel* model_) + { + m_model_ = model_; + return; + } + + ElectricalModel* ElectricalTimingOptimizer::getModel() + { + return m_model_; + } + + void ElectricalTimingOptimizer::constructModel() + { + if(getModel() == NULL) + { + return; + } + + const Map<PortInfo*>* port_info = getModel()->getInputs(); + Map<PortInfo*>::ConstIterator it_begin = port_info->begin(); + Map<PortInfo*>::ConstIterator it_end = port_info->end(); + Map<PortInfo*>::ConstIterator it; + + for(it = it_begin; it != it_end; ++it) + { + const String& port_name = it->first; + const PortInfo* port_info = it->second; + StdCell* inv0 = getTechModel()->getStdCellLib()->createStdCell("INV", port_name + "Driver0"); + inv0->construct(); + StdCell* inv1 = getTechModel()->getStdCellLib()->createStdCell("INV", port_name + "Driver1"); + inv1->construct(); + + addSubInstances(inv0, 1.0); + addSubInstances(inv1, 1.0); + + createInputPort(port_name, port_info->getNetIndex()); + createNet(port_name + "Driver0In"); + createNet(port_name + "Driver0Out"); + createNet(port_name + "Driver1Out"); + assignVirtualFanin(port_name + "Driver0In", port_name); + portConnect(inv0, "A", port_name + "Driver0In"); + portConnect(inv0, "Y", port_name + "Driver0Out"); + portConnect(inv1, "A", port_name + "Driver0Out"); + portConnect(inv1, "Y", port_name + "Driver1Out"); + + createNet(port_name + "In", port_info->getNetIndex()); + assignVirtualFanout(port_name + "In", port_name + "Driver1Out"); + + portConnect(getModel(), port_name, port_name + "In"); + } + + return; + } +}// namespace DSENT + diff --git a/ext/dsent/model/timing_graph/ElectricalTimingOptimizer.h b/ext/dsent/model/timing_graph/ElectricalTimingOptimizer.h new file mode 100644 index 000000000..c0c850e0b --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalTimingOptimizer.h @@ -0,0 +1,30 @@ +#ifndef __DSENT_MODEL_TIMING_GRAPH_ELECTRICAL_TIMING_OPTIMIZER_H__ +#define __DSENT_MODEL_TIMING_GRAPH_ELECTRICAL_TIMING_OPTIMIZER_H__ + +#include "util/CommonType.h" +#include "model/ElectricalModel.h" + +namespace DSENT +{ + // This model is only used to optimize the timing + class ElectricalTimingOptimizer : public ElectricalModel + { + public: + ElectricalTimingOptimizer(const String& instance_name_, const TechModel* tech_model_); + virtual ~ElectricalTimingOptimizer(); + + public: + void setModel(ElectricalModel* model_); + ElectricalModel* getModel(); + + protected: + // Build the optimizer + virtual void constructModel(); + + private: + ElectricalModel* m_model_; + }; // class ElectricalTimingOptimizer +} // namespace + +#endif // __DSENT_MODEL_TIMING_GRAPH_ELECTRICAL_TIMING_OPTIMIZER_H__ + diff --git a/ext/dsent/model/timing_graph/ElectricalTimingTree.cc b/ext/dsent/model/timing_graph/ElectricalTimingTree.cc new file mode 100644 index 000000000..83d583c53 --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalTimingTree.cc @@ -0,0 +1,247 @@ + +#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<ElectricalTimingNode*>* 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 + diff --git a/ext/dsent/model/timing_graph/ElectricalTimingTree.h b/ext/dsent/model/timing_graph/ElectricalTimingTree.h new file mode 100644 index 000000000..4dfbff8a7 --- /dev/null +++ b/ext/dsent/model/timing_graph/ElectricalTimingTree.h @@ -0,0 +1,73 @@ +#ifndef __DSENT_MODEL_ELECTRICAL_TIMING_TREE_H__ +#define __DSENT_MODEL_ELECTRICAL_TIMING_TREE_H__ + +#include <vector> + +#include "util/CommonType.h" +#include "model/timing_graph/ElectricalTimingNode.h" + +namespace DSENT +{ + using std::vector; + + class ElectricalDriver; + + class ElectricalTimingTree + { + public: + // The visited number for the next timing run. This needs to be + // global because several timing trees may be created to evaluate + // a single timing path, causing problems + static int msTreeNum; + + public: + // Construct timing tree that watches over model_ + ElectricalTimingTree(const String& instance_name_, ElectricalModel* model_); + ~ElectricalTimingTree(); + + public: + // Get tree name + const String& getInstanceName() const; + + // A wrapper for extractCritPathDelay + // Update the tree num before do extract critical path delay recursively + double performCritPathExtract(ElectricalTimingNode* node_); + // Calculate the delay of the marked critical path from a starting node + double calculateCritPathDelay(ElectricalTimingNode* node_) const; + // Calculate the transition at a node + double calculateNodeTransition(ElectricalTimingNode* node_) const; + // Returns the optimal node to optimize timing (by sizing up) in the critical + // path to reduce critical path delay + ElectricalTimingNode* findNodeForTimingOpt(ElectricalTimingNode* node_) const; + // Perform incremental timing optimization to guarantee that all timing paths from a + // starting node meets a required delay + // Return false if the timing optimization fails to meet the required delay + bool performTimingOpt(ElectricalTimingNode* node_, double required_delay_); + + // Return the model + ElectricalModel* getModel(); + + private: + // Disable the use of copy constructor + ElectricalTimingTree(const ElectricalTimingTree& graph_); + + // Recursively calculate delay from a starting node, finding and marking the + // critical path along the way and returns the delay of the critical path + double extractCritPathDelay(ElectricalTimingNode* node_); + + public: + // Set the sequence number of the timing tree + static void setTreeNum(int tree_num_); + static int getTreeNum(); + + private: + // Name of the timing tree + const String m_instance_name_; + // A pointer to the model that contains this node + ElectricalModel* m_model_; + + }; // class ElectricalTimingTree +} // namespace DSENT + +#endif // __DSENT_MODEL_ELECTRICAL_TIMING_TREE_H__ + |