Deleted Added
sdiff udiff text old ( 256281 ) new ( 263508 )
full compact
HeuristicBase.h (256281) HeuristicBase.h (263508)
1//===-- HeuristcBase.h --- Heuristic base class for PBQP --------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 13 unchanged lines hidden (view full) ---

22 /// To implement your own heuristic using this class as a base you'll have to
23 /// implement, as a minimum, the following methods:
24 /// <ul>
25 /// <li> void addToHeuristicList(Graph::NodeItr) : Add a node to the
26 /// heuristic reduction list.
27 /// <li> void heuristicReduce() : Perform a single heuristic reduction.
28 /// <li> void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent)
29 /// change to the cost matrix on the given edge (by R2).
1//===-- HeuristcBase.h --- Heuristic base class for PBQP --------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 13 unchanged lines hidden (view full) ---

22 /// To implement your own heuristic using this class as a base you'll have to
23 /// implement, as a minimum, the following methods:
24 /// <ul>
25 /// <li> void addToHeuristicList(Graph::NodeItr) : Add a node to the
26 /// heuristic reduction list.
27 /// <li> void heuristicReduce() : Perform a single heuristic reduction.
28 /// <li> void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent)
29 /// change to the cost matrix on the given edge (by R2).
30 /// <li> void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new
30 ///
  • void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new
    		•
    31 /// costs on the given edge.
    32 /// <li> void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new
    33 /// edge into the PBQP graph (by R2).
    34 /// <li> void handleRemoveEdge(Graph::EdgeItr, Graph::NodeItr) : Handle the
    35 /// disconnection of the given edge from the given node.
    36 /// <li> A constructor for your derived class : to pass back a reference to
    37 /// the solver which is using this heuristic.
    38 /// </ul>
    39 ///
    40 /// These methods are implemented in this class for documentation purposes,
    41 /// but will assert if called.
    		31 /// costs on the given edge.
    32 /// <li> void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new
    33 /// edge into the PBQP graph (by R2).
    34 /// <li> void handleRemoveEdge(Graph::EdgeItr, Graph::NodeItr) : Handle the
    35 /// disconnection of the given edge from the given node.
    36 /// <li> A constructor for your derived class : to pass back a reference to
    37 /// the solver which is using this heuristic.
    38 /// </ul>
    39 ///
    40 /// These methods are implemented in this class for documentation purposes,
    41 /// but will assert if called.
    42 ///
    		42 ///
    43 /// Note that this class uses the curiously recursive template idiom to
    44 /// forward calls to the derived class. These methods need not be made
    45 /// virtual, and indeed probably shouldn't for performance reasons.
    46 ///
    47 /// You'll also need to provide NodeData and EdgeData structs in your class.
    48 /// These can be used to attach data relevant to your heuristic to each
    49 /// node/edge in the PBQP graph.
    50
    51 template <typename HImpl>
    52 class HeuristicBase {
    53 private:
    54
    		43 /// Note that this class uses the curiously recursive template idiom to
    44 /// forward calls to the derived class. These methods need not be made
    45 /// virtual, and indeed probably shouldn't for performance reasons.
    46 ///
    47 /// You'll also need to provide NodeData and EdgeData structs in your class.
    48 /// These can be used to attach data relevant to your heuristic to each
    49 /// node/edge in the PBQP graph.
    50
    51 template <typename HImpl>
    52 class HeuristicBase {
    53 private:
    54
    55 typedef std::list<Graph::NodeItr> OptimalList;
    		55 typedef std::list<Graph::NodeId> OptimalList;
    56
    57 HeuristicSolverImpl<HImpl> &s;
    58 Graph &g;
    59 OptimalList optimalList;
    60
    61 // Return a reference to the derived heuristic.
    62 HImpl& impl() { return static_cast<HImpl&>(*this); }
    63
    64 // Add the given node to the optimal reductions list. Keep an iterator to
    		56
    57 HeuristicSolverImpl<HImpl> &s;
    58 Graph &g;
    59 OptimalList optimalList;
    60
    61 // Return a reference to the derived heuristic.
    62 HImpl& impl() { return static_cast<HImpl&>(*this); }
    63
    64 // Add the given node to the optimal reductions list. Keep an iterator to
    65 // its location for fast removal.
    66 void addToOptimalReductionList(Graph::NodeItr nItr) {
    67 optimalList.insert(optimalList.end(), nItr);
    		65 // its location for fast removal.
    66 void addToOptimalReductionList(Graph::NodeId nId) {
    67 optimalList.insert(optimalList.end(), nId);
    68 }
    69
    70 public:
    71
    72 /// \brief Construct an instance with a reference to the given solver.
    73 /// @param solver The solver which is using this heuristic instance.
    74 HeuristicBase(HeuristicSolverImpl<HImpl> &solver)
    75 : s(solver), g(s.getGraph()) { }

    --- 13 unchanged lines hidden (view full) ---

    89 /// @return Whether or not the solver should run a simplification phase
    90 /// prior to the main setup and reduction.
    91 ///
    92 /// HeuristicBase returns true from this method as it's a sensible default,
    93 /// however you can over-ride it in your derived class if you want different
    94 /// behaviour.
    95 bool solverRunSimplify() const { return true; }
    96
    		68 }
    69
    70 public:
    71
    72 /// \brief Construct an instance with a reference to the given solver.
    73 /// @param solver The solver which is using this heuristic instance.
    74 HeuristicBase(HeuristicSolverImpl<HImpl> &solver)
    75 : s(solver), g(s.getGraph()) { }

    --- 13 unchanged lines hidden (view full) ---

    89 /// @return Whether or not the solver should run a simplification phase
    90 /// prior to the main setup and reduction.
    91 ///
    92 /// HeuristicBase returns true from this method as it's a sensible default,
    93 /// however you can over-ride it in your derived class if you want different
    94 /// behaviour.
    95 bool solverRunSimplify() const { return true; }
    96
    97 /// \brief Decide whether a node should be optimally or heuristically
    		97 /// \brief Decide whether a node should be optimally or heuristically
    98 /// reduced.
    99 /// @return Whether or not the given node should be listed for optimal
    100 /// reduction (via R0, R1 or R2).
    101 ///
    102 /// HeuristicBase returns true for any node with degree less than 3. This is
    103 /// sane and sensible for many situations, but not all. You can over-ride
    104 /// this method in your derived class if you want a different selection
    105 /// criteria. Note however that your criteria for selecting optimal nodes
    106 /// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or
    107 /// higher should not be selected under any circumstances.
    		98 /// reduced.
    99 /// @return Whether or not the given node should be listed for optimal
    100 /// reduction (via R0, R1 or R2).
    101 ///
    102 /// HeuristicBase returns true for any node with degree less than 3. This is
    103 /// sane and sensible for many situations, but not all. You can over-ride
    104 /// this method in your derived class if you want a different selection
    105 /// criteria. Note however that your criteria for selecting optimal nodes
    106 /// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or
    107 /// higher should not be selected under any circumstances.
    108 bool shouldOptimallyReduce(Graph::NodeItr nItr) {
    109 if (g.getNodeDegree(nItr) < 3)
    		108 bool shouldOptimallyReduce(Graph::NodeId nId) {
    109 if (g.getNodeDegree(nId) < 3)
    110 return true;
    111 // else
    112 return false;
    113 }
    114
    115 /// \brief Add the given node to the list of nodes to be optimally reduced.
    		110 return true;
    111 // else
    112 return false;
    113 }
    114
    115 /// \brief Add the given node to the list of nodes to be optimally reduced.
    116 /// @param nItr Node iterator to be added.
    		116 /// @param nId Node id to be added.
    117 ///
    118 /// You probably don't want to over-ride this, except perhaps to record
    119 /// statistics before calling this implementation. HeuristicBase relies on
    120 /// its behaviour.
    		117 ///
    118 /// You probably don't want to over-ride this, except perhaps to record
    119 /// statistics before calling this implementation. HeuristicBase relies on
    120 /// its behaviour.
    121 void addToOptimalReduceList(Graph::NodeItr nItr) {
    122 optimalList.push_back(nItr);
    		121 void addToOptimalReduceList(Graph::NodeId nId) {
    122 optimalList.push_back(nId);
    123 }
    124
    125 /// \brief Initialise the heuristic.
    126 ///
    127 /// HeuristicBase iterates over all nodes in the problem and adds them to
    128 /// the appropriate list using addToOptimalReduceList or
    129 /// addToHeuristicReduceList based on the result of shouldOptimallyReduce.
    130 ///
    131 /// This behaviour should be fine for most situations.
    132 void setup() {
    133 for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
    134 nItr != nEnd; ++nItr) {
    		123 }
    124
    125 /// \brief Initialise the heuristic.
    126 ///
    127 /// HeuristicBase iterates over all nodes in the problem and adds them to
    128 /// the appropriate list using addToOptimalReduceList or
    129 /// addToHeuristicReduceList based on the result of shouldOptimallyReduce.
    130 ///
    131 /// This behaviour should be fine for most situations.
    132 void setup() {
    133 for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
    134 nItr != nEnd; ++nItr) {
    135 if (impl().shouldOptimallyReduce(nItr)) {
    136 addToOptimalReduceList(nItr);
    		135 if (impl().shouldOptimallyReduce(*nItr)) {
    136 addToOptimalReduceList(*nItr);
    137 } else {
    		137 } else {
    138 impl().addToHeuristicReduceList(nItr);
    		138 impl().addToHeuristicReduceList(*nItr);
    139 }
    140 }
    141 }
    142
    143 /// \brief Optimally reduce one of the nodes in the optimal reduce list.
    144 /// @return True if a reduction takes place, false if the optimal reduce
    145 /// list is empty.
    146 ///
    147 /// Selects a node from the optimal reduce list and removes it, applying
    148 /// R0, R1 or R2 as appropriate based on the selected node's degree.
    149 bool optimalReduce() {
    150 if (optimalList.empty())
    151 return false;
    152
    		139 }
    140 }
    141 }
    142
    143 /// \brief Optimally reduce one of the nodes in the optimal reduce list.
    144 /// @return True if a reduction takes place, false if the optimal reduce
    145 /// list is empty.
    146 ///
    147 /// Selects a node from the optimal reduce list and removes it, applying
    148 /// R0, R1 or R2 as appropriate based on the selected node's degree.
    149 bool optimalReduce() {
    150 if (optimalList.empty())
    151 return false;
    152
    153 Graph::NodeItr nItr = optimalList.front();
    		153 Graph::NodeId nId = optimalList.front();
    154 optimalList.pop_front();
    155
    		154 optimalList.pop_front();
    155
    156 switch (s.getSolverDegree(nItr)) {
    157 case 0: s.applyR0(nItr); break;
    158 case 1: s.applyR1(nItr); break;
    159 case 2: s.applyR2(nItr); break;
    		156 switch (s.getSolverDegree(nId)) {
    157 case 0: s.applyR0(nId); break;
    158 case 1: s.applyR1(nId); break;
    159 case 2: s.applyR2(nId); break;
    160 default: llvm_unreachable(
    161 "Optimal reductions of degree > 2 nodes is invalid.");
    162 }
    163
    164 return true;
    165 }
    166
    167 /// \brief Perform the PBQP reduction process.

    --- 11 unchanged lines hidden (view full) ---

    179 } else {
    180 finished = true;
    181 }
    182 }
    183 }
    184 }
    185
    186 /// \brief Add a node to the heuristic reduce list.
    		160 default: llvm_unreachable(
    161 "Optimal reductions of degree > 2 nodes is invalid.");
    162 }
    163
    164 return true;
    165 }
    166
    167 /// \brief Perform the PBQP reduction process.

    --- 11 unchanged lines hidden (view full) ---

    179 } else {
    180 finished = true;
    181 }
    182 }
    183 }
    184 }
    185
    186 /// \brief Add a node to the heuristic reduce list.
    187 /// @param nItr Node iterator to add to the heuristic reduce list.
    188 void addToHeuristicList(Graph::NodeItr nItr) {
    		187 /// @param nId Node id to add to the heuristic reduce list.
    188 void addToHeuristicList(Graph::NodeId nId) {
    189 llvm_unreachable("Must be implemented in derived class.");
    190 }
    191
    192 /// \brief Heuristically reduce one of the nodes in the heuristic
    193 /// reduce list.
    194 /// @return True if a reduction takes place, false if the heuristic reduce
    195 /// list is empty.
    196 bool heuristicReduce() {
    197 llvm_unreachable("Must be implemented in derived class.");
    198 return false;
    199 }
    200
    201 /// \brief Prepare a change in the costs on the given edge.
    		189 llvm_unreachable("Must be implemented in derived class.");
    190 }
    191
    192 /// \brief Heuristically reduce one of the nodes in the heuristic
    193 /// reduce list.
    194 /// @return True if a reduction takes place, false if the heuristic reduce
    195 /// list is empty.
    196 bool heuristicReduce() {
    197 llvm_unreachable("Must be implemented in derived class.");
    198 return false;
    199 }
    200
    201 /// \brief Prepare a change in the costs on the given edge.
    202 /// @param eItr Edge iterator.
    203 void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
    		202 /// @param eId Edge id.
    203 void preUpdateEdgeCosts(Graph::EdgeId eId) {
    204 llvm_unreachable("Must be implemented in derived class.");
    205 }
    206
    207 /// \brief Handle the change in the costs on the given edge.
    		204 llvm_unreachable("Must be implemented in derived class.");
    205 }
    206
    207 /// \brief Handle the change in the costs on the given edge.
    208 /// @param eItr Edge iterator.
    209 void postUpdateEdgeCostts(Graph::EdgeItr eItr) {
    		208 /// @param eId Edge id.
    209 void postUpdateEdgeCostts(Graph::EdgeId eId) {
    210 llvm_unreachable("Must be implemented in derived class.");
    211 }
    212
    213 /// \brief Handle the addition of a new edge into the PBQP graph.
    		210 llvm_unreachable("Must be implemented in derived class.");
    211 }
    212
    213 /// \brief Handle the addition of a new edge into the PBQP graph.
    214 /// @param eItr Edge iterator for the added edge.
    215 void handleAddEdge(Graph::EdgeItr eItr) {
    		214 /// @param eId Edge id for the added edge.
    215 void handleAddEdge(Graph::EdgeId eId) {
    216 llvm_unreachable("Must be implemented in derived class.");
    217 }
    218
    219 /// \brief Handle disconnection of an edge from a node.
    		216 llvm_unreachable("Must be implemented in derived class.");
    217 }
    218
    219 /// \brief Handle disconnection of an edge from a node.
    220 /// @param eItr Edge iterator for edge being disconnected.
    221 /// @param nItr Node iterator for the node being disconnected from.
    		220 /// @param eId Edge id for edge being disconnected.
    221 /// @param nId Node id for the node being disconnected from.
    222 ///
    223 /// Edges are frequently removed due to the removal of a node. This
    224 /// method allows for the effect to be computed only for the remaining
    225 /// node in the graph.
    		222 ///
    223 /// Edges are frequently removed due to the removal of a node. This
    224 /// method allows for the effect to be computed only for the remaining
    225 /// node in the graph.
    226 void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
    		226 void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) {
    227 llvm_unreachable("Must be implemented in derived class.");
    228 }
    229
    230 /// \brief Clean up any structures used by HeuristicBase.
    231 ///
    232 /// At present this just performs a sanity check: that the optimal reduce
    233 /// list is empty now that reduction has completed.
    234 ///

    --- 13 unchanged lines hidden ---     		227 llvm_unreachable("Must be implemented in derived class.");
    228 }
    229
    230 /// \brief Clean up any structures used by HeuristicBase.
    231 ///
    232 /// At present this just performs a sanity check: that the optimal reduce
    233 /// list is empty now that reduction has completed.
    234 ///

    --- 13 unchanged lines hidden ---