This module implements scheduling algorithms which are applied to general scheduling problems as described by the data type in this module. Acyclic dataflow graphs and basic blocks can be easily mapped to these problems, which additionally allow to add runtimes and required ressources for each node.
Type  Description 


A scheduling problem sp is given by an acyclic graph that is determined by its set of edges sp.dependences that represent dependencies. For each node, sp.runtime and sp.resType specify its runtime and used resource which is expected to be the kind of a functional unit that will be allocated for executing the operation. Finally, sp.numNodes and sp.numResTypes clearly denote the number of nodes and the number of function units in total. Caution: it is not required that the nodes are 0..sp.numNodes1 which means that holes in the interval are allowed. 






Function or value  Description 

AllenKennedy algorithm [AlKe87] for loop distribution and parallelization The algorithm considers a loop nesting with loop variables i[1],...,i[n] and a loop body with a sequence of instructions I[1],...,I[m] that have loopcarried and inner loop dependencies which are expressed with their reduced dependency graph (RGD). The problem is given by the RDG whose vertices are the names of the instructions Ik of the loop body and whose edges are the dependencies which are labeled with a vector of length n that denotes the a loopcarried dependency on loop k if entry k is nonzero, and otherwise the dependency is an inner loop dependency.

Full Usage:
ForceDirectedScheduling beQuiet sp
Parameters:
bool
sp : SchedulingProblem
Returns: Schedule

Force directed scheduling generates a schedule with the minimal runtime as determined by ASAP and ALAP scheduling, but then schedules the instructions such that the use of the resources is as much as possible evenly distributed over the runtime to heuristically minimize the resources.

Full Usage:
GenerateScheduleILP sp maxRes
Parameters:
SchedulingProblem
maxRes : int[]
Returns: string[] * string[] * string[] * string[]

compute an ILP problem for minimal time resource aware scheduling

Full Usage:
LinearSchedule beQuiet sp maxRes
Parameters:
bool
sp : SchedulingProblem
maxRes : int[]
Returns: Schedule

Linear scheduling is guaranteed to generate a schedule that does not use more than the given upper bounds of the resources

Full Usage:
ListSchedule beQuiet sp maxRes
Parameters:
bool
sp : SchedulingProblem
maxRes : int[]
Returns: Schedule

List scheduling is guaranteed to generate a schedule that does not use more than the given upper bounds of the resources


print a schedule

Full Usage:
PriorityBasedScheduling pL
Parameters:
(int * int) list
Returns: int * (bool * (int * int) * (int * int) list) list

PriorityBasedScheduling implements a preemptive prioritybased scheduler. The processes are given in a sorted list pL where processes with higher priority occur first. Each process is described by a pair (c,p) where c is the number of cycles required by this process within each period p. It is known that a schedule exists if and only if the priorities are determined such that processes with lesser period have higher priority. The function returns a pair (period,schedules) such that period is the least common multiple of the periods of the processes and schedules contains for each process a tuple (f,(c,p),psched) where f is true if the deadlines are met for the process, (c,p) is the definition of the process, and psched defines the intervals where the process owns the CPU.

Full Usage:
ScheduleALAP beQuiet sp
Parameters:
bool
sp : SchedulingProblem
Returns: Schedule

compute an ALAP schedule by scheduling nodes as late as possible within the minimal runtime of an ASAP schedule (assuming infinite resources)

Full Usage:
ScheduleASAP beQuiet sp
Parameters:
bool
sp : SchedulingProblem
Returns: Schedule

compute an ASAP schedule by scheduling nodes as soon as the input values are available for them assuming infinite resources




