iengine.hpp

00001 /*
00002 This file is part of GraphLab.
00003 
00004 GraphLab is free software: you can redistribute it and/or modify
00005 it under the terms of the GNU Lesser General Public License as 
00006 published by the Free Software Foundation, either version 3 of 
00007 the License, or (at your option) any later version.
00008 
00009 GraphLab is distributed in the hope that it will be useful,
00010 but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012 GNU Lesser General Public License for more details.
00013 
00014 You should have received a copy of the GNU Lesser General Public 
00015 License along with GraphLab.  If not, see <http://www.gnu.org/licenses/>.
00016 */
00017 
00018 /* \file iengine.hpp
00019    \brief The file containing the iengine description
00020    
00021    This file contains the description of the engine interface.  All
00022    graphlab engines (single_threaded, multi_threaded, distributed, ...)
00023    should satisfy the functionality described below.
00024 */
00025 
00026 #ifndef GRAPHLAB_IENGINE_HPP
00027 #define GRAPHLAB_IENGINE_HPP
00028 
00029 #include <graphlab/graph/graph.hpp>
00030 #include <graphlab/schedulers/ischeduler.hpp>
00031 #include <graphlab/monitoring/imonitor.hpp>
00032 #include <graphlab/metrics/metrics.hpp>
00033 #include <graphlab/scope/iscope.hpp>
00034 #include <graphlab/shared_data/glshared.hpp>
00035 namespace graphlab {
00036   
00037   /**
00038    * \brief the reasons for execution completion.
00039    *
00040    * Because there are several reasons why the graphlab engine might
00041    * terminate the exec_status value is returned from the start
00042    * function after completing execution. 
00043    *
00044    */
00045   enum exec_status {
00046 
00047     EXEC_UNSET,  /** The default termination reason */
00048 
00049     EXEC_TASK_DEPLETION, /**<Execution completed successfully due to
00050                             task depletion */
00051 
00052     EXEC_TERM_FUNCTION,  /**< Execution completed successfully due to
00053                             termination function. */
00054 
00055     EXEC_TIMEOUT,       /**< The execution completed after timing
00056                            out */
00057 
00058     EXEC_TASK_BUDGET_EXCEEDED, /**< The execution completed because
00059                                   the maximum number of tasks was
00060                                   exceeded */
00061 
00062     EXEC_FORCED_ABORT,     /**< the engine was stopped by calling force
00063                              abort */
00064                              
00065     EXEC_EXCEPTION        /**< the engine was stopped by an exception */
00066   };
00067   
00068 
00069   
00070   /**
00071      \brief The abstract interface of a GraphLab engine.
00072      The graphlab engine interface describes the core functionality
00073      provided by all graphlab engines.  The engine is templatized over
00074      the type of graph.
00075      
00076      The GraphLab engines are a core element of the GraphLab
00077      framework.  The engines are responsible for applying a the update
00078      tasks and sync operations to a graph and shared data using the
00079      scheduler to determine the update schedule. This class provides a
00080      generic interface to interact with engines written to execute on
00081      different platforms.
00082      
00083      While users are free to directly instantiate the engine of their
00084      choice we highly recommend the use of the \ref core data
00085      structure to manage the creation of engines. Alternatively, users
00086      can use the 
00087      \ref gl_new_engine "graphlab::engine_factory::new_engine"
00088      static functions to create
00089      engines directly from configuration strings.
00090   */
00091   template<typename Graph>
00092   class iengine {
00093   public:
00094 
00095     //! The type of graph that the engine operates on
00096     typedef Graph graph_type;
00097 
00098     //! The type of update task
00099     typedef update_task<Graph> update_task_type;
00100 
00101     //! The type of update function
00102     typedef typename update_task_type::update_function_type 
00103                                                update_function_type;
00104 
00105     //! The type of scheduler
00106     typedef ischeduler<Graph> ischeduler_type;
00107 
00108     //! The type of monitor
00109     typedef imonitor<Graph> imonitor_type;
00110 
00111     //! The type of scope 
00112     typedef iscope<Graph> iscope_type;
00113 
00114     typedef void(*sync_function_type)(iscope_type& scope,
00115                                       any& accumulator);
00116 
00117     typedef void(*merge_function_type)(any& merge_dest,
00118                                        const any& merge_src);
00119 
00120     
00121     /**
00122      * The termination function is a function that reads the shared
00123      * data and returns true if the engine should terminate execution.
00124      * The termination function is called at fixed millisecond
00125      * intervals and therefore the engine may continue to execute even
00126      * after a termination function evaluates to true.  Because
00127      * termination functions are executed frequently and cannot
00128      * directly contribut to the computation, they should return
00129      * quickly.
00130      */
00131     typedef bool (*termination_function_type) ();
00132     
00133 
00134     //! Virtual destructor required for inheritance 
00135     virtual ~iengine() {};
00136 
00137     //! get the number of cpus
00138     virtual size_t get_ncpus() const = 0;
00139 
00140 
00141     /**
00142      * \brief Set the default scope range.
00143      *
00144      * The default scope range determines the locking extent of an
00145      * update function. See \ref Scopes for details.
00146      *
00147      * \param default_scope_range can take on any of the values
00148      * described in \ref scope_range
00149      *
00150      */
00151     virtual void set_default_scope(scope_range::scope_range_enum default_scope_range) = 0;
00152     
00153     /**
00154      * \brief Start the engine execution.
00155      *
00156      * This \b blocking function starts the engine and does not
00157      * return until either one of the termination conditions evaluate
00158      * true or the scheduler has no tasks remaining.
00159      */
00160     virtual void start() = 0;
00161 
00162 
00163     /**
00164      * \brief Force engine to terminate immediately.
00165      *
00166      * This function is used to stop the engine execution by forcing
00167      * immediate termination.  Any existing update tasks will finish
00168      * but no new update tasks will be started and the call to start()
00169      * will return.
00170      */
00171     virtual void stop() = 0;
00172 
00173     
00174     /**
00175      * \brief Describe the reason for termination.
00176      *
00177      * Return the reason for the last termination.
00178      */
00179     virtual exec_status last_exec_status() const = 0;
00180 
00181 
00182     
00183     /**
00184      * \brief Get the number of updates executed by the engine.
00185      *
00186      * This function returns the numbe of updates executed by the last
00187      * run of this engine.
00188      * 
00189      * \return the total number of updates
00190      */
00191     virtual size_t last_update_count() const = 0;
00192 
00193         
00194     /**
00195      * \brief Register a monitor with an engine. 
00196      *
00197      * A monitor tracks the execution of an engine can be useful when
00198      * debugging. 
00199      */
00200     virtual void register_monitor(imonitor_type* listener) = 0;
00201     
00202     /**
00203      * \brief Adds an update task with a particular priority.
00204      * This function is forwarded to the scheduler.
00205      */
00206     virtual void add_task(update_task_type task, double priority) = 0;
00207 
00208     /**
00209      * \brief Add an update function to a particular vertex.
00210      */
00211     virtual void add_vtask(vertex_id_t vid, 
00212                           update_function_type fun, 
00213                           double priority = 1.0) {
00214       add_task(update_task_type(vid, fun),  priority);
00215     }
00216 
00217     /**
00218      * \brief Creates a collection of tasks on all the vertices in
00219      * 'vertices', and all with the same update function and priority
00220      * This function is forwarded to the scheduler.
00221      */
00222     virtual void add_tasks(const std::vector<vertex_id_t>& vertices,
00223                            update_function_type func, double priority) = 0;
00224 
00225     /**
00226      * \brief Creates a collection of tasks on all the vertices in the graph,
00227      * with the same update function and priority
00228      * This function is forwarded to the scheduler.
00229      */
00230     virtual void add_task_to_all(update_function_type func,
00231                                  double priority) = 0;
00232     /**
00233      * \brief associate a termination function with this engine.
00234      *
00235      * An engine can typically have many termination functions
00236      * associated with it. A termination function is a function which
00237      * takes a constant reference to the shared data and returns a
00238      * boolean which is true if the engine should terminate execution.
00239      *
00240      * A termination function has the following type:
00241      * \code
00242      * bool term_fun(const ishared_data_type* shared_data)
00243      * \endcode
00244      */
00245     virtual void add_terminator(termination_function_type term) = 0;
00246 
00247     //!  remove all associated termination functions
00248     virtual void clear_terminators() = 0;
00249     
00250 
00251     /**
00252      * Set whether sched yield should be used when waiting on new
00253      * jobs
00254      */
00255     virtual void set_sched_yield(bool value) { };
00256 
00257     /**
00258      * Set whether cpu affinities should be used.
00259      */
00260     virtual void set_cpu_affinities(bool value) { };
00261 
00262     
00263     
00264     /**
00265      *  \brief The timeout is the total
00266      *  ammount of time in seconds that the engine may run before
00267      *  exeuction is automatically terminated.
00268      */
00269     virtual void set_timeout(size_t timeout_secs) = 0;
00270     
00271     /**
00272      * \brief set a limit on the number of tasks that may be executed.
00273      * 
00274      * By once the engine has achived the max_task parameter execution
00275      * will be terminated. If max_tasks is set to zero then the
00276      * task_budget is ignored.  If max_tasks is greater than zero than
00277      * the value of max tasks is used.  Note that if max_task is
00278      * nonzero the engine encurs the cost of an additional atomic
00279      * operation in the main loop potentially reducing the overall
00280      * parallel performance.
00281      */
00282     virtual void set_task_budget(size_t max_tasks) = 0;
00283 
00284 
00285     /** \brief Update the scheduler options.  */
00286     virtual void set_scheduler_options(const scheduler_options& opts) = 0;
00287 
00288     /** \brief Update the engine options.  */
00289     virtual void set_engine_options(const scheduler_options& opts) = 0;
00290 
00291 
00292     /**
00293      * \brief Registers a sync with the engine.
00294      *
00295      * Registers a sync with the engine.
00296      * The sync will be performed approximately every "interval" updates,
00297      * and will perform a reduction over all vertices from rangelow
00298      * to rangehigh inclusive.
00299      * The merge function may be NULL, in which it will not be used.
00300      * However, it is highly recommended to provide a merge function since
00301      * this allow the sync operation to be parallelized.
00302      *
00303       * The sync operation is guaranteed to be strictly sequentially consistent
00304      * with all other execution.
00305      *
00306      * \param shared The shared variable to synchronize
00307      * \param sync The reduction function
00308      * \param apply The final apply function which writes to the shared value
00309      * \param zero The initial zero value passed to the reduction
00310      * \param sync_interval Frequency at which the sync is initiated.
00311      *                      Corresponds approximately to the number of
00312      *                     update function calls before the sync is reevaluated.
00313      *                     If 0, the sync will only be evaluated once
00314      *                     at engine start,  and will never be evaluated again.
00315      *                     Defaults to 0.
00316      * \param merge Combined intermediate reduction value. defaults to NULL.
00317      *              in which case, it will not be used.
00318      * \param rangelow he lower range of vertex id to start syncing.
00319      *                 The range is inclusive. i.e. vertex with id 'rangelow'
00320      *                 and vertex with id 'rangehigh' will be included.
00321      *                 Defaults to 0.
00322      * \param rangehigh The upper range of vertex id to stop syncing.
00323      *                  The range is inclusive. i.e. vertex with id 'rangelow'
00324      *                  and vertex with id 'rangehigh' will be included.
00325      *                  Defaults to infinity.
00326      */
00327     virtual void set_sync(glshared_base& shared,
00328                           sync_function_type sync,
00329                           glshared_base::apply_function_type apply,
00330                           const any& zero,
00331                           size_t sync_interval = 0,
00332                           merge_function_type merge = NULL,
00333                           vertex_id_t rangelow = 0,
00334                           vertex_id_t rangehigh = -1) = 0;
00335 
00336     /**
00337      * Performs a sync immediately. This function requires that the shared
00338      * variable already be registered with the engine.
00339      */
00340     virtual void sync_now(glshared_base& shared) = 0;
00341     
00342     // Convenience function.
00343     static std::string exec_status_as_string(exec_status es) {
00344       switch(es) {
00345       case EXEC_UNSET: return "engine not run!";
00346       case EXEC_FORCED_ABORT: return "forced abort";
00347       case EXEC_TASK_BUDGET_EXCEEDED: return "budget exceed";
00348       case EXEC_TERM_FUNCTION: return "termination function";
00349       case EXEC_TASK_DEPLETION: return "task depletion (natural)";
00350       case EXEC_TIMEOUT: return "timeout";
00351       case EXEC_EXCEPTION: return "exception";
00352       };
00353       return "unknown";
00354     }
00355 
00356     /**
00357      * Return the metrics information logged by the engine.
00358      * \see dump_metrics reset_metrics
00359      */
00360     virtual metrics get_metrics() {
00361       return metrics();
00362     }
00363 
00364     /**
00365      * Clears all logged metrics
00366      * \see dump_metrics get_metrics
00367      */
00368     virtual void reset_metrics() { }
00369     
00370     /**
00371      * Writes out the metrics information logged by the engine
00372      * and all subordinate classes.
00373      *
00374      * Engine writers should note that for dump_metrics() to work,
00375      * the engine only has to implement get_metrics()
00376      * and reset_metrics(). Default behavior is to report the metrics
00377      * returned by get_metrics() and call reset_metrics().
00378      * This behavior may be overridden by implementing this function.
00379      * 
00380      * \see get_metrics reset_metrics
00381      */
00382     virtual void report_metrics(imetrics_reporter &reporter) {
00383       get_metrics().report(reporter);
00384     }
00385     
00386   };
00387 
00388 }
00389 
00390 #endif
00391