Introduction
In static scheduling, there are 2 predominant models for representation of a concurrent program :
In a (STG) model, a concurrent program is represented by an undirected connected graph, with the vertices as tasks and the edges indicating which tasks communicate. Source nodes represent starting points where program begins execution, while sink nodes represent termination. Between the two we have a set of interior nodes connected with weighted edges which correspond to the communication delay.
In a DAG model, the nodes are tasks, while the directed edges give both the precedence and the communication among the tasks. In the recent times, a hybrid representation has been developed integrating the above two schemes into a Temporal Communication Graph (TCG), allowing one to identify logically synchronous phases of communication and computation.
Classification of Static Scheduling Methods
Locally Optimal Solutions : Locally optimal scheduling methods rely on efficient search techniques using algorithms such as simulted annealing methods, mathematical programming methods and state space seacrh methods.
The simulated annealing methods perform the following steps :
Mathematical programming methods use linear, integer or non-linear programming methods to resolve task scheduling problems. The process consists of :
The state space search methods rely on branch and bound search search techniques to conduct a search of the solution space for scheduling of an app. on a given architecture. This is realized by building a search tree of possible schedules, defining a cost evaluation function and searching the tree for the best schedule. All these methods are time consuming and computation intensitive.
Sub-optimal solutions : These methods rely on the rules-of-thumb and heuristics to guide a scheduling process. List schedulingis the most popular technique inspite of poor performance in high communication delay situations. There are two simple steps:
Prognosis and future directions in Static Scheduling