1 /** 2 * 3 * Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU) 4 * info_at_agrum_dot_org 5 * 6 * This library is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU Lesser General Public License as published by 8 * the Free Software Foundation, either version 3 of the License, or 9 * (at your option) any later version. 10 * 11 * This library is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public License 17 * along with this library. If not, see <http://www.gnu.org/licenses/>. 18 * 19 */ 20 21 22 /** @file 23 * @brief a scheduler that executes any available operation (chosen aribtrarily) 24 * 25 * @author Christophe GONZALES(_at_AMU) and Pierre-Henri WUILLEMIN(_at_LIP6) 26 */ 27 28 #ifndef DOXYGEN_SHOULD_SKIP_THIS 29 30 # include <agrum/agrum.h> 31 # include <limits> 32 33 namespace gum { 34 35 /// default constructor 36 template < typename GUM_SCALAR > SchedulerBasic()37 SchedulerBasic< GUM_SCALAR >::SchedulerBasic() : Scheduler< GUM_SCALAR >() { 38 // for debugging purposes 39 GUM_CONSTRUCTOR(SchedulerBasic); 40 } 41 42 /// copy constructor 43 template < typename GUM_SCALAR > SchedulerBasic(const SchedulerBasic<GUM_SCALAR> & from)44 SchedulerBasic< GUM_SCALAR >::SchedulerBasic(const SchedulerBasic< GUM_SCALAR >& from) : 45 Scheduler< GUM_SCALAR >(from) { 46 // for debugging purposes 47 GUM_CONS_CPY(SchedulerBasic); 48 } 49 50 /// destructor 51 template < typename GUM_SCALAR > ~SchedulerBasic()52 SchedulerBasic< GUM_SCALAR >::~SchedulerBasic() { 53 // for debugging purposes 54 GUM_DESTRUCTOR(SchedulerBasic); 55 } 56 57 /// virtual constructor 58 template < typename GUM_SCALAR > newFactory()59 SchedulerBasic< GUM_SCALAR >* SchedulerBasic< GUM_SCALAR >::newFactory() const { 60 return new SchedulerBasic< GUM_SCALAR >(*this); 61 } 62 63 /// execute all the operations of a given schedule 64 template < typename GUM_SCALAR > execute(Schedule<GUM_SCALAR> & schedule)65 bool SchedulerBasic< GUM_SCALAR >::execute(Schedule< GUM_SCALAR >& schedule) { 66 const NodeSet& available = schedule.availableOperations(); 67 68 while (!available.empty()) { 69 for (typename NodeSet::const_iterator_safe iter = available.beginSafe(); 70 iter != available.endSafe(); 71 ++iter) { 72 schedule.execute(*iter); 73 } 74 } 75 76 return (schedule.scheduling_dag().size() == 0); 77 } 78 79 /// execute only k operations of a given schedule (default k = 1) 80 template < typename GUM_SCALAR > execute(Schedule<GUM_SCALAR> & schedule,Size k)81 bool SchedulerBasic< GUM_SCALAR >::execute(Schedule< GUM_SCALAR >& schedule, Size k) { 82 const NodeSet& available = schedule.availableOperations(); 83 84 while (!available.empty() && k) { 85 for (typename NodeSet::const_iterator_safe iter = available.beginSafe(); 86 iter != available.endSafe() && k; 87 ++iter, --k) { 88 schedule.execute(*iter); 89 } 90 } 91 92 return !k || (schedule.scheduling_dag().size() == 0); 93 } 94 95 /** @bried returns an estimation of the number of elementary operations needed 96 * to perform a given schedule */ 97 template < typename GUM_SCALAR > nbOperations(const Schedule<GUM_SCALAR> & schedule)98 float SchedulerBasic< GUM_SCALAR >::nbOperations(const Schedule< GUM_SCALAR >& schedule) const { 99 NodeSet available = schedule.availableOperations(); 100 DAG dag = schedule.scheduling_dag(); 101 float nb_operations = 0; 102 103 while (!available.empty()) { 104 for (typename NodeSet::const_iterator_safe iter = available.beginSafe(); 105 iter != available.endSafe(); 106 ++iter) { 107 NodeId id = *iter; 108 nb_operations += schedule.nbOperations(id); 109 const NodeSet& children = dag.children(id); 110 111 for (typename NodeSet::const_iterator_safe iter_children = children.beginSafe(); 112 iter_children != children.endSafe(); 113 ++iter_children) { 114 if (dag.parents(*iter_children).size() == 1) { available.insert(*iter_children); } 115 } 116 117 dag.eraseNode(id); 118 available.erase(iter); 119 } 120 } 121 122 return nb_operations; 123 } 124 125 /** @bried returns an estimation of the number of elementary operations needed 126 * to perform the k first ScheduleOperations of a given schedule */ 127 template < typename GUM_SCALAR > nbOperations(const Schedule<GUM_SCALAR> & schedule,Size k)128 float SchedulerBasic< GUM_SCALAR >::nbOperations(const Schedule< GUM_SCALAR >& schedule, 129 Size k) const { 130 NodeSet available = schedule.availableOperations(); 131 DAG dag = schedule.scheduling_dag(); 132 float nb_operations = 0; 133 134 while (!available.empty() && k) { 135 for (typename NodeSet::const_iterator_safe iter = available.beginSafe(); 136 iter != available.endSafe() && k; 137 ++iter, --k) { 138 NodeId id = *iter; 139 nb_operations += schedule.nbOperations(id); 140 const NodeSet& children = dag.children(id); 141 142 for (typename NodeSet::const_iterator_safe iter_children = children.beginSafe(); 143 iter_children != children.endSafe(); 144 ++iter_children) { 145 if (dag.parents(*iter_children).size() == 1) { available.insert(*iter_children); } 146 } 147 148 dag.eraseNode(id); 149 available.erase(iter); 150 } 151 } 152 153 return nb_operations; 154 } 155 156 /// returns the memory consumption used during the execution of a schedule 157 template < typename GUM_SCALAR > 158 std::pair< long, long > memoryUsage(const Schedule<GUM_SCALAR> & schedule)159 SchedulerBasic< GUM_SCALAR >::memoryUsage(const Schedule< GUM_SCALAR >& schedule) const { 160 NodeSet available = schedule.availableOperations(); 161 DAG dag = schedule.scheduling_dag(); 162 long max_memory = 0; 163 long current_memory = 0; 164 165 while (!available.empty()) { 166 for (typename NodeSet::const_iterator_safe iter = available.beginSafe(); 167 iter != available.endSafe(); 168 ++iter) { 169 NodeId id = *iter; 170 171 std::pair< long, long > mem_op = schedule.memoryUsage(id); 172 173 if ((std::numeric_limits< long >::max() - current_memory < mem_op.first) 174 || (std::numeric_limits< long >::max() - current_memory < mem_op.second)) { 175 GUM_ERROR(OutOfBounds, "memory usage out of long int range") 176 } 177 178 if (current_memory + mem_op.first > max_memory) max_memory = current_memory + mem_op.first; 179 180 current_memory += mem_op.second; 181 182 const NodeSet& children = dag.children(id); 183 184 for (typename NodeSet::const_iterator_safe iter_children = children.beginSafe(); 185 iter_children != children.endSafe(); 186 ++iter_children) { 187 if (dag.parents(*iter_children).size() == 1) { available.insert(*iter_children); } 188 } 189 190 dag.eraseNode(id); 191 available.erase(iter); 192 } 193 } 194 195 return std::pair< long, long >(max_memory, current_memory); 196 } 197 198 /** @brief returns the memory consumption used during the execution of the 199 * k first ScheduleOperations of a given schedule */ 200 template < typename GUM_SCALAR > 201 std::pair< long, long > memoryUsage(const Schedule<GUM_SCALAR> & schedule,Size k)202 SchedulerBasic< GUM_SCALAR >::memoryUsage(const Schedule< GUM_SCALAR >& schedule, 203 Size k) const { 204 NodeSet available = schedule.availableOperations(); 205 DAG dag = schedule.scheduling_dag(); 206 long max_memory = 0; 207 long current_memory = 0; 208 209 while (!available.empty() && k) { 210 for (typename NodeSet::const_iterator_safe iter = available.beginSafe(); 211 iter != available.endSafe() && k; 212 ++iter, --k) { 213 NodeId id = *iter; 214 215 std::pair< long, long > mem_op = schedule.memoryUsage(id); 216 217 if ((std::numeric_limits< long >::max() - current_memory < mem_op.first) 218 || (std::numeric_limits< long >::max() - current_memory < mem_op.second)) { 219 GUM_ERROR(OutOfBounds, "memory usage out of long int range") 220 } 221 222 if (current_memory + mem_op.first > max_memory) max_memory = current_memory + mem_op.first; 223 224 current_memory += mem_op.second; 225 226 const NodeSet& children = dag.children(id); 227 228 for (typename NodeSet::const_iterator_safe iter_children = children.beginSafe(); 229 iter_children != children.endSafe(); 230 ++iter_children) { 231 if (dag.parents(*iter_children).size() == 1) { available.insert(*iter_children); } 232 } 233 234 dag.eraseNode(id); 235 available.erase(iter); 236 } 237 } 238 239 return std::pair< long, long >(max_memory, current_memory); 240 } 241 242 } /* namespace gum */ 243 244 #endif /* DOXYGEN_SHOULD_SKIP_THIS */ 245