Package edu.isi.pegasus.planner.selector.site.heft

Class Algorithm

java.lang.Object
edu.isi.pegasus.planner.selector.site.heft.Algorithm
public class Algorithm extends Object
The HEFT based site selector. The runtime for the job in seconds is picked from the pegasus profile key runtime in the transformation catalog for a transformation.

The data communication costs between jobs if scheduled on different sites is assumed to be fixed. Later on if required, the ability to specify this value will be exposed via properties.

The number of processors in a site is picked by the attribute idle-nodes associated with the vanilla jobmanager for a site in the site catalog.

There are two important differences with the algorithm cited in the HEFT paper. 

    - Our implementation uses downward ranks instead of the upward ranks as
      mentioned in the paper. The formulas have been updated accordingly.

    - During the processor selection phase, we do the simple selection and
      not follow the insertion based approach.
Version:
$Revision$
Author:
Karan Vahi
See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final float
    AVERAGE_BANDWIDTH
    The average bandwidth between the sites.
    static final float
    AVERAGE_DATA_SIZE_BETWEEN_JOBS
    The average data that is transferred in between 2 jobs in the workflow.
    static final int
    DEFAULT_NUMBER_OF_FREE_NODES
    The default number of nodes that are associated with a site if not found in the site catalog.
    private float
    mAverageCommunicationCost
    The average communication cost between nodes.
    static final long
    MAXIMUM_FINISH_TIME
    The maximum finish time possible for a job.
    private String
    mLabel
    The label of the workflow.
    private edu.isi.pegasus.common.logging.LogManager
    mLogger
    The handle to the LogManager
    private edu.isi.pegasus.planner.common.PegasusProperties
    mProps
    The handle to the properties.
    private String
    mRequestID
    The request id associated with the DAX.
    private Map
    mSiteMap
    Map containing the number of free nodes for each site.
    private List
    mSites
    The list of sites where the workflow can run.
    private edu.isi.pegasus.planner.catalog.site.classes.SiteStore
    mSiteStore
    Handle to the site catalog.
    private edu.isi.pegasus.planner.catalog.TransformationCatalog
    mTCHandle
    The handle to the transformation catalog.
    protected edu.isi.pegasus.planner.catalog.transformation.Mapper
    mTCMapper
    Handle to the TCMapper.
    private edu.isi.pegasus.planner.partitioner.graph.Graph
    mWorkflow
    The workflow in the graph format, that needs to be scheduled.
    static final String
    PROCESS_CATALOG_IMPL_PROPERTY
    The property that designates which Process catalog impl to pick up.
    static final String
    RUNTIME_PROFILE_KEY
    The pegasus profile key that gives us the expected runtime.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Algorithm(edu.isi.pegasus.planner.classes.PegasusBag bag)
    The default constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    protected float
    calculateAverageComputeTime(edu.isi.pegasus.planner.classes.Job job)
    Returns the average compute time in seconds for a job.
    protected long[]
    calculateEstimatedStartAndFinishTime(edu.isi.pegasus.planner.partitioner.graph.GraphNode node, String site)
    Estimates the start and finish time of a job on a site.
    protected float
    computeDownwardRank(edu.isi.pegasus.planner.partitioner.graph.GraphNode node)
    Computes the downward rank of a node.
    String
    description()
    This method returns a String describing the site selection technique that is being implemented by the implementing class.
    protected long
    getAvailableTime(String site, long readyTime)
    Returns the available time for a site.
    protected int
    getExpectedRuntime(edu.isi.pegasus.planner.classes.Job job, edu.isi.pegasus.planner.catalog.transformation.TransformationCatalogEntry entry)
    Return expected runtime.
    protected double
    getExpectedRuntimeFromAC(edu.isi.pegasus.planner.classes.Job job, edu.isi.pegasus.planner.catalog.transformation.TransformationCatalogEntry entry)
    Return expected runtime from the AC only if the process catalog is initialized.
    private float
    getFloatValue(Object key)
    A convenience method to get the intValue for the object passed.
    protected int
    getFreeNodesForSite(String site)
    Returns the freenodes for a site.
    long
    getMakespan()
    Returns the makespan of the scheduled workflow.
    String
    mapJob2ExecPool(edu.isi.pegasus.planner.classes.Job job, List pools)
    The call out to the site selector to determine on what pool the job should be scheduled.
    protected void
    populateSiteMap(List sites)
    Populates the number of free nodes for each site, by querying the Site Catalog.
    void
    schedule(edu.isi.pegasus.planner.classes.ADag dag, List sites)
    Schedules the workflow using the heft.
    void
    schedule(edu.isi.pegasus.planner.classes.ADag workflow, List sites, String label)
    Schedules the workflow according to the HEFT algorithm.
    protected void
    scheduleJob(String site, long start, long end)
    Schedules a job to a site.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • RUNTIME_PROFILE_KEY

      public static final String RUNTIME_PROFILE_KEY
      The pegasus profile key that gives us the expected runtime.
      See Also:

    • PROCESS_CATALOG_IMPL_PROPERTY

      public static final String PROCESS_CATALOG_IMPL_PROPERTY
      The property that designates which Process catalog impl to pick up.
      See Also:

    • AVERAGE_BANDWIDTH

      public static final float AVERAGE_BANDWIDTH
      The average bandwidth between the sites. In mega bytes/per second.
      See Also:

    • AVERAGE_DATA_SIZE_BETWEEN_JOBS

      public static final float AVERAGE_DATA_SIZE_BETWEEN_JOBS
      The average data that is transferred in between 2 jobs in the workflow. In megabytes.
      See Also:

    • DEFAULT_NUMBER_OF_FREE_NODES

      public static final int DEFAULT_NUMBER_OF_FREE_NODES
      The default number of nodes that are associated with a site if not found in the site catalog.
      See Also:

    • MAXIMUM_FINISH_TIME

      public static final long MAXIMUM_FINISH_TIME
      The maximum finish time possible for a job.
      See Also:

    • mAverageCommunicationCost

      private float mAverageCommunicationCost
      The average communication cost between nodes.

    • mWorkflow

      private edu.isi.pegasus.planner.partitioner.graph.Graph mWorkflow
      The workflow in the graph format, that needs to be scheduled.

    • mSiteStore

      private edu.isi.pegasus.planner.catalog.site.classes.SiteStore mSiteStore
      Handle to the site catalog.

    • mSites

      private List mSites
      The list of sites where the workflow can run.

    • mSiteMap

      private Map mSiteMap
      Map containing the number of free nodes for each site. The key is the site name, and value is a Site object.

    • mTCMapper

      protected edu.isi.pegasus.planner.catalog.transformation.Mapper mTCMapper
      Handle to the TCMapper.

    • mLogger

      private edu.isi.pegasus.common.logging.LogManager mLogger
      The handle to the LogManager

    • mProps

      private edu.isi.pegasus.planner.common.PegasusProperties mProps
      The handle to the properties.

    • mRequestID

      private String mRequestID
      The request id associated with the DAX.

    • mLabel

      private String mLabel
      The label of the workflow.

    • mTCHandle

      private edu.isi.pegasus.planner.catalog.TransformationCatalog mTCHandle
      The handle to the transformation catalog.

  • Constructor Details

    • Algorithm

      public Algorithm(edu.isi.pegasus.planner.classes.PegasusBag bag)
      The default constructor.
      Parameters:
      bag - the bag of Pegasus related objects.

  • Method Details

    • schedule

      public void schedule(edu.isi.pegasus.planner.classes.ADag dag, List sites)
      Schedules the workflow using the heft.
      Parameters:
      dag - the ADag object containing the abstract workflow that needs to be mapped.
      sites - the list of candidate sites where the workflow can potentially execute.

    • schedule

      public void schedule(edu.isi.pegasus.planner.classes.ADag workflow, List sites, String label)
      Schedules the workflow according to the HEFT algorithm.
      Parameters:
      workflow - the workflow that has to be scheduled.
      sites - the list of candidate sites where the workflow can potentially execute.
      label - the label of the workflow

    • getMakespan

      public long getMakespan()
      Returns the makespan of the scheduled workflow. It is maximum of the actual finish times for the leaves of the scheduled workflow.
      Returns:
      long the makespan of the workflow.

    • calculateEstimatedStartAndFinishTime

      protected long[] calculateEstimatedStartAndFinishTime(edu.isi.pegasus.planner.partitioner.graph.GraphNode node, String site)
      Estimates the start and finish time of a job on a site.
      Parameters:
      node - the node that is being scheduled
      site - the site for which the finish time is reqd.
      Returns:
      long[0] the estimated start time. long[1] the estimated finish time.

    • computeDownwardRank

      protected float computeDownwardRank(edu.isi.pegasus.planner.partitioner.graph.GraphNode node)
      Computes the downward rank of a node.

      The downward rank of node i is _ ___ max { rank( n ) + w + c } j E pred( i ) d j j ji

      Parameters:
      node - the GraphNode whose rank needs to be computed.
      Returns:
      computed rank.

    • calculateAverageComputeTime

      protected float calculateAverageComputeTime(edu.isi.pegasus.planner.classes.Job job)
      Returns the average compute time in seconds for a job.
      Parameters:
      job - the job whose average compute time is to be computed.
      Returns:
      the weighted compute time in seconds.

    • getExpectedRuntime

      protected int getExpectedRuntime(edu.isi.pegasus.planner.classes.Job job, edu.isi.pegasus.planner.catalog.transformation.TransformationCatalogEntry entry)
      Return expected runtime.
      Parameters:
      job - the job in the workflow.
      entry - the TransformationCatalogEntry object.
      Returns:
      the runtime in seconds.

    • getExpectedRuntimeFromAC

      protected double getExpectedRuntimeFromAC(edu.isi.pegasus.planner.classes.Job job, edu.isi.pegasus.planner.catalog.transformation.TransformationCatalogEntry entry)
      Return expected runtime from the AC only if the process catalog is initialized. Since Pegasus 3.0 release it always returns -1.
      Parameters:
      job - the job in the workflow.
      entry - the TC entry
      Returns:
      the runtime in seconds.

    • populateSiteMap

      protected void populateSiteMap(List sites)
      Populates the number of free nodes for each site, by querying the Site Catalog.
      Parameters:
      sites - list of sites.

    • getFreeNodesForSite

      protected int getFreeNodesForSite(String site)
      Returns the freenodes for a site.
      Parameters:
      site - the site identifier.
      Returns:
      number of nodes

    • scheduleJob

      protected void scheduleJob(String site, long start, long end)
      Schedules a job to a site.
      Parameters:
      site - the site at which to schedule
      start - the start time for job
      end - the end time of job

    • getAvailableTime

      protected long getAvailableTime(String site, long readyTime)
      Returns the available time for a site.
      Parameters:
      site - the site at which you want to schedule the job.
      readyTime - the time at which all the data reqd by the job will arrive at site.
      Returns:
      the available time of the site.

    • description

      public String description()
      This method returns a String describing the site selection technique that is being implemented by the implementing class.
      Returns:
      String

    • mapJob2ExecPool

      public String mapJob2ExecPool(edu.isi.pegasus.planner.classes.Job job, List pools)
      The call out to the site selector to determine on what pool the job should be scheduled.
      Parameters:
      job - Job the Job object corresponding to the job whose execution pool we want to determine.
      pools - the list of String objects representing the execution pools that can be used.
      Returns:
      if the pool is found to which the job can be mapped, a string of the form executionpool:jobmanager where the jobmanager can be null. If the pool is not found, then set poolhandle to NONE. null - if some error occured .

    • getFloatValue

      private float getFloatValue(Object key)
      A convenience method to get the intValue for the object passed.
      Parameters:
      key - the key to be converted
      Returns:
      the floatt value if object an integer, else -1