Heuristic Functions

Algorithm Heuristic Functions

The A* implementation that was used in this algorithm relied on a set of heuristic functions that determined a partial schedule's cost function; this cost function represents the lower bound of the finishing time of a partial schedule.

The lower bound is calculated by finding the maximum of all three heuristic functions to set an underestimate of the potential lower bound.

costFunction = maximum{maxDRT, maxBL, maxIdleTime}

---

1. Bottom Level

This function is based on tasks that have already been scheduled. The bottom level cost encapsulates the longest path in the task graph for the current partial schedule. It uses the critical path of the next node to be scheduled. This way, the lower bound can be determined by the longest path to the schedule without communication cost.

f_BL(s) = max_{n∈partialSchedule}{t_s(n) + bl_w(n)}

where t_s(n) is the starting time of node n that is the newest node being scheduled.

2. Data Ready Time

This function acknowledges the potential nodes that are left to be scheduled. Taking the newest scheduled node, it iterates through all the nodes that are eligible to be scheduled, denoted by a list named free. Nodes are placed into free only if they either have no parents, or all their parents have already been scheduled (and therefore all of their dependencies are satisfied).

With each node in free, this function finds the earliest time that it is able to be scheduled without breaching any dependencies. This is the earliest time that the node is able to be scheduled, also called the earliest data ready time, and can be denoted by:

t_dr(n)

The cost function of DRT is calculated by this data ready time and the addition of the bottom level (the critical path) of that free node. After all nodes have been iterated from free, the maximum data ready time is taken as a representation of the lower bound for the start time of any task.

f_DRT(s) = max_n∈free{t_dr(n) + bl_w(n)}

3. Idle Time

Now that both cases of already scheduled nodes and potential nodes to be scheduled have been taken into account with the other two functions, the Idle Time cost function is used to compare situations where nodes that have been scheduled in a processor are not back-to-back (i.e, there gaps/idle times within the processor).

In this case, we can use the combined weights of all nodes in the graph in addition to its current idle time, and divide it with the number of processors to estimate the final schedule length. While this may be accurate at times, notr that this can only be quite close if there is good load balancing (where communication costs are low or the number of edges is small).

This idle time cost function is denoted by the equation below:

f_idle-time(s) = ((sum of weights of all nodes) + (total idle time present in the partial schedule)) / (number of processors)

---

Using these three heuristic functions, the maximum of these values are taken in order to obtain an underestimate of the finishing scheduling time. The priority queue will be sorted in accordance with each partial schedule's cost functions, as explained in the Algorithms section of the wiki.

costFunction_{partialSchedule}(s) = max{f_BL(s), f_DRT(s), f_idle-time(s)}