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